1 // Created on: 2013-12-20
2 // Created by: Denis BOGOLEPOV
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_BinnedBuilder_Header
17 #define _BVH_BinnedBuilder_Header
18
19 #include <BVH_QueueBuilder.hxx>
20
21 #include <algorithm>
22
23 #if defined (_WIN32) && defined (max)
24 #undef max
25 #endif
26
27 #include <limits>
28
29 //! Stores parameters of single bin (slice of AABB).
30 template<class T, int N>
31 struct BVH_Bin
32 {
33 //! Creates new node bin.
BVH_BinBVH_Bin34 BVH_Bin() : Count (0) {}
35
36 Standard_Integer Count; //!< Number of primitives in the bin
37 BVH_Box<T, N> Box; //!< AABB of primitives in the bin
38 };
39
40 //! Performs construction of BVH tree using binned SAH algorithm. Number
41 //! of bins controls BVH quality in cost of construction time (greater -
42 //! better). For optimal results, use 32 - 48 bins. However, reasonable
43 //! performance is provided even for 4 - 8 bins (it is only 10-20% lower
44 //! in comparison with optimal settings). Note that multiple threads can
45 //! be used only with thread safe BVH primitive sets.
46 template<class T, int N, int Bins = BVH_Constants_NbBinsOptimal>
47 class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
48 {
49 public:
50
51 //! Type of the array of bins of BVH tree node.
52 typedef BVH_Bin<T, N> BVH_BinVector[Bins];
53
54 //! Describes split plane candidate.
55 struct BVH_SplitPlane
56 {
57 BVH_Bin<T, N> LftVoxel;
58 BVH_Bin<T, N> RghVoxel;
59 };
60
61 //! Type of the array of split plane candidates.
62 typedef BVH_SplitPlane BVH_SplitPlanes[Bins + 1];
63
64 public:
65
66 //! Creates binned SAH BVH builder.
BVH_BinnedBuilder(const Standard_Integer theLeafNodeSize=BVH_Constants_LeafNodeSizeDefault,const Standard_Integer theMaxTreeDepth=BVH_Constants_MaxTreeDepth,const Standard_Boolean theDoMainSplits=Standard_False,const Standard_Integer theNumOfThreads=1)67 BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
68 const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth,
69 const Standard_Boolean theDoMainSplits = Standard_False,
70 const Standard_Integer theNumOfThreads = 1)
71 : BVH_QueueBuilder<T, N> (theLeafNodeSize, theMaxTreeDepth, theNumOfThreads),
72 myUseMainAxis (theDoMainSplits)
73 {
74 //
75 }
76
77 //! Releases resources of binned SAH BVH builder.
~BVH_BinnedBuilder()78 virtual ~BVH_BinnedBuilder() {}
79
80 protected:
81
82 //! Performs splitting of the given BVH node.
83 virtual typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>* theSet,
84 BVH_Tree<T, N>* theBVH,
85 const Standard_Integer theNode) const Standard_OVERRIDE;
86
87 //! Arranges node primitives into bins.
88 virtual void getSubVolumes (BVH_Set<T, N>* theSet,
89 BVH_Tree<T, N>* theBVH,
90 const Standard_Integer theNode,
91 BVH_BinVector& theBins,
92 const Standard_Integer theAxis) const;
93
94 private:
95
96 Standard_Boolean myUseMainAxis; //!< Defines whether to search for the best split or use the widest axis
97
98 };
99
100 // =======================================================================
101 // function : getSubVolumes
102 // purpose :
103 // =======================================================================
104 template<class T, int N, int Bins>
getSubVolumes(BVH_Set<T,N> * theSet,BVH_Tree<T,N> * theBVH,const Standard_Integer theNode,BVH_BinVector & theBins,const Standard_Integer theAxis) const105 void BVH_BinnedBuilder<T, N, Bins>::getSubVolumes (BVH_Set<T, N>* theSet,
106 BVH_Tree<T, N>* theBVH,
107 const Standard_Integer theNode,
108 BVH_BinVector& theBins,
109 const Standard_Integer theAxis) const
110 {
111 const T aMin = BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
112 const T aMax = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
113 const T anInverseStep = static_cast<T> (Bins) / (aMax - aMin);
114 for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
115 {
116 typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
117 Standard_Integer aBinIndex = BVH::IntFloor<T> ((theSet->Center (anIdx, theAxis) - aMin) * anInverseStep);
118 if (aBinIndex < 0)
119 {
120 aBinIndex = 0;
121 }
122 else if (aBinIndex >= Bins)
123 {
124 aBinIndex = Bins - 1;
125 }
126
127 theBins[aBinIndex].Count++;
128 theBins[aBinIndex].Box.Combine (aBox);
129 }
130 }
131
132 namespace BVH
133 {
134 template<class T, int N>
SplitPrimitives(BVH_Set<T,N> * theSet,const BVH_Box<T,N> & theBox,const Standard_Integer theBeg,const Standard_Integer theEnd,const Standard_Integer theBin,const Standard_Integer theAxis,const Standard_Integer theBins)135 Standard_Integer SplitPrimitives (BVH_Set<T, N>* theSet,
136 const BVH_Box<T, N>& theBox,
137 const Standard_Integer theBeg,
138 const Standard_Integer theEnd,
139 const Standard_Integer theBin,
140 const Standard_Integer theAxis,
141 const Standard_Integer theBins)
142 {
143 const T aMin = BVH::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
144 const T aMax = BVH::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
145
146 const T anInverseStep = static_cast<T> (theBins) / (aMax - aMin);
147
148 Standard_Integer aLftIdx (theBeg);
149 Standard_Integer aRghIdx (theEnd);
150
151 do
152 {
153 while (BVH::IntFloor<T> ((theSet->Center (aLftIdx, theAxis) - aMin) * anInverseStep) <= theBin && aLftIdx < theEnd)
154 {
155 ++aLftIdx;
156 }
157 while (BVH::IntFloor<T> ((theSet->Center (aRghIdx, theAxis) - aMin) * anInverseStep) > theBin && aRghIdx > theBeg)
158 {
159 --aRghIdx;
160 }
161
162 if (aLftIdx <= aRghIdx)
163 {
164 if (aLftIdx != aRghIdx)
165 {
166 theSet->Swap (aLftIdx, aRghIdx);
167 }
168
169 ++aLftIdx;
170 --aRghIdx;
171 }
172 } while (aLftIdx <= aRghIdx);
173
174 return aLftIdx;
175 }
176
177 template<class T, int N>
178 struct BVH_AxisSelector
179 {
180 typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
MainAxisBVH::BVH_AxisSelector181 static Standard_Integer MainAxis (const BVH_VecNt& theSize)
182 {
183 if (theSize.y() > theSize.x())
184 {
185 return theSize.y() > theSize.z() ? 1 : 2;
186 }
187 else
188 {
189 return theSize.z() > theSize.x() ? 2 : 0;
190 }
191 }
192 };
193
194 template<class T>
195 struct BVH_AxisSelector<T, 2>
196 {
197 typedef typename BVH::VectorType<T, 2>::Type BVH_VecNt;
MainAxisBVH::BVH_AxisSelector198 static Standard_Integer MainAxis (const BVH_VecNt& theSize)
199 {
200 return theSize.x() > theSize.y() ? 0 : 1;
201 }
202 };
203 }
204
205 // =======================================================================
206 // function : buildNode
207 // purpose :
208 // =======================================================================
209 template<class T, int N, int Bins>
buildNode(BVH_Set<T,N> * theSet,BVH_Tree<T,N> * theBVH,const Standard_Integer theNode) const210 typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_BinnedBuilder<T, N, Bins>::buildNode (BVH_Set<T, N>* theSet,
211 BVH_Tree<T, N>* theBVH,
212 const Standard_Integer theNode) const
213 {
214 const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
215 const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
216 if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
217 {
218 return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning
219 }
220
221 const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
222 theBVH->MaxPoint (theNode));
223 const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();
224
225 // Parameters for storing best split
226 Standard_Integer aMinSplitAxis = -1;
227 Standard_Integer aMinSplitIndex = 0;
228 Standard_Integer aMinSplitNumLft = 0;
229 Standard_Integer aMinSplitNumRgh = 0;
230
231 BVH_Box<T, N> aMinSplitBoxLft;
232 BVH_Box<T, N> aMinSplitBoxRgh;
233
234 Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
235 const Standard_Integer aMainAxis = BVH::BVH_AxisSelector<T, N>::MainAxis (aSize);
236
237 // Find best split
238 for (Standard_Integer anAxis = myUseMainAxis ? aMainAxis : 0; anAxis <= (myUseMainAxis ? aMainAxis : Min (N - 1, 2)); ++anAxis)
239 {
240 if (BVH::VecComp<T, N>::Get (aSize, anAxis) <= BVH::THE_NODE_MIN_SIZE)
241 {
242 continue;
243 }
244
245 BVH_BinVector aBinVector;
246 getSubVolumes (theSet, theBVH, theNode, aBinVector, anAxis);
247
248 BVH_SplitPlanes aSplitPlanes;
249 for (Standard_Integer aLftSplit = 1, aRghSplit = Bins - 1; aLftSplit < Bins; ++aLftSplit, --aRghSplit)
250 {
251 aSplitPlanes[aLftSplit].LftVoxel.Count = aSplitPlanes[aLftSplit - 1].LftVoxel.Count + aBinVector[aLftSplit - 1].Count;
252 aSplitPlanes[aRghSplit].RghVoxel.Count = aSplitPlanes[aRghSplit + 1].RghVoxel.Count + aBinVector[aRghSplit + 0].Count;
253
254 aSplitPlanes[aLftSplit].LftVoxel.Box = aSplitPlanes[aLftSplit - 1].LftVoxel.Box;
255 aSplitPlanes[aRghSplit].RghVoxel.Box = aSplitPlanes[aRghSplit + 1].RghVoxel.Box;
256
257 aSplitPlanes[aLftSplit].LftVoxel.Box.Combine (aBinVector[aLftSplit - 1].Box);
258 aSplitPlanes[aRghSplit].RghVoxel.Box.Combine (aBinVector[aRghSplit + 0].Box);
259 }
260
261 // Choose the best split (with minimum SAH cost)
262 for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
263 {
264 // Simple SAH evaluation
265 Standard_Real aCost =
266 (static_cast<Standard_Real> (aSplitPlanes[aSplit].LftVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].LftVoxel.Count
267 + (static_cast<Standard_Real> (aSplitPlanes[aSplit].RghVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].RghVoxel.Count;
268
269 if (aCost <= aMinSplitCost)
270 {
271 aMinSplitCost = aCost;
272 aMinSplitAxis = anAxis;
273 aMinSplitIndex = aSplit;
274 aMinSplitBoxLft = aSplitPlanes[aSplit].LftVoxel.Box;
275 aMinSplitBoxRgh = aSplitPlanes[aSplit].RghVoxel.Box;
276 aMinSplitNumLft = aSplitPlanes[aSplit].LftVoxel.Count;
277 aMinSplitNumRgh = aSplitPlanes[aSplit].RghVoxel.Count;
278 }
279 }
280 }
281
282 theBVH->SetInner (theNode);
283 Standard_Integer aMiddle = -1;
284 if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0 || aMinSplitAxis == -1) // case of objects with the same center
285 {
286 aMinSplitBoxLft.Clear();
287 aMinSplitBoxRgh.Clear();
288
289 aMiddle = std::max (aNodeBegPrimitive + 1,
290 static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));
291
292 aMinSplitNumLft = aMiddle - aNodeBegPrimitive;
293 for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
294 {
295 aMinSplitBoxLft.Combine (theSet->Box (anIndex));
296 }
297
298 aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;
299 for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
300 {
301 aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
302 }
303 }
304 else
305 {
306 aMiddle = BVH::SplitPrimitives<T, N> (theSet,
307 anAABB,
308 aNodeBegPrimitive,
309 aNodeEndPrimitive,
310 aMinSplitIndex - 1,
311 aMinSplitAxis,
312 Bins);
313 }
314
315 typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range;
316 return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft,
317 aMinSplitBoxRgh,
318 Range (aNodeBegPrimitive, aMiddle - 1),
319 Range (aMiddle, aNodeEndPrimitive));
320 }
321
322 #endif // _BVH_BinnedBuilder_Header
323