0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[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 template<class T, int N> class BVH_Builder;
24
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 {
36   friend class BVH_Builder<T, N>;
37
38 public:
39
40   typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
41
42 public:
43
44   //! Creates new empty BVH tree.
45   BVH_Tree() : myDepth (0)
46   {
47     //
48   }
49
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
164   //! Returns depth of BVH tree from last build.
165   Standard_Integer Depth() const
166   {
167     return myDepth;
168   }
169
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
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
202 public:
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
240 protected:
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
251   //! Depth of constructed tree.
252   Standard_Integer myDepth;
253
254 };
255
256 #include <BVH_Tree.lxx>
257
258 #endif // _BVH_Tree_Header