0025234: Implementing LBVH builder
authordbp <dbp@opencascade.com>
Wed, 24 Sep 2014 15:32:40 +0000 (19:32 +0400)
committerbugmaster <bugmaster@opencascade.com>
Thu, 9 Oct 2014 12:02:09 +0000 (16:02 +0400)
Performs fast BVH construction using LBVH building approach. Algorithm uses spatial Morton codes to reduce the BVH construction problem to a sorting problem (radix sort -- O(N) complexity). This Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees of lower quality compared to SAH-based BVH builders but it is over an order of magnitude faster (up to 4M triangles per second).

17 files changed:
src/BVH/BVH.cxx
src/BVH/BVH_BinnedBuilder.hxx
src/BVH/BVH_BinnedBuilder.lxx
src/BVH/BVH_Builder.hxx
src/BVH/BVH_Builder.lxx
src/BVH/BVH_LinearBuilder.hxx [new file with mode: 0644]
src/BVH/BVH_LinearBuilder.lxx [new file with mode: 0644]
src/BVH/BVH_QueueBuilder.hxx [new file with mode: 0644]
src/BVH/BVH_QueueBuilder.lxx [new file with mode: 0644]
src/BVH/BVH_SweepPlaneBuilder.hxx
src/BVH/BVH_SweepPlaneBuilder.lxx
src/BVH/BVH_Tree.hxx
src/BVH/BVH_Tree.lxx
src/BVH/BVH_Triangulation.lxx
src/BVH/BVH_Types.hxx
src/BVH/BVH_Types.lxx
src/BVH/FILES

index efc40ff..cf81cfc 100644 (file)
@@ -15,6 +15,7 @@
 
 #include <BVH_Geometry.hxx>
 #include <BVH_Triangulation.hxx>
+#include <BVH_LinearBuilder.hxx>
 #include <BVH_BinnedBuilder.hxx>
 #include <BVH_SweepPlaneBuilder.hxx>
 #include <BVH_SpatialMedianBuilder.hxx>
@@ -85,6 +86,12 @@ template class BVH_BinnedBuilder<Standard_ShortReal, 2>;
 template class BVH_BinnedBuilder<Standard_ShortReal, 3>;
 template class BVH_BinnedBuilder<Standard_ShortReal, 4>;
 
+template class BVH_LinearBuilder<Standard_Real, 3>;
+template class BVH_LinearBuilder<Standard_Real, 4>;
+
+template class BVH_LinearBuilder<Standard_ShortReal, 3>;
+template class BVH_LinearBuilder<Standard_ShortReal, 4>;
+
 template class BVH_SweepPlaneBuilder<Standard_Real, 2>;
 template class BVH_SweepPlaneBuilder<Standard_Real, 3>;
 template class BVH_SweepPlaneBuilder<Standard_Real, 4>;
index 1592285..06a3228 100644 (file)
@@ -16,7 +16,7 @@
 #ifndef _BVH_BinnedBuilder_Header
 #define _BVH_BinnedBuilder_Header
 
-#include <BVH_Builder.hxx>
+#include <BVH_QueueBuilder.hxx>
 
 #include <algorithm>
 
@@ -34,7 +34,7 @@ struct BVH_Bin
 //! Performs building of BVH tree using binned SAH algorithm.
 //! Number of Bins controls tree's quality (greater - better) in cost of construction time.
 template<class T, int N, int Bins = 32>
-class BVH_BinnedBuilder : public BVH_Builder<T, N>
+class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
 {
 public:
 
index c002b56..3ea88cd 100644 (file)
@@ -20,8 +20,8 @@
 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)
+: BVH_QueueBuilder<T, N> (theLeafNodeSize,
+                          theMaxTreeDepth)
 {
   //
 }
@@ -36,17 +36,6 @@ BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
   //
 }
 
-namespace BVH
-{
-  template<class T>
-  static inline Standard_Integer IntFloor (const T theValue)
-  {
-    const Standard_Integer aRes = static_cast<Standard_Integer> (theValue);
-    
-    return aRes - static_cast<Standard_Integer> (aRes > theValue);
-  }
-}
-
 // =======================================================================
 // function : GetSubVolumes
 // purpose  :
@@ -291,7 +280,7 @@ void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
 
     if (!isLeaf)
     {
-      BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
+      BVH_QueueBuilder<T, N>::myTasksQueue.Append (aChildIndex);
     }
 
     BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
index 09093bf..1521343 100644 (file)
@@ -19,8 +19,6 @@
 #include <BVH_Set.hxx>
 #include <BVH_Tree.hxx>
 
