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