0030656: Modeling Algorithms - Change Boolean Operations algorithm to use BVH tree...
authoremv <emv@opencascade.com>
Thu, 18 Apr 2019 12:34:37 +0000 (15:34 +0300)
committerbugmaster <bugmaster@opencascade.com>
Tue, 4 Jun 2019 14:36:43 +0000 (17:36 +0300)
Switching the Boolean Operations algorithm to use the BVH tree instead of UB tree as selection of the elements from BVH tree is usually faster.

21 files changed:
dox/dev_guides/upgrade/upgrade.md
samples/tcl/ANC101.tcl
src/BOPAlgo/BOPAlgo_BuilderFace.cxx
src/BOPAlgo/BOPAlgo_BuilderSolid.cxx
src/BOPAlgo/BOPAlgo_PaveFiller.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_3.cxx
src/BOPAlgo/BOPAlgo_PaveFiller_5.cxx
src/BOPAlgo/BOPAlgo_Tools.cxx
src/BOPAlgo/BOPAlgo_Tools.hxx
src/BOPDS/BOPDS_Iterator.cxx
src/BOPDS/BOPDS_Iterator.hxx
src/BOPDS/BOPDS_IteratorSI.cxx
src/BOPDS/BOPDS_ShapeInfo.lxx
src/BOPDS/BOPDS_SubIterator.cxx
src/BOPTools/BOPTools_BoxBndTree.hxx [deleted file]
src/BOPTools/BOPTools_BoxSelector.hxx
src/BOPTools/BOPTools_BoxTree.hxx [new file with mode: 0644]
src/BOPTools/BOPTools_PairSelector.hxx [new file with mode: 0644]
src/BOPTools/FILES
src/BRepOffset/BRepOffset_Inter3d.cxx
src/IntPolyh/IntPolyh_MaillageAffinage.cxx

index c672488..e4c7825 100644 (file)
@@ -1751,3 +1751,13 @@ Proxy classes *SelectBasics_SensitiveEntity* and *SelectBasics_EntityOwner* have
 *env.bat* produced by Visual Studio project generator *genproj.bat* has been modified so that *%CSF_DEFINES%* variable is reset to initial state.
 Custom building environment relying on old behavior and setting extra macros within *%CSF_DEFINES%* before env.bat should be updated
 to either modify custom.bat or setup new variable *%CSF_DEFINES_EXTRA%* instead.
+
+@subsection upgrade_740_BVH_in_BOP Switching Boolean Operations algorithm to use BVH tree instead of UB tree
+
+Since OCCT 7.4.0 Boolean Operations algorithm uses BVH tree instead of UBTree to find the pairs of entities with interfering bounding boxes.
+The following API changes have been made:
+* BOPTools_BoxBndTree and BOPTools_BoxBndTreeSelector have been removed. Use the BOPTools_BoxTree and BOPTools_BoxTreeSelector instead.
+* BOPTools_BoxSelector::SetBox() method now accepts the BVH_Box instead of Bnd_Box.
+* Methods BOPTools_BoxSelector::Reject and BOPTools_BoxSelector::Accept have been removed as unused.
+* The RunParallel flag has been removed from the list of parameters of BOPAlgo_Tools::IntersectVertices method. Earlier, it performed selection from the UB tree in parallel mode. Now all interfering pairs are found in one pass, using pair traverse of the same BVH tree.
+
index 818f3eb..42852eb 100644 (file)
@@ -264,11 +264,11 @@ bfuse _model _model t_s
 explode _model e
 
 # Make a weld at joint edges of platform and wedge 
-blend _model _model 2 _model_26
 blend _model _model 2 _model_27
 blend _model _model 2 _model_28
 blend _model _model 2 _model_29
-blend _model _model 2 _model_31
+blend _model _model 2 _model_30
+blend _model _model 2 _model_32
 
 # Cylinder on wedge
 blend result _model 2 _model_161
index d75aad1..8fe38f1 100644 (file)
@@ -24,7 +24,8 @@
 #include <BOPAlgo_Alerts.hxx>
 #include <BOPTools_AlgoTools.hxx>
 #include <BOPTools_AlgoTools2D.hxx>
-#include <BOPTools_BoxSelector.hxx>
+#include <BOPTools_BoxTree.hxx>
+#include <Bnd_Tools.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
 #include <BRepBndLib.hxx>
@@ -38,7 +39,6 @@
 #include <IntTools_Context.hxx>
 #include <IntTools_FClass2d.hxx>
 #include <NCollection_DataMap.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <TColStd_MapOfInteger.hxx>
 #include <TopAbs.hxx>
 #include <TopExp.hxx>
@@ -448,28 +448,28 @@ void BOPAlgo_BuilderFace::PerformAreas()
 
   // Classify holes relatively faces
 
-  // Prepare tree filler with the boxes of the hole faces
-  NCollection_UBTree<Standard_Integer, Bnd_Box2d> aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
-
+  // Prepare tree with the boxes of the hole faces
+  BOPTools_Box2dTree aBoxTree;
   Standard_Integer i, aNbH = aHoleFaces.Extent();
+  aBoxTree.SetSize (aNbH);
   for (i = 1; i <= aNbH; ++i)
   {
     const TopoDS_Face& aHFace = TopoDS::Face(aHoleFaces(i));
     //
     Bnd_Box2d aBox;
     BRepTools::AddUVBounds(aHFace, aBox);
-    aTreeFiller.Add(i, aBox);
+    aBoxTree.Add(i, Bnd_Tools::Bnd2BVH (aBox));
   }
 
-  // Shake TreeFiller
-  aTreeFiller.Fill();
+  // Build BVH
+  aBoxTree.Build();
 
   // Find outer growth face that is most close to each hole face
   TopTools_IndexedDataMapOfShapeShape aHoleFaceMap;
 
   // Selector
-  BOPTools_BoxSelector<Bnd_Box2d> aSelector;
+  BOPTools_Box2dTreeSelector aSelector;
+  aSelector.SetBVHSet (&aBoxTree);
 
   TopTools_ListIteratorOfListOfShape aItLS(aNewFaces);
   for (; aItLS.More(); aItLS.Next())
@@ -481,8 +481,8 @@ void BOPAlgo_BuilderFace::PerformAreas()
     BRepTools::AddUVBounds(aFace, aBox);
 
     aSelector.Clear();
-    aSelector.SetBox(aBox);
-    aBBTree.Select(aSelector);
+    aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBox));
+    aSelector.Select();
 
     const TColStd_ListOfInteger& aLI = aSelector.Indices();
     TColStd_ListIteratorOfListOfInteger aItLI(aLI);
@@ -590,9 +590,8 @@ void BOPAlgo_BuilderFace::PerformInternalShapes()
     // No edges left for classification
     return;
 
-  // Prepare tree filler with the boxes of the edges to classify
-  NCollection_UBTree<Standard_Integer, Bnd_Box2d> aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box2d> aTreeFiller(aBBTree);
+  // Prepare tree with the boxes of the edges to classify
+  BOPTools_Box2dTree aBoxTree;
 
   // Map of edges to classify
   TopTools_IndexedMapOfShape anEdgesMap;
@@ -611,13 +610,13 @@ void BOPAlgo_BuilderFace::PerformInternalShapes()
         BRepTools::AddUVBounds(myFace, aE, aBoxE);
         // Make sure the index of edge in the map and
         // of the box in the tree is the same
-        aTreeFiller.Add(anEdgesMap.Add(aE), aBoxE);
+        aBoxTree.Add(anEdgesMap.Add(aE), Bnd_Tools::Bnd2BVH (aBoxE));
       }
     }
   }
 
-  // Shake the tree
-  aTreeFiller.Fill();
+  // Build BVH
+  aBoxTree.Build();
 
   // Fence map
   TColStd_MapOfInteger aMEDone;
@@ -633,9 +632,10 @@ void BOPAlgo_BuilderFace::PerformInternalShapes()
     BRepTools::AddUVBounds(aF, aBoxF);
 
     // Select edges for the classification
-    BOPTools_BoxSelector<Bnd_Box2d> aSelector;
-    aSelector.SetBox(aBoxF);
-    if (!aBBTree.Select(aSelector))
+    BOPTools_Box2dTreeSelector aSelector;
+    aSelector.SetBVHSet (&aBoxTree);
+    aSelector.SetBox(Bnd_Tools::Bnd2BVH (aBoxF));
+    if (!aSelector.Select())
       continue;
 
     // Collect edges inside the face
index 29cc5a6..a024a4f 100644 (file)
 #include <BOPAlgo_Tools.hxx>
 #include <BOPTools_AlgoTools.hxx>
 #include <BOPTools_AlgoTools3D.hxx>
-#include <BOPTools_BoxBndTree.hxx>
+#include <BOPTools_BoxTree.hxx>
 #include <BOPTools_CoupleOfShape.hxx>
 #include <BOPTools_Parallel.hxx>
+#include <Bnd_Tools.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
 #include <BRepBndLib.hxx>
@@ -39,7 +40,6 @@
 #include <IntTools_Context.hxx>
 #include <NCollection_DataMap.hxx>
 #include <NCollection_List.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <NCollection_Vector.hxx>
 #include <TColStd_MapIntegerHasher.hxx>
 #include <TopAbs.hxx>
@@ -443,24 +443,23 @@ void BOPAlgo_BuilderSolid::PerformAreas()
 
   // Classify holes relatively solids
 
-  // Prepare tree filler with the boxes of the hole shells
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
-
+  // Prepare tree with the boxes of the hole shells
+  BOPTools_BoxTree aBBTree;
   Standard_Integer i, aNbH = aHoleShells.Extent();
+  aBBTree.SetSize (aNbH);
   for (i = 1; i <= aNbH; ++i)
   {
     const TopoDS_Shape& aHShell = aHoleShells(i);
     //
     Bnd_Box aBox;
     BRepBndLib::Add(aHShell, aBox);
-    aTreeFiller.Add(i, aBox);
+    aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
 
     myBoxes.Bind(aHShell, aBox);
   }
 
-  // Shake TreeFiller
-  aTreeFiller.Fill();
+  // Build BVH
+  aBBTree.Build();
 
   // Find outer growth shell that is most close to each hole shell
   TopTools_IndexedDataMapOfShapeShape aHoleSolidMap;
@@ -476,9 +475,10 @@ void BOPAlgo_BuilderSolid::PerformAreas()
 
     myBoxes.Bind(aSolid, aBox);
 
-    BOPTools_BoxBndTreeSelector aSelector;
-    aSelector.SetBox(aBox);
-    aBBTree.Select(aSelector);
+    BOPTools_BoxTreeSelector aSelector;
+    aSelector.SetBox(Bnd_Tools::Bnd2BVH(aBox));
+    aSelector.SetBVHSet (&aBBTree);
+    aSelector.Select();
 
     const TColStd_ListOfInteger& aLI = aSelector.Indices();
     TColStd_ListIteratorOfListOfInteger aItLI(aLI);
