0026364: Foundation Classes, TKMath - Optimize BVH binned algorithm
authordbp <dbp@opencascade.com>
Tue, 23 Jun 2015 09:34:06 +0000 (12:34 +0300)
committerbugmaster <bugmaster@opencascade.com>
Tue, 21 Jul 2015 07:55:47 +0000 (10:55 +0300)
src/BVH/BVH_BinnedBuilder.hxx
src/BVH/BVH_BinnedBuilder.lxx

index 80d2dc9..011295f 100644 (file)
@@ -42,9 +42,19 @@ class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
 {
 public:
 
-  //! Type for the array of bins of BVH tree node.
+  //! Type of the array of bins of BVH tree node.
   typedef BVH_Bin<T, N> BVH_BinVector[Bins];
 
+  //! Describes split plane candidate.
+  struct BVH_SplitPlane
+  {
+    BVH_Bin<T, N> LftVoxel;
+    BVH_Bin<T, N> RghVoxel;
+  };
+
+  //! Type of the array of split plane candidates.
+  typedef BVH_SplitPlane BVH_SplitPlanes[Bins + 1];
+
 public:
 
   //! Creates binned SAH BVH builder.
index c0d95c7..5be6c34 100644 (file)
@@ -212,45 +212,43 @@ typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_BinnedBuilder<T, N, Bins>::B
   for (Standard_Integer anAxis = myUseMainAxis ? aMainAxis : 0; anAxis <= (myUseMainAxis ? aMainAxis : Min (N - 1, 2)); ++anAxis)
   {
     if (BVH::VecComp<T, N>::Get (aSize, anAxis) <= BVH::THE_NODE_MIN_SIZE)
+    {
       continue;
+    }
 
-    BVH_BinVector aBins;
-    GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);
+    BVH_BinVector aBinVector;
+    GetSubVolumes (theSet, theBVH, theNode, aBinVector, anAxis);
 
-    // Choose the best split (with minimum SAH cost)
-    for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
+    BVH_SplitPlanes aSplitPlanes;
+    for (Standard_Integer aLftSplit = 1, aRghSplit = Bins - 1; aLftSplit < Bins; ++aLftSplit, --aRghSplit)
     {
-      Standard_Integer aLftCount = 0;
-      Standard_Integer aRghCount = 0;
+      aSplitPlanes[aLftSplit].LftVoxel.Count = aSplitPlanes[aLftSplit - 1].LftVoxel.Count + aBinVector[aLftSplit - 1].Count;
+      aSplitPlanes[aRghSplit].RghVoxel.Count = aSplitPlanes[aRghSplit + 1].RghVoxel.Count + aBinVector[aRghSplit + 0].Count;
 
-      BVH_Box<T, N> aLftAABB;
-      BVH_Box<T, N> aRghAABB;
-
-      for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex)
-      {
-        aLftCount += aBins[anIndex].Count;
-        aLftAABB.Combine (aBins[anIndex].Box);
-      }
+      aSplitPlanes[aLftSplit].LftVoxel.Box = aSplitPlanes[aLftSplit - 1].LftVoxel.Box;
+      aSplitPlanes[aRghSplit].RghVoxel.Box = aSplitPlanes[aRghSplit + 1].RghVoxel.Box;
 
-      for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
-      {
-        aRghCount += aBins[anIndex].Count;
-        aRghAABB.Combine (aBins[anIndex].Box);
-      }
+      aSplitPlanes[aLftSplit].LftVoxel.Box.Combine (aBinVector[aLftSplit - 1].Box);
+      aSplitPlanes[aRghSplit].RghVoxel.Box.Combine (aBinVector[aRghSplit + 0].Box);
+    }
 
+    // Choose the best split (with minimum SAH cost)
+    for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
+    {
       // Simple SAH evaluation
-      Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
-                          + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;
+      Standard_Real aCost =
+        (static_cast<Standard_Real> (aSplitPlanes[aSplit].LftVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].LftVoxel.Count
+      + (static_cast<Standard_Real> (aSplitPlanes[aSplit].RghVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].RghVoxel.Count;
 
       if (aCost <= aMinSplitCost)
       {
         aMinSplitCost   = aCost;
         aMinSplitAxis   = anAxis;
         aMinSplitIndex  = aSplit;
-        aMinSplitBoxLft = aLftAABB;
-        aMinSplitBoxRgh = aRghAABB;
-        aMinSplitNumLft = aLftCount;
-        aMinSplitNumRgh = aRghCount;
+        aMinSplitBoxLft = aSplitPlanes[aSplit].LftVoxel.Box;
+        aMinSplitBoxRgh = aSplitPlanes[aSplit].RghVoxel.Box;
+        aMinSplitNumLft = aSplitPlanes[aSplit].LftVoxel.Count;
+        aMinSplitNumRgh = aSplitPlanes[aSplit].RghVoxel.Count;
       }
     }
   }