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 | |
3a507ddb |
16 | #include <BVH_QuickSorter.hxx> |
3c4e78f2 |
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, |
65578e1c |
26 | const Standard_Integer theMaxTreeDepth, |
27 | const Standard_Integer theNumOfThreads) |
0ef61b50 |
28 | : BVH_QueueBuilder<T, N> (theLeafNodeSize, |
65578e1c |
29 | theMaxTreeDepth, |
30 | theNumOfThreads) |
3c4e78f2 |
31 | { |
32 | // |
33 | } |
34 | |
35 | // ======================================================================= |
36 | // function : ~BVH_SweepPlaneBuilder |
37 | // purpose : |
38 | // ======================================================================= |
39 | template<class T, int N> |
40 | BVH_SweepPlaneBuilder<T, N>::~BVH_SweepPlaneBuilder() |
41 | { |
42 | // |
43 | } |
44 | |
45 | // ======================================================================= |
46 | // function : BuildNode |
47 | // purpose : |
48 | // ======================================================================= |
49 | template<class T, int N> |
65578e1c |
50 | typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_SweepPlaneBuilder<T, N>::BuildNode (BVH_Set<T, N>* theSet, |
51 | BVH_Tree<T, N>* theBVH, |
52 | const Standard_Integer theNode) |
3c4e78f2 |
53 | { |
54 | const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); |
55 | const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); |
56 | const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode); |
57 | |
228de226 |
58 | if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize) |
59 | { |
65578e1c |
60 | return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning |
228de226 |
61 | } |
62 | |
3c4e78f2 |
63 | // Parameters for storing best split |
64 | Standard_Integer aMinSplitAxis = -1; |
65 | Standard_Integer aMinSplitIndex = 0; |
66 | |
e3709f1d |
67 | NCollection_Array1<Standard_Real> aLftSet (0, aNodeNbPrimitives - 1); |
68 | NCollection_Array1<Standard_Real> aRghSet (0, aNodeNbPrimitives - 1); |
3c4e78f2 |
69 | |
70 | Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max(); |
71 | |
72 | // Find best split |
73 | for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) |
74 | { |
3a7a7013 |
75 | const T aNodeSize = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) - |
76 | BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis); |
679d3878 |
77 | if (aNodeSize <= BVH::THE_NODE_MIN_SIZE) |
3c4e78f2 |
78 | { |
79 | continue; |
80 | } |
81 | |
3a507ddb |
82 | BVH_QuickSorter<T, N> (anAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive); |
3c4e78f2 |
83 | |
84 | BVH_Box<T, N> aLftBox; |
85 | BVH_Box<T, N> aRghBox; |
86 | |
e3709f1d |
87 | aLftSet.ChangeFirst() = std::numeric_limits<T>::max(); |
88 | aRghSet.ChangeFirst() = std::numeric_limits<T>::max(); |
3c4e78f2 |
89 | |
90 | // Sweep from left |
91 | for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) |
92 | { |
93 | aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1)); |
94 | |
e3709f1d |
95 | aLftSet (anIndex) = static_cast<Standard_Real> (aLftBox.Area()); |
3c4e78f2 |
96 | } |
97 | |
98 | // Sweep from right |
99 | for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) |
100 | { |
101 | aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1)); |
102 | |
e3709f1d |
103 | aRghSet (anIndex) = static_cast<Standard_Real> (aRghBox.Area()); |
3c4e78f2 |
104 | } |
105 | |
106 | // Find best split using simplified SAH |
107 | for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh) |
108 | { |
e3709f1d |
109 | Standard_Real aCost = (aLftSet (aNbLft) /* / aNodeArea */) * aNbLft + |
110 | (aRghSet (aNbRgh) /* / aNodeArea */) * aNbRgh; |
3c4e78f2 |
111 | |
112 | if (aCost < aMinSplitCost) |
113 | { |
114 | aMinSplitCost = aCost; |
115 | aMinSplitAxis = anAxis; |
116 | aMinSplitIndex = aNbLft; |
117 | } |
118 | } |
119 | } |
120 | |
121 | if (aMinSplitAxis == -1) |
122 | { |
65578e1c |
123 | return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // failed to find split axis |
3c4e78f2 |
124 | } |
125 | |
126 | theBVH->SetInner (theNode); |
127 | |
128 | if (aMinSplitAxis != (N < 4 ? N - 1 : 2)) |
129 | { |
3a507ddb |
130 | BVH_QuickSorter<T, N> (aMinSplitAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive); |
3c4e78f2 |
131 | } |
132 | |
133 | BVH_Box<T, N> aMinSplitBoxLft; |
134 | BVH_Box<T, N> aMinSplitBoxRgh; |
135 | |
136 | // Compute bounding boxes for selected split plane |
137 | for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex) |
138 | { |
139 | aMinSplitBoxLft.Combine (theSet->Box (anIndex)); |
140 | } |
141 | |
142 | for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex) |
143 | { |
144 | aMinSplitBoxRgh.Combine (theSet->Box (anIndex)); |
145 | } |
146 | |
147 | const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex; |
148 | |
65578e1c |
149 | typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range; |
3c4e78f2 |
150 | |
65578e1c |
151 | return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft, |
152 | aMinSplitBoxRgh, |
153 | Range (aNodeBegPrimitive, aMiddle - 1), |
154 | Range (aMiddle, aNodeEndPrimitive)); |
3c4e78f2 |
155 | } |