index d03fac1..a12e527 100644 (file)
@@ -298,7 +298,7 @@ void BOPAlgo_PaveFiller::PerformInternal()
   //
   MakeSplitEdges();
   if (HasErrors()) {
-    return; 
+    return;
   }
   //
   UpdatePaveBlocksWithSDVertices();
@@ -361,7 +361,7 @@ void BOPAlgo_PaveFiller::RepeatIntersection()
     return;
 
   // Update iterator of pairs of shapes with interfering boxes
-  myIterator->PrepareExt(anExtraInterfMap);
+  myIterator->IntersectExt(anExtraInterfMap);
 
   // Perform intersections with vertices
   PerformVV();
index 4171cc9..6994be6 100644 (file)
@@ -595,7 +595,7 @@ void BOPAlgo_PaveFiller::TreatNewVertices
   //
   // Perform intersection
   TopTools_ListOfListOfShape aChains;
-  BOPAlgo_Tools::IntersectVertices(aVerts, myRunParallel, myFuzzyValue, aChains);
+  BOPAlgo_Tools::IntersectVertices(aVerts, myFuzzyValue, aChains);
   //
   // Treat the results - make new vertices for each chain
   TopTools_ListOfListOfShape::Iterator aItC(aChains);
index c6b43cf..7248bf9 100644 (file)
@@ -17,6 +17,7 @@
 
 
 #include <Bnd_Box.hxx>
+#include <Bnd_Tools.hxx>
 #include <BOPAlgo_PaveFiller.hxx>
 #include <BOPAlgo_Alerts.hxx>
 #include <BOPAlgo_Tools.hxx>
@@ -31,7 +32,6 @@
 #include <BOPDS_PaveBlock.hxx>
 #include <BOPTools_AlgoTools.hxx>
 #include <BOPTools_AlgoTools2D.hxx>
-#include <BOPTools_BoxSelector.hxx>
 #include <BOPTools_Parallel.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
@@ -729,8 +729,7 @@ void BOPAlgo_PaveFiller::ForceInterfEF(const BOPDS_IndexedMapOfPaveBlock& theMPB
     return;
 
   // Fill the tree with bounding boxes of the pave blocks
-  NCollection_UBTree<Standard_Integer, Bnd_Box> aBBTree;
-  NCollection_UBTreeFiller<Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
+  BOPTools_BoxTree aBBTree;
 
   Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
   BOPDS_IndexedMapOfPaveBlock aPBMap(1, anAlloc);
@@ -751,11 +750,11 @@ void BOPAlgo_PaveFiller::ForceInterfEF(const BOPDS_IndexedMapOfPaveBlock& theMPB
     Standard_Boolean isSplit;
     aPB->ShrunkData(f, l, aPBBox, isSplit);
 
-    aTreeFiller.Add(aPBMap.Add(aPB), aPBBox);
+    aBBTree.Add(aPBMap.Add(aPB), Bnd_Tools::Bnd2BVH(aPBBox));
   }
 
   // Shake the tree
-  aTreeFiller.Fill();
+  aBBTree.Build();
 
   // Find pairs of Face/PaveBlock containing the same vertices
   // and prepare those pairs for intersection.
@@ -774,10 +773,10 @@ void BOPAlgo_PaveFiller::ForceInterfEF(const BOPDS_IndexedMapOfPaveBlock& theMPB
       continue;
 
     const Bnd_Box& aBoxF = aSI.Box();
-    BOPTools_BoxSelector<Bnd_Box> aSelector;
-    aSelector.SetBox(aBoxF);
-
-    if (!aBBTree.Select(aSelector))
+    BOPTools_BoxTreeSelector aSelector;
+    aSelector.SetBox(Bnd_Tools::Bnd2BVH(aBoxF));
+    aSelector.SetBVHSet (&aBBTree);
+    if (!aSelector.Select())
       continue;
 
     const TopoDS_Face& aF = TopoDS::Face(aSI.Shape());
index fa93d31..b5b7625 100644 (file)
@@ -25,7 +25,7 @@
 #include <BOPDS_PaveBlock.hxx>
 #include <BOPTools_AlgoTools.hxx>
 #include <BOPTools_AlgoTools2D.hxx>
-#include <BOPTools_BoxBndTree.hxx>
+#include <BOPTools_BoxTree.hxx>
 #include <BOPTools_Parallel.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
@@ -33,6 +33,7 @@
 #include <BRepBndLib.hxx>
 #include <BRepBuilderAPI_MakeFace.hxx>
 #include <BRepLib.hxx>
+#include <Bnd_Tools.hxx>
 #include <GeomAPI_ProjectPointOnCurve.hxx>
 #include <GeomAPI_ProjectPointOnSurf.hxx>
 #include <gp_Circ.hxx>
@@ -45,7 +46,6 @@
 #include <gp_Vec.hxx>
 #include <IntTools_Context.hxx>
 #include <NCollection_IncAllocator.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <NCollection_Vector.hxx>
 #include <Standard_ErrorHandler.hxx>
 #include <Standard_Failure.hxx>
@@ -954,78 +954,66 @@ Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
 
 /////////////////////////////////////////////////////////////////////////
 //=======================================================================
-//class    : BOPAlgo_TNV
+//class    : BOPAlgo_PairVerticesSelector
 //purpose  : 
 //=======================================================================
-class BOPAlgo_TNV;
-typedef NCollection_Vector<BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
+class BOPAlgo_PairVerticesSelector : public BOPTools_BoxPairSelector
+{
+public:
 
-//=======================================================================
-class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
- public:
-  BOPAlgo_TNV() 
-    : BOPTools_BoxBndTreeSelector(),
-      myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
-  };
-  //
-  ~BOPAlgo_TNV(){
-  };
-  //
-  void SetVertex(const TopoDS_Vertex& aV) {
-    myV=aV;
-    myPnt = BRep_Tool::Pnt(myV);
-  }
-  //
-  const TopoDS_Vertex& Vertex()const {
-    return myV;
-  }
-  //
-  void SetTree(BOPTools_BoxBndTree& aTree) {
-    myTree=&aTree;
-  }
-  //
-  void SetTolerance(const Standard_Real theTol) {
-    myTol = theTol;
-  }
-  //
-  Standard_Real Tolerance() const {
-    return myTol;
-  }
-  //
-  const gp_Pnt& Pnt() const {
-    return myPnt;
+  BOPAlgo_PairVerticesSelector()
+    : myVertices(NULL),
+      myFuzzyValue(Precision::Confusion())
+  {}
+
+  //! Sets the map of vertices with tolerances
+  void SetMapOfVerticesTolerances (const TopTools_IndexedDataMapOfShapeReal& theVertices)
+  {
+    myVertices = &theVertices;
   }
-  //
-  void SetFuzzyValue(const Standard_Real theFuzzyValue) {
+
+  //! Sets the fuzzy value
+  void SetFuzzyValue (const Standard_Real theFuzzyValue)
+  {
     myFuzzyValue = theFuzzyValue;
   }
-  //
-  void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
-    myVecTNV = &theVec;
-  }
-  //
-  virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
+
+  //! Checks and accepts the pair of elements.
+  virtual Standard_Boolean Accept (const Standard_Integer theID1,
+                                   const Standard_Integer theID2) Standard_OVERRIDE
   {
-    const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
-    Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
-    aTolSum2 *= aTolSum2;
-    Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
-    if (aD2 < aTolSum2)
-      return BOPTools_BoxBndTreeSelector::Accept(theIndex);
+    if (!RejectElement (theID1, theID2))
+    {
+      const Standard_Integer anID1 = this->myBVHSet1->Element (theID1);
+      const TopoDS_Vertex& aV1 = TopoDS::Vertex (myVertices->FindKey (anID1));
+      Standard_Real aTolV1 = BRep_Tool::Tolerance (aV1);
+      if (aTolV1 < myVertices->FindFromIndex (anID1))
+        aTolV1 = myVertices->FindFromIndex (anID1);
+      gp_Pnt aP1 = BRep_Tool::Pnt (aV1);
+
+      const Standard_Integer anID2 = this->myBVHSet1->Element (theID2);
+      const TopoDS_Vertex& aV2 = TopoDS::Vertex (myVertices->FindKey (anID2));
+      Standard_Real aTolV2 = BRep_Tool::Tolerance (aV2);
+      if (aTolV2 < myVertices->FindFromIndex (anID2))
+        aTolV2 = myVertices->FindFromIndex (anID2);
+      gp_Pnt aP2 = BRep_Tool::Pnt (aV2);
+
+      Standard_Real aTolSum2 = aTolV1 + aTolV2 + myFuzzyValue;
+      aTolSum2 *= aTolSum2;
+
+      Standard_Real aD2 = aP1.SquareDistance (aP2);
+      if (aD2 < aTolSum2)
+      {
+        myPairs.push_back (PairIDs (anID1, anID2));
+        return Standard_True;
+      }
+    }
     return Standard_False;
   }
-  //
-  void Perform() {
-    myTree->Select(*this);
-  }
-  //
- protected:
-  Standard_Real myTol;
+
+protected:
+  const TopTools_IndexedDataMapOfShapeReal * myVertices;
   Standard_Real myFuzzyValue;
-  gp_Pnt        myPnt;
-  TopoDS_Vertex myV;
-  BOPTools_BoxBndTree *myTree;
-  const BOPAlgo_VectorOfTNV *myVecTNV;
 };
 //
 /////////////////////////////////////////////////////////////////////////
@@ -1035,84 +1023,82 @@ class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
 //purpose  : Builds the chains of intersecting vertices
 //=======================================================================
 void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
-                                      const Standard_Boolean theRunParallel,
                                       const Standard_Real theFuzzyValue,
                                       TopTools_ListOfListOfShape& theChains)
 {
-  Standard_Integer i, j, aNbV = theVertices.Extent();
+  Standard_Integer aNbV = theVertices.Extent();
   if (aNbV <= 1) {
     if (aNbV == 1) {
       theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
     }
     return;
   }
-  //
-  // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, 
-                            Bnd_Box> aTreeFiller(aBBTree);
-  // Perform intersection of the vertices
-  BOPAlgo_VectorOfTNV aVTNV;
-  //
-  // Use additional tolerance for intersection
+
+  // Additional tolerance for intersection
   Standard_Real aTolAdd = theFuzzyValue / 2.;
-  // Prepare the tree
-  for (i = 1; i <= aNbV; ++i) {
+
+  // Use BVH Tree for sorting the vertices
+  BOPTools_BoxTree aBBTree;
+  aBBTree.SetSize (aNbV);
+
+  for (Standard_Integer i = 1; i <= aNbV; ++i)
+  {
     const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
     Standard_Real aTol = BRep_Tool::Tolerance(aV);
-    if (aTol < theVertices(i)) {
+    if (aTol < theVertices(i))
       aTol = theVertices(i);
-    }
+
     // Build bnd box for vertex
     Bnd_Box aBox;
     aBox.Add(BRep_Tool::Pnt(aV));
     aBox.SetGap(aTol + aTolAdd);
-    //
-    aTreeFiller.Add(i, aBox);
-    //
-    BOPAlgo_TNV& aTNV=aVTNV.Appended();
-    aTNV.SetTree(aBBTree);
-    aTNV.SetBox(aBox);
-    aTNV.SetVertex(aV);
-    aTNV.SetTolerance(aTol);
-    aTNV.SetFuzzyValue(theFuzzyValue);
-    aTNV.SetVectorOfTNV(aVTNV);
+    aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBox));
   }
-  // Shake the tree
-  aTreeFiller.Fill();
-  //
-  // Perform intersection
-  BOPTools_Parallel::Perform (theRunParallel, aVTNV);
-  //
-  // Fence map
-  TColStd_MapOfInteger aMFence;
-  // Build chains of intersecting vertices
-  for (i = 1; i <= aNbV; ++i) {
-    if (!aMFence.Add(i)) {
-      continue;
-    }
-    // Start the chain
-    TColStd_IndexedMapOfInteger aMChain;
-    aMChain.Add(i);
-    //
-    for (j = 1; j <= aMChain.Extent(); ++j) {
-      BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
-      const TColStd_ListOfInteger& aLI = aTNV.Indices();
-      // Add these vertices into the chain
-      for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
-        if (aMFence.Add(aItLI.Value())) {
-          aMChain.Add(aItLI.Value());
-        }
-      }
-    }
-    //
-    // Put vertices of the chain into the list
-    TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
-    //
-    Standard_Integer aNbVChain = aMChain.Extent();
-    for (j = 1; j <= aNbVChain; ++j) {
-      const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
-      aChain.Append(aVP);
+
+  aBBTree.Build();
+
+  // Perform selection of the interfering vertices
+  BOPAlgo_PairVerticesSelector aPairSelector;
+  aPairSelector.SetBVHSets (&aBBTree, &aBBTree);
+  aPairSelector.SetSame (Standard_True);
+  aPairSelector.SetMapOfVerticesTolerances (theVertices);
+  aPairSelector.SetFuzzyValue (theFuzzyValue);
+  aPairSelector.Select();
+
+  // Treat the selected pairs
+  const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
+
+  // Collect interfering pairs
+  Handle(NCollection_IncAllocator) anAlloc = new NCollection_IncAllocator;
+  NCollection_IndexedDataMap<Standard_Integer, TColStd_ListOfInteger> aMILI (1, anAlloc);
+
+  for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
+  {
+    const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
+    BOPAlgo_Tools::FillMap<Standard_Integer, TColStd_MapIntegerHasher> (aPair.ID1, aPair.ID2, aMILI, anAlloc);
+  }
+
+  NCollection_List<TColStd_ListOfInteger> aBlocks (anAlloc);
+  BOPAlgo_Tools::MakeBlocks<Standard_Integer, TColStd_MapIntegerHasher> (aMILI, aBlocks, anAlloc);
+
+  NCollection_List<TColStd_ListOfInteger>::Iterator itLI (aBlocks);
+  for (; itLI.More(); itLI.Next())
+  {
+    const TColStd_ListOfInteger& aLI = itLI.Value();
+    TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
+    
+    for (TColStd_ListOfInteger::Iterator itI (aLI); itI.More(); itI.Next())
+      aChain.Append (theVertices.FindKey (itI.Value()));
+  }
+
+  // Add not interfered vertices as a chain of 1 element
+  for (Standard_Integer i = 1; i <= aNbV; ++i)
+  {
+    if (!aMILI.Contains (i))
+    {
+      TopTools_ListOfShape &aChain = theChains.Append (TopTools_ListOfShape());
+      aChain.Append (theVertices.FindKey(i));
     }
   }
 }
@@ -1236,9 +1222,9 @@ public:
   };
 
   //! Sets the Bounding Box tree
