0027368: Finding objects in vicinity of a ray
authordbp <dbp@opencascade.org>
Mon, 25 Apr 2016 09:29:35 +0000 (12:29 +0300)
committerbugmaster <bugmaster@opencascade.com>
Thu, 28 Apr 2016 14:44:36 +0000 (17:44 +0300)
In frames of this issue, radix sort functionality from BVH_LinearBuilder was generalized and implemented as separate classes in BVH package. The basic API of sorting class is given in BVH_Sorter class, while BVH_QuickSorter and BVH_RadixSorter provide quck sroting and radix sorting algorithms respectivly.

src/BVH/BVH.cxx
src/BVH/BVH_LinearBuilder.hxx
src/BVH/BVH_LinearBuilder.lxx
src/BVH/BVH_QuickSorter.hxx [new file with mode: 0644]
src/BVH/BVH_QuickSorter.lxx [moved from src/BVH/BVH_Sorter.lxx with 57% similarity]
src/BVH/BVH_RadixSorter.hxx [new file with mode: 0644]
src/BVH/BVH_RadixSorter.lxx [new file with mode: 0644]
src/BVH/BVH_Sorter.hxx
src/BVH/BVH_SweepPlaneBuilder.lxx
src/BVH/FILES

index 1a29545..2301f3f 100644 (file)
@@ -14,6 +14,8 @@
 // commercial license or contractual agreement.
 
 #include <BVH_Geometry.hxx>
+#include <BVH_QuickSorter.hxx>
+#include <BVH_RadixSorter.hxx>
 #include <BVH_Triangulation.hxx>
 #include <BVH_DistanceField.hxx>
 #include <BVH_LinearBuilder.hxx>
@@ -93,6 +95,18 @@ template class BVH_BinnedBuilder<Standard_ShortReal, 2>;
 template class BVH_BinnedBuilder<Standard_ShortReal, 3>;
 template class BVH_BinnedBuilder<Standard_ShortReal, 4>;
 
+template class BVH_QuickSorter<Standard_Real, 3>;
+template class BVH_QuickSorter<Standard_Real, 4>;
+
+template class BVH_QuickSorter<Standard_ShortReal, 3>;
+template class BVH_QuickSorter<Standard_ShortReal, 4>;
+
+template class BVH_RadixSorter<Standard_Real, 3>;
+template class BVH_RadixSorter<Standard_Real, 4>;
+
+template class BVH_RadixSorter<Standard_ShortReal, 3>;
+template class BVH_RadixSorter<Standard_ShortReal, 4>;
+
 template class BVH_LinearBuilder<Standard_Real, 3>;
 template class BVH_LinearBuilder<Standard_Real, 4>;
 
index 95e2c1f..1bb6fc0 100644 (file)
@@ -16,9 +16,7 @@
 #ifndef _BVH_LinearBuilder_Header
 #define _BVH_LinearBuilder_Header
 
-#include <BVH_Builder.hxx>
-
-typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
+#include <BVH_RadixSorter.hxx>
 
 //! Performs fast BVH construction using LBVH building approach.
 //! Algorithm uses spatial Morton codes to reduce the BVH construction
@@ -53,12 +51,26 @@ public:
 
 protected:
 
+    typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
+
+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);
+  Standard_Integer EmitHierachy (BVH_Tree<T, N>*        theBVH,
+                                 const Standard_Integer theBit,
+                                 const Standard_Integer theShift,
+                                 const Standard_Integer theStart,
+                                 const Standard_Integer theFinal);
+
+  //! Returns index of the first element which does not compare less than the given one.
+  Standard_Integer LowerBound (Standard_Integer theStart,
+                               Standard_Integer theFinal,
+                               Standard_Integer theDigit);
+
+protected:
+
+  //! Tool object to perform radix sort of BVH primitives.
+  NCollection_Handle<BVH_RadixSorter<T, N> > myRadixSorter;
 
 };
 
index 6e92028..e616590 100644 (file)
 // Alternatively, this file may be used under the terms of Open CASCADE
 // commercial license or contractual agreement.
 
