0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[occt.git] / src / BVH / BVH_SweepPlaneBuilder.lxx
1 // Created on: 2014-01-09
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 #include <BVH_Sorter.hxx>
17
18 // =======================================================================
19 // function : BVH_SweepPlaneBuilder
20 // purpose  :
21 // =======================================================================
22 template<class T, int N>
23 BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize,
24                                                     const Standard_Integer theMaxTreeDepth)
25 : BVH_Builder<T, N> (theLeafNodeSize,
26                      theMaxTreeDepth)
27 {
28   //
29 }
30
31 // =======================================================================
32 // function : ~BVH_SweepPlaneBuilder
33 // purpose  :
34 // =======================================================================
35 template<class T, int N>
36 BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder()
37 {
38   //
39 }
40
41 // =======================================================================
42 // function : BuildNode
43 // purpose  :
44 // =======================================================================
45 template<class T, int N>
46 void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>*         theSet,
47                                              BVH_Tree<T, N>*        theBVH,
48                                              const Standard_Integer theNode)
49 {
50   const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
51   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
52   const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode);
53
54   if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
55   {
56     return; // node does not require partitioning
57   }
58
59   // Parameters for storing best split
60   Standard_Integer aMinSplitAxis = -1;
61   Standard_Integer aMinSplitIndex = 0;
62
63   Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
64   Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
65
66   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
67
68   // Find best split
69   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
70   {
71     const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
72                         BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
73     if (aNodeSize <= THE_NODE_MIN_SIZE)
74     {
75       continue;
76     }
77
78     BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
79
80     BVH_Box<T, N> aLftBox;
81     BVH_Box<T, N> aRghBox;
82
83     *aLftSet = std::numeric_limits<T>::max();
84     *aRghSet = std::numeric_limits<T>::max();
85
86     // Sweep from left
87     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
88     {
89       aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
90
91       aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
92     }
93
94     // Sweep from right
95     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
96     {
97       aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
98
99       aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
100     }
101
102     // Find best split using simplified SAH
103     for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
104     {
105       Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
106                             (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
107
108       if (aCost < aMinSplitCost)
109       {
110         aMinSplitCost = aCost;
111         aMinSplitAxis = anAxis;
112         aMinSplitIndex = aNbLft;
113       }
114     }
115   }
116
117   if (aMinSplitAxis == -1)
118   {
119     return;
120   }
121
122   theBVH->SetInner (theNode);
123
124   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
125   {
126     BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
127   }
128
129   BVH_Box<T, N> aMinSplitBoxLft;
130   BVH_Box<T, N> aMinSplitBoxRgh;
131
132   // Compute bounding boxes for selected split plane
133   for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
134   {
135     aMinSplitBoxLft.Combine (theSet->Box (anIndex));
136   }
137
138   for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
139   {
140     aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
141   }
142
143   const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
144
145   static const Standard_Integer aLftNode = 1;
146   static const Standard_Integer aRghNode = 2;
147
148   // Setting up tasks for child nodes
149   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
150   {
151     typename BVH_Box<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode)
152                                                      ? aMinSplitBoxLft.CornerMin()
153                                                      : aMinSplitBoxRgh.CornerMin();
154     typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode)
155                                                      ? aMinSplitBoxLft.CornerMax()
156                                                      : aMinSplitBoxRgh.CornerMax();
157
158     Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
159                                         ? aNodeBegPrimitive
160                                         : aMiddle;
161     Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
162                                         ? aMiddle - 1
163                                         : aNodeEndPrimitive;
164
165     Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
166                                                         aChildBegPrimitive, aChildEndPrimitive);
167
168     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
169
170     // Check to see if child node must be split
171     const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
172                                              ? aMiddle - aNodeBegPrimitive
173                                              : aNodeEndPrimitive - aMiddle + 1;
174
175     if (aSide == aLftNode)
176       theBVH->LeftChild (theNode) = aChildIndex;
177     else
178       theBVH->RightChild (theNode) = aChildIndex;
179
180     const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
181                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
182
183     if (!isLeaf)
184     {
185       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
186     }
187
188     BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex));
189   }
190 }