-  void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
+  void SetBBTree(BOPTools_BoxTree* theBBTree)
   {
-    myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
+    myBBTree = theBBTree;
   };
 
   //! Sets the ShapeBox structure
@@ -1288,7 +1274,7 @@ private:
   TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
   TopTools_ListOfShape myInFaces; //! Faces classified as IN
 
-  BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
+  BOPTools_BoxTree* myBBTree; //! BVH tree of bounding boxes
   BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
 
   TopoDS_Iterator myItF; //! Iterators
@@ -1308,10 +1294,11 @@ void BOPAlgo_FillIn3DParts::Perform()
   myInFaces.Clear();
 
   // 1. Select boxes of faces that are not out of aBoxS
-  BOPTools_BoxBndTreeSelector aSelector;
-  aSelector.SetBox(myBoxS);
+  BOPTools_BoxTreeSelector aSelector;
+  aSelector.SetBox(Bnd_Tools::Bnd2BVH(myBoxS));
+  aSelector.SetBVHSet (myBBTree);
   //
-  if (!myBBTree->Select(aSelector))
+  if (!aSelector.Select())
     return;
 
   const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
@@ -1559,19 +1546,18 @@ void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
     }
   }
 
-  // Prepare UB tree of bounding boxes of the faces to classify
+  // Prepare BVH tree of bounding boxes of the faces to classify
   // taking the bounding boxes from the just prepared vector
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
-
+  BOPTools_BoxTree aBBTree;
   Standard_Integer aNbF = aVSB.Length();
+  aBBTree.SetSize (aNbF);
   for (Standard_Integer i = 0; i < aNbF; ++i)
   {
-    aTreeFiller.Add(i, aVSB(i).Box());
+    aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aVSB(i).Box()));
   }
 
   // Shake tree filler
-  aTreeFiller.Fill();
+  aBBTree.Build();
 
   // Prepare vector of solids to classify
   BOPAlgo_VectorOfFillIn3DParts aVFIP;
@@ -1605,7 +1591,7 @@ void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
     if (pLIF)
       aFIP.SetOwnIF(*pLIF);
 
-    aFIP.SetBBTree(aBBTree);
+    aFIP.SetBBTree(&aBBTree);
     aFIP.SetShapeBoxVector(aVSB);
   }
 
index 50492e9..9d20dd3 100644 (file)
@@ -162,7 +162,6 @@ public:
 
   //! Finds chains of intersecting vertices
   Standard_EXPORT static void IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
-                                                const Standard_Boolean theRunParallel,
                                                 const Standard_Real theFuzzyValue,
                                                 TopTools_ListOfListOfShape& theChains);
 
index 0322838..a685c02 100644 (file)
 
 #include <Bnd_Box.hxx>
 #include <Bnd_OBB.hxx>
+#include <Bnd_Tools.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_IndexRange.hxx>
 #include <BOPDS_Iterator.hxx>
 #include <BOPDS_Pair.hxx>
 #include <BOPDS_MapOfPair.hxx>
 #include <BOPDS_Tools.hxx>
-#include <BOPTools_BoxBndTree.hxx>
+#include <BOPTools_BoxTree.hxx>
 #include <BOPTools_Parallel.hxx>
 #include <IntTools_Context.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <NCollection_Vector.hxx>
 #include <TopoDS_Shape.hxx>
 #include <algorithm>
 //class    : BOPDS_TreeSelector
 //purpose  : 
 //=======================================================================
