c2aee79389b084c1a5bcdbcbc82aae4cee331864
[occt.git] / 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 #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 // =======================================================================
306 template<class T, int N>
307 void 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 {
311   Standard_STATIC_ASSERT (N == 3 || N == 4);
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
349
350   BVH_Builder<T, N>::updateDepth (theBVH, aHeight);
351 }
352
353 #endif // _BVH_LinearBuilder_Header