1 // Created on: 2014-09-11
2 // Created by: Danila ULYANOV
3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef _BVH_LinearBuilder_Header
17 #define _BVH_LinearBuilder_Header
19 #include <BVH_RadixSorter.hxx>
20 #include <Standard_Assert.hxx>
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).
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>
37 typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
41 //! Creates binned LBVH builder.
42 BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
43 const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth);
45 //! Releases resources of LBVH builder.
46 virtual ~BVH_LinearBuilder();
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;
55 typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
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;
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;
75 // =======================================================================
76 // function : BVH_LinearBuilder
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,
88 // =======================================================================
89 // function : ~BVH_LinearBuilder
91 // =======================================================================
92 template<class T, int N>
93 BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
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
108 Standard_Integer aNbPrims = theFinal - theStart;
109 unsigned int aBit = 1U << theDigit;
112 const Standard_Integer aStep = aNbPrims / 2;
113 if (theEncodedLinks.Value (theStart + aStep).first & aBit)
119 theStart += aStep + 1;
120 aNbPrims -= aStep + 1;
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
139 if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
141 const Standard_Integer aPosition = theDigit < 0 ?
142 (theStart + theFinal) / 2 : lowerBound (theEncodedLinks, theStart, theFinal, theDigit);
143 if (aPosition == theStart || aPosition == theFinal)
145 return emitHierachy (theBVH, theEncodedLinks, theDigit - 1, theShift, theStart, theFinal);
149 const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
150 const Standard_Integer aRghNode = theShift + aPosition - theStart;
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);
155 theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
156 theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
162 return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1);
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)
172 const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
175 const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
176 const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
178 const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
179 const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
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];
186 BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
187 BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
189 theTree->MinPointBuffer()[theNode] = aLftMinPoint;
190 theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
191 return Max (aLftDepth, aRghDepth) + 1;
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)
199 const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
200 if (aPrimIdx == aData.y())
202 aMinPoint = aBox.CornerMin();
203 aMaxPoint = aBox.CornerMax();
207 BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
208 BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
215 template<class T, int N>
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
225 //! Task for parallel bounds updating.
226 template<class T, int N>
227 class UpdateBoundTask
231 UpdateBoundTask (const Standard_Boolean isParallel)
232 : myIsParallel (isParallel)
236 //! Executes the task.
237 void operator()(const BoundData<T, N>& theData) const
239 if (theData.myBVH->IsOuter (theData.myNode) || theData.myLevel > 2)
241 *theData.myHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, theData.myNode);
245 Standard_Integer aLftHeight = 0;
246 Standard_Integer aRghHeight = 0;
248 const Standard_Integer aLftChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].y();
249 const Standard_Integer aRghChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].z();
251 std::vector<BoundData<T, N> > aList;
253 if (!theData.myBVH->IsOuter (aLftChild))
255 BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aLftChild, theData.myLevel + 1, &aLftHeight};
256 aList.push_back (aBoundData);
260 aLftHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aLftChild);
263 if (!theData.myBVH->IsOuter (aRghChild))
265 BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aRghChild, theData.myLevel + 1, &aRghHeight};
266 aList.push_back (aBoundData);
270 aRghHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aRghChild);
275 OSD_Parallel::ForEach (aList.begin (), aList.end (), UpdateBoundTask<T, N> (myIsParallel), !myIsParallel);
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];
283 BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
284 BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
286 theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint;
287 theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint;
289 *theData.myHeight = Max (aLftHeight, aRghHeight) + 1;
295 Standard_Boolean myIsParallel;
299 // =======================================================================
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
308 Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
309 const Standard_Integer aSetSize = theSet->Size();
310 if (theBVH == NULL || aSetSize == 0)
317 // Step 0 -- Initialize parameter of virtual grid
318 BVH_RadixSorter<T, N> aRadixSorter (theBox);
319 aRadixSorter.SetParallel (this->IsParallel());
321 // Step 1 - Perform radix sorting of primitive set
322 aRadixSorter.Perform (theSet);
324 // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
325 emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
327 // Step 3 -- Compute bounding boxes of BVH nodes
328 theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
329 theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
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);
336 BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
339 #endif // _BVH_LinearBuilder_Header