src/BVH/BVH_LinearBuilder.hxx

   1 // Created on: 2014-09-11
   2 // Created by: Danila ULYANOV
   3 // Copyright (c) 2013-2014 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_LinearBuilder_Header
  17 #define _BVH_LinearBuilder_Header
  18
  19 #include <BVH_RadixSorter.hxx>
  20 #include <Standard_Assert.hxx>
  21
  22 //! Performs fast BVH construction using LBVH building approach.
  23 //! Algorithm uses spatial Morton codes to reduce the BVH construction
  24 //! problem to a sorting problem (radix sort -- O(N) complexity). This
  25 //! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
  26 //! of lower quality compared to SAH-based BVH builders but it is over
  27 //! an order of magnitude faster (up to 3M triangles per second).
  28 //!
  29 //! For more details see:
  30 //! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
  31 //! Fast BVH construction on GPUs. Eurographics, 2009.
  32 template<class T, int N>
  33 class BVH_LinearBuilder : public BVH_Builder<T, N>
  34 {
  35 public:
  36
  37   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
  38
  39 public:
  40
  41   //! Creates binned LBVH builder.
  42   BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
  43                      const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth);
  44
  45   //! Releases resources of LBVH builder.
  46   virtual ~BVH_LinearBuilder();
  47
  48   //! Builds BVH.
  49   virtual void Build (BVH_Set<T, N>*       theSet,
  50                       BVH_Tree<T, N>*      theBVH,
  51                       const BVH_Box<T, N>& theBox) const Standard_OVERRIDE;
  52
  53 protected:
  54
  55   typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
  56
  57 protected:
  58
  59   //! Emits hierarchy from sorted Morton codes.
  60   Standard_Integer emitHierachy (BVH_Tree<T, N>*        theBVH,
  61                                  const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
  62                                  const Standard_Integer theBit,
  63                                  const Standard_Integer theShift,
  64                                  const Standard_Integer theStart,
  65                                  const Standard_Integer theFinal) const;
  66
  67   //! Returns index of the first element which does not compare less than the given one.
  68   Standard_Integer lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
  69                                Standard_Integer theStart,
  70                                Standard_Integer theFinal,
  71                                Standard_Integer theDigit) const;
  72
  73 };
  74
  75 // =======================================================================
  76 // function : BVH_LinearBuilder
  77 // purpose  :
  78 // =======================================================================
  79 template<class T, int N>
  80 BVH_LinearBuilder<T, N>::BVH_LinearBuilder (const Standard_Integer theLeafNodeSize,
  81                                             const Standard_Integer theMaxTreeDepth)
  82 : BVH_Builder<T, N> (theLeafNodeSize,
  83                      theMaxTreeDepth)
  84 {
  85   //
  86 }
  87
  88 // =======================================================================
  89 // function : ~BVH_LinearBuilder
  90 // purpose  :
  91 // =======================================================================
  92 template<class T, int N>
  93 BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
  94 {
  95   //
  96 }
  97
  98 // =======================================================================
  99 // function : lowerBound
 100 // purpose  : Returns index of first element greater than the given one
 101 // =======================================================================
 102 template<class T, int N>
 103 Standard_Integer BVH_LinearBuilder<T, N>::lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
 104                                                       Standard_Integer theStart,
 105                                                       Standard_Integer theFinal,
 106                                                       Standard_Integer theDigit) const
 107 {
 108   Standard_Integer aNbPrims = theFinal - theStart;
 109   unsigned int aBit = 1U << theDigit;
 110   while (aNbPrims > 0)
 111   {
 112     const Standard_Integer aStep = aNbPrims / 2;
 113     if (theEncodedLinks.Value (theStart + aStep).first & aBit)
 114     {
 115       aNbPrims = aStep;
 116     }
 117     else
 118     {
 119       theStart += aStep + 1;
 120       aNbPrims -= aStep + 1;
 121     }
 122   }
 123
 124   return theStart;
 125 }
 126
 127 // =======================================================================
 128 // function : emitHierachy
 129 // purpose  : Emits hierarchy from sorted Morton codes
 130 // =======================================================================
 131 template<class T, int N>
 132 Standard_Integer BVH_LinearBuilder<T, N>::emitHierachy (BVH_Tree<T, N>*        theBVH,
 133                                                         const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
 134                                                         const Standard_Integer theDigit,
 135                                                         const Standard_Integer theShift,
 136                                                         const Standard_Integer theStart,
 137                                                         const Standard_Integer theFinal) const
 138 {
 139   if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
 140   {
 141     const Standard_Integer aPosition = theDigit < 0 ?
 142       (theStart + theFinal) / 2 : lowerBound (theEncodedLinks, theStart, theFinal, theDigit);
 143     if (aPosition == theStart || aPosition == theFinal)
 144     {
 145       return emitHierachy (theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, theFinal);
 146     }
 147
 148     // Build inner node
 149     const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
 150     const Standard_Integer aRghNode = theShift + aPosition - theStart;
 151
 152     const Standard_Integer aLftChild = emitHierachy (theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, aPosition);
 153     const Standard_Integer aRghChild = emitHierachy (theBVH, theEncodedLinks, theDigit - 1, aRghNode, aPosition, theFinal);
 154
 155     theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
 156     theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
 157     return aNode;
 158   }
 159   else
 160   {
 161     // Build leaf node
 162     return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1);
 163   }
 164 }
 165
 166 namespace BVH
 167 {
 168   //! Calculates bounding boxes (AABBs) for the given BVH tree.
 169   template<class T, int N>
 170   Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0)
 171   {
 172     const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
 173     if (aData.x() == 0)
 174     {
 175       const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
 176       const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
 177
 178       const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
 179       const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
 180
 181       typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
 182       typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
 183       typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
 184       typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
 185
 186       BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 187       BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 188
 189       theTree->MinPointBuffer()[theNode] = aLftMinPoint;
 190       theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
 191       return Max (aLftDepth, aRghDepth) + 1;
 192     }
 193     else
 194     {
 195       typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
 196       typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
 197       for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
 198       {
 199         const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
 200         if (aPrimIdx == aData.y())
 201         {
 202           aMinPoint = aBox.CornerMin();
 203           aMaxPoint = aBox.CornerMax();
 204         }
 205         else
 206         {
 207           BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
 208           BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
 209         }
 210       }
 211     }
 212     return 0;
 213   }
 214
 215   template<class T, int N>
 216   struct BoundData
 217   {
 218     BVH_Set <T, N>*   mySet;    //!< Set of geometric objects
 219     BVH_Tree<T, N>*   myBVH;    //!< BVH tree built over the set
 220     Standard_Integer  myNode;   //!< BVH node to update bounding box
 221     Standard_Integer  myLevel;  //!< Level of the processed BVH node
 222     Standard_Integer* myHeight; //!< Height of the processed BVH node
 223   };
 224
 225   //! Task for parallel bounds updating.
 226   template<class T, int N>
 227   class UpdateBoundTask
 228   {
 229   public:
 230
 231     UpdateBoundTask (const Standard_Boolean isParallel)
 232     : myIsParallel (isParallel)
 233     {
 234     }
 235
 236     //! Executes the task.
 237     void operator()(const BoundData<T, N>& theData) const
 238     {
 239       if (theData.myBVH->IsOuter (theData.myNode) || theData.myLevel > 2)
 240       {
 241         *theData.myHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, theData.myNode);
 242       }
 243       else
 244       {
 245         Standard_Integer aLftHeight = 0;
 246         Standard_Integer aRghHeight = 0;
 247
 248         const Standard_Integer aLftChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].y();
 249         const Standard_Integer aRghChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].z();
 250
 251         std::vector<BoundData<T, N> > aList;
 252         aList.reserve (2);
 253         if (!theData.myBVH->IsOuter (aLftChild))
 254         {
 255           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aLftChild, theData.myLevel + 1, &aLftHeight};
 256           aList.push_back (aBoundData);
 257         }
 258         else
 259         {
 260           aLftHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aLftChild);
 261         }
 262
 263         if (!theData.myBVH->IsOuter (aRghChild))
 264         {
 265           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aRghChild, theData.myLevel + 1, &aRghHeight};
 266           aList.push_back (aBoundData);
 267         }
 268         else
 269         {
 270           aRghHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aRghChild);
 271         }
 272
 273         if (!aList.empty())
 274         {
 275           OSD_Parallel::ForEach (aList.begin (), aList.end (), UpdateBoundTask<T, N> (myIsParallel), !myIsParallel);
 276         }
 277
 278         typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theData.myBVH->MinPointBuffer()[aLftChild];
 279         typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theData.myBVH->MaxPointBuffer()[aLftChild];
 280         typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theData.myBVH->MinPointBuffer()[aRghChild];
 281         typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theData.myBVH->MaxPointBuffer()[aRghChild];
 282
 283         BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 284         BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 285
 286         theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint;
 287         theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint;
 288
 289         *theData.myHeight = Max (aLftHeight, aRghHeight) + 1;
 290       }
 291     }
 292
 293   private:
 294
 295     Standard_Boolean myIsParallel;
 296   };
 297 }
 298
 299 // =======================================================================
 300 // function : Build
 301 // purpose  :
 302 // =======================================================================
 303 template<class T, int N>
 304 void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
 305                                      BVH_Tree<T, N>*      theBVH,
 306                                      const BVH_Box<T, N>& theBox) const
 307 {
 308   Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
 309   const Standard_Integer aSetSize = theSet->Size();
 310   if (theBVH == NULL || aSetSize == 0)
 311   {
 312     return;
 313   }
 314
 315   theBVH->Clear();
 316
 317   // Step 0 -- Initialize parameter of virtual grid
 318   BVH_RadixSorter<T, N> aRadixSorter (theBox);
 319   aRadixSorter.SetParallel (this->IsParallel());
 320
 321   // Step 1 - Perform radix sorting of primitive set
 322   aRadixSorter.Perform (theSet);
 323
 324   // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
 325   emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
 326
 327   // Step 3 -- Compute bounding boxes of BVH nodes
 328   theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 329   theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 330
 331   Standard_Integer aHeight = 0;
 332   BVH::BoundData<T, N> aBoundData = { theSet, theBVH, 0, 0, &aHeight };
 333   BVH::UpdateBoundTask<T, N> aBoundTask (this->IsParallel());
 334   aBoundTask (aBoundData);
 335
 336   BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
 337 }
 338
 339 #endif // _BVH_LinearBuilder_Header