0028824: Possibility to build OCCT 7.1.0 and above using Visual Studio 2008
[occt.git] / src / BVH / BVH_BinaryTree.hxx
CommitLineData
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.
25template<class T, int N>
26class BVH_Tree<T, N, BVH_BinaryTree> : public BVH_TreeBase<T, N>
27{
28public: //! @name custom data types
29
30 typedef typename BVH_TreeBase<T, N>::BVH_VecNt BVH_VecNt;
31
32public: //! @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
58public: //! @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
134public: //! @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 147namespace 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// =======================================================================
190template<class T, int N>
191T 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// =======================================================================
202template<class T, int N>
203BVH_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
71c810df 218 BVH::Array<T, N>::Append (aQBVH->myMinPointBuffer, BVH::Array<T, N>::Value (this->myMinPointBuffer, opencascade::std::get<0> (aNode)));
219 BVH::Array<T, N>::Append (aQBVH->myMaxPointBuffer, BVH::Array<T, N>::Value (this->myMaxPointBuffer, opencascade::std::get<0> (aNode)));
e28f12b3 220
221 BVH_Vec4i aNodeInfo;
71c810df 222 if (this->IsOuter (opencascade::std::get<0> (aNode))) // is leaf node
e28f12b3 223 {
224 aNodeInfo = BVH_Vec4i (1 /* leaf flag */,
71c810df 225 this->BegPrimitive (opencascade::std::get<0> (aNode)), this->EndPrimitive (opencascade::std::get<0> (aNode)), opencascade::std::get<1> (aNode) /* level */);
e28f12b3 226 }
227 else
228 {
229 NCollection_Vector<int> aGrandChildNodes;
230
71c810df 231 const int aLftChild = Child<0> (opencascade::std::get<0> (aNode));
232 const int aRghChild = Child<1> (opencascade::std::get<0> (aNode));
e28f12b3 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 {
71c810df 255 aQueue.push_back (std::make_pair (aGrandChildNodes (aNodeIdx), opencascade::std::get<1> (aNode) + 1));
e28f12b3 256 }
257
258 aNodeInfo = BVH_Vec4i (0 /* inner flag */,
71c810df 259 aNbNodes, aGrandChildNodes.Size() - 1, opencascade::std::get<1> (aNode) /* level */);
e28f12b3 260
71c810df 261 aQBVH->myDepth = Max (aQBVH->myDepth, opencascade::std::get<1> (aNode) + 1);
e28f12b3 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