0028639: Improve performance of the IntPolyh_MaillageAffinage algorithm
[occt.git] / src / IntPolyh / IntPolyh_Intersection.cxx
old mode 100755 (executable)
new mode 100644 (file)
index 3b93b0b..0d88026
@@ -1,33 +1,37 @@
-// File:       IntPolyh_Intersection.cxx
-// Created:    Wed Mar  3 11:33:51 1999
-// Author:     Fabrice SERVANT
-//             <fst>
+// Created on: 1999-03-03
+// Created by: Fabrice SERVANT
+// Copyright (c) 1999-1999 Matra Datavision
+// Copyright (c) 1999-2014 OPEN CASCADE SAS
+//
+// This file is part of Open CASCADE Technology software library.
+//
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
+//
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
 
 //  modified by Edward AGAPOV (eap) Tue Jan 22 12:29:55 2002 (occ53)
 //  Modified by skv - Thu Sep 25 18:24:29 2003 OCC567
 
-#include <IntPolyh_Intersection.ixx>
+#include <Adaptor3d_HSurface.hxx>
+#include <IntPolyh_Couple.hxx>
+#include <IntPolyh_Intersection.hxx>
+#include <IntPolyh_MaillageAffinage.hxx>
 #include <IntPolyh_SectionLine.hxx>
 #include <IntPolyh_StartPoint.hxx>
-#include <IntPolyh_MaillageAffinage.hxx>
-#include <IntPolyh_Couple.hxx>
-
-#ifdef DEB
-  # define MYDEBUG DEB 
-#else
-  # define MYDEBUG 0
-#endif
+#include <IntPolyh_Triangle.hxx>
+#include <NCollection_Map.hxx>
+#include <IntPolyh_CoupleMapHasher.hxx>
 
 Standard_Integer MYDISPLAY = 0;
 Standard_Integer MYPRINT   = 0;
 
-# if MYDEBUG
-//  # include "visudebug.hxx"
-# endif
-
-
 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