-#include <NCollection_Vector.hxx>
-
 namespace
 {
   //! Minimum node size to split.
@@ -38,21 +36,14 @@ public:
                const Standard_Integer theMaxTreeDepth);
 
   //! Releases resources of BVH builder.
-  virtual ~BVH_Builder() = 0;
+  virtual ~BVH_Builder();
 
 public:
 
   //! Builds BVH using specified algorithm.
-  void Build (BVH_Set<T, N>*       theSet,
-              BVH_Tree<T, N>*      theBVH,
-              const BVH_Box<T, N>& theBox);
-
-protected:
-
-  //! Builds BVH node for specified task info.
-  virtual void BuildNode (BVH_Set<T, N>*         theSet,
-                          BVH_Tree<T, N>*        theBVH,
-                          const Standard_Integer theTask);
+  virtual void Build (BVH_Set<T, N>*       theSet,
+                      BVH_Tree<T, N>*      theBVH,
+                      const BVH_Box<T, N>& theBox) = 0;
 
   //! Updates depth of constructed BVH tree.
   void UpdateDepth (BVH_Tree<T, N>*        theBVH,
@@ -68,7 +59,6 @@ protected:
 
   Standard_Integer                     myMaxTreeDepth; //!< Maximum depth of constructed BVH
   Standard_Integer                     myLeafNodeSize; //!< Maximum number of primitives per leaf
-  NCollection_Vector<Standard_Integer> myTasksQueue;   //!< Queue to manage BVH node building tasks
 
 };
 
index 9dd4b7a..ebb173a 100644 (file)
@@ -15,7 +15,7 @@
 
 // =======================================================================
 // function : BVH_Builder