-#include <algorithm>
-
 #include <Standard_Assert.hxx>
 
-#include <NCollection_Array1.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  :
@@ -54,69 +38,78 @@ BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
   //
 }
 
-namespace BVH
+// =======================================================================
+// function : LowerBound
+// purpose  : Returns index of first element greater than the given one
+// =======================================================================
+template<class T, int N>
+Standard_Integer BVH_LinearBuilder<T, N>::LowerBound (Standard_Integer theStart,
+                                                      Standard_Integer theFinal,
+                                                      Standard_Integer theDigit)
 {
-  // Radix sort STL predicate for 32-bit integer.
-  class BitPredicate
+  Standard_Integer aNbPrims = theFinal - theStart;
+
+  while (aNbPrims > 0)
   {
-    Standard_Integer myBit;
+    const Standard_Integer aStep = aNbPrims / 2;
 
-  public:
-    
-    //! Creates new radix sort predicate.
-    BitPredicate (const Standard_Integer theBit) : myBit (theBit) 
+    if (myRadixSorter->EncodedLinks().Value (theStart + aStep).first & (1 << theDigit))
     {
-      //
+      aNbPrims = aStep;
     }
-    
-    //! Returns predicate value.
-    bool operator() (const BVH_EncodedLink theLink) const
+    else
     {
-      const Standard_Integer aMask = 1 << myBit;
-
-      return !(theLink.first & aMask); // 0-bit to the left side
+      theStart += aStep + 1;
+      aNbPrims -= aStep + 1;
     }
-  };
+  }
 
-  //! STL compare tool used in binary search algorithm.
-  class BitComparator
-  {
-    Standard_Integer myBit;
+  return theStart;
+}
 
-  public:
+// =======================================================================
+// 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,
+                                                        const Standard_Integer theStart,
+                                                        const Standard_Integer theFinal)
+{
+  if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
+  {
+    const Standard_Integer aPosition = theBit < 0 ?
+      (theStart + theFinal) / 2 : LowerBound (theStart, theFinal, theBit);
 
-    //! Creates new STL comparator.
-    BitComparator (const Standard_Integer theBit) : myBit (theBit) 
+    if (aPosition == theStart || aPosition == theFinal)
     {
-      //
+      return EmitHierachy (theBVH, theBit - 1, theShift, theStart, theFinal);
     }
 
-    //! Checks left value for the given bit.
-    bool operator() (BVH_EncodedLink theLink1, BVH_EncodedLink /*theLink2*/)
-    {
-      return !(theLink1.first & (1 << myBit));
-    }
-  };
+    // Build inner node
+    const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
 
-  //! Tool object for sorting link array using radix sort algorithm.
-  struct RadixSorter
-  {
-    typedef std::vector<BVH_EncodedLink>::iterator LinkIterator;
+    const Standard_Integer aRghNode = theShift + aPosition - theStart;
 
-    // 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;
-      }
-    }
-  };
+    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 + theFinal - theStart - 1);
+  }
+}
 
+namespace BVH
+{
   //! 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)
@@ -168,108 +161,9 @@ namespace BVH
 
     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 > BVH_Builder<T, N>::myLeafNodeSize)
-  {
-    std::vector<BVH_EncodedLink>::iterator aPosition =
-      (theBit >= 0) ? std::lower_bound (theStart, theFinal, BVH_EncodedLink(), BVH::BitComparator (theBit))
-                    :                   theStart + ((theFinal - theStart) / 2);
-
-    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
@@ -370,9 +264,9 @@ namespace BVH
       return NULL;
     }
   };
-}
 
 #endif
+}
 
 // =======================================================================
 // function : Build
@@ -392,116 +286,35 @@ void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
 
   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 T aMinSize = static_cast<T> (BVH::THE_NODE_MIN_SIZE);