-class BOPDS_TSR : public BOPTools_BoxBndTreeSelector{
+class BOPDS_TSR : public BOPTools_BoxTreeSelector
+{
  public:
   BOPDS_TSR() : 
-    BOPTools_BoxBndTreeSelector(), 
+    BOPTools_BoxTreeSelector(), 
     myHasBRep(Standard_False), 
-    myTree(NULL),
     myIndex(-1) {}
   //
   virtual ~BOPDS_TSR() {
@@ -52,23 +52,18 @@ class BOPDS_TSR : public BOPTools_BoxBndTreeSelector{
     myHasBRep=bFlag;
   }
   //
-  void SetTree(BOPTools_BoxBndTree& aTree) {
-    myTree=&aTree;
-  }
-  //
   void SetIndex(const Standard_Integer theIndex) { myIndex = theIndex; }
   //
   Standard_Integer Index() const { return myIndex; }
   //
   void Perform() {
     if (myHasBRep) {
-      myTree->Select(*this);
+      Select();
     }
   }
   //
  protected:
   Standard_Boolean myHasBRep;
-  BOPTools_BoxBndTree *myTree;
   Standard_Integer myIndex;
 };
 //
@@ -76,7 +71,6 @@ class BOPDS_TSR : public BOPTools_BoxBndTreeSelector{
 typedef NCollection_Vector<BOPDS_TSR> BOPDS_VectorOfTSR;
 /////////////////////////////////////////////////////////////////////////
 
-
 //=======================================================================
 //function : 
 //purpose  : 
@@ -289,142 +283,81 @@ void BOPDS_Iterator::Intersect(const Handle(IntTools_Context)& theCtx,
                                const Standard_Boolean theCheckOBB,
                                const Standard_Real theFuzzyValue)
 {
-  Standard_Integer i, j, iX, i1, i2, iR, aNb, aNbR;
-  Standard_Integer iTi, iTj;
-  TopAbs_ShapeEnum aTi, aTj;
-  //
-  myBoxTree.Clear();
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(myBoxTree);
-  //
-  aNb = myDS->NbSourceShapes();
-  BOPDS_VectorOfTSR aVTSR(aNb);
-  //
-  for (i=0; i<aNb; ++i) {
-    const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
-    Standard_Boolean bHasBrep = aSI.IsInterfering() && !(aSI.ShapeType() == TopAbs_SOLID);
-    //
-    BOPDS_TSR& aTSR=aVTSR.Appended();
-    //
-    aTSR.SetHasBRep(bHasBrep);
-    if (!bHasBrep) {
+  const Standard_Integer aNb = myDS->NbSourceShapes();
+
+  // Prepare BVH
+  BOPTools_BoxTree aBoxTree;
+  aBoxTree.SetSize (aNb);
+  for (Standard_Integer i = 0; i < aNb; ++i)
+  {
+    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
+    if (!aSI.HasBRep())
       continue;
-    }
-    //
-    const Bnd_Box& aBoxEx=aSI.Box();
-    aTSR.SetTree(myBoxTree);
-    aTSR.SetBox(aBoxEx);
-    aTSR.SetIndex(i);
-    //
-    aTreeFiller.Add(i, aBoxEx);
+    const Bnd_Box& aBox = aSI.Box();
+    aBoxTree.Add (i, Bnd_Tools::Bnd2BVH (aBox));
   }
-  //
-  aTreeFiller.Fill();
-  //
-  //===========================================
-  BOPTools_Parallel::Perform (myRunParallel, aVTSR);
-  //===========================================
-  //
-  BOPDS_MapOfPair aMPFence;
-  //
-  aNbR = myDS->NbRanges() - 1;
-  for (iR = 0; iR < aNbR; ++iR) {
-    const BOPDS_IndexRange& aR = myDS->Range(iR);
-    i1 = aR.First();
-    i2 = aR.Last();
-    for (i = i1; i <= i2; ++i) {
-      const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
-      //
-      if (!aSI.IsInterfering() || (aSI.ShapeType() == TopAbs_SOLID)) {
-        continue;
-      }
-      //
-      BOPDS_TSR& aTSRi = aVTSR(i);
-      const TColStd_ListOfInteger& aLI = aTSRi.Indices();
-      Standard_Integer aNbSD = aLI.Extent();
-      if (!aNbSD) {
-        continue;
-      }
-      //
-      aTi = aSI.ShapeType();
-      iTi = BOPDS_Tools::TypeToInteger(aTi);
-      //
-      TColStd_ListIteratorOfListOfInteger aIt(aLI);
-      for (; aIt.More(); aIt.Next()) {
-        j = aIt.Value(); // DS index
-        if (j >= i1 && j <= i2) {
-          continue;// same range
-        }
-        //
-        const BOPDS_ShapeInfo& aSJ = myDS->ShapeInfo(j);
-        aTj = aSJ.ShapeType();
-        iTj = BOPDS_Tools::TypeToInteger(aTj);
-        //
-        // avoid interfering of the same shapes and shape with its sub-shapes
-        if (((iTi < iTj) && aSI.HasSubShape(j)) ||
-            ((iTi > iTj) && aSJ.HasSubShape(i))) {
-          continue;
-        }
-        //
-        BOPDS_Pair aPair(i, j);
-        if (aMPFence.Add(aPair)) {
-          if (theCheckOBB)
-          {
-            // Check intersection of Oriented bounding boxes of the shapes
-            Bnd_OBB& anOBBi = theCtx->OBB(aSI.Shape(), theFuzzyValue);
-            Bnd_OBB& anOBBj = theCtx->OBB(aSJ.Shape(), theFuzzyValue);
-
-            if (anOBBi.IsOut(anOBBj))
-              continue;
-          }
-
-          iX = BOPDS_Tools::TypeToInteger(aTi, aTj);
-          myLists(iX).Append(aPair);
-        }// if (aMPFence.Add(aPair)) {
-      }// for (; aIt.More(); aIt.Next()) {
-    }//for (i=i1; i<=i2; ++i) {
-  }//for (iR=1; iR<aNbR; ++iR) {
-  //
-  aMPFence.Clear();
-  aVTSR.Clear();
-  //-----------------------------------------------------scope_1 t
-}
 
-//=======================================================================
-// function: PrepareExt
-// purpose: 
-//=======================================================================
-void BOPDS_Iterator::PrepareExt(const TColStd_MapOfInteger& theIndices)
-{
-  if (!myDS)
-    return;
+  // Build BVH
+  aBoxTree.Build();
+
+  // Select pairs of shapes with interfering bounding boxes
+  BOPTools_BoxPairSelector aPairSelector;
+  aPairSelector.SetBVHSets (&aBoxTree, &aBoxTree);
+  aPairSelector.SetSame (Standard_True);
+  aPairSelector.Select();
+  aPairSelector.Sort();
 
-  // Update UB tree of bounding boxes with the increased shapes.
-  // It is expected that not too many shapes will be modified during
-  // the intersection, so after updating the tree it should not become
-  // too unbalanced.
-  TColStd_MapIteratorOfMapOfInteger itM(theIndices);
-  for (; itM.More(); itM.Next())
+  // Treat the selected pairs
+  const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
+
+  Standard_Integer iPair = 0;
+
+  const Standard_Integer aNbR = myDS->NbRanges();
+  for (Standard_Integer iR = 0; iR < aNbR; ++iR)
   {
-    Standard_Integer nV = itM.Value();
-    myBoxTree.Remove(nV);
+    const BOPDS_IndexRange& aRange = myDS->Range(iR);
 
-    // Add with new box
-    Standard_Integer nVSD = nV;
-    myDS->HasShapeSD(nV, nVSD);
-    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nVSD);
-    const Bnd_Box& aBox = aSI.Box();
-    myBoxTree.Add(nV, aBox);
-  }
+    for (; iPair < aNbPairs; ++iPair)
+    {
+      const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
+      if (!aRange.Contains (aPair.ID1))
+        // Go to the next range
+        break;
 
-  // Clear the extra lists
-  const Standard_Integer aNbExt = BOPDS_Iterator::NbExtInterfs();
-  myLength = 0;
-  for (Standard_Integer i = 0; i < aNbExt; ++i)
-    myExtLists(i).Clear();
+      if (aRange.Contains (aPair.ID2))
+        // Go to the next pair
+        continue;
 
-  IntersectExt(theIndices);
+      const BOPDS_ShapeInfo& aSI1 = myDS->ShapeInfo (aPair.ID1);
+      const BOPDS_ShapeInfo& aSI2 = myDS->ShapeInfo (aPair.ID2);
 
-  myUseExt = Standard_True;
+      const TopAbs_ShapeEnum aType1 = aSI1.ShapeType();
+      const TopAbs_ShapeEnum aType2 = aSI2.ShapeType();
+
+      Standard_Integer iType1 = BOPDS_Tools::TypeToInteger (aType1);
+      Standard_Integer iType2 = BOPDS_Tools::TypeToInteger (aType2);
+
+      // avoid interfering of the shape with its sub-shapes
+      if (((iType1 < iType2) && aSI1.HasSubShape (aPair.ID2)) ||
+          ((iType1 > iType2) && aSI2.HasSubShape (aPair.ID1)))
+        continue;
+
+      if (theCheckOBB)
+      {
+        // Check intersection of Oriented bounding boxes of the shapes
+        const Bnd_OBB& anOBB1 = theCtx->OBB (aSI1.Shape(), theFuzzyValue);
+        const Bnd_OBB& anOBB2 = theCtx->OBB (aSI2.Shape(), theFuzzyValue);
+
+        if (anOBB1.IsOut (anOBB2))
+          continue;
+      }
+
+      Standard_Integer iX = BOPDS_Tools::TypeToInteger (aType1, aType2);
+      myLists(iX).Append (BOPDS_Pair (Min (aPair.ID1, aPair.ID2),
+                                      Max (aPair.ID1, aPair.ID2)));
+    }
+  }
 }
 
 //=======================================================================
@@ -433,24 +366,43 @@ void BOPDS_Iterator::PrepareExt(const TColStd_MapOfInteger& theIndices)
 //=======================================================================
 void BOPDS_Iterator::IntersectExt(const TColStd_MapOfInteger& theIndices)
 {
-  // Prepare vector for parallel selection
-  BOPDS_VectorOfTSR aVTSR(theIndices.Extent());
+  if (!myDS)
+    return;
 
-  TColStd_MapIteratorOfMapOfInteger itM(theIndices);
-  for (; itM.More(); itM.Next())
+  const Standard_Integer aNb = myDS->NbSourceShapes();
+
+  BOPTools_BoxTree aBoxTree;
+  aBoxTree.SetSize (aNb);
+  BOPDS_VectorOfTSR aVTSR(theIndices.Extent());
+  //
+  for (Standard_Integer i = 0; i < aNb; ++i)
   {
-    Standard_Integer nV = itM.Value();
-    Standard_Integer nVSD = nV;
-    myDS->HasShapeSD(nV, nVSD);
-    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nVSD);
-    const Bnd_Box& aBox = aSI.Box();
-    BOPDS_TSR& aTSR = aVTSR.Appended();
-    aTSR.SetHasBRep(Standard_True);
-    aTSR.SetTree(myBoxTree);
-    aTSR.SetBox(aBox);
-    aTSR.SetIndex(nV);
+    const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
+    if (!aSI.IsInterfering() || (aSI.ShapeType() == TopAbs_SOLID))
+      continue;
+    //
+    if (theIndices.Contains (i))
+    {
+      Standard_Integer nVSD = i;
+      myDS->HasShapeSD (i, nVSD);
+      const BOPDS_ShapeInfo& aSISD = myDS->ShapeInfo (nVSD);
+      const Bnd_Box& aBox = aSISD.Box ();
+      aBoxTree.Add (i, Bnd_Tools::Bnd2BVH(aBox));
+
+      BOPDS_TSR& aTSR=aVTSR.Appended();
+      aTSR.SetHasBRep(Standard_True);
+      aTSR.SetBVHSet (&aBoxTree);
+      aTSR.SetBox (Bnd_Tools::Bnd2BVH (aBox));
+      aTSR.SetIndex (i);
+    }
+    else
+    {
+      aBoxTree.Add (i, Bnd_Tools::Bnd2BVH (aSI.Box ()));
+    }
   }
 
+  aBoxTree.Build();
+
   // Perform selection
   BOPTools_Parallel::Perform (myRunParallel, aVTSR);
 
@@ -459,8 +411,8 @@ void BOPDS_Iterator::IntersectExt(const TColStd_MapOfInteger& theIndices)
   // Fence map to avoid duplicating pairs
   BOPDS_MapOfPair aMPFence;
 
-  const Standard_Integer aNb = aVTSR.Length();
-  for (Standard_Integer k = 0; k < aNb; ++k)
+  const Standard_Integer aNbV = aVTSR.Length();
+  for (Standard_Integer k = 0; k < aNbV; ++k)
   {
     BOPDS_TSR& aTSRi = aVTSR(k);
     const TColStd_ListOfInteger& aLI = aTSRi.Indices();
@@ -485,7 +437,7 @@ void BOPDS_Iterator::IntersectExt(const TColStd_MapOfInteger& theIndices)
       const TopAbs_ShapeEnum aTJ = aSJ.ShapeType();
       const Standard_Integer iTJ = BOPDS_Tools::TypeToInteger(aTJ);
 
-      // avoid interfering of the same shapes and shape with its sub-shapes
+      // avoid interfering of the shape with its sub-shapes
       if (((iTI < iTJ) && aSI.HasSubShape(j)) ||
           ((iTI > iTJ) && aSJ.HasSubShape(i)))
         continue;
@@ -499,4 +451,6 @@ void BOPDS_Iterator::IntersectExt(const TColStd_MapOfInteger& theIndices)
       }
     }
   }
+
+  myUseExt = Standard_True;
 }
index 04b339a..9faf534 100644 (file)
@@ -26,7 +26,7 @@
 #include <BOPDS_PDS.hxx>
 #include <BOPDS_VectorOfPair.hxx>
 #include <BOPDS_VectorOfVectorOfPair.hxx>
-#include <BOPTools_BoxBndTree.hxx>
+#include <BOPTools_BoxTree.hxx>
 #include <NCollection_BaseAllocator.hxx>
 #include <Precision.hxx>
 #include <Standard_Boolean.hxx>