-// purpose  :
+// purpose  : Creates abstract BVH builder
 // =======================================================================
 template<class T, int N>
 BVH_Builder<T, N>::BVH_Builder (const Standard_Integer theLeafNodeSize,
@@ -28,57 +28,10 @@ BVH_Builder<T, N>::BVH_Builder (const Standard_Integer theLeafNodeSize,
 
 // =======================================================================
 // function : ~BVH_Builder
-// purpose  :
+// purpose  : Releases resources of BVH builder
 // =======================================================================
 template<class T, int N>
 BVH_Builder<T, N>::~BVH_Builder()
 {
   //
 }
-
-// =======================================================================
-// function : Build
-// purpose  :
-// =======================================================================
-template<class T, int N>
-void BVH_Builder<T, N>::Build (BVH_Set<T, N>*       theSet,
-                               BVH_Tree<T, N>*      theBVH,
-                               const BVH_Box<T, N>& theBox)
-{
-  if (theBVH == NULL)
-  {
-    return;
-  }
-
-  theBVH->Clear();
-  if (theSet->Size() == 0)
-  {
-    return;
-  }
-
-  const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, theSet->Size() - 1);
-  if (theSet->Size() == 1)
-  {
-    return;
-  }
-
-  myTasksQueue.Append (aRoot);
-  for (Standard_Integer aTask = 0; aTask < myTasksQueue.Size(); ++aTask)
-  {
-    BuildNode (theSet, theBVH, myTasksQueue.Value (aTask));
-  }
-
-  myTasksQueue.Clear();
-}
-
-// =======================================================================
-// function : BuildNode
-// purpose  :
-// =======================================================================
-template<class T, int N>
-void BVH_Builder<T, N>::BuildNode (BVH_Set<T, N>* ,
-                                   BVH_Tree<T, N>* ,
-                                   const Standard_Integer )
-{
-  // need to disable compile warnings
-}
diff --git a/src/BVH/BVH_LinearBuilder.hxx b/src/BVH/BVH_LinearBuilder.hxx
new file mode 100644 (file)
index 0000000..95e2c1f
--- /dev/null
@@ -0,0 +1,67 @@
+// Created on: 2014-09-11
+// Created by: Danila ULYANOV
+// Copyright (c) 2013-2014 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_LinearBuilder_Header
+#define _BVH_LinearBuilder_Header
+
+#include <BVH_Builder.hxx>
+
+typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
+
+//! Performs fast BVH construction using LBVH building approach.
+//! Algorithm uses spatial Morton codes to reduce the BVH construction
+//! problem to a sorting problem (radix sort -- O(N) complexity). This
+//! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
+//! of lower quality compared to SAH-based BVH builders but it is over
+//! an order of magnitude faster (up to 3M triangles per second).
+//! 
+//! For more details see:
+//! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
+//! Fast BVH construction on GPUs. Eurographics, 2009.
+template<class T, int N>
+class BVH_LinearBuilder : public BVH_Builder<T, N>
+{
+public:
+
+  typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
+
+public:
+
+  //! Creates binned LBVH builder.
+  BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = 5,
+                     const Standard_Integer theMaxTreeDepth = 32);
+
+  //! Releases resources of LBVH builder.
+  virtual ~BVH_LinearBuilder();
+
+  //! Builds BVH.
+  void Build (BVH_Set<T, N>*       theSet,
+              BVH_Tree<T, N>*      theBVH,
+              const BVH_Box<T, N>& theBox);
+
+protected:
+
+  //! Emits hierarchy from sorted Morton codes.
+  Standard_Integer EmitHierachy (BVH_Tree<T, N>*                        theBVH,
+                                 const Standard_Integer                 theBit,
+                                 const Standard_Integer                 theShift,
+                                 std::vector<BVH_EncodedLink>::iterator theStart,
+                                 std::vector<BVH_EncodedLink>::iterator theFinal);
+
+};
+
+#include <BVH_LinearBuilder.lxx>
+
+#endif // _BVH_LinearBuilder_Header
diff --git a/src/BVH/BVH_LinearBuilder.lxx b/src/BVH/BVH_LinearBuilder.lxx
new file mode 100644 (file)
index 0000000..26a7d0d
--- /dev/null
@@ -0,0 +1,503 @@
+// Created on: 2014-09-11
+// Created by: Danila ULYANOV
+// Copyright (c) 2013-2014 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 <algorithm>
+
+#include <Standard_Assert.hxx>
+
+#ifdef HAVE_TBB
+  // On Windows, function TryEnterCriticalSection has appeared in Windows NT
+  // and is surrounded by #ifdef in MS VC++ 7.1 headers.
+  // Thus to use it we need to define appropriate macro saying that we will
+  // run on Windows NT 4.0 at least
+  #if defined(_WIN32) && !defined(_WIN32_WINNT)
+    #define _WIN32_WINNT 0x0501
+  #endif
+
+  #include <tbb/task.h>
+#endif
+
+// =======================================================================
+// function : BVH_LinearBuilder
+// purpose  :
+// =======================================================================
+template<class T, int N>
+BVH_LinearBuilder<T, N>::BVH_LinearBuilder (const Standard_Integer theLeafNodeSize,
+                                            const Standard_Integer theMaxTreeDepth)
+: BVH_Builder<T, N> (theLeafNodeSize,
+                     theMaxTreeDepth)
+{
+  //
+}
+
+// =======================================================================
+// function : ~BVH_LinearBuilder
+// purpose  :
+// =======================================================================
+template<class T, int N>
+BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
+{
+  //
+}
+
+namespace BVH
+{
+  // Radix sort STL predicate for 32-bit integer.
+  class BitPredicate
+  {
+    Standard_Integer myBit;
+
+  public:
+    
+    //! Creates new radix sort predicate.
+    BitPredicate (const Standard_Integer theBit) : myBit (theBit) 
+    {
+      //
+    }
+    
+    //! Returns predicate value.
+    bool operator() (const BVH_EncodedLink theLink) const
+    {
+      const Standard_Integer aMask = 1 << myBit;
+
+      return !(theLink.first & aMask); // 0-bit to the left side
+    }
+  };
+
+  //! STL compare tool used in binary search algorithm.
+  class BitComparator
+  {
+    Standard_Integer myBit;
+
+  public:
+
+    //! Creates new STL comparator.
+    BitComparator (const Standard_Integer theBit) : myBit (theBit) 
+    {
+      //
+    }
+
+    //! Checks left value for the given bit.
+    bool operator() (BVH_EncodedLink theLink1, BVH_EncodedLink /*theLink2*/)
+    {
+      return !(theLink1.first & (1 << myBit));
+    }
+  };
+
+  //! Tool object for sorting link array using radix sort algorithm.
+  struct RadixSorter
+  {
+    typedef std::vector<BVH_EncodedLink>::iterator LinkIterator;
+
+    // Performs MSD (most significant digit) radix sort.
+    static void Perform (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theBit = 29)
+    {
+      while (theStart != theFinal && theBit >= 0)
+      {
+        LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theBit--));
+        
+        Perform (theStart, anOffset, theBit);
+      
+        theStart = anOffset;
+      }
+    }
+  };
+
+  //! Calculates bounding boxes (AABBs) for the given BVH tree. 
+  template<class T, int N>
+  Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0)
+  {
+    const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
+
+    if (aData.x() == 0)
+    {
+      const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
+      const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
+
+      const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
+      const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
+
+      typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
+      typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
+      typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
+      typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
+
+      BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
+      BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
+    
+      theTree->MinPointBuffer()[theNode] = aLftMinPoint;
+      theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
+
+      return Max (aLftDepth, aRghDepth) + 1;
+    }
+    else
+    {
+      typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
+      typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
+
+      for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
+      {
+        const typename BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
+
+        if (aPrimIdx == aData.y())
+        {
+          aMinPoint = aBox.CornerMin();
+          aMaxPoint = aBox.CornerMax();
+        }
+        else
+        {
+          BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
+          BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
+        }
+      }
+    }
+
+    return 0;
+  }
+}
+
+// =======================================================================
+// function : EmitHierachy
+// purpose  : Emits hierarchy from sorted Morton codes
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_LinearBuilder<T, N>::EmitHierachy (BVH_Tree<T, N>*                        theBVH,
+                                                        const Standard_Integer                 theBit,
+                                                        const Standard_Integer                 theShift,
+                                                        std::vector<BVH_EncodedLink>::iterator theStart,
+                                                        std::vector<BVH_EncodedLink>::iterator theFinal)
+{
+  if (theFinal - theStart > myLeafNodeSize && theBit >= 0)
+  {
+    std::vector<BVH_EncodedLink>::iterator aPosition = std::lower_bound (
+      theStart, theFinal, BVH_EncodedLink(), BVH::BitComparator (theBit));
+
+    if (aPosition == theStart || aPosition == theFinal)
+    {
+      return EmitHierachy (theBVH, theBit - 1, theShift, theStart, theFinal);
+    }
+
+    // Build inner node
+    const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
+
+    const Standard_Integer aRghNode = theShift + static_cast<Standard_Integer> (aPosition - theStart);
+    
+    const Standard_Integer aLftChild = EmitHierachy (theBVH, theBit - 1, theShift, theStart, aPosition);
+    const Standard_Integer aRghChild = EmitHierachy (theBVH, theBit - 1, aRghNode, aPosition, theFinal);
+
+    theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
+    theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
+    
+    return aNode;
+  }
+  else
+  {
+    // Build leaf node
+    return theBVH->AddLeafNode (theShift, theShift + static_cast<Standard_Integer> (theFinal - theStart) - 1);
+  }
+}
+
+#ifdef HAVE_TBB
+
+namespace BVH
+{
+  //! TBB task for parallel radix sort.
+  class RadixSortTask : public tbb::task
+  {
+    typedef std::vector<BVH_EncodedLink>::iterator LinkIterator;
+
+  private:
+
+    //! Start range element.
+    LinkIterator myStart;
+    
+    //! Final range element.
+    LinkIterator myFinal;
+
+    //! Bit position for range partition.
+    Standard_Integer myDigit;
+
+  public:
+
+    //! Creates new TBB radix sort task.
+    RadixSortTask (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
+    : myStart (theStart),
+      myFinal (theFinal),
+      myDigit (theDigit)
+    {
+      //
+    }
+
+    //! Executes the task.
+    tbb::task* execute()
+    {
+      if (myDigit < 28)
+      {
+        BVH::RadixSorter::Perform (myStart, myFinal, myDigit);
+      }
+      else
+      {
+        LinkIterator anOffset = std::partition (myStart, myFinal, BitPredicate (myDigit));
+
+        tbb::task_list aList;
+
+        aList.push_back (*new ( allocate_child() )
+          RadixSortTask (myStart, anOffset, myDigit - 1));
+
+        aList.push_back (*new ( allocate_child() )
+          RadixSortTask (anOffset, myFinal, myDigit - 1));
+
+        set_ref_count (3); // count + 1
+        spawn_and_wait_for_all (aList);
+      }
+
+      return NULL;
+    }
+  };
+
+  //! TBB task for parallel bounds updating.
+  template<class T, int N>
+  class UpdateBoundTask: public tbb::task
+  {
+    //! Set of geometric objects.
+    BVH_Set<T, N>* mySet;
+
+    //! BVH tree built over the set.
+    BVH_Tree<T, N>* myBVH;
+
+    //! BVH node to update bounding box.
+    Standard_Integer myNode;
+
+    //! Level of the processed BVH node.
+    Standard_Integer myLevel;
+
+    //! Height of the processed BVH node.
+    Standard_Integer* myHeight;
+
+  public:
+
+    //! Creates new TBB parallel bound update task.
+    UpdateBoundTask (BVH_Set<T, N>*    theSet,
+                     BVH_Tree<T, N>*   theBVH,
+                     Standard_Integer  theNode,
+                     Standard_Integer  theLevel,
+                     Standard_Integer* theHeight)
+    : mySet    (theSet),
+      myBVH    (theBVH),
+      myNode   (theNode),
+      myLevel  (theLevel),
+      myHeight (theHeight)
+    {
+      //
+    }
+
+    //! Executes the task.
+    tbb::task* execute()
+    {
+      if (myBVH->IsOuter (myNode) || myLevel > 2)
+      {
+        *myHeight = BVH::UpdateBounds (mySet, myBVH, myNode);
+      }
+      else
+      {
+        Standard_Integer aLftHeight = 0;
+        Standard_Integer aRghHeight = 0;
+
+        tbb::task_list aList;
+
+        const Standard_Integer aLftChild = myBVH->NodeInfoBuffer()[myNode].y();
+        const Standard_Integer aRghChild = myBVH->NodeInfoBuffer()[myNode].z();
+
+        Standard_Integer aCount = 1;
+
+        if (!myBVH->IsOuter (aLftChild))
+        {
+          ++aCount;
+          aList.push_back (*new ( allocate_child() )
+            UpdateBoundTask (mySet, myBVH, aLftChild, myLevel + 1, &aLftHeight));
+        }
+        else
+        {
+          aLftHeight = BVH::UpdateBounds (mySet, myBVH, aLftChild);
+        }
+
+        if (!myBVH->IsOuter (aRghChild))
+        {
+          ++aCount;
+          aList.push_back (*new( allocate_child() )
+            UpdateBoundTask (mySet, myBVH, aRghChild, myLevel + 1, &aRghHeight));
+        }
+        else
+        {
+          aRghHeight = BVH::UpdateBounds (mySet, myBVH, aRghChild);
+        }
+
+        if (aCount > 1)
+        {
+          set_ref_count (aCount);
+          spawn_and_wait_for_all (aList);
+        }
+
+        typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = myBVH->MinPointBuffer()[aLftChild];
+        typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = myBVH->MaxPointBuffer()[aLftChild];
+        typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = myBVH->MinPointBuffer()[aRghChild];
+        typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = myBVH->MaxPointBuffer()[aRghChild];
+
+        BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
+        BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
+
+        myBVH->MinPointBuffer()[myNode] = aLftMinPoint;
+        myBVH->MaxPointBuffer()[myNode] = aLftMaxPoint;
+
+        *myHeight = Max (aLftHeight, aRghHeight) + 1;
+      }
+
+      return NULL;
+    }
+  };
+}
+
+#endif
+
+// =======================================================================
+// function : Build
+// purpose  :
+// =======================================================================
+template<class T, int N>
+void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
+                                     BVH_Tree<T, N>*      theBVH,
+                                     const BVH_Box<T, N>& theBox)
+{
+  Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+  if (theBVH == NULL || theSet->Size() == 0)
+  {
+    return;
+  }
+
+  theBVH->Clear();
+
+  const Standard_Integer aDimensionX = 1024;
+  const Standard_Integer aDimensionY = 1024;
+  const Standard_Integer aDimensionZ = 1024;
+
+  const BVH_VecNt aSceneMin = theBox.CornerMin();
+  const BVH_VecNt aSceneMax = theBox.CornerMax();
+
+  const BVH_VecNt aSceneSize = aSceneMax - aSceneMin;
+
+  const T aReverseSizeX = static_cast<T> (aDimensionX) / (aSceneMax.x() - aSceneMin.x());
+  const T aReverseSizeY = static_cast<T> (aDimensionY) / (aSceneMax.y() - aSceneMin.y());
+  const T aReverseSizeZ = static_cast<T> (aDimensionZ) / (aSceneMax.z() - aSceneMin.z());
+
+  std::vector<BVH_EncodedLink> anEncodedLinks (theSet->Size(), BVH_EncodedLink());
+
+  // Step 1 -- Assign Morton code to each primitive
+  for (Standard_Integer aPrimIdx = 0; aPrimIdx < theSet->Size(); ++aPrimIdx)
+  {
+    const BVH_VecNt aCenter = theSet->Box (aPrimIdx).Center();
+
+    Standard_Integer aVoxelX = BVH::IntFloor ((aCenter.x() - aSceneMin.x()) * aReverseSizeX);
+    Standard_Integer aVoxelY = BVH::IntFloor ((aCenter.y() - aSceneMin.y()) * aReverseSizeY);
+    Standard_Integer aVoxelZ = BVH::IntFloor ((aCenter.z() - aSceneMin.z()) * aReverseSizeZ);
+
+    aVoxelX = Max (0, Min (aVoxelX, aDimensionX - 1));
+    aVoxelY = Max (0, Min (aVoxelY, aDimensionY - 1));
+    aVoxelZ = Max (0, Min (aVoxelZ, aDimensionZ - 1));
+
+    aVoxelX = (aVoxelX | (aVoxelX << 16)) & 0x030000FF;
+    aVoxelX = (aVoxelX | (aVoxelX <<  8)) & 0x0300F00F;
+    aVoxelX = (aVoxelX | (aVoxelX <<  4)) & 0x030C30C3;
+    aVoxelX = (aVoxelX | (aVoxelX <<  2)) & 0x09249249;
+
+    aVoxelY = (aVoxelY | (aVoxelY << 16)) & 0x030000FF;
+    aVoxelY = (aVoxelY | (aVoxelY <<  8)) & 0x0300F00F;
+    aVoxelY = (aVoxelY | (aVoxelY <<  4)) & 0x030C30C3;
+    aVoxelY = (aVoxelY | (aVoxelY <<  2)) & 0x09249249;
+
+    aVoxelZ = (aVoxelZ | (aVoxelZ << 16)) & 0x030000FF;
+    aVoxelZ = (aVoxelZ | (aVoxelZ <<  8)) & 0x0300F00F;
+    aVoxelZ = (aVoxelZ | (aVoxelZ <<  4)) & 0x030C30C3;
+    aVoxelZ = (aVoxelZ | (aVoxelZ <<  2)) & 0x09249249;
+
+    anEncodedLinks[aPrimIdx] = BVH_EncodedLink (
+      aVoxelX | (aVoxelY << 1) | (aVoxelZ << 2), aPrimIdx);
+  }
+
+  // Step 2 -- Sort primitives by their Morton codes using radix sort
+#ifdef HAVE_TBB
+
+  BVH::RadixSortTask& aSortTask = *new ( tbb::task::allocate_root() )
+    BVH::RadixSortTask (anEncodedLinks.begin(), anEncodedLinks.end(), 29);
+
+  tbb::task::spawn_root_and_wait (aSortTask);
+
+#else
+
+  BVH::RadixSorter::Perform (anEncodedLinks.begin(), anEncodedLinks.end());
+
+#endif
+
+  // Step 3 -- Emitting BVH hierarchy from sorted Morton codes
+  EmitHierachy (theBVH, 29, 0, anEncodedLinks.begin(), anEncodedLinks.end());
+
+  Standard_Integer* aLinkMap = new Standard_Integer[theSet->Size()];
+
+  for (Standard_Integer aLinkIdx = 0; aLinkIdx < theSet->Size(); ++aLinkIdx)
+  {
+    aLinkMap[anEncodedLinks[aLinkIdx].second] = aLinkIdx;
+  }
+
+  // Step 4 -- Rearranging primitive list according to Morton codes (in place)
+  Standard_Integer aPrimIdx = 0;
+
+  while (aPrimIdx < theSet->Size())
+  {
+    const Standard_Integer aSortIdx = aLinkMap[aPrimIdx];
+
+    if (aPrimIdx != aSortIdx)
+    {
+      theSet->Swap (aPrimIdx, aSortIdx);
+
+      std::swap (aLinkMap[aPrimIdx],
+                 aLinkMap[aSortIdx]);
+    }
+    else
+    {
+      ++aPrimIdx;
+    }
+  }
+
+  // Step 5 -- Compute bounding boxes of BVH nodes
+  theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
+  theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
+
+  Standard_Integer aDepth = 0;
+
+#ifdef HAVE_TBB
+
+  BVH::UpdateBoundTask<T, N>& aRootTask = *new ( tbb::task::allocate_root() )
+    BVH::UpdateBoundTask<T, N> (theSet, theBVH, 0, 0, &aDepth);
+
+  tbb::task::spawn_root_and_wait (aRootTask);
+
+#else
+
+  aDepth = BVH::UpdateBounds (theSet, theBVH, 0);
+
+#endif
+
+  BVH_Builder<T, N>::UpdateDepth (theBVH, aDepth);
+}
diff --git a/src/BVH/BVH_QueueBuilder.hxx b/src/BVH/BVH_QueueBuilder.hxx
new file mode 100644 (file)
index 0000000..4c0d86b
--- /dev/null
@@ -0,0 +1,58 @@
+// Created on: 2014-09-15
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2014 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_QueueBuilder_Header
+#define _BVH_QueueBuilder_Header
+
+#include <BVH_Builder.hxx>
+
+#include <NCollection_Vector.hxx>
+
+//! Abstract BVH builder based on the concept of work queue.
+template<class T, int N>
+class BVH_QueueBuilder : public BVH_Builder<T, N>
+{
+public:
+
+  //! Creates new BVH queue based builder.
+  BVH_QueueBuilder (const Standard_Integer theLeafNodeSize,
+                    const Standard_Integer theMaxTreeDepth);
+
+  //! Releases resources of BVH queue based builder.
+  virtual ~BVH_QueueBuilder() = 0;
+
+public:
+
+  //! Builds BVH using specific algorithm.
+  virtual void Build (BVH_Set<T, N>*       theSet,
+                      BVH_Tree<T, N>*      theBVH,
+                      const BVH_Box<T, N>& theBox);
+
+protected:
+
+  //! Builds BVH node for the given task info.
+  virtual void BuildNode (BVH_Set<T, N>*         theSet,
+                          BVH_Tree<T, N>*        theBVH,
+                          const Standard_Integer theTask);
+
+protected:
+
+  NCollection_Vector<Standard_Integer> myTasksQueue;   //!< Queue to manage BVH node building tasks
+
+};
+
+#include <BVH_QueueBuilder.lxx>
+
+#endif // _BVH_QueueBuilder_Header
diff --git a/src/BVH/BVH_QueueBuilder.lxx b/src/BVH/BVH_QueueBuilder.lxx
new file mode 100644 (file)
index 0000000..70d8bf1
--- /dev/null
@@ -0,0 +1,84 @@
+// Created on: 2014-09-15
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2014 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.
+
+// =======================================================================
+// function : BVH_QueueBuilder
+// purpose  : Creates new BVH queue based builder
+// =======================================================================
+template<class T, int N>
+BVH_QueueBuilder<T, N>::BVH_QueueBuilder (const Standard_Integer theLeafNodeSize,
+                                          const Standard_Integer theMaxTreeDepth)
+: BVH_Builder<T, N> (theLeafNodeSize,
+                     theMaxTreeDepth)
+{
+  //
+}
+
+// =======================================================================
+// function : ~BVH_QueueBuilder
+// purpose  : Releases resources of BVH queue based builder
+// =======================================================================
+template<class T, int N>
+BVH_QueueBuilder<T, N>::~BVH_QueueBuilder()
+{
+  //
+}
+
+// =======================================================================
+// function : Build
+// purpose  : Builds BVH using specific algorithm
+// =======================================================================
+template<class T, int N>
+void BVH_QueueBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
+                                    BVH_Tree<T, N>*      theBVH,
+                                    const BVH_Box<T, N>& theBox)
+{
+  if (theBVH == NULL)
+  {
+    return;
+  }
+
+  theBVH->Clear();
+  if (theSet->Size() == 0)
+  {
+    return;
+  }
+
+  const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, theSet->Size() - 1);
+  if (theSet->Size() == 1)
+  {
+    return;
+  }
+
+  myTasksQueue.Append (aRoot);
+  for (Standard_Integer aTask = 0; aTask < myTasksQueue.Size(); ++aTask)
+  {
+    BuildNode (theSet, theBVH, myTasksQueue.Value (aTask));
+  }
+
+  myTasksQueue.Clear();
+}
+
+// =======================================================================
+// function : BuildNode
+// purpose  : Builds BVH node for the given task info
+// =======================================================================
+template<class T, int N>
+void BVH_QueueBuilder<T, N>::BuildNode (BVH_Set<T, N>*         /* theSet */,
+                                        BVH_Tree<T, N>*        /* theBVH */,
+                                        const Standard_Integer /* theTask */)
+{
+  // needed to disable compile warnings
+}
index b2ff52f..8d05d5f 100644 (file)
 #ifndef _BVH_SweepPlaneBuilder_Header
 #define _BVH_SweepPlaneBuilder_Header
 
