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 | |
3a7a7013 |
25 | BVH::ArrayOp<T, N>::Clear (myMinPointBuffer); |
26 | BVH::ArrayOp<T, N>::Clear (myMaxPointBuffer); |
3c4e78f2 |
27 | |
3a7a7013 |
28 | BVH::ArrayOp<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 | { |
39 | BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
40 | |
41 | return static_cast<Standard_Integer> (BVH::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
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 | { |
52 | BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
53 | |
54 | return static_cast<Standard_Integer> (BVH::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1); |
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 | { |
3a7a7013 |
67 | BVH::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint); |
68 | BVH::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint); |
3c4e78f2 |
69 | |
3a7a7013 |
70 | BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0)); |
3c4e78f2 |
71 | |
3a7a7013 |
72 | return static_cast<Standard_Integer> (BVH::ArrayOp<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 | { |
3a7a7013 |
85 | BVH::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint); |
86 | BVH::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint); |
3c4e78f2 |
87 | |
3a7a7013 |
88 | BVH::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0)); |
3c4e78f2 |
89 | |
3a7a7013 |
90 | return static_cast<Standard_Integer> (BVH::ArrayOp<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 | { |
102 | return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem); |
103 | } |
104 | |
105 | // ======================================================================= |
106 | // function : AddInnerNode |
107 | // purpose : |
108 | // ======================================================================= |
109 | template<class T, int N> |
110 | Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_Box<T, N>& theAABB, |
111 | const Standard_Integer theLftChild, |
112 | const Standard_Integer theRghChild) |
113 | { |
114 | return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild); |
115 | } |
116 | |
3a7a7013 |
117 | namespace BVH |
3c4e78f2 |
118 | { |
119 | template<class T, int N> |
120 | void EstimateSAH (const BVH_Tree<T, N>* theTree, |
121 | const Standard_Integer theNode, |
122 | T theProbability, |
123 | T& theSAH) |
124 | { |
125 | BVH_Box<T, N> aBox (theTree->MinPoint (theNode), |
126 | theTree->MaxPoint (theNode)); |
127 | |
128 | if (theTree->IsOuter (theNode)) |
129 | { |
130 | theSAH += theProbability * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1); |
131 | } |
132 | else |
133 | { |
134 | theSAH += theProbability * static_cast<T> (2.0); |
135 | |
136 | BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->LeftChild (theNode)), |
137 | theTree->MaxPoint (theTree->LeftChild (theNode))); |
138 | |
139 | if (theProbability > 0.0) |
140 | { |
141 | EstimateSAH (theTree, theTree->LeftChild (theNode), |
142 | theProbability * aLftBox.Area() / aBox.Area(), theSAH); |
143 | } |
144 | |
145 | BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)), |
146 | theTree->MaxPoint (theTree->RightChild (theNode))); |
147 | |
148 | if (theProbability > 0.0) |
149 | { |
150 | EstimateSAH (theTree, theTree->RightChild (theNode), |
151 | theProbability * aRghBox.Area() / aBox.Area(), theSAH); |
152 | } |
153 | } |
154 | } |
155 | } |
156 | |
157 | // ======================================================================= |
158 | // function : EstimateSAH |
159 | // purpose : |
160 | // ======================================================================= |
161 | template<class T, int N> |
162 | T BVH_Tree<T, N>::EstimateSAH() const |
163 | { |
164 | T aSAH = static_cast<T> (0.0); |
3a7a7013 |
165 | BVH::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH); |
3c4e78f2 |
166 | return aSAH; |
167 | } |