3c4e78f2 |
1 | // Created on: 2014-01-09 |
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 | #include <BVH_Sorter.hxx> |
17 | |
18 | // ======================================================================= |
19 | // function : BVH_SweepPlaneBuilder |
20 | // purpose : |
21 | // ======================================================================= |
22 | template<class T, int N> |
23 | BVH_SweepPlaneBuilder<T, N>::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize, |
24 | const Standard_Integer theMaxTreeDepth) |
25 | : BVH_Builder<T, N> (theLeafNodeSize, |
26 | theMaxTreeDepth) |
27 | { |
28 | // |
29 | } |
30 | |
31 | // ======================================================================= |
32 | // function : ~BVH_SweepPlaneBuilder |
33 | // purpose : |
34 | // ======================================================================= |
35 | template<class T, int N> |
36 | BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder() |
37 | { |
38 | // |
39 | } |
40 | |
41 | // ======================================================================= |
42 | // function : BuildNode |
43 | // purpose : |
44 | // ======================================================================= |
45 | template<class T, int N> |
46 | void BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>* theSet, |
47 | BVH_Tree<T, N>* theBVH, |
48 | const Standard_Integer theNode) |
49 | { |
50 | const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); |
51 | const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); |
52 | const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode); |
53 | |
228de226 |
54 | if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize) |
55 | { |
56 | return; // node does not require partitioning |
57 | } |
58 | |
3c4e78f2 |
59 | // Parameters for storing best split |
60 | Standard_Integer aMinSplitAxis = -1; |
61 | Standard_Integer aMinSplitIndex = 0; |
62 | |
63 | Standard_Real* aLftSet = new Standard_Real[aNodeNbPrimitives]; |
64 | Standard_Real* aRghSet = new Standard_Real[aNodeNbPrimitives]; |
65 | |
66 | Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max(); |
67 | |
68 | // Find best split |
69 | for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) |
70 | { |
3a7a7013 |
71 | const T aNodeSize = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) - |
72 | BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis); |
3c4e78f2 |
73 | if (aNodeSize <= THE_NODE_MIN_SIZE) |
74 | { |
75 | continue; |
76 | } |
77 | |
78 | BVH_Sorter<T, N>::Perform (theSet, anAxis, aNodeBegPrimitive, aNodeEndPrimitive); |
79 | |
80 | BVH_Box<T, N> aLftBox; |
81 | BVH_Box<T, N> aRghBox; |
82 | |
83 | *aLftSet = std::numeric_limits<T>::max(); |
84 | *aRghSet = std::numeric_limits<T>::max(); |
85 | |
86 | // Sweep from left |
87 | for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) |
88 | { |
89 | aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1)); |
90 | |
91 | aLftSet[anIndex] = static_cast<Standard_Real> (aLftBox.Area()); |
92 | } |
93 | |
94 | // Sweep from right |
95 | for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) |
96 | { |
97 | aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1)); |
98 | |
99 | aRghSet[anIndex] = static_cast<Standard_Real> (aRghBox.Area()); |
100 | } |
101 | |
102 | // Find best split using simplified SAH |
103 | for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh) |
104 | { |
105 | Standard_Real aCost = (aLftSet[aNbLft] /* / aNodeArea */) * aNbLft + |
106 | (aRghSet[aNbRgh] /* / aNodeArea */) * aNbRgh; |
107 | |
108 | if (aCost < aMinSplitCost) |
109 | { |
110 | aMinSplitCost = aCost; |
111 | aMinSplitAxis = anAxis; |
112 | aMinSplitIndex = aNbLft; |
113 | } |
114 | } |
115 | } |
116 | |
117 | if (aMinSplitAxis == -1) |
118 | { |
119 | return; |
120 | } |
121 | |
122 | theBVH->SetInner (theNode); |
123 | |
124 | if (aMinSplitAxis != (N < 4 ? N - 1 : 2)) |
125 | { |
126 | BVH_Sorter<T, N>::Perform (theSet, aMinSplitAxis, aNodeBegPrimitive, aNodeEndPrimitive); |
127 | } |
128 | |
129 | BVH_Box<T, N> aMinSplitBoxLft; |
130 | BVH_Box<T, N> aMinSplitBoxRgh; |
131 | |
132 | // Compute bounding boxes for selected split plane |
133 | for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex) |
134 | { |
135 | aMinSplitBoxLft.Combine (theSet->Box (anIndex)); |
136 | } |
137 | |
138 | for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex) |
139 | { |
140 | aMinSplitBoxRgh.Combine (theSet->Box (anIndex)); |
141 | } |
142 | |
143 | const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex; |
144 | |
145 | static const Standard_Integer aLftNode = 1; |
146 | static const Standard_Integer aRghNode = 2; |
147 | |
148 | // Setting up tasks for child nodes |
149 | for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) |
150 | { |
151 | typename BVH_Box<T, N>::BVH_VecNt aChildMinPoint = (aSide == aLftNode) |
152 | ? aMinSplitBoxLft.CornerMin() |
153 | : aMinSplitBoxRgh.CornerMin(); |
154 | typename BVH_Box<T, N>::BVH_VecNt aChildMaxPoint = (aSide == aLftNode) |
155 | ? aMinSplitBoxLft.CornerMax() |
156 | : aMinSplitBoxRgh.CornerMax(); |
157 | |
158 | Standard_Integer aChildBegPrimitive = (aSide == aLftNode) |
159 | ? aNodeBegPrimitive |
160 | : aMiddle; |
161 | Standard_Integer aChildEndPrimitive = (aSide == aLftNode) |
162 | ? aMiddle - 1 |
163 | : aNodeEndPrimitive; |
164 | |
165 | Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint, |
166 | aChildBegPrimitive, aChildEndPrimitive); |
167 | |
168 | theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; |
169 | |
170 | // Check to see if child node must be split |
171 | const Standard_Integer aChildNbPimitives = (aSide == aLftNode) |
172 | ? aMiddle - aNodeBegPrimitive |
173 | : aNodeEndPrimitive - aMiddle + 1; |
174 | |
175 | if (aSide == aLftNode) |
176 | theBVH->LeftChild (theNode) = aChildIndex; |
177 | else |
178 | theBVH->RightChild (theNode) = aChildIndex; |
179 | |
180 | const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize |
181 | || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth; |
182 | |
183 | if (!isLeaf) |
184 | { |
185 | BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex); |
186 | } |
fc73a202 |
187 | |
188 | BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (aChildIndex)); |
3c4e78f2 |
189 | } |
190 | } |