-#include <BVH_Builder.hxx>
+#include <BVH_QueueBuilder.hxx>
 
 //! Performs building of BVH tree using sweep plane SAH algorithm.
 template<class T, int N>
-class BVH_SweepPlaneBuilder : public BVH_Builder<T, N>
+class BVH_SweepPlaneBuilder : public BVH_QueueBuilder<T, N>
 {
 public:
 
index cfa1255..1708206 100644 (file)
@@ -22,8 +22,8 @@
 template<class T, int N>
 BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
                                                     const Standard_Integer theMaxTreeDepth)
-: BVH_Builder<T, N> (theLeafNodeSize,
-                     theMaxTreeDepth)
+: BVH_QueueBuilder<T, N> (theLeafNodeSize,
+                          theMaxTreeDepth)
 {
   //
 }
@@ -182,7 +182,7 @@ void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>*         theSet,
 
     if (!isLeaf)
     {
-      BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
+      BVH_QueueBuilder<T, N>::myTasksQueue.Append (aChildIndex);
     }
 
     BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
index c92cddd..5aeecd0 100644 (file)
@@ -194,6 +194,14 @@ public:
                                  const Standard_Integer theLftChild,
                                  const Standard_Integer theRghChild);
 
+  //! Adds new leaf node to the BVH with UNINITIALIZED bounds.
+  Standard_Integer AddLeafNode (const Standard_Integer theBegElem,
+                                const Standard_Integer theEndElem);
+
+  //! Adds new inner node to the BVH with UNINITIALIZED bounds.
+  Standard_Integer AddInnerNode (const Standard_Integer theLftChild,
+                                 const Standard_Integer theRghChild);
+
   //! Returns value of SAH (surface area heuristic).
   //! Allows to compare the quality of BVH trees constructed for
   //! the same sets of geometric objects with different methods.
