0024473: TKMath, BVH - introduce template-based package for Bounding volume hierarchy...
[occt.git] / src / BVH / BVH_SweepPlaneBuilder.lxx
1 // Created on: 2014-01-09
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 #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   // Parameters for storing best split
55   Standard_Integer aMinSplitAxis = -1;
56   Standard_Integer aMinSplitIndex = 0;
57
58   Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives];
59   Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives];
60
61   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
62
63   // Find best split
64   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
65   {
66     const T aNodeSize = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) -
67                         BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis);
68     if (aNodeSize <= THE_NODE_MIN_SIZE)
69     {
70       continue;
71     }
72
73     BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive);
74
75     BVH_Box<T, N> aLftBox;
76     BVH_Box<T, N> aRghBox;
77
78     *aLftSet = std::numeric_limits<T>::max();
79     *aRghSet = std::numeric_limits<T>::max();
80
81     // Sweep from left
82     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
83     {
84       aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1));
85
86       aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area());
87     }
88
89     // Sweep from right
90     for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex)
91     {
92       aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1));
93
94       aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area());
95     }
96
97     // Find best split using simplified SAH
98     for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh)
99     {
100       Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft +
101                             (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh;
102
103       if (aCost < aMinSplitCost)
104       {
105         aMinSplitCost = aCost;
106         aMinSplitAxis = anAxis;
107         aMinSplitIndex = aNbLft;
108       }
109     }
110   }
111
112   if (aMinSplitAxis == -1)
113   {
114     return;
115   }
116
117   theBVH->SetInner (theNode);
118
119   if (aMinSplitAxis != (N < 4 ? N - 1 : 2))
120   {
121     BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive);
122   }
123
124   BVH_Box<T, N> aMinSplitBoxLft;
125   BVH_Box<T, N> aMinSplitBoxRgh;
126
127   // Compute bounding boxes for selected split plane
128   for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex)
129   {
130     aMinSplitBoxLft.Combine (theSet->Box (anIndex));
131   }
132
133   for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex)
134   {
135     aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
136   }
137
138   const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex;
139
140   static const Standard_Integer aLftNode = 1;
141   static const Standard_Integer aRghNode = 2;
142
143   // Setting up tasks for child nodes
144   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
145   {
146     typename BVH_Box<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode)
147                                                      ? aMinSplitBoxLft.CornerMin()
148                                                      : aMinSplitBoxRgh.CornerMin();
149     typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode)
150                                                      ? aMinSplitBoxLft.CornerMax()
151                                                      : aMinSplitBoxRgh.CornerMax();
152
153     Standard_Integer aChildBegPrimitive = (aSide == aLftNode)
154                                         ? aNodeBegPrimitive
155                                         : aMiddle;
156     Standard_Integer aChildEndPrimitive = (aSide == aLftNode)
157                                         ? aMiddle - 1
158                                         : aNodeEndPrimitive;
159
160     Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint,
161                                                         aChildBegPrimitive, aChildEndPrimitive);
162
163     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
164
165     // Check to see if child node must be split
166     const Standard_Integer aChildNbPimitives = (aSide == aLftNode)
167                                              ? aMiddle - aNodeBegPrimitive
168                                              : aNodeEndPrimitive - aMiddle + 1;
169
170     if (aSide == aLftNode)
171       theBVH->LeftChild (theNode) = aChildIndex;
172     else
173       theBVH->RightChild (theNode) = aChildIndex;
174
175     const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
176                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
177
178     if (!isLeaf)
179     {
180       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
181     }
182   }
183 }