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   while (aNbPrims > 0)
 110   {
 111     const Standard_Integer aStep = aNbPrims / 2;
 112     if (theEncodedLinks.Value (theStart + aStep).first & (1 << theDigit))
 113     {
 114       aNbPrims = aStep;
 115     }
 116     else
 117     {
 118       theStart += aStep + 1;
 119       aNbPrims -= aStep + 1;
 120     }
 121   }
 122
 123   return theStart;
 124 }
 125
 126 // =======================================================================
 127 // function : emitHierachy
 128 // purpose  : Emits hierarchy from sorted Morton codes
 129 // =======================================================================
 130 template<class T, int N>
 131 Standard_Integer BVH_LinearBuilder<T, N>::emitHierachy (BVH_Tree<T, N>*        theBVH,
 132                                                         const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
 133                                                         const Standard_Integer theBit,
 134                                                         const Standard_Integer theShift,
 135                                                         const Standard_Integer theStart,
 136                                                         const Standard_Integer theFinal) const
 137 {
 138   if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
 139   {
 140     const Standard_Integer aPosition = theBit < 0 ?
 141       (theStart + theFinal) / 2 : lowerBound (theEncodedLinks, theStart, theFinal, theBit);
 142     if (aPosition == theStart || aPosition == theFinal)
 143     {
 144       return emitHierachy (theBVH, theEncodedLinks, theBit - 1, theShift, theStart, theFinal);
 145     }
 146
 147     // Build inner node
 148     const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
 149     const Standard_Integer aRghNode = theShift + aPosition - theStart;
 150
 151     const Standard_Integer aLftChild = emitHierachy (theBVH, theEncodedLinks, theBit - 1, theShift, theStart, aPosition);
 152     const Standard_Integer aRghChild = emitHierachy (theBVH, theEncodedLinks, theBit - 1, aRghNode, aPosition, theFinal);
 153
 154     theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
 155     theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
 156     return aNode;
 157   }
 158   else
 159   {
 160     // Build leaf node
 161     return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1);
 162   }
 163 }
 164
 165 namespace BVH
 166 {
 167   //! Calculates bounding boxes (AABBs) for the given BVH tree.
 168   template<class T, int N>
 169   Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0)
 170   {
 171     const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
 172     if (aData.x() == 0)
 173     {
 174       const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
 175       const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
 176
 177       const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
 178       const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
 179
 180       typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
 181       typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
 182       typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
 183       typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
 184
 185       BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 186       BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 187
 188       theTree->MinPointBuffer()[theNode] = aLftMinPoint;
 189       theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
 190       return Max (aLftDepth, aRghDepth) + 1;
 191     }
 192     else
 193     {
 194       typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
 195       typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
 196       for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
 197       {
 198         const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
 199         if (aPrimIdx == aData.y())
 200         {
 201           aMinPoint = aBox.CornerMin();
 202           aMaxPoint = aBox.CornerMax();
 203         }
 204         else
 205         {
 206           BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
 207           BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
 208         }
 209       }
 210     }
 211     return 0;
 212   }
 213
 214   template<class T, int N>
 215   struct BoundData
 216   {
 217     BVH_Set <T, N>*   mySet;    //!< Set of geometric objects
 218     BVH_Tree<T, N>*   myBVH;    //!< BVH tree built over the set
 219     Standard_Integer  myNode;   //!< BVH node to update bounding box
 220     Standard_Integer  myLevel;  //!< Level of the processed BVH node
 221     Standard_Integer* myHeight; //!< Height of the processed BVH node
 222   };
 223
 224   //! Task for parallel bounds updating.
 225   template<class T, int N>
 226   class UpdateBoundTask
 227   {
 228   public:
 229
 230     UpdateBoundTask (const Standard_Boolean isParallel)
 231     : myIsParallel (isParallel)
 232     {
 233     }
 234
 235     //! Executes the task.
 236     void operator()(const BoundData<T, N>& theData) const
 237     {
 238       if (theData.myBVH->IsOuter (theData.myNode) || theData.myLevel > 2)
 239       {
 240         *theData.myHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, theData.myNode);
 241       }
 242       else
 243       {
 244         Standard_Integer aLftHeight = 0;
 245         Standard_Integer aRghHeight = 0;
 246
 247         const Standard_Integer aLftChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].y();
 248         const Standard_Integer aRghChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].z();
 249
 250         std::vector<BoundData<T, N> > aList;
 251         aList.reserve (2);
 252         if (!theData.myBVH->IsOuter (aLftChild))
 253         {
 254           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aLftChild, theData.myLevel + 1, &aLftHeight};
 255           aList.push_back (aBoundData);
 256         }
 257         else
 258         {
 259           aLftHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aLftChild);
 260         }
 261
 262         if (!theData.myBVH->IsOuter (aRghChild))
 263         {
 264           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aRghChild, theData.myLevel + 1, &aRghHeight};
 265           aList.push_back (aBoundData);
 266         }
 267         else
 268         {
 269           aRghHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aRghChild);
 270         }
 271
 272         if (!aList.empty())
 273         {
 274           OSD_Parallel::ForEach (aList.begin (), aList.end (), UpdateBoundTask<T, N> (myIsParallel), !myIsParallel);
 275         }
 276
 277         typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theData.myBVH->MinPointBuffer()[aLftChild];
 278         typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theData.myBVH->MaxPointBuffer()[aLftChild];
 279         typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theData.myBVH->MinPointBuffer()[aRghChild];
 280         typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theData.myBVH->MaxPointBuffer()[aRghChild];
 281
 282         BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 283         BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 284
 285         theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint;
 286         theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint;
 287
 288         *theData.myHeight = Max (aLftHeight, aRghHeight) + 1;
 289       }
 290     }
 291
 292   private:
 293
 294     Standard_Boolean myIsParallel;
 295   };
 296 }
 297
 298 // =======================================================================
 299 // function : Build
 300 // purpose  :
 301 // =======================================================================
 302 template<class T, int N>
 303 void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
 304                                      BVH_Tree<T, N>*      theBVH,
 305                                      const BVH_Box<T, N>& theBox) const
 306 {
 307   Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
 308   const Standard_Integer aSetSize = theSet->Size();
 309   if (theBVH == NULL || aSetSize == 0)
 310   {
 311     return;
 312   }
 313
 314   theBVH->Clear();
 315
 316   // Step 0 -- Initialize parameter of virtual grid
 317   BVH_RadixSorter<T, N> aRadixSorter (theBox);
 318   aRadixSorter.SetParallel (this->IsParallel());
 319
 320   // Step 1 - Perform radix sorting of primitive set
 321   aRadixSorter.Perform (theSet);
 322
 323   // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
 324   emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
 325
 326   // Step 3 -- Compute bounding boxes of BVH nodes
 327   theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 328   theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 329
 330   Standard_Integer aHeight = 0;
 331   BVH::BoundData<T, N> aBoundData = { theSet, theBVH, 0, 0, &aHeight };
 332   BVH::UpdateBoundTask<T, N> aBoundTask (this->IsParallel());
 333   aBoundTask (aBoundData);
 334
 335   BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
 336 }
 337
 338 #endif // _BVH_LinearBuilder_Header