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 | // ======================================================================= |
17 | // function : Clear |
18 | // purpose : |
19 | // ======================================================================= |
20 | template<class T, int N> |
21 | void BVH_Tree<T, N>::Clear() |
22 | { |
fc73a202 |
23 | myDepth = 0; |
24 | |
679d3878 |
25 | BVH::Array<T, N>::Clear (myMinPointBuffer); |
26 | BVH::Array<T, N>::Clear (myMaxPointBuffer); |
3c4e78f2 |
27 | |
679d3878 |
28 | BVH::Array<Standard_Integer, 4>::Clear (myNodeInfoBuffer); |
3c4e78f2 |
29 | } |
30 | |
0ef61b50 |
31 | // ======================================================================= |
32 | // function : AddLeafNode |
33 | // purpose : |
34 | // ======================================================================= |
35 | template<class T, int N> |
36 | Standard_Integer BVH_Tree<T, N>::AddLeafNode (const Standard_Integer theBegElem, |
37 | const Standard_Integer theEndElem) |
38 | { |
679d3878 |
39 | BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
0ef61b50 |
40 | |
679d3878 |
41 | return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
0ef61b50 |
42 | } |
43 | |
44 | // ======================================================================= |
45 | // function : AddInnerNode |
46 | // purpose : |
47 | // ======================================================================= |
48 | template<class T, int N> |
49 | Standard_Integer BVH_Tree<T, N>::AddInnerNode (const Standard_Integer theLftChild, |
50 | const Standard_Integer theRghChild) |
51 | { |
679d3878 |
52 | BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
0ef61b50 |
53 | |
679d3878 |
54 | return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
0ef61b50 |
55 | } |
56 | |
3c4e78f2 |
57 | // ======================================================================= |
58 | // function : AddLeafNode |
59 | // purpose : |
60 | // ======================================================================= |
61 | template<class T, int N> |
62 | Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_VecNt& theMinPoint, |
63 | const BVH_VecNt& theMaxPoint, |
64 | const Standard_Integer theBegElem, |
65 | const Standard_Integer theEndElem) |
66 | { |
679d3878 |
67 | BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint); |
68 | BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint); |
3c4e78f2 |
69 | |
679d3878 |
70 | BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
3c4e78f2 |
71 | |
679d3878 |
72 | return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
3c4e78f2 |
73 | } |
74 | |
75 | // ======================================================================= |
76 | // function : AddInnerNode |
77 | // purpose : |
78 | // ======================================================================= |
79 | template<class T, int N> |
80 | Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_VecNt& theMinPoint, |
81 | const BVH_VecNt& theMaxPoint, |
82 | const Standard_Integer theLftChild, |
83 | const Standard_Integer theRghChild) |
84 | { |
679d3878 |
85 | BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint); |
86 | BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint); |
3c4e78f2 |
87 | |
679d3878 |
88 | BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
3c4e78f2 |
89 | |
679d3878 |
90 | return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
3c4e78f2 |
91 | } |
92 | |
93 | // ======================================================================= |
94 | // function : AddLeafNode |
95 | // purpose : |
96 | // ======================================================================= |
97 | template<class T, int N> |
98 | Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_Box<T, N>& theAABB, |
99 | const Standard_Integer theBegElem, |
100 | const Standard_Integer theEndElem) |
101 | { |
65578e1c |
102 | return AddLeafNode (theAABB.CornerMin(), |
103 | theAABB.CornerMax(), |
104 | theBegElem, |
105 | theEndElem); |
3c4e78f2 |
106 | } |
107 | |
108 | // ======================================================================= |
109 | // function : AddInnerNode |
110 | // purpose : |
111 | // ======================================================================= |
112 | template<class T, int N> |
113 | Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_Box<T, N>& theAABB, |
114 | const Standard_Integer theLftChild, |
115 | const Standard_Integer theRghChild) |
116 | { |
65578e1c |
117 | return AddInnerNode (theAABB.CornerMin(), |
118 | theAABB.CornerMax(), |
119 | theLftChild, |
120 | theRghChild); |
3c4e78f2 |
121 | } |
122 | |
3a7a7013 |
123 | namespace BVH |
3c4e78f2 |
124 | { |
679d3878 |
125 | //! Internal function for recursive calculation of |
126 | //! surface area heuristic (SAH) of the given tree. |
3c4e78f2 |
127 | template<class T, int N> |
128 | void EstimateSAH (const BVH_Tree<T, N>* theTree, |
129 | const Standard_Integer theNode, |
679d3878 |
130 | T theProb, |
3c4e78f2 |
131 | T& theSAH) |
132 | { |
133 | BVH_Box<T, N> aBox (theTree->MinPoint (theNode), |
134 | theTree->MaxPoint (theNode)); |
135 | |
136 | if (theTree->IsOuter (theNode)) |
137 | { |
679d3878 |
138 | theSAH += theProb * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1); |
3c4e78f2 |
139 | } |
140 | else |
141 | { |
679d3878 |
142 | theSAH += theProb * static_cast<T> (2.0); |
3c4e78f2 |
143 | |
144 | BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->LeftChild (theNode)), |
145 | theTree->MaxPoint (theTree->LeftChild (theNode))); |
146 | |
679d3878 |
147 | if (theProb > 0.0) |
3c4e78f2 |
148 | { |
149 | EstimateSAH (theTree, theTree->LeftChild (theNode), |
679d3878 |
150 | theProb * aLftBox.Area() / aBox.Area(), theSAH); |
3c4e78f2 |
151 | } |
152 | |
153 | BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)), |
154 | theTree->MaxPoint (theTree->RightChild (theNode))); |
155 | |
679d3878 |
156 | if (theProb > 0.0) |
3c4e78f2 |
157 | { |
158 | EstimateSAH (theTree, theTree->RightChild (theNode), |
679d3878 |
159 | theProb * aRghBox.Area() / aBox.Area(), theSAH); |
3c4e78f2 |
160 | } |
161 | } |
162 | } |
163 | } |
164 | |
165 | // ======================================================================= |
166 | // function : EstimateSAH |
167 | // purpose : |
168 | // ======================================================================= |
169 | template<class T, int N> |
170 | T BVH_Tree<T, N>::EstimateSAH() const |
171 | { |
172 | T aSAH = static_cast<T> (0.0); |
3a7a7013 |
173 | BVH::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH); |
3c4e78f2 |
174 | return aSAH; |
175 | } |
65578e1c |
176 | |
177 | // ======================================================================= |
178 | // function : Reserve |
179 | // purpose : |
180 | // ======================================================================= |
181 | template<class T, int N> |
182 | void BVH_Tree<T, N>::Reserve (const Standard_Integer theNbNodes) |
183 | { |
184 | BVH::Array<T, N>::Reserve (myMinPointBuffer, theNbNodes); |
185 | BVH::Array<T, N>::Reserve (myMaxPointBuffer, theNbNodes); |
186 | BVH::Array<Standard_Integer, 4>::Reserve (myNodeInfoBuffer, theNbNodes); |
187 | } |