0ef61b50 |
1 | // Created on: 2014-09-15 |
2 | // Created by: Denis BOGOLEPOV |
3 | // Copyright (c) 2013-2014 OPEN CASCADE SAS |
4 | // |
5 | // This file is part of Open CASCADE Technology software library. |
6 | // |
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 |
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 | #ifndef _BVH_QueueBuilder_Header |
17 | #define _BVH_QueueBuilder_Header |
18 | |
19 | #include <BVH_Builder.hxx> |
65578e1c |
20 | #include <BVH_BuildThread.hxx> |
0ef61b50 |
21 | #include <NCollection_Vector.hxx> |
22 | |
23 | //! Abstract BVH builder based on the concept of work queue. |
65578e1c |
24 | //! Queue based BVH builders support parallelization with a |
25 | //! fixed number of threads (maximum efficiency is achieved |
26 | //! by setting the number of threads equal to the number of |
27 | //! CPU cores plus one). Note that to support parallel mode, |
28 | //! a corresponding BVH primitive set should provide thread |
29 | //! safe implementations of interface functions (e.g., Swap, |
30 | //! Box, Center). Otherwise, the results will be undefined. |
31 | //! \tparam T Numeric data type |
32 | //! \tparam N Vector dimension |
0ef61b50 |
33 | template<class T, int N> |
34 | class BVH_QueueBuilder : public BVH_Builder<T, N> |
35 | { |
36 | public: |
37 | |
38 | //! Creates new BVH queue based builder. |
39 | BVH_QueueBuilder (const Standard_Integer theLeafNodeSize, |
65578e1c |
40 | const Standard_Integer theMaxTreeDepth, |
e28f12b3 |
41 | const Standard_Integer theNumOfThreads = 1) |
42 | : BVH_Builder<T, N> (theLeafNodeSize, |
43 | theMaxTreeDepth), |
44 | myNumOfThreads (theNumOfThreads) {} |
0ef61b50 |
45 | |
46 | //! Releases resources of BVH queue based builder. |
47 | virtual ~BVH_QueueBuilder() = 0; |
48 | |
49 | public: |
50 | |
51 | //! Builds BVH using specific algorithm. |
52 | virtual void Build (BVH_Set<T, N>* theSet, |
53 | BVH_Tree<T, N>* theBVH, |
e28f12b3 |
54 | const BVH_Box<T, N>& theBox) const Standard_OVERRIDE; |
0ef61b50 |
55 | |
56 | protected: |
57 | |
65578e1c |
58 | //! Stores range of primitives belonging to a BVH node. |
59 | struct BVH_PrimitiveRange |
60 | { |
61 | Standard_Integer Start; |
62 | Standard_Integer Final; |
63 | |
64 | //! Creates new primitive range. |
65 | BVH_PrimitiveRange (Standard_Integer theStart = -1, |
66 | Standard_Integer theFinal = -1) |
67 | : Start (theStart), |
68 | Final (theFinal) |
69 | { |
70 | // |
71 | } |
72 | |
73 | //! Returns total number of primitives. |
74 | Standard_Integer Size() const |
75 | { |
76 | return Final - Start + 1; |
77 | } |
78 | |
79 | //! Checks if the range is initialized. |
80 | Standard_Boolean IsValid() const |
81 | { |
82 | return Start != -1; |
83 | } |
84 | }; |
85 | |
86 | //! Stores parameters of constructed child nodes. |
87 | struct BVH_ChildNodes |
88 | { |
89 | //! Bounding boxes of child nodes. |
90 | BVH_Box<T, N> Boxes[2]; |
91 | |
92 | //! Primitive ranges of child nodes. |
93 | BVH_PrimitiveRange Ranges[2]; |
94 | |
95 | //! Creates new parameters of BVH child nodes. |
96 | BVH_ChildNodes() |
97 | { |
98 | // |
99 | } |
100 | |
101 | //! Creates new parameters of BVH child nodes. |
102 | BVH_ChildNodes (const BVH_Box<T, N>& theLftBox, |
103 | const BVH_Box<T, N>& theRghBox, |
104 | const BVH_PrimitiveRange& theLftRange, |
105 | const BVH_PrimitiveRange& theRghRange) |
106 | { |
107 | Boxes[0] = theLftBox; |
108 | Boxes[1] = theRghBox; |
109 | Ranges[0] = theLftRange; |
110 | Ranges[1] = theRghRange; |
111 | } |
112 | |
113 | //! Returns number of primitives in the given child. |
114 | Standard_Integer NbPrims (const Standard_Integer theChild) const |
115 | { |
116 | return Ranges[theChild].Size(); |
117 | } |
118 | |
119 | //! Checks if the parameters is initialized. |
120 | Standard_Boolean IsValid() const |
121 | { |
122 | return Ranges[0].IsValid() && Ranges[1].IsValid(); |
123 | } |
124 | }; |
125 | |
126 | //! Wrapper for BVH build data. |
127 | class BVH_TypedBuildTool : public BVH_BuildTool |
128 | { |
129 | public: |
130 | |
131 | //! Creates new BVH build thread. |
e28f12b3 |
132 | BVH_TypedBuildTool (BVH_Set<T, N>* theSet, |
133 | BVH_Tree<T, N>* theBVH, |
134 | BVH_BuildQueue& theBuildQueue, |
135 | const BVH_QueueBuilder<T, N>* theAlgo) |
65578e1c |
136 | : mySet (theSet), |
e28f12b3 |
137 | myBVH (theBVH), |
138 | myBuildQueue (&theBuildQueue), |
139 | myAlgo (theAlgo) |
65578e1c |
140 | { |
e28f12b3 |
141 | Standard_ASSERT_RAISE (myAlgo != NULL, "Error! BVH builder should be queue based"); |
65578e1c |
142 | } |
143 | |
144 | //! Performs splitting of the given BVH node. |
e28f12b3 |
145 | virtual void Perform (const Standard_Integer theNode) Standard_OVERRIDE |
65578e1c |
146 | { |
e28f12b3 |
147 | const typename BVH_QueueBuilder<T, N>::BVH_ChildNodes aChildren = myAlgo->buildNode (mySet, myBVH, theNode); |
148 | myAlgo->addChildren (myBVH, *myBuildQueue, theNode, aChildren); |
65578e1c |
149 | } |
150 | |
151 | protected: |
152 | |
e28f12b3 |
153 | BVH_Set<T, N>* mySet; //!< Primitive set to build BVH |
154 | BVH_Tree<T, N>* myBVH; //!< Output BVH tree for the set |
155 | BVH_BuildQueue* myBuildQueue; |
156 | const BVH_QueueBuilder<T, N>* myAlgo; //!< Queue based BVH builder to use |
65578e1c |
157 | |
65578e1c |
158 | }; |
159 | |
160 | protected: |
161 | |
162 | //! Performs splitting of the given BVH node. |
e28f12b3 |
163 | virtual typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>* theSet, |
65578e1c |
164 | BVH_Tree<T, N>* theBVH, |
e28f12b3 |
165 | const Standard_Integer theNode) const = 0; |
65578e1c |
166 | |
167 | //! Processes child nodes of the splitted BVH node. |
e28f12b3 |
168 | virtual void addChildren (BVH_Tree<T, N>* theBVH, |
169 | BVH_BuildQueue& theBuildQueue, |
170 | const Standard_Integer theNode, |
171 | const BVH_ChildNodes& theSubNodes) const; |
0ef61b50 |
172 | |
173 | protected: |
174 | |
65578e1c |
175 | Standard_Integer myNumOfThreads; //!< Number of threads used to build BVH |
0ef61b50 |
176 | |
177 | }; |
178 | |
e28f12b3 |
179 | // ======================================================================= |
180 | // function : addChildren |
181 | // purpose : |
182 | // ======================================================================= |
183 | template<class T, int N> |
184 | void BVH_QueueBuilder<T, N>::addChildren (BVH_Tree<T, N>* theBVH, |
185 | BVH_BuildQueue& theBuildQueue, |
186 | const Standard_Integer theNode, |
187 | const typename BVH_QueueBuilder<T, N>::BVH_ChildNodes& theSubNodes) const |
188 | { |
189 | Standard_Integer aChildren[] = { -1, -1 }; |
190 | if (!theSubNodes.IsValid()) |
191 | { |
192 | return; |
193 | } |
194 | |
195 | // Add child nodes |
196 | { |
197 | Standard_Mutex::Sentry aSentry (theBuildQueue.myMutex); |
198 | |
199 | for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) |
200 | { |
201 | aChildren[anIdx] = theBVH->AddLeafNode (theSubNodes.Boxes[anIdx], |
202 | theSubNodes.Ranges[anIdx].Start, |
203 | theSubNodes.Ranges[anIdx].Final); |
204 | } |
205 | |
206 | BVH_Builder<T, N>::updateDepth (theBVH, theBVH->Level (theNode) + 1); |
207 | } |
208 | |
209 | // Set parameters of child nodes and generate new tasks |
210 | for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) |
211 | { |
212 | const Standard_Integer aChildIndex = aChildren[anIdx]; |
213 | |
214 | theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; |
215 | |
216 | (anIdx == 0 ? theBVH->template Child<0> (theNode) |
217 | : theBVH->template Child<1> (theNode)) = aChildIndex; |
218 | |
219 | // Check to see if the child node must be split |
220 | const Standard_Boolean isLeaf = theSubNodes.NbPrims (anIdx) <= BVH_Builder<T, N>::myLeafNodeSize |
221 | || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth; |
222 | |
223 | if (!isLeaf) |
224 | { |
225 | theBuildQueue.Enqueue (aChildIndex); |
226 | } |
227 | } |
228 | } |
229 | |
230 | // ======================================================================= |
231 | // function : Build |
232 | // purpose : Builds BVH using specific algorithm |
233 | // ======================================================================= |
234 | template<class T, int N> |
235 | void BVH_QueueBuilder<T, N>::Build (BVH_Set<T, N>* theSet, |
236 | BVH_Tree<T, N>* theBVH, |
237 | const BVH_Box<T, N>& theBox) const |
238 | { |
239 | Standard_ASSERT_RETURN (theBVH != NULL, |
240 | "Error! BVH tree to construct is NULL", ); |
241 | |
242 | theBVH->Clear(); |
243 | const Standard_Integer aSetSize = theSet->Size(); |
244 | if (aSetSize == 0) |
245 | { |
246 | return; |
247 | } |
248 | |
249 | const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, aSetSize - 1); |
250 | if (theSet->Size() == 1) |
251 | { |
252 | return; |
253 | } |
254 | |
255 | BVH_BuildQueue aBuildQueue; |
256 | aBuildQueue.Enqueue (aRoot); |
257 | |
258 | BVH_TypedBuildTool aBuildTool (theSet, theBVH, aBuildQueue, this); |
259 | if (myNumOfThreads > 1) |
260 | { |
261 | // Reserve the maximum possible number of nodes in the BVH |
262 | theBVH->Reserve (2 * aSetSize - 1); |
263 | |
264 | NCollection_Vector<Handle(BVH_BuildThread)> aThreads; |
265 | |
266 | // Run BVH build threads |
267 | for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) |
268 | { |
269 | aThreads.Append (new BVH_BuildThread (aBuildTool, aBuildQueue)); |
270 | aThreads.Last()->Run(); |
271 | } |
272 | |
273 | // Wait until all threads finish their work |
274 | for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) |
275 | { |
276 | aThreads.ChangeValue (aThreadIndex)->Wait(); |
277 | } |
278 | |
279 | // Free unused memory |
280 | theBVH->Reserve (theBVH->Length()); |
281 | } |
282 | else |
283 | { |
284 | BVH_BuildThread aThread (aBuildTool, aBuildQueue); |
285 | |
286 | // Execute thread function inside current thread |
287 | aThread.execute(); |
288 | } |
289 | } |
290 | |
291 | // ======================================================================= |
292 | // function : ~BVH_QueueBuilder |
293 | // purpose : |
294 | // ======================================================================= |
295 | template<class T, int N> |
296 | BVH_QueueBuilder<T, N>::~BVH_QueueBuilder() |
297 | { |
298 | // |
299 | } |
0ef61b50 |
300 | |
301 | #endif // _BVH_QueueBuilder_Header |