0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[occt.git] / src / BVH / BVH_BinnedBuilder.lxx
1 // Created on: 2013-12-20
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013-2014 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 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.
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 Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
140   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
141
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();
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
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   }
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)
261                                    ? aNodeBegPrimitive
262                                    : aMiddle;
263     Standard_Integer aEndPrimitive = (aSide == aLftNode)
264                                    ? aMiddle - 1
265                                    : aNodeEndPrimitive;
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)
285     {
286       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
287     }
288
289     BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
290   }
291 }