0024473: TKMath, BVH - introduce template-based package for Bounding volume hierarchy...
[occt.git] / src / BVH / BVH_BinnedBuilder.lxx
diff --git a/src/BVH/BVH_BinnedBuilder.lxx b/src/BVH/BVH_BinnedBuilder.lxx
new file mode 100644 (file)
index 0000000..0cf105d
--- /dev/null
@@ -0,0 +1,256 @@
+// Created on: 2013-12-20
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013 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 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.
+
+// =======================================================================
+// function : BVH_BinnedBuilder
+// purpose  :
+// =======================================================================
+template<class T, int N, int Bins>
+BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize,
+                                                  const Standard_Integer theMaxTreeDepth)
+: BVH_Builder<T, N> (theLeafNodeSize,
+                     theMaxTreeDepth)
+{
+  //
+}
+
+// =======================================================================
+// function : ~BVH_BinnedBuilder
+// purpose  :
+// =======================================================================
+template<class T, int N, int Bins>
+BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
+{
+  //
+}
+
+// =======================================================================
+// function : GetSubVolumes
+// purpose  :
+// =======================================================================
+template<class T, int N, int Bins>
+void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>*         theSet,
+                                                   BVH_Tree<T, N>*        theBVH,
+                                                   const Standard_Integer theNode,
+                                                   BVH_BinVector&         theBins,
+                                                   const Standard_Integer theAxis)
+{
+  const T aMin = BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
+  const T aMax = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
+
+  const T anInvStep = static_cast<T> (Bins) / (aMax - aMin);
+
+  for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
+  {
+    typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
+
+    Standard_Integer aBinIndex = static_cast<Standard_Integer> (std::floor ((theSet->Center (anIdx, theAxis) - aMin) * anInvStep));
+    if (aBinIndex < 0)
+    {
+      aBinIndex = 0;
+    }
+    else if (aBinIndex >= Bins)
+    {
+      aBinIndex = Bins - 1;
+    }
+
+    theBins[aBinIndex].Count++;
+    theBins[aBinIndex].Box.Combine (aBox);
+  }
+}
+
+namespace BVHTools
+{
+  // =======================================================================
+  // function : SplitPrimitives
+  // purpose  :
+  // =======================================================================
+  template<class T, int N>
+  Standard_Integer SplitPrimitives (BVH_Set<T, N>*         theSet,
+                                    const BVH_Box<T, N>&   theBox,
+                                    const Standard_Integer theBeg,
+                                    const Standard_Integer theEnd,
+                                    const Standard_Integer theBin,
+                                    const Standard_Integer theAxis,
+                                    const Standard_Integer theBins)
+  {
+    const T aMin = BVHTools::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
+    const T aMax = BVHTools::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
+
+    const T anInvStep = static_cast<T> (theBins) / (aMax - aMin);
+
+    Standard_Integer aLftIdx (theBeg);
+    Standard_Integer aRghIdx (theEnd);
+
+    do
+    {
+      while ((Standard_Integer) std::floor ((theSet->Center (aLftIdx, theAxis) - aMin) * anInvStep) <= theBin && aLftIdx < theEnd)
+      {
+        ++aLftIdx;
+      }
+      while ((Standard_Integer) std::floor ((theSet->Center (aRghIdx, theAxis) - aMin) * anInvStep) > theBin && aRghIdx > theBeg)
+      {
+        --aRghIdx;
+      }
+
+      if (aLftIdx <= aRghIdx)
+      {
+        if (aLftIdx != aRghIdx)
+        {
+          theSet->Swap (aLftIdx, aRghIdx);
+        }
+
+        ++aLftIdx;
+        --aRghIdx;
+      }
+    } while (aLftIdx <= aRghIdx);
+
+    return aLftIdx;
+  }
+}
+
+#if defined (_WIN32) && defined (max)
+  #undef max
+#endif
+
+#include <limits>
+
+// =======================================================================
+// function : BuildNode
+// purpose  :
+// =======================================================================
+template<class T, int N, int Bins>
+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 typename BVH_Box<T, N>::BVH_VecNt aSize = aBox.Size();
+
+  // Parameters for storing best split
+  Standard_Integer aMinSplitAxis   = -1;
+  Standard_Integer aMinSplitIndex  =  0;
+  Standard_Integer aMinSplitNumLft =  0;
+  Standard_Integer aMinSplitNumRgh =  0;
+
+  BVH_Box<T, N> aMinSplitBoxLft;
+  BVH_Box<T, N> aMinSplitBoxRgh;
+
+  Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
+
+  // Find best split
+  for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
+  {
+    if (BVHTools::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE)
+      continue;
+
+    BVH_BinVector aBins;
+    GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);
+
+    // Choose the best split (with minimum SAH cost)
+    for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
+    {
+      Standard_Integer aLftCount = 0;
+      Standard_Integer aRghCount = 0;
+
+      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);
+      }
+
+      for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
+      {
+        aRghCount += aBins[anIndex].Count;
+        aRghAABB.Combine (aBins[anIndex].Box);
+      }
+
+      // Simple SAH evaluation
+      Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
+                          + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;
+
+      if (aCost <= aMinSplitCost)
+      {
+        aMinSplitCost   = aCost;
+        aMinSplitAxis   = anAxis;
+        aMinSplitIndex  = aSplit;
+        aMinSplitBoxLft = aLftAABB;
+        aMinSplitBoxRgh = aRghAABB;
+        aMinSplitNumLft = aLftCount;
+        aMinSplitNumRgh = aRghCount;
+      }
+    }
+  }
+
+  if (aMinSplitAxis == -1)
+  {
+    return;
+  }
+
+  theBVH->SetInner (theNode);
+
+  const Standard_Integer aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, aBox,
+                                                                    theBVH->BegPrimitive (theNode),
+                                                                    theBVH->EndPrimitive (theNode),
+                                                                    aMinSplitIndex - 1,
+                                                                    aMinSplitAxis,
+                                                                    Bins);
+
+  static const Standard_Integer aLftNode = 1;
+  static const Standard_Integer aRghNode = 2;
+
+  // Setting up tasks for child nodes
+  for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
+  {
+    typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
+                                                ? aMinSplitBoxLft.CornerMin()
+                                                : aMinSplitBoxRgh.CornerMin();
+    typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode)
+                                                ? aMinSplitBoxLft.CornerMax()
+                                                : aMinSplitBoxRgh.CornerMax();
+
+    Standard_Integer aBegPrimitive = (aSide == aLftNode)
+                                   ? theBVH->BegPrimitive (theNode)
+                                   : aMiddle;
+    Standard_Integer aEndPrimitive = (aSide == aLftNode)
+                                   ? aMiddle - 1
+                                   : theBVH->EndPrimitive (theNode);
+
+    Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);
+
+    theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
+
+    // Check to see if child node must be split
+    const Standard_Integer aNbPimitives = (aSide == aLftNode)
+                                        ? aMinSplitNumLft
+                                        : aMinSplitNumRgh;
+
+    if (aSide == aLftNode)
+      theBVH->LeftChild  (theNode) = aChildIndex;
+    else
+      theBVH->RightChild (theNode) = aChildIndex;
+
+    const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
+                                 || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
+
+    if (!isLeaf)
+      BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
+  }
+}