Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-30 08:45:56 

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   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
0037 
0038 public:
0039   //! Creates binned LBVH builder.
0040   BVH_LinearBuilder(const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
0041                     const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth);
0042 
0043   //! Releases resources of LBVH builder.
0044   virtual ~BVH_LinearBuilder();
0045 
0046   //! Builds BVH.
0047   virtual void Build(BVH_Set<T, N>*       theSet,
0048                      BVH_Tree<T, N>*      theBVH,
0049                      const BVH_Box<T, N>& theBox) const Standard_OVERRIDE;
0050 
0051 protected:
0052   typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
0053 
0054 protected:
0055   //! Emits hierarchy from sorted Morton codes.
0056   Standard_Integer emitHierachy(BVH_Tree<T, N>*                            theBVH,
0057                                 const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0058                                 const Standard_Integer                     theBit,
0059                                 const Standard_Integer                     theShift,
0060                                 const Standard_Integer                     theStart,
0061                                 const Standard_Integer                     theFinal) const;
0062 
0063   //! Returns index of the first element which does not compare less than the given one.
0064   Standard_Integer lowerBound(const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0065                               Standard_Integer                           theStart,
0066                               Standard_Integer                           theFinal,
0067                               Standard_Integer                           theDigit) const;
0068 };
0069 
0070 // =======================================================================
0071 // function : BVH_LinearBuilder
0072 // purpose  :
0073 // =======================================================================
0074 template <class T, int N>
0075 BVH_LinearBuilder<T, N>::BVH_LinearBuilder(const Standard_Integer theLeafNodeSize,
0076                                            const Standard_Integer theMaxTreeDepth)
0077     : BVH_Builder<T, N>(theLeafNodeSize, theMaxTreeDepth)
0078 {
0079   //
0080 }
0081 
0082 // =======================================================================
0083 // function : ~BVH_LinearBuilder
0084 // purpose  :
0085 // =======================================================================
0086 template <class T, int N>
0087 BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
0088 {
0089   //
0090 }
0091 
0092 // =======================================================================
0093 // function : lowerBound
0094 // purpose  : Returns index of first element greater than the given one
0095 // =======================================================================
0096 template <class T, int N>
0097 Standard_Integer BVH_LinearBuilder<T, N>::lowerBound(
0098   const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0099   Standard_Integer                           theStart,
0100   Standard_Integer                           theFinal,
0101   Standard_Integer                           theDigit) const
0102 {
0103   Standard_Integer aNbPrims = theFinal - theStart;
0104   unsigned int     aBit     = 1U << theDigit;
0105   while (aNbPrims > 0)
0106   {
0107     const Standard_Integer aStep = aNbPrims / 2;
0108     if (theEncodedLinks.Value(theStart + aStep).first & aBit)
0109     {
0110       aNbPrims = aStep;
0111     }
0112     else
0113     {
0114       theStart += aStep + 1;
0115       aNbPrims -= aStep + 1;
0116     }
0117   }
0118 
0119   return theStart;
0120 }
0121 
0122 // =======================================================================
0123 // function : emitHierachy
0124 // purpose  : Emits hierarchy from sorted Morton codes
0125 // =======================================================================
0126 template <class T, int N>
0127 Standard_Integer BVH_LinearBuilder<T, N>::emitHierachy(
0128   BVH_Tree<T, N>*                            theBVH,
0129   const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
0130   const Standard_Integer                     theDigit,
0131   const Standard_Integer                     theShift,
0132   const Standard_Integer                     theStart,
0133   const Standard_Integer                     theFinal) const
0134 {
0135   if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
0136   {
0137     const Standard_Integer aPosition =
0138       theDigit < 0 ? (theStart + theFinal) / 2
0139                    : lowerBound(theEncodedLinks, theStart, theFinal, theDigit);
0140     if (aPosition == theStart || aPosition == theFinal)
0141     {
0142       return emitHierachy(theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, theFinal);
0143     }
0144 
0145     // Build inner node
0146     const Standard_Integer aNode    = theBVH->AddInnerNode(0, 0);
0147     const Standard_Integer aRghNode = theShift + aPosition - theStart;
0148 
0149     const Standard_Integer aLftChild =
0150       emitHierachy(theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, aPosition);
0151     const Standard_Integer aRghChild =
0152       emitHierachy(theBVH, theEncodedLinks, theDigit - 1, aRghNode, aPosition, theFinal);
0153 
0154     theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
0155     theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
0156     return aNode;
0157   }
0158   else
0159   {
0160     // Build leaf node
0161     return theBVH->AddLeafNode(theShift, theShift + theFinal - theStart - 1);
0162   }
0163 }
0164 
0165 namespace BVH
0166 {
0167 //! Calculates bounding boxes (AABBs) for the given BVH tree.
0168 template <class T, int N>
0169 Standard_Integer UpdateBounds(BVH_Set<T, N>*         theSet,
0170                               BVH_Tree<T, N>*        theTree,
0171                               const Standard_Integer theNode = 0)
0172 {
0173   const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
0174   if (aData.x() == 0)
0175   {
0176     const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
0177     const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
0178 
0179     const Standard_Integer aLftDepth = UpdateBounds(theSet, theTree, aLftChild);
0180     const Standard_Integer aRghDepth = UpdateBounds(theSet, theTree, aRghChild);
0181 
0182     typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
0183     typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
0184     typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
0185     typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
0186 
0187     BVH::BoxMinMax<T, N>::CwiseMin(aLftMinPoint, aRghMinPoint);
0188     BVH::BoxMinMax<T, N>::CwiseMax(aLftMaxPoint, aRghMaxPoint);
0189 
0190     theTree->MinPointBuffer()[theNode] = aLftMinPoint;
0191     theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
0192     return Max(aLftDepth, aRghDepth) + 1;
0193   }
0194   else
0195   {
0196     typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
0197     typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
0198     for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
0199     {
0200       const BVH_Box<T, N> aBox = theSet->Box(aPrimIdx);
0201       if (aPrimIdx == aData.y())
0202       {
0203         aMinPoint = aBox.CornerMin();
0204         aMaxPoint = aBox.CornerMax();
0205       }
0206       else
0207       {
0208         BVH::BoxMinMax<T, N>::CwiseMin(aMinPoint, aBox.CornerMin());
0209         BVH::BoxMinMax<T, N>::CwiseMax(aMaxPoint, aBox.CornerMax());
0210       }
0211     }
0212   }
0213   return 0;
0214 }
0215 
0216 template <class T, int N>
0217 struct BoundData
0218 {
0219   BVH_Set<T, N>*    mySet;    //!< Set of geometric objects
0220   BVH_Tree<T, N>*   myBVH;    //!< BVH tree built over the set
0221   Standard_Integer  myNode;   //!< BVH node to update bounding box
0222   Standard_Integer  myLevel;  //!< Level of the processed BVH node
0223   Standard_Integer* myHeight; //!< Height of the processed BVH node
0224 };
0225 
0226 //! Task for parallel bounds updating.
0227 template <class T, int N>
0228 class UpdateBoundTask
0229 {
0230 public:
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,
0256                                       theData.myBVH,
0257                                       aLftChild,
0258                                       theData.myLevel + 1,
0259                                       &aLftHeight};
0260         aList.push_back(aBoundData);
0261       }
0262       else
0263       {
0264         aLftHeight = BVH::UpdateBounds(theData.mySet, theData.myBVH, aLftChild);
0265       }
0266 
0267       if (!theData.myBVH->IsOuter(aRghChild))
0268       {
0269         BoundData<T, N> aBoundData = {theData.mySet,
0270                                       theData.myBVH,
0271                                       aRghChild,
0272                                       theData.myLevel + 1,
0273                                       &aRghHeight};
0274         aList.push_back(aBoundData);
0275       }
0276       else
0277       {
0278         aRghHeight = BVH::UpdateBounds(theData.mySet, theData.myBVH, aRghChild);
0279       }
0280 
0281       if (!aList.empty())
0282       {
0283         OSD_Parallel::ForEach(aList.begin(),
0284                               aList.end(),
0285                               UpdateBoundTask<T, N>(myIsParallel),
0286                               !myIsParallel);
0287       }
0288 
0289       typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theData.myBVH->MinPointBuffer()[aLftChild];
0290       typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theData.myBVH->MaxPointBuffer()[aLftChild];
0291       typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theData.myBVH->MinPointBuffer()[aRghChild];
0292       typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theData.myBVH->MaxPointBuffer()[aRghChild];
0293 
0294       BVH::BoxMinMax<T, N>::CwiseMin(aLftMinPoint, aRghMinPoint);
0295       BVH::BoxMinMax<T, N>::CwiseMax(aLftMaxPoint, aRghMaxPoint);
0296 
0297       theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint;
0298       theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint;
0299 
0300       *theData.myHeight = Max(aLftHeight, aRghHeight) + 1;
0301     }
0302   }
0303 
0304 private:
0305   Standard_Boolean myIsParallel;
0306 };
0307 } // namespace BVH
0308 
0309 // =======================================================================
0310 // function : Build
0311 // purpose  :
0312 // =======================================================================
0313 template <class T, int N>
0314 void BVH_LinearBuilder<T, N>::Build(BVH_Set<T, N>*       theSet,
0315                                     BVH_Tree<T, N>*      theBVH,
0316                                     const BVH_Box<T, N>& theBox) const
0317 {
0318   Standard_STATIC_ASSERT(N == 2 || N == 3 || N == 4);
0319   const Standard_Integer aSetSize = theSet->Size();
0320   if (theBVH == NULL || aSetSize == 0)
0321   {
0322     return;
0323   }
0324 
0325   theBVH->Clear();
0326 
0327   // Step 0 -- Initialize parameter of virtual grid
0328   BVH_RadixSorter<T, N> aRadixSorter(theBox);
0329   aRadixSorter.SetParallel(this->IsParallel());
0330 
0331   // Step 1 - Perform radix sorting of primitive set
0332   aRadixSorter.Perform(theSet);
0333 
0334   // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
0335   emitHierachy(theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
0336 
0337   // Step 3 -- Compute bounding boxes of BVH nodes
0338   theBVH->MinPointBuffer().resize(theBVH->NodeInfoBuffer().size());
0339   theBVH->MaxPointBuffer().resize(theBVH->NodeInfoBuffer().size());
0340 
0341   Standard_Integer           aHeight    = 0;
0342   BVH::BoundData<T, N>       aBoundData = {theSet, theBVH, 0, 0, &aHeight};
0343   BVH::UpdateBoundTask<T, N> aBoundTask(this->IsParallel());
0344   aBoundTask(aBoundData);
0345 
0346   BVH_Builder<T, N>::updateDepth(theBVH, aHeight);
0347 }
0348 
0349 #endif // _BVH_LinearBuilder_Header
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!