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.
*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.
+
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
#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>
#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>
// 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())
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);
// 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;
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;
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
#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>
#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>
// 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;
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);
//
MakeSplitEdges();
if (HasErrors()) {
- return;
+ return;
}
//
UpdatePaveBlocksWithSDVertices();
return;
// Update iterator of pairs of shapes with interfering boxes
- myIterator->PrepareExt(anExtraInterfMap);
+ myIterator->IntersectExt(anExtraInterfMap);
// Perform intersections with vertices
PerformVV();
//
// 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);
#include <Bnd_Box.hxx>
+#include <Bnd_Tools.hxx>
#include <BOPAlgo_PaveFiller.hxx>
#include <BOPAlgo_Alerts.hxx>
#include <BOPAlgo_Tools.hxx>
#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>
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);
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.
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());
#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>
#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>
#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>
/////////////////////////////////////////////////////////////////////////
//=======================================================================
-//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;
};
//
/////////////////////////////////////////////////////////////////////////
//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));
}
}
}
};
//! 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
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
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();
}
}
- // 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;
if (pLIF)
aFIP.SetOwnIF(*pLIF);
- aFIP.SetBBTree(aBBTree);
+ aFIP.SetBBTree(&aBBTree);
aFIP.SetShapeBoxVector(aVSB);
}
//! 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);
#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() {
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;
};
//
typedef NCollection_Vector<BOPDS_TSR> BOPDS_VectorOfTSR;
/////////////////////////////////////////////////////////////////////////
-
//=======================================================================
//function :
//purpose :
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)));
+ }
+ }
}
//=======================================================================
//=======================================================================
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);
// 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();
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;
}
}
}
+
+ myUseExt = Standard_True;
}
#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>
//! 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;
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
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
#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>
// 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)));
+ }
}
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
#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>
// 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);
}
}
+++ /dev/null
-// 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
#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()
}
//! Sets the box
- void SetBox(const BoxType& theBox)
+ void SetBox (const BVH_Box <Standard_Real, Dimension>& theBox)
{
myBox = theBox;
}
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
--- /dev/null
+// 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
--- /dev/null
+// 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
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
// 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>
#include <TopTools_MapOfShape.hxx>
//
#include <BRepBndLib.hxx>
-#include <BOPTools_BoxBndTree.hxx>
-#include <NCollection_UBTreeFiller.hxx>
+#include <BOPTools_BoxTree.hxx>
//
#include <BOPTools_AlgoTools.hxx>
//---------------------------------------------------------------
// 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
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
#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;
Standard_Integer& aI1,
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;
};
//=======================================================================
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);
}
}
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
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;
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)) {
Standard_Integer IntPolyh_MaillageAffinage::TriangleCompare ()
{
// Find couples with interfering bounding boxes
- IntPolyh_IndexedDataMapOfIntegerArrayOfInteger aDMILI;
+ IntPolyh_IndexedDataMapOfIntegerListOfInteger aDMILI;
GetInterferingTriangles(TTriangles1, TPoints1,
TTriangles2, TPoints2,
aDMILI);
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];
projects / occt.git / commitdiff