1 // Created on: 2013-12-20
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 // =======================================================================
17 // function : BVH_BinnedBuilder
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_QueueBuilder<T, N> (theLeafNodeSize,
29 // =======================================================================
30 // function : ~BVH_BinnedBuilder
32 // =======================================================================
33 template<class T, int N, int Bins>
34 BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
39 // =======================================================================
40 // function : GetSubVolumes
42 // =======================================================================
43 template<class T, int N, int Bins>
44 void 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)
50 const T aMin = BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
51 const T aMax = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
53 const T anInverseStep = static_cast<T> (Bins) / (aMax - aMin);
55 for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
57 typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
59 Standard_Integer aBinIndex = BVH::IntFloor<T> (
60 (theSet->Center (anIdx, theAxis) - aMin) * anInverseStep);
66 else if (aBinIndex >= Bins)
71 theBins[aBinIndex].Count++;
72 theBins[aBinIndex].Box.Combine (aBox);
78 // =======================================================================
79 // function : SplitPrimitives
81 // =======================================================================
82 template<class T, int N>
83 Standard_Integer SplitPrimitives (BVH_Set<T, N>* theSet,
84 const BVH_Box<T, N>& theBox,
85 const Standard_Integer theBeg,
86 const Standard_Integer theEnd,
87 const Standard_Integer theBin,
88 const Standard_Integer theAxis,
89 const Standard_Integer theBins)
91 const T aMin = BVH::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
92 const T aMax = BVH::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
94 const T anInverseStep = static_cast<T> (theBins) / (aMax - aMin);
96 Standard_Integer aLftIdx (theBeg);
97 Standard_Integer aRghIdx (theEnd);
101 while (BVH::IntFloor<T> ((theSet->Center (aLftIdx, theAxis) - aMin) * anInverseStep) <= theBin && aLftIdx < theEnd)
105 while (BVH::IntFloor<T> ((theSet->Center (aRghIdx, theAxis) - aMin) * anInverseStep) > theBin && aRghIdx > theBeg)
110 if (aLftIdx <= aRghIdx)
112 if (aLftIdx != aRghIdx)
114 theSet->Swap (aLftIdx, aRghIdx);
120 } while (aLftIdx <= aRghIdx);
126 #if defined (_WIN32) && defined (max)
132 // =======================================================================
133 // function : BuildNode
135 // =======================================================================
136 template<class T, int N, int Bins>
137 void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>* theSet,
138 BVH_Tree<T, N>* theBVH,
139 const Standard_Integer theNode)
141 const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
142 const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
144 if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
146 return; // node does not require partitioning
149 const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
150 theBVH->MaxPoint (theNode));
152 const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();
154 // Parameters for storing best split
155 Standard_Integer aMinSplitAxis = -1;
156 Standard_Integer aMinSplitIndex = 0;
157 Standard_Integer aMinSplitNumLft = 0;
158 Standard_Integer aMinSplitNumRgh = 0;
160 BVH_Box<T, N> aMinSplitBoxLft;
161 BVH_Box<T, N> aMinSplitBoxRgh;
163 Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
166 for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
168 if (BVH::VecComp<T, N>::Get (aSize, anAxis) <= BVH::THE_NODE_MIN_SIZE)
172 GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);
174 // Choose the best split (with minimum SAH cost)
175 for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
177 Standard_Integer aLftCount = 0;
178 Standard_Integer aRghCount = 0;
180 BVH_Box<T, N> aLftAABB;
181 BVH_Box<T, N> aRghAABB;
183 for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex)
185 aLftCount += aBins[anIndex].Count;
186 aLftAABB.Combine (aBins[anIndex].Box);
189 for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
191 aRghCount += aBins[anIndex].Count;
192 aRghAABB.Combine (aBins[anIndex].Box);
195 // Simple SAH evaluation
196 Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
197 + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;
199 if (aCost <= aMinSplitCost)
201 aMinSplitCost = aCost;
202 aMinSplitAxis = anAxis;
203 aMinSplitIndex = aSplit;
204 aMinSplitBoxLft = aLftAABB;
205 aMinSplitBoxRgh = aRghAABB;
206 aMinSplitNumLft = aLftCount;
207 aMinSplitNumRgh = aRghCount;
212 theBVH->SetInner (theNode);
214 Standard_Integer aMiddle = -1;
216 if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0 || aMinSplitAxis == -1) // case of objects with the same center
218 aMinSplitBoxLft.Clear();
219 aMinSplitBoxRgh.Clear();
221 aMiddle = std::max (aNodeBegPrimitive + 1,
222 static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));
224 aMinSplitNumLft = aMiddle - aNodeBegPrimitive;
226 for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
228 aMinSplitBoxLft.Combine (theSet->Box (anIndex));
231 aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;
233 for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
235 aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
240 aMiddle = BVH::SplitPrimitives<T, N> (theSet, anAABB,
241 aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins);
244 static const Standard_Integer aLftNode = 1;
245 static const Standard_Integer aRghNode = 2;
247 // Setting up tasks for child nodes
248 for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
250 typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
251 ? aMinSplitBoxLft.CornerMin()
252 : aMinSplitBoxRgh.CornerMin();
253 typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode)
254 ? aMinSplitBoxLft.CornerMax()
255 : aMinSplitBoxRgh.CornerMax();
257 Standard_Integer aBegPrimitive = (aSide == aLftNode)
260 Standard_Integer aEndPrimitive = (aSide == aLftNode)
264 Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);
266 theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
268 // Check to see if child node must be split
269 const Standard_Integer aNbPimitives = (aSide == aLftNode)
273 if (aSide == aLftNode)
274 theBVH->LeftChild (theNode) = aChildIndex;
276 theBVH->RightChild (theNode) = aChildIndex;
278 const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
279 || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
283 BVH_QueueBuilder<T, N>::myTasksQueue.Append (aChildIndex);
286 BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));