0030655: Modeling Data - Provide interfaces for selection of the elements from BVH...
authoremv <emv@opencascade.com>
Wed, 17 Apr 2019 14:29:02 +0000 (17:29 +0300)
committerbugmaster <bugmaster@opencascade.com>
Tue, 28 May 2019 16:02:22 +0000 (19:02 +0300)
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.

24 files changed:
src/BRepExtrema/BRepExtrema_OverlapTool.cxx
src/BRepExtrema/BRepExtrema_OverlapTool.hxx
src/BRepExtrema/BRepExtrema_ShapeProximity.hxx
src/BVH/BVH_Box.hxx
src/BVH/BVH_BoxSet.hxx [new file with mode: 0644]
src/BVH/BVH_Distance.hxx [new file with mode: 0644]
src/BVH/BVH_DistanceField.lxx
src/BVH/BVH_IndexedBoxSet.hxx [new file with mode: 0644]
src/BVH/BVH_PairDistance.hxx [new file with mode: 0644]
src/BVH/BVH_Tools.hxx [new file with mode: 0644]
src/BVH/BVH_Traverse.hxx [new file with mode: 0644]
src/BVH/BVH_Traverse.lxx [new file with mode: 0644]
src/BVH/FILES
src/Bnd/Bnd_Tools.hxx [new file with mode: 0644]
src/Bnd/FILES
src/QABugs/FILES
src/QABugs/QABugs.cxx
src/QABugs/QABugs.hxx
src/QABugs/QABugs_BVH.cxx [new file with mode: 0644]
tests/lowalgos/bvh/bug30655_1 [new file with mode: 0644]
tests/lowalgos/bvh/bug30655_2 [new file with mode: 0644]
tests/lowalgos/bvh/bug30655_3 [new file with mode: 0644]
tests/lowalgos/bvh/bug30655_4 [new file with mode: 0644]
tests/lowalgos/grids.list

index f2600de..8dd8252 100644 (file)
@@ -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<BVH_Tree<Standard_Real, 3> >& aBVH1 = mySet1->BVH();
-  const opencascade::handle<BVH_Tree<Standard_Real, 3> >& 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;
 }
index 4ea3ef2..08628c2 100644 (file)
 #ifndef _BRepExtrema_OverlapTool_HeaderFile
 #define _BRepExtrema_OverlapTool_HeaderFile
 
-#include <BVH_Geometry.hxx>
 #include <BRepExtrema_TriangleSet.hxx>
 #include <BRepExtrema_ElementFilter.hxx>
 #include <BRepExtrema_MapOfIntegerPackedMapOfInteger.hxx>
