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.
// 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>
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>;
#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
BVH_Tree<T, N>* theBVH,
const BVH_Box<T, N>& theBox);
+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;
};
// 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 :
//
}
-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)
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
return NULL;
}
};
-}
#endif
+}
// =======================================================================
// function : Build
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);
}
--- /dev/null
+// 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
--- /dev/null
+// 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.
+
+// =======================================================================
+// function : Perform
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_QuickSorter<T, N>::Perform (BVH_Set<T, N>* theSet)
+{
+ Perform (theSet, 0, theSet->Size() - 1);
+}
+
+// =======================================================================
+// function : Perform
+// purpose :
+// =======================================================================
+template<class T, int N>
+void BVH_QuickSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
+{
+ Standard_Integer aLft = theStart;
+ Standard_Integer aRgh = theFinal;
+
+ T aPivot = theSet->Center ((aRgh + aLft) / 2, myAxis);
+
+ while (aLft < aRgh)
+ {
+ while (theSet->Center (aLft, myAxis) < aPivot && aLft < theFinal)
+ {
+ ++aLft;
+ }
+
+ while (theSet->Center (aRgh, myAxis) > aPivot && aRgh > theStart)
+ {
+ --aRgh;
+ }
+
+ if (aLft <= aRgh)
+ {
+ if (aLft != aRgh)
+ {
+ theSet->Swap (aLft, aRgh);
+ }
+
+ ++aLft;
+ --aRgh;
+ }
+ }
+
+ if (aRgh > theStart)
+ {
+ Perform (theSet, theStart, aRgh);
+ }
+
+ if (aLft < theFinal)
+ {
+ Perform (theSet, aLft, theFinal);
+ }
+}
--- /dev/null
+// 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
--- /dev/null
+// 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;
+ }
+ }
+}
#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
+++ /dev/null
-// Created on: 2014-01-10
-// 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 : Perform
-// purpose :
-// =======================================================================
-template<class T, int N>
-void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>* theSet,
- const Standard_Integer theAxis)
-{
- Perform (theSet, theAxis, 0, theSet->Size() - 1);
-}
-
-// =======================================================================
-// function : Perform
-// 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)
-{
- Standard_Integer aLft = theBegElement;
- Standard_Integer aRgh = theEndElement;
-
- T aPivot = theSet->Center ((aRgh + aLft) / 2, theAxis);
-
- while (aLft < aRgh)
- {
- while (theSet->Center (aLft, theAxis) < aPivot && aLft < theEndElement)
- {
- ++aLft;
- }
-
- while (theSet->Center (aRgh, theAxis) > aPivot && aRgh > theBegElement)
- {
- --aRgh;
- }
-
- if (aLft <= aRgh)
- {
- if (aLft != aRgh)
- {
- theSet->Swap (aLft, aRgh);
- }
-
- ++aLft;
- --aRgh;
- }
- }
-
- if (aRgh > theBegElement)
- {
- Perform (theSet, theAxis, theBegElement, aRgh);
- }
-
- if (aLft < theEndElement)
- {
- Perform (theSet, theAxis, aLft, theEndElement);
- }
-}
// 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>
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;
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;
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