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 | |
65578e1c |
16 | #include <NCollection_Vector.hxx> |
17 | |
0ef61b50 |
18 | // ======================================================================= |
19 | // function : BVH_QueueBuilder |
20 | // purpose : Creates new BVH queue based builder |
21 | // ======================================================================= |
22 | template<class T, int N> |
23 | BVH_QueueBuilder<T, N>::BVH_QueueBuilder (const Standard_Integer theLeafNodeSize, |
65578e1c |
24 | const Standard_Integer theMaxTreeDepth, |
25 | const Standard_Integer theNumOfThreads) |
0ef61b50 |
26 | : BVH_Builder<T, N> (theLeafNodeSize, |
65578e1c |
27 | theMaxTreeDepth), |
28 | myNumOfThreads (theNumOfThreads) |
0ef61b50 |
29 | { |
30 | // |
31 | } |
32 | |
33 | // ======================================================================= |
34 | // function : ~BVH_QueueBuilder |
35 | // purpose : Releases resources of BVH queue based builder |
36 | // ======================================================================= |
37 | template<class T, int N> |
38 | BVH_QueueBuilder<T, N>::~BVH_QueueBuilder() |
39 | { |
40 | // |
41 | } |
42 | |
65578e1c |
43 | // ======================================================================= |
44 | // function : AddChildren |
45 | // purpose : |
46 | // ======================================================================= |
47 | template<class T, int N> |
48 | void BVH_QueueBuilder<T, N>::AddChildren (BVH_Tree<T, N>* theBVH, |
49 | const Standard_Integer theNode, |
50 | const typename BVH_QueueBuilder<T, N>::BVH_ChildNodes& theSubNodes) |
51 | { |
52 | Standard_Integer aChildren[] = { -1, -1 }; |
53 | |
54 | if (!theSubNodes.IsValid()) |
55 | { |
56 | return; |
57 | } |
58 | |
59 | // Add child nodes |
60 | { |
61 | Standard_Mutex::Sentry aSentry (myBuildQueue.myMutex); |
62 | |
63 | for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) |
64 | { |
65 | aChildren[anIdx] = theBVH->AddLeafNode (theSubNodes.Boxes[anIdx], |
66 | theSubNodes.Ranges[anIdx].Start, |
67 | theSubNodes.Ranges[anIdx].Final); |
68 | } |
69 | |
70 | BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (theNode) + 1); |
71 | } |
72 | |
73 | // Set parameters of child nodes and generate new tasks |
74 | for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) |
75 | { |
76 | const Standard_Integer aChildIndex = aChildren[anIdx]; |
77 | |
78 | theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; |
79 | |
80 | (anIdx == 0 ? theBVH->LeftChild (theNode) : theBVH->RightChild (theNode)) = aChildIndex; |
81 | |
82 | // Check to see if the child node must be split |
83 | const Standard_Boolean isLeaf = theSubNodes.NbPrims (anIdx) <= BVH_Builder<T, N>::myLeafNodeSize |
84 | || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth; |
85 | |
86 | if (!isLeaf) |
87 | { |
88 | myBuildQueue.Enqueue (aChildIndex); |
89 | } |
90 | } |
91 | } |
92 | |
0ef61b50 |
93 | // ======================================================================= |
94 | // function : Build |
95 | // purpose : Builds BVH using specific algorithm |
96 | // ======================================================================= |
97 | template<class T, int N> |
98 | void BVH_QueueBuilder<T, N>::Build (BVH_Set<T, N>* theSet, |
99 | BVH_Tree<T, N>* theBVH, |
100 | const BVH_Box<T, N>& theBox) |
101 | { |
65578e1c |
102 | Standard_ASSERT_RETURN (theBVH != NULL, |
103 | "Error! BVH tree to construct is NULL", ); |
0ef61b50 |
104 | |
105 | theBVH->Clear(); |
106 | if (theSet->Size() == 0) |
107 | { |
108 | return; |
109 | } |
110 | |
111 | const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, theSet->Size() - 1); |
112 | if (theSet->Size() == 1) |
113 | { |
114 | return; |
115 | } |
116 | |
65578e1c |
117 | myBuildQueue.Enqueue (aRoot); |
118 | |
119 | BVH_TypedBuildTool aBuildTool (theSet, theBVH, this); |
120 | |
121 | if (myNumOfThreads > 1) |
0ef61b50 |
122 | { |
65578e1c |
123 | // Reserve the maximum possible number of nodes in the BVH |
124 | theBVH->Reserve (2 * theSet->Size() - 1); |
0ef61b50 |
125 | |
65578e1c |
126 | NCollection_Vector<Handle(BVH_BuildThread)> aThreads; |
0ef61b50 |
127 | |
65578e1c |
128 | // Run BVH build threads |
129 | for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) |
130 | { |
131 | aThreads.Append (new BVH_BuildThread (aBuildTool, myBuildQueue)); |
132 | aThreads.Last()->Run(); |
133 | } |
134 | |
135 | // Wait until all threads finish their work |
136 | for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) |
137 | { |
138 | aThreads.ChangeValue (aThreadIndex)->Wait(); |
139 | } |
140 | |
141 | // Free unused memory |
142 | theBVH->Reserve (theBVH->Length()); |
143 | } |
144 | else |
145 | { |
146 | BVH_BuildThread aThread (aBuildTool, myBuildQueue); |
147 | |
148 | // Execute thread function inside current thread |
149 | aThread.execute(); |
150 | } |
0ef61b50 |
151 | } |