0024669: BVH binned builder fails to separate objects with the same center
authordbp <dbp@opencascade.com>
Mon, 17 Mar 2014 11:54:15 +0000 (15:54 +0400)
committerbugmaster <bugmaster@opencascade.com>
Thu, 20 Mar 2014 09:48:25 +0000 (13:48 +0400)
src/BVH/BVH_BinnedBuilder.hxx
src/BVH/BVH_BinnedBuilder.lxx
src/BVH/BVH_SweepPlaneBuilder.lxx

index 95b87dc..45c034d 100644 (file)
@@ -26,7 +26,7 @@ struct BVH_Bin
   BVH_Bin() : Count (0) {}
 
   Standard_Integer Count; //!< Number of primitives in the bin
-  BVH_Box<T, N>    Box;   //!< AABB of the bin
+  BVH_Box<T, N>    Box;   //!< AABB of primitives in the bin
 };
 
 //! Performs building of BVH tree using binned SAH algorithm.
index fb18dc6..85511a9 100644 (file)
@@ -136,10 +136,18 @@ void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
                                                BVH_Tree<T, N>*        theBVH,
                                                const Standard_Integer theNode)
 {
-  const BVH_Box<T, N> aBox (theBVH->MinPoint (theNode),
-                            theBVH->MaxPoint (theNode));
+  const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
+  const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
 
-  const typename BVH_Box<T, N>::BVH_VecNt aSize = aBox.Size();
+  if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
+  {
+    return; // node does not require partitioning
+  }
+
+  const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
+                              theBVH->MaxPoint (theNode));
+
+  const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();
 
   // Parameters for storing best split
   Standard_Integer aMinSplitAxis   = -1;
@@ -206,12 +214,35 @@ void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
 
   theBVH->SetInner (theNode);
 
-  const Standard_Integer aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, aBox,
-                                                                    theBVH->BegPrimitive (theNode),
-                                                                    theBVH->EndPrimitive (theNode),
-                                                                    aMinSplitIndex - 1,
-                                                                    aMinSplitAxis,
-                                                                    Bins);
+  Standard_Integer aMiddle = -1;
+
+  if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0) // case of objects with the same center
+  {
+    aMinSplitBoxLft.Clear();
+    aMinSplitBoxRgh.Clear();
+
+    aMiddle = std::max (aNodeBegPrimitive + 1,
+      static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));
+
+    aMinSplitNumLft = aMiddle - aNodeBegPrimitive;
+
+    for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
+    {
+      aMinSplitBoxLft.Combine (theSet->Box (anIndex));
+    }
+
+    aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;
+
+    for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
+    {
+      aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
+    }
+  }
+  else
+  {
+    aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, anAABB,
+      aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins);
+  }
 
   static const Standard_Integer aLftNode = 1;
   static const Standard_Integer aRghNode = 2;
@@ -227,11 +258,11 @@ void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
                                                 : aMinSplitBoxRgh.CornerMax();
 
     Standard_Integer aBegPrimitive = (aSide == aLftNode)
-                                   ? theBVH->BegPrimitive (theNode)
+                                   ? aNodeBegPrimitive
                                    : aMiddle;
     Standard_Integer aEndPrimitive = (aSide == aLftNode)
                                    ? aMiddle - 1
-                                   : theBVH->EndPrimitive (theNode);
+                                   : aNodeEndPrimitive;
 
     Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);
 
index e06a8ce..7e8fcf6 100644 (file)
@@ -51,6 +51,11 @@ void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>*         theSet,
   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
   const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
 
+  if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
+  {
+    return; // node does not require partitioning
+  }
+
   // Parameters for storing best split
   Standard_Integer aMinSplitAxis = -1;
   Standard_Integer aMinSplitIndex = 0;