src/IntPolyh/IntPolyh_Intersection.cxx

   1 // Created on: 1999-03-03
   2 // Created by: Fabrice SERVANT
   3 // Copyright (c) 1999-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17
  18 #include <IntPolyh_Intersection.hxx>
  19
  20 #include <Adaptor3d_Surface.hxx>
  21
  22 #include <IntPolyh_Couple.hxx>
  23 #include <IntPolyh_CoupleMapHasher.hxx>
  24 #include <IntPolyh_MaillageAffinage.hxx>
  25 #include <IntPolyh_SectionLine.hxx>
  26 #include <IntPolyh_StartPoint.hxx>
  27 #include <IntPolyh_Tools.hxx>
  28 #include <IntPolyh_Triangle.hxx>
  29
  30 #include <NCollection_Map.hxx>
  31
  32 static Standard_Integer ComputeIntersection(IntPolyh_PMaillageAffinage& theMaillage);
  33
  34 //=======================================================================
  35 //function : IntPolyh_Intersection
  36 //purpose  :
  37 //=======================================================================
  38 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_Surface)& theS1,
  39                                              const Handle(Adaptor3d_Surface)& theS2)
  40 {
  41   mySurf1 = theS1;
  42   mySurf2 = theS2;
  43   myNbSU1 = 10;
  44   myNbSV1 = 10;
  45   myNbSU2 = 10;
  46   myNbSV2 = 10;
  47   myIsDone = Standard_False;
  48   myIsParallel = Standard_False;
  49   mySectionLines.Init(1000);
  50   myTangentZones.Init(10000);
  51   Perform();
  52 }
  53
  54 //=======================================================================
  55 //function : IntPolyh_Intersection
  56 //purpose  :
  57 //=======================================================================
  58 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_Surface)& theS1,
  59                                              const Standard_Integer            theNbSU1,
  60                                              const Standard_Integer            theNbSV1,
  61                                              const Handle(Adaptor3d_Surface)& theS2,
  62                                              const Standard_Integer            theNbSU2,
  63                                              const Standard_Integer            theNbSV2)
  64 {
  65   mySurf1 = theS1;
  66   mySurf2 = theS2;
  67   myNbSU1 = theNbSU1;
  68   myNbSV1 = theNbSV1;
  69   myNbSU2 = theNbSU2;
  70   myNbSV2 = theNbSV2;
  71   myIsDone = Standard_False;
  72   myIsParallel = Standard_False;
  73   mySectionLines.Init(1000);
  74   myTangentZones.Init(10000);
  75   Perform();
  76 }
  77
  78 //=======================================================================
  79 //function : IntPolyh_Intersection
  80 //purpose  :
  81 //=======================================================================
  82 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_Surface)& theS1,
  83                                              const TColStd_Array1OfReal&       theUPars1,
  84                                              const TColStd_Array1OfReal&       theVPars1,
  85                                              const Handle(Adaptor3d_Surface)& theS2,
  86                                              const TColStd_Array1OfReal&       theUPars2,
  87                                              const TColStd_Array1OfReal&       theVPars2)
  88 {
  89   mySurf1 = theS1;
  90   mySurf2 = theS2;
  91   myNbSU1 = theUPars1.Length();
  92   myNbSV1 = theVPars1.Length();
  93   myNbSU2 = theUPars2.Length();
  94   myNbSV2 = theVPars2.Length();
  95   myIsDone = Standard_False;
  96   myIsParallel = Standard_False;
  97   mySectionLines.Init(1000);
  98   myTangentZones.Init(10000);
  99   Perform(theUPars1, theVPars1, theUPars2, theVPars2);
 100 }
 101
 102 //=======================================================================
 103 //function : GetLinePoint
 104 //purpose  :
 105 //=======================================================================
 106 void IntPolyh_Intersection::GetLinePoint(const Standard_Integer Indexl,
 107                                          const Standard_Integer Indexp,
 108                                          Standard_Real &x,
 109                                          Standard_Real &y,
 110                                          Standard_Real &z,
 111                                          Standard_Real &u1,
 112                                          Standard_Real &v1,
 113                                          Standard_Real &u2,
 114                                          Standard_Real &v2,
 115                                          Standard_Real &incidence) const
 116 {
 117   const IntPolyh_SectionLine  &msl = mySectionLines[Indexl - 1];
 118   const IntPolyh_StartPoint   &sp = msl[Indexp - 1];
 119   x = sp.X();
 120   y = sp.Y();
 121   z = sp.Z();
 122   u1 = sp.U1();
 123   v1 = sp.V1();
 124   u2 = sp.U2();
 125   v2 = sp.V2();
 126   incidence = sp.GetAngle();
 127 }
 128
 129 //=======================================================================
 130 //function : GetTangentZonePoint
 131 //purpose  :
 132 //=======================================================================
 133 void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
 134                                                 const Standard_Integer /*Indexp*/,
 135                                                 Standard_Real &x,
 136                                                 Standard_Real &y,
 137                                                 Standard_Real &z,
 138                                                 Standard_Real &u1,
 139                                                 Standard_Real &v1,
 140                                                 Standard_Real &u2,
 141                                                 Standard_Real &v2) const
 142 {
 143   const IntPolyh_StartPoint   &sp = myTangentZones[Indexz - 1];
 144   x = sp.X();
 145   y = sp.Y();
 146   z = sp.Z();
 147   u1 = sp.U1();
 148   v1 = sp.V1();
 149   u2 = sp.U2();
 150   v2 = sp.V2();
 151 }
 152
 153 //=======================================================================
 154 //function : Perform
 155 //purpose  :
 156 //=======================================================================
 157 void IntPolyh_Intersection::Perform()
 158 {
 159   // Prepare the sampling of the surfaces - UV parameters of the triangulation nodes
 160   TColStd_Array1OfReal UPars1, VPars1, UPars2, VPars2;
 161   IntPolyh_Tools::MakeSampling(mySurf1, myNbSU1, myNbSV1, Standard_False, UPars1, VPars1);
 162   IntPolyh_Tools::MakeSampling(mySurf2, myNbSU2, myNbSV2, Standard_False, UPars2, VPars2);
 163
 164   // Perform intersection
 165   Perform(UPars1, VPars1, UPars2, VPars2);
 166 }
 167
 168 //=======================================================================
 169 //function : Perform
 170 //purpose  :
 171 //=======================================================================
 172 void IntPolyh_Intersection::Perform(const TColStd_Array1OfReal& theUPars1,
 173                                     const TColStd_Array1OfReal& theVPars1,
 174                                     const TColStd_Array1OfReal& theUPars2,
 175                                     const TColStd_Array1OfReal& theVPars2)
 176 {
 177   myIsDone = Standard_True;
 178
 179   // Compute the deflection of the given sampling if it is not set
 180   Standard_Real aDeflTol1 = IntPolyh_Tools::ComputeDeflection(mySurf1, theUPars1, theVPars1);
 181   Standard_Real aDeflTol2 = IntPolyh_Tools::ComputeDeflection(mySurf2, theUPars2, theVPars2);
 182
 183   // Perform standard intersection
 184   IntPolyh_PMaillageAffinage pMaillageStd = 0;
 185   Standard_Integer           nbCouplesStd = 0;
 186   Standard_Boolean isStdDone = PerformStd(theUPars1, theVPars1,
 187                                           theUPars2, theVPars2,
 188                                           aDeflTol1, aDeflTol2,
 189                                           pMaillageStd, nbCouplesStd);
 190
 191   if (!isStdDone)
 192   {
 193     // Intersection not done
 194     myIsDone = Standard_False;
 195     if (pMaillageStd) delete pMaillageStd;
 196     return;
 197   }
 198
 199   if (!IsAdvRequired(pMaillageStd))
 200   {
 201     // Default interference done well, use it
 202     pMaillageStd->StartPointsChain(mySectionLines, myTangentZones);
 203   }
 204   else
 205   {
 206     // Default intersection is done, but too few interferences found.
 207     // Perform advanced intersection - perform intersection four times with different shifts.
 208     IntPolyh_PMaillageAffinage pMaillageFF = 0;
 209     IntPolyh_PMaillageAffinage pMaillageFR = 0;
 210     IntPolyh_PMaillageAffinage pMaillageRF = 0;
 211     IntPolyh_PMaillageAffinage pMaillageRR = 0;
 212     Standard_Integer           nbCouplesAdv = 0;
 213
 214     Standard_Boolean isAdvDone = PerformAdv(theUPars1, theVPars1,
 215                                               theUPars2, theVPars2,
 216                                               aDeflTol1, aDeflTol2,
 217                                               pMaillageFF,
 218                                               pMaillageFR,
 219                                               pMaillageRF,
 220                                               pMaillageRR,
 221                                               nbCouplesAdv);
 222
 223     if (isAdvDone && nbCouplesAdv > 0)
 224     {
 225       // Advanced interference found
 226       pMaillageFF->StartPointsChain(mySectionLines, myTangentZones);
 227       pMaillageFR->StartPointsChain(mySectionLines, myTangentZones);
 228       pMaillageRF->StartPointsChain(mySectionLines, myTangentZones);
 229       pMaillageRR->StartPointsChain(mySectionLines, myTangentZones);
 230     }
 231     else
 232     {
 233       // Advanced intersection not done or no intersection is found -> use standard intersection
 234       if (nbCouplesStd > 0)
 235         pMaillageStd->StartPointsChain(mySectionLines, myTangentZones);
 236     }
 237
 238     // Clean up
 239     if (pMaillageFF) delete pMaillageFF;
 240     if (pMaillageFR) delete pMaillageFR;
 241     if (pMaillageRF) delete pMaillageRF;
 242     if (pMaillageRR) delete pMaillageRR;
 243   }
 244
 245   // clean up
 246   if (pMaillageStd) delete pMaillageStd;
 247 }
 248
 249 //=======================================================================
 250 //function : PerformStd
 251 //purpose  :
 252 //=======================================================================
 253 Standard_Boolean IntPolyh_Intersection::PerformStd(const TColStd_Array1OfReal& theUPars1,
 254                                                    const TColStd_Array1OfReal& theVPars1,
 255                                                    const TColStd_Array1OfReal& theUPars2,
 256                                                    const TColStd_Array1OfReal& theVPars2,
 257                                                    const Standard_Real         theDeflTol1,
 258                                                    const Standard_Real         theDeflTol2,
 259                                                    IntPolyh_PMaillageAffinage& theMaillageS,
 260                                                    Standard_Integer&           theNbCouples)
 261 {
 262   Standard_Boolean isDone = PerformMaillage(theUPars1, theVPars1,
 263                                             theUPars2, theVPars2,
 264                                             theDeflTol1, theDeflTol2,
 265                                             theMaillageS);
 266   theNbCouples = (isDone) ? (theMaillageS->GetCouples().Extent()) : 0;
 267   return isDone;
 268 }
 269
 270 //=======================================================================
 271 //function : PerformAdv
 272 //purpose  :
 273 //=======================================================================
 274 Standard_Boolean IntPolyh_Intersection::PerformAdv(const TColStd_Array1OfReal& theUPars1,
 275                                                    const TColStd_Array1OfReal& theVPars1,
 276                                                    const TColStd_Array1OfReal& theUPars2,
 277                                                    const TColStd_Array1OfReal& theVPars2,
 278                                                    const Standard_Real         theDeflTol1,
 279                                                    const Standard_Real         theDeflTol2,
 280                                                    IntPolyh_PMaillageAffinage& theMaillageFF,
 281                                                    IntPolyh_PMaillageAffinage& theMaillageFR,
 282                                                    IntPolyh_PMaillageAffinage& theMaillageRF,
 283                                                    IntPolyh_PMaillageAffinage& theMaillageRR,
 284                                                    Standard_Integer&           theNbCouples)
 285 {
 286   // Compute the points on the surface and normal directions in these points
 287   IntPolyh_ArrayOfPointNormal aPoints1, aPoints2;
 288   IntPolyh_Tools::FillArrayOfPointNormal(mySurf1, theUPars1, theVPars1, aPoints1);
 289   IntPolyh_Tools::FillArrayOfPointNormal(mySurf2, theUPars2, theVPars2, aPoints2);
 290
 291   // Perform intersection with the different shifts of the triangles
 292   Standard_Boolean isDone =
 293     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
 294                     theDeflTol1, theDeflTol2,                   // deflection tolerance
 295                     aPoints1, aPoints2,                         // points and normals
 296                     Standard_True , Standard_False,             // shift
 297                     theMaillageFR)
 298                     &&
 299     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
 300                     theDeflTol1, theDeflTol2,                   // deflection tolerance
 301                     aPoints1, aPoints2,                         // points and normals
 302                     Standard_False, Standard_True,              // shift
 303                     theMaillageRF)
 304                     &&
 305     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
 306                     theDeflTol1, theDeflTol2,                   // deflection tolerance
 307                     aPoints1, aPoints2,                         // points and normals
 308                     Standard_True, Standard_True,               // shift
 309                     theMaillageFF)
 310                     &&
 311     PerformMaillage(theUPars1, theVPars1, theUPars2, theVPars2, // sampling
 312                     theDeflTol1, theDeflTol2,                   // deflection tolerance
 313                     aPoints1, aPoints2,                         // points and normals
 314                     Standard_False, Standard_False,             // shift
 315                     theMaillageRR);
 316
 317   if (isDone)
 318   {
 319     theNbCouples = theMaillageFF->GetCouples().Extent() +
 320                    theMaillageFR->GetCouples().Extent() +
 321                    theMaillageRF->GetCouples().Extent() +
 322                    theMaillageRR->GetCouples().Extent();
 323
 324     // Merge couples
 325     if(theNbCouples > 0)
 326       MergeCouples(theMaillageFF->GetCouples(),
 327                    theMaillageFR->GetCouples(),
 328                    theMaillageRF->GetCouples(),
 329                    theMaillageRR->GetCouples());
 330   }
 331
 332   return isDone;
 333 }
 334
 335 //=======================================================================
 336 //function : PerformMaillage
 337 //purpose  : Computes standard MaillageAffinage (without shift)
 338 //=======================================================================
 339 Standard_Boolean IntPolyh_Intersection::PerformMaillage(const TColStd_Array1OfReal& theUPars1,
 340                                                         const TColStd_Array1OfReal& theVPars1,
 341                                                         const TColStd_Array1OfReal& theUPars2,
 342                                                         const TColStd_Array1OfReal& theVPars2,
 343                                                         const Standard_Real         theDeflTol1,
 344                                                         const Standard_Real         theDeflTol2,
 345                                                         IntPolyh_PMaillageAffinage& theMaillage)
 346 {
 347   theMaillage =
 348     new IntPolyh_MaillageAffinage(mySurf1, theUPars1.Length(), theVPars1.Length(),
 349                                   mySurf2, theUPars2.Length(), theVPars2.Length(),
 350                                   0);
 351
 352   theMaillage->FillArrayOfPnt(1, theUPars1, theVPars1, &theDeflTol1);
 353   theMaillage->FillArrayOfPnt(2, theUPars2, theVPars2, &theDeflTol2);
 354
 355   Standard_Integer FinTTC = ComputeIntersection(theMaillage);
 356
 357   // If no intersecting triangles are found, try enlarged surfaces
 358   if (FinTTC == 0)
 359   {
 360     // Check if enlarge for the surfaces is possible
 361     Standard_Boolean isEnlargeU1, isEnlargeV1, isEnlargeU2, isEnlargeV2;
 362     IntPolyh_Tools::IsEnlargePossible(mySurf1, isEnlargeU1, isEnlargeV1);
 363     IntPolyh_Tools::IsEnlargePossible(mySurf2, isEnlargeU2, isEnlargeV2);
 364
 365     if (isEnlargeU1 || isEnlargeV1 || isEnlargeU2 || isEnlargeV2)
 366     {
 367       theMaillage->SetEnlargeZone(Standard_True);
 368       // Make new points on the enlarged surface
 369       theMaillage->FillArrayOfPnt(1);
 370       theMaillage->FillArrayOfPnt(2);
 371       // Compute intersection
 372       ComputeIntersection(theMaillage);
 373       theMaillage->SetEnlargeZone(Standard_False);
 374     }
 375   }
 376
 377   // if too many intersections, consider surfaces parallel
 378   return AnalyzeIntersection(theMaillage);
 379 }
 380
 381 //=======================================================================
 382 //function : PerformMaillage
 383 //purpose  : Computes MaillageAffinage
 384 //=======================================================================
 385 Standard_Boolean IntPolyh_Intersection::PerformMaillage(const TColStd_Array1OfReal& theUPars1,
 386                                                         const TColStd_Array1OfReal& theVPars1,
 387                                                         const TColStd_Array1OfReal& theUPars2,
 388                                                         const TColStd_Array1OfReal& theVPars2,
 389                                                         const Standard_Real         theDeflTol1,
 390                                                         const Standard_Real         theDeflTol2,
 391                                                         const IntPolyh_ArrayOfPointNormal& thePoints1,
 392                                                         const IntPolyh_ArrayOfPointNormal& thePoints2,
 393                                                         const Standard_Boolean      theIsFirstFwd,
 394                                                         const Standard_Boolean      theIsSecondFwd,
 395                                                         IntPolyh_PMaillageAffinage& theMaillage)
 396 {
 397   theMaillage =
 398     new IntPolyh_MaillageAffinage(mySurf1, theUPars1.Length(), theVPars1.Length(),
 399                                   mySurf2, theUPars2.Length(), theVPars2.Length(),
 400                                   0);
 401
 402   theMaillage->FillArrayOfPnt(1, theIsFirstFwd , thePoints1, theUPars1, theVPars1, theDeflTol1);
 403   theMaillage->FillArrayOfPnt(2, theIsSecondFwd, thePoints2, theUPars2, theVPars2, theDeflTol2);
 404
 405   ComputeIntersection(theMaillage);
 406
 407   return AnalyzeIntersection(theMaillage);
 408 }
 409
 410 //=======================================================================
 411 //function : MergeCouples
 412 //purpose  : This method analyzes the lists to find same couples.
 413 //           If some are detected it leaves the couple in only one list
 414 //           deleting from others.
 415 //=======================================================================
 416 void IntPolyh_Intersection::MergeCouples(IntPolyh_ListOfCouples &anArrayFF,
 417                                          IntPolyh_ListOfCouples &anArrayFR,
 418                                          IntPolyh_ListOfCouples &anArrayRF,
 419                                          IntPolyh_ListOfCouples &anArrayRR) const
 420 {
 421   // Fence map to remove from the lists the duplicating elements.
 422   NCollection_Map<IntPolyh_Couple, IntPolyh_CoupleMapHasher> aFenceMap;
 423   //
 424   IntPolyh_ListOfCouples* pLists[4] = {&anArrayFF, &anArrayFR, &anArrayRF, &anArrayRR};
 425   for (Standard_Integer i = 0; i < 4; ++i) {
 426     IntPolyh_ListIteratorOfListOfCouples aIt(*pLists[i]);
 427     for (; aIt.More();) {
 428       if (!aFenceMap.Add(aIt.Value())) {
 429         pLists[i]->Remove(aIt);
 430         continue;
 431       }
 432       aIt.Next();
 433     }
 434   }
 435 }
 436
 437 //=======================================================================
 438 //function : IsAdvRequired
 439 //purpose  : Analyzes the standard intersection on the angles between triangles.
 440 //           If the angle between some of the interfering triangles is
 441 //           too small (less than 5 deg), the advanced intersection is required.
 442 //           Otherwise, the standard intersection is considered satisfactory.
 443 //=======================================================================
 444 Standard_Boolean IntPolyh_Intersection::IsAdvRequired(IntPolyh_PMaillageAffinage& theMaillage)
 445 {
 446   if (!theMaillage)
 447     return Standard_True;
 448
 449   // Interfering triangles
 450   IntPolyh_ListOfCouples& Couples = theMaillage->GetCouples();
 451   // Number of interfering pairs
 452   Standard_Integer aNbCouples = Couples.Extent();
 453   // Flag to define whether advanced intersection is required or not
 454   Standard_Boolean isAdvReq = (aNbCouples == 0) && !IsParallel();
 455   if (isAdvReq)
 456     // No interfering triangles are found -> perform advanced intersection
 457     return isAdvReq;
 458
 459   if (aNbCouples > 10)
 460     // Enough interfering triangles are found -> no need to perform advanced intersection
 461     return isAdvReq;
 462
 463   const Standard_Real anEps = .996; //~ cos of 5 deg
 464   IntPolyh_ListIteratorOfListOfCouples aIt(Couples);
 465   for(; aIt.More(); aIt.Next())
 466   {
 467     if (Abs(aIt.Value().Angle()) > anEps)
 468     {
 469       // The angle between interfering triangles is small -> perform advanced
 470       // intersection to make intersection more precise
 471       isAdvReq = Standard_True;
 472       break;
 473     }
 474   }
 475
 476   return isAdvReq;
 477 }
 478
 479 //=======================================================================
 480 //function : ComputeIntersection
 481 //purpose  : Computes the intersection of the triangles
 482 //=======================================================================
 483 Standard_Integer ComputeIntersection(IntPolyh_PMaillageAffinage& theMaillage)
 484 {
 485   if (!theMaillage)
 486     return 0;
 487
 488   // Compute common box and mark the points inside that box
 489   theMaillage->CommonBox();
 490
 491   // Make triangles
 492   theMaillage->FillArrayOfTriangles(1);
 493   theMaillage->FillArrayOfTriangles(2);
 494
 495   // Make edges
 496   theMaillage->FillArrayOfEdges(1);
 497   theMaillage->FillArrayOfEdges(2);
 498
 499   // Deflection refinement
 500   theMaillage->TrianglesDeflectionsRefinementBSB();
 501
 502   return theMaillage->TriangleCompare();
 503 }
 504
 505 //=======================================================================
 506 //function : AnalyzeIntersection
 507 //purpose  : Analyzes the intersection on the number of interfering triangles
 508 //=======================================================================
 509 Standard_Boolean IntPolyh_Intersection::AnalyzeIntersection(IntPolyh_PMaillageAffinage& theMaillage)
 510 {
 511   if (!theMaillage)
 512     return Standard_False;
 513
 514   IntPolyh_ListOfCouples& Couples = theMaillage->GetCouples();
 515   Standard_Integer FinTTC = Couples.Extent();
 516   if(FinTTC > 200)
 517   {
 518     const Standard_Real eps = .996; //~ cos of 5deg.
 519     Standard_Integer npara = 0;
 520     IntPolyh_ListIteratorOfListOfCouples aIt(Couples);
 521     for(; aIt.More(); aIt.Next())
 522     {
 523       Standard_Real cosa = Abs(aIt.Value().Angle());
 524       if(cosa > eps) ++npara;
 525     }
 526
 527     if (npara >= theMaillage->GetArrayOfTriangles(1).NbItems() ||
 528         npara >= theMaillage->GetArrayOfTriangles(2).NbItems())
 529     {
 530       Couples.Clear();
 531       myIsParallel = Standard_True;
 532       return Standard_True;
 533     }
 534   }
 535   return Standard_True;
 536 }