0028824: Possibility to build OCCT 7.1.0 and above using Visual Studio 2008
[occt.git] / src / BVH / BVH_BinaryTree.hxx
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
21 #include <deque>
22 #include <tuple>
23
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'.
38   void SetOuter (const int theNodeIndex) { BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 1; }
39
40   //! Sets node type to 'inner'.
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]; }
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>
51   int& ChangeChild (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; }
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>
56   int& Child (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; }
57
58 public: //! @name methods for adding/removing tree nodes
59
60   //! Removes all nodes from the tree.
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   }
68
69   //! Reserves internal BVH storage, so that it
70   //! can contain the given number of BVH nodes.
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   }
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,
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   }
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,
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   }
101
102   //! Adds new leaf node to the BVH.
103   int AddLeafNode (const BVH_Box<T, N>& theAABB,
104                    const int            theBegElem,
105                    const int            theEndElem)
106   {
107     return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem);
108   }
109
110   //! Adds new inner node to the BVH.
111   int AddInnerNode (const BVH_Box<T, N>& theAABB,
112                     const int            theLftChild,
113                     const int            theRghChild)
114   {
115     return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild);
116   }
117
118   //! Adds new leaf node to the BVH with UNINITIALIZED bounds.
119   int AddLeafNode (const int theBegElem,
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   }
125
126   //! Adds new inner node to the BVH with UNINITIALIZED bounds.
127   int AddInnerNode (const int theLftChild,
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   }
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
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, 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)));
220
221     BVH_Vec4i aNodeInfo;
222     if (this->IsOuter (opencascade::std::get<0> (aNode))) // is leaf node
223     {
224       aNodeInfo = BVH_Vec4i (1 /* leaf flag */,
225         this->BegPrimitive (opencascade::std::get<0> (aNode)), this->EndPrimitive (opencascade::std::get<0> (aNode)), opencascade::std::get<1> (aNode) /* level */);
226     }
227     else
228     {
229       NCollection_Vector<int> aGrandChildNodes;
230
231       const int aLftChild = Child<0> (opencascade::std::get<0> (aNode));
232       const int aRghChild = Child<1> (opencascade::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), opencascade::std::get<1> (aNode) + 1));
256       }
257
258       aNodeInfo = BVH_Vec4i (0 /* inner flag */,
259         aNbNodes, aGrandChildNodes.Size() - 1, opencascade::std::get<1> (aNode) /* level */);
260
261       aQBVH->myDepth = Max (aQBVH->myDepth, opencascade::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 }
272
273 #endif // _BVH_BinaryTree_Header