@@ -88,7 +88,7 @@ public:
 
   //! Updates the tree of Bounding Boxes with increased boxes and
   //! intersects such elements with the tree.
-  Standard_EXPORT void PrepareExt(const TColStd_MapOfInteger& theIndicies);
+  Standard_EXPORT void IntersectExt(const TColStd_MapOfInteger& theIndicies);
 
   //! Returns the number of intersections founded
   Standard_EXPORT Standard_Integer ExpectedLength() const;
@@ -119,12 +119,6 @@ protected: //! @name Protected methods for bounding boxes intersection
                                          const Standard_Boolean theCheckOBB = Standard_False,
                                          const Standard_Real theFuzzyValue = Precision::Confusion());
 
-  //! Intersects the bounding boxes of the shapes with given indices in DS
-  //! with the tree of bounding boxes and saves the interfering pairs in
-  //! extra lists for further geometrical intersection.
-  Standard_EXPORT void IntersectExt(const TColStd_MapOfInteger& theIndices);
-
-
 protected: //! @name Fields
 
   Handle(NCollection_BaseAllocator) myAllocator; //!< Allocator
@@ -134,7 +128,6 @@ protected: //! @name Fields
   BOPDS_VectorOfVectorOfPair myLists;            //!< Pairs with interfering bounding boxes
   BOPDS_VectorOfPair::Iterator myIterator;       //!< Iterator on each interfering type
   Standard_Boolean myRunParallel;                //!< Flag for parallel processing
-  BOPTools_BoxBndTree myBoxTree;                 //!< Unbalanced tree of bounding boxes
   BOPDS_VectorOfVectorOfPair myExtLists;         //!< Extra pairs of sub-shapes found after
                                                  //! intersection of increased sub-shapes
   Standard_Boolean myUseExt;                     //!< Information flag for using the extra lists
index 3b82401..13f0926 100644 (file)
@@ -14,6 +14,7 @@
 
 #include <Bnd_Box.hxx>
 #include <Bnd_OBB.hxx>
+#include <Bnd_Tools.hxx>
 #include <BOPDS_DS.hxx>
 #include <BOPDS_IndexRange.hxx>
 #include <BOPDS_IteratorSI.hxx>
 #include <BOPDS_Pair.hxx>
 #include <BOPDS_ShapeInfo.hxx>
 #include <BOPDS_Tools.hxx>
-#include <BOPTools_BoxBndTree.hxx>
+#include <BOPTools_BoxTree.hxx>
 #include <BRep_Tool.hxx>
 #include <gp_Pnt.hxx>
 #include <IntTools_Context.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <TopAbs_ShapeEnum.hxx>
 #include <TColStd_DataMapOfIntegerInteger.hxx>
 #include <TColStd_DataMapOfIntegerListOfInteger.hxx>
@@ -79,83 +79,68 @@ void BOPDS_IteratorSI::UpdateByLevelOfCheck(const Standard_Integer theLevel)
 // function: Intersect
 // purpose: 
 //=======================================================================
