0024473: TKMath, BVH - introduce template-based package for Bounding volume hierarchy...
[occt.git] / src / BVH / BVH_BinnedBuilder.lxx
1 // Created on: 2013-12-20
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013 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
8 // under the terms of the GNU Lesser General Public 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 // =======================================================================
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
39 // =======================================================================
40 // function : GetSubVolumes
41 // purpose  :
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)
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
74 namespace 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 // =======================================================================
134 template<class T, int N, int Bins>
135 void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
136                                                BVH_Tree<T, N>*        theBVH,
137                                                const Standard_Integer theNode)
138 {
139   const BVH_Box<T, N> aBox (theBVH->MinPoint (theNode),
140                             theBVH->MaxPoint (theNode));
141
142   const typename BVH_Box<T, N>::BVH_VecNt aSize = aBox.Size();
143
144   // Parameters for storing best split
145   Standard_Integer aMinSplitAxis   = -1;
146   Standard_Integer aMinSplitIndex  =  0;
147   Standard_Integer aMinSplitNumLft =  0;
148   Standard_Integer aMinSplitNumRgh =  0;
149
150   BVH_Box<T, N> aMinSplitBoxLft;
151   BVH_Box<T, N> aMinSplitBoxRgh;
152
153   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
154
155   // Find best split
156   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
157   {
158     if (BVHTools::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE)
159       continue;
160
161     BVH_BinVector aBins;
162     GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);
163
164     // Choose the best split (with minimum SAH cost)
165     for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
166     {
167       Standard_Integer aLftCount = 0;
168       Standard_Integer aRghCount = 0;
169
170       BVH_Box<T, N> aLftAABB;
171       BVH_Box<T, N> aRghAABB;
172
173       for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex)
174       {
175         aLftCount += aBins[anIndex].Count;
176         aLftAABB.Combine (aBins[anIndex].Box);
177       }
178
179       for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
180       {
181         aRghCount += aBins[anIndex].Count;
182         aRghAABB.Combine (aBins[anIndex].Box);
183       }
184
185       // Simple SAH evaluation
186       Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
187                           + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;
188
189       if (aCost <= aMinSplitCost)
190       {
191         aMinSplitCost   = aCost;
192         aMinSplitAxis   = anAxis;
193         aMinSplitIndex  = aSplit;
194         aMinSplitBoxLft = aLftAABB;
195         aMinSplitBoxRgh = aRghAABB;
196         aMinSplitNumLft = aLftCount;
197         aMinSplitNumRgh = aRghCount;
198       }
199     }
200   }
201
202   if (aMinSplitAxis == -1)
203   {
204     return;
205   }
206
207   theBVH->SetInner (theNode);
208
209   const Standard_Integer aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, aBox,
210                                                                     theBVH->BegPrimitive (theNode),
211                                                                     theBVH->EndPrimitive (theNode),
212                                                                     aMinSplitIndex - 1,
213                                                                     aMinSplitAxis,
214                                                                     Bins);
215
216   static const Standard_Integer aLftNode = 1;
217   static const Standard_Integer aRghNode = 2;
218
219   // Setting up tasks for child nodes
220   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
221   {
222     typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
223                                                 ? aMinSplitBoxLft.CornerMin()
224                                                 : aMinSplitBoxRgh.CornerMin();
225     typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode)
226                                                 ? aMinSplitBoxLft.CornerMax()
227                                                 : aMinSplitBoxRgh.CornerMax();
228
229     Standard_Integer aBegPrimitive = (aSide == aLftNode)
230                                    ? theBVH->BegPrimitive (theNode)
231                                    : aMiddle;
232     Standard_Integer aEndPrimitive = (aSide == aLftNode)
233                                    ? aMiddle - 1
234                                    : theBVH->EndPrimitive (theNode);
235
236     Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);
237
238     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
239
240     // Check to see if child node must be split
241     const Standard_Integer aNbPimitives = (aSide == aLftNode)
242                                         ? aMinSplitNumLft
243                                         : aMinSplitNumRgh;
244
245     if (aSide == aLftNode)
246       theBVH->LeftChild  (theNode) = aChildIndex;
247     else
248       theBVH->RightChild (theNode) = aChildIndex;
249
250     const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
251                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
252
253     if (!isLeaf)
254       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
255   }
256 }