f2474958 |
1 | // Created on: 2016-06-20 |
2 | // Created by: Denis BOGOLEPOV |
3 | // Copyright (c) 2016 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 | #ifndef _BVH_BinaryTree_Header |
17 | #define _BVH_BinaryTree_Header |
18 | |
19 | #include <BVH_QuadTree.hxx> |
20 | |
e28f12b3 |
21 | #include <deque> |
22 | #include <tuple> |
23 | |
f2474958 |
24 | //! Specialization of binary BVH tree. |
25 | template<class T, int N> |
26 | class BVH_Tree<T, N, BVH_BinaryTree> : public BVH_TreeBase<T, N> |
27 | { |
28 | public: //! @name custom data types |
29 | |
30 | typedef typename BVH_TreeBase<T, N>::BVH_VecNt BVH_VecNt; |
31 | |
32 | public: //! @name methods for accessing individual nodes |
33 | |
34 | //! Creates new empty BVH tree. |
35 | BVH_Tree() : BVH_TreeBase<T, N>() { } |
36 | |
37 | //! Sets node type to 'outer'. |
e28f12b3 |
38 | void SetOuter (const int theNodeIndex) { BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 1; } |
f2474958 |
39 | |
40 | //! Sets node type to 'inner'. |
e28f12b3 |
41 | void SetInner (const int theNodeIndex) { BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 0; } |
42 | |
43 | //! Returns index of the K-th child of the given inner node. |
44 | //! \tparam K the index of node child (0 or 1) |
45 | template<int K> |
46 | int Child (const int theNodeIndex) const { return BVH::Array<int, 4>::Value (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; } |
f2474958 |
47 | |
48 | //! Returns index of the K-th child of the given inner node. |
49 | //! \tparam K the index of node child (0 or 1) |
50 | template<int K> |
e28f12b3 |
51 | int& ChangeChild (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; } |
f2474958 |
52 | |
53 | //! Returns index of the K-th child of the given inner node. |
54 | //! \tparam K the index of node child (0 or 1) |
55 | template<int K> |
e28f12b3 |
56 | int& Child (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; } |
f2474958 |
57 | |
58 | public: //! @name methods for adding/removing tree nodes |
59 | |
60 | //! Removes all nodes from the tree. |
e28f12b3 |
61 | void Clear() |
62 | { |
63 | this->myDepth = 0; |
64 | BVH::Array<T, N>::Clear (this->myMinPointBuffer); |
65 | BVH::Array<T, N>::Clear (this->myMaxPointBuffer); |
66 | BVH::Array<int, 4>::Clear(this->myNodeInfoBuffer); |
67 | } |
f2474958 |
68 | |
69 | //! Reserves internal BVH storage, so that it |
70 | //! can contain the given number of BVH nodes. |
e28f12b3 |
71 | void Reserve (const int theNbNodes) |
72 | { |
73 | BVH::Array<T, N>::Reserve (this->myMinPointBuffer, theNbNodes); |
74 | BVH::Array<T, N>::Reserve (this->myMaxPointBuffer, theNbNodes); |
75 | BVH::Array<int, 4>::Reserve (this->myNodeInfoBuffer, theNbNodes); |
76 | } |
f2474958 |
77 | |
78 | //! Adds new leaf node to the BVH. |
79 | int AddLeafNode (const BVH_VecNt& theMinPoint, |
80 | const BVH_VecNt& theMaxPoint, |
81 | const int theBegElem, |
e28f12b3 |
82 | const int theEndElem) |
83 | { |
84 | BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint); |
85 | BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint); |
86 | BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
87 | return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1; |
88 | } |
f2474958 |
89 | |
90 | //! Adds new inner node to the BVH. |
91 | int AddInnerNode (const BVH_VecNt& theMinPoint, |
92 | const BVH_VecNt& theMaxPoint, |
93 | const int theLftChild, |
e28f12b3 |
94 | const int theRghChild) |
95 | { |
96 | BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint); |
97 | BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint); |
98 | BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
99 | return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1; |
100 | } |
f2474958 |
101 | |
102 | //! Adds new leaf node to the BVH. |
103 | int AddLeafNode (const BVH_Box<T, N>& theAABB, |
104 | const int theBegElem, |
e28f12b3 |
105 | const int theEndElem) |
106 | { |
107 | return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem); |
108 | } |
f2474958 |
109 | |
110 | //! Adds new inner node to the BVH. |
111 | int AddInnerNode (const BVH_Box<T, N>& theAABB, |
112 | const int theLftChild, |
e28f12b3 |
113 | const int theRghChild) |
114 | { |
115 | return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild); |
116 | } |
f2474958 |
117 | |
118 | //! Adds new leaf node to the BVH with UNINITIALIZED bounds. |
119 | int AddLeafNode (const int theBegElem, |
e28f12b3 |
120 | const int theEndElem) |
121 | { |
122 | BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
123 | return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1; |
124 | } |
f2474958 |
125 | |
126 | //! Adds new inner node to the BVH with UNINITIALIZED bounds. |
127 | int AddInnerNode (const int theLftChild, |
e28f12b3 |
128 | const int theRghChild) |
129 | { |
130 | BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
131 | return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1; |
132 | } |
f2474958 |
133 | |
134 | public: //! @name methods specific to binary BVH |
135 | |
136 | //! Returns value of SAH (surface area heuristic). |
137 | //! Allows to compare the quality of BVH trees constructed for |
138 | //! the same sets of geometric objects with different methods. |
139 | T EstimateSAH() const; |
140 | |
141 | //! Collapses the tree into QBVH an returns it. As a result, each |
142 | //! 2-nd level of current tree is kept and the rest are discarded. |
143 | BVH_Tree<T, N, BVH_QuadTree>* CollapseToQuadTree() const; |
144 | |
145 | }; |
146 | |
e28f12b3 |
147 | namespace BVH |
148 | { |
149 | //! Internal function for recursive calculation of |
150 | //! surface area heuristic (SAH) of the given tree. |
151 | template<class T, int N> |
152 | void EstimateSAH (const BVH_Tree<T, N, BVH_BinaryTree>* theTree, const int theNode, T theProb, T& theSAH) |
153 | { |
154 | BVH_Box<T, N> aBox (theTree->MinPoint (theNode), |
155 | theTree->MaxPoint (theNode)); |
156 | |
157 | if (theTree->IsOuter (theNode)) |
158 | { |
159 | theSAH += theProb * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1); |
160 | } |
161 | else |
162 | { |
163 | theSAH += theProb * static_cast<T> (2.0); |
164 | |
165 | BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->template Child<0> (theNode)), |
166 | theTree->MaxPoint (theTree->template Child<0> (theNode))); |
167 | |
168 | if (theProb > 0.0) |
169 | { |
170 | EstimateSAH (theTree, theTree->template Child<0> (theNode), |
171 | theProb * aLftBox.Area() / aBox.Area(), theSAH); |
172 | } |
173 | |
174 | BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->template Child<1> (theNode)), |
175 | theTree->MaxPoint (theTree->template Child<1> (theNode))); |
176 | |
177 | if (theProb > 0.0) |
178 | { |
179 | EstimateSAH (theTree, theTree->template Child<1> (theNode), |
180 | theProb * aRghBox.Area() / aBox.Area(), theSAH); |
181 | } |
182 | } |
183 | } |
184 | } |
185 | |
186 | // ======================================================================= |
187 | // function : EstimateSAH |
188 | // purpose : |
189 | // ======================================================================= |
190 | template<class T, int N> |
191 | T BVH_Tree<T, N, BVH_BinaryTree>::EstimateSAH() const |
192 | { |
193 | T aSAH = static_cast<T> (0.0); |
194 | BVH::EstimateSAH<T, N> (this, 0, static_cast<T> (1.0), aSAH); |
195 | return aSAH; |
196 | } |
197 | |
198 | // ======================================================================= |
199 | // function : CollapseToQuadTree |
200 | // purpose : |
201 | // ======================================================================= |
202 | template<class T, int N> |
203 | BVH_Tree<T, N, BVH_QuadTree>* BVH_Tree<T, N, BVH_BinaryTree>::CollapseToQuadTree() const |
204 | { |
205 | BVH_Tree<T, N, BVH_QuadTree>* aQBVH = new BVH_Tree<T, N, BVH_QuadTree>; |
206 | |
207 | if (this->Length() == 0) |
208 | { |
209 | return aQBVH; |
210 | } |
211 | |
212 | std::deque<std::pair<int, int> > aQueue (1, std::make_pair (0, 0)); |
213 | |
214 | for (int aNbNodes = 1; !aQueue.empty();) |
215 | { |
216 | const std::pair<int, int> aNode = aQueue.front(); |
217 | |
218 | BVH::Array<T, N>::Append (aQBVH->myMinPointBuffer, BVH::Array<T, N>::Value (this->myMinPointBuffer, std::get<0> (aNode))); |
219 | BVH::Array<T, N>::Append (aQBVH->myMaxPointBuffer, BVH::Array<T, N>::Value (this->myMaxPointBuffer, std::get<0> (aNode))); |
220 | |
221 | BVH_Vec4i aNodeInfo; |
222 | if (this->IsOuter (std::get<0> (aNode))) // is leaf node |
223 | { |
224 | aNodeInfo = BVH_Vec4i (1 /* leaf flag */, |
225 | this->BegPrimitive (std::get<0> (aNode)), this->EndPrimitive (std::get<0> (aNode)), std::get<1> (aNode) /* level */); |
226 | } |
227 | else |
228 | { |
229 | NCollection_Vector<int> aGrandChildNodes; |
230 | |
231 | const int aLftChild = Child<0> (std::get<0> (aNode)); |
232 | const int aRghChild = Child<1> (std::get<0> (aNode)); |
233 | if (this->IsOuter (aLftChild)) // is leaf node |
234 | { |
235 | aGrandChildNodes.Append (aLftChild); |
236 | } |
237 | else |
238 | { |
239 | aGrandChildNodes.Append (Child<0> (aLftChild)); |
240 | aGrandChildNodes.Append (Child<1> (aLftChild)); |
241 | } |
242 | |
243 | if (this->IsOuter (aRghChild)) // is leaf node |
244 | { |
245 | aGrandChildNodes.Append (aRghChild); |
246 | } |
247 | else |
248 | { |
249 | aGrandChildNodes.Append (Child<0> (aRghChild)); |
250 | aGrandChildNodes.Append (Child<1> (aRghChild)); |
251 | } |
252 | |
253 | for (int aNodeIdx = 0; aNodeIdx < aGrandChildNodes.Size(); ++aNodeIdx) |
254 | { |
255 | aQueue.push_back (std::make_pair (aGrandChildNodes (aNodeIdx), std::get<1> (aNode) + 1)); |
256 | } |
257 | |
258 | aNodeInfo = BVH_Vec4i (0 /* inner flag */, |
259 | aNbNodes, aGrandChildNodes.Size() - 1, std::get<1> (aNode) /* level */); |
260 | |
261 | aQBVH->myDepth = Max (aQBVH->myDepth, std::get<1> (aNode) + 1); |
262 | |
263 | aNbNodes += aGrandChildNodes.Size(); |
264 | } |
265 | |
266 | BVH::Array<int, 4>::Append (aQBVH->myNodeInfoBuffer, aNodeInfo); |
267 | aQueue.pop_front(); // node processing completed |
268 | } |
269 | |
270 | return aQBVH; |
271 | } |
f2474958 |
272 | |
273 | #endif // _BVH_BinaryTree_Header |