-
-  const T aReverseSizeX = static_cast<T> (aDimensionX) / Max (aMinSize, aSceneMax.x() - aSceneMin.x());
-  const T aReverseSizeY = static_cast<T> (aDimensionY) / Max (aMinSize, aSceneMax.y() - aSceneMin.y());
-  const T aReverseSizeZ = static_cast<T> (aDimensionZ) / Max (aMinSize, aSceneMax.z() - aSceneMin.z());
-
-  std::vector<BVH_EncodedLink> anEncodedLinks (aSetSize, BVH_EncodedLink());
-
-  // Step 1 -- Assign Morton code to each primitive
-  for (Standard_Integer aPrimIdx = 0; aPrimIdx < aSetSize; ++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());
-
-  NCollection_Array1<Standard_Integer> aLinkMap (0, aSetSize - 1);
-  for (Standard_Integer aLinkIdx = 0; aLinkIdx < aSetSize; ++aLinkIdx)
-  {
-    aLinkMap (anEncodedLinks[aLinkIdx].second) = aLinkIdx;
-  }
-
-  // Step 4 -- Rearranging primitive list according to Morton codes (in place)
-  Standard_Integer aPrimIdx = 0;
+  // Step 0 -- Initialize parameter of virtual grid
+  myRadixSorter = new BVH_RadixSorter<T, N> (theBox);
 
-  while (aPrimIdx < aSetSize)
-  {
-    const Standard_Integer aSortIdx = aLinkMap (aPrimIdx);
-
-    if (aPrimIdx != aSortIdx)
-    {
-      theSet->Swap (aPrimIdx, aSortIdx);
+  // Step 1 - Perform radix sorting of primitive set
+  myRadixSorter->Perform (theSet);
 
-      std::swap (aLinkMap (aPrimIdx),
-                 aLinkMap (aSortIdx));
-    }
-    else
-    {
-      ++aPrimIdx;
-    }
-  }
+  // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
+  EmitHierachy (theBVH, 29, 0, 0, theSet->Size());
 
-  // Step 5 -- Compute bounding boxes of BVH nodes
+  // Step 3 -- Compute bounding boxes of BVH nodes
   theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
   theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 
-  Standard_Integer aDepth = 0;
+  Standard_Integer aHeight = 0;
 
 #ifdef HAVE_TBB
 
   // Note: Although TBB tasks are allocated using placement
   // new, we do not need to delete them explicitly
   BVH::UpdateBoundTask<T, N>& aRootTask = *new ( tbb::task::allocate_root() )
-    BVH::UpdateBoundTask<T, N> (theSet, theBVH, 0, 0, &aDepth);
+    BVH::UpdateBoundTask<T, N> (theSet, theBVH, 0, 0, &aHeight);
 
   tbb::task::spawn_root_and_wait (aRootTask);
 
 #else
 
-  aDepth = BVH::UpdateBounds (theSet, theBVH, 0);
+  aHeight = BVH::UpdateBounds (theSet, theBVH, 0);
 
 #endif
 
-  BVH_Builder<T, N>::UpdateDepth (theBVH, aDepth);
+  BVH_Builder<T, N>::UpdateDepth (theBVH, aHeight);
 }
diff --git a/src/BVH/BVH_QuickSorter.hxx b/src/BVH/BVH_QuickSorter.hxx
new file mode 100644 (file)
index 0000000..b39da74
--- /dev/null
@@ -0,0 +1,46 @@
+// Created on: 2016-04-13
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2016 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_QuickSorter_Header
+#define _BVH_QuickSorter_Header
+
+#include <BVH_Sorter.hxx>
+
+//! Performs centroid-based sorting of abstract set along
+//! the given axis (X - 0, Y - 1, Z - 2) using quick sort.
+template<class T, int N>
+class BVH_QuickSorter : public BVH_Sorter<T, N>
+{
+public:
+
+  //! Creates new BVH quick sorter for the given axis.
+  BVH_QuickSorter (const Standard_Integer theAxis = 0) : myAxis (theAxis) { }
+
+  //! Sorts the set.
+  virtual void Perform (BVH_Set<T, N>* theSet);
+
+  //! Sorts the given (inclusive) range in the set.
+  virtual void Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal);
+
+protected:
+
+  //! Axis used to arrange the primitives (X - 0, Y - 1, Z - 2).
+  Standard_Integer myAxis;
+
+};
+
+#include <BVH_QuickSorter.lxx>
+
+#endif // _BVH_QuickSorter_Header
similarity index 57%
rename from src/BVH/BVH_Sorter.lxx
rename to src/BVH/BVH_QuickSorter.lxx
index a94dd12..b6161af 100644 (file)
@@ -1,6 +1,6 @@
-// Created on: 2014-01-10
+// Created on: 2016-04-13
 // Created by: Denis BOGOLEPOV
