7b7b661cd59901856ca370b4c07606f546c60f39
[occt.git] / src / BVH / BVH_Tree.hxx
1 // Created on: 2013-12-20
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 #ifndef _BVH_Tree_Header
17 #define _BVH_Tree_Header
18
19 #include <Standard_Type.hxx>
20
21 #include <BVH_Box.hxx>
22
23 //! Stores parameters of bounding volume hierarchy (BVH).
24 //! Bounding volume hierarchy (BVH) organizes geometric objects in
25 //! the tree based on spatial relationships. Each node in the tree
26 //! contains an axis-aligned bounding box of all the objects below
27 //! it. Bounding volume hierarchies are used in many algorithms to
28 //! support efficient operations on the sets of geometric objects,
29 //! such as collision detection, ray-tracing, searching of nearest
30 //! objects, and view frustum culling.
31 template<class T, int N>
32 class BVH_Tree
33 {
34 public:
35
36   typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
37
38 public:
39
40   //! Returns minimum point of the given node.
41   BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex)
42   {
43     return BVHTools::ArrayOp<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
44   }
45
46   //! Returns maximum point of the given node.
47   BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex)
48   {
49     return BVHTools::ArrayOp<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
50   }
51
52   //! Returns minimum point of the given node.
53   const BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) const
54   {
55     return BVHTools::ArrayOp<T, N>::Value (myMinPointBuffer, theNodeIndex);
56   }
57
58   //! Returns maximum point of the given node.
59   const BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) const
60   {
61     return BVHTools::ArrayOp<T, N>::Value (myMaxPointBuffer, theNodeIndex);
62   }
63
64   //! Returns index of left child of the given inner node.
65   Standard_Integer& LeftChild (const Standard_Integer theNodeIndex)
66   {
67     return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
68   }
69
70   //! Returns index of left child of the given inner node.
71   Standard_Integer LeftChild (const Standard_Integer theNodeIndex) const
72   {
73     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
74   }
75
76   //! Returns index of right child of the given inner node.
77   Standard_Integer& RightChild (const Standard_Integer theNodeIndex)
78   {
79     return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
80   }
81
82   //! Returns index of right child of the given inner node.
83   Standard_Integer RightChild (const Standard_Integer theNodeIndex) const
84   {
85     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
86   }
87
88   //! Returns index of first primitive of the given leaf node.
89   Standard_Integer& BegPrimitive (const Standard_Integer theNodeIndex)
90   {
91     return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
92   }
93
94   //! Returns index of first primitive of the given leaf node.
95   Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const
96   {
97     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
98   }
99
100   //! Returns index of last primitive of the given leaf node.
101   Standard_Integer& EndPrimitive (const Standard_Integer theNodeIndex)
102   {
103     return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
104   }
105
106   //! Returns index of last primitive of the given leaf node.
107   Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const
108   {
109     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
110   }
111
112   //! Returns number of primitives for the given tree node.
113   Standard_Integer NbPrimitives (const Standard_Integer theNodeIndex) const
114   {
115     return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1;
116   }
117
118   //! Returns level (depth) of the given node.
119   Standard_Integer& Level (const Standard_Integer theNodeIndex)
120   {
121     return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
122   }
123
124   //! Returns level (depth) of the given node.
125   Standard_Integer Level (const Standard_Integer theNodeIndex) const
126   {
127     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
128   }
129
130   //! Is node a leaf (outer)?
131   Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const
132   {
133     return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() > 0;
134   }
135
136   //! Sets node type to 'outer'.
137   void SetOuter (const Standard_Integer theNodeIndex)
138   {
139     BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1;
140   }
141
142   //! Sets node type to 'inner'.
143   void SetInner (const Standard_Integer theNodeIndex)
144   {
145     BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 0;
146   }
147
148   //! Returns total number of BVH nodes.
149   Standard_Integer Length() const
150   {
151     return BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer);
152   }
153
154 public:
155
156   //! Removes all BVH nodes.
157   void Clear();
158
159   //! Adds new leaf node to the BVH.
160   Standard_Integer AddLeafNode (const BVH_VecNt&       theMinPoint,
161                                 const BVH_VecNt&       theMaxPoint,
162                                 const Standard_Integer theBegElem,
163                                 const Standard_Integer theEndElem);
164
165   //! Adds new inner node to the BVH.
166   Standard_Integer AddInnerNode (const BVH_VecNt&       theMinPoint,
167                                  const BVH_VecNt&       theMaxPoint,
168                                  const Standard_Integer theLftChild,
169                                  const Standard_Integer theRghChild);
170
171   //! Adds new leaf node to the BVH.
172   Standard_Integer AddLeafNode (const BVH_Box<T, N>&   theAABB,
173                                 const Standard_Integer theBegElem,
174                                 const Standard_Integer theEndElem);
175
176   //! Adds new inner node to the BVH.
177   Standard_Integer AddInnerNode (const BVH_Box<T, N>&   theAABB,
178                                  const Standard_Integer theLftChild,
179                                  const Standard_Integer theRghChild);
180
181   //! Returns value of SAH (surface area heuristic).
182   //! Allows to compare the quality of BVH trees constructed for
183   //! the same sets of geometric objects with different methods.
184   T EstimateSAH() const;
185
186 public:
187
188   //! Returns array of node min points.
189   typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer()
190   {
191     return myMinPointBuffer;
192   }
193
194   //! Returns array of node min points.
195   const typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer() const
196   {
197     return myMinPointBuffer;
198   }
199
200   //! Returns array of node max points.
201   typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer()
202   {
203     return myMaxPointBuffer;
204   }
205
206   //! Returns array of node max points.
207   const typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer() const
208   {
209     return myMaxPointBuffer;
210   }
211
212   //! Returns array of node data records.
213   BVH_Array4i& NodeInfoBuffer()
214   {
215     return myNodeInfoBuffer;
216   }
217
218   //! Returns array of node data records.
219   const BVH_Array4i& NodeInfoBuffer() const
220   {
221     return myNodeInfoBuffer;
222   }
223
224 protected:
225
226   //! Array of node minimum points.
227   typename BVHTools::ArrayType<T, N>::Type myMinPointBuffer;
228
229   //! Array of node maximum points.
230   typename BVHTools::ArrayType<T, N>::Type myMaxPointBuffer;
231
232   //! Array of node data records.
233   BVH_Array4i myNodeInfoBuffer;
234
235 };
236
237 #include <BVH_Tree.lxx>
238
239 #endif // _BVH_Tree_Header