-void BOPDS_IteratorSI::Intersect(const Handle(IntTools_Context)& theCtx,
-                                 const Standard_Boolean theCheckOBB,
-                                 const Standard_Real theFuzzyValue)
+void BOPDS_IteratorSI::Intersect (const Handle(IntTools_Context)& theCtx,
+                                  const Standard_Boolean theCheckOBB,
+                                  const Standard_Real theFuzzyValue)
 {
-  Standard_Integer i, j, iX, aNbS;
-  Standard_Integer iTi, iTj;
-  TopAbs_ShapeEnum aTi, aTj;
-  //
-  BOPTools_BoxBndTreeSelector aSelector;
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
-  //
-  aNbS = myDS->NbSourceShapes();
-  for (i=0; i<aNbS; ++i) {
-    const BOPDS_ShapeInfo& aSI=myDS->ShapeInfo(i);
-    if (!aSI.IsInterfering()) {
+  const Standard_Integer aNbS = myDS->NbSourceShapes();
+
+  BOPTools_BoxTree aBBTree;
+  aBBTree.SetSize (aNbS);
+
+  for (Standard_Integer i = 0; i < aNbS; ++i)
+  {
+    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo (i);
+    if (!aSI.IsInterfering())
       continue;
-    }
-    //
+
     const Bnd_Box& aBoxEx = aSI.Box();
-    aTreeFiller.Add(i, aBoxEx);
+    aBBTree.Add (i, Bnd_Tools::Bnd2BVH (aBoxEx));
   }
-  //
-  aTreeFiller.Fill();
-  //
-  BOPDS_MapOfPair aMPFence;
-  //
-  for (i = 0; i < aNbS; ++i) {
-    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
-    if (!aSI.IsInterfering()){
-      continue;
-    }
-    //
-    const Bnd_Box& aBoxEx = aSI.Box();
-    //
-    aSelector.Clear();
-    aSelector.SetBox(aBoxEx);
-    //
-    Standard_Integer aNbSD = aBBTree.Select(aSelector);
-    if (!aNbSD) {
+
+  aBBTree.Build();
+
+  // Select pairs of shapes with interfering bounding boxes
+  BOPTools_BoxPairSelector aPairSelector;
+  aPairSelector.SetBVHSets (&aBBTree, &aBBTree);
+  aPairSelector.SetSame (Standard_True);
+  aPairSelector.Select();
+  aPairSelector.Sort();
+
+  // Treat the selected pairs
+  const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
+
+  for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
+  {
+    const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
+
+    const BOPDS_ShapeInfo& aSI1 = myDS->ShapeInfo (aPair.ID1);
+    const BOPDS_ShapeInfo& aSI2 = myDS->ShapeInfo (aPair.ID2);
+
+    const TopAbs_ShapeEnum aType1 = aSI1.ShapeType();
+    const TopAbs_ShapeEnum aType2 = aSI2.ShapeType();
+
+    Standard_Integer iType1 = BOPDS_Tools::TypeToInteger (aType1);
+    Standard_Integer iType2 = BOPDS_Tools::TypeToInteger (aType2);
+
+    // avoid interfering of the shape with its sub-shapes
+    if (((iType1 < iType2) && aSI1.HasSubShape (aPair.ID2)) ||
+        ((iType1 > iType2) && aSI2.HasSubShape (aPair.ID1)))
       continue;
-    }
-    //
-    aTi = aSI.ShapeType();
-    iTi = BOPDS_Tools::TypeToInteger(aTi);
-    //
-    const TColStd_ListOfInteger& aLI = aSelector.Indices();
-    TColStd_ListIteratorOfListOfInteger aIt(aLI);
-    for (; aIt.More(); aIt.Next()) {
-      j = aIt.Value();
-      const BOPDS_ShapeInfo& aSJ = myDS->ShapeInfo(j);
-      aTj = aSJ.ShapeType();
-      iTj = BOPDS_Tools::TypeToInteger(aTj);
-      //
-      // avoid interfering of the same shapes and shape with its sub-shapes
-      if ((i == j) || ((iTi < iTj) && aSI.HasSubShape(j)) ||
-                      ((iTi > iTj) && aSJ.HasSubShape(i))) {
+
+    if (theCheckOBB)
+    {
+      // Check intersection of Oriented bounding boxes of the shapes
+      const Bnd_OBB& anOBB1 = theCtx->OBB (aSI1.Shape (), theFuzzyValue);
+      const Bnd_OBB& anOBB2 = theCtx->OBB (aSI2.Shape (), theFuzzyValue);
+
+      if (anOBB1.IsOut (anOBB2))
         continue;
-      }
-      //
-      BOPDS_Pair aPair(i, j);
-      if (aMPFence.Add(aPair)) {
-        if (theCheckOBB)
-        {
-          // Check intersection of Oriented bounding boxes of the shapes
-          Bnd_OBB& anOBBi = theCtx->OBB(aSI.Shape(), theFuzzyValue);
-          Bnd_OBB& anOBBj = theCtx->OBB(aSJ.Shape(), theFuzzyValue);
-
-          if (anOBBi.IsOut(anOBBj))
-            continue;
-        }
-
-        iX = BOPDS_Tools::TypeToInteger(aTi, aTj);
-        myLists(iX).Append(aPair);
-      }// if (aMPKXB.Add(aPKXB)) {
-    }// for (; aIt.More(); aIt.Next()) {
-  }//for (i=1; i<=aNbS; ++i) {
-  //
-  aMPFence.Clear();
+    }
+
+    Standard_Integer iX = BOPDS_Tools::TypeToInteger (aType1, aType2);
+    myLists(iX).Append (BOPDS_Pair (Min (aPair.ID1, aPair.ID2),
+                                    Max (aPair.ID1, aPair.ID2)));
+  }
 }
index f528d35..3acaa2b 100644 (file)
@@ -126,18 +126,7 @@ inline TColStd_ListOfInteger& BOPDS_ShapeInfo::ChangeSubShapes()
 inline Standard_Boolean BOPDS_ShapeInfo::HasSubShape
   (const Standard_Integer theI)const
 {
-  Standard_Boolean bRet;
-  TColStd_ListIteratorOfListOfInteger aIt;
-  //
-  bRet=Standard_False;
-  aIt.Initialize(mySubShapes);
-  for (; aIt.More(); aIt.Next()) {
-    bRet=(theI==aIt.Value());
-    if (bRet) {
-      return bRet;
-    }
-  }
-  return bRet;
+  return mySubShapes.Contains (theI);
 }
 //=======================================================================
 //function : HasReference
index 18ec0e5..5105fa3 100644 (file)
 #include <BOPDS_SubIterator.hxx>
 
 #include <Bnd_Box.hxx>
+#include <Bnd_Tools.hxx>
 
 #include <BOPDS_DS.hxx>
 #include <BOPDS_Pair.hxx>
 #include <BOPDS_MapOfPair.hxx>
 
-#include <BOPTools_BoxBndTree.hxx>
-
-#include <NCollection_UBTreeFiller.hxx>
+#include <BOPTools_BoxTree.hxx>
 
 #include <TopoDS_Shape.hxx>
 
@@ -115,60 +114,65 @@ void BOPDS_SubIterator::Initialize()
 // function: Intersect
 // purpose: 
 //=======================================================================
-  void BOPDS_SubIterator::Intersect()
+void BOPDS_SubIterator::Intersect()
 {
-  Standard_Integer i, j, iTi, iTj;
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
-  //
-  TColStd_ListIteratorOfListOfInteger aIt(*mySubSet1);
-  for (; aIt.More(); aIt.Next()) {
-    i = aIt.Value();
-    //
-    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
-    const Bnd_Box& aBoxEx = aSI.Box();
-    //
-    aTreeFiller.Add(i, aBoxEx);
+  if (!mySubSet1->Extent() || !mySubSet2->Extent())
+    return;
+
+  // Construct BVH tree for each sub-set
+  BOPTools_BoxTree aBBTree[2];
+  for (Standard_Integer i = 0; i < 2; ++i)
+  {
+    const TColStd_ListOfInteger* aSubSet = !i ? mySubSet1 : mySubSet2;
+    aBBTree[i].SetSize (aSubSet->Extent());
+    for (TColStd_ListOfInteger::Iterator it (*aSubSet); it.More(); it.Next())
+    {
+      const Standard_Integer nS = it.Value();
+      const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(nS);
+      const Bnd_Box& aBoxEx = aSI.Box();
+      aBBTree[i].Add(nS, Bnd_Tools::Bnd2BVH (aBoxEx));
+    }
+    aBBTree[i].Build();
   }
-  //
-  aTreeFiller.Fill();
-  //
+
+  // Perform selection of the interfering pairs
+  BOPTools_BoxPairSelector aPairSelector;
+  aPairSelector.SetBVHSets (&aBBTree[0], &aBBTree[1]);
+  aPairSelector.Select();
+  aPairSelector.Sort();
+
+  // Treat the selected pairs
+  const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
+
+  // Fence map
   BOPDS_MapOfPair aMPKFence;
-  //
-  aIt.Initialize(*mySubSet2);
-  for (; aIt.More(); aIt.Next()) {
-    i = aIt.Value();
-    //
-    const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
-    const Bnd_Box& aBoxEx = aSI.Box();
-    //
-    BOPTools_BoxBndTreeSelector aSelector;
-    aSelector.SetBox(aBoxEx);
-    Standard_Integer aNbSD = aBBTree.Select(aSelector);
-    if (!aNbSD) {
+
+  for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
+  {
+    const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
+    if (aPair.ID1 == aPair.ID2)
       continue;
-    }
-    //
-    iTi = BOPDS_Tools::TypeToInteger(aSI.ShapeType());
-    //
-    const TColStd_ListOfInteger& aLI = aSelector.Indices();
-    TColStd_ListIteratorOfListOfInteger aItLI(aLI);
-    for (; aItLI.More(); aItLI.Next()) {
-      j = aItLI.Value();
-      //
-      const BOPDS_ShapeInfo& aSJ = myDS->ShapeInfo(j);
-      iTj = BOPDS_Tools::TypeToInteger(aSJ.ShapeType());
-      //
-      // avoid interfering of the same shapes and shape with its sub-shapes
-      if ((i == j) || ((iTi < iTj) && aSI.HasSubShape(j)) ||
-                      ((iTi > iTj) && aSJ.HasSubShape(i))) {
-        continue;
-      }
-      //
-      BOPDS_Pair aPair(j, i);
-      if (aMPKFence.Add(aPair)) {
-        myList.Append(aPair);
-      }
-    }
+
+    BOPDS_Pair aDSPair (Min(aPair.ID1, aPair.ID2),
+                        Max(aPair.ID1, aPair.ID2));
+    if (!aMPKFence.Add(aDSPair))
+      continue;
+
+    const BOPDS_ShapeInfo& aSI1 = myDS->ShapeInfo (aPair.ID1);
+    const BOPDS_ShapeInfo& aSI2 = myDS->ShapeInfo (aPair.ID2);
+
+    const TopAbs_ShapeEnum aType1 = aSI1.ShapeType();
+    const TopAbs_ShapeEnum aType2 = aSI2.ShapeType();
+
+    Standard_Integer iType1 = BOPDS_Tools::TypeToInteger (aType1);
+    Standard_Integer iType2 = BOPDS_Tools::TypeToInteger (aType2);
+
+    // avoid interfering of the shape with its sub-shapes
+    if (((iType1 < iType2) && aSI1.HasSubShape (aPair.ID2)) ||
+        ((iType1 > iType2) && aSI2.HasSubShape (aPair.ID1)))
+      continue;
+
+    myList.Append(aDSPair);
   }
 }
diff --git a/src/BOPTools/BOPTools_BoxBndTree.hxx b/src/BOPTools/BOPTools_BoxBndTree.hxx
deleted file mode 100644 (file)
index 6ed2ea0..0000000
+++ /dev/null
@@ -1,26 +0,0 @@
-// Created by: Eugeny MALTCHIKOV
-// Copyright (c) 2017 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.
-
-#ifndef BOPTools_BoxBndTree_HeaderFile
-#define BOPTools_BoxBndTree_HeaderFile
-
-#include <Bnd_Box.hxx>
-#include <BOPTools_BoxSelector.hxx>
-#include <NCollection_EBTree.hxx>
-#include <Standard_Integer.hxx>
-
-typedef NCollection_EBTree<Standard_Integer, Bnd_Box> BOPTools_BoxBndTree;
-typedef BOPTools_BoxSelector<Bnd_Box> BOPTools_BoxBndTreeSelector;
-
-#endif
index e8bf268..c29012e 100644 (file)
 #ifndef BOPTools_BoxSelector_HeaderFile
 #define BOPTools_BoxSelector_HeaderFile
 
-#include <TColStd_ListOfInteger.hxx>
-#include <NCollection_UBTree.hxx>
+#include <BVH_Traverse.hxx>
+#include <BVH_BoxSet.hxx>
+
 #include <Standard_Integer.hxx>
+#include <TColStd_ListOfInteger.hxx>
 
-//! Template Selector for the unbalanced binary tree
-//! of overlapped bounding boxes.
-template <class BoxType> class BOPTools_BoxSelector :
-  public NCollection_UBTree<Standard_Integer, BoxType>::Selector
+//! Template Selector for elements selection from BVH tree.
+template <int Dimension>
+class BOPTools_BoxSelector :
+  public BVH_Traverse <Standard_Real, Dimension, BVH_BoxSet <Standard_Real, Dimension, Standard_Integer>, Standard_Boolean>
 {
 public:
 
+  typedef typename BVH::VectorType<Standard_Real, Dimension>::Type BVH_VecNd;
+
+public: //! @name Constructor
+
   //! Empty constructor
   BOPTools_BoxSelector() {};
 
-  //! Checks if the box should be rejected
-  virtual Standard_Boolean Reject(const BoxType& theOther) const
-  {
-    return myBox.IsOut(theOther);
-  }
-
-  //! Accepts the index
-  virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
-  {
-    myIndices.Append(theIndex);
-    return Standard_True;
-  }
+public: //! @name public interfaces
 
   //! Clears the indices
   void Clear()
@@ -49,7 +44,7 @@ public:
   }
 
   //! Sets the box
-  void SetBox(const BoxType& theBox)
+  void SetBox (const BVH_Box <Standard_Real, Dimension>& theBox)
   {
     myBox = theBox;
   }
@@ -60,11 +55,46 @@ public:
     return myIndices;
   }
 
-private:
+public: //! @name Rejection/Acceptance rules
+
+  //! Checks if the box should be rejected
+  virtual Standard_Boolean RejectNode (const BVH_VecNd& theCMin,
+                                       const BVH_VecNd& theCMax,
+                                       Standard_Boolean& theIsInside) const Standard_OVERRIDE
+  {
+    Standard_Boolean hasOverlap;
+    theIsInside = myBox.Contains (theCMin, theCMax, hasOverlap);
+    return !hasOverlap;
+  }
+
+  //! Checks if the element should be rejected
+  Standard_Boolean RejectElement (const Standard_Integer theIndex)
+  {
+    return myBox.IsOut (this->myBVHSet->Box (theIndex));
+  }
+
+  //! Checks if the metric of the node may be accepted
+  virtual Standard_Boolean AcceptMetric (const Standard_Boolean& theIsInside) const Standard_OVERRIDE
+  {
+    return theIsInside;
+  }
+
+  //! Accepts the element with the index <theIndex> in BVH tree
+  virtual Standard_Boolean Accept (const Standard_Integer theIndex,
+                                   const Standard_Boolean& theIsInside) Standard_OVERRIDE
+  {
+    if (theIsInside || !RejectElement (theIndex))
+    {
+      myIndices.Append (this->myBVHSet->Element (theIndex));
+      return Standard_True;
+    }
+    return Standard_False;
+  }
 
-  BoxType myBox;
-  TColStd_ListOfInteger myIndices;
+protected: //! @name Fields
 
+  BVH_Box <Standard_Real, Dimension> myBox; //!< Selection box
+  TColStd_ListOfInteger myIndices;          //!< Selected indices
 };
 
 #endif
diff --git a/src/BOPTools/BOPTools_BoxTree.hxx b/src/BOPTools/BOPTools_BoxTree.hxx
new file mode 100644 (file)
index 0000000..7477139
--- /dev/null
@@ -0,0 +1,47 @@
+// Created by: Eugeny MALTCHIKOV
+// Copyright (c) 2017 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.
+
+#ifndef BOPTools_BoxTree_HeaderFile
+#define BOPTools_BoxTree_HeaderFile
+
+#include <BVH_BoxSet.hxx>
+#include <BOPTools_BoxSelector.hxx>
+#include <BOPTools_PairSelector.hxx>
+#include <Standard_Integer.hxx>
+#include <Standard_Real.hxx>
+#include <BVH_LinearBuilder.hxx>
+
+//! Redefines BoxSet to use the Linear builder by default
+
+template <class NumType, int Dimension, class DataType>
+class BOPTools_BoxSet : public BVH_BoxSet <NumType, Dimension, DataType>
+{
+public: //! @name Constructors
+  //! Empty constructor for use the default BVH_Builder
+  BOPTools_BoxSet (const opencascade::handle <BVH_Builder <NumType, Dimension> >& theBuilder = NULL)
+    : BVH_BoxSet <NumType, Dimension, DataType> (theBuilder.IsNull() ? new BVH_LinearBuilder<NumType, Dimension>() : theBuilder)
+  {}
+};
+
+//! 2D definitions
+typedef BOPTools_BoxSet <Standard_Real, 2, Standard_Integer> BOPTools_Box2dTree;
+typedef BOPTools_BoxSelector<2> BOPTools_Box2dTreeSelector;
+typedef BOPTools_PairSelector<2> BOPTools_Box2dPairSelector;
+
+//! 3D definitions
+typedef BOPTools_BoxSet <Standard_Real, 3, Standard_Integer> BOPTools_BoxTree;
+typedef BOPTools_BoxSelector<3> BOPTools_BoxTreeSelector;
+typedef BOPTools_PairSelector<3> BOPTools_BoxPairSelector;
+
+#endif
diff --git a/src/BOPTools/BOPTools_PairSelector.hxx b/src/BOPTools/BOPTools_PairSelector.hxx
new file mode 100644 (file)
index 0000000..19a2274
--- /dev/null
@@ -0,0 +1,131 @@
+// Created by: Eugeny MALTCHIKOV
+// Copyright (c) 2017 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.
+
+#ifndef BOPTools_PairSelector_HeaderFile
+#define BOPTools_PairSelector_HeaderFile
+
+#include <BVH_Traverse.hxx>
+#include <BVH_BoxSet.hxx>
+
+#include <Standard_Integer.hxx>
+#include <TColStd_ListOfInteger.hxx>
+#include <algorithm>
+
+//! Template Selector for selection of the elements from two BVH trees.
+template <int Dimension>
+class BOPTools_PairSelector :
+  public BVH_PairTraverse <Standard_Real, Dimension, BVH_BoxSet <Standard_Real, Dimension, Standard_Integer>>
+{
+public: //! @name public types
+
+  //! Auxiliary structure to keep the pair of indices
+  struct PairIDs
+  {
+    PairIDs (const Standard_Integer theId1 = -1,
+             const Standard_Integer theId2 = -1)
+      : ID1 (theId1), ID2 (theId2)
+    {}
+
+    Standard_Boolean operator< (const PairIDs& theOther) const
+    {
+      return ID1 < theOther.ID1 ||
+            (ID1 == theOther.ID1 && ID2 < theOther.ID2);
+    }
+
+    Standard_Integer ID1;
+    Standard_Integer ID2;
+  };
+
+  typedef typename BVH::VectorType<Standard_Real, Dimension>::Type BVH_VecNd;
+
+public: //! @name Constructor
+
+  //! Empty constructor
+  BOPTools_PairSelector()
+    : mySameBVHs (Standard_False)
+  {}
+
+public: //! @name public interfaces
+
+  //! Clears the indices
+  void Clear()
+  {
+    myPairs.Clear();
+  }
+
+  //! Sorts the indices
+  void Sort()
+  {
+    std::sort (myPairs.begin(), myPairs.end());
+  }
+
+  //! Tells to selector that BVH trees are the same.
+  //! If the flag is set to true the resulting vector will contain
+  //! only unique pairs (mirrored pairs will be rejected,
+  //! e.g. (1, 2) will be taken, (2, 1) will be rejected) and will
+  //! not contain pairs in which IDs are the same (pair (1, 1) will be rejected).
+  //! If it is required to have a full vector of pairs even
+  //! for the same BVH trees, just keep the false value of this flag.
+  void SetSame (const Standard_Boolean theIsSame)
+  {
+    mySameBVHs = theIsSame;
+  }
+
+  //! Returns the list of accepted indices
+  const std::vector<PairIDs>& Pairs() const
+  {
+    return myPairs;
+  }
+
+public: //! @name Rejection/Acceptance rules
+
+  //! Basing on the bounding boxes of the nodes checks if the pair of nodes should be rejected.
+  virtual Standard_Boolean RejectNode (const BVH_VecNd& theCMin1,
+                                       const BVH_VecNd& theCMax1,
+                                       const BVH_VecNd& theCMin2,
+                                       const BVH_VecNd& theCMax2,
+                                       Standard_Real&) const Standard_OVERRIDE
+  {
+    return BVH_Box<Standard_Real, 3> (theCMin1, theCMax1).IsOut (theCMin2, theCMax2);
+  }
+
+  //! Checks if the pair of elements should be rejected.
+  Standard_Boolean RejectElement (const Standard_Integer theID1,
+                                  const Standard_Integer theID2)
+  {
+    return (mySameBVHs && theID1 >= theID2) ||
+            this->myBVHSet1->Box (theID1).IsOut(
+            this->myBVHSet2->Box (theID2));
+  }
+
+  //! Checks and accepts the pair of elements.
+  virtual Standard_Boolean Accept (const Standard_Integer theID1,
+                                   const Standard_Integer theID2) Standard_OVERRIDE
+  {
+    if (!RejectElement (theID1, theID2))
+    {
+      myPairs.push_back (PairIDs (this->myBVHSet1->Element (theID1),
+                                  this->myBVHSet2->Element (theID2)));
+      return Standard_True;
+    }
+    return Standard_False;
+  }
+
+protected: //! @name Fields
+
+  std::vector<PairIDs> myPairs; //!< Selected pairs of indices
+  Standard_Boolean mySameBVHs;  //!< Selection is performed from the same BVH trees
+};
+
+#endif
index 26526d0..26ade9a 100755 (executable)
@@ -8,13 +8,14 @@ BOPTools_AlgoTools3D.hxx
 BOPTools_AlgoTools_1.cxx
 BOPTools_AlgoTools_2.cxx
 BOPTools_BoxSelector.hxx
-BOPTools_BoxBndTree.hxx
+BOPTools_BoxTree.hxx
 BOPTools_ConnexityBlock.hxx
 BOPTools_CoupleOfShape.hxx
 BOPTools_IndexedDataMapOfSetShape.hxx
 BOPTools_ListOfConnexityBlock.hxx
 BOPTools_ListOfCoupleOfShape.hxx
 BOPTools_MapOfSet.hxx
+BOPTools_PairSelector.hxx
 BOPTools_Parallel.hxx
 BOPTools_Set.cxx
 BOPTools_Set.hxx
index adbaa2d..0019a4f 100644 (file)
@@ -16,6 +16,7 @@
 
 //  Modified by skv - Fri Dec 26 12:20:14 2003 OCC4455
 
+#include <Bnd_Tools.hxx>
 #include <BRep_Builder.hxx>
 #include <BRep_Tool.hxx>
 #include <BRepAdaptor_Curve.hxx>
@@ -46,8 +47,7 @@
 #include <TopTools_MapOfShape.hxx>
 //
 #include <BRepBndLib.hxx>
-#include <BOPTools_BoxBndTree.hxx>
-#include <NCollection_UBTreeFiller.hxx>
+#include <BOPTools_BoxTree.hxx>
 //
 #include <BOPTools_AlgoTools.hxx>
 
@@ -114,8 +114,8 @@ void BRepOffset_Inter3d::CompletInt(const TopTools_ListOfShape& SetOfFaces,
   //---------------------------------------------------------------
 
   // Prepare tools for sorting the bounding boxes
-  BOPTools_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
+  BOPTools_BoxTree aBBTree;
+  aBBTree.SetSize (SetOfFaces.Extent());
   //
   NCollection_IndexedDataMap<TopoDS_Shape, Bnd_Box, TopTools_ShapeMapHasher> aMFaces;
   // Construct bounding boxes for faces and add them to the tree
@@ -127,37 +127,37 @@ void BRepOffset_Inter3d::CompletInt(const TopTools_ListOfShape& SetOfFaces,
     Bnd_Box aBoxF;
     BRepBndLib::Add(aF, aBoxF);
     //
-    Standard_Integer i = aMFaces.Add(aF, aBoxF);
+    Standard_Integer i = aMFaces.Add (aF, aBoxF);
     //
-    aTreeFiller.Add(i, aBoxF);
+    aBBTree.Add(i, Bnd_Tools::Bnd2BVH(aBoxF));
   }
-  //
-  // shake tree filler
-  aTreeFiller.Fill();
-  //
-  // get faces with interfering bounding boxes
-  aItL.Initialize(SetOfFaces);
-  for (; aItL.More(); aItL.Next()) {
-    const TopoDS_Face& aF1 = TopoDS::Face(aItL.Value());
-    const Bnd_Box& aBoxF1 = aMFaces.FindFromKey(aF1);
-    //
-    BOPTools_BoxBndTreeSelector aSelector;
-    aSelector.SetBox(aBoxF1);
-    aBBTree.Select(aSelector);
-    //
-    const TColStd_ListOfInteger& aLI = aSelector.Indices();
-    TColStd_ListIteratorOfListOfInteger aItLI(aLI);
-    for (; aItLI.More(); aItLI.Next()) {
-      Standard_Integer i = aItLI.Value();
-      const TopoDS_Face& aF2 = TopoDS::Face(aMFaces.FindKey(i));
-      //
-      // intersect faces
-      FaceInter(aF1, aF2, InitOffsetFace);
-    }
+
+  // Build BVH
+  aBBTree.Build();
+
+  // Perform selection of the pairs
+  BOPTools_BoxPairSelector aSelector;
+  aSelector.SetBVHSets (&aBBTree, &aBBTree);
+  aSelector.SetSame (Standard_True);
+  aSelector.Select();
+  aSelector.Sort();
+
+  // Treat the selected pairs
+  const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
+
+  for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair)
+  {
+    const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
+
+    const TopoDS_Face& aF1 = TopoDS::Face (aMFaces.FindKey (Min (aPair.ID1, aPair.ID2)));
+    const TopoDS_Face& aF2 = TopoDS::Face (aMFaces.FindKey (Max (aPair.ID1, aPair.ID2)));
+
+    // intersect faces
+    FaceInter(aF1, aF2, InitOffsetFace);
   }
 }
 
-
 //=======================================================================
 //function : FaceInter
 //purpose  : Performs intersection of the given faces
index a0f7958..bcc580f 100644 (file)
 #include <Bnd_BoundSortBox.hxx>
 #include <Bnd_Box.hxx>
 #include <Bnd_HArray1OfBox.hxx>
+#include <Bnd_Tools.hxx>
+#include <BVH_BoxSet.hxx>
+#include <BVH_LinearBuilder.hxx>
+#include <BVH_Traverse.hxx>
 #include <gp.hxx>
 #include <gp_Pnt.hxx>
 #include <IntPolyh_ListOfCouples.hxx>
 #include <TColStd_Array1OfInteger.hxx>
 #include <TColStd_MapOfInteger.hxx>
 #include <TColStd_ListIteratorOfListOfInteger.hxx>
-#include <NCollection_UBTree.hxx>
-#include <NCollection_UBTreeFiller.hxx>
 #include <algorithm>
 #include <NCollection_IndexedDataMap.hxx>
 
 typedef NCollection_Array1<Standard_Integer> IntPolyh_ArrayOfInteger;
 typedef NCollection_IndexedDataMap
   <Standard_Integer,
-   IntPolyh_ArrayOfInteger,
-   TColStd_MapIntegerHasher> IntPolyh_IndexedDataMapOfIntegerArrayOfInteger;
+   TColStd_ListOfInteger,
+   TColStd_MapIntegerHasher> IntPolyh_IndexedDataMapOfIntegerListOfInteger;
 
 
 static Standard_Real MyTolerance=10.0e-7;
@@ -133,32 +135,82 @@ static
                         Standard_Integer& aI2);
 
 //=======================================================================
