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 | |
3c4e78f2 |
50 | //! Returns minimum point of the given node. |
51 | BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) |
52 | { |
679d3878 |
53 | return BVH::Array<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex); |
3c4e78f2 |
54 | } |
55 | |
56 | //! Returns maximum point of the given node. |
57 | BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) |
58 | { |
679d3878 |
59 | return BVH::Array<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex); |
3c4e78f2 |
60 | } |
61 | |
62 | //! Returns minimum point of the given node. |
63 | const BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) const |
64 | { |
679d3878 |
65 | return BVH::Array<T, N>::Value (myMinPointBuffer, theNodeIndex); |
3c4e78f2 |
66 | } |
67 | |
68 | //! Returns maximum point of the given node. |
69 | const BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) const |
70 | { |
679d3878 |
71 | return BVH::Array<T, N>::Value (myMaxPointBuffer, theNodeIndex); |
3c4e78f2 |
72 | } |
73 | |
74 | //! Returns index of left child of the given inner node. |
75 | Standard_Integer& LeftChild (const Standard_Integer theNodeIndex) |
76 | { |
679d3878 |
77 | return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
78 | } |
79 | |
80 | //! Returns index of left child of the given inner node. |
81 | Standard_Integer LeftChild (const Standard_Integer theNodeIndex) const |
82 | { |
679d3878 |
83 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
84 | } |
85 | |
86 | //! Returns index of right child of the given inner node. |
87 | Standard_Integer& RightChild (const Standard_Integer theNodeIndex) |
88 | { |
679d3878 |
89 | return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
90 | } |
91 | |
92 | //! Returns index of right child of the given inner node. |
93 | Standard_Integer RightChild (const Standard_Integer theNodeIndex) const |
94 | { |
679d3878 |
95 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
96 | } |
97 | |
98 | //! Returns index of first primitive of the given leaf node. |
99 | Standard_Integer& BegPrimitive (const Standard_Integer theNodeIndex) |
100 | { |
679d3878 |
101 | return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
102 | } |
103 | |
104 | //! Returns index of first primitive of the given leaf node. |
105 | Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const |
106 | { |
679d3878 |
107 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
108 | } |
109 | |
110 | //! Returns index of last primitive of the given leaf node. |
111 | Standard_Integer& EndPrimitive (const Standard_Integer theNodeIndex) |
112 | { |
679d3878 |
113 | return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
114 | } |
115 | |
116 | //! Returns index of last primitive of the given leaf node. |
117 | Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const |
118 | { |
679d3878 |
119 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
120 | } |
121 | |
122 | //! Returns number of primitives for the given tree node. |
123 | Standard_Integer NbPrimitives (const Standard_Integer theNodeIndex) const |
124 | { |
125 | return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1; |
126 | } |
127 | |
128 | //! Returns level (depth) of the given node. |
129 | Standard_Integer& Level (const Standard_Integer theNodeIndex) |
130 | { |
679d3878 |
131 | return BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w(); |
3c4e78f2 |
132 | } |
133 | |
134 | //! Returns level (depth) of the given node. |
135 | Standard_Integer Level (const Standard_Integer theNodeIndex) const |
136 | { |
679d3878 |
137 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).w(); |
3c4e78f2 |
138 | } |
139 | |
140 | //! Is node a leaf (outer)? |
141 | Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const |
142 | { |
679d3878 |
143 | return BVH::Array<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() > 0; |
3c4e78f2 |
144 | } |
145 | |
146 | //! Sets node type to 'outer'. |
147 | void SetOuter (const Standard_Integer theNodeIndex) |
148 | { |
679d3878 |
149 | BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1; |
3c4e78f2 |
150 | } |
151 | |
152 | //! Sets node type to 'inner'. |
153 | void SetInner (const Standard_Integer theNodeIndex) |
154 | { |
679d3878 |
155 | BVH::Array<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 0; |
3c4e78f2 |
156 | } |
157 | |
158 | //! Returns total number of BVH nodes. |
159 | Standard_Integer Length() const |
160 | { |
679d3878 |
161 | return BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer); |
3c4e78f2 |
162 | } |
163 | |
fc73a202 |
164 | //! Returns depth of BVH tree from last build. |
165 | Standard_Integer Depth() const |
166 | { |
167 | return myDepth; |
168 | } |
169 | |
3c4e78f2 |
170 | public: |
171 | |
172 | //! Removes all BVH nodes. |
173 | void Clear(); |
174 | |
175 | //! Adds new leaf node to the BVH. |
176 | Standard_Integer AddLeafNode (const BVH_VecNt& theMinPoint, |
177 | const BVH_VecNt& theMaxPoint, |
178 | const Standard_Integer theBegElem, |
179 | const Standard_Integer theEndElem); |
180 | |
181 | //! Adds new inner node to the BVH. |
182 | Standard_Integer AddInnerNode (const BVH_VecNt& theMinPoint, |
183 | const BVH_VecNt& theMaxPoint, |
184 | const Standard_Integer theLftChild, |
185 | const Standard_Integer theRghChild); |
186 | |
187 | //! Adds new leaf node to the BVH. |
188 | Standard_Integer AddLeafNode (const BVH_Box<T, N>& theAABB, |
189 | const Standard_Integer theBegElem, |
190 | const Standard_Integer theEndElem); |
191 | |
192 | //! Adds new inner node to the BVH. |
193 | Standard_Integer AddInnerNode (const BVH_Box<T, N>& theAABB, |
194 | const Standard_Integer theLftChild, |
195 | const Standard_Integer theRghChild); |
196 | |
0ef61b50 |
197 | //! Adds new leaf node to the BVH with UNINITIALIZED bounds. |
198 | Standard_Integer AddLeafNode (const Standard_Integer theBegElem, |
199 | const Standard_Integer theEndElem); |
200 | |
201 | //! Adds new inner node to the BVH with UNINITIALIZED bounds. |
202 | Standard_Integer AddInnerNode (const Standard_Integer theLftChild, |
203 | const Standard_Integer theRghChild); |
204 | |
3c4e78f2 |
205 | //! Returns value of SAH (surface area heuristic). |
206 | //! Allows to compare the quality of BVH trees constructed for |
207 | //! the same sets of geometric objects with different methods. |
208 | T EstimateSAH() const; |
209 | |
210 | public: |
211 | |
212 | //! Returns array of node min points. |
3a7a7013 |
213 | typename BVH::ArrayType<T, N>::Type& MinPointBuffer() |
3c4e78f2 |
214 | { |
215 | return myMinPointBuffer; |
216 | } |
217 | |
218 | //! Returns array of node min points. |
3a7a7013 |
219 | const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const |
3c4e78f2 |
220 | { |
221 | return myMinPointBuffer; |
222 | } |
223 | |
224 | //! Returns array of node max points. |
3a7a7013 |
225 | typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() |
3c4e78f2 |
226 | { |
227 | return myMaxPointBuffer; |
228 | } |
229 | |
230 | //! Returns array of node max points. |
3a7a7013 |
231 | const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const |
3c4e78f2 |
232 | { |
233 | return myMaxPointBuffer; |
234 | } |
235 | |
236 | //! Returns array of node data records. |
237 | BVH_Array4i& NodeInfoBuffer() |
238 | { |
239 | return myNodeInfoBuffer; |
240 | } |
241 | |
242 | //! Returns array of node data records. |
243 | const BVH_Array4i& NodeInfoBuffer() const |
244 | { |
245 | return myNodeInfoBuffer; |
246 | } |
247 | |
248 | protected: |
249 | |
250 | //! Array of node minimum points. |
3a7a7013 |
251 | typename BVH::ArrayType<T, N>::Type myMinPointBuffer; |
3c4e78f2 |
252 | |
253 | //! Array of node maximum points. |
3a7a7013 |
254 | typename BVH::ArrayType<T, N>::Type myMaxPointBuffer; |
3c4e78f2 |
255 | |
256 | //! Array of node data records. |
257 | BVH_Array4i myNodeInfoBuffer; |
258 | |
fc73a202 |
259 | //! Depth of constructed tree. |
260 | Standard_Integer myDepth; |
261 | |
3c4e78f2 |
262 | }; |
263 | |
264 | #include <BVH_Tree.lxx> |
265 | |
266 | #endif // _BVH_Tree_Header |