-// Copyright (c) 2013-2014 OPEN CASCADE SAS
+// Copyright (c) 2013-2016 OPEN CASCADE SAS
 //
 // This file is part of Open CASCADE Technology software library.
 //
 // purpose  :
 // =======================================================================
 template<class T, int N>
-void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
-                                const Standard_Integer theAxis)
+void BVH_QuickSorter<T, N>::Perform (BVH_Set<T, N>* theSet)
 {
-  Perform (theSet, theAxis, 0, theSet->Size() - 1);
+  Perform (theSet, 0, theSet->Size() - 1);
 }
 
 // =======================================================================
@@ -29,24 +28,21 @@ void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
 // purpose  :
 // =======================================================================
 template<class T, int N>
-void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
-                                const Standard_Integer theAxis,
-                                const Standard_Integer theBegElement,
-                                const Standard_Integer theEndElement)
+void BVH_QuickSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
 {
-  Standard_Integer aLft = theBegElement;
-  Standard_Integer aRgh = theEndElement;
+  Standard_Integer aLft = theStart;
+  Standard_Integer aRgh = theFinal;
 
-  T aPivot = theSet->Center ((aRgh + aLft) / 2, theAxis);
+  T aPivot = theSet->Center ((aRgh + aLft) / 2, myAxis);
 
   while (aLft < aRgh)
   {
-    while (theSet->Center (aLft, theAxis) < aPivot && aLft < theEndElement)
+    while (theSet->Center (aLft, myAxis) < aPivot && aLft < theFinal)
     {
       ++aLft;
     }
 
-    while (theSet->Center (aRgh, theAxis) > aPivot && aRgh > theBegElement)
+    while (theSet->Center (aRgh, myAxis) > aPivot && aRgh > theStart)
     {
       --aRgh;
     }
@@ -63,13 +59,13 @@ void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
     }
   }
 
-  if (aRgh > theBegElement)
+  if (aRgh > theStart)
   {
-    Perform (theSet, theAxis, theBegElement, aRgh);
+    Perform (theSet, theStart, aRgh);
   }
 
-  if (aLft < theEndElement)
+  if (aLft < theFinal)
   {
-    Perform (theSet, theAxis, aLft, theEndElement);
+    Perform (theSet, aLft, theFinal);
   }
 }
