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