index 98d9b2f..ac3d5a5 100644 (file)
@@ -33,6 +33,32 @@ void BVH_Tree<T, N>::Clear()
 // purpose  :
 // =======================================================================
 template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddLeafNode (const Standard_Integer theBegElem,
+                                              const Standard_Integer theEndElem)
+{
+  BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
+
+  return static_cast<Standard_Integer> (BVH::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
+}
+
+// =======================================================================
+// function : AddInnerNode
+// purpose  :
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_Tree<T, N>::AddInnerNode (const Standard_Integer theLftChild,
+                                               const Standard_Integer theRghChild)
+{
+  BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
+
+  return static_cast<Standard_Integer> (BVH::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer)  - 1);
+}
+
+// =======================================================================
+// function : AddLeafNode
+// purpose  :
+// =======================================================================
+template<class T, int N>
 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_VecNt&       theMinPoint,
                                               const BVH_VecNt&       theMaxPoint,
                                               const Standard_Integer theBegElem,
index fb1b180..5cc9d64 100644 (file)
@@ -94,9 +94,8 @@ template<class T, int N>
 void BVH_Triangulation<T, N>::Swap (const Standard_Integer theIndex1,
                                     const Standard_Integer theIndex2)
 {
-  BVH_Vec4i anIndices1 = BVH::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex1);
-  BVH_Vec4i anIndices2 = BVH::ArrayOp<Standard_Integer, 4>::Value (Elements, theIndex2);
+  BVH_Vec4i& anIndices1 = BVH::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex1);
+  BVH_Vec4i& anIndices2 = BVH::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex2);
 