-                                            const Handle(Adaptor3d_HSurface)& S2)
+                                             const Handle(Adaptor3d_HSurface)& S2)
 {
   myNbSU1 = -1;
   myNbSV1 = -1;
@@ -42,11 +46,11 @@ IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S
 }
 
 IntPolyh_Intersection::IntPolyh_Intersection(const Handle(Adaptor3d_HSurface)& S1,
-                                            const Standard_Integer NbSU1,
-                                            const Standard_Integer NbSV1,
-                                            const Handle(Adaptor3d_HSurface)& S2,
-                                            const Standard_Integer NbSU2,
-                                            const Standard_Integer NbSV2)
+                                             const Standard_Integer NbSU1,
+                                             const Standard_Integer NbSV1,
+                                             const Handle(Adaptor3d_HSurface)& S2,
+                                             const Standard_Integer NbSU2,
+                                             const Standard_Integer NbSV2)
 {
   myNbSU1 = NbSU1;
   myNbSV1 = NbSV1;
@@ -64,92 +68,56 @@ void IntPolyh_Intersection::Perform() {
 
   done = Standard_True;
 
-  Standard_Boolean startFromAdvanced = Standard_False;
   Standard_Boolean isStdDone = Standard_False;
   Standard_Boolean isAdvDone = Standard_False;
   Standard_Integer nbCouplesStd = 0;
   Standard_Integer nbCouplesAdv = 0;
   
-  //GeomAbs_SurfaceType ST1 = mySurf1->GetType();
-  //GeomAbs_SurfaceType ST2 = mySurf2->GetType();
-
-//   if(ST1 == GeomAbs_Torus || ST2 == GeomAbs_Torus)
-//     startFromAdvanced = Standard_True;
-  
   IntPolyh_PMaillageAffinage aPMaillageStd = 0;
   IntPolyh_PMaillageAffinage aPMaillageFF = 0;
   IntPolyh_PMaillageAffinage aPMaillageFR = 0;
   IntPolyh_PMaillageAffinage aPMaillageRF = 0;
   IntPolyh_PMaillageAffinage aPMaillageRR = 0;
 
+  isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
 
-  if(!startFromAdvanced) {
-
-    isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
-
-    // default interference done well, use it
-    if(isStdDone && nbCouplesStd > 10) {
-      aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
-    }
-    // default interference done, but too few interferences foud;
-    // use advanced interference
-    else if(isStdDone && nbCouplesStd <= 10) {
-      isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
-      
-      // advanced interference found
-      if(isAdvDone && nbCouplesAdv > 10) {
-       aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
-      }
-      else {
-       // use result of default
-       if(nbCouplesStd > 0)
-         aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
-      }
-    }
-    // default interference faild, use advanced
-    else {
-//       isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
-      
-//       if(isAdvDone && nbCouplesAdv > 0) {cout << "4adv done, nbc: " << nbCouplesAdv << endl;
-//     aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
-//     aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
-//     aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
-//     aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
-//       }
-    }
-  }// start from default
-  else {
-    
+  // default interference done well, use it
+  if(isStdDone && nbCouplesStd > 10) {
+    aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
+  }
+  // default interference done, but too few interferences foud;
+  // use advanced interference
+  else if(isStdDone && nbCouplesStd <= 10) {
     isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
 
-    // advanced done, interference found; use it
-    if(isAdvDone) {
-
-      if(nbCouplesAdv > 0) {
-       aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
-       aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
-      }
-      else {
-       isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
-       if(isStdDone && nbCouplesStd > 0)
-         aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
-      }
+    // advanced interference found
+    if(isAdvDone && nbCouplesAdv > 0) {
+      aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
+      aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
+      aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
+      aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
     }
     else {
-      isStdDone = PerformStd(aPMaillageStd,nbCouplesStd);
-      if(isStdDone && nbCouplesStd > 0)
-       aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
+      // use result of default
+      if(nbCouplesStd > 0)
+        aPMaillageStd->StartPointsChain(TSectionLines, TTangentZones);
     }
-  } // start from advanced
+  }
+  // default interference faild, use advanced
+  else {
+    //       isAdvDone = PerformAdv(aPMaillageFF,aPMaillageFR,aPMaillageRF,aPMaillageRR,nbCouplesAdv);
+
+    //       if(isAdvDone && nbCouplesAdv > 0) {cout << "4adv done, nbc: " << nbCouplesAdv << endl;
+    //         aPMaillageFF->StartPointsChain(TSectionLines,TTangentZones);
+    //         aPMaillageFR->StartPointsChain(TSectionLines,TTangentZones);
+    //         aPMaillageRF->StartPointsChain(TSectionLines,TTangentZones);
+    //         aPMaillageRR->StartPointsChain(TSectionLines,TTangentZones);
+    //       }
+  }
 
   // accept result
-  nbsectionlines = TSectionLines.NbSectionLines();
-  nbtangentzones = TTangentZones.NbTangentZones();
+  nbsectionlines = TSectionLines.NbItems();
+  nbtangentzones = TTangentZones.NbItems();
 
   // clean up
   if(aPMaillageStd) delete aPMaillageStd;
@@ -180,7 +148,7 @@ Standard_Integer IntPolyh_Intersection::NbPointsInLine(const Standard_Integer In
 }
 
 
-Standard_Integer IntPolyh_Intersection::NbPointsInTangentZone(const Standard_Integer IndexLine) const {   
+Standard_Integer IntPolyh_Intersection::NbPointsInTangentZone(const Standard_Integer) const {   
   //-- IndexLine--;     (pas implemente) Attention : Tableaux de 0 a n-1 
   // eap
   // return(TTangentZones.NbTangentZones());
@@ -217,7 +185,7 @@ void IntPolyh_Intersection::GetLinePoint(const Standard_Integer Indexl,
 
 
 void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
-                                       const Standard_Integer Indexp,
+                                       const Standard_Integer /*Indexp*/,
                                        Standard_Real &x,
                                        Standard_Real &y,
                                        Standard_Real &z,
@@ -231,7 +199,7 @@ void IntPolyh_Intersection::GetTangentZonePoint(const Standard_Integer Indexz,
   const IntPolyh_StartPoint   &sp=TTangentZones[Indexz-1];
   x=sp.X();
   y=sp.Y();
-  z=sp.Y();
+  z=sp.Z();
   u1=sp.U1();
   v1=sp.V1();
   u2=sp.U2();
@@ -263,22 +231,20 @@ Standard_Boolean IntPolyh_Intersection::PerformMaillage
   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
                          xx0, yy0, zz0, xx1, yy1, zz1);
   
-  theMaillageS->FillArrayOfEdges(1);
-  theMaillageS->FillArrayOfEdges(2);
-
   theMaillageS->FillArrayOfTriangles(1);
   theMaillageS->FillArrayOfTriangles(2);
   
-  theMaillageS->LinkEdges2Triangles();
-  
+  theMaillageS->FillArrayOfEdges(1);
+  theMaillageS->FillArrayOfEdges(2);
+
   theMaillageS->TrianglesDeflectionsRefinementBSB();
 
   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
 
   // if too many intersections, consider surfaces parallel (eap)
   if(FinTTC > 200 &&
-     (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbTriangles() ||
-      FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbTriangles()) ) {
+     (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbItems() ||
+      FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbItems()) ) {
     return Standard_False;
   }
 
@@ -306,14 +272,12 @@ Standard_Boolean IntPolyh_Intersection::PerformMaillage(IntPolyh_PMaillageAffina
   theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
                          xx0, yy0, zz0, xx1, yy1, zz1);
   
-  theMaillageS->FillArrayOfEdges(1);
-  theMaillageS->FillArrayOfEdges(2);
-
   theMaillageS->FillArrayOfTriangles(1);
   theMaillageS->FillArrayOfTriangles(2);
   
-  theMaillageS->LinkEdges2Triangles();
-  
+  theMaillageS->FillArrayOfEdges(1);
+  theMaillageS->FillArrayOfEdges(2);
+
   theMaillageS->TrianglesDeflectionsRefinementBSB();
 
   Standard_Integer FinTTC = theMaillageS->TriangleCompare();
@@ -325,111 +289,63 @@ Standard_Boolean IntPolyh_Intersection::PerformMaillage(IntPolyh_PMaillageAffina
     theMaillageS->FillArrayOfPnt(2);
     theMaillageS->CommonBox(theMaillageS->GetBox(1), theMaillageS->GetBox(2),
                            xx0, yy0, zz0, xx1, yy1, zz1);
-    theMaillageS->FillArrayOfEdges(1);
-    theMaillageS->FillArrayOfEdges(2);
     theMaillageS->FillArrayOfTriangles(1);
     theMaillageS->FillArrayOfTriangles(2);
-    theMaillageS->LinkEdges2Triangles();
+    theMaillageS->FillArrayOfEdges(1);
+    theMaillageS->FillArrayOfEdges(2);
     theMaillageS->TrianglesDeflectionsRefinementBSB();
     FinTTC = theMaillageS->TriangleCompare();
     myZone = Standard_False;
     theMaillageS->SetEnlargeZone( myZone );
   }
 
-  // if too many intersections, consider surfaces parallel (eap)
-  if(FinTTC > 200 &&
-     (FinTTC >= theMaillageS->GetArrayOfTriangles(1).NbTriangles() ||
-      FinTTC >= theMaillageS->GetArrayOfTriangles(2).NbTriangles()) ) {
-    return Standard_False;
-  }
-
   return Standard_True;
 }
 
 //=======================================================================
 //function : MergeCouples
-//purpose  : This method analyzes arrays to find same couples. If some 
-//           are detected it leaves the couple in only one array 
+//purpose  : This method analyzes the lists to find same couples.
+//           If some are detected it leaves the couple in only one list
 //           deleting from others.
 //=======================================================================
 
-void IntPolyh_Intersection::MergeCouples
-                            (IntPolyh_ArrayOfCouples &anArrayFF,
-                            IntPolyh_ArrayOfCouples &anArrayFR,
-                            IntPolyh_ArrayOfCouples &anArrayRF,
-                            IntPolyh_ArrayOfCouples &anArrayRR) const
+void IntPolyh_Intersection::MergeCouples(IntPolyh_ListOfCouples &anArrayFF,
+                                         IntPolyh_ListOfCouples &anArrayFR,
+                                         IntPolyh_ListOfCouples &anArrayRF,
+                                         IntPolyh_ListOfCouples &anArrayRR) const
 {
-  // Step 1: Sorting arrays.
-  IntPolyh_ArrayOfCouples *anArrays[4];
-  Standard_Integer         aNbCouples[4];
-  Standard_Integer         i;
-  IntPolyh_ArrayOfCouples *aTmpPtr;
-  Standard_Integer         aTmpNbr;
-
-  anArrays[0] = &anArrayFF;
-  anArrays[1] = &anArrayFR;
-  anArrays[2] = &anArrayRF;
-  anArrays[3] = &anArrayRR;
-
-  for (i = 0; i < 4; i++)
-    aNbCouples[i] = anArrays[i]->NbCouples();
-
-  Standard_Boolean isChanged = Standard_True;
-
-  while (isChanged) {
-    isChanged = Standard_False;
-
-    for (i = 0; i < 3; i++) {
-      if (aNbCouples[i] < aNbCouples[i + 1]) {
-       aTmpPtr           = anArrays[i];
-       anArrays[i]       = anArrays[i + 1];
-       anArrays[i + 1]   = aTmpPtr;
-       aTmpNbr           = aNbCouples[i];
-       aNbCouples[i]     = aNbCouples[i + 1];
-       aNbCouples[i + 1] = aTmpNbr;
-       isChanged         = Standard_True;
-      }
-    }
-  }
-
-  // Step 2: Searching for same couples.
-  Standard_Integer j;
-  Standard_Integer indC1;
-  Standard_Integer indC2;
-
-  for (i = 0; i < 3; i++) {
-    for (j = i + 1; j < 4; j++) {
-      for (indC1 = 1; indC1 <= aNbCouples[i]; indC1++) {
-       IntPolyh_Couple &aCouple1 = anArrays[i]->ChangeValue(indC1);
-
-       if (aCouple1.AnalyseFlagValue() == 1)
-         continue;
-
-       for (indC2 = 1; indC2 <= aNbCouples[j]; indC2++) {
-         IntPolyh_Couple &aCouple2 = anArrays[j]->ChangeValue(indC2);
-
-         if (aCouple2.AnalyseFlagValue() == 1)
-           continue;
-
-         if (aCouple1.FirstValue()  == aCouple2.FirstValue() &&
-             aCouple1.SecondValue() == aCouple2.SecondValue()) {
-           aCouple2.SetAnalyseFlag(1);
-         }
-       }
+  // Fence map to remove from the lists the duplicating elements.
+  NCollection_Map<IntPolyh_Couple, IntPolyh_CoupleMapHasher> aFenceMap;
+  //
+  IntPolyh_ListOfCouples* pLists[4] = {&anArrayFF, &anArrayFR, &anArrayRF, &anArrayRR};
+  for (Standard_Integer i = 0; i < 4; ++i) {
+    IntPolyh_ListIteratorOfListOfCouples aIt(*pLists[i]);
+    for (; aIt.More();) {
+      if (!aFenceMap.Add(aIt.Value())) {
+        pLists[i]->Remove(aIt);
+        continue;
       }
+      aIt.Next();
     }
   }
 }
-//  Modified by skv - Thu Sep 25 18:07:42 2003 OCC567 End
 
+//=======================================================================
+//function : PerformStd
+//purpose  : 
+//=======================================================================
 Standard_Boolean IntPolyh_Intersection::PerformStd(IntPolyh_PMaillageAffinage& MaillageS,
                                                   Standard_Integer&           NbCouples)
 {
   Standard_Boolean isdone = PerformMaillage(MaillageS);
-  NbCouples = (isdone) ? (MaillageS->GetArrayOfCouples().NbCouples()) : 0;
+  NbCouples = (isdone) ? (MaillageS->GetCouples().Extent()) : 0;
   return isdone;
 }
 
+//=======================================================================
+//function : PerformAdv
+//purpose  : 
+//=======================================================================
 Standard_Boolean IntPolyh_Intersection::PerformAdv(IntPolyh_PMaillageAffinage& MaillageFF,
                                                   IntPolyh_PMaillageAffinage& MaillageFR,
                                                   IntPolyh_PMaillageAffinage& MaillageRF,
@@ -446,14 +362,14 @@ Standard_Boolean IntPolyh_Intersection::PerformAdv(IntPolyh_PMaillageAffinage& M
     isdone = Standard_False; 
 
   if(isdone) {
-    NbCouples = MaillageFF->GetArrayOfCouples().NbCouples() +
-      MaillageFR->GetArrayOfCouples().NbCouples() +
-       MaillageRF->GetArrayOfCouples().NbCouples() +
-         MaillageRR->GetArrayOfCouples().NbCouples();
+    NbCouples = MaillageFF->GetCouples().Extent() +
+      MaillageFR->GetCouples().Extent() +
+       MaillageRF->GetCouples().Extent() +
+         MaillageRR->GetCouples().Extent();
 
     if(NbCouples > 0)
-      MergeCouples(MaillageFF->GetArrayOfCouples(),MaillageFR->GetArrayOfCouples(),
-                  MaillageRF->GetArrayOfCouples(),MaillageRR->GetArrayOfCouples());
+      MergeCouples(MaillageFF->GetCouples(),MaillageFR->GetCouples(),
+                  MaillageRF->GetCouples(),MaillageRR->GetCouples());
   }
   return isdone;
 }