From 7c1a82100041c3b397b8e44925cee83d985e7804 Mon Sep 17 00:00:00 2001 From: emv Date: Wed, 17 Apr 2019 17:29:02 +0300 Subject: [PATCH] 0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree Provide the easy to use interfaces for selection of the elements from BVH tree. The selection rules should be implemented in the selector class derived from *BVH_Traverse* or in *BVH_PairTraverse* in Reject/Accept methods. The *BVH_Traverse* is used for selection of the elements from the tree. The *BVH_PairTraverse* is used for selection of the pairs of elements from two BVH trees. Auxiliary changes: - Two methods BVH_Box::IsOut(OtherBox) and BVH_Box::IsOut(Point) have been added; - Added methods for conversion of Bnd boxes to BVH boxes Added new class *BVH_Tools* containing useful static methods operating on BVH points and boxes. The classes BRepExtrema_OverlapTool and BVH_DistanceField have been rebased to use the new traverse methods. --- src/BRepExtrema/BRepExtrema_OverlapTool.cxx | 421 +++------ src/BRepExtrema/BRepExtrema_OverlapTool.hxx | 30 +- .../BRepExtrema_ShapeProximity.hxx | 1 - src/BVH/BVH_Box.hxx | 81 ++ src/BVH/BVH_BoxSet.hxx | 132 +++ src/BVH/BVH_Distance.hxx | 97 ++ src/BVH/BVH_DistanceField.lxx | 320 +++---- src/BVH/BVH_IndexedBoxSet.hxx | 109 +++ src/BVH/BVH_PairDistance.hxx | 102 +++ src/BVH/BVH_Tools.hxx | 165 ++++ src/BVH/BVH_Traverse.hxx | 343 +++++++ src/BVH/BVH_Traverse.lxx | 299 ++++++ src/BVH/FILES | 7 + src/Bnd/Bnd_Tools.hxx | 47 + src/Bnd/FILES | 1 + src/QABugs/FILES | 1 + src/QABugs/QABugs.cxx | 1 + src/QABugs/QABugs.hxx | 1 + src/QABugs/QABugs_BVH.cxx | 854 ++++++++++++++++++ tests/lowalgos/bvh/bug30655_1 | 58 ++ tests/lowalgos/bvh/bug30655_2 | 16 + tests/lowalgos/bvh/bug30655_3 | 21 + tests/lowalgos/bvh/bug30655_4 | 13 + tests/lowalgos/grids.list | 3 +- 24 files changed, 2663 insertions(+), 460 deletions(-) create mode 100644 src/BVH/BVH_BoxSet.hxx create mode 100644 src/BVH/BVH_Distance.hxx create mode 100644 src/BVH/BVH_IndexedBoxSet.hxx create mode 100644 src/BVH/BVH_PairDistance.hxx create mode 100644 src/BVH/BVH_Tools.hxx create mode 100644 src/BVH/BVH_Traverse.hxx create mode 100644 src/BVH/BVH_Traverse.lxx create mode 100644 src/Bnd/Bnd_Tools.hxx create mode 100644 src/QABugs/QABugs_BVH.cxx create mode 100644 tests/lowalgos/bvh/bug30655_1 create mode 100644 tests/lowalgos/bvh/bug30655_2 create mode 100644 tests/lowalgos/bvh/bug30655_3 create mode 100644 tests/lowalgos/bvh/bug30655_4 diff --git a/src/BRepExtrema/BRepExtrema_OverlapTool.cxx b/src/BRepExtrema/BRepExtrema_OverlapTool.cxx index f2600de4c8..8dd8252c2f 100644 --- a/src/BRepExtrema/BRepExtrema_OverlapTool.cxx +++ b/src/BRepExtrema/BRepExtrema_OverlapTool.cxx @@ -22,7 +22,8 @@ //purpose : //======================================================================= BRepExtrema_OverlapTool::BRepExtrema_OverlapTool() -: myFilter (NULL) +: myFilter (NULL), + myTolerance (0.0) { myIsDone = Standard_False; } @@ -33,7 +34,8 @@ BRepExtrema_OverlapTool::BRepExtrema_OverlapTool() //======================================================================= BRepExtrema_OverlapTool::BRepExtrema_OverlapTool (const Handle(BRepExtrema_TriangleSet)& theSet1, const Handle(BRepExtrema_TriangleSet)& theSet2) -: myFilter (NULL) +: myFilter (NULL), + myTolerance (0.0) { LoadTriangleSets (theSet1, theSet2); } @@ -57,21 +59,6 @@ void BRepExtrema_OverlapTool::LoadTriangleSets (const Handle(BRepExtrema_Triangl namespace { - //! Tool class to describe stack item in traverse function. - struct BRepExtrema_StackItem - { - Standard_Integer Node1; - Standard_Integer Node2; - - BRepExtrema_StackItem (const Standard_Integer theNode1 = 0, - const Standard_Integer theNode2 = 0) - : Node1 (theNode1), - Node2 (theNode2) - { - // - } - }; - //! Bounding triangular prism for specified triangle. class BRepExtrema_BoundingPrism { @@ -517,175 +504,163 @@ namespace } //======================================================================= -//function : intersectTriangleRangesExact +//function : intersectTrianglesExact //purpose : //======================================================================= -void BRepExtrema_OverlapTool::intersectTriangleRangesExact (const BVH_Vec4i& theLeaf1, - const BVH_Vec4i& theLeaf2) +void BRepExtrema_OverlapTool::intersectTrianglesExact (const Standard_Integer theTrgIdx1, + const Standard_Integer theTrgIdx2) { - for (Standard_Integer aTrgIdx1 = theLeaf1.y(); aTrgIdx1 <= theLeaf1.z(); ++aTrgIdx1) - { - const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (aTrgIdx1); + const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1); - BVH_Vec3d aTrg1Vert1; - BVH_Vec3d aTrg1Vert2; - BVH_Vec3d aTrg1Vert3; + BVH_Vec3d aTrg1Vert1; + BVH_Vec3d aTrg1Vert2; + BVH_Vec3d aTrg1Vert3; - mySet1->GetVertices (aTrgIdx1, - aTrg1Vert1, - aTrg1Vert2, - aTrg1Vert3); + mySet1->GetVertices (theTrgIdx1, + aTrg1Vert1, + aTrg1Vert2, + aTrg1Vert3); - const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); + const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); - for (Standard_Integer aTrgIdx2 = theLeaf2.y(); aTrgIdx2 <= theLeaf2.z(); ++aTrgIdx2) - { - const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (aTrgIdx2); + const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2); - if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) - { - continue; - } + if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) + { + return; + } - BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? - BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (aTrgIdx1, aTrgIdx2); + BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? + BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2); - if (aResult == BRepExtrema_ElementFilter::Overlap) - { - getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); - getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); + if (aResult == BRepExtrema_ElementFilter::Overlap) + { + getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); + getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES - if (mySet1 == mySet2) - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles1.Add (aTrgIdx2); - } - else - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles2.Add (aTrgIdx2); - } + if (mySet1 == mySet2) + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles1.Add (theTrgIdx2); + } + else + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles2.Add (theTrgIdx2); + } #endif - } - else if (aResult == BRepExtrema_ElementFilter::DoCheck) - { - BVH_Vec3d aTrg2Vert1; - BVH_Vec3d aTrg2Vert2; - BVH_Vec3d aTrg2Vert3; - - mySet2->GetVertices (aTrgIdx2, aTrg2Vert1, aTrg2Vert2, aTrg2Vert3); - - if (trianglesIntersected (aTrg1Vert1, - aTrg1Vert2, - aTrg1Vert3, - aTrg2Vert1, - aTrg2Vert2, - aTrg2Vert3)) - { - getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); - getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); + } + else if (aResult == BRepExtrema_ElementFilter::DoCheck) + { + BVH_Vec3d aTrg2Vert1; + BVH_Vec3d aTrg2Vert2; + BVH_Vec3d aTrg2Vert3; + + mySet2->GetVertices (theTrgIdx2, aTrg2Vert1, aTrg2Vert2, aTrg2Vert3); + + if (trianglesIntersected (aTrg1Vert1, + aTrg1Vert2, + aTrg1Vert3, + aTrg2Vert1, + aTrg2Vert2, + aTrg2Vert3)) + { + getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); + getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES - if (mySet1 == mySet2) - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles1.Add (aTrgIdx2); - } - else - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles2.Add (aTrgIdx2); - } -#endif - } + if (mySet1 == mySet2) + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles1.Add (theTrgIdx2); + } + else + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles2.Add (theTrgIdx2); } +#endif } } } //======================================================================= -//function : intersectTriangleRangesToler +//function : intersectTrianglesToler //purpose : //======================================================================= -void BRepExtrema_OverlapTool::intersectTriangleRangesToler (const BVH_Vec4i& theLeaf1, - const BVH_Vec4i& theLeaf2, - const Standard_Real theToler) +void BRepExtrema_OverlapTool::intersectTrianglesToler (const Standard_Integer theTrgIdx1, + const Standard_Integer theTrgIdx2, + const Standard_Real theToler) { - for (Standard_Integer aTrgIdx1 = theLeaf1.y(); aTrgIdx1 <= theLeaf1.z(); ++aTrgIdx1) - { - const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (aTrgIdx1); + const Standard_Integer aFaceIdx1 = mySet1->GetFaceID (theTrgIdx1); - BVH_Vec3d aTrg1Vert1; - BVH_Vec3d aTrg1Vert2; - BVH_Vec3d aTrg1Vert3; + BVH_Vec3d aTrg1Vert1; + BVH_Vec3d aTrg1Vert2; + BVH_Vec3d aTrg1Vert3; - mySet1->GetVertices (aTrgIdx1, - aTrg1Vert1, - aTrg1Vert2, - aTrg1Vert3); + mySet1->GetVertices (theTrgIdx1, + aTrg1Vert1, + aTrg1Vert2, + aTrg1Vert3); - BRepExtrema_BoundingPrism aPrism1; // not initialized + BRepExtrema_BoundingPrism aPrism1; // not initialized - const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); + const Standard_Boolean aIsInSet = myOverlapSubShapes1.IsBound (aFaceIdx1); - for (Standard_Integer aTrgIdx2 = theLeaf2.y(); aTrgIdx2 <= theLeaf2.z(); ++aTrgIdx2) - { - const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (aTrgIdx2); + const Standard_Integer aFaceIdx2 = mySet2->GetFaceID (theTrgIdx2); - if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) - { - continue; - } + if (aIsInSet && myOverlapSubShapes1.Find (aFaceIdx1).Contains (aFaceIdx2)) + { + return; + } - BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? - BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (aTrgIdx1, aTrgIdx2); + BRepExtrema_ElementFilter::FilterResult aResult = myFilter == NULL ? + BRepExtrema_ElementFilter::DoCheck : myFilter->PreCheckElements (theTrgIdx1, theTrgIdx2); - if (aResult == BRepExtrema_ElementFilter::Overlap) - { - getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); - getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); + if (aResult == BRepExtrema_ElementFilter::Overlap) + { + getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); + getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); #ifdef OVERLAP_TOOL_OUTPUT_TRIANGLES - if (mySet1 == mySet2) - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles1.Add (aTrgIdx2); - } - else - { - myOverlapTriangles1.Add (aTrgIdx1); - myOverlapTriangles2.Add (aTrgIdx2); - } + if (mySet1 == mySet2) + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles1.Add (theTrgIdx2); + } + else + { + myOverlapTriangles1.Add (theTrgIdx1); + myOverlapTriangles2.Add (theTrgIdx2); + } #endif - } - else if (aResult == BRepExtrema_ElementFilter::DoCheck) - { - if (!aPrism1.IsInited) - { - aPrism1.Init (aTrg1Vert1, aTrg1Vert2, aTrg1Vert3, theToler); - } + } + else if (aResult == BRepExtrema_ElementFilter::DoCheck) + { + if (!aPrism1.IsInited) + { + aPrism1.Init (aTrg1Vert1, aTrg1Vert2, aTrg1Vert3, theToler); + } - BVH_Vec3d aTrg2Vert1; - BVH_Vec3d aTrg2Vert2; - BVH_Vec3d aTrg2Vert3; + BVH_Vec3d aTrg2Vert1; + BVH_Vec3d aTrg2Vert2; + BVH_Vec3d aTrg2Vert3; - mySet2->GetVertices (aTrgIdx2, - aTrg2Vert1, - aTrg2Vert2, - aTrg2Vert3); + mySet2->GetVertices (theTrgIdx2, + aTrg2Vert1, + aTrg2Vert2, + aTrg2Vert3); - BRepExtrema_BoundingPrism aPrism2 (aTrg2Vert1, - aTrg2Vert2, - aTrg2Vert3, - theToler); + BRepExtrema_BoundingPrism aPrism2 (aTrg2Vert1, + aTrg2Vert2, + aTrg2Vert3, + theToler); - if (prismsIntersected (aPrism1, aPrism2)) - { - getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); - getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); - } - } + if (prismsIntersected (aPrism1, aPrism2)) + { + getSetOfFaces (myOverlapSubShapes1, aFaceIdx1).Add (aFaceIdx2); + getSetOfFaces (myOverlapSubShapes2, aFaceIdx2).Add (aFaceIdx1); } } } @@ -696,136 +671,38 @@ void BRepExtrema_OverlapTool::intersectTriangleRangesToler (const BVH_Vec4i& //======================================================================= void BRepExtrema_OverlapTool::Perform (const Standard_Real theTolerance) { - if (mySet1.IsNull() || mySet2.IsNull()) - { - return; - } + myTolerance = theTolerance; - BRepExtrema_StackItem aStack[96]; + myIsDone = (this->Select(mySet1->BVH(), mySet2->BVH()) > 0); +} - const opencascade::handle >& aBVH1 = mySet1->BVH(); - const opencascade::handle >& aBVH2 = mySet2->BVH(); +//======================================================================= +//function : Branch rejection +//purpose : +//======================================================================= +Standard_Boolean BRepExtrema_OverlapTool::RejectNode (const BVH_Vec3d& theCornerMin1, + const BVH_Vec3d& theCornerMax1, + const BVH_Vec3d& theCornerMin2, + const BVH_Vec3d& theCornerMax2, + Standard_Real&) const +{ + return !overlapBoxes (theCornerMin1, theCornerMax1, theCornerMin2, theCornerMax2, myTolerance); +} - if (aBVH1.IsNull() || aBVH2.IsNull()) +//======================================================================= +//function : Leaf acceptance +//purpose : +//======================================================================= +Standard_Boolean BRepExtrema_OverlapTool::Accept (const Standard_Integer theTrgIdx1, + const Standard_Integer theTrgIdx2) +{ + if (myTolerance == 0.0) { - return; + intersectTrianglesExact (theTrgIdx1, theTrgIdx2); } - - BRepExtrema_StackItem aNodes; // current pair of nodes - - Standard_Integer aHead = -1; // stack head position - - for (;;) + else { - BVH_Vec4i aNodeData1 = aBVH1->NodeInfoBuffer()[aNodes.Node1]; - BVH_Vec4i aNodeData2 = aBVH2->NodeInfoBuffer()[aNodes.Node2]; - - if (aNodeData1.x() != 0 && aNodeData2.x() != 0) // leaves - { - if (theTolerance == 0.0) - { - intersectTriangleRangesExact (aNodeData1, aNodeData2); - } - else - { - intersectTriangleRangesToler (aNodeData1, aNodeData2, theTolerance); - } - - if (aHead < 0) - break; - - aNodes = aStack[aHead--]; - } - else - { - BRepExtrema_StackItem aPairsToProcess[4]; - - Standard_Integer aNbPairs = 0; - - if (aNodeData1.x() == 0) // inner node - { - const BVH_Vec3d& aMinPntLft1 = aBVH1->MinPoint (aNodeData1.y()); - const BVH_Vec3d& aMaxPntLft1 = aBVH1->MaxPoint (aNodeData1.y()); - const BVH_Vec3d& aMinPntRgh1 = aBVH1->MinPoint (aNodeData1.z()); - const BVH_Vec3d& aMaxPntRgh1 = aBVH1->MaxPoint (aNodeData1.z()); - - if (aNodeData2.x() == 0) // inner node - { - const BVH_Vec3d& aMinPntLft2 = aBVH2->MinPoint (aNodeData2.y()); - const BVH_Vec3d& aMaxPntLft2 = aBVH2->MaxPoint (aNodeData2.y()); - const BVH_Vec3d& aMinPntRgh2 = aBVH2->MinPoint (aNodeData2.z()); - const BVH_Vec3d& aMaxPntRgh2 = aBVH2->MaxPoint (aNodeData2.z()); - - if (overlapBoxes (aMinPntLft1, aMaxPntLft1, aMinPntLft2, aMaxPntLft2, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.y(), aNodeData2.y()); - } - if (overlapBoxes (aMinPntLft1, aMaxPntLft1, aMinPntRgh2, aMaxPntRgh2, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.y(), aNodeData2.z()); - } - if (overlapBoxes (aMinPntRgh1, aMaxPntRgh1, aMinPntLft2, aMaxPntLft2, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.z(), aNodeData2.y()); - } - if (overlapBoxes (aMinPntRgh1, aMaxPntRgh1, aMinPntRgh2, aMaxPntRgh2, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.z(), aNodeData2.z()); - } - } - else - { - const BVH_Vec3d& aMinPntLeaf = aBVH2->MinPoint (aNodes.Node2); - const BVH_Vec3d& aMaxPntLeaf = aBVH2->MaxPoint (aNodes.Node2); - - if (overlapBoxes (aMinPntLft1, aMaxPntLft1, aMinPntLeaf, aMaxPntLeaf, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.y(), aNodes.Node2); - } - if (overlapBoxes (aMinPntRgh1, aMaxPntRgh1, aMinPntLeaf, aMaxPntLeaf, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodeData1.z(), aNodes.Node2); - } - } - } - else - { - const BVH_Vec3d& aMinPntLeaf = aBVH1->MinPoint (aNodes.Node1); - const BVH_Vec3d& aMaxPntLeaf = aBVH1->MaxPoint (aNodes.Node1); - - const BVH_Vec3d& aMinPntLft2 = aBVH2->MinPoint (aNodeData2.y()); - const BVH_Vec3d& aMaxPntLft2 = aBVH2->MaxPoint (aNodeData2.y()); - const BVH_Vec3d& aMinPntRgh2 = aBVH2->MinPoint (aNodeData2.z()); - const BVH_Vec3d& aMaxPntRgh2 = aBVH2->MaxPoint (aNodeData2.z()); - - if (overlapBoxes (aMinPntLft2, aMaxPntLft2, aMinPntLeaf, aMaxPntLeaf, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodes.Node1, aNodeData2.y()); - } - if (overlapBoxes (aMinPntRgh2, aMaxPntRgh2, aMinPntLeaf, aMaxPntLeaf, theTolerance)) - { - aPairsToProcess[aNbPairs++] = BRepExtrema_StackItem (aNodes.Node1, aNodeData2.z()); - } - } - - if (aNbPairs > 0) - { - aNodes = aPairsToProcess[0]; - - for (Standard_Integer anIdx = 1; anIdx < aNbPairs; ++anIdx) - { - aStack[++aHead] = aPairsToProcess[anIdx]; - } - } - else - { - if (aHead < 0) - break; - - aNodes = aStack[aHead--]; - } - } + intersectTrianglesToler (theTrgIdx1, theTrgIdx2, myTolerance); } - - myIsDone = Standard_True; + return Standard_True; } diff --git a/src/BRepExtrema/BRepExtrema_OverlapTool.hxx b/src/BRepExtrema/BRepExtrema_OverlapTool.hxx index 4ea3ef2030..08628c2656 100644 --- a/src/BRepExtrema/BRepExtrema_OverlapTool.hxx +++ b/src/BRepExtrema/BRepExtrema_OverlapTool.hxx @@ -16,10 +16,10 @@ #ifndef _BRepExtrema_OverlapTool_HeaderFile #define _BRepExtrema_OverlapTool_HeaderFile -#include #include #include #include +#include //! Enables storing of individual overlapped triangles (useful for debug). // #define OVERLAP_TOOL_OUTPUT_TRIANGLES @@ -35,7 +35,7 @@ //! In second case, tessellation of single shape will be tested for self- //! intersections. Please note that algorithm results are approximate and //! depend greatly on the quality of input tessellation(s). -class BRepExtrema_OverlapTool +class BRepExtrema_OverlapTool : public BVH_PairTraverse { public: @@ -78,16 +78,30 @@ public: //! Sets filtering tool for preliminary checking pairs of mesh elements. void SetElementFilter (BRepExtrema_ElementFilter* theFilter) { myFilter = theFilter; } + +public: //! @name Reject/Accept implementations + + //! Defines the rules for node rejection by bounding box + Standard_EXPORT virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin1, + const BVH_Vec3d& theCornerMax1, + const BVH_Vec3d& theCornerMin2, + const BVH_Vec3d& theCornerMax2, + Standard_Real&) const Standard_OVERRIDE; + //! Defines the rules for leaf acceptance + Standard_EXPORT virtual Standard_Boolean Accept (const Standard_Integer theLeaf1, + const Standard_Integer theLeaf2) Standard_OVERRIDE; + + protected: //! Performs narrow-phase of overlap test (exact intersection). - void intersectTriangleRangesExact (const BVH_Vec4i& theLeaf1, - const BVH_Vec4i& theLeaf2); + void intersectTrianglesExact (const Standard_Integer theTrgIdx1, + const Standard_Integer theTrgIdx2); //! Performs narrow-phase of overlap test (intersection with non-zero tolerance). - void intersectTriangleRangesToler (const BVH_Vec4i& theLeaf1, - const BVH_Vec4i& theLeaf2, - const Standard_Real theToler); + void intersectTrianglesToler (const Standard_Integer theTrgIdx1, + const Standard_Integer theTrgIdx2, + const Standard_Real theToler); private: @@ -113,6 +127,8 @@ private: //! Is overlap test test completed? Standard_Boolean myIsDone; + + Standard_Real myTolerance; }; #endif // _BRepExtrema_OverlapTool_HeaderFile diff --git a/src/BRepExtrema/BRepExtrema_ShapeProximity.hxx b/src/BRepExtrema/BRepExtrema_ShapeProximity.hxx index 0cdb4aba76..328d23d94d 100644 --- a/src/BRepExtrema/BRepExtrema_ShapeProximity.hxx +++ b/src/BRepExtrema/BRepExtrema_ShapeProximity.hxx @@ -16,7 +16,6 @@ #ifndef _BRepExtrema_ShapeProximity_HeaderFile #define _BRepExtrema_ShapeProximity_HeaderFile -#include #include #include diff --git a/src/BVH/BVH_Box.hxx b/src/BVH/BVH_Box.hxx index 8210aa39ba..920c278a41 100644 --- a/src/BVH/BVH_Box.hxx +++ b/src/BVH/BVH_Box.hxx @@ -108,6 +108,87 @@ public: //! Returns center of bounding box along the given axis. T Center (const Standard_Integer theAxis) const; +public: + + //! Checks if the Box is out of the other box. + Standard_Boolean IsOut (const BVH_Box& theOther) const + { + if (!theOther.IsValid()) + return Standard_True; + + return IsOut (theOther.myMinPoint, theOther.myMaxPoint); + } + + //! Checks if the Box is out of the other box defined by two points. + Standard_Boolean IsOut (const BVH_VecNt& theMinPoint, + const BVH_VecNt& theMaxPoint) const + { + if (!IsValid()) + return Standard_True; + + int n = Min (N, 3); + for (int i = 0; i < n; ++i) + { + if (myMinPoint[i] > theMaxPoint[i] || + myMaxPoint[i] < theMinPoint[i]) + return Standard_True; + } + return Standard_False; + } + + //! Checks if the Box fully contains the other box. + Standard_Boolean Contains (const BVH_Box& theOther, + Standard_Boolean& hasOverlap) const + { + hasOverlap = Standard_False; + if (!theOther.IsValid()) + return Standard_False; + + return Contains (theOther.myMinPoint, theOther.myMaxPoint, hasOverlap); + } + + //! Checks if the Box is fully contains the other box. + Standard_Boolean Contains (const BVH_VecNt& theMinPoint, + const BVH_VecNt& theMaxPoint, + Standard_Boolean& hasOverlap) const + { + hasOverlap = Standard_False; + if (!IsValid()) + return Standard_False; + + Standard_Boolean isInside = Standard_True; + + int n = Min (N, 3); + for (int i = 0; i < n; ++i) + { + hasOverlap = (myMinPoint[i] <= theMaxPoint[i] && + myMaxPoint[i] >= theMinPoint[i]); + if (!hasOverlap) + return Standard_False; + + isInside = isInside && (myMinPoint[i] <= theMinPoint[i] && + myMaxPoint[i] >= theMaxPoint[i]); + } + return isInside; + } + + //! Checks if the Point is out of the box. + Standard_Boolean IsOut (const BVH_VecNt& thePoint) const + { + if (!IsValid()) + return Standard_True; + + int n = Min (N, 3); + for (int i = 0; i < n; ++i) + { + if (thePoint[i] < myMinPoint[i] || + thePoint[i] > myMaxPoint[i]) + return Standard_True; + } + return Standard_False; + } + + protected: BVH_VecNt myMinPoint; //!< Minimum point of bounding box diff --git a/src/BVH/BVH_BoxSet.hxx b/src/BVH/BVH_BoxSet.hxx new file mode 100644 index 0000000000..5aace9e994 --- /dev/null +++ b/src/BVH/BVH_BoxSet.hxx @@ -0,0 +1,132 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_BoxSet_Header +#define _BVH_BoxSet_Header + +#include + +//! Implements easy to use interfaces for adding the elements into +//! BVH tree and its following construction. +//! To make it more effective it is better to set the number of elements +//! that are going to be added into BVH tree. +//! For better efficiency on heavy data types it is recommended to use +//! either BHV_IndexedBoxSet which uses indirect indexing for accessing +//! the elements and their boxes or set the element to be an index +//! of the real element in the application's internal data structures. +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam DataType Type of elements on which the boxes are built +template +class BVH_BoxSet : public BVH_PrimitiveSet +{ +public: //! @name Constructors + + //! Empty constructor for use the default BVH_Builder + BVH_BoxSet() + : BVH_PrimitiveSet () + { + } + + //! Constructor for usage the custom BVH builder + BVH_BoxSet (const opencascade::handle >& theBuilder) + : BVH_PrimitiveSet (theBuilder) + { + } + +public: //! @name Setting expected size of the BVH + + //! Sets the expected size of BVH tree + virtual void SetSize (const Standard_Size theSize) + { + myElements.reserve (theSize); + myBoxes.reserve (theSize); + } + +public: //! @name Adding elements in BVH + + //! Adds the element into BVH + virtual void Add (const DataType& theElement, const BVH_Box& theBox) + { + myElements.push_back (theElement); + myBoxes.push_back (theBox); + BVH_Object::myIsDirty = Standard_True; + } + +public: //! @name BVH construction + + //! BVH construction + void Build() + { + BVH_PrimitiveSet ::Update(); + } + +public: //! @name Clearing the elements and boxes + + //! Clears the vectors of elements and boxes + virtual void Clear() + { + myElements.clear(); + myBoxes.clear(); + BVH_Object::myIsDirty = Standard_True; + } + +public: //! @name Necessary overrides for BVH construction + + //! Make inherited method Box() visible to avoid CLang warning + using BVH_PrimitiveSet ::Box; + + //! Returns the bounding box with the given index. + virtual BVH_Box Box (const Standard_Integer theIndex) const Standard_OVERRIDE + { + return myBoxes[theIndex]; + } + + //! Returns centroid position along specified axis. + virtual Standard_Real Center (const Standard_Integer theIndex, + const Standard_Integer theAxis) const Standard_OVERRIDE + { + return Box (theIndex).Center (theAxis); + } + + //! Returns the number of boxes. + virtual Standard_Integer Size() const Standard_OVERRIDE + { + return static_cast (myBoxes.size()); + } + + //! Swaps indices of two specified boxes. + virtual void Swap (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + std::swap (myElements[theIndex1], myElements[theIndex2]); + std::swap (myBoxes [theIndex1], myBoxes [theIndex2]); + } + + //! Returns the Element with the index theIndex. + virtual DataType Element (const Standard_Integer theIndex) const + { + return myElements[theIndex]; + } + +protected: //! @name Fields + + std::vector myElements; //!< Elements + std::vector > myBoxes; //!< Boxes for the elements + +}; + +#endif // _BVH_BoxSet_Header diff --git a/src/BVH/BVH_Distance.hxx b/src/BVH/BVH_Distance.hxx new file mode 100644 index 0000000000..286b08a394 --- /dev/null +++ b/src/BVH/BVH_Distance.hxx @@ -0,0 +1,97 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_Distance_Header +#define _BVH_Distance_Header + +#include + +//! Abstract class for computation of the min distance between some +//! Object and elements of BVH tree. +//! To use this class it is required to define two methods: +//! - *RejectNode* to compute distance from the object to bounding box +//! - *Accept* to compute distance from the object to the element of tree +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam ObjectType Type of the object to which the distance is required +//! \tparam BVHSetType Type of the set on which BVH is built +template +class BVH_Distance : public BVH_Traverse +{ +public: //! @name Constructor + + //! Constructor + BVH_Distance() + : BVH_Traverse (), + myDistance (std::numeric_limits::max()) + { + } + +public: //! @name Setting object for distance computation + + //! Sets the object to which the distance is required + void SetObject (const ObjectType& theObject) + { + myObject = theObject; + } + +public: //! @name Compute the distance + + //! Computes the distance between object and BVH tree + NumType ComputeDistance() + { + myIsDone = this->Select() > 0; + return myDistance; + } + +public: //! @name Accessing the results + + //! Returns IsDone flag + Standard_Boolean IsDone () const { return myIsDone; } + + //! Returns the computed distance + NumType Distance() const { return myDistance; } + +public: //! @name Definition of the rules for tree descend + + //! Compares the two metrics and chooses the best one + virtual Standard_Boolean IsMetricBetter (const NumType& theLeft, + const NumType& theRight) const Standard_OVERRIDE + { + return theLeft < theRight; + } + + //! Rejects the branch by the metric + virtual Standard_Boolean RejectMetric (const NumType& theMetric) const Standard_OVERRIDE + { + return theMetric > myDistance; + } + + //! Returns the flag controlling the tree descend + virtual Standard_Boolean Stop() const Standard_OVERRIDE + { + return myDistance == static_cast(0); + } + +protected: //! @name Fields + + NumType myDistance; //!< Distance + Standard_Boolean myIsDone; //!< State of the algorithm + ObjectType myObject; //!< Object to compute the distance to + +}; + +#endif // _BVH_Distance_Header diff --git a/src/BVH/BVH_DistanceField.lxx b/src/BVH/BVH_DistanceField.lxx index 5d3e12ce9a..5be06f3f8f 100644 --- a/src/BVH/BVH_DistanceField.lxx +++ b/src/BVH/BVH_DistanceField.lxx @@ -15,6 +15,7 @@ #include #include +#include // ======================================================================= // function : BVH_DistanceField @@ -163,235 +164,196 @@ namespace BVH } //======================================================================= - //function : SquareDistanceToObject - //purpose : Computes squared distance from point to BVH triangulation + //function : SquareDistanceToPoint + //purpose : Abstract class to compute squared distance from point to BVH tree //======================================================================= - template - T SquareDistanceToObject (BVH_Object* theObject, - const typename VectorType::Type& thePnt, Standard_Boolean& theIsOutside) + template + class SquareDistanceToPoint : public BVH_Distance::Type, BVHSetType> { - Standard_STATIC_ASSERT (N == 3 || N == 4); + public: + typedef typename VectorType::Type BVH_VecNt; - T aMinDistance = std::numeric_limits::max(); + public: + SquareDistanceToPoint() + : BVH_Distance(), + myIsOutside (Standard_True) + {} - BVH_Triangulation* aTriangulation = - dynamic_cast*> (theObject); + public: - Standard_ASSERT_RETURN (aTriangulation != NULL, - "Error: Unsupported BVH object (non triangulation)", aMinDistance); + //! IsOutside + Standard_Boolean IsOutside() const { return myIsOutside; } - const opencascade::handle >& aBVH = aTriangulation->BVH(); - if (aBVH.IsNull()) + public: + + //! Defines the rules for node rejection + virtual Standard_Boolean RejectNode (const BVH_VecNt& theCMin, + const BVH_VecNt& theCMax, + T& theMetric) const Standard_OVERRIDE { - return Standard_False; + theMetric = DistanceToBox (this->myObject, theCMin, theCMax); + return theMetric > this->myDistance; } - std::pair aStack[BVH_Constants_MaxTreeDepth]; - - Standard_Integer aHead = -1; - Standard_Integer aNode = 0; // root node + public: - for (;;) + //! Redefine the Stop to never stop the selection + virtual Standard_Boolean Stop() const Standard_OVERRIDE { - BVH_Vec4i aData = aBVH->NodeInfoBuffer()[aNode]; + return Standard_False; + } - if (aData.x() == 0) // if inner node - { - const T aDistToLft = DistanceToBox (thePnt, - aBVH->MinPoint (aData.y()), - aBVH->MaxPoint (aData.y())); - - const T aDistToRgh = DistanceToBox (thePnt, - aBVH->MinPoint (aData.z()), - aBVH->MaxPoint (aData.z())); - - const Standard_Boolean aHitLft = aDistToLft <= aMinDistance; - const Standard_Boolean aHitRgh = aDistToRgh <= aMinDistance; - - if (aHitLft & aHitRgh) - { - aNode = (aDistToLft < aDistToRgh) ? aData.y() : aData.z(); - - aStack[++aHead] = std::pair ( - aDistToLft < aDistToRgh ? aData.z() : aData.y(), Max (aDistToLft, aDistToRgh)); - } - else - { - if (aHitLft | aHitRgh) - { - aNode = aHitLft ? aData.y() : aData.z(); - } - else - { - if (aHead < 0) - return aMinDistance; - - std::pair& anInfo = aStack[aHead--]; - - while (anInfo.second > aMinDistance) - { - if (aHead < 0) - return aMinDistance; - - anInfo = aStack[aHead--]; - } - - aNode = anInfo.first; - } - } - } - else // if leaf node - { - for (Standard_Integer aTrgIdx = aData.y(); aTrgIdx <= aData.z(); ++aTrgIdx) - { - const BVH_Vec4i aTriangle = aTriangulation->Elements[aTrgIdx]; + protected: - const typename VectorType::Type aVertex0 = aTriangulation->Vertices[aTriangle.x()]; - const typename VectorType::Type aVertex1 = aTriangulation->Vertices[aTriangle.y()]; - const typename VectorType::Type aVertex2 = aTriangulation->Vertices[aTriangle.z()]; + Standard_Boolean myIsOutside; + }; - const typename VectorType::Type aDirection = - DirectionToNearestPoint (thePnt, aVertex0, aVertex1, aVertex2); + //======================================================================= + //function : PointTriangulationSquareDistance + //purpose : Computes squared distance from point to BVH triangulation + //======================================================================= + template + class PointTriangulationSquareDistance: public SquareDistanceToPoint > + { + public: + typedef typename VectorType::Type BVH_VecNt; - const T aDistance = BVH_DOT3 (aDirection, aDirection); + public: + //! Constructor + PointTriangulationSquareDistance() + : SquareDistanceToPoint>() + { + } - if (aDistance < aMinDistance) - { - aMinDistance = aDistance; + public: + // Accepting the element + virtual Standard_Boolean Accept (const Standard_Integer theIndex, + const T&) Standard_OVERRIDE + { + const BVH_Vec4i aTriangle = this->myBVHSet->Elements[theIndex]; - typename VectorType::Type aTrgEdges[] = { aVertex1 - aVertex0, - aVertex2 - aVertex0 }; + const BVH_VecNt aVertex0 = this->myBVHSet->Vertices[aTriangle.x()]; + const BVH_VecNt aVertex1 = this->myBVHSet->Vertices[aTriangle.y()]; + const BVH_VecNt aVertex2 = this->myBVHSet->Vertices[aTriangle.z()]; - typename VectorType::Type aTrgNormal; - - aTrgNormal.x() = aTrgEdges[0].y() * aTrgEdges[1].z() - aTrgEdges[0].z() * aTrgEdges[1].y(); - aTrgNormal.y() = aTrgEdges[0].z() * aTrgEdges[1].x() - aTrgEdges[0].x() * aTrgEdges[1].z(); - aTrgNormal.z() = aTrgEdges[0].x() * aTrgEdges[1].y() - aTrgEdges[0].y() * aTrgEdges[1].x(); + const BVH_VecNt aDirection = + DirectionToNearestPoint (this->myObject, aVertex0, aVertex1, aVertex2); - theIsOutside = BVH_DOT3 (aTrgNormal, aDirection) > 0; - } - } + const T aDistance = BVH_DOT3 (aDirection, aDirection); - if (aHead < 0) - return aMinDistance; + if (aDistance < this->myDistance) + { + this->myDistance = aDistance; - std::pair& anInfo = aStack[aHead--]; + BVH_VecNt aTrgEdges[] = { aVertex1 - aVertex0, aVertex2 - aVertex0 }; - while (anInfo.second > aMinDistance) - { - if (aHead < 0) - return aMinDistance; + BVH_VecNt aTrgNormal; - anInfo = aStack[aHead--]; - } + aTrgNormal.x () = aTrgEdges[0].y () * aTrgEdges[1].z () - aTrgEdges[0].z () * aTrgEdges[1].y (); + aTrgNormal.y () = aTrgEdges[0].z () * aTrgEdges[1].x () - aTrgEdges[0].x () * aTrgEdges[1].z (); + aTrgNormal.z () = aTrgEdges[0].x () * aTrgEdges[1].y () - aTrgEdges[0].y () * aTrgEdges[1].x (); - aNode = anInfo.first; + this->myIsOutside = BVH_DOT3 (aTrgNormal, aDirection) > 0; + + return Standard_True; } + + return Standard_False; } - } + }; //======================================================================= - //function : SquareDistanceToGeomerty - //purpose : Computes squared distance from point to BVH geometry + //function : SquareDistanceToObject + //purpose : Computes squared distance from point to BVH triangulation //======================================================================= template - T SquareDistanceToGeomerty (BVH_Geometry& theGeometry, + T SquareDistanceToObject (BVH_Object* theObject, const typename VectorType::Type& thePnt, Standard_Boolean& theIsOutside) { Standard_STATIC_ASSERT (N == 3 || N == 4); - const BVH_Tree* aBVH = theGeometry.BVH().get(); + T aMinDistance = std::numeric_limits::max(); - if (aBVH == NULL) + BVH_Triangulation* aTriangulation = + dynamic_cast*> (theObject); + + Standard_ASSERT_RETURN (aTriangulation != NULL, + "Error: Unsupported BVH object (non triangulation)", aMinDistance); + + const opencascade::handle >& aBVH = aTriangulation->BVH(); + if (aBVH.IsNull()) { return Standard_False; } - std::pair aStack[BVH_Constants_MaxTreeDepth]; + PointTriangulationSquareDistance aDistTool; + aDistTool.SetObject (thePnt); + aDistTool.SetBVHSet (aTriangulation); + aDistTool.ComputeDistance(); + theIsOutside = aDistTool.IsOutside(); + return aDistTool.Distance(); + } - Standard_Integer aHead = -1; - Standard_Integer aNode = 0; // root node + //======================================================================= + //function : PointGeometrySquareDistance + //purpose : Computes squared distance from point to BVH geometry + //======================================================================= + template + class PointGeometrySquareDistance: public SquareDistanceToPoint > + { + public: + typedef typename VectorType::Type BVH_VecNt; - T aMinDistance = std::numeric_limits::max(); + public: + //! Constructor + PointGeometrySquareDistance() + : SquareDistanceToPoint>() + { + } - for (;;) + public: + // Accepting the element + virtual Standard_Boolean Accept (const Standard_Integer theIndex, + const T&) Standard_OVERRIDE { - BVH_Vec4i aData = aBVH->NodeInfoBuffer()[aNode]; + Standard_Boolean isOutside = Standard_True; + const T aDistance = SquareDistanceToObject ( + this->myBVHSet->Objects ()(theIndex).operator->(), this->myObject, isOutside); - if (aData.x() == 0) // if inner node + if (aDistance < this->myDistance) { - const T aDistToLft = DistanceToBox (thePnt, - aBVH->MinPoint (aData.y()), - aBVH->MaxPoint (aData.y())); - - const T aDistToRgh = DistanceToBox (thePnt, - aBVH->MinPoint (aData.z()), - aBVH->MaxPoint (aData.z())); - - const Standard_Boolean aHitLft = aDistToLft <= aMinDistance; - const Standard_Boolean aHitRgh = aDistToRgh <= aMinDistance; - - if (aHitLft & aHitRgh) - { - aNode = (aDistToLft < aDistToRgh) ? aData.y() : aData.z(); - - aStack[++aHead] = std::pair ( - aDistToLft < aDistToRgh ? aData.z() : aData.y(), Max (aDistToLft, aDistToRgh)); - } - else - { - if (aHitLft | aHitRgh) - { - aNode = aHitLft ? aData.y() : aData.z(); - } - else - { - if (aHead < 0) - return aMinDistance; - - std::pair& anInfo = aStack[aHead--]; - - while (anInfo.second > aMinDistance) - { - if (aHead < 0) - return aMinDistance; - - anInfo = aStack[aHead--]; - } - - aNode = anInfo.first; - } - } - } - else // if leaf node - { - Standard_Boolean isOutside = Standard_True; + this->myDistance = aDistance; + this->myIsOutside = isOutside; - const T aDistance = SquareDistanceToObject ( - theGeometry.Objects()(aNode).operator->(), thePnt, isOutside); - - if (aDistance < aMinDistance) - { - aMinDistance = aDistance; - theIsOutside = isOutside; - } - - if (aHead < 0) - return aMinDistance; - - std::pair& anInfo = aStack[aHead--]; + return Standard_True; + } + return Standard_False; + } + }; - while (anInfo.second > aMinDistance) - { - if (aHead < 0) - return aMinDistance; + //======================================================================= + //function : SquareDistanceToGeomerty + //purpose : Computes squared distance from point to BVH geometry + //======================================================================= + template + T SquareDistanceToGeomerty (BVH_Geometry& theGeometry, + const typename VectorType::Type& thePnt, Standard_Boolean& theIsOutside) + { + Standard_STATIC_ASSERT (N == 3 || N == 4); - anInfo = aStack[aHead--]; - } + const BVH_Tree* aBVH = theGeometry.BVH().get(); - aNode = anInfo.first; - } + if (aBVH == NULL) + { + return Standard_False; } + + PointGeometrySquareDistance aDistTool; + aDistTool.SetObject (thePnt); + aDistTool.SetBVHSet (&theGeometry); + aDistTool.ComputeDistance(); + theIsOutside = aDistTool.IsOutside(); + return aDistTool.Distance(); } } diff --git a/src/BVH/BVH_IndexedBoxSet.hxx b/src/BVH/BVH_IndexedBoxSet.hxx new file mode 100644 index 0000000000..dd822adce0 --- /dev/null +++ b/src/BVH/BVH_IndexedBoxSet.hxx @@ -0,0 +1,109 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_IndexedBoxSet_Header +#define _BVH_IndexedBoxSet_Header + +#include + +//! Implements easy to use interfaces for adding the elements into +//! BVH tree and its following construction. +//! To make it more effective it is better to set the number of elements +//! that are going to be added into BVH tree. +//! It uses the indirect indexing for accessing the elements and their boxes +//! which allows using heavy data types as elements with better efficiency +//! during BVH construction and just a bit slower selection time. +//! Due to better BVH tree construction time the class will be more efficient +//! than BVH_BoxSet on the operations where just a few selections from +//! the tree required. +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam DataType Type of elements on which the boxes are built +template +class BVH_IndexedBoxSet : public BVH_BoxSet +{ +public: //! @name Constructors + + //! Empty constructor for use the default BVH_Builder + BVH_IndexedBoxSet() + : BVH_BoxSet () + { + } + + //! Constructor for usage the custom BVH builder + BVH_IndexedBoxSet (const opencascade::handle >& theBuilder) + : BVH_BoxSet (theBuilder) + { + } + +public: //! @name Setting expected size of the BVH + + //! Sets the expected size of BVH tree + virtual void SetSize (const Standard_Size theSize) Standard_OVERRIDE + { + myIndices.reserve (theSize); + BVH_BoxSet ::SetSize (theSize); + } + +public: //! @name Adding elements in BVH + + //! Adds the element into BVH + virtual void Add (const DataType& theElement, const BVH_Box& theBox) Standard_OVERRIDE + { + myIndices.push_back (static_cast (myIndices.size())); + BVH_BoxSet ::Add (theElement, theBox); + } + +public: //! @name Clearing the elements and boxes + + //! Clears the vectors of elements and boxes + virtual void Clear() Standard_OVERRIDE + { + myIndices.clear(); + BVH_BoxSet ::Clear(); + } + +public: //! @name Necessary overrides for BVH construction + + //! Make inherited method Box() visible to avoid CLang warning + using BVH_BoxSet ::Box; + + //! Returns the bounding box with the given index. + virtual BVH_Box Box (const Standard_Integer theIndex) const Standard_OVERRIDE + { + return myBoxes[myIndices[theIndex]]; + } + + //! Swaps indices of two specified boxes. + virtual void Swap (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + std::swap (myIndices[theIndex1], myIndices[theIndex2]); + } + + //! Returns the Element with the index theIndex. + virtual DataType Element (const Standard_Integer theIndex) const + { + return myElements[myIndices[theIndex]]; + } + +protected: //! @name Fields + + std::vector myIndices; + +}; + +#endif // _BVH_IndexedBoxSet_Header diff --git a/src/BVH/BVH_PairDistance.hxx b/src/BVH/BVH_PairDistance.hxx new file mode 100644 index 0000000000..c7238ccfe9 --- /dev/null +++ b/src/BVH/BVH_PairDistance.hxx @@ -0,0 +1,102 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_PairDistance_Header +#define _BVH_PairDistance_Header + +#include +#include + +//! Abstract class for computation of the min distance between +//! elements of two BVH trees. +//! To use this class it is required to define only the method +//! *Accept* to compute the distance between elements of the trees. +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam BVHSetType Type of the set on which BVH is built +template +class BVH_PairDistance : public BVH_PairTraverse +{ +public: + typedef typename BVH_Tools::BVH_VecNt BVH_VecNt; + +public: //! @name Constructor + + //! Constructor + BVH_PairDistance() + : BVH_PairTraverse (), + myDistance (std::numeric_limits::max()) + { + } + +public: //! @name Compute the distance + + //! Computes the distance between two BVH trees + NumType ComputeDistance () + { + myIsDone = this->Select() > 0; + return myDistance; + } + +public: //! @name Accessing the results + + //! Returns IsDone flag + Standard_Boolean IsDone () const { return myIsDone; } + + //! Returns the computed distance + NumType Distance() const { return myDistance; } + +public: //! @name Definition of the rules for tree descend + + //! Compares the two metrics and chooses the best one + virtual Standard_Boolean IsMetricBetter (const NumType& theLeft, + const NumType& theRight) const Standard_OVERRIDE + { + return theLeft < theRight; + } + + //! Computes the distance between boxes of the nodes + virtual Standard_Boolean RejectNode (const BVH_VecNt& theCornerMin1, + const BVH_VecNt& theCornerMax1, + const BVH_VecNt& theCornerMin2, + const BVH_VecNt& theCornerMax2, + NumType& theMetric) const Standard_OVERRIDE + { + theMetric = BVH_Tools::BoxBoxSquareDistance (theCornerMin1, theCornerMax1, + theCornerMin2, theCornerMax2); + return theMetric > myDistance; + } + + //! Rejects the branch by the metric + virtual Standard_Boolean RejectMetric (const NumType& theMetric) const Standard_OVERRIDE + { + return theMetric > myDistance; + } + + //! Returns the flag controlling the tree descend + virtual Standard_Boolean Stop() const Standard_OVERRIDE + { + return myDistance == static_cast(0); + } + +protected: //! @name Fields + + NumType myDistance; //!< Square distance + Standard_Boolean myIsDone; //!< State of the algorithm + +}; + +#endif // _BVH_Distance_Header diff --git a/src/BVH/BVH_Tools.hxx b/src/BVH/BVH_Tools.hxx new file mode 100644 index 0000000000..24d16b58a8 --- /dev/null +++ b/src/BVH/BVH_Tools.hxx @@ -0,0 +1,165 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_Tools_Header +#define _BVH_Tools_Header + +#include +#include + +//! Defines a set of static methods operating with points and bounding boxes. +//! \tparam T Numeric data type +//! \tparam N Vector dimension +template +class BVH_Tools +{ +public: //! @name public types + + typedef typename BVH::VectorType::Type BVH_VecNt; + +public: //! @name Box-Box Square distance + + //! Computes Square distance between Axis aligned bounding boxes + static T BoxBoxSquareDistance (const BVH_Box& theBox1, + const BVH_Box& theBox2) + { + return BoxBoxSquareDistance (theBox1.CornerMin(), theBox1.CornerMax(), + theBox2.CornerMin(), theBox2.CornerMax()); + } + + //! Computes Square distance between Axis aligned bounding boxes + static T BoxBoxSquareDistance (const BVH_VecNt& theCMin1, + const BVH_VecNt& theCMax1, + const BVH_VecNt& theCMin2, + const BVH_VecNt& theCMax2) + { + T aDist = 0; + for (int i = 0; i < N; ++i) + { + if (theCMin1[i] > theCMax2[i]) { T d = theCMin1[i] - theCMax2[i]; d *= d; aDist += d; } + else if (theCMax1[i] < theCMin2[i]) { T d = theCMin2[i] - theCMax1[i]; d *= d; aDist += d; } + } + return aDist; + } + +public: //! @name Point-Box Square distance + + //! Computes square distance between point and bounding box + static T PointBoxSquareDistance (const BVH_VecNt& thePoint, + const BVH_Box& theBox) + { + return PointBoxSquareDistance (thePoint, + theBox.CornerMin(), + theBox.CornerMax()); + } + + //! Computes square distance between point and bounding box + static T PointBoxSquareDistance (const BVH_VecNt& thePoint, + const BVH_VecNt& theCMin, + const BVH_VecNt& theCMax) + { + T aDist = 0; + for (int i = 0; i < N; ++i) + { + if (thePoint[i] < theCMin[i]) { T d = theCMin[i] - thePoint[i]; d *= d; aDist += d; } + else if (thePoint[i] > theCMax[i]) { T d = thePoint[i] - theCMax[i]; d *= d; aDist += d; } + } + return aDist; + } + +public: //! @name Point-Triangle Square distance + + //! Computes square distance between point and triangle + static T PointTriangleSquareDistance (const BVH_VecNt& thePoint, + const BVH_VecNt& theNode0, + const BVH_VecNt& theNode1, + const BVH_VecNt& theNode2) + { + const BVH_VecNt aAB = theNode1 - theNode0; + const BVH_VecNt aAC = theNode2 - theNode0; + const BVH_VecNt aAP = thePoint - theNode0; + + T aABdotAP = aAB.Dot(aAP); + T aACdotAP = aAC.Dot(aAP); + + if (aABdotAP <= 0. && aACdotAP <= 0.) + { + return aAP.Dot(aAP); + } + + const BVH_VecNt aBC = theNode2 - theNode1; + const BVH_VecNt aBP = thePoint - theNode1; + + T aBAdotBP = -(aAB.Dot(aBP)); + T aBCdotBP = (aBC.Dot(aBP)); + + if (aBAdotBP <= 0. && aBCdotBP <= 0.) + { + return (aBP.Dot(aBP)); + } + + const BVH_VecNt aCP = thePoint - theNode2; + + T aCBdotCP = -(aBC.Dot(aCP)); + T aCAdotCP = -(aAC.Dot(aCP)); + + if (aCAdotCP <= 0. && aCBdotCP <= 0.) + { + return (aCP.Dot(aCP)); + } + + T aACdotBP = (aAC.Dot(aBP)); + + T aVC = aABdotAP * aACdotBP + aBAdotBP * aACdotAP; + + if (aVC <= 0. && aABdotAP > 0. && aBAdotBP > 0.) + { + const BVH_VecNt aDirect = aAP - aAB * (aABdotAP / (aABdotAP + aBAdotBP)); + + return (aDirect.Dot(aDirect)); + } + + T aABdotCP = (aAB.Dot(aCP)); + + T aVA = aBAdotBP * aCAdotCP - aABdotCP * aACdotBP; + + if (aVA <= 0. && aBCdotBP > 0. && aCBdotCP > 0.) + { + const BVH_VecNt aDirect = aBP - aBC * (aBCdotBP / (aBCdotBP + aCBdotCP)); + + return (aDirect.Dot(aDirect)); + } + + T aVB = aABdotCP * aACdotAP + aABdotAP * aCAdotCP; + + if (aVB <= 0. && aACdotAP > 0. && aCAdotCP > 0.) + { + const BVH_VecNt aDirect = aAP - aAC * (aACdotAP / (aACdotAP + aCAdotCP)); + + return (aDirect.Dot(aDirect)); + } + + T aNorm = aVA + aVB + aVC; + + const BVH_VecNt& aDirect = thePoint - (theNode0 * aVA + + theNode1 * aVB + + theNode2 * aVC) / aNorm; + + return (aDirect.Dot(aDirect)); + } + +}; + +#endif \ No newline at end of file diff --git a/src/BVH/BVH_Traverse.hxx b/src/BVH/BVH_Traverse.hxx new file mode 100644 index 0000000000..583adfeac8 --- /dev/null +++ b/src/BVH/BVH_Traverse.hxx @@ -0,0 +1,343 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _BVH_Traverse_Header +#define _BVH_Traverse_Header + +#include +#include + +//! The classes implement the traverse of the BVH tree. +//! +//! There are two traverse methods implemented: +//! - Traverse of the single tree +//! - Parallel traverse of two trees +//! +//! To perform Selection of the elements from BVH_Tree using +//! the traverse methods implemented here it is +//! required to define Acceptance/Rejection rules in the +//! following methods: +//! - *RejectNode* - Node rejection by its bounding box. +//! It is applied to both inner and outer nodes of the BVH tree. +//! Optionally, the method should compute the metric for the node +//! which will allow performing traverse faster by descending by the +//! best branches. +//! - *Accept* - Element acceptance. It takes the index of the element +//! of BVH tree. The access to the element itself should be performed +//! through the set on which BVH is built. +//! The *Accept* method implements the leaf node operation and usually +//! defines the logic of the whole operation. +//! - *IsMetricBetter* - Compares the metrics of the nodes and returns +//! true if the left metric is better than the right one. +//! - *RejectMetric* - Node rejection by the metric. It should compare +//! the metric of the node with the global one and return true +//! if the global metric is better than the given one. +//! - *Stop* - implements conditions to stop the tree descend if the necessary +//! elements are already found. +//! +//! The selector of a single tree has an extra method which allows +//! accepting the whole branches without any further checks +//! (e.g. full inclusion test): +//! - *AcceptMetric* - basing on the metric of the node decides if the +//! node may be accepted without any further checks. +//! +//! Two ways of selection are possible: +//! 1. Set the BVH set containing the tree and use the method Select() +//! which allows using common interface for setting the BVH Set for accessing +//! the BVH tree and elements in the Accept method. +//! 2. Keep the BVHSetType void, do not set the BVH set and use the +//! method Select (const BVH_Tree<>&) which allows performing selection +//! on the arbitrary BVH tree. +//! +//! Here is the example of usage of the traverse to find the point-triangulation +//! minimal distance. +//! ~~~~ +//! // Structure to contain points of the triangle +//! struct Triangle +//! { +//! Triangle() {} +//! Triangle(const BVH_Vec3d& theNode1, +//! const BVH_Vec3d& theNode2, +//! const BVH_Vec3d& theNode3) +//! : Node1 (theNode1), Node2 (theNode2), Node3 (theNode3) +//! {} +//! +//! BVH_Vec3d Node1; +//! BVH_Vec3d Node2; +//! BVH_Vec3d Node3; +//! }; +//! +//! // Selector for min point-triangulation distance +//! class BVH_PointTriangulationSqDist : +//! public BVH_Distance> +//! { +//! public: +//! +//! // Computes the distance from the point to bounding box +//! virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCMin, +//! const BVH_Vec3d& theCMax, +//! Standard_Real& theDistance) const Standard_OVERRIDE +//! { +//! theDistance = BVH_Tools::PointBoxSquareDistance (myObject, theCMin, theCMax); +//! return RejectMetric (theDistance); +//! } +//! +//! // Computes the distance from the point to triangle +//! virtual Standard_Boolean Accept (const Standard_Integer theIndex, +//! const Standard_Real&) Standard_OVERRIDE +//! { +//! const Triangle& aTri = myBVHSet->Element (theIndex); +//! Standard_Real aDist = BVH_Tools::PointTriangleSquareDistance (myObject, aTri.Node1, aTri.Node2, aTri.Node3); +//! if (aDist < myDistance) +//! { +//! myDistance = aDist; +//! return Standard_True; +//! } +//! return Standard_False; +//! } +//! }; +//! +//! // Point to which the distance is required +//! BVH_Vec3d aPoint = ...; +//! // BVH Set containing triangulation +//! opencascade::handle> aTriangulationSet = ...; +//! +//! BVH_PointTriangulationSqDist aDistTool; +//! aDistTool.SetObject (aPoint); +//! aDistTool.SetBVHSet (aTriangulationSet.get()); +//! aDistTool.ComputeDistance(); +//! if (aDistTool.IsDone()) +//! { +//! Standard_Real aPointTriSqDist = aDistTool.Distance(); +//! } +//! +//! ~~~~ +//! + +//! Abstract class implementing the base Traverse interface +//! required for selection of the elements from BVH tree. +//! +//! \tparam MetricType Type of metric to perform more optimal tree descend +template +class BVH_BaseTraverse +{ +public: //! @name Metrics comparison for choosing the best branch + + //! Compares the two metrics and chooses the best one. + //! Returns true if the first metric is better than the second, + //! false otherwise. + virtual Standard_Boolean IsMetricBetter (const MetricType&, + const MetricType&) const + { + // Keep the left to right tree descend by default + return Standard_True; + } + +public: //! @name Rejection of the node by metric + + //! Rejects the node by the metric + virtual Standard_Boolean RejectMetric (const MetricType&) const + { + // Do not reject any nodes by metric by default + return Standard_False; + } + +public: //! @name Condition to stop the descend + + //! Returns the flag controlling the tree descend. + //! Returns true if the tree descend should be stopped. + virtual Standard_Boolean Stop() const + { + // Do not stop tree descend by default + return Standard_False; + } + +protected: //! @name Constructors + + //! Constructor + BVH_BaseTraverse() {} + + //! Destructor + virtual ~BVH_BaseTraverse() {} +}; + +//! Abstract class implementing the traverse of the single binary tree. +//! Selection of the data from the tree is performed by the +//! rules defined in the Accept/Reject methods. +//! See description of the required methods in the comments above. +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the index) +//! \tparam MetricType Type of metric to perform more optimal tree descend +template +class BVH_Traverse : public BVH_BaseTraverse +{ +public: //! @name public types + + typedef typename BVH_Box::BVH_VecNt BVH_VecNt; + +public: //! @name Constructor + + //! Constructor + BVH_Traverse() + : BVH_BaseTraverse(), + myBVHSet (NULL) + {} + +public: //! @name Setting the set to access the elements and BVH tree + + //! Sets the BVH Set containing the BVH tree + void SetBVHSet (BVHSetType* theBVHSet) + { + myBVHSet = theBVHSet; + } + +public: //! @name Rules for Accept/Reject + + //! Basing on the given metric, checks if the whole branch may be + //! accepted without any further checks. + //! Returns true if the metric is accepted, false otherwise. + virtual Standard_Boolean AcceptMetric (const MetricType&) const + { + // Do not accept the whole branch by default + return Standard_False; + } + + //! Rejection of the node by bounding box. + //! Metric is computed to choose the best branch. + //! Returns true if the node should be rejected, false otherwise. + virtual Standard_Boolean RejectNode (const BVH_VecNt& theCornerMin, + const BVH_VecNt& theCornerMax, + MetricType& theMetric) const = 0; + + //! Leaf element acceptance. + //! Metric of the parent leaf-node is passed to avoid the check on the + //! element and accept it unconditionally. + //! Returns true if the element has been accepted, false otherwise. + virtual Standard_Boolean Accept (const Standard_Integer theIndex, + const MetricType& theMetric) = 0; + +public: //! @name Selection + + //! Selection of the elements from the BVH tree by the + //! rules defined in Accept/Reject methods. + //! The method requires the BVHSet containing BVH tree to be set. + //! Returns the number of accepted elements. + Standard_Integer Select() + { + if (myBVHSet) + { + const opencascade::handle>& aBVH = myBVHSet->BVH(); + return Select (aBVH); + } + return 0; + } + + //! Performs selection of the elements from the BVH tree by the + //! rules defined in Accept/Reject methods. + //! Returns the number of accepted elements. + Standard_Integer Select (const opencascade::handle>& theBVH); + +protected: //! @name Fields + + BVHSetType* myBVHSet; +}; + +//! Abstract class implementing the parallel traverse of two binary trees. +//! Selection of the data from the trees is performed by the +//! rules defined in the Accept/Reject methods. +//! See description of the required methods in the comments above. +//! +//! \tparam NumType Numeric data type +//! \tparam Dimension Vector dimension +//! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the index) +//! \tparam MetricType Type of metric to perform more optimal tree descend +template +class BVH_PairTraverse : public BVH_BaseTraverse +{ +public: //! @name public types + + typedef typename BVH_Box::BVH_VecNt BVH_VecNt; + +public: //! @name Constructor + + //! Constructor + BVH_PairTraverse() + : BVH_BaseTraverse(), + myBVHSet1 (NULL), + myBVHSet2 (NULL) + { + } + +public: //! @name Setting the sets to access the elements and BVH trees + + //! Sets the BVH Sets containing the BVH trees + void SetBVHSets (BVHSetType* theBVHSet1, + BVHSetType* theBVHSet2) + { + myBVHSet1 = theBVHSet1; + myBVHSet2 = theBVHSet2; + } + +public: //! @name Rules for Accept/Reject + + //! Rejection of the pair of nodes by bounding boxes. + //! Metric is computed to choose the best branch. + //! Returns true if the pair of nodes should be rejected, false otherwise. + virtual Standard_Boolean RejectNode (const BVH_VecNt& theCornerMin1, + const BVH_VecNt& theCornerMax1, + const BVH_VecNt& theCornerMin2, + const BVH_VecNt& theCornerMax2, + MetricType& theMetric) const = 0; + + //! Leaf element acceptance. + //! Returns true if the pair of elements is accepted, false otherwise. + virtual Standard_Boolean Accept (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) = 0; + +public: //! @name Selection + + //! Selection of the pairs of elements of two BVH trees by the + //! rules defined in Accept/Reject methods. + //! The method requires the BVHSets containing BVH trees to be set. + //! Returns the number of accepted pairs of elements. + Standard_Integer Select() + { + if (myBVHSet1 && myBVHSet2) + { + const opencascade::handle >& aBVH1 = myBVHSet1->BVH(); + const opencascade::handle >& aBVH2 = myBVHSet2->BVH(); + return Select (aBVH1, aBVH2); + } + return 0; + } + + //! Performs selection of the elements from two BVH trees by the + //! rules defined in Accept/Reject methods. + //! Returns the number of accepted pairs of elements. + Standard_Integer Select (const opencascade::handle>& theBVH1, + const opencascade::handle>& theBVH2); + +protected: //! @name Fields + + BVHSetType* myBVHSet1; + BVHSetType* myBVHSet2; + +}; + +#include + +#endif // _BVH_Traverse_Header diff --git a/src/BVH/BVH_Traverse.lxx b/src/BVH/BVH_Traverse.lxx new file mode 100644 index 0000000000..b261dd9eb1 --- /dev/null +++ b/src/BVH/BVH_Traverse.lxx @@ -0,0 +1,299 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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. + +namespace +{ + //! Auxiliary structure for keeping the nodes to process + template struct BVH_NodeInStack + { + //! Constructor + BVH_NodeInStack (const Standard_Integer theNodeID = 0, + const MetricType& theMetric = MetricType()) + : NodeID (theNodeID), Metric (theMetric) + {} + + // Fields + Standard_Integer NodeID; //!< Id of the node in the BVH tree + MetricType Metric; //!< Metric computed for the node + }; +} + +// ======================================================================= +// function : BVH_Traverse::Select +// purpose : +// ======================================================================= +template +Standard_Integer BVH_Traverse ::Select + (const opencascade::handle>& theBVH) +{ + if (theBVH.IsNull()) + return 0; + + if (theBVH->NodeInfoBuffer().empty()) + return 0; + + // Create stack + BVH_NodeInStack aStack[BVH_Constants_MaxTreeDepth]; + + BVH_NodeInStack aNode (0); // Currently processed node, starting with the root node + BVH_NodeInStack aPrevNode = aNode; // Previously processed node + + Standard_Integer aHead = -1; // End of the stack + Standard_Integer aNbAccepted = 0; // Counter for accepted elements + + for (;;) + { + const BVH_Vec4i& aData = theBVH->NodeInfoBuffer()[aNode.NodeID]; + + if (aData.x() == 0) + { + // Inner node: + // - check the metric of the node + // - test the children of the node + + if (!this->AcceptMetric (aNode.Metric)) + { + // Test the left branch + MetricType aMetricLft; + Standard_Boolean isGoodLft = !RejectNode (theBVH->MinPoint (aData.y()), + theBVH->MaxPoint (aData.y()), + aMetricLft); + if (this->Stop()) + return aNbAccepted; + + // Test the right branch + MetricType aMetricRgh; + Standard_Boolean isGoodRgh = !RejectNode (theBVH->MinPoint (aData.z()), + theBVH->MaxPoint (aData.z()), + aMetricRgh); + if (this->Stop()) + return aNbAccepted; + + if (isGoodLft && isGoodRgh) + { + // Chose the branch with the best metric to be processed next, + // put the other branch in the stack + if (this->IsMetricBetter (aMetricLft, aMetricRgh)) + { + aNode = BVH_NodeInStack (aData.y(), aMetricLft); + aStack[++aHead] = BVH_NodeInStack (aData.z(), aMetricRgh); + } + else + { + aNode = BVH_NodeInStack (aData.z(), aMetricRgh); + aStack[++aHead] = BVH_NodeInStack (aData.y(), aMetricLft); + } + } + else if (isGoodLft || isGoodRgh) + { + aNode = isGoodLft ? + BVH_NodeInStack (aData.y(), aMetricLft) : + BVH_NodeInStack (aData.z(), aMetricRgh); + } + } + else + { + // Both children will be accepted + // Take one for processing, put the other into stack + aNode = BVH_NodeInStack (aData.y(), aNode.Metric); + aStack[++aHead] = BVH_NodeInStack (aData.z(), aNode.Metric); + } + } + else + { + // Leaf node - apply the leaf node operation to each element + for (Standard_Integer iN = aData.y(); iN <= aData.z(); ++iN) + { + if (Accept (iN, aNode.Metric)) + ++aNbAccepted; + + if (this->Stop()) + return aNbAccepted; + } + } + + if (aNode.NodeID == aPrevNode.NodeID) + { + if (aHead < 0) + return aNbAccepted; + + // Remove the nodes with bad metric from the stack + aNode = aStack[aHead--]; + while (this->RejectMetric (aNode.Metric)) + { + if (aHead < 0) + return aNbAccepted; + aNode = aStack[aHead--]; + } + } + + aPrevNode = aNode; + } +} + +namespace +{ + //! Auxiliary structure for keeping the pair of nodes to process + template struct BVH_PairNodesInStack + { + //! Constructor + BVH_PairNodesInStack (const Standard_Integer theNodeID1 = 0, + const Standard_Integer theNodeID2 = 0, + const MetricType& theMetric = MetricType()) + : NodeID1 (theNodeID1), NodeID2 (theNodeID2), Metric (theMetric) + {} + + // Fields + Standard_Integer NodeID1; //!< Id of the node in the first BVH tree + Standard_Integer NodeID2; //!< Id of the node in the second BVH tree + MetricType Metric; //!< Metric computed for the pair of nodes + }; +} + +// ======================================================================= +// function : BVH_PairTraverse::Select +// purpose : +// ======================================================================= +template +Standard_Integer BVH_PairTraverse::Select + (const opencascade::handle>& theBVH1, + const opencascade::handle>& theBVH2) +{ + if (theBVH1.IsNull() || theBVH2.IsNull()) + return 0; + + const BVH_Array4i& aBVHNodes1 = theBVH1->NodeInfoBuffer(); + const BVH_Array4i& aBVHNodes2 = theBVH2->NodeInfoBuffer(); + if (aBVHNodes1.empty() || aBVHNodes2.empty()) + return 0; + + // On each iteration we can add max four new pairs of nodes to process. + // One of these pairs goes directly to processing, while others + // are put in the stack. So the max number of pairs in the stack is + // the max tree depth multiplied by 3. + const Standard_Integer aMaxNbPairsInStack = 3 * BVH_Constants_MaxTreeDepth; + + // Stack of pairs of nodes to process + BVH_PairNodesInStack aStack[aMaxNbPairsInStack]; + + // Currently processed pair, starting with the root nodes + BVH_PairNodesInStack aNode (0, 0); + // Previously processed pair + BVH_PairNodesInStack aPrevNode = aNode; + // End of the stack + Standard_Integer aHead = -1; + // Counter for accepted elements + Standard_Integer aNbAccepted = 0; + + for (;;) + { + const BVH_Vec4i& aData1 = aBVHNodes1[aNode.NodeID1]; + const BVH_Vec4i& aData2 = aBVHNodes2[aNode.NodeID2]; + + if (aData1.x() != 0 && aData2.x() != 0) + { + // Outer/Outer + for (Standard_Integer iN1 = aData1.y(); iN1 <= aData1.z(); ++iN1) + { + for (Standard_Integer iN2 = aData2.y(); iN2 <= aData2.z(); ++iN2) + { + if (Accept (iN1, iN2)) + ++aNbAccepted; + + if (this->Stop()) + return aNbAccepted; + } + } + } + else + { + BVH_PairNodesInStack aPairs[4]; + Standard_Integer aNbPairs = 0; + + if (aData1.x() == 0 && aData2.x() == 0) + { + // Inner/Inner + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.y(), aData2.y()); + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.y(), aData2.z()); + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.z(), aData2.y()); + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.z(), aData2.z()); + } + else if (aData1.x() == 0) + { + // Inner/Outer + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.y(), aNode.NodeID2); + aPairs[aNbPairs++] = BVH_PairNodesInStack (aData1.z(), aNode.NodeID2); + } + else if (aData2.x() == 0) + { + // Outer/Inner + aPairs[aNbPairs++] = BVH_PairNodesInStack (aNode.NodeID1, aData2.y()); + aPairs[aNbPairs++] = BVH_PairNodesInStack (aNode.NodeID1, aData2.z()); + } + + BVH_PairNodesInStack aKeptPairs[4]; + Standard_Integer aNbKept = 0; + // Compute metrics for the nodes + for (Standard_Integer iPair = 0; iPair < aNbPairs; ++iPair) + { + const Standard_Boolean isPairRejected = + RejectNode (theBVH1->MinPoint (aPairs[iPair].NodeID1), theBVH1->MaxPoint (aPairs[iPair].NodeID1), + theBVH2->MinPoint (aPairs[iPair].NodeID2), theBVH2->MaxPoint (aPairs[iPair].NodeID2), + aPairs[iPair].Metric); + if (!isPairRejected) + { + // Put the item into the sorted array of pairs + Standard_Integer iSort = aNbKept; + while (iSort > 0 && this->IsMetricBetter (aPairs[iPair].Metric, aKeptPairs[iSort - 1].Metric)) + { + aKeptPairs[iSort] = aKeptPairs[iSort - 1]; + --iSort; + } + aKeptPairs[iSort] = aPairs[iPair]; + aNbKept++; + } + } + + if (aNbKept > 0) + { + aNode = aKeptPairs[0]; + + for (Standard_Integer iPair = 1; iPair < aNbKept; ++iPair) + { + aStack[++aHead] = aKeptPairs[iPair]; + } + } + } + + if (aNode.NodeID1 == aPrevNode.NodeID1 && + aNode.NodeID2 == aPrevNode.NodeID2) + { + // No pairs to add + if (aHead < 0) + return aNbAccepted; + + // Remove the pairs of nodes with bad metric from the stack + aNode = aStack[aHead--]; + while (this->RejectMetric (aNode.Metric)) + { + if (aHead < 0) + return aNbAccepted; + aNode = aStack[aHead--]; + } + } + + aPrevNode = aNode; + } +} diff --git a/src/BVH/FILES b/src/BVH/FILES index a563d1f113..90535a2098 100644 --- a/src/BVH/FILES +++ b/src/BVH/FILES @@ -1,18 +1,22 @@ BVH.cxx BVH_BinnedBuilder.hxx BVH_Box.hxx +BVH_BoxSet.hxx BVH_Builder.hxx BVH_BuildQueue.hxx BVH_BuildQueue.cxx BVH_BuildThread.hxx BVH_BuildThread.cxx BVH_Constants.hxx +BVH_Distance.hxx BVH_DistanceField.hxx BVH_DistanceField.lxx BVH_Geometry.hxx +BVH_IndexedBoxSet.hxx BVH_LinearBuilder.hxx BVH_Object.hxx BVH_ObjectSet.hxx +BVH_PairDistance.hxx BVH_PrimitiveSet.hxx BVH_PrimitiveSet3d.hxx BVH_Properties.cxx @@ -24,6 +28,9 @@ BVH_QuickSorter.hxx BVH_RadixSorter.hxx BVH_SpatialMedianBuilder.hxx BVH_SweepPlaneBuilder.hxx +BVH_Tools.hxx +BVH_Traverse.hxx +BVH_Traverse.lxx BVH_Tree.hxx BVH_BinaryTree.hxx BVH_QuadTree.hxx diff --git a/src/Bnd/Bnd_Tools.hxx b/src/Bnd/Bnd_Tools.hxx new file mode 100644 index 0000000000..cf108622e7 --- /dev/null +++ b/src/Bnd/Bnd_Tools.hxx @@ -0,0 +1,47 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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 _Bnd_Tools_Header +#define _Bnd_Tools_Header + +#include +#include +#include + +//! Defines a set of static methods operating with bounding boxes +class Bnd_Tools +{ +public: //! @name Bnd_Box to BVH_Box conversion + + //! Converts the given Bnd_Box2d to BVH_Box + static BVH_Box Bnd2BVH (const Bnd_Box2d& theBox) + { + Standard_Real aXMin, aYMin, aXMax, aYMax; + theBox.Get (aXMin, aYMin, aXMax, aYMax); + return BVH_Box (BVH_Vec2d (aXMin, aYMin), + BVH_Vec2d (aXMax, aYMax)); + } + + //! Converts the given Bnd_Box to BVH_Box + static BVH_Box Bnd2BVH (const Bnd_Box& theBox) + { + Standard_Real aXMin, aYMin, aZMin, aXMax, aYMax, aZMax; + theBox.Get (aXMin, aYMin, aZMin, aXMax, aYMax, aZMax); + return BVH_Box (BVH_Vec3d (aXMin, aYMin, aZMin), + BVH_Vec3d (aXMax, aYMax, aZMax)); + } +}; + +#endif // _Bnd_Tools_Header diff --git a/src/Bnd/FILES b/src/Bnd/FILES index 1e88fce03d..03743cff52 100644 --- a/src/Bnd/FILES +++ b/src/Bnd/FILES @@ -32,3 +32,4 @@ Bnd_SeqOfBox.hxx Bnd_Sphere.cxx Bnd_Sphere.hxx Bnd_Sphere.lxx +Bnd_Tools.hxx diff --git a/src/QABugs/FILES b/src/QABugs/FILES index fd015d2532..e63687d16d 100644 --- a/src/QABugs/FILES +++ b/src/QABugs/FILES @@ -19,5 +19,6 @@ QABugs_17.cxx QABugs_18.cxx QABugs_19.cxx QABugs_20.cxx +QABugs_BVH.cxx QABugs_PresentableObject.cxx QABugs_PresentableObject.hxx diff --git a/src/QABugs/QABugs.cxx b/src/QABugs/QABugs.cxx index 1a9cd066bb..b53dfc9f64 100644 --- a/src/QABugs/QABugs.cxx +++ b/src/QABugs/QABugs.cxx @@ -35,6 +35,7 @@ void QABugs::Commands(Draw_Interpretor& theCommands) { QABugs::Commands_18(theCommands); QABugs::Commands_19(theCommands); QABugs::Commands_20(theCommands); + QABugs::Commands_BVH(theCommands); return; } diff --git a/src/QABugs/QABugs.hxx b/src/QABugs/QABugs.hxx index fbe908642f..a04340e6aa 100644 --- a/src/QABugs/QABugs.hxx +++ b/src/QABugs/QABugs.hxx @@ -73,6 +73,7 @@ public: Standard_EXPORT static void Commands_20 (Draw_Interpretor& DI); + Standard_EXPORT static void Commands_BVH (Draw_Interpretor& DI); protected: diff --git a/src/QABugs/QABugs_BVH.cxx b/src/QABugs/QABugs_BVH.cxx new file mode 100644 index 0000000000..a2c96aadaf --- /dev/null +++ b/src/QABugs/QABugs_BVH.cxx @@ -0,0 +1,854 @@ +// Created by: Eugeny MALTCHIKOV +// Created on: 2019-04-17 +// Copyright (c) 2019 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. + +#include + +#include +#include + +#include + +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include + +#include +#include + +#include +#include +#include +#include + +#include + +//======================================================================= +//function : ShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class ShapeSelector : + public BVH_Traverse , Standard_Boolean> +{ +public: + //! Constructor + ShapeSelector() {} + + //! Sets the Box for selection + void SetBox (const Bnd_Box& theBox) + { + myBox = Bnd_Tools::Bnd2BVH (theBox); + } + + //! Returns the selected shapes + const NCollection_List& Shapes () const { return myShapes; } + +public: + + //! Defines the rules for node rejection by bounding box + virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin, + const BVH_Vec3d& theCornerMax, + Standard_Boolean& theIsInside) const Standard_OVERRIDE + { + Standard_Boolean hasOverlap; + theIsInside = myBox.Contains (theCornerMin, theCornerMax, hasOverlap); + return !hasOverlap; + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean AcceptMetric (const Standard_Boolean& theIsInside) const Standard_OVERRIDE + { + return theIsInside; + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const Standard_Integer theIndex, + const Standard_Boolean& theIsInside) Standard_OVERRIDE + { + if (theIsInside || !myBox.IsOut (myBVHSet->Box (theIndex))) + { + myShapes.Append (myBVHSet->Element (theIndex)); + return Standard_True; + } + return Standard_False; + } + +protected: + + BVH_Box myBox; //!< Selection box + NCollection_List myShapes; //!< Selected shapes +}; + +//======================================================================= +//function : ShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class ShapeSelectorVoid : + public BVH_Traverse +{ +public: + //! Constructor + ShapeSelectorVoid() {} + + //! Sets the Box for selection + void SetBox (const Bnd_Box& theBox) + { + myBox = Bnd_Tools::Bnd2BVH (theBox); + } + + //! Returns the selected shapes + const NCollection_List& Shapes () const { return myShapes; } + +public: + + //! Sets the Box Set + void SetShapeBoxSet (const opencascade::handle>& theBoxSet) + { + myBoxSet = theBoxSet; + } + +public: + + //! Defines the rules for node rejection by bounding box + virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin, + const BVH_Vec3d& theCornerMax, + Standard_Boolean& theIsInside) const Standard_OVERRIDE + { + Standard_Boolean hasOverlap; + theIsInside = myBox.Contains (theCornerMin, theCornerMax, hasOverlap); + return !hasOverlap; + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean AcceptMetric (const Standard_Boolean& theIsInside) const Standard_OVERRIDE + { + return theIsInside; + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const Standard_Integer theIndex, + const Standard_Boolean& theIsInside) Standard_OVERRIDE + { + if (theIsInside || !myBox.IsOut (myBoxSet->Box (theIndex))) + { + myShapes.Append (myBoxSet->Element (theIndex)); + return Standard_True; + } + return Standard_False; + } + +protected: + + opencascade::handle> myBoxSet; //!< ShapeBoxSet + BVH_Box myBox; //!< Selection box + NCollection_List myShapes; //!< Selected shapes +}; + +//======================================================================= +//function : QABVH_ShapeSelect +//purpose : Test the work of BVH on the simple example of shapes selection +//======================================================================= +static Standard_Integer QABVH_ShapeSelect (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc < 4) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + // Get the shape to add its sub-shapes into BVH + TopoDS_Shape aShape = DBRep::Get (theArgv [2]); + if (aShape.IsNull()) + { + std::cout << theArgv[2] << " does not exist" << std::endl; + return 1; + } + + // Get the shape to get the Box for selection + TopoDS_Shape aBShape = DBRep::Get (theArgv [3]); + if (aBShape.IsNull()) + { + std::cout << theArgv[3] << " does not exist" << std::endl; + return 1; + } + + // Which selector to use + Standard_Boolean useVoidSelector = Standard_False; + if (theArgc > 4) + useVoidSelector = !strcmp (theArgv[4], "-void"); + + // Define BVH Builder + opencascade::handle > aLBuilder = + new BVH_LinearBuilder (); + + // Create the ShapeSet + opencascade::handle > aShapeBoxSet = + new BVH_BoxSet (aLBuilder); + + // Add elements into BVH + + // Map the shape + TopTools_IndexedMapOfShape aMapShapes; + TopExp::MapShapes (aShape, TopAbs_VERTEX, aMapShapes); + TopExp::MapShapes (aShape, TopAbs_EDGE, aMapShapes); + TopExp::MapShapes (aShape, TopAbs_FACE, aMapShapes); + + for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS) + { + const TopoDS_Shape& aS = aMapShapes(iS); + + Bnd_Box aSBox; + BRepBndLib::Add (aS, aSBox); + + aShapeBoxSet->Add (aS, Bnd_Tools::Bnd2BVH (aSBox)); + } + + // Build BVH + aShapeBoxSet->Build(); + + TopTools_ListOfShape aSelectedShapes; + + // Prepare a Box for selection + Bnd_Box aSelectionBox; + BRepBndLib::Add (aBShape, aSelectionBox); + + // Perform selection + if (!useVoidSelector) + { + ShapeSelector aSelector; + aSelector.SetBox (aSelectionBox); + aSelector.SetBVHSet (aShapeBoxSet.get()); + aSelector.Select(); + aSelectedShapes = aSelector.Shapes(); + } + else + { + ShapeSelectorVoid aSelector; + aSelector.SetBox (aSelectionBox); + aSelector.SetShapeBoxSet (aShapeBoxSet); + aSelector.Select (aShapeBoxSet->BVH()); + aSelectedShapes = aSelector.Shapes(); + } + + // Draw the selected shapes + TopoDS_Compound aResult; + BRep_Builder().MakeCompound (aResult); + + for (TopTools_ListOfShape::Iterator it (aSelectedShapes); it.More(); it.Next()) + BRep_Builder().Add (aResult, it.Value()); + + DBRep::Set (theArgv[1], aResult); + return 0; +} + +//======================================================================= +//function : PairShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class PairShapesSelector : + public BVH_PairTraverse > +{ +public: + //! Constructor + PairShapesSelector() {} + + //! Returns the selected pairs of shapes + const NCollection_List >& Pairs () const { return myPairs; } + +public: + + //! Defines the rules for node rejection + virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin1, + const BVH_Vec3d& theCornerMax1, + const BVH_Vec3d& theCornerMin2, + const BVH_Vec3d& theCornerMax2, + Standard_Real&) const Standard_OVERRIDE + { + return BVH_Box (theCornerMin1, theCornerMax1).IsOut ( + BVH_Box (theCornerMin2, theCornerMax2)); + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + BVH_Box aBox1 = myBVHSet1->Box (theIndex1); + BVH_Box aBox2 = myBVHSet2->Box (theIndex2); + if (!aBox1.IsOut (aBox2)) + { + myPairs.Append (std::pair (myBVHSet1->Element (theIndex1), + myBVHSet2->Element (theIndex2))); + return Standard_True; + } + return Standard_False; + } + +protected: + + NCollection_List > myPairs; //!< Selected pairs +}; + +//======================================================================= +//function : PairShapeSelector +//purpose : Implement the simplest shape's selector +//======================================================================= +class PairShapesSelectorVoid : + public BVH_PairTraverse +{ +public: + //! Constructor + PairShapesSelectorVoid() {} + + //! Returns the selected pairs of shapes + const NCollection_List >& Pairs () const { return myPairs; } + +public: + + //! Sets the sets to access the elements + void SetShapeBoxSets (const opencascade::handle>& theSBSet1, + const opencascade::handle>& theSBSet2) + { + mySBSet1 = theSBSet1; + mySBSet2 = theSBSet2; + } + +public: + + //! Defines the rules for node rejection + virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin1, + const BVH_Vec3d& theCornerMax1, + const BVH_Vec3d& theCornerMin2, + const BVH_Vec3d& theCornerMax2, + Standard_Real&) const Standard_OVERRIDE + { + return BVH_Box (theCornerMin1, theCornerMax1).IsOut ( + BVH_Box (theCornerMin2, theCornerMax2)); + } + + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + BVH_Box aBox1 = mySBSet1->Box (theIndex1); + BVH_Box aBox2 = mySBSet2->Box (theIndex2); + if (!aBox1.IsOut (aBox2)) + { + myPairs.Append (std::pair (mySBSet1->Element (theIndex1), + mySBSet2->Element (theIndex2))); + return Standard_True; + } + return Standard_False; + } + +protected: + opencascade::handle> mySBSet1; //!< First ShapeBoxSet + opencascade::handle> mySBSet2; //!< Second ShapeBoxSet + NCollection_List > myPairs; //!< Selected pairs +}; + +//======================================================================= +//function : QABVH_PairSelect +//purpose : Test the work of BVH on the simple example of pairs of shapes selection +//======================================================================= +static Standard_Integer QABVH_PairSelect (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc < 4) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + TopoDS_Shape aShape[2]; + // Get the first shape + aShape[0] = DBRep::Get (theArgv [2]); + if (aShape[0].IsNull()) + { + std::cout << theArgv[2] << " does not exist" << std::endl; + return 1; + } + + // Get the second shape + aShape[1] = DBRep::Get (theArgv [3]); + if (aShape[1].IsNull()) + { + std::cout << theArgv[3] << " does not exist" << std::endl; + return 1; + } + + // Which selector to use + Standard_Boolean useVoidSelector = Standard_False; + if (theArgc > 4) + useVoidSelector = !strcmp (theArgv[4], "-void"); + + // Define BVH Builder + opencascade::handle > aLBuilder = + new BVH_LinearBuilder (); + + // Create the ShapeSet + opencascade::handle > aShapeBoxSet[2]; + + for (Standard_Integer i = 0; i < 2; ++i) + { + aShapeBoxSet[i] = new BVH_BoxSet (aLBuilder); + // Add elements into set + TopTools_IndexedMapOfShape aMapShapes; + TopExp::MapShapes (aShape[i], TopAbs_VERTEX, aMapShapes); + TopExp::MapShapes (aShape[i], TopAbs_EDGE, aMapShapes); + TopExp::MapShapes (aShape[i], TopAbs_FACE, aMapShapes); + + for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS) + { + const TopoDS_Shape& aS = aMapShapes(iS); + + Bnd_Box aSBox; + BRepBndLib::Add (aS, aSBox); + + aShapeBoxSet[i]->Add (aS, Bnd_Tools::Bnd2BVH (aSBox)); + } + // Build BVH + aShapeBoxSet[i]->Build(); + } + + NCollection_List > aPairs; + if (!useVoidSelector) + { + // Initialize selector + PairShapesSelector aSelector; + // Select the elements + aSelector.SetBVHSets (aShapeBoxSet[0].get(), aShapeBoxSet[1].get()); + aSelector.Select(); + aPairs = aSelector.Pairs(); + } + else + { + // Initialize selector + PairShapesSelectorVoid aSelector; + // Select the elements + aSelector.SetShapeBoxSets (aShapeBoxSet[0], aShapeBoxSet[1]); + aSelector.Select (aShapeBoxSet[0]->BVH(), aShapeBoxSet[1]->BVH()); + aPairs = aSelector.Pairs(); + } + + // Draw the selected shapes + TopoDS_Compound aResult; + BRep_Builder().MakeCompound (aResult); + + for (NCollection_List >::Iterator it (aPairs); it.More(); it.Next()) + { + TopoDS_Compound aPair; + BRep_Builder().MakeCompound (aPair); + + BRep_Builder().Add (aPair, it.Value().first); + BRep_Builder().Add (aPair, it.Value().second); + + BRep_Builder().Add (aResult, aPair); + } + + DBRep::Set (theArgv[1], aResult); + return 0; +} + + +//======================================================================= +//function : Triangle +//purpose : Auxiliary structure to keep the nodes of the triangle +//======================================================================= +struct Triangle +{ + Triangle() {} + Triangle(const BVH_Vec3d& theP1, + const BVH_Vec3d& theP2, + const BVH_Vec3d& theP3) + : _Node1 (theP1), _Node2 (theP2), _Node3 (theP3) + {} + + BVH_Vec3d _Node1; + BVH_Vec3d _Node2; + BVH_Vec3d _Node3; +}; + +//======================================================================= +//function : TriangleTriangleSqDistance +//purpose : Computes the Triangle-Triangle square distance +//======================================================================= +static Standard_Real TriangleTriangleSqDistance (const BVH_Vec3d& theNode11, + const BVH_Vec3d& theNode12, + const BVH_Vec3d& theNode13, + const BVH_Vec3d& theNode21, + const BVH_Vec3d& theNode22, + const BVH_Vec3d& theNode23) +{ + Standard_Real aDist, aMinDist = RealLast(); + + BVH_Vec3d aNodes[2][3] = { { theNode11, theNode12, theNode13 }, + { theNode21, theNode22, theNode23 } }; + + const Standard_Integer aNbSeg = 100; // number of segments on edge + for (Standard_Integer iT = 0; iT < 2; ++iT) + { + // projecting points of one triangle on the opposite triangle + for (Standard_Integer iP = 0; iP < 3; ++iP) + { + aDist = + BVH_Tools::PointTriangleSquareDistance (aNodes[iT][iP], + aNodes[(iT + 1) % 2][0], + aNodes[(iT + 1) % 2][1], + aNodes[(iT + 1) % 2][2]); + if (aDist < aMinDist) + { + aMinDist = aDist; + if (aMinDist == 0) + return aMinDist; + } + } + + // projecting edges on the opposite triangle + std::pair anEdges[3] = + { std::pair (aNodes[iT][0], aNodes[iT][1]), + std::pair (aNodes[iT][1], aNodes[iT][2]), + std::pair (aNodes[iT][2], aNodes[iT][0]) }; + + for (Standard_Integer iE = 0; iE < 3; ++iE) + { + const BVH_Vec3d& aPFirst = anEdges[iE].first, aPLast = anEdges[iE].second; + BVH_Vec3d anEdge = (aPLast - aPFirst); + Standard_Real aLength = anEdge.Modulus(); + if (aLength < Precision::Confusion()) + continue; + anEdge /= aLength; + + Standard_Real aDelta = aLength / aNbSeg; + + for (Standard_Integer iP = 1; iP < aNbSeg; ++iP) + { + BVH_Vec3d aPE = aPFirst + anEdge.Multiplied (iP * aDelta); + aDist = + BVH_Tools::PointTriangleSquareDistance (aPE, + aNodes[(iT + 1) % 2][0], + aNodes[(iT + 1) % 2][1], + aNodes[(iT + 1) % 2][2]); + if (aDist < aMinDist) + { + aMinDist = aDist; + if (aMinDist == 0) + return aMinDist; + } + } + } + } + return aMinDist; +} + +//======================================================================= +//function : MeshMeshDistance +//purpose : Class to compute the distance between two meshes +//======================================================================= +class MeshMeshDistance : public BVH_PairDistance> +{ +public: + //! Constructor + MeshMeshDistance() {} + +public: + //! Defines the rules for leaf acceptance + virtual Standard_Boolean Accept (const Standard_Integer theIndex1, + const Standard_Integer theIndex2) Standard_OVERRIDE + { + const Triangle& aTri1 = myBVHSet1->Element (theIndex1); + const Triangle& aTri2 = myBVHSet2->Element (theIndex2); + + Standard_Real aDistance = TriangleTriangleSqDistance (aTri1._Node1, aTri1._Node2, aTri1._Node3, + aTri2._Node1, aTri2._Node2, aTri2._Node3); + if (aDistance < myDistance) + { + myDistance = aDistance; + return Standard_True; + } + return Standard_False; + } +}; + +//======================================================================= +//function : QABVH_PairDistance +//purpose : Computes the distance between two meshes of the given shapes +//======================================================================= +static Standard_Integer QABVH_PairDistance (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc != 3) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + TopoDS_Shape aShape[2]; + // Get the first shape + aShape[0] = DBRep::Get (theArgv [1]); + if (aShape[0].IsNull()) + { + std::cout << theArgv[1] << " does not exist" << std::endl; + return 1; + } + + // Get the second shape + aShape[1] = DBRep::Get (theArgv [2]); + if (aShape[1].IsNull()) + { + std::cout << theArgv[2] << " does not exist" << std::endl; + return 1; + } + + // Define BVH Builder + opencascade::handle > aLBuilder = + new BVH_LinearBuilder (); + + // Create the ShapeSet + opencascade::handle > aTriangleBoxSet[2]; + + for (Standard_Integer i = 0; i < 2; ++i) + { + aTriangleBoxSet[i] = new BVH_BoxSet (aLBuilder); + + TopTools_IndexedMapOfShape aMapShapes; + TopExp::MapShapes (aShape[i], TopAbs_FACE, aMapShapes); + + for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS) + { + const TopoDS_Face& aF = TopoDS::Face (aMapShapes(iS)); + TopLoc_Location aLoc; + const Handle(Poly_Triangulation)& aTriangulation = BRep_Tool::Triangulation(aF, aLoc); + + const TColgp_Array1OfPnt& aNodes = aTriangulation->Nodes(); + const Poly_Array1OfTriangle& aTriangles = aTriangulation->Triangles(); + + const int aNbTriangles = aTriangles.Length(); + for (int iT = 1; iT <= aNbTriangles; ++iT) + { + const Poly_Triangle& aTriangle = aTriangles (iT); + // Nodes indices + Standard_Integer id1, id2, id3; + aTriangle.Get (id1, id2, id3); + + const gp_Pnt& aP1 = aNodes(id1).Transformed(aLoc.Transformation()); + const gp_Pnt& aP2 = aNodes(id2).Transformed(aLoc.Transformation()); + const gp_Pnt& aP3 = aNodes(id3).Transformed(aLoc.Transformation()); + + BVH_Vec3d aBVHP1 (aP1.X(), aP1.Y(), aP1.Z()); + BVH_Vec3d aBVHP2 (aP2.X(), aP2.Y(), aP2.Z()); + BVH_Vec3d aBVHP3 (aP3.X(), aP3.Y(), aP3.Z()); + + BVH_Box aBox; + aBox.Add (aBVHP1); + aBox.Add (aBVHP2); + aBox.Add (aBVHP3); + + aTriangleBoxSet[i]->Add (Triangle (aBVHP1, aBVHP2, aBVHP3), aBox); + } + } + // Build BVH + aTriangleBoxSet[i]->Build(); + } + + // Initialize selector + MeshMeshDistance aDistTool; + // Select the elements + aDistTool.SetBVHSets (aTriangleBoxSet[0].get(), aTriangleBoxSet[1].get()); + Standard_Real aSqDist = aDistTool.ComputeDistance(); + if (!aDistTool.IsDone()) + std::cout << "Not Done" << std::endl; + else + theDI << "Distance " << sqrt (aSqDist) << "\n"; + + return 0; +} + +//======================================================================= +//function : QABVH_TriangleSet +//purpose : Auxiliary class to contain triangulation of a face +//======================================================================= +class QABVH_TriangleSet : public BVH_Triangulation +{ +public: + QABVH_TriangleSet() + : BVH_Triangulation() + {} + +public: + + //! Creates the triangulation from a face + void Build (const TopoDS_Face& theFace) + { + TopLoc_Location aLoc; + const Handle(Poly_Triangulation)& aTriangulation = BRep_Tool::Triangulation(theFace, aLoc); + + const TColgp_Array1OfPnt& aNodes = aTriangulation->Nodes(); + const Poly_Array1OfTriangle& aTriangles = aTriangulation->Triangles(); + + const int aNbTriangles = aTriangles.Length(); + for (int iT = 1; iT <= aNbTriangles; ++iT) + { + const Poly_Triangle& aTriangle = aTriangles (iT); + // Nodes indices + Standard_Integer id1, id2, id3; + aTriangle.Get (id1, id2, id3); + + const gp_Pnt& aP1 = aNodes(id1).Transformed(aLoc.Transformation()); + const gp_Pnt& aP2 = aNodes(id2).Transformed(aLoc.Transformation()); + const gp_Pnt& aP3 = aNodes(id3).Transformed(aLoc.Transformation()); + + BVH_Vec3d aBVHP1 (aP1.X(), aP1.Y(), aP1.Z()); + BVH_Vec3d aBVHP2 (aP2.X(), aP2.Y(), aP2.Z()); + BVH_Vec3d aBVHP3 (aP3.X(), aP3.Y(), aP3.Z()); + + Standard_Integer id = static_cast(Vertices.size()) - 1; + Vertices.push_back (aBVHP1); + Vertices.push_back (aBVHP2); + Vertices.push_back (aBVHP3); + + Elements.push_back (BVH_Vec4i (id + 1, id + 2, id + 3, iT)); + } + + MarkDirty(); + BVH(); + } +}; + +//======================================================================= +//function : QABVH_Geometry +//purpose : Auxiliary class to contain triangulation of a shape +//======================================================================= +class QABVH_Geometry : public BVH_Geometry +{ +public: + QABVH_Geometry() + : BVH_Geometry() + {} + +public: + + //! Creates the triangulation from a face + void Build (const TopoDS_Shape& theShape) + { + TopExp_Explorer anExp (theShape, TopAbs_FACE); + for (; anExp.More(); anExp.Next()) + { + const TopoDS_Face& aF = TopoDS::Face (anExp.Current()); + Handle(QABVH_TriangleSet) aTriSet = new QABVH_TriangleSet(); + aTriSet->Build (aF); + myObjects.Append (aTriSet); + } + + MarkDirty(); + BVH(); + } +}; + +//======================================================================= +//function : QABVH_DistanceField +//purpose : Computes the distance field on a given shape +//======================================================================= +static Standard_Integer QABVH_DistanceField (Draw_Interpretor& theDI, + Standard_Integer theArgc, + const char** theArgv) +{ + if (theArgc < 2) + { + theDI.PrintHelp (theArgv[0]); + return 1; + } + + TopoDS_Shape aShape; + // Get the first shape + aShape = DBRep::Get (theArgv [1]); + if (aShape.IsNull()) + { + std::cout << theArgv[1] << " does not exist" << std::endl; + return 1; + } + + Standard_Integer aNbDim = 10; + if (theArgc > 2) + { + aNbDim = Draw::Atoi (theArgv[2]); + } + + QABVH_Geometry aGeometry; + aGeometry.Build(aShape); + + BVH_DistanceField aDField(aNbDim, Standard_True); + aDField.Build (aGeometry); + + for (Standard_Integer iX = 0; iX < aDField.DimensionX(); ++iX) + { + for (Standard_Integer iY = 0; iY < aDField.DimensionY(); ++iY) + { + for (Standard_Integer iZ = 0; iZ < aDField.DimensionZ(); ++iZ) + { + Standard_Real aDist = aDField.Voxel (iX, iY, iZ); + std::cout << "(" << iX << ", " << iY << ", " << iZ << "): " << aDist << std::endl; + } + } + } + return 0; +} + +//======================================================================= +//function : Commands_BVH +//purpose : BVH commands +//======================================================================= +void QABugs::Commands_BVH (Draw_Interpretor& theCommands) +{ + const char *group = "QABugs"; + + theCommands.Add ("QABVH_ShapeSelect", + "Tests the work of BHV_BoxSet algorithm on the simple example of selection of shapes which boxes interfere with given box.\n" + "Usage: QABVH_ShapeSelect result shape box (defined as a solid) [-void]\n" + "\tResult should contain all sub-shapes of the shape interfering with given box", + __FILE__, QABVH_ShapeSelect, group); + + theCommands.Add ("QABVH_PairSelect", + "Tests the work of BHV_BoxSet algorithm on the simple example of selection of pairs of shapes with interfering bounding boxes.\n" + "Usage: QABVH_PairSelect result shape1 shape2 [-void]\n" + "\tResult should contain all interfering pairs (compound of pairs)", + __FILE__, QABVH_PairSelect, group); + + theCommands.Add ("QABVH_PairDistance", + "Computes the distance between the meshes of the given shapes.\n" + "Usage: QABVH_PairDistance shape1 shape2\n" + "\tThe given shapes should contain triangulation\n", + __FILE__, QABVH_PairDistance, group); + + theCommands.Add ("QABVH_DistanceField", + "Computes the distance field for a shape with triangulation\n" + "Usage: QABVH_DistanceField shape [nbSplit]\n", + __FILE__, QABVH_DistanceField, group); + +} diff --git a/tests/lowalgos/bvh/bug30655_1 b/tests/lowalgos/bvh/bug30655_1 new file mode 100644 index 0000000000..bcf4760e2a --- /dev/null +++ b/tests/lowalgos/bvh/bug30655_1 @@ -0,0 +1,58 @@ +puts "=======" +puts "0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree" +puts "=======" +puts "" + +pload QAcommands + +box b 10 10 10 + +# select elements interfering with each vertex (must be one vertex (itself), three edges and three faces - 7 in total) +foreach v [explode b v] { + QABVH_ShapeSelect r_$v b $v + QABVH_ShapeSelect rv_$v b $v -void + + if { [llength [explode r_$v]] != 7} { + puts "Error: incorrect selection" + } + + checknbshapes rv_$v -ref [nbshapes r_$v] + checkprops rv_$v -equal r_$v +} + +# select elements interfering with each edge (must be two vertices, five edges and and four faces - 11 in total) +foreach e [explode b e] { + QABVH_ShapeSelect r_$e b $e + QABVH_ShapeSelect rv_$e b $e -void + + if { [llength [explode r_$e]] != 11} { + puts "Error: incorrect selection" + } + + checknbshapes rv_$e -ref [nbshapes r_$e] + checkprops rv_$e -equal r_$e +} + +# select elements interfering with each face (must be ffour vertices, eight edges and and five faces - 17 in total) +foreach f [explode b f] { + QABVH_ShapeSelect r_$f b $f + QABVH_ShapeSelect rv_$f b $f -void + + if { [llength [explode r_$f]] != 17} { + puts "Error: incorrect selection" + } + + checknbshapes rv_$f -ref [nbshapes r_$f] + checkprops rv_$f -equal r_$f +} + +# intersect the box with itself - select all interfering pairs (8 * 7 + 12 * 11 + 6 * 17 = 290) +QABVH_PairSelect r b b +QABVH_PairSelect rv b b -void + +if { [llength [explode r]] != 290} { + puts "Error: incorrect selection" +} + +checknbshapes rv -ref [nbshapes r] +checkprops rv -equal r diff --git a/tests/lowalgos/bvh/bug30655_2 b/tests/lowalgos/bvh/bug30655_2 new file mode 100644 index 0000000000..7f057e4e8b --- /dev/null +++ b/tests/lowalgos/bvh/bug30655_2 @@ -0,0 +1,16 @@ +puts "=======" +puts "0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree" +puts "=======" +puts "" + +pload QAcommands + +box b1 10 10 10 +box b2 20 0 0 10 10 10 + +incmesh b1 0.1 +incmesh b2 0.1 + +regexp {Distance ([-0-9.+eE]*)} [QABVH_PairDistance b1 b2] full dist + +checkreal "Distance" $dist 10 0 1.e-2 diff --git a/tests/lowalgos/bvh/bug30655_3 b/tests/lowalgos/bvh/bug30655_3 new file mode 100644 index 0000000000..101bd3222b --- /dev/null +++ b/tests/lowalgos/bvh/bug30655_3 @@ -0,0 +1,21 @@ +puts "=======" +puts "0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree" +puts "=======" +puts "" + +pload QAcommands + +psphere s1 100 +psphere s2 110 +ttranslate s2 150 150 150 + +incmesh s1 0.01 +incmesh s2 0.01 + +dchrono stime start +regexp {Distance ([-0-9.+eE]*)} [QABVH_PairDistance s1 s2] full dist +dchrono stime stop counter MESH_MESH_DISTANCE + +distmini d s1 s2 + +checkreal "Distance" $dist [dval d_val] 0 1.e-2 diff --git a/tests/lowalgos/bvh/bug30655_4 b/tests/lowalgos/bvh/bug30655_4 new file mode 100644 index 0000000000..054e65ccf3 --- /dev/null +++ b/tests/lowalgos/bvh/bug30655_4 @@ -0,0 +1,13 @@ +puts "=======" +puts "0030655: Modeling Data - Provide interfaces for selection of the elements from BVH tree" +puts "=======" +puts "" + +pload QAcommands + +box b 10 10 10 +incmesh b 0.1 + +# test the work of distance field +QABVH_DistanceField b 2 + diff --git a/tests/lowalgos/grids.list b/tests/lowalgos/grids.list index 398ff7c2b2..eabf01d895 100644 --- a/tests/lowalgos/grids.list +++ b/tests/lowalgos/grids.list @@ -4,4 +4,5 @@ 004 extcc 005 2dgcc 006 intss -007 classifier \ No newline at end of file +007 classifier +008 bvh -- 2.20.1