-  BVH::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex1) = anIndices2;
-  BVH::ArrayOp<Standard_Integer, 4>::ChangeValue (Elements, theIndex2) = anIndices1;
+  std::swap (anIndices1, anIndices2);
 }
index 53e6a94..d67f04f 100644 (file)
@@ -75,6 +75,14 @@ namespace BVH
   {
     typedef NCollection_Mat4<T> Type;
   };
+
+  template<class T>
+  static inline Standard_Integer IntFloor (const T theValue)
+  {
+    const Standard_Integer aRes = static_cast<Standard_Integer> (theValue);
+    
+    return aRes - static_cast<Standard_Integer> (aRes > theValue);
+  }
 }
 
 //! 2D vector of integers.
index 9ae79c8..b4d5650 100644 (file)
@@ -64,7 +64,7 @@ namespace BVH
                                                        const Standard_Integer theIndex)
     {
     #ifdef _BVH_USE_STD_VECTOR_
-      return theArray.at (theIndex);
+      return theArray[theIndex];
     #else
       return theArray.Value (theIndex);
     #endif
@@ -75,7 +75,7 @@ namespace BVH
                                                        const Standard_Integer theIndex)
     {
     #ifdef _BVH_USE_STD_VECTOR_
-      return theArray.at (theIndex);
+      return theArray[theIndex];
     #else
       return theArray.ChangeValue (theIndex);
     #endif
index 54d882b..c50ec7b 100644 (file)
@@ -7,6 +7,8 @@ BVH_Builder.hxx
 BVH_Builder.lxx
 BVH_Geometry.hxx
 BVH_Geometry.lxx
+BVH_LinearBuilder.hxx
+BVH_LinearBuilder.lxx
 BVH_Object.hxx
 BVH_Object.lxx
 BVH_ObjectSet.hxx
@@ -30,3 +32,5 @@ BVH_Triangulation.hxx
 BVH_Triangulation.lxx
 BVH_Types.hxx
 BVH_Types.lxx
+BVH_QueueBuilder.hxx
+BVH_QueueBuilder.lxx