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 | |
f2474958 |
16 | #ifndef _BVH_TreeBase_Header |
17 | #define _BVH_TreeBase_Header |
3c4e78f2 |
18 | |
19 | #include <BVH_Box.hxx> |
20 | |
fc73a202 |
21 | template<class T, int N> class BVH_Builder; |
22 | |
f5b72419 |
23 | //! A non-template class for using as base for BVH_TreeBase |
24 | //! (just to have a named base class). |
25 | class BVH_TreeBaseTransient : public Standard_Transient |
26 | { |
27 | DEFINE_STANDARD_RTTIEXT(BVH_TreeBaseTransient, Standard_Transient) |
28 | protected: |
29 | BVH_TreeBaseTransient() {} |
0904aa63 |
30 | |
31 | //! Dumps the content of me into the stream |
32 | virtual void DumpJson (Standard_OStream& theOStream, const Standard_Integer theDepth = -1) const { (void)theOStream; (void)theDepth; } |
33 | |
34 | //! Dumps the content of me into the stream |
35 | virtual void DumpNode (const int theNodeIndex, Standard_OStream& theOStream, const Standard_Integer theDepth) const |
36 | { (void)theNodeIndex; (void)theOStream; (void)theDepth; } |
f5b72419 |
37 | }; |
38 | |
3c4e78f2 |
39 | //! Stores parameters of bounding volume hierarchy (BVH). |
40 | //! Bounding volume hierarchy (BVH) organizes geometric objects in |
41 | //! the tree based on spatial relationships. Each node in the tree |
42 | //! contains an axis-aligned bounding box of all the objects below |
43 | //! it. Bounding volume hierarchies are used in many algorithms to |
44 | //! support efficient operations on the sets of geometric objects, |
45 | //! such as collision detection, ray-tracing, searching of nearest |
46 | //! objects, and view frustum culling. |
47 | template<class T, int N> |
f5b72419 |
48 | class BVH_TreeBase : public BVH_TreeBaseTransient |
3c4e78f2 |
49 | { |
fc73a202 |
50 | friend class BVH_Builder<T, N>; |
51 | |
f2474958 |
52 | public: //! @name custom data types |
3c4e78f2 |
53 | |
54 | typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt; |
55 | |
f2474958 |
56 | public: //! @name general methods |
3c4e78f2 |
57 | |
fc73a202 |
58 | //! Creates new empty BVH tree. |
f2474958 |
59 | BVH_TreeBase() : myDepth (0) { } |
60 | |
61 | //! Releases resources of BVH tree. |
e28f12b3 |
62 | virtual ~BVH_TreeBase() {} |
f2474958 |
63 | |
64 | //! Returns depth (height) of BVH tree. |
65 | int Depth() const |
66 | { |
67 | return myDepth; |
68 | } |
69 | |
70 | //! Returns total number of BVH tree nodes. |
71 | int Length() const |
fc73a202 |
72 | { |
f2474958 |
73 | return BVH::Array<int, 4>::Size (myNodeInfoBuffer); |
fc73a202 |
74 | } |
75 | |
f2474958 |
76 | public: //! @name methods for accessing individual nodes |
65578e1c |
77 | |
3c4e78f2 |
78 | //! Returns minimum point of the given node. |
f2474958 |
79 | BVH_VecNt& MinPoint (const int theNodeIndex) |
3c4e78f2 |
80 | { |
679d3878 |
81 | return BVH::Array<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex); |
3c4e78f2 |
82 | } |
83 | |
84 | //! Returns maximum point of the given node. |
f2474958 |
85 | BVH_VecNt& MaxPoint (const int theNodeIndex) |
3c4e78f2 |
86 | { |
679d3878 |
87 | return BVH::Array<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex); |
3c4e78f2 |
88 | } |
89 | |
90 | //! Returns minimum point of the given node. |
f2474958 |
91 | const BVH_VecNt& MinPoint (const int theNodeIndex) const |
3c4e78f2 |
92 | { |
679d3878 |
93 | return BVH::Array<T, N>::Value (myMinPointBuffer, theNodeIndex); |
3c4e78f2 |
94 | } |
95 | |
96 | //! Returns maximum point of the given node. |
f2474958 |
97 | const BVH_VecNt& MaxPoint (const int theNodeIndex) const |
3c4e78f2 |
98 | { |
679d3878 |
99 | return BVH::Array<T, N>::Value (myMaxPointBuffer, theNodeIndex); |
3c4e78f2 |
100 | } |
101 | |
3c4e78f2 |
102 | //! Returns index of first primitive of the given leaf node. |
f2474958 |
103 | int& BegPrimitive (const int theNodeIndex) |
3c4e78f2 |
104 | { |
f2474958 |
105 | return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
106 | } |
107 | |
f2474958 |
108 | //! Returns index of last primitive of the given leaf node. |
109 | int& EndPrimitive (const int theNodeIndex) |
3c4e78f2 |
110 | { |
f2474958 |
111 | return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
112 | } |
113 | |
f2474958 |
114 | //! Returns index of first primitive of the given leaf node. |
115 | int BegPrimitive (const int theNodeIndex) const |
3c4e78f2 |
116 | { |
f2474958 |
117 | return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).y(); |
3c4e78f2 |
118 | } |
119 | |
120 | //! Returns index of last primitive of the given leaf node. |
f2474958 |
121 | int EndPrimitive (const int theNodeIndex) const |
3c4e78f2 |
122 | { |
f2474958 |
123 | return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).z(); |
3c4e78f2 |
124 | } |
125 | |
f2474958 |
126 | //! Returns number of primitives in the given leaf node. |
127 | int NbPrimitives (const int theNodeIndex) const |
3c4e78f2 |
128 | { |
129 | return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1; |
130 | } |
131 | |
132 | //! Returns level (depth) of the given node. |
f2474958 |
133 | int& Level (const int theNodeIndex) |
3c4e78f2 |
134 | { |
f2474958 |
135 | return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w(); |
3c4e78f2 |
136 | } |
137 | |
138 | //! Returns level (depth) of the given node. |
f2474958 |
139 | int Level (const int theNodeIndex) const |
3c4e78f2 |
140 | { |
f2474958 |
141 | return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).w(); |
3c4e78f2 |
142 | } |
143 | |
f2474958 |
144 | //! Checks whether the given node is outer. |
145 | bool IsOuter (const int theNodeIndex) const |
3c4e78f2 |
146 | { |
f2474958 |
147 | return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() != 0; |
3c4e78f2 |
148 | } |
149 | |
f2474958 |
150 | public: //! @name methods for accessing serialized tree data |
3c4e78f2 |
151 | |
f2474958 |
152 | //! Returns array of node data records. |
153 | BVH_Array4i& NodeInfoBuffer() |
3c4e78f2 |
154 | { |
f2474958 |
155 | return myNodeInfoBuffer; |
3c4e78f2 |
156 | } |
157 | |
f2474958 |
158 | //! Returns array of node data records. |
159 | const BVH_Array4i& NodeInfoBuffer() const |
fc73a202 |
160 | { |
f2474958 |
161 | return myNodeInfoBuffer; |
fc73a202 |
162 | } |
163 | |
f2474958 |
164 | //! Returns array of node minimum points. |
3a7a7013 |
165 | typename BVH::ArrayType<T, N>::Type& MinPointBuffer() |
3c4e78f2 |
166 | { |
167 | return myMinPointBuffer; |
168 | } |
169 | |
f2474958 |
170 | //! Returns array of node maximum points. |
3a7a7013 |
171 | typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() |
3c4e78f2 |
172 | { |
173 | return myMaxPointBuffer; |
174 | } |
175 | |
f2474958 |
176 | //! Returns array of node minimum points. |
177 | const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const |
3c4e78f2 |
178 | { |
f2474958 |
179 | return myMinPointBuffer; |
3c4e78f2 |
180 | } |
181 | |
f2474958 |
182 | //! Returns array of node maximum points. |
183 | const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const |
3c4e78f2 |
184 | { |
f2474958 |
185 | return myMaxPointBuffer; |
3c4e78f2 |
186 | } |
187 | |
0904aa63 |
188 | //! Dumps the content of me into the stream |
189 | virtual void DumpJson (Standard_OStream& theOStream, const Standard_Integer theDepth = -1) const Standard_OVERRIDE |
190 | { |
191 | DUMP_CLASS_BEGIN (theOStream, BVH_TreeBase); |
192 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, myDepth); |
193 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, Length()); |
194 | |
195 | for (Standard_Integer aNodeIdx = 0; aNodeIdx < Length(); ++aNodeIdx) |
196 | { |
197 | DumpNode (aNodeIdx, theOStream, theDepth); |
198 | } |
199 | } |
200 | |
201 | //! Dumps the content of node into the stream |
202 | virtual void DumpNode (const int theNodeIndex, Standard_OStream& theOStream, const Standard_Integer theDepth) const Standard_OVERRIDE |
203 | { |
204 | DUMP_CLASS_BEGIN (theOStream, BVH_TreeNode); |
205 | |
206 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, theNodeIndex); |
207 | |
208 | Bnd_Box aBndBox = BVH::ToBndBox (MinPoint (theNodeIndex), MaxPoint (theNodeIndex)); |
209 | Bnd_Box* aPointer = &aBndBox; |
210 | DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, aPointer); |
211 | |
212 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, BegPrimitive (theNodeIndex)); |
213 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, EndPrimitive (theNodeIndex)); |
214 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, Level (theNodeIndex)); |
215 | DUMP_FIELD_VALUE_NUMERICAL (theOStream, IsOuter (theNodeIndex)); |
216 | } |
217 | |
f2474958 |
218 | public: //! @name protected fields |
3c4e78f2 |
219 | |
f2474958 |
220 | //! Array of node data records. |
221 | BVH_Array4i myNodeInfoBuffer; |
3c4e78f2 |
222 | |
223 | //! Array of node minimum points. |
3a7a7013 |
224 | typename BVH::ArrayType<T, N>::Type myMinPointBuffer; |
3c4e78f2 |
225 | |
226 | //! Array of node maximum points. |
3a7a7013 |
227 | typename BVH::ArrayType<T, N>::Type myMaxPointBuffer; |
3c4e78f2 |
228 | |
f2474958 |
229 | //! Current depth of BVH tree (set by builder). |
230 | int myDepth; |
3c4e78f2 |
231 | |
f2474958 |
232 | }; |
fc73a202 |
233 | |
f2474958 |
234 | //! Type corresponding to quad BVH. |
235 | struct BVH_QuadTree { }; |
236 | |
237 | //! Type corresponding to binary BVH. |
238 | struct BVH_BinaryTree { }; |
239 | |
240 | //! BVH tree with given arity (2 or 4). |
241 | template<class T, int N, class Arity = BVH_BinaryTree> |
242 | class BVH_Tree |
243 | { |
244 | // Invalid type |
3c4e78f2 |
245 | }; |
246 | |
f2474958 |
247 | #endif // _BVH_TreeBase_Header |