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 | // ======================================================================= |
17 | // function : BVH_BinnedBuilder |
18 | // purpose : |
19 | // ======================================================================= |
20 | template<class T, int N, int Bins> |
21 | BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize, |
22 | const Standard_Integer theMaxTreeDepth) |
23 | : BVH_Builder<T, N> (theLeafNodeSize, |
24 | theMaxTreeDepth) |
25 | { |
26 | // |
27 | } |
28 | |
29 | // ======================================================================= |
30 | // function : ~BVH_BinnedBuilder |
31 | // purpose : |
32 | // ======================================================================= |
33 | template<class T, int N, int Bins> |
34 | BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder() |
35 | { |
36 | // |
37 | } |
38 | |
3a7a7013 |
39 | namespace BVH |
40 | { |
41 | template<class T> |
42 | static inline Standard_Integer IntFloor (const T theValue) |
43 | { |
44 | const Standard_Integer aRes = static_cast<Standard_Integer> (theValue); |
45 | |
46 | return aRes - static_cast<Standard_Integer> (aRes > theValue); |
47 | } |
48 | } |
49 | |
3c4e78f2 |
50 | // ======================================================================= |
51 | // function : GetSubVolumes |
52 | // purpose : |
53 | // ======================================================================= |
54 | template<class T, int N, int Bins> |
55 | void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>* theSet, |
56 | BVH_Tree<T, N>* theBVH, |
57 | const Standard_Integer theNode, |
58 | BVH_BinVector& theBins, |
59 | const Standard_Integer theAxis) |
60 | { |
3a7a7013 |
61 | const T aMin = BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis); |
62 | const T aMax = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis); |
3c4e78f2 |
63 | |
3a7a7013 |
64 | const T anInverseStep = static_cast<T> (Bins) / (aMax - aMin); |
3c4e78f2 |
65 | |
66 | for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx) |
67 | { |
68 | typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx); |
69 | |
3a7a7013 |
70 | Standard_Integer aBinIndex = BVH::IntFloor<T> ( |
71 | (theSet->Center (anIdx, theAxis) - aMin) * anInverseStep); |
72 | |
3c4e78f2 |
73 | if (aBinIndex < 0) |
74 | { |
75 | aBinIndex = 0; |
76 | } |
77 | else if (aBinIndex >= Bins) |
78 | { |
79 | aBinIndex = Bins - 1; |
80 | } |
81 | |
82 | theBins[aBinIndex].Count++; |
83 | theBins[aBinIndex].Box.Combine (aBox); |
84 | } |
85 | } |
86 | |
3a7a7013 |
87 | namespace BVH |
3c4e78f2 |
88 | { |
89 | // ======================================================================= |
90 | // function : SplitPrimitives |
91 | // purpose : |
92 | // ======================================================================= |
93 | template<class T, int N> |
94 | Standard_Integer SplitPrimitives (BVH_Set<T, N>* theSet, |
95 | const BVH_Box<T, N>& theBox, |
96 | const Standard_Integer theBeg, |
97 | const Standard_Integer theEnd, |
98 | const Standard_Integer theBin, |
99 | const Standard_Integer theAxis, |
100 | const Standard_Integer theBins) |
101 | { |
3a7a7013 |
102 | const T aMin = BVH::VecComp<T, N>::Get (theBox.CornerMin(), theAxis); |
103 | const T aMax = BVH::VecComp<T, N>::Get (theBox.CornerMax(), theAxis); |
3c4e78f2 |
104 | |
3a7a7013 |
105 | const T anInverseStep = static_cast<T> (theBins) / (aMax - aMin); |
3c4e78f2 |
106 | |
107 | Standard_Integer aLftIdx (theBeg); |
108 | Standard_Integer aRghIdx (theEnd); |
109 | |
110 | do |
111 | { |
3a7a7013 |
112 | while (BVH::IntFloor<T> ((theSet->Center (aLftIdx, theAxis) - aMin) * anInverseStep) <= theBin && aLftIdx < theEnd) |
3c4e78f2 |
113 | { |
114 | ++aLftIdx; |
115 | } |
3a7a7013 |
116 | while (BVH::IntFloor<T> ((theSet->Center (aRghIdx, theAxis) - aMin) * anInverseStep) > theBin && aRghIdx > theBeg) |
3c4e78f2 |
117 | { |
118 | --aRghIdx; |
119 | } |
120 | |
121 | if (aLftIdx <= aRghIdx) |
122 | { |
123 | if (aLftIdx != aRghIdx) |
124 | { |
125 | theSet->Swap (aLftIdx, aRghIdx); |
126 | } |
127 | |
128 | ++aLftIdx; |
129 | --aRghIdx; |
130 | } |
131 | } while (aLftIdx <= aRghIdx); |
132 | |
133 | return aLftIdx; |
134 | } |
135 | } |
136 | |
137 | #if defined (_WIN32) && defined (max) |
138 | #undef max |
139 | #endif |
140 | |
141 | #include <limits> |
142 | |
143 | // ======================================================================= |
144 | // function : BuildNode |
145 | // purpose : |
146 | // ======================================================================= |
147 | template<class T, int N, int Bins> |
148 | void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>* theSet, |
149 | BVH_Tree<T, N>* theBVH, |
150 | const Standard_Integer theNode) |
151 | { |
228de226 |
152 | const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); |
153 | const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); |
3c4e78f2 |
154 | |
228de226 |
155 | if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize) |
156 | { |
157 | return; // node does not require partitioning |
158 | } |
159 | |
160 | const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode), |
161 | theBVH->MaxPoint (theNode)); |
162 | |
163 | const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size(); |
3c4e78f2 |
164 | |
165 | // Parameters for storing best split |
166 | Standard_Integer aMinSplitAxis = -1; |
167 | Standard_Integer aMinSplitIndex = 0; |
168 | Standard_Integer aMinSplitNumLft = 0; |
169 | Standard_Integer aMinSplitNumRgh = 0; |
170 | |
171 | BVH_Box<T, N> aMinSplitBoxLft; |
172 | BVH_Box<T, N> aMinSplitBoxRgh; |
173 | |
174 | Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max(); |
175 | |
176 | // Find best split |
177 | for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) |
178 | { |
3a7a7013 |
179 | if (BVH::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE) |
3c4e78f2 |
180 | continue; |
181 | |
182 | BVH_BinVector aBins; |
183 | GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis); |
184 | |
185 | // Choose the best split (with minimum SAH cost) |
186 | for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit) |
187 | { |
188 | Standard_Integer aLftCount = 0; |
189 | Standard_Integer aRghCount = 0; |
190 | |
191 | BVH_Box<T, N> aLftAABB; |
192 | BVH_Box<T, N> aRghAABB; |
193 | |
194 | for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex) |
195 | { |
196 | aLftCount += aBins[anIndex].Count; |
197 | aLftAABB.Combine (aBins[anIndex].Box); |
198 | } |
199 | |
200 | for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex) |
201 | { |
202 | aRghCount += aBins[anIndex].Count; |
203 | aRghAABB.Combine (aBins[anIndex].Box); |
204 | } |
205 | |
206 | // Simple SAH evaluation |
207 | Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount |
208 | + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount; |
209 | |
210 | if (aCost <= aMinSplitCost) |
211 | { |
212 | aMinSplitCost = aCost; |
213 | aMinSplitAxis = anAxis; |
214 | aMinSplitIndex = aSplit; |
215 | aMinSplitBoxLft = aLftAABB; |
216 | aMinSplitBoxRgh = aRghAABB; |
217 | aMinSplitNumLft = aLftCount; |
218 | aMinSplitNumRgh = aRghCount; |
219 | } |
220 | } |
221 | } |
222 | |
3c4e78f2 |
223 | theBVH->SetInner (theNode); |
224 | |
228de226 |
225 | Standard_Integer aMiddle = -1; |
226 | |
61aa7f3d |
227 | if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0 || aMinSplitAxis == -1) // case of objects with the same center |
228de226 |
228 | { |
229 | aMinSplitBoxLft.Clear(); |
230 | aMinSplitBoxRgh.Clear(); |
231 | |
232 | aMiddle = std::max (aNodeBegPrimitive + 1, |
233 | static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f)); |
234 | |
235 | aMinSplitNumLft = aMiddle - aNodeBegPrimitive; |
236 | |
237 | for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex) |
238 | { |
239 | aMinSplitBoxLft.Combine (theSet->Box (anIndex)); |
240 | } |
241 | |
242 | aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1; |
243 | |
244 | for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex) |
245 | { |
246 | aMinSplitBoxRgh.Combine (theSet->Box (anIndex)); |
247 | } |
248 | } |
249 | else |
250 | { |
3a7a7013 |
251 | aMiddle = BVH::SplitPrimitives<T, N> (theSet, anAABB, |
228de226 |
252 | aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins); |
253 | } |
3c4e78f2 |
254 | |
255 | static const Standard_Integer aLftNode = 1; |
256 | static const Standard_Integer aRghNode = 2; |
257 | |
258 | // Setting up tasks for child nodes |
259 | for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) |
260 | { |
261 | typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode) |
262 | ? aMinSplitBoxLft.CornerMin() |
263 | : aMinSplitBoxRgh.CornerMin(); |
264 | typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode) |
265 | ? aMinSplitBoxLft.CornerMax() |
266 | : aMinSplitBoxRgh.CornerMax(); |
267 | |
268 | Standard_Integer aBegPrimitive = (aSide == aLftNode) |
228de226 |
269 | ? aNodeBegPrimitive |
3c4e78f2 |
270 | : aMiddle; |
271 | Standard_Integer aEndPrimitive = (aSide == aLftNode) |
272 | ? aMiddle - 1 |
228de226 |
273 | : aNodeEndPrimitive; |
3c4e78f2 |
274 | |
275 | Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive); |
276 | |
277 | theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; |
278 | |
279 | // Check to see if child node must be split |
280 | const Standard_Integer aNbPimitives = (aSide == aLftNode) |
281 | ? aMinSplitNumLft |
282 | : aMinSplitNumRgh; |
283 | |
284 | if (aSide == aLftNode) |
285 | theBVH->LeftChild (theNode) = aChildIndex; |
286 | else |
287 | theBVH->RightChild (theNode) = aChildIndex; |
288 | |
289 | const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize |
290 | || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth; |
291 | |
292 | if (!isLeaf) |
fc73a202 |
293 | { |
3c4e78f2 |
294 | BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex); |
fc73a202 |
295 | } |
296 | |
297 | BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex)); |
3c4e78f2 |
298 | } |
299 | } |