+//class : IntPolyh_BoxBndTree
+//purpose  : BVH structure to contain the boxes of triangles
+//=======================================================================
+typedef BVH_BoxSet <Standard_Real, 3, Standard_Integer> IntPolyh_BoxBndTree;
+
+//=======================================================================
 //class : IntPolyh_BoxBndTreeSelector
-//purpose  : Select interfering bounding boxes
+//purpose  : Selector of interfering boxes
 //=======================================================================
-typedef NCollection_UBTree<Standard_Integer, Bnd_Box> IntPolyh_BoxBndTree;
-class IntPolyh_BoxBndTreeSelector : public IntPolyh_BoxBndTree::Selector {
- public:
-  IntPolyh_BoxBndTreeSelector(const Bnd_Box& theBox) : myBox(theBox) {}
-  //
-  virtual Standard_Boolean Reject(const Bnd_Box& theOther) const
+class IntPolyh_BoxBndTreeSelector :
+  public BVH_PairTraverse<Standard_Real, 3, IntPolyh_BoxBndTree>
+{
+public:
+  typedef BVH_Box<Standard_Real, 3>::BVH_VecNt BVH_Vec3d;
+
+  //! Auxiliary structure to keep the pair of indices
+  struct PairIDs
   {
-    return myBox.IsOut(theOther);
+    PairIDs (const Standard_Integer theId1 = -1,
+             const Standard_Integer theId2 = -1)
+      : ID1 (theId1), ID2 (theId2)
+    {}
+
+    Standard_Boolean operator< (const PairIDs& theOther) const
+    {
+      return ID1 < theOther.ID1 ||
+            (ID1 == theOther.ID1 && ID2 < theOther.ID2);
+    }
+
+    Standard_Integer ID1;
+    Standard_Integer ID2;
+  };
+
+public:
+
+  //! Constructor
+  IntPolyh_BoxBndTreeSelector ()
+  {}
+
+  //! Rejects the node
+  virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCMin1,
+                                       const BVH_Vec3d& theCMax1,
+                                       const BVH_Vec3d& theCMin2,
+                                       const BVH_Vec3d& theCMax2,
+                                       Standard_Real&) const Standard_OVERRIDE
+  {
+    return BVH_Box<Standard_Real, 3> (theCMin1, theCMax1).IsOut (theCMin2, theCMax2);
   }
-  //
-  virtual Standard_Boolean Accept(const Standard_Integer &theInd)
+
+  //! Accepts the element
+  virtual Standard_Boolean Accept (const Standard_Integer theID1,
+                                   const Standard_Integer theID2) Standard_OVERRIDE
   {
-    myIndices.Append(theInd);
-    return Standard_True;
+    if (!myBVHSet1->Box (theID1).IsOut (myBVHSet2->Box (theID2)))
+    {
+      myPairs.push_back (PairIDs (myBVHSet1->Element (theID1), myBVHSet2->Element (theID2)));
+      return Standard_True;
+    }
+    return Standard_False;
   }
-  //
-  const TColStd_ListOfInteger& Indices() const
+
+  //! Returns indices
+  const std::vector<PairIDs>& Pairs() const
+  {
+    return myPairs;
+  }
+
+  //! Sorts the resulting indices
+  void Sort()
   {
-    return myIndices;
+    std::sort (myPairs.begin(), myPairs.end());
   }
- private:
-  Bnd_Box myBox;
-  TColStd_ListOfInteger myIndices;
+
+private:
+
+  std::vector<PairIDs> myPairs;
 };
 
 //=======================================================================
