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