diff --git a/src/BVH/BVH_RadixSorter.hxx b/src/BVH/BVH_RadixSorter.hxx
new file mode 100644 (file)
index 0000000..1d97b7e
--- /dev/null
@@ -0,0 +1,63 @@
+// Created on: 2016-04-13
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2016 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_RadixSorter_Header
+#define _BVH_RadixSorter_Header
+
+#include <BVH_Sorter.hxx>
+#include <BVH_Builder.hxx>
+
+#include <NCollection_Handle.hxx>
+#include <NCollection_Array1.hxx>
+
+//! Pair of Morton code and primitive ID.
+typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
+
+//! Performs radix sort of a BVH primitive set using
+//! 10-bit Morton codes (or 1024 x 1024 x 1024 grid).
+template<class T, int N>
+class BVH_RadixSorter : public BVH_Sorter<T, N>
+{
+public:
+
+  typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
+
+public:
+
+  //! Creates new BVH radix sorter for the given AABB.
+  BVH_RadixSorter (const BVH_Box<T, N>& theBox) : myBox (theBox) { }
+
+  //! Sorts the set.
+  virtual void Perform (BVH_Set<T, N>* theSet);
+
+  //! Sorts the given (inclusive) range in the set.
+  virtual void Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal);
+
+  //! Returns Morton codes assigned to BVH primitives.
+  const NCollection_Array1<BVH_EncodedLink>& EncodedLinks() const { return *myEncodedLinks; }
+
+protected:
+
+  //! Axis-aligned bounding box (AABB) to perform sorting.
+  BVH_Box<T, N> myBox;
+
+  //! Morton codes assigned to BVH primitives.
+  NCollection_Handle<NCollection_Array1<BVH_EncodedLink> > myEncodedLinks;
+
+};
+
+#include <BVH_RadixSorter.lxx>
+
+#endif // _BVH_RadixSorter_Header
diff --git a/src/BVH/BVH_RadixSorter.lxx b/src/BVH/BVH_RadixSorter.lxx
new file mode 100644 (file)
index 0000000..3cfa574
--- /dev/null
@@ -0,0 +1,241 @@
+// Created on: 2016-04-13
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2016 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>
+
+#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/parallel_invoke.h>
+#endif
+
+// =======================================================================
+// function : Perform
+// purpose  :
+// =======================================================================
+template<class T, int N>
+void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet)
+{
+  Perform (theSet, 0, theSet->Size() - 1);
+}
+
+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.
+  class RadixSorter
+  {
+  public:
+
+    typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
+
+  private:
+
+  //! TBB functor class to run sorting.
+  class Functor
+  {
+    //! Start element of exclusive sorting range.
+    LinkIterator myStart;
+
+    //! Final element of exclusive sorting range.
+    LinkIterator myFinal;
+
+    //! Bit number used for partition operation.
+    Standard_Integer myDigit;
+
+  public:
+
+    //! Creates new sorting functor.
+    Functor (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
+     : myStart (theStart),
+       myFinal (theFinal),
+       myDigit (theDigit) { }
+
+    //! Runs sorting function for the given range.
+    void operator() () const
+    {
+      RadixSorter::Sort (myStart, myFinal, myDigit);
+    }
+  };
+
+  public:
+
+    static void Sort (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
+    {
+#ifdef HAVE_TBB
+      if (theDigit < 24)
+      {
+        BVH::RadixSorter::perform (theStart, theFinal, theDigit);
+      }
+      else
+      {
+        LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theDigit));
+
+        tbb::parallel_invoke (Functor (theStart, anOffset, theDigit - 1),
+                              Functor (anOffset, theFinal, theDigit - 1));
+      }
+#else
+      BVH::RadixSorter::perform (theStart, theFinal, theDigit);
+#endif
+    }
+
+  protected:
+
+    // 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;
+      }
+    }
+  };
+}
+
+// =======================================================================
+// function : Perform
+// purpose  :
+// =======================================================================
+template<class T, int N>
+void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
+{
+  Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+  const Standard_Integer aDimensionX = 1024;
+  const Standard_Integer aDimensionY = 1024;
+  const Standard_Integer aDimensionZ = 1024;
+
+  const BVH_VecNt aSceneMin = myBox.CornerMin();
+  const BVH_VecNt aSceneMax = myBox.CornerMax();
+
+  const T aReverseSizeX = static_cast<T> (aDimensionX) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.x() - aSceneMin.x());
+  const T aReverseSizeY = static_cast<T> (aDimensionY) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.y() - aSceneMin.y());
+  const T aReverseSizeZ = static_cast<T> (aDimensionZ) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.z() - aSceneMin.z());
+
+  myEncodedLinks = new NCollection_Array1<BVH_EncodedLink> (theStart, theFinal);
+
+  // Step 1 -- Assign Morton code to each primitive
+  for (Standard_Integer aPrimIdx = theStart; aPrimIdx <= theFinal; ++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;
+
+    myEncodedLinks->ChangeValue (aPrimIdx) = BVH_EncodedLink (
+      aVoxelX | (aVoxelY << 1) | (aVoxelZ << 2), aPrimIdx);
+  }
+
+  // Step 2 -- Sort primitives by their Morton codes using radix sort
+  BVH::RadixSorter::Sort (myEncodedLinks->begin(), myEncodedLinks->end(), 29);
+
+  NCollection_Array1<Standard_Integer> aLinkMap (theStart, theFinal);
+
+  for (Standard_Integer aLinkIdx = theStart; aLinkIdx <= theFinal; ++aLinkIdx)
+  {
+    aLinkMap (myEncodedLinks->Value (aLinkIdx).second) = aLinkIdx;
+  }
+
+  // Step 3 -- Rearranging primitive list according to Morton codes (in place)
+  Standard_Integer aPrimIdx = theStart;
+
+  while (aPrimIdx <= theFinal)
+  {
+    const Standard_Integer aSortIdx = aLinkMap (aPrimIdx);
+
+    if (aPrimIdx != aSortIdx)
+    {
+      theSet->Swap (aPrimIdx, aSortIdx);
+
+      std::swap (aLinkMap (aPrimIdx),
+                 aLinkMap (aSortIdx));
+    }
+    else
+    {
+      ++aPrimIdx;
+    }
+  }
+}
index 190549f..59e2fbd 100644 (file)
 
 #include <BVH_Set.hxx>
 
