include/opencascade/BVH_LinearBuilder.hxx

0001 // Created on: 2014-09-11
0002 // Created by: Danila ULYANOV
0003 // Copyright (c) 2013-2014 OPEN CASCADE SAS
0004 //
0005 // This file is part of Open CASCADE Technology software library.
0006 //
0007 // This library is free software; you can redistribute it and/or modify it under
0008 // the terms of the GNU Lesser General Public License version 2.1 as published
0009 // by the Free Software Foundation, with special exception defined in the file
0010 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0011 // distribution for complete text of the license and disclaimer of any warranty.
0012 //
0013 // Alternatively, this file may be used under the terms of Open CASCADE
0014 // commercial license or contractual agreement.
0015
0016 #ifndef _BVH_LinearBuilder_Header
0017 #define _BVH_LinearBuilder_Header
0018
0019 #include <BVH_RadixSorter.hxx>
0020 #include <Standard_Assert.hxx>
0021
0022 //! Performs fast BVH construction using LBVH building approach.
0023 //! Algorithm uses spatial Morton codes to reduce the BVH construction
0024 //! problem to a sorting problem (radix sort -- O(N) complexity). This
0025 //! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
0026 //! of lower quality compared to SAH-based BVH builders but it is over
0027 //! an order of magnitude faster (up to 3M triangles per second).
0028 //!
0029 //! For more details see:
0030 //! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
0031 //! Fast BVH construction on GPUs. Eurographics, 2009.
0032 template<class T, int N>
0033 class BVH_LinearBuilder : public BVH_Builder<T, N>
0034 {
0035 public:
0036
0037   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
0038
0039 public:
0040
0041   //! Creates binned LBVH builder.
0042   BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
0043                      const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth);
0044
0045   //! Releases resources of LBVH builder.
0046   virtual ~BVH_LinearBuilder();
0047
0048   //! Builds BVH.
0049   virtual void Build (BVH_Set<T, N>*       theSet,
0050                       BVH_Tree<T, N>*      theBVH,
0051                       const BVH_Box<T, N>& theBox) const Standard_OVERRIDE;
0052
0053 protected:
0054
0055   typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
0056
0057 protected:
0058
0059   //! Emits hierarchy from sorted Morton codes.
0060   Standard_Integer emitHierachy (BVH_Tree<T, N>*        theBVH,
0061                                  const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0062                                  const Standard_Integer theBit,
0063                                  const Standard_Integer theShift,
0064                                  const Standard_Integer theStart,
0065                                  const Standard_Integer theFinal) const;
0066
0067   //! Returns index of the first element which does not compare less than the given one.
0068   Standard_Integer lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0069                                Standard_Integer theStart,
0070                                Standard_Integer theFinal,
0071                                Standard_Integer theDigit) const;
0072
0073 };
0074
0075 // =======================================================================
0076 // function : BVH_LinearBuilder
0077 // purpose  :
0078 // =======================================================================
0079 template<class T, int N>
0080 BVH_LinearBuilder<T, N>::BVH_LinearBuilder (const Standard_Integer theLeafNodeSize,
0081                                             const Standard_Integer theMaxTreeDepth)
0082 : BVH_Builder<T, N> (theLeafNodeSize,
0083                      theMaxTreeDepth)
0084 {
0085   //
0086 }
0087
0088 // =======================================================================
0089 // function : ~BVH_LinearBuilder
0090 // purpose  :
0091 // =======================================================================
0092 template<class T, int N>
0093 BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
0094 {
0095   //
0096 }
0097
0098 // =======================================================================
0099 // function : lowerBound
0100 // purpose  : Returns index of first element greater than the given one
0101 // =======================================================================
0102 template<class T, int N>
0103 Standard_Integer BVH_LinearBuilder<T, N>::lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0104                                                       Standard_Integer theStart,
0105                                                       Standard_Integer theFinal,
0106                                                       Standard_Integer theDigit) const
0107 {
0108   Standard_Integer aNbPrims = theFinal - theStart;
0109   unsigned int aBit = 1U << theDigit;
0110   while (aNbPrims > 0)
0111   {
0112     const Standard_Integer aStep = aNbPrims / 2;
0113     if (theEncodedLinks.Value (theStart + aStep).first & aBit)
0114     {
0115       aNbPrims = aStep;
0116     }
0117     else
0118     {
0119       theStart += aStep + 1;
0120       aNbPrims -= aStep + 1;
0121     }
0122   }
0123
0124   return theStart;
0125 }
0126
0127 // =======================================================================
0128 // function : emitHierachy
0129 // purpose  : Emits hierarchy from sorted Morton codes
0130 // =======================================================================
0131 template<class T, int N>
0132 Standard_Integer BVH_LinearBuilder<T, N>::emitHierachy (BVH_Tree<T, N>*        theBVH,
0133                                                         const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0134                                                         const Standard_Integer theDigit,
0135                                                         const Standard_Integer theShift,
0136                                                         const Standard_Integer theStart,
0137                                                         const Standard_Integer theFinal) const
0138 {
0139   if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
0140   {
0141     const Standard_Integer aPosition = theDigit < 0 ?
0142       (theStart + theFinal) / 2 : lowerBound (theEncodedLinks, theStart, theFinal, theDigit);
0143     if (aPosition == theStart || aPosition == theFinal)
0144     {
0145       return emitHierachy (theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, theFinal);
0146     }
0147
0148     // Build inner node
0149     const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
0150     const Standard_Integer aRghNode = theShift + aPosition - theStart;
0151
0152     const Standard_Integer aLftChild = emitHierachy (theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, aPosition);
0153     const Standard_Integer aRghChild = emitHierachy (theBVH, theEncodedLinks, theDigit - 1, aRghNode, aPosition, theFinal);
0154
0155     theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
0156     theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
0157     return aNode;
0158   }
0159   else
0160   {
0161     // Build leaf node
0162     return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1);
0163   }
0164 }
0165
0166 namespace BVH
0167 {
0168   //! Calculates bounding boxes (AABBs) for the given BVH tree.
0169   template<class T, int N>
0170   Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0)
0171   {
0172     const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
0173     if (aData.x() == 0)
0174     {
0175       const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
0176       const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
0177
0178       const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
0179       const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
0180
0181       typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
0182       typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
0183       typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
0184       typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
0185
0186       BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
0187       BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
0188
0189       theTree->MinPointBuffer()[theNode] = aLftMinPoint;
0190       theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
0191       return Max (aLftDepth, aRghDepth) + 1;
0192     }
0193     else
0194     {
0195       typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
0196       typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
0197       for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
0198       {
0199         const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
0200         if (aPrimIdx == aData.y())
0201         {
0202           aMinPoint = aBox.CornerMin();
0203           aMaxPoint = aBox.CornerMax();
0204         }
0205         else
0206         {
0207           BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
0208           BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
0209         }
0210       }
0211     }
0212     return 0;
0213   }
0214
0215   template<class T, int N>
0216   struct BoundData
0217   {
0218     BVH_Set <T, N>*   mySet;    //!< Set of geometric objects
0219     BVH_Tree<T, N>*   myBVH;    //!< BVH tree built over the set
0220     Standard_Integer  myNode;   //!< BVH node to update bounding box
0221     Standard_Integer  myLevel;  //!< Level of the processed BVH node
0222     Standard_Integer* myHeight; //!< Height of the processed BVH node
0223   };
0224
0225   //! Task for parallel bounds updating.
0226   template<class T, int N>
0227   class UpdateBoundTask
0228   {
0229   public:
0230
0231     UpdateBoundTask (const Standard_Boolean isParallel)
0232     : myIsParallel (isParallel)
0233     {
0234     }
0235
0236     //! Executes the task.
0237     void operator()(const BoundData<T, N>& theData) const
0238     {
0239       if (theData.myBVH->IsOuter (theData.myNode) || theData.myLevel > 2)
0240       {
0241         *theData.myHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, theData.myNode);
0242       }
0243       else
0244       {
0245         Standard_Integer aLftHeight = 0;
0246         Standard_Integer aRghHeight = 0;
0247
0248         const Standard_Integer aLftChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].y();
0249         const Standard_Integer aRghChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].z();
0250
0251         std::vector<BoundData<T, N> > aList;
0252         aList.reserve (2);
0253         if (!theData.myBVH->IsOuter (aLftChild))
0254         {
0255           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aLftChild, theData.myLevel + 1, &aLftHeight};
0256           aList.push_back (aBoundData);
0257         }
0258         else
0259         {
0260           aLftHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aLftChild);
0261         }
0262
0263         if (!theData.myBVH->IsOuter (aRghChild))
0264         {
0265           BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aRghChild, theData.myLevel + 1, &aRghHeight};
0266           aList.push_back (aBoundData);
0267         }
0268         else
0269         {
0270           aRghHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aRghChild);
0271         }
0272
0273         if (!aList.empty())
0274         {
0275           OSD_Parallel::ForEach (aList.begin (), aList.end (), UpdateBoundTask<T, N> (myIsParallel), !myIsParallel);
0276         }
0277
0278         typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theData.myBVH->MinPointBuffer()[aLftChild];
0279         typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theData.myBVH->MaxPointBuffer()[aLftChild];
0280         typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theData.myBVH->MinPointBuffer()[aRghChild];
0281         typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theData.myBVH->MaxPointBuffer()[aRghChild];
0282
0283         BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
0284         BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
0285
0286         theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint;
0287         theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint;
0288
0289         *theData.myHeight = Max (aLftHeight, aRghHeight) + 1;
0290       }
0291     }
0292
0293   private:
0294
0295     Standard_Boolean myIsParallel;
0296   };
0297 }
0298
0299 // =======================================================================
0300 // function : Build
0301 // purpose  :
0302 // =======================================================================
0303 template<class T, int N>
0304 void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
0305                                      BVH_Tree<T, N>*      theBVH,
0306                                      const BVH_Box<T, N>& theBox) const
0307 {
0308   Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
0309   const Standard_Integer aSetSize = theSet->Size();
0310   if (theBVH == NULL || aSetSize == 0)
0311   {
0312     return;
0313   }
0314
0315   theBVH->Clear();
0316
0317   // Step 0 -- Initialize parameter of virtual grid
0318   BVH_RadixSorter<T, N> aRadixSorter (theBox);
0319   aRadixSorter.SetParallel (this->IsParallel());
0320
0321   // Step 1 - Perform radix sorting of primitive set
0322   aRadixSorter.Perform (theSet);
0323
0324   // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
0325   emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
0326
0327   // Step 3 -- Compute bounding boxes of BVH nodes
0328   theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
0329   theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
0330
0331   Standard_Integer aHeight = 0;
0332   BVH::BoundData<T, N> aBoundData = { theSet, theBVH, 0, 0, &aHeight };
0333   BVH::UpdateBoundTask<T, N> aBoundTask (this->IsParallel());
0334   aBoundTask (aBoundData);
0335
0336   BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
0337 }
0338
0339 #endif // _BVH_LinearBuilder_Header