0030131: Foundation Classes - support of Linear builder for 2D BVH trees
[occt.git] / src / BVH / BVH_LinearBuilder.hxx
CommitLineData
0ef61b50 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
3a507ddb 19#include <BVH_RadixSorter.hxx>
e28f12b3 20#include <Standard_Assert.hxx>
0ef61b50 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.
32template<class T, int N>
33class BVH_LinearBuilder : public BVH_Builder<T, N>
34{
35public:
36
37 typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
38
39public:
40
41 //! Creates binned LBVH builder.
f5b72419 42 BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
43 const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth);
0ef61b50 44
45 //! Releases resources of LBVH builder.
46 virtual ~BVH_LinearBuilder();
47
48 //! Builds BVH.
e28f12b3 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;
0ef61b50 52
53protected:
54
e28f12b3 55 typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator;
3a507ddb 56
57protected:
58
0ef61b50 59 //! Emits hierarchy from sorted Morton codes.
e28f12b3 60 Standard_Integer emitHierachy (BVH_Tree<T, N>* theBVH,
61 const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
3a507ddb 62 const Standard_Integer theBit,
63 const Standard_Integer theShift,
64 const Standard_Integer theStart,
e28f12b3 65 const Standard_Integer theFinal) const;
3a507ddb 66
67 //! Returns index of the first element which does not compare less than the given one.
e28f12b3 68 Standard_Integer lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks,
69 Standard_Integer theStart,
3a507ddb 70 Standard_Integer theFinal,
e28f12b3 71 Standard_Integer theDigit) const;
3a507ddb 72
e28f12b3 73};
3a507ddb 74
e28f12b3 75// =======================================================================
76// function : BVH_LinearBuilder
77// purpose :
78// =======================================================================
79template<class T, int N>
80BVH_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}
0ef61b50 87
e28f12b3 88// =======================================================================
89// function : ~BVH_LinearBuilder
90// purpose :
91// =======================================================================
92template<class T, int N>
93BVH_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// =======================================================================
102template<class T, int N>
103Standard_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// =======================================================================
130template<class T, int N>
131Standard_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
165namespace 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#ifdef HAVE_TBB
215
216 //! TBB task for parallel bounds updating.
217 template<class T, int N>
218 class UpdateBoundTask: public tbb::task
219 {
220
221 BVH_Set<T, N>* mySet; //!< Set of geometric objects
222 BVH_Tree<T, N>* myBVH; //!< BVH tree built over the set
223 Standard_Integer myNode; //!< BVH node to update bounding box
224 Standard_Integer myLevel; //!< Level of the processed BVH node
225 Standard_Integer* myHeight; //!< Height of the processed BVH node
226
227 public:
228
229 //! Creates new TBB parallel bound update task.
230 UpdateBoundTask (BVH_Set<T, N>* theSet,
231 BVH_Tree<T, N>* theBVH,
232 Standard_Integer theNode,
233 Standard_Integer theLevel,
234 Standard_Integer* theHeight)
235 : mySet (theSet), myBVH (theBVH), myNode (theNode), myLevel (theLevel), myHeight (theHeight) {}
236
237 //! Executes the task.
238 tbb::task* execute()
239 {
240 if (myBVH->IsOuter (myNode) || myLevel > 2)
241 {
242 *myHeight = BVH::UpdateBounds (mySet, myBVH, myNode);
243 }
244 else
245 {
246 Standard_Integer aLftHeight = 0;
247 Standard_Integer aRghHeight = 0;
248
249 const Standard_Integer aLftChild = myBVH->NodeInfoBuffer()[myNode].y();
250 const Standard_Integer aRghChild = myBVH->NodeInfoBuffer()[myNode].z();
251
252 Standard_Integer aCount = 1;
253 tbb::task_list aList;
254 if (!myBVH->IsOuter (aLftChild))
255 {
256 ++aCount;
257 aList.push_back (*new ( allocate_child() )
258 UpdateBoundTask (mySet, myBVH, aLftChild, myLevel + 1, &aLftHeight));
259 }
260 else
261 {
262 aLftHeight = BVH::UpdateBounds (mySet, myBVH, aLftChild);
263 }
264
265 if (!myBVH->IsOuter (aRghChild))
266 {
267 ++aCount;
268 aList.push_back (*new( allocate_child() )
269 UpdateBoundTask (mySet, myBVH, aRghChild, myLevel + 1, &aRghHeight));
270 }
271 else
272 {
273 aRghHeight = BVH::UpdateBounds (mySet, myBVH, aRghChild);
274 }
275
276 if (aCount > 1)
277 {
278 set_ref_count (aCount);
279 spawn_and_wait_for_all (aList);
280 }
281
282 typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = myBVH->MinPointBuffer()[aLftChild];
283 typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = myBVH->MaxPointBuffer()[aLftChild];
284 typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = myBVH->MinPointBuffer()[aRghChild];
285 typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = myBVH->MaxPointBuffer()[aRghChild];
286
287 BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
288 BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
289
290 myBVH->MinPointBuffer()[myNode] = aLftMinPoint;
291 myBVH->MaxPointBuffer()[myNode] = aLftMaxPoint;
292
293 *myHeight = Max (aLftHeight, aRghHeight) + 1;
294 }
295 return NULL;
296 }
297 };
298
299#endif
300}
301
302// =======================================================================
303// function : Build
304// purpose :
305// =======================================================================
306template<class T, int N>
307void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>* theSet,
308 BVH_Tree<T, N>* theBVH,
309 const BVH_Box<T, N>& theBox) const
310{
d0bcf7aa 311 Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
e28f12b3 312 const Standard_Integer aSetSize = theSet->Size();
313 if (theBVH == NULL || aSetSize == 0)
314 {
315 return;
316 }
317
318 theBVH->Clear();
319
320 // Step 0 -- Initialize parameter of virtual grid
321 BVH_RadixSorter<T, N> aRadixSorter (theBox);
322
323 // Step 1 - Perform radix sorting of primitive set
324 aRadixSorter.Perform (theSet);
325
326 // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
327 emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size());
328
329 // Step 3 -- Compute bounding boxes of BVH nodes
330 theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
331 theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
332
333 Standard_Integer aHeight = 0;
334
335#ifdef HAVE_TBB
336
337 // Note: Although TBB tasks are allocated using placement
338 // new, we do not need to delete them explicitly
339 BVH::UpdateBoundTask<T, N>& aRootTask = *new ( tbb::task::allocate_root() )
340 BVH::UpdateBoundTask<T, N> (theSet, theBVH, 0, 0, &aHeight);
341
342 tbb::task::spawn_root_and_wait (aRootTask);
343
344#else
345
346 aHeight = BVH::UpdateBounds (theSet, theBVH, 0);
347
348#endif
0ef61b50 349
e28f12b3 350 BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
351}
0ef61b50 352
353#endif // _BVH_LinearBuilder_Header