@@ -170,59 +222,57 @@ static
                                const IntPolyh_ArrayOfPoints& thePoints1,
                                IntPolyh_ArrayOfTriangles& theTriangles2,
                                const IntPolyh_ArrayOfPoints& thePoints2,
-                               IntPolyh_IndexedDataMapOfIntegerArrayOfInteger& theCouples)
+                               IntPolyh_IndexedDataMapOfIntegerListOfInteger& theCouples)
 {
+  // Use linear builder for BVH construction
+  opencascade::handle<BVH_LinearBuilder<Standard_Real, 3>> aLBuilder =
+    new BVH_LinearBuilder<Standard_Real, 3> (10);
+
   // To find the triangles with interfering bounding boxes
-  // use the algorithm of unbalanced binary tree of overlapping bounding boxes
-  IntPolyh_BoxBndTree aBBTree;
-  NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
-  // 1. Fill the tree with the boxes of the triangles from second surface
-  Standard_Integer i, aNbT2 = theTriangles2.NbItems();
-  Standard_Boolean bAdded = Standard_False;
-  for (i = 0; i < aNbT2; ++i) {
-    IntPolyh_Triangle& aT = theTriangles2[i];
-    if (!aT.IsIntersectionPossible() || aT.IsDegenerated()) {
-      continue;
+  // use the BVH structure
+  IntPolyh_BoxBndTree aBBTree1 (aLBuilder), aBBTree2 (aLBuilder);
+
+  // 1. Fill the trees with the boxes of the surfaces triangles
+  for (Standard_Integer i = 0; i < 2; ++i)
+  {
+    IntPolyh_BoxBndTree &aBBTree =          !i ? aBBTree1      : aBBTree2;
+    IntPolyh_ArrayOfTriangles& aTriangles = !i ? theTriangles1 : theTriangles2;
+    const IntPolyh_ArrayOfPoints& aPoints = !i ? thePoints1    : thePoints2;
+
+    const Standard_Integer aNbT = aTriangles.NbItems();
+    aBBTree.SetSize (aNbT);
+    for (Standard_Integer j = 0; j < aNbT; ++j)
+    {
+      IntPolyh_Triangle& aT = aTriangles[j];
+      if (!aT.IsIntersectionPossible() || aT.IsDegenerated())
+        continue;
+
+      aBBTree.Add (j, Bnd_Tools::Bnd2BVH (aT.BoundingBox(aPoints)));
     }
-    //
-    const Bnd_Box& aBox = aT.BoundingBox(thePoints2);
-    aTreeFiller.Add(i, aBox);
-    bAdded = Standard_True;
+
+    if (!aBBTree.Size())
+      return;
   }
-  //
-  if (!bAdded)
-    // Intersection is not possible for all triangles in theTriangles2
-    return;
+  // 2. Construct BVH trees
+  aBBTree1.Build();
+  aBBTree2.Build();
 
-  // 2. Shake the tree filler
-  aTreeFiller.Fill();
-  //
-  // 3. Find boxes interfering with the first triangles
-  Standard_Integer aNbT1 = theTriangles1.NbItems();
-  for (i = 0; i < aNbT1; ++i) {
-    IntPolyh_Triangle& aT = theTriangles1[i];
-    if (!aT.IsIntersectionPossible() || aT.IsDegenerated()) {
-      continue;
-    }
-    //
-    const Bnd_Box& aBox = aT.BoundingBox(thePoints1);
-    //
-    IntPolyh_BoxBndTreeSelector aSelector(aBox);
-    if (!aBBTree.Select(aSelector)) {
-      continue;
-    }
-    //
-    const TColStd_ListOfInteger& aLI = aSelector.Indices();
-    // Sort the indices
-    IntPolyh_ArrayOfInteger anArr(1, aLI.Extent());
-    TColStd_ListIteratorOfListOfInteger aItLI(aLI);
-    for (Standard_Integer j = 1; aItLI.More(); aItLI.Next(), ++j) {
-      anArr(j) = aItLI.Value();
-    }
-    //
-    std::sort(anArr.begin(), anArr.end());
-    //
-    theCouples.Add(i, anArr);
+  // 3. Perform selection of the interfering triangles
+  IntPolyh_BoxBndTreeSelector aSelector;
+  aSelector.SetBVHSets (&aBBTree1, &aBBTree2);
+  aSelector.Select();
+  aSelector.Sort();
+
+  const std::vector<IntPolyh_BoxBndTreeSelector::PairIDs>& aPairs = aSelector.Pairs();
+  const Standard_Integer aNbPairs = static_cast<Standard_Integer>(aPairs.size());
+
+  for (Standard_Integer i = 0; i < aNbPairs; ++i)
+  {
+    const IntPolyh_BoxBndTreeSelector::PairIDs& aPair = aPairs[i];
+    TColStd_ListOfInteger* pTriangles2 = theCouples.ChangeSeek (aPair.ID1);
+    if (!pTriangles2)
+      pTriangles2 = &theCouples( theCouples.Add (aPair.ID1, TColStd_ListOfInteger()));
+    pTriangles2->Append (aPair.ID2);
   }
 }
 
@@ -921,7 +971,7 @@ static
                                       const Standard_Real theFlecheCritique2)
 {
   // Find the intersecting triangles
-  IntPolyh_IndexedDataMapOfIntegerArrayOfInteger aDMILI;
+  IntPolyh_IndexedDataMapOfIntegerListOfInteger aDMILI;
   GetInterferingTriangles(theTriangles1, thePoints1, theTriangles2, thePoints2, aDMILI);
   //
   // Interfering triangles of second surface
@@ -938,8 +988,8 @@ static
       continue;
     }
     //
-    const IntPolyh_ArrayOfInteger *pLI = aDMILI.Seek(i_S1);
-    if (!pLI || !pLI->Length()) {
+    const TColStd_ListOfInteger *pLI = aDMILI.Seek(i_S1);
+    if (!pLI || pLI->IsEmpty()) {
       // Mark non-interfering triangles of S1 to avoid their repeated usage
       aTriangle1.SetIntersectionPossible(Standard_False);
       continue;
@@ -949,7 +999,7 @@ static
       aTriangle1.MiddleRefinement(i_S1, theS1, thePoints1, theTriangles1, theEdges1);
     }
     //
-    IntPolyh_ArrayOfInteger::Iterator Iter(*pLI);
+    TColStd_ListOfInteger::Iterator Iter(*pLI);
     for (; Iter.More(); Iter.Next()) {
       Standard_Integer i_S2 = Iter.Value();
       if (aMIntS2.Add(i_S2)) {
@@ -2295,7 +2345,7 @@ Standard_Integer IntPolyh_MaillageAffinage::TriangleEdgeContact
 Standard_Integer IntPolyh_MaillageAffinage::TriangleCompare ()
 {
   // Find couples with interfering bounding boxes
-  IntPolyh_IndexedDataMapOfIntegerArrayOfInteger aDMILI;
+  IntPolyh_IndexedDataMapOfIntegerListOfInteger aDMILI;
   GetInterferingTriangles(TTriangles1, TPoints1,
                           TTriangles2, TPoints2,
                           aDMILI);
@@ -2314,8 +2364,8 @@ Standard_Integer IntPolyh_MaillageAffinage::TriangleCompare ()
     const IntPolyh_Point& P2 = TPoints1[Triangle1.SecondPoint()];
     const IntPolyh_Point& P3 = TPoints1[Triangle1.ThirdPoint()];
     //
-    const IntPolyh_ArrayOfInteger& aLI2 = aDMILI(i);
-    IntPolyh_ArrayOfInteger::Iterator aItLI(aLI2);
+    const TColStd_ListOfInteger& aLI2 = aDMILI(i);
+    TColStd_ListOfInteger::Iterator aItLI(aLI2);
     for (; aItLI.More(); aItLI.Next()) {
       const Standard_Integer i_S2 = aItLI.Value();
       IntPolyh_Triangle &Triangle2 =  TTriangles2[i_S2];