0030997: Foundation Classes - name correction of dump macros
[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_TreeBase_Header
17 #define _BVH_TreeBase_Header
18
19 #include <BVH_Box.hxx>
20
21 template<class T, int N> class BVH_Builder;
22
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() {}
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; }
37 };
38
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>
48 class BVH_TreeBase : public BVH_TreeBaseTransient
49 {
50   friend class BVH_Builder<T, N>;
51
52 public: //! @name custom data types
53
54   typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
55
56 public: //! @name general methods
57
58   //! Creates new empty BVH tree.
59   BVH_TreeBase() : myDepth (0) { }
60
61   //! Releases resources of BVH tree.
62   virtual ~BVH_TreeBase() {}
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
72   {
73     return BVH::Array<int, 4>::Size (myNodeInfoBuffer);
74   }
75
76 public: //! @name methods for accessing individual nodes
77
78   //! Returns minimum point of the given node.
79   BVH_VecNt& MinPoint (const int theNodeIndex)
80   {
81     return BVH::Array<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
82   }
83
84   //! Returns maximum point of the given node.
85   BVH_VecNt& MaxPoint (const int theNodeIndex)
86   {
87     return BVH::Array<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
88   }
89
90   //! Returns minimum point of the given node.
91   const BVH_VecNt& MinPoint (const int theNodeIndex) const
92   {
93     return BVH::Array<T, N>::Value (myMinPointBuffer, theNodeIndex);
94   }
95
96   //! Returns maximum point of the given node.
97   const BVH_VecNt& MaxPoint (const int theNodeIndex) const
98   {
99     return BVH::Array<T, N>::Value (myMaxPointBuffer, theNodeIndex);
100   }
101
102   //! Returns index of first primitive of the given leaf node.
103   int& BegPrimitive (const int theNodeIndex)
104   {
105     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
106   }
107
108   //! Returns index of last primitive of the given leaf node.
109   int& EndPrimitive (const int theNodeIndex)
110   {
111     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
112   }
113
114   //! Returns index of first primitive of the given leaf node.
115   int BegPrimitive (const int theNodeIndex) const
116   {
117     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
118   }
119
120   //! Returns index of last primitive of the given leaf node.
121   int EndPrimitive (const int theNodeIndex) const
122   {
123     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
124   }
125
126   //! Returns number of primitives in the given leaf node.
127   int NbPrimitives (const int theNodeIndex) const
128   {
129     return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1;
130   }
131
132   //! Returns level (depth) of the given node.
133   int& Level (const int theNodeIndex)
134   {
135     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
136   }
137
138   //! Returns level (depth) of the given node.
139   int Level (const int theNodeIndex) const
140   {
141     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
142   }
143
144   //! Checks whether the given node is outer.
145   bool IsOuter (const int theNodeIndex) const
146   {
147     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() != 0;
148   }
149
150 public: //! @name methods for accessing serialized tree data
151
152   //! Returns array of node data records.
153   BVH_Array4i& NodeInfoBuffer()
154   {
155     return myNodeInfoBuffer;
156   }
157
158   //! Returns array of node data records.
159   const BVH_Array4i& NodeInfoBuffer() const
160   {
161     return myNodeInfoBuffer;
162   }
163
164   //! Returns array of node minimum points.
165   typename BVH::ArrayType<T, N>::Type& MinPointBuffer()
166   {
167     return myMinPointBuffer;
168   }
169
170   //! Returns array of node maximum points.
171   typename BVH::ArrayType<T, N>::Type& MaxPointBuffer()
172   {
173     return myMaxPointBuffer;
174   }
175
176   //! Returns array of node minimum points.
177   const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const
178   {
179     return myMinPointBuffer;
180   }
181
182   //! Returns array of node maximum points.
183   const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const
184   {
185     return myMaxPointBuffer;
186   }
187
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     OCCT_DUMP_CLASS_BEGIN (theOStream, BVH_TreeBase);
192     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myDepth);
193     OCCT_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     OCCT_DUMP_CLASS_BEGIN (theOStream, BVH_TreeNode);
205
206     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, theNodeIndex);
207
208     Bnd_Box aBndBox = BVH::ToBndBox (MinPoint (theNodeIndex), MaxPoint (theNodeIndex));
209     Bnd_Box* aPointer = &aBndBox;
210     OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, aPointer);
211
212     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, BegPrimitive (theNodeIndex));
213     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, EndPrimitive (theNodeIndex));
214     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, Level (theNodeIndex));
215     OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, IsOuter (theNodeIndex));
216   }
217
218 public: //! @name protected fields
219
220   //! Array of node data records.
221   BVH_Array4i myNodeInfoBuffer;
222
223   //! Array of node minimum points.
224   typename BVH::ArrayType<T, N>::Type myMinPointBuffer;
225
226   //! Array of node maximum points.
227   typename BVH::ArrayType<T, N>::Type myMaxPointBuffer;
228
229   //! Current depth of BVH tree (set by builder).
230   int myDepth;
231
232 };
233
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
245 };
246
247 #endif // _BVH_TreeBase_Header