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