-//! Performs centroid-based sorting of abstract set.
+//! Tool object to sort abstract primitive set.
 template<class T, int N>
 class BVH_Sorter
 {
 public:
 
-  //! Sorts the set by centroids coordinates in specified axis.
-  static void Perform (BVH_Set<T, N>*         theSet,
-                       const Standard_Integer theAxis);
+  //! Releases resources of BVH sorter.
+  virtual ~BVH_Sorter() { }
 
-  //! Sorts the set by centroids coordinates in specified axis.
-  static void Perform (BVH_Set<T, N>*         theSet,
-                       const Standard_Integer theAxis,
-                       const Standard_Integer theBegElement,
-                       const Standard_Integer theEndElement);
+  //! Sorts the set.
+  virtual void Perform (BVH_Set<T, N>* theSet) = 0;
 
-};
+  //! Sorts the given (inclusive) range in the set.
+  virtual void Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal) = 0;
 
-#include <BVH_Sorter.lxx>
+};
 
 #endif // _BVH_Sorter_Header
index 697c962..1b3fed2 100644 (file)
@@ -13,7 +13,7 @@
 // Alternatively, this file may be used under the terms of Open CASCADE
 // commercial license or contractual agreement.
 
-#include <BVH_Sorter.hxx>
+#include <BVH_QuickSorter.hxx>
 
 #include <NCollection_Array1.hxx>
 
@@ -79,7 +79,7 @@ typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_SweepPlaneBuilder<T, N>::Bui
       continue;
     }
 
-    BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
+    BVH_QuickSorter<T, N> (anAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive);
 
     BVH_Box<T, N> aLftBox;
     BVH_Box<T, N> aRghBox;
@@ -127,7 +127,7 @@ typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_SweepPlaneBuilder<T, N>::Bui
 
   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
   {
-    BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
+    BVH_QuickSorter<T, N> (aMinSplitAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive);
   }
 
   BVH_Box<T, N> aMinSplitBoxLft;
index 3684e12..cb4d59b 100644 (file)
@@ -29,7 +29,10 @@ BVH_QueueBuilder.lxx
 BVH_Set.hxx
 BVH_Set.lxx
 BVH_Sorter.hxx
-BVH_Sorter.lxx
+BVH_QuickSorter.hxx
+BVH_QuickSorter.lxx
+BVH_RadixSorter.hxx
+BVH_RadixSorter.lxx
 BVH_SpatialMedianBuilder.hxx
 BVH_SpatialMedianBuilder.lxx
 BVH_SweepPlaneBuilder.hxx