3c4e78f2 |
1 | // Created on: 2013-12-20 |
2 | // Created by: Denis BOGOLEPOV |
d5f74e42 |
3 | // Copyright (c) 2013-2014 OPEN CASCADE SAS |
3c4e78f2 |
4 | // |
5 | // This file is part of Open CASCADE Technology software library. |
6 | // |
d5f74e42 |
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 |
3c4e78f2 |
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 | |
0ef61b50 |
19 | #include <BVH_QueueBuilder.hxx> |
3c4e78f2 |
20 | |
a096a7a5 |
21 | #include <algorithm> |
22 | |
e28f12b3 |
23 | #if defined (_WIN32) && defined (max) |
24 | #undef max |
25 | #endif |
26 | |
27 | #include <limits> |
28 | |
65578e1c |
29 | //! Stores parameters of single bin (slice of AABB). |
3c4e78f2 |
30 | template<class T, int N> |
31 | struct BVH_Bin |
32 | { |
33 | //! Creates new node bin. |
34 | BVH_Bin() : Count (0) {} |
35 | |
36 | Standard_Integer Count; //!< Number of primitives in the bin |
228de226 |
37 | BVH_Box<T, N> Box; //!< AABB of primitives in the bin |
3c4e78f2 |
38 | }; |
39 | |
65578e1c |
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. |
f5b72419 |
46 | template<class T, int N, int Bins = BVH_Constants_NbBinsOptimal> |
0ef61b50 |
47 | class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N> |
3c4e78f2 |
48 | { |
49 | public: |
50 | |
a1c05aa5 |
51 | //! Type of the array of bins of BVH tree node. |
3c4e78f2 |
52 | typedef BVH_Bin<T, N> BVH_BinVector[Bins]; |
53 | |
a1c05aa5 |
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 | |
3c4e78f2 |
64 | public: |
65 | |
66 | //! Creates binned SAH BVH builder. |
f5b72419 |
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, |
e28f12b3 |
70 | const Standard_Integer theNumOfThreads = 1) |
71 | : BVH_QueueBuilder<T, N> (theLeafNodeSize, theMaxTreeDepth, theNumOfThreads), |
72 | myUseMainAxis (theDoMainSplits) |
73 | { |
74 | // |
75 | } |
3c4e78f2 |
76 | |
77 | //! Releases resources of binned SAH BVH builder. |
e28f12b3 |
78 | virtual ~BVH_BinnedBuilder() {} |
3c4e78f2 |
79 | |
80 | protected: |
81 | |
65578e1c |
82 | //! Performs splitting of the given BVH node. |
e28f12b3 |
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; |
3c4e78f2 |
86 | |
87 | //! Arranges node primitives into bins. |
e28f12b3 |
88 | virtual void getSubVolumes (BVH_Set<T, N>* theSet, |
3c4e78f2 |
89 | BVH_Tree<T, N>* theBVH, |
90 | const Standard_Integer theNode, |
91 | BVH_BinVector& theBins, |
e28f12b3 |
92 | const Standard_Integer theAxis) const; |
3c4e78f2 |
93 | |
f751596e |
94 | private: |
95 | |
96 | Standard_Boolean myUseMainAxis; //!< Defines whether to search for the best split or use the widest axis |
97 | |
3c4e78f2 |
98 | }; |
99 | |
e28f12b3 |
100 | // ======================================================================= |
101 | // function : getSubVolumes |
102 | // purpose : |
103 | // ======================================================================= |
104 | template<class T, int N, int Bins> |
105 | 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> |
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; |
181 | 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; |
198 | 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> |
210 | 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 | } |
3c4e78f2 |
321 | |
322 | #endif // _BVH_BinnedBuilder_Header |