+#include <BVH_Traverse.hxx>
 
 //! 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 <Standard_Real, 3>
 {
 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
index 0cdb4ab..328d23d 100644 (file)
@@ -16,7 +16,6 @@
 #ifndef _BRepExtrema_ShapeProximity_HeaderFile
 #define _BRepExtrema_ShapeProximity_HeaderFile
 
-#include <BVH_Geometry.hxx>
 #include <NCollection_DataMap.hxx>
 #include <TColStd_PackedMapOfInteger.hxx>
 
index 8210aa3..920c278 100644 (file)
@@ -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<T, N>& 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<T, N>& 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 (file)
index 0000000..5aace9e
--- /dev/null
@@ -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 <BVH_PrimitiveSet.hxx>
+
+//! 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 NumType, int Dimension, class DataType = Standard_Integer>
+class BVH_BoxSet : public BVH_PrimitiveSet <NumType, Dimension>
+{
+public: //! @name Constructors
+
+  //! Empty constructor for use the default BVH_Builder
+  BVH_BoxSet()
+    : BVH_PrimitiveSet <NumType, Dimension>()
+  {
+  }
+  
+  //! Constructor for usage the custom BVH builder
+  BVH_BoxSet (const opencascade::handle <BVH_Builder <NumType, Dimension> >& theBuilder)
+    : BVH_PrimitiveSet <NumType, Dimension> (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<NumType, Dimension>& theBox)
+  {
+    myElements.push_back (theElement);
+    myBoxes.push_back (theBox);
+    BVH_Object<NumType, Dimension>::myIsDirty = Standard_True;
+  }
+
+public: //! @name BVH construction
+
+  //! BVH construction
+  void Build()
+  {
+    BVH_PrimitiveSet <NumType, Dimension>::Update();
+  }
+
+public: //! @name Clearing the elements and boxes
+
+  //! Clears the vectors of elements and boxes
+  virtual void Clear()
+  {
+    myElements.clear();
+    myBoxes.clear();
+    BVH_Object<NumType, Dimension>::myIsDirty = Standard_True;
+  }
+
+public: //! @name Necessary overrides for BVH construction
+
+  //! Make inherited method Box() visible to avoid CLang warning
+  using BVH_PrimitiveSet <NumType, Dimension>::Box;
+
+  //! Returns the bounding box with the given index.
+  virtual BVH_Box <NumType, Dimension> 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<Standard_Integer> (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 <DataType> myElements;                   //!< Elements
+  std::vector <BVH_Box <NumType, Dimension> > 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 (file)
index 0000000..286b08a
--- /dev/null
@@ -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 <BVH_Traverse.hxx>
+
+//! 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 NumType, int Dimension, class ObjectType, class BVHSetType>
+class BVH_Distance : public BVH_Traverse<NumType, Dimension, BVHSetType, NumType>
+{
+public: //! @name Constructor
+
+  //! Constructor
+  BVH_Distance()
+    : BVH_Traverse <NumType, Dimension, BVHSetType, NumType>(),
+      myDistance (std::numeric_limits<NumType>::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<NumType>(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
index 5d3e12c..5be06f3 100644 (file)
@@ -15,6 +15,7 @@
 
 #include <BVH_Triangulation.hxx>
 #include <OSD_Parallel.hxx>
+#include <BVH_Distance.hxx>
 
 // =======================================================================
 // 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<class T, int N>
-  T SquareDistanceToObject (BVH_Object<T, N>* theObject,
-    const typename VectorType<T, N>::Type& thePnt, Standard_Boolean& theIsOutside)
+  template<class T, int N, class BVHSetType>
+  class SquareDistanceToPoint : public BVH_Distance<T,N,typename VectorType<T, N>::Type, BVHSetType>
   {
-    Standard_STATIC_ASSERT (N == 3 || N == 4);
+  public:
+    typedef typename VectorType<T, N>::Type BVH_VecNt;
 
-    T aMinDistance = std::numeric_limits<T>::max();
+  public:
+    SquareDistanceToPoint()
+      : BVH_Distance<T, N, BVH_VecNt, BVHSetType>(),
+        myIsOutside (Standard_True)
+    {}
 
-    BVH_Triangulation<T, N>* aTriangulation =
-      dynamic_cast<BVH_Triangulation<T, N>*> (theObject);
+  public:
 
-    Standard_ASSERT_RETURN (aTriangulation != NULL,
-      "Error: Unsupported BVH object (non triangulation)", aMinDistance);
+    //! IsOutside
+    Standard_Boolean IsOutside() const { return myIsOutside; }
 
-    const opencascade::handle<BVH_Tree<T, N> >& 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<T, N> (this->myObject, theCMin, theCMax);
+      return theMetric > this->myDistance;
     }
 
-    std::pair<Standard_Integer, T> 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<T, N> (thePnt,
-                                                  aBVH->MinPoint (aData.y()),
-                                                  aBVH->MaxPoint (aData.y()));
-
-        const T aDistToRgh = DistanceToBox<T, N> (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<Standard_Integer, T> (
-            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<Standard_Integer, T>& 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<T, N>::Type aVertex0 = aTriangulation->Vertices[aTriangle.x()];
-          const typename VectorType<T, N>::Type aVertex1 = aTriangulation->Vertices[aTriangle.y()];
-          const typename VectorType<T, N>::Type aVertex2 = aTriangulation->Vertices[aTriangle.z()];
+    Standard_Boolean myIsOutside;
+  };
 
-          const typename VectorType<T, N>::Type aDirection =
-            DirectionToNearestPoint<T, N> (thePnt, aVertex0, aVertex1, aVertex2);
+  //=======================================================================
+  //function : PointTriangulationSquareDistance
+  //purpose  : Computes squared distance from point to BVH triangulation
+  //=======================================================================
+  template<class T, int N>
+  class PointTriangulationSquareDistance: public SquareDistanceToPoint <T,N, BVH_Triangulation<T, N>>
+  {
+  public:
+    typedef typename VectorType<T, N>::Type BVH_VecNt;
 
-          const T aDistance = BVH_DOT3 (aDirection, aDirection);
+  public:
+    //! Constructor
+    PointTriangulationSquareDistance()
+      : SquareDistanceToPoint<T, N, BVH_Triangulation<T, N>>()
+    {
+    }
 
-          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<T, N>::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<T, N>::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<T, N> (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<Standard_Integer, T>& 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<class T, int N>
-  T SquareDistanceToGeomerty (BVH_Geometry<T, N>& theGeometry,
+  T SquareDistanceToObject (BVH_Object<T, N>* theObject,
     const typename VectorType<T, N>::Type& thePnt, Standard_Boolean& theIsOutside)
   {
     Standard_STATIC_ASSERT (N == 3 || N == 4);
 
-    const BVH_Tree<T, N, BVH_BinaryTree>* aBVH = theGeometry.BVH().get();
+    T aMinDistance = std::numeric_limits<T>::max();
 
-    if (aBVH == NULL)
+    BVH_Triangulation<T, N>* aTriangulation =
+      dynamic_cast<BVH_Triangulation<T, N>*> (theObject);
+
+    Standard_ASSERT_RETURN (aTriangulation != NULL,
+      "Error: Unsupported BVH object (non triangulation)", aMinDistance);
+
+    const opencascade::handle<BVH_Tree<T, N> >& aBVH = aTriangulation->BVH();
+    if (aBVH.IsNull())
     {
       return Standard_False;
     }
 
-    std::pair<Standard_Integer, T> aStack[BVH_Constants_MaxTreeDepth];
+    PointTriangulationSquareDistance<T,N> 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 T, int N>
+  class PointGeometrySquareDistance: public SquareDistanceToPoint <T,N,BVH_Geometry<T, N>>
+  {
+  public:
+    typedef typename VectorType<T, N>::Type BVH_VecNt;
 
-    T aMinDistance = std::numeric_limits<T>::max();
+  public:
+    //! Constructor
+    PointGeometrySquareDistance()
+      : SquareDistanceToPoint<T, N, BVH_Geometry<T, N>>()
+    {
+    }
 
-    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<T, N> (thePnt,
-                                                  aBVH->MinPoint (aData.y()),
-                                                  aBVH->MaxPoint (aData.y()));
-
-        const T aDistToRgh = DistanceToBox<T, N> (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<Standard_Integer, T> (
-            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<Standard_Integer, T>& 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<Standard_Integer, T>& 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<class T, int N>
+  T SquareDistanceToGeomerty (BVH_Geometry<T, N>& theGeometry,
+    const typename VectorType<T, N>::Type& thePnt, Standard_Boolean& theIsOutside)
+  {
+    Standard_STATIC_ASSERT (N == 3 || N == 4);
 
-          anInfo = aStack[aHead--];
-        }
+    const BVH_Tree<T, N, BVH_BinaryTree>* aBVH = theGeometry.BVH().get();
 
-        aNode = anInfo.first;
-      }
+    if (aBVH == NULL)
+    {
+      return Standard_False;
     }
+
+    PointGeometrySquareDistance<T,N> 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 (file)
index 0000000..dd822ad
--- /dev/null
@@ -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 <BVH_BoxSet.hxx>
+
+//! 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 NumType, int Dimension, class DataType = Standard_Integer>
+class BVH_IndexedBoxSet : public BVH_BoxSet <NumType, Dimension, DataType>
+{
+public: //! @name Constructors
+
+  //! Empty constructor for use the default BVH_Builder
+  BVH_IndexedBoxSet()
+    : BVH_BoxSet <NumType, Dimension, DataType>()
+  {
+  }
+  
+  //! Constructor for usage the custom BVH builder
+  BVH_IndexedBoxSet (const opencascade::handle <BVH_Builder <NumType, Dimension> >& theBuilder)
+    : BVH_BoxSet <NumType, Dimension, DataType> (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 <NumType, Dimension, DataType>::SetSize (theSize);
+  }
+
+public: //! @name Adding elements in BVH
+
+  //! Adds the element into BVH
+  virtual void Add (const DataType& theElement, const BVH_Box<NumType, Dimension>& theBox) Standard_OVERRIDE
+  {
+    myIndices.push_back (static_cast<Standard_Integer> (myIndices.size()));
+    BVH_BoxSet <NumType, Dimension, DataType>::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 <NumType, Dimension, DataType>::Clear();
+  }
+
+public: //! @name Necessary overrides for BVH construction
+
+  //! Make inherited method Box() visible to avoid CLang warning
+  using BVH_BoxSet <NumType, Dimension, DataType>::Box;
+
+  //! Returns the bounding box with the given index.
+  virtual BVH_Box <NumType, Dimension> 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 <Standard_Integer> myIndices;
+
+};
+
+#endif // _BVH_IndexedBoxSet_Header
diff --git a/src/BVH/BVH_PairDistance.hxx b/src/BVH/BVH_PairDistance.hxx
new file mode 100644 (file)
index 0000000..c7238cc
--- /dev/null
@@ -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 <BVH_Traverse.hxx>
+#include <BVH_Tools.hxx>
+
+//! 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 NumType, int Dimension, class BVHSetType>
+class BVH_PairDistance : public BVH_PairTraverse<NumType, Dimension, BVHSetType, NumType>
+{
+public:
+  typedef typename BVH_Tools<NumType, Dimension>::BVH_VecNt BVH_VecNt;
+
+public: //! @name Constructor
+
+  //! Constructor
+  BVH_PairDistance()
+    : BVH_PairTraverse <NumType, Dimension, BVHSetType, NumType>(),
+      myDistance (std::numeric_limits<NumType>::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<NumType, Dimension>::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<NumType>(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 (file)
index 0000000..24d16b5
--- /dev/null
@@ -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 <BVH_Box.hxx>
+#include <BVH_Types.hxx>
+
+//! Defines a set of static methods operating with points and bounding boxes.
+//! \tparam T Numeric data type
+//! \tparam N Vector dimension
+template <class T, int N>
+class BVH_Tools
+{
+public: //! @name public types
+
+  typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
+
+public: //! @name Box-Box Square distance
+
+  //! Computes Square distance between Axis aligned bounding boxes
+  static T BoxBoxSquareDistance (const BVH_Box<T, N>& theBox1,
+                                 const BVH_Box<T, N>& 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<T, N>& 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 (file)
index 0000000..583adfe
--- /dev/null
@@ -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 <BVH_Box.hxx>
+#include <BVH_Tree.hxx>
+
+//! 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<Standard_Real, 3, BVH_Vec3d, BVH_BoxSet<Standard_Real, 3, Triangle>>
+//! {
+//! 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<Standard_Real, 3>::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<Standard_Real, 3>::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<BVH_BoxSet<Standard_Real, 3, Triangle>> 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 MetricType>
+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 NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
+class BVH_Traverse : public BVH_BaseTraverse<MetricType>
+{
+public: //! @name public types
+
+  typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;
+
+public: //! @name Constructor
+
+  //! Constructor
+  BVH_Traverse()
+    : BVH_BaseTraverse<MetricType>(),
+      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<BVH_Tree <NumType, Dimension>>& 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<BVH_Tree <NumType, Dimension>>& 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 NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
+class BVH_PairTraverse : public BVH_BaseTraverse<MetricType>
+{
+public: //! @name public types
+
+  typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;
+
+public: //! @name Constructor
+
+  //! Constructor
+  BVH_PairTraverse()
+    : BVH_BaseTraverse<MetricType>(),
+      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 <BVH_Tree <NumType, Dimension> >& aBVH1 = myBVHSet1->BVH();
+      const opencascade::handle <BVH_Tree <NumType, Dimension> >& 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<BVH_Tree <NumType, Dimension>>& theBVH1,
+                           const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH2);
+
+protected: //! @name Fields
+
+  BVHSetType* myBVHSet1;
+  BVHSetType* myBVHSet2;
+
+};
+
+#include <BVH_Traverse.lxx>
+
+#endif // _BVH_Traverse_Header
diff --git a/src/BVH/BVH_Traverse.lxx b/src/BVH/BVH_Traverse.lxx
new file mode 100644 (file)
index 0000000..b261dd9
--- /dev/null
@@ -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<class MetricType> 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 <class NumType, int Dimension, class BVHSetType, class MetricType>
+Standard_Integer BVH_Traverse <NumType, Dimension, BVHSetType, MetricType>::Select
+  (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH)
+{
+  if (theBVH.IsNull())
+    return 0;
+
+  if (theBVH->NodeInfoBuffer().empty())
+    return 0;
+
+  // Create stack
+  BVH_NodeInStack<MetricType> aStack[BVH_Constants_MaxTreeDepth];
+
+  BVH_NodeInStack<MetricType> aNode (0);         // Currently processed node, starting with the root node
+  BVH_NodeInStack<MetricType> 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<MetricType> (aData.y(), aMetricLft);
+            aStack[++aHead] = BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
+          }
+          else
+          {
+            aNode           = BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
+            aStack[++aHead] = BVH_NodeInStack<MetricType> (aData.y(), aMetricLft);
+          }
+        }
+        else if (isGoodLft || isGoodRgh)
+        {
+          aNode = isGoodLft ?
+            BVH_NodeInStack<MetricType> (aData.y(), aMetricLft) :
+            BVH_NodeInStack<MetricType> (aData.z(), aMetricRgh);
+        }
+      }
+      else
+      {
+        // Both children will be accepted
+        // Take one for processing, put the other into stack
+        aNode           = BVH_NodeInStack<MetricType> (aData.y(), aNode.Metric);
+        aStack[++aHead] = BVH_NodeInStack<MetricType> (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<class MetricType> 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 <class NumType, int Dimension, class BVHSetType, class MetricType>
+Standard_Integer BVH_PairTraverse<NumType, Dimension, BVHSetType, MetricType>::Select
+  (const opencascade::handle<BVH_Tree <NumType, Dimension>>& theBVH1,
+   const opencascade::handle<BVH_Tree <NumType, Dimension>>& 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<MetricType> aStack[aMaxNbPairsInStack];
+
+  // Currently processed pair, starting with the root nodes
+  BVH_PairNodesInStack<MetricType> aNode (0, 0);
+  // Previously processed pair
+  BVH_PairNodesInStack<MetricType> 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<MetricType> aPairs[4];
+      Standard_Integer aNbPairs = 0;
+
+      if (aData1.x() == 0 && aData2.x() == 0)
+      {
+        // Inner/Inner
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aData2.y());
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aData2.z());
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aData2.y());
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aData2.z());
+      }
+      else if (aData1.x() == 0)
+      {
+        // Inner/Outer
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.y(), aNode.NodeID2);
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aData1.z(), aNode.NodeID2);
+      }
+      else if (aData2.x() == 0)
+      {
+        // Outer/Inner
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aNode.NodeID1, aData2.y());
+        aPairs[aNbPairs++] = BVH_PairNodesInStack<MetricType> (aNode.NodeID1, aData2.z());
+      }
+
+      BVH_PairNodesInStack<MetricType> 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;
+  }
+}
index a563d1f..90535a2 100644 (file)
@@ -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 (file)
index 0000000..cf10862
--- /dev/null
@@ -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 <Bnd_Box2d.hxx>
+#include <Bnd_Box.hxx>
+#include <BVH_Box.hxx>
+
+//! 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 <Standard_Real, 2> Bnd2BVH (const Bnd_Box2d& theBox)
+  {
+    Standard_Real aXMin, aYMin, aXMax, aYMax;
+    theBox.Get (aXMin, aYMin, aXMax, aYMax);
+    return BVH_Box <Standard_Real, 2> (BVH_Vec2d (aXMin, aYMin),
+                                       BVH_Vec2d (aXMax, aYMax));
+  }
+
+  //! Converts the given Bnd_Box to BVH_Box
+  static BVH_Box <Standard_Real, 3> Bnd2BVH (const Bnd_Box& theBox)
+  {
+    Standard_Real aXMin, aYMin, aZMin, aXMax, aYMax, aZMax;
+    theBox.Get (aXMin, aYMin, aZMin, aXMax, aYMax, aZMax);
+    return BVH_Box <Standard_Real, 3> (BVH_Vec3d (aXMin, aYMin, aZMin),
+                                       BVH_Vec3d (aXMax, aYMax, aZMax));
+  }
+};
+
+#endif // _Bnd_Tools_Header
index 1e88fce..03743cf 100644 (file)
@@ -32,3 +32,4 @@ Bnd_SeqOfBox.hxx
 Bnd_Sphere.cxx
 Bnd_Sphere.hxx
 Bnd_Sphere.lxx
+Bnd_Tools.hxx
index fd015d2..e63687d 100644 (file)
@@ -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
index 1a9cd06..b53dfc9 100644 (file)
@@ -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;
 }
index fbe9086..a04340e 100644 (file)
@@ -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 (file)
index 0000000..a2c96aa
--- /dev/null
@@ -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 <QABugs.hxx>
+
+#include <Bnd_Box.hxx>
+#include <Bnd_Tools.hxx>
+
+#include <BRep_Builder.hxx>
+
+#include <BRepBndLib.hxx>
+
+#include <BVH_Box.hxx>
+#include <BVH_BoxSet.hxx>
+#include <BVH_DistanceField.hxx>
+#include <BVH_Geometry.hxx>
+#include <BVH_LinearBuilder.hxx>
+#include <BVH_PairDistance.hxx>
+#include <BVH_Traverse.hxx>
+#include <BVH_Triangulation.hxx>
+
+#include <DBRep.hxx>
+#include <Draw.hxx>
+
+#include <Precision.hxx>
+
+#include <TopExp.hxx>
+#include <TopExp_Explorer.hxx>
+
+#include <TopoDS.hxx>
+#include <TopoDS_Compound.hxx>
+#include <TopoDS_Face.hxx>
+#include <TopoDS_Shape.hxx>
+
+#include <TopTools_IndexedMapOfShape.hxx>
+
+//=======================================================================
+//function : ShapeSelector
+//purpose : Implement the simplest shape's selector
+//=======================================================================
+class ShapeSelector :
+  public BVH_Traverse <Standard_Real, 3, BVH_BoxSet <Standard_Real, 3, TopoDS_Shape>, 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<TopoDS_Shape>& 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 <Standard_Real, 3> myBox;         //!< Selection box
+  NCollection_List <TopoDS_Shape> myShapes; //!< Selected shapes
+};
+
+//=======================================================================
+//function : ShapeSelector
+//purpose : Implement the simplest shape's selector
+//=======================================================================
+class ShapeSelectorVoid :
+  public BVH_Traverse <Standard_Real, 3, void, Standard_Boolean>
+{
+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<TopoDS_Shape>& Shapes () const { return myShapes; }
+
+public:
+
+  //! Sets the Box Set
+  void SetShapeBoxSet (const opencascade::handle<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>>& 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<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>> myBoxSet; //!< ShapeBoxSet
+  BVH_Box <Standard_Real, 3> myBox;         //!< Selection box
+  NCollection_List <TopoDS_Shape> 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 <BVH_LinearBuilder <Standard_Real, 3> > aLBuilder =
+      new BVH_LinearBuilder <Standard_Real, 3>();
+
+  // Create the ShapeSet
+  opencascade::handle <BVH_BoxSet <Standard_Real, 3, TopoDS_Shape> > aShapeBoxSet =
+    new BVH_BoxSet <Standard_Real, 3, TopoDS_Shape> (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 <Standard_Real, 3, BVH_BoxSet <Standard_Real, 3, TopoDS_Shape>>
+{
+public:
+  //! Constructor
+  PairShapesSelector() {}
+
+  //! Returns the selected pairs of shapes
+  const NCollection_List <std::pair <TopoDS_Shape, TopoDS_Shape> >& 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 <Standard_Real, 3>(theCornerMin1, theCornerMax1).IsOut (
+           BVH_Box <Standard_Real, 3>(theCornerMin2, theCornerMax2));
+  }
+
+  //! Defines the rules for leaf acceptance
+  virtual Standard_Boolean Accept (const Standard_Integer theIndex1,
+                                   const Standard_Integer theIndex2) Standard_OVERRIDE
+  {
+    BVH_Box<Standard_Real, 3> aBox1 = myBVHSet1->Box (theIndex1);
+    BVH_Box<Standard_Real, 3> aBox2 = myBVHSet2->Box (theIndex2);
+    if (!aBox1.IsOut (aBox2))
+    {
+      myPairs.Append (std::pair <TopoDS_Shape, TopoDS_Shape> (myBVHSet1->Element (theIndex1),
+                                                              myBVHSet2->Element (theIndex2)));
+      return Standard_True;
+    }
+    return Standard_False;
+  }
+
+protected:
+
+  NCollection_List <std::pair <TopoDS_Shape, TopoDS_Shape> > myPairs; //!< Selected pairs
+};
+
+//=======================================================================
+//function : PairShapeSelector
+//purpose : Implement the simplest shape's selector
+//=======================================================================
+class PairShapesSelectorVoid :
+  public BVH_PairTraverse <Standard_Real, 3>
+{
+public:
+  //! Constructor
+  PairShapesSelectorVoid() {}
+
+  //! Returns the selected pairs of shapes
+  const NCollection_List <std::pair <TopoDS_Shape, TopoDS_Shape> >& Pairs () const { return myPairs; }
+
+public:
+
+  //! Sets the sets to access the elements
+  void SetShapeBoxSets (const opencascade::handle<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>>& theSBSet1,
+                        const opencascade::handle<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>>& 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 <Standard_Real, 3>(theCornerMin1, theCornerMax1).IsOut (
+           BVH_Box <Standard_Real, 3>(theCornerMin2, theCornerMax2));
+  }
+
+  //! Defines the rules for leaf acceptance
+  virtual Standard_Boolean Accept (const Standard_Integer theIndex1,
+                                   const Standard_Integer theIndex2) Standard_OVERRIDE
+  {
+    BVH_Box<Standard_Real, 3> aBox1 = mySBSet1->Box (theIndex1);
+    BVH_Box<Standard_Real, 3> aBox2 = mySBSet2->Box (theIndex2);
+    if (!aBox1.IsOut (aBox2))
+    {
+      myPairs.Append (std::pair <TopoDS_Shape, TopoDS_Shape> (mySBSet1->Element (theIndex1),
+                                                              mySBSet2->Element (theIndex2)));
+      return Standard_True;
+    }
+    return Standard_False;
+  }
+
+protected:
+  opencascade::handle<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>> mySBSet1; //!< First ShapeBoxSet
+  opencascade::handle<BVH_BoxSet<Standard_Real, 3, TopoDS_Shape>> mySBSet2; //!< Second ShapeBoxSet
+  NCollection_List <std::pair <TopoDS_Shape, TopoDS_Shape> > 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 <BVH_LinearBuilder <Standard_Real, 3> > aLBuilder =
+      new BVH_LinearBuilder <Standard_Real, 3>();
+
+  // Create the ShapeSet
+  opencascade::handle <BVH_BoxSet <Standard_Real, 3, TopoDS_Shape> > aShapeBoxSet[2];
+
+  for (Standard_Integer i = 0; i < 2; ++i)
+  {
+    aShapeBoxSet[i] = new BVH_BoxSet <Standard_Real, 3, TopoDS_Shape> (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 <std::pair <TopoDS_Shape, TopoDS_Shape> > 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 <std::pair <TopoDS_Shape, TopoDS_Shape> >::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<Standard_Real, 3>::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<BVH_Vec3d, BVH_Vec3d> anEdges[3] =
+      { std::pair<BVH_Vec3d, BVH_Vec3d> (aNodes[iT][0], aNodes[iT][1]),
+        std::pair<BVH_Vec3d, BVH_Vec3d> (aNodes[iT][1], aNodes[iT][2]),
+        std::pair<BVH_Vec3d, BVH_Vec3d> (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<Standard_Real, 3>::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<Standard_Real, 3, BVH_BoxSet<Standard_Real, 3, Triangle>>
+{
+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 <BVH_LinearBuilder <Standard_Real, 3> > aLBuilder =
+      new BVH_LinearBuilder <Standard_Real, 3>();
+
+  // Create the ShapeSet
+  opencascade::handle <BVH_BoxSet <Standard_Real, 3, Triangle> > aTriangleBoxSet[2];
+
+  for (Standard_Integer i = 0; i < 2; ++i)
+  {
+    aTriangleBoxSet[i] = new BVH_BoxSet <Standard_Real, 3, Triangle> (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<Standard_Real, 3> 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<Standard_Real, 3>
+{
+public:
+  QABVH_TriangleSet()
+    : BVH_Triangulation<Standard_Real, 3>()
+  {}
+
+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<Standard_Integer>(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<Standard_Real, 3>
+{
+public:
+  QABVH_Geometry()
+    : BVH_Geometry<Standard_Real, 3>()
+  {}
+
+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<Standard_Real, 3> 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 (file)
index 0000000..bcf4760
--- /dev/null
@@ -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 (file)
index 0000000..7f057e4
--- /dev/null
@@ -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 (file)
index 0000000..101bd32
--- /dev/null
@@ -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 (file)
index 0000000..054e65c
--- /dev/null
@@ -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
+
index 398ff7c..eabf01d 100644 (file)
@@ -4,4 +4,5 @@
 004 extcc
 005 2dgcc
 006 intss
-007 classifier
\ No newline at end of file
+007 classifier
+008 bvh