0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[occt.git] / src / BVH / BVH_Tree.hxx
CommitLineData
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 23template<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.
33template<class T, int N>
34class BVH_Tree
35{
fc73a202 36 friend class BVH_Builder<T, N>;
37
3c4e78f2 38public:
39
40 typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
41
42public:
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 {
53 return BVHTools::ArrayOp<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
54 }
55
56 //! Returns maximum point of the given node.
57 BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex)
58 {
59 return BVHTools::ArrayOp<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
60 }
61
62 //! Returns minimum point of the given node.
63 const BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) const
64 {
65 return BVHTools::ArrayOp<T, N>::Value (myMinPointBuffer, theNodeIndex);
66 }
67
68 //! Returns maximum point of the given node.
69 const BVH_VecNt& MaxPoint (const Standard_Integer theNodeIndex) const
70 {
71 return BVHTools::ArrayOp<T, N>::Value (myMaxPointBuffer, theNodeIndex);
72 }
73
74 //! Returns index of left child of the given inner node.
75 Standard_Integer& LeftChild (const Standard_Integer theNodeIndex)
76 {
77 return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
78 }
79
80 //! Returns index of left child of the given inner node.
81 Standard_Integer LeftChild (const Standard_Integer theNodeIndex) const
82 {
83 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
84 }
85
86 //! Returns index of right child of the given inner node.
87 Standard_Integer& RightChild (const Standard_Integer theNodeIndex)
88 {
89 return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
90 }
91
92 //! Returns index of right child of the given inner node.
93 Standard_Integer RightChild (const Standard_Integer theNodeIndex) const
94 {
95 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
96 }
97
98 //! Returns index of first primitive of the given leaf node.
99 Standard_Integer& BegPrimitive (const Standard_Integer theNodeIndex)
100 {
101 return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
102 }
103
104 //! Returns index of first primitive of the given leaf node.
105 Standard_Integer BegPrimitive (const Standard_Integer theNodeIndex) const
106 {
107 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
108 }
109
110 //! Returns index of last primitive of the given leaf node.
111 Standard_Integer& EndPrimitive (const Standard_Integer theNodeIndex)
112 {
113 return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
114 }
115
116 //! Returns index of last primitive of the given leaf node.
117 Standard_Integer EndPrimitive (const Standard_Integer theNodeIndex) const
118 {
119 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
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 {
131 return BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
132 }
133
134 //! Returns level (depth) of the given node.
135 Standard_Integer Level (const Standard_Integer theNodeIndex) const
136 {
137 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
138 }
139
140 //! Is node a leaf (outer)?
141 Standard_Boolean IsOuter (const Standard_Integer theNodeIndex) const
142 {
143 return BVHTools::ArrayOp<Standard_Integer, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() > 0;
144 }
145
146 //! Sets node type to 'outer'.
147 void SetOuter (const Standard_Integer theNodeIndex)
148 {
149 BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 1;
150 }
151
152 //! Sets node type to 'inner'.
153 void SetInner (const Standard_Integer theNodeIndex)
154 {
155 BVHTools::ArrayOp<Standard_Integer, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).x() = 0;
156 }
157
158 //! Returns total number of BVH nodes.
159 Standard_Integer Length() const
160 {
161 return BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer);
162 }
163
fc73a202 164 //! Returns depth of BVH tree from last build.
165 Standard_Integer Depth() const
166 {
167 return myDepth;
168 }
169
3c4e78f2 170public:
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
197 //! Returns value of SAH (surface area heuristic).
198 //! Allows to compare the quality of BVH trees constructed for
199 //! the same sets of geometric objects with different methods.
200 T EstimateSAH() const;
201
202public:
203
204 //! Returns array of node min points.
205 typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer()
206 {
207 return myMinPointBuffer;
208 }
209
210 //! Returns array of node min points.
211 const typename BVHTools::ArrayType<T, N>::Type& MinPointBuffer() const
212 {
213 return myMinPointBuffer;
214 }
215
216 //! Returns array of node max points.
217 typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer()
218 {
219 return myMaxPointBuffer;
220 }
221
222 //! Returns array of node max points.
223 const typename BVHTools::ArrayType<T, N>::Type& MaxPointBuffer() const
224 {
225 return myMaxPointBuffer;
226 }
227
228 //! Returns array of node data records.
229 BVH_Array4i& NodeInfoBuffer()
230 {
231 return myNodeInfoBuffer;
232 }
233
234 //! Returns array of node data records.
235 const BVH_Array4i& NodeInfoBuffer() const
236 {
237 return myNodeInfoBuffer;
238 }
239
240protected:
241
242 //! Array of node minimum points.
243 typename BVHTools::ArrayType<T, N>::Type myMinPointBuffer;
244
245 //! Array of node maximum points.
246 typename BVHTools::ArrayType<T, N>::Type myMaxPointBuffer;
247
248 //! Array of node data records.
249 BVH_Array4i myNodeInfoBuffer;
250
fc73a202 251 //! Depth of constructed tree.
252 Standard_Integer myDepth;
253
3c4e78f2 254};
255
256#include <BVH_Tree.lxx>
257
258#endif // _BVH_Tree_Header