1 // Created on: 2014-09-15
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #include <NCollection_Vector.hxx>
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,
24 const Standard_Integer theMaxTreeDepth,
25 const Standard_Integer theNumOfThreads)
26 : BVH_Builder<T, N> (theLeafNodeSize,
28 myNumOfThreads (theNumOfThreads)
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()
43 // =======================================================================
44 // function : AddChildren
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)
52 Standard_Integer aChildren[] = { -1, -1 };
54 if (!theSubNodes.IsValid())
61 Standard_Mutex::Sentry aSentry (myBuildQueue.myMutex);
63 for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx)
65 aChildren[anIdx] = theBVH->AddLeafNode (theSubNodes.Boxes[anIdx],
66 theSubNodes.Ranges[anIdx].Start,
67 theSubNodes.Ranges[anIdx].Final);
70 BVH_Builder<T, N>::UpdateDepth (theBVH, theBVH->Level (theNode) + 1);
73 // Set parameters of child nodes and generate new tasks
74 for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx)
76 const Standard_Integer aChildIndex = aChildren[anIdx];
78 theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
80 (anIdx == 0 ? theBVH->LeftChild (theNode) : theBVH->RightChild (theNode)) = aChildIndex;
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;
88 myBuildQueue.Enqueue (aChildIndex);
93 // =======================================================================
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)
102 Standard_ASSERT_RETURN (theBVH != NULL,
103 "Error! BVH tree to construct is NULL", );
106 if (theSet->Size() == 0)
111 const Standard_Integer aRoot = theBVH->AddLeafNode (theBox, 0, theSet->Size() - 1);
112 if (theSet->Size() == 1)
117 myBuildQueue.Enqueue (aRoot);
119 BVH_TypedBuildTool aBuildTool (theSet, theBVH, this);
121 if (myNumOfThreads > 1)
123 // Reserve the maximum possible number of nodes in the BVH
124 theBVH->Reserve (2 * theSet->Size() - 1);
126 NCollection_Vector<Handle(BVH_BuildThread)> aThreads;
128 // Run BVH build threads
129 for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex)
131 aThreads.Append (new BVH_BuildThread (aBuildTool, myBuildQueue));
132 aThreads.Last()->Run();
135 // Wait until all threads finish their work
136 for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex)
138 aThreads.ChangeValue (aThreadIndex)->Wait();
141 // Free unused memory
142 theBVH->Reserve (theBVH->Length());
146 BVH_BuildThread aThread (aBuildTool, myBuildQueue);
148 // Execute thread function inside current thread