src/BVH/BVH_RadixSorter.hxx

   1 // Created on: 2016-04-13
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2013-2016 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef _BVH_RadixSorter_Header
  17 #define _BVH_RadixSorter_Header
  18
  19 #include <BVH_Sorter.hxx>
  20 #include <BVH_Builder.hxx>
  21 #include <NCollection_Array1.hxx>
  22 #include <NCollection_Shared.hxx>
  23
  24 #include <algorithm>
  25
  26 #ifdef HAVE_TBB
  27   // On Windows, function TryEnterCriticalSection has appeared in Windows NT
  28   // and is surrounded by #ifdef in MS VC++ 7.1 headers.
  29   // Thus to use it we need to define appropriate macro saying that we will
  30   // run on Windows NT 4.0 at least
  31   #if defined(_WIN32) && !defined(_WIN32_WINNT)
  32     #define _WIN32_WINNT 0x0501
  33   #endif
  34
  35   #include <tbb/parallel_invoke.h>
  36 #endif
  37
  38 //! Pair of Morton code and primitive ID.
  39 typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
  40
  41 //! Performs radix sort of a BVH primitive set using
  42 //! 10-bit Morton codes (or 1024 x 1024 x 1024 grid).
  43 template<class T, int N>
  44 class BVH_RadixSorter : public BVH_Sorter<T, N>
  45 {
  46 public:
  47
  48   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
  49
  50 public:
  51
  52   //! Creates new BVH radix sorter for the given AABB.
  53   BVH_RadixSorter (const BVH_Box<T, N>& theBox) : myBox (theBox) { }
  54
  55   //! Sorts the set.
  56   virtual void Perform (BVH_Set<T, N>* theSet) Standard_OVERRIDE { Perform (theSet, 0, theSet->Size() - 1); }
  57
  58   //! Sorts the given (inclusive) range in the set.
  59   virtual void Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal) Standard_OVERRIDE;
  60
  61   //! Returns Morton codes assigned to BVH primitives.
  62   const NCollection_Array1<BVH_EncodedLink>& EncodedLinks() const { return *myEncodedLinks; }
  63
  64 protected:
  65
  66   //! Axis-aligned bounding box (AABB) to perform sorting.
  67   BVH_Box<T, N> myBox;
  68
  69   //! Morton codes assigned to BVH primitives.
  70   Handle(NCollection_Shared<NCollection_Array1<BVH_EncodedLink> >) myEncodedLinks;
  71
  72 };
  73
  74 namespace BVH
  75 {
  76   // Radix sort STL predicate for 32-bit integer.
  77   struct BitPredicate
  78   {
  79     Standard_Integer myBit;
  80
  81     //! Creates new radix sort predicate.
  82     BitPredicate (const Standard_Integer theBit) : myBit (theBit) {}
  83
  84     //! Returns predicate value.
  85     bool operator() (const BVH_EncodedLink theLink) const
  86     {
  87       const Standard_Integer aMask = 1 << myBit;
  88       return !(theLink.first & aMask); // 0-bit to the left side
  89     }
  90   };
  91
  92   //! STL compare tool used in binary search algorithm.
  93   struct BitComparator
  94   {
  95     Standard_Integer myBit;
  96
  97     //! Creates new STL comparator.
  98     BitComparator (const Standard_Integer theBit) : myBit (theBit) {}
  99
 100     //! Checks left value for the given bit.
 101     bool operator() (BVH_EncodedLink theLink1, BVH_EncodedLink /*theLink2*/)
 102     {
 103       return !(theLink1.first & (1 << myBit));
 104     }
 105   };
 106
 107   //! Tool object for sorting link array using radix sort algorithm.
 108   class RadixSorter
 109   {
 110   public:
 111
 112     typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
 113
 114   private:
 115
 116     //! TBB functor class to run sorting.
 117     struct Functor
 118     {
 119       LinkIterator     myStart; //!< Start element of exclusive sorting range
 120       LinkIterator     myFinal; //!< Final element of exclusive sorting range
 121       Standard_Integer myDigit; //!< Bit number used for partition operation
 122
 123       //! Creates new sorting functor.
 124       Functor (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
 125       : myStart (theStart), myFinal (theFinal), myDigit (theDigit) {}
 126
 127       //! Runs sorting function for the given range.
 128       void operator() () const
 129       {
 130         RadixSorter::Sort (myStart, myFinal, myDigit);
 131       }
 132     };
 133
 134   public:
 135
 136     static void Sort (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theDigit)
 137     {
 138     #ifdef HAVE_TBB
 139       if (theDigit < 24)
 140       {
 141         BVH::RadixSorter::perform (theStart, theFinal, theDigit);
 142       }
 143       else
 144       {
 145         LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theDigit));
 146         tbb::parallel_invoke (Functor (theStart, anOffset, theDigit - 1),
 147                               Functor (anOffset, theFinal, theDigit - 1));
 148       }
 149     #else
 150       BVH::RadixSorter::perform (theStart, theFinal, theDigit);
 151     #endif
 152     }
 153
 154   protected:
 155
 156     // Performs MSD (most significant digit) radix sort.
 157     static void perform (LinkIterator theStart, LinkIterator theFinal, Standard_Integer theBit = 29)
 158     {
 159       while (theStart != theFinal && theBit >= 0)
 160       {
 161         LinkIterator anOffset = std::partition (theStart, theFinal, BitPredicate (theBit--));
 162         perform (theStart, anOffset, theBit);
 163         theStart = anOffset;
 164       }
 165     }
 166   };
 167 }
 168
 169 // =======================================================================
 170 // function : Perform
 171 // purpose  :
 172 // =======================================================================
 173 template<class T, int N>
 174 void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
 175 {
 176   Standard_STATIC_ASSERT (N == 3 || N == 4);
 177
 178   const Standard_Integer aDimensionX = 1024;
 179   const Standard_Integer aDimensionY = 1024;
 180   const Standard_Integer aDimensionZ = 1024;
 181
 182   const BVH_VecNt aSceneMin = myBox.CornerMin();
 183   const BVH_VecNt aSceneMax = myBox.CornerMax();
 184
 185   const T aReverseSizeX = static_cast<T> (aDimensionX) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.x() - aSceneMin.x());
 186   const T aReverseSizeY = static_cast<T> (aDimensionY) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.y() - aSceneMin.y());
 187   const T aReverseSizeZ = static_cast<T> (aDimensionZ) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.z() - aSceneMin.z());
 188
 189   myEncodedLinks = new NCollection_Shared<NCollection_Array1<BVH_EncodedLink> >(theStart, theFinal);
 190
 191   // Step 1 -- Assign Morton code to each primitive
 192   for (Standard_Integer aPrimIdx = theStart; aPrimIdx <= theFinal; ++aPrimIdx)
 193   {
 194     const BVH_VecNt aCenter = theSet->Box (aPrimIdx).Center();
 195
 196     Standard_Integer aVoxelX = BVH::IntFloor ((aCenter.x() - aSceneMin.x()) * aReverseSizeX);
 197     Standard_Integer aVoxelY = BVH::IntFloor ((aCenter.y() - aSceneMin.y()) * aReverseSizeY);
 198     Standard_Integer aVoxelZ = BVH::IntFloor ((aCenter.z() - aSceneMin.z()) * aReverseSizeZ);
 199
 200     aVoxelX = Max (0, Min (aVoxelX, aDimensionX - 1));
 201     aVoxelY = Max (0, Min (aVoxelY, aDimensionY - 1));
 202     aVoxelZ = Max (0, Min (aVoxelZ, aDimensionZ - 1));
 203
 204     aVoxelX = (aVoxelX | (aVoxelX << 16)) & 0x030000FF;
 205     aVoxelX = (aVoxelX | (aVoxelX <<  8)) & 0x0300F00F;
 206     aVoxelX = (aVoxelX | (aVoxelX <<  4)) & 0x030C30C3;
 207     aVoxelX = (aVoxelX | (aVoxelX <<  2)) & 0x09249249;
 208
 209     aVoxelY = (aVoxelY | (aVoxelY << 16)) & 0x030000FF;
 210     aVoxelY = (aVoxelY | (aVoxelY <<  8)) & 0x0300F00F;
 211     aVoxelY = (aVoxelY | (aVoxelY <<  4)) & 0x030C30C3;
 212     aVoxelY = (aVoxelY | (aVoxelY <<  2)) & 0x09249249;
 213
 214     aVoxelZ = (aVoxelZ | (aVoxelZ << 16)) & 0x030000FF;
 215     aVoxelZ = (aVoxelZ | (aVoxelZ <<  8)) & 0x0300F00F;
 216     aVoxelZ = (aVoxelZ | (aVoxelZ <<  4)) & 0x030C30C3;
 217     aVoxelZ = (aVoxelZ | (aVoxelZ <<  2)) & 0x09249249;
 218
 219     myEncodedLinks->ChangeValue (aPrimIdx) = BVH_EncodedLink (
 220       aVoxelX | (aVoxelY << 1) | (aVoxelZ << 2), aPrimIdx);
 221   }
 222
 223   // Step 2 -- Sort primitives by their Morton codes using radix sort
 224   BVH::RadixSorter::Sort (myEncodedLinks->begin(), myEncodedLinks->end(), 29);
 225
 226   NCollection_Array1<Standard_Integer> aLinkMap (theStart, theFinal);
 227   for (Standard_Integer aLinkIdx = theStart; aLinkIdx <= theFinal; ++aLinkIdx)
 228   {
 229     aLinkMap (myEncodedLinks->Value (aLinkIdx).second) = aLinkIdx;
 230   }
 231
 232   // Step 3 -- Rearranging primitive list according to Morton codes (in place)
 233   Standard_Integer aPrimIdx = theStart;
 234   while (aPrimIdx <= theFinal)
 235   {
 236     const Standard_Integer aSortIdx = aLinkMap (aPrimIdx);
 237     if (aPrimIdx != aSortIdx)
 238     {
 239       theSet->Swap (aPrimIdx, aSortIdx);
 240       std::swap (aLinkMap (aPrimIdx),
 241                  aLinkMap (aSortIdx));
 242     }
 243     else
 244     {
 245       ++aPrimIdx;
 246     }
 247   }
 248 }
 249
 250 #endif // _BVH_RadixSorter_Header