From 65578e1c7c224ec364cd02f69e7db9ab076497c5 Mon Sep 17 00:00:00 2001 From: dbp Date: Fri, 17 Jul 2015 14:29:50 +0300 Subject: [PATCH] 0026292: Visualization - Parallelize queue-based BVH builders (subclasses of BVH_QueueBuilder) --- src/BVH/BVH_BinnedBuilder.hxx | 21 +++-- src/BVH/BVH_BinnedBuilder.lxx | 75 +++++---------- src/BVH/BVH_BuildQueue.cxx | 81 ++++++++++++++++ src/BVH/BVH_BuildQueue.hxx | 75 +++++++++++++++ src/BVH/BVH_BuildThread.cxx | 64 +++++++++++++ src/BVH/BVH_BuildThread.hxx | 80 ++++++++++++++++ src/BVH/BVH_DistanceField.lxx | 2 - src/BVH/BVH_QueueBuilder.hxx | 139 ++++++++++++++++++++++++++-- src/BVH/BVH_QueueBuilder.lxx | 111 +++++++++++++++++----- src/BVH/BVH_SweepPlaneBuilder.hxx | 11 ++- src/BVH/BVH_SweepPlaneBuilder.lxx | 65 +++---------- src/BVH/BVH_Tree.hxx | 6 +- src/BVH/BVH_Tree.lxx | 22 ++++- src/BVH/BVH_Types.hxx | 31 +++++++ src/BVH/FILES | 4 + src/OpenGl/OpenGl_SceneGeometry.cxx | 23 +++-- src/OpenGl/OpenGl_SceneGeometry.hxx | 8 +- 17 files changed, 654 insertions(+), 164 deletions(-) create mode 100644 src/BVH/BVH_BuildQueue.cxx create mode 100644 src/BVH/BVH_BuildQueue.hxx create mode 100644 src/BVH/BVH_BuildThread.cxx create mode 100644 src/BVH/BVH_BuildThread.hxx diff --git a/src/BVH/BVH_BinnedBuilder.hxx b/src/BVH/BVH_BinnedBuilder.hxx index ee2c4474e1..80d2dc98b6 100644 --- a/src/BVH/BVH_BinnedBuilder.hxx +++ b/src/BVH/BVH_BinnedBuilder.hxx @@ -20,7 +20,7 @@ #include -//! Stores parameters of single node bin (slice of AABB). +//! Stores parameters of single bin (slice of AABB). template struct BVH_Bin { @@ -31,8 +31,12 @@ struct BVH_Bin BVH_Box Box; //!< AABB of primitives in the bin }; -//! Performs building of BVH tree using binned SAH algorithm. -//! Number of Bins controls tree's quality (greater - better) in cost of construction time. +//! Performs construction of BVH tree using binned SAH algorithm. Number +//! of bins controls BVH quality in cost of construction time (greater - +//! better). For optimal results, use 32 - 48 bins. However, reasonable +//! performance is provided even for 4 - 8 bins (it is only 10-20% lower +//! in comparison with optimal settings). Note that multiple threads can +//! be used only with thread safe BVH primitive sets. template class BVH_BinnedBuilder : public BVH_QueueBuilder { @@ -46,17 +50,18 @@ public: //! Creates binned SAH BVH builder. BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = 5, const Standard_Integer theMaxTreeDepth = 32, - const Standard_Boolean theToUseMainAxis = Standard_False); + const Standard_Boolean theDoMainSplits = 0, + const Standard_Integer theNumOfThreads = 1); //! Releases resources of binned SAH BVH builder. virtual ~BVH_BinnedBuilder(); protected: - //! Builds BVH node for specified task info. - virtual void BuildNode (BVH_Set* theSet, - BVH_Tree* theBVH, - const Standard_Integer theNode); + //! Performs splitting of the given BVH node. + typename BVH_QueueBuilder::BVH_ChildNodes BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode); //! Arranges node primitives into bins. virtual void GetSubVolumes (BVH_Set* theSet, diff --git a/src/BVH/BVH_BinnedBuilder.lxx b/src/BVH/BVH_BinnedBuilder.lxx index 9ab554b509..c0d95c7020 100644 --- a/src/BVH/BVH_BinnedBuilder.lxx +++ b/src/BVH/BVH_BinnedBuilder.lxx @@ -20,10 +20,12 @@ template BVH_BinnedBuilder::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize, const Standard_Integer theMaxTreeDepth, - const Standard_Boolean theToUseMainAxis) + const Standard_Boolean theDoMainSplits, + const Standard_Integer theNumOfThreads) : BVH_QueueBuilder (theLeafNodeSize, - theMaxTreeDepth), - myUseMainAxis (theToUseMainAxis) + theMaxTreeDepth, + theNumOfThreads), + myUseMainAxis (theDoMainSplits) { // } @@ -176,16 +178,16 @@ namespace BVH // purpose : // ======================================================================= template -void BVH_BinnedBuilder::BuildNode (BVH_Set* theSet, - BVH_Tree* theBVH, - const Standard_Integer theNode) +typename BVH_QueueBuilder::BVH_ChildNodes BVH_BinnedBuilder::BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode) { const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder::myLeafNodeSize) { - return; // node does not require partitioning + return typename BVH_QueueBuilder::BVH_ChildNodes(); // node does not require partitioning } const BVH_Box anAABB (theBVH->MinPoint (theNode), @@ -204,7 +206,7 @@ void BVH_BinnedBuilder::BuildNode (BVH_Set* theSet, Standard_Real aMinSplitCost = std::numeric_limits::max(); - Standard_Integer aMainAxis = BVH::BVH_AxisSelector::MainAxis (aSize); + const Standard_Integer aMainAxis = BVH::BVH_AxisSelector::MainAxis (aSize); // Find best split for (Standard_Integer anAxis = myUseMainAxis ? aMainAxis : 0; anAxis <= (myUseMainAxis ? aMainAxis : Min (N - 1, 2)); ++anAxis) @@ -281,52 +283,19 @@ void BVH_BinnedBuilder::BuildNode (BVH_Set* theSet, } else { - aMiddle = BVH::SplitPrimitives (theSet, anAABB, - aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins); + aMiddle = BVH::SplitPrimitives (theSet, + anAABB, + aNodeBegPrimitive, + aNodeEndPrimitive, + aMinSplitIndex - 1, + aMinSplitAxis, + Bins); } - static const Standard_Integer aLftNode = 1; - static const Standard_Integer aRghNode = 2; + typedef typename BVH_QueueBuilder::BVH_PrimitiveRange Range; - // Setting up tasks for child nodes - for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) - { - typename BVH_Box::BVH_VecNt aMinPoint = (aSide == aLftNode) - ? aMinSplitBoxLft.CornerMin() - : aMinSplitBoxRgh.CornerMin(); - typename BVH_Box::BVH_VecNt aMaxPoint = (aSide == aLftNode) - ? aMinSplitBoxLft.CornerMax() - : aMinSplitBoxRgh.CornerMax(); - - Standard_Integer aBegPrimitive = (aSide == aLftNode) - ? aNodeBegPrimitive - : aMiddle; - Standard_Integer aEndPrimitive = (aSide == aLftNode) - ? aMiddle - 1 - : aNodeEndPrimitive; - - Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive); - - theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; - - // Check to see if child node must be split - const Standard_Integer aNbPimitives = (aSide == aLftNode) - ? aMinSplitNumLft - : aMinSplitNumRgh; - - if (aSide == aLftNode) - theBVH->LeftChild (theNode) = aChildIndex; - else - theBVH->RightChild (theNode) = aChildIndex; - - const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder::myLeafNodeSize - || theBVH->Level (aChildIndex) >= BVH_Builder::myMaxTreeDepth; - - if (!isLeaf) - { - BVH_QueueBuilder::myTasksQueue.Append (aChildIndex); - } - - BVH_Builder::UpdateDepth (theBVH, theBVH->Level (aChildIndex)); - } + return typename BVH_QueueBuilder::BVH_ChildNodes (aMinSplitBoxLft, + aMinSplitBoxRgh, + Range (aNodeBegPrimitive, aMiddle - 1), + Range (aMiddle, aNodeEndPrimitive)); } diff --git a/src/BVH/BVH_BuildQueue.cxx b/src/BVH/BVH_BuildQueue.cxx new file mode 100644 index 0000000000..86b48569d4 --- /dev/null +++ b/src/BVH/BVH_BuildQueue.cxx @@ -0,0 +1,81 @@ +// Created on: 2015-05-27 +// Created by: Denis BOGOLEPOV +// Copyright (c) 2015 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + +// ======================================================================= +// function : Size +// purpose : Returns current size of BVH build queue +// ======================================================================= +Standard_Integer BVH_BuildQueue::Size() +{ + Standard_Integer aSize; + + myMutex.Lock(); + { + aSize = myQueue.Size(); + } + myMutex.Unlock(); + + return aSize; +} + +// ======================================================================= +// function : Enqueue +// purpose : Enqueues new work-item onto BVH build queue +// ======================================================================= +void BVH_BuildQueue::Enqueue (const Standard_Integer& theWorkItem) +{ + myMutex.Lock(); + { + myQueue.Append (theWorkItem); + } + myMutex.Unlock(); +} + +// ======================================================================= +// function : Fetch +// purpose : Fetches first work-item from BVH build queue +// ======================================================================= +Standard_Integer BVH_BuildQueue::Fetch (Standard_Boolean& wasBusy) +{ + Standard_Integer aQuery = -1; + { + Standard_Mutex::Sentry aSentry (myMutex); + + if (!myQueue.IsEmpty()) + { + aQuery = myQueue.First(); + + myQueue.Remove (1); // remove item from queue + } + + if (aQuery != -1) + { + if (!wasBusy) + { + ++myNbThreads; + } + } + else if (wasBusy) + { + --myNbThreads; + } + + wasBusy = aQuery != -1; + } + + return aQuery; +} diff --git a/src/BVH/BVH_BuildQueue.hxx b/src/BVH/BVH_BuildQueue.hxx new file mode 100644 index 0000000000..ab7d5cc31e --- /dev/null +++ b/src/BVH/BVH_BuildQueue.hxx @@ -0,0 +1,75 @@ +// Created on: 2015-05-28 +// Created by: Denis BOGOLEPOV +// Copyright (c) 2015 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#ifndef _BVH_BuildQueue_Header +#define _BVH_BuildQueue_Header + +#include + +#include +#include + +//! Command-queue for parallel building of BVH nodes. +class BVH_BuildQueue +{ + template friend class BVH_QueueBuilder; + +public: + + //! Creates new BVH build queue. + BVH_BuildQueue() + : myNbThreads (0) + { + // + } + + //! Releases resources of BVH build queue. + ~BVH_BuildQueue() + { + // + } + +public: + + //! Returns current size of BVH build queue. + Standard_EXPORT Standard_Integer Size(); + + //! Enqueues new work-item onto BVH build queue. + Standard_EXPORT void Enqueue (const Standard_Integer& theNode); + + //! Fetches first work-item from BVH build queue. + Standard_EXPORT Standard_Integer Fetch (Standard_Boolean& wasBusy); + + //! Checks if there are active build threads. + Standard_Boolean HasBusyThreads() + { + return myNbThreads != 0; + } + +protected: + + //! Queue of BVH nodes to build. + NCollection_Sequence myQueue; + +protected: + + //! Manages access serialization of working threads. + Standard_Mutex myMutex; + + //! Number of active build threads. + Standard_Integer myNbThreads; +}; + +#endif // _BVH_BuildQueue_Header diff --git a/src/BVH/BVH_BuildThread.cxx b/src/BVH/BVH_BuildThread.cxx new file mode 100644 index 0000000000..9e0fc4c8f9 --- /dev/null +++ b/src/BVH/BVH_BuildThread.cxx @@ -0,0 +1,64 @@ +// Created on: 2015-05-29 +// Created by: Denis BOGOLEPOV +// Copyright (c) 2013-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#include + +// ======================================================================= +// function : BVH_BuildThread +// purpose : Creates new BVH build thread +// ======================================================================= +BVH_BuildThread::BVH_BuildThread (BVH_BuildTool& theBuildTool, + BVH_BuildQueue& theBuildQueue) +: myBuildTool (theBuildTool), + myBuildQueue (theBuildQueue), + myWorkThread (threadFunction) +{ + // +} + +// ======================================================================= +// function : execute +// purpose : Executes BVH build thread +// ======================================================================= +void BVH_BuildThread::execute() +{ + for (Standard_Boolean wasBusy = Standard_False; /**/; /**/) + { + const Standard_Integer aNode = myBuildQueue.Fetch (wasBusy); + + if (aNode == -1) // queue is empty + { + if (!myBuildQueue.HasBusyThreads()) + { + break; // no active threads + } + } + else + { + myBuildTool.Perform (aNode); + } + } +} + +// ======================================================================= +// function : threadFunction +// purpose : Thread function for BVH build thread +// ======================================================================= +Standard_Address BVH_BuildThread::threadFunction (Standard_Address theData) +{ + static_cast (theData)->execute(); + + return NULL; +} diff --git a/src/BVH/BVH_BuildThread.hxx b/src/BVH/BVH_BuildThread.hxx new file mode 100644 index 0000000000..0200497f05 --- /dev/null +++ b/src/BVH/BVH_BuildThread.hxx @@ -0,0 +1,80 @@ +// Created on: 2015-05-29 +// Created by: Denis BOGOLEPOV +// Copyright (c) 2013-2014 OPEN CASCADE SAS +// +// This file is part of Open CASCADE Technology software library. +// +// This library is free software; you can redistribute it and/or modify it under +// the terms of the GNU Lesser General Public License version 2.1 as published +// by the Free Software Foundation, with special exception defined in the file +// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT +// distribution for complete text of the license and disclaimer of any warranty. +// +// Alternatively, this file may be used under the terms of Open CASCADE +// commercial license or contractual agreement. + +#ifndef _BVH_BuildThread_Header +#define _BVH_BuildThread_Header + +#include +#include + +//! Tool object to call BVH builder subroutines. +struct BVH_BuildTool +{ + //! Performs splitting of the given BVH node. + virtual void Perform (const Standard_Integer theNode) = 0; +}; + +//! Wrapper for BVH build thread. +class BVH_BuildThread : public Standard_Transient +{ + template friend class BVH_QueueBuilder; + +public: + + //! Creates new BVH build thread. + Standard_EXPORT BVH_BuildThread (BVH_BuildTool& theBuildTool, BVH_BuildQueue& theBuildQueue); + + //! Starts execution of BVH build thread. + void Run() + { + myWorkThread.Run (this); + } + + //! Waits till the thread finishes execution. + void Wait() + { + myWorkThread.Wait(); + } + +protected: + + //! Executes BVH build thread. + Standard_EXPORT void execute(); + + //! Thread function for BVH build thread. + static Standard_Address threadFunction (Standard_Address theData); + + //! Assignment operator (to remove VC compile warning). + BVH_BuildThread& operator= (const BVH_BuildThread&); + +protected: + + //! Data needed to build the BVH. + BVH_BuildTool& myBuildTool; + + //! Reference to BVH build queue. + BVH_BuildQueue& myBuildQueue; + + //! Thread to execute work items. + OSD_Thread myWorkThread; + +public: + + DEFINE_STANDARD_RTTI(BVH_BuildThread, Standard_Transient) +}; + +DEFINE_STANDARD_HANDLE (BVH_BuildThread, Standard_Transient) + +#endif // _BVH_BuildThread_Header diff --git a/src/BVH/BVH_DistanceField.lxx b/src/BVH/BVH_DistanceField.lxx index 570cc7a0cc..9d183a991b 100644 --- a/src/BVH/BVH_DistanceField.lxx +++ b/src/BVH/BVH_DistanceField.lxx @@ -13,8 +13,6 @@ // Alternatively, this file may be used under the terms of Open CASCADE // commercial license or contractual agreement. -#include - #include #ifdef HAVE_TBB diff --git a/src/BVH/BVH_QueueBuilder.hxx b/src/BVH/BVH_QueueBuilder.hxx index 4c0d86b4f3..a27ef13651 100644 --- a/src/BVH/BVH_QueueBuilder.hxx +++ b/src/BVH/BVH_QueueBuilder.hxx @@ -17,10 +17,19 @@ #define _BVH_QueueBuilder_Header #include - +#include #include //! Abstract BVH builder based on the concept of work queue. +//! Queue based BVH builders support parallelization with a +//! fixed number of threads (maximum efficiency is achieved +//! by setting the number of threads equal to the number of +//! CPU cores plus one). Note that to support parallel mode, +//! a corresponding BVH primitive set should provide thread +//! safe implementations of interface functions (e.g., Swap, +//! Box, Center). Otherwise, the results will be undefined. +//! \tparam T Numeric data type +//! \tparam N Vector dimension template class BVH_QueueBuilder : public BVH_Builder { @@ -28,7 +37,8 @@ public: //! Creates new BVH queue based builder. BVH_QueueBuilder (const Standard_Integer theLeafNodeSize, - const Standard_Integer theMaxTreeDepth); + const Standard_Integer theMaxTreeDepth, + const Standard_Integer theNumOfThreads = 1); //! Releases resources of BVH queue based builder. virtual ~BVH_QueueBuilder() = 0; @@ -42,14 +52,129 @@ public: protected: - //! Builds BVH node for the given task info. - virtual void BuildNode (BVH_Set* theSet, - BVH_Tree* theBVH, - const Standard_Integer theTask); + //! Stores range of primitives belonging to a BVH node. + struct BVH_PrimitiveRange + { + Standard_Integer Start; + Standard_Integer Final; + + //! Creates new primitive range. + BVH_PrimitiveRange (Standard_Integer theStart = -1, + Standard_Integer theFinal = -1) + : Start (theStart), + Final (theFinal) + { + // + } + + //! Returns total number of primitives. + Standard_Integer Size() const + { + return Final - Start + 1; + } + + //! Checks if the range is initialized. + Standard_Boolean IsValid() const + { + return Start != -1; + } + }; + + //! Stores parameters of constructed child nodes. + struct BVH_ChildNodes + { + //! Bounding boxes of child nodes. + BVH_Box Boxes[2]; + + //! Primitive ranges of child nodes. + BVH_PrimitiveRange Ranges[2]; + + //! Creates new parameters of BVH child nodes. + BVH_ChildNodes() + { + // + } + + //! Creates new parameters of BVH child nodes. + BVH_ChildNodes (const BVH_Box& theLftBox, + const BVH_Box& theRghBox, + const BVH_PrimitiveRange& theLftRange, + const BVH_PrimitiveRange& theRghRange) + { + Boxes[0] = theLftBox; + Boxes[1] = theRghBox; + Ranges[0] = theLftRange; + Ranges[1] = theRghRange; + } + + //! Returns number of primitives in the given child. + Standard_Integer NbPrims (const Standard_Integer theChild) const + { + return Ranges[theChild].Size(); + } + + //! Checks if the parameters is initialized. + Standard_Boolean IsValid() const + { + return Ranges[0].IsValid() && Ranges[1].IsValid(); + } + }; + + //! Wrapper for BVH build data. + class BVH_TypedBuildTool : public BVH_BuildTool + { + public: + + //! Creates new BVH build thread. + BVH_TypedBuildTool (BVH_Set* theSet, + BVH_Tree* theBVH, + BVH_Builder* theAlgo) + : mySet (theSet), + myBVH (theBVH) + { + myAlgo = dynamic_cast* > (theAlgo); + + Standard_ASSERT_RAISE (myAlgo != NULL, + "Error! BVH builder should be queue based"); + } + + //! Performs splitting of the given BVH node. + virtual void Perform (const Standard_Integer theNode) + { + const typename BVH_QueueBuilder::BVH_ChildNodes aChildren = myAlgo->BuildNode (mySet, myBVH, theNode); + + myAlgo->AddChildren (myBVH, theNode, aChildren); + } + + protected: + + //! Primitive set to build BVH. + BVH_Set* mySet; + + //! Output BVH tree for the set. + BVH_Tree* myBVH; + + //! Queue based BVH builder to use. + BVH_QueueBuilder* myAlgo; + }; + +protected: + + //! Performs splitting of the given BVH node. + virtual typename BVH_QueueBuilder::BVH_ChildNodes BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode) = 0; + + //! Processes child nodes of the splitted BVH node. + virtual void AddChildren (BVH_Tree* theBVH, + const Standard_Integer theNode, + const BVH_ChildNodes& theSubNodes); protected: - NCollection_Vector myTasksQueue; //!< Queue to manage BVH node building tasks + BVH_BuildQueue myBuildQueue; //!< Queue to manage BVH node building tasks + + Standard_Integer myNumOfThreads; //!< Number of threads used to build BVH }; diff --git a/src/BVH/BVH_QueueBuilder.lxx b/src/BVH/BVH_QueueBuilder.lxx index 70d8bf13d5..20ecff23dd 100644 --- a/src/BVH/BVH_QueueBuilder.lxx +++ b/src/BVH/BVH_QueueBuilder.lxx @@ -13,15 +13,19 @@ // Alternatively, this file may be used under the terms of Open CASCADE // commercial license or contractual agreement. +#include + // ======================================================================= // function : BVH_QueueBuilder // purpose : Creates new BVH queue based builder // ======================================================================= template BVH_QueueBuilder::BVH_QueueBuilder (const Standard_Integer theLeafNodeSize, - const Standard_Integer theMaxTreeDepth) + const Standard_Integer theMaxTreeDepth, + const Standard_Integer theNumOfThreads) : BVH_Builder (theLeafNodeSize, - theMaxTreeDepth) + theMaxTreeDepth), + myNumOfThreads (theNumOfThreads) { // } @@ -36,6 +40,56 @@ BVH_QueueBuilder::~BVH_QueueBuilder() // } +// ======================================================================= +// function : AddChildren +// purpose : +// ======================================================================= +template +void BVH_QueueBuilder::AddChildren (BVH_Tree* theBVH, + const Standard_Integer theNode, + const typename BVH_QueueBuilder::BVH_ChildNodes& theSubNodes) +{ + Standard_Integer aChildren[] = { -1, -1 }; + + if (!theSubNodes.IsValid()) + { + return; + } + + // Add child nodes + { + Standard_Mutex::Sentry aSentry (myBuildQueue.myMutex); + + for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) + { + aChildren[anIdx] = theBVH->AddLeafNode (theSubNodes.Boxes[anIdx], + theSubNodes.Ranges[anIdx].Start, + theSubNodes.Ranges[anIdx].Final); + } + + BVH_Builder::UpdateDepth (theBVH, theBVH->Level (theNode) + 1); + } + + // Set parameters of child nodes and generate new tasks + for (Standard_Integer anIdx = 0; anIdx < 2; ++anIdx) + { + const Standard_Integer aChildIndex = aChildren[anIdx]; + + theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; + + (anIdx == 0 ? theBVH->LeftChild (theNode) : theBVH->RightChild (theNode)) = aChildIndex; + + // Check to see if the child node must be split + const Standard_Boolean isLeaf = theSubNodes.NbPrims (anIdx) <= BVH_Builder::myLeafNodeSize + || theBVH->Level (aChildIndex) >= BVH_Builder::myMaxTreeDepth; + + if (!isLeaf) + { + myBuildQueue.Enqueue (aChildIndex); + } + } +} + // ======================================================================= // function : Build // purpose : Builds BVH using specific algorithm @@ -45,10 +99,8 @@ void BVH_QueueBuilder::Build (BVH_Set* theSet, BVH_Tree* theBVH, const BVH_Box& theBox) { - if (theBVH == NULL) - { - return; - } + Standard_ASSERT_RETURN (theBVH != NULL, + "Error! BVH tree to construct is NULL", ); theBVH->Clear(); if (theSet->Size() == 0) @@ -62,23 +114,38 @@ void BVH_QueueBuilder::Build (BVH_Set* theSet, return; } - myTasksQueue.Append (aRoot); - for (Standard_Integer aTask = 0; aTask < myTasksQueue.Size(); ++aTask) + myBuildQueue.Enqueue (aRoot); + + BVH_TypedBuildTool aBuildTool (theSet, theBVH, this); + + if (myNumOfThreads > 1) { - BuildNode (theSet, theBVH, myTasksQueue.Value (aTask)); - } + // Reserve the maximum possible number of nodes in the BVH + theBVH->Reserve (2 * theSet->Size() - 1); - myTasksQueue.Clear(); -} + NCollection_Vector aThreads; -// ======================================================================= -// function : BuildNode -// purpose : Builds BVH node for the given task info -// ======================================================================= -template -void BVH_QueueBuilder::BuildNode (BVH_Set* /* theSet */, - BVH_Tree* /* theBVH */, - const Standard_Integer /* theTask */) -{ - // needed to disable compile warnings + // Run BVH build threads + for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) + { + aThreads.Append (new BVH_BuildThread (aBuildTool, myBuildQueue)); + aThreads.Last()->Run(); + } + + // Wait until all threads finish their work + for (Standard_Integer aThreadIndex = 0; aThreadIndex < myNumOfThreads; ++aThreadIndex) + { + aThreads.ChangeValue (aThreadIndex)->Wait(); + } + + // Free unused memory + theBVH->Reserve (theBVH->Length()); + } + else + { + BVH_BuildThread aThread (aBuildTool, myBuildQueue); + + // Execute thread function inside current thread + aThread.execute(); + } } diff --git a/src/BVH/BVH_SweepPlaneBuilder.hxx b/src/BVH/BVH_SweepPlaneBuilder.hxx index 8d05d5f206..ab802ca63d 100644 --- a/src/BVH/BVH_SweepPlaneBuilder.hxx +++ b/src/BVH/BVH_SweepPlaneBuilder.hxx @@ -26,17 +26,18 @@ public: //! Creates sweep plane SAH BVH builder. BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize = 5, - const Standard_Integer theMaxTreeDepth = 32); + const Standard_Integer theMaxTreeDepth = 32, + const Standard_Integer theNumOfThreads = 1); //! Releases resources of sweep plane SAH BVH builder. virtual ~BVH_SweepPlaneBuilder(); protected: - //! Builds specified BVH node. - virtual void BuildNode (BVH_Set* theSet, - BVH_Tree* theBVH, - const Standard_Integer theNode); + //! Performs splitting of the given BVH node. + typename BVH_QueueBuilder::BVH_ChildNodes BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode); }; diff --git a/src/BVH/BVH_SweepPlaneBuilder.lxx b/src/BVH/BVH_SweepPlaneBuilder.lxx index 1e85e674ad..697c9625b1 100644 --- a/src/BVH/BVH_SweepPlaneBuilder.lxx +++ b/src/BVH/BVH_SweepPlaneBuilder.lxx @@ -23,9 +23,11 @@ // ======================================================================= template BVH_SweepPlaneBuilder::BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize, - const Standard_Integer theMaxTreeDepth) + const Standard_Integer theMaxTreeDepth, + const Standard_Integer theNumOfThreads) : BVH_QueueBuilder (theLeafNodeSize, - theMaxTreeDepth) + theMaxTreeDepth, + theNumOfThreads) { // } @@ -45,9 +47,9 @@ BVH_SweepPlaneBuilder::~BVH_SweepPlaneBuilder() // purpose : // ======================================================================= template -void BVH_SweepPlaneBuilder::BuildNode (BVH_Set* theSet, - BVH_Tree* theBVH, - const Standard_Integer theNode) +typename BVH_QueueBuilder::BVH_ChildNodes BVH_SweepPlaneBuilder::BuildNode (BVH_Set* theSet, + BVH_Tree* theBVH, + const Standard_Integer theNode) { const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); @@ -55,7 +57,7 @@ void BVH_SweepPlaneBuilder::BuildNode (BVH_Set* theSet, if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder::myLeafNodeSize) { - return; // node does not require partitioning + return typename BVH_QueueBuilder::BVH_ChildNodes(); // node does not require partitioning } // Parameters for storing best split @@ -118,7 +120,7 @@ void BVH_SweepPlaneBuilder::BuildNode (BVH_Set* theSet, if (aMinSplitAxis == -1) { - return; + return typename BVH_QueueBuilder::BVH_ChildNodes(); // failed to find split axis } theBVH->SetInner (theNode); @@ -144,49 +146,10 @@ void BVH_SweepPlaneBuilder::BuildNode (BVH_Set* theSet, const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex; - static const Standard_Integer aLftNode = 1; - static const Standard_Integer aRghNode = 2; + typedef typename BVH_QueueBuilder::BVH_PrimitiveRange Range; - // Setting up tasks for child nodes - for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide) - { - typename BVH_Box::BVH_VecNt aChildMinPoint = (aSide == aLftNode) - ? aMinSplitBoxLft.CornerMin() - : aMinSplitBoxRgh.CornerMin(); - typename BVH_Box::BVH_VecNt aChildMaxPoint = (aSide == aLftNode) - ? aMinSplitBoxLft.CornerMax() - : aMinSplitBoxRgh.CornerMax(); - - Standard_Integer aChildBegPrimitive = (aSide == aLftNode) - ? aNodeBegPrimitive - : aMiddle; - Standard_Integer aChildEndPrimitive = (aSide == aLftNode) - ? aMiddle - 1 - : aNodeEndPrimitive; - - Standard_Integer aChildIndex = theBVH->AddLeafNode (aChildMinPoint, aChildMaxPoint, - aChildBegPrimitive, aChildEndPrimitive); - - theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1; - - // Check to see if child node must be split - const Standard_Integer aChildNbPimitives = (aSide == aLftNode) - ? aMiddle - aNodeBegPrimitive - : aNodeEndPrimitive - aMiddle + 1; - - if (aSide == aLftNode) - theBVH->LeftChild (theNode) = aChildIndex; - else - theBVH->RightChild (theNode) = aChildIndex; - - const Standard_Boolean isLeaf = aChildNbPimitives <= BVH_Builder::myLeafNodeSize - || theBVH->Level (aChildIndex) >= BVH_Builder::myMaxTreeDepth; - - if (!isLeaf) - { - BVH_QueueBuilder::myTasksQueue.Append (aChildIndex); - } - - BVH_Builder::UpdateDepth (theBVH, theBVH->Level (aChildIndex)); - } + return typename BVH_QueueBuilder::BVH_ChildNodes (aMinSplitBoxLft, + aMinSplitBoxRgh, + Range (aNodeBegPrimitive, aMiddle - 1), + Range (aMiddle, aNodeEndPrimitive)); } diff --git a/src/BVH/BVH_Tree.hxx b/src/BVH/BVH_Tree.hxx index fecaabd71d..5c323a951f 100644 --- a/src/BVH/BVH_Tree.hxx +++ b/src/BVH/BVH_Tree.hxx @@ -47,6 +47,10 @@ public: // } + //! Reserves internal BVH storage, so that it + //! can contain specified number of tree nodes. + void Reserve (const Standard_Integer theNbNodes); + //! Returns minimum point of the given node. BVH_VecNt& MinPoint (const Standard_Integer theNodeIndex) { @@ -256,7 +260,7 @@ protected: //! Array of node data records. BVH_Array4i myNodeInfoBuffer; - //! Depth of constructed tree. + //! Current depth of BVH tree. Standard_Integer myDepth; }; diff --git a/src/BVH/BVH_Tree.lxx b/src/BVH/BVH_Tree.lxx index e0bd7d0076..549c6893a1 100644 --- a/src/BVH/BVH_Tree.lxx +++ b/src/BVH/BVH_Tree.lxx @@ -99,7 +99,10 @@ Standard_Integer BVH_Tree::AddLeafNode (const BVH_Box& theAABB, const Standard_Integer theBegElem, const Standard_Integer theEndElem) { - return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem); + return AddLeafNode (theAABB.CornerMin(), + theAABB.CornerMax(), + theBegElem, + theEndElem); } // ======================================================================= @@ -111,7 +114,10 @@ Standard_Integer BVH_Tree::AddInnerNode (const BVH_Box& theAABB, const Standard_Integer theLftChild, const Standard_Integer theRghChild) { - return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild); + return AddInnerNode (theAABB.CornerMin(), + theAABB.CornerMax(), + theLftChild, + theRghChild); } namespace BVH @@ -167,3 +173,15 @@ T BVH_Tree::EstimateSAH() const BVH::EstimateSAH (this, 0, static_cast (1.0), aSAH); return aSAH; } + +// ======================================================================= +// function : Reserve +// purpose : +// ======================================================================= +template +void BVH_Tree::Reserve (const Standard_Integer theNbNodes) +{ + BVH::Array::Reserve (myMinPointBuffer, theNbNodes); + BVH::Array::Reserve (myMaxPointBuffer, theNbNodes); + BVH::Array::Reserve (myNodeInfoBuffer, theNbNodes); +} diff --git a/src/BVH/BVH_Types.hxx b/src/BVH/BVH_Types.hxx index afada8168a..a556672efd 100644 --- a/src/BVH/BVH_Types.hxx +++ b/src/BVH/BVH_Types.hxx @@ -26,6 +26,11 @@ #include #include +// GCC supports shrink function only in C++11 mode +#if defined(_BVH_USE_STD_VECTOR_) && defined(_MSC_VER) && !defined(__INTEL_COMPILER) + #define _STD_VECTOR_SHRINK +#endif + namespace BVH { //! Tool class for selecting appropriate vector type (Eigen or NCollection). @@ -179,6 +184,7 @@ namespace BVH { typedef typename BVH::ArrayType::Type BVH_ArrayNt; + //! Returns a const reference to the element with the given index. static inline const typename BVH::VectorType::Type& Value ( const BVH_ArrayNt& theArray, const Standard_Integer theIndex) { @@ -189,6 +195,7 @@ namespace BVH #endif } + //! Returns a reference to the element with the given index. static inline typename BVH::VectorType::Type& ChangeValue ( BVH_ArrayNt& theArray, const Standard_Integer theIndex) { @@ -199,6 +206,7 @@ namespace BVH #endif } + //! Adds the new element at the end of the array. static inline void Append (BVH_ArrayNt& theArray, const typename BVH::VectorType::Type& theElement) { @@ -209,6 +217,7 @@ namespace BVH #endif } + //! Returns the number of elements in the given array. static inline Standard_Integer Size (const BVH_ArrayNt& theArray) { #ifdef _BVH_USE_STD_VECTOR_ @@ -218,12 +227,34 @@ namespace BVH #endif } + //! Removes all elements from the given array. static inline void Clear (BVH_ArrayNt& theArray) { #ifdef _BVH_USE_STD_VECTOR_ theArray.clear(); #else theArray.Clear(); +#endif + } + + //! Requests that the array capacity be at least enough to + //! contain given number of elements. This function has no + //! effect in case of NCollection based array. + static inline void Reserve (BVH_ArrayNt& theArray, const Standard_Integer theCount) + { +#ifdef _BVH_USE_STD_VECTOR_ + if (Size (theArray) == theCount) + { +#ifdef _STD_VECTOR_SHRINK + theArray.shrink_to_fit(); +#endif + } + else + { + theArray.reserve (theCount); + } +#else + // do nothing #endif } }; diff --git a/src/BVH/FILES b/src/BVH/FILES index 15b1a1dc85..3684e1286a 100644 --- a/src/BVH/FILES +++ b/src/BVH/FILES @@ -5,6 +5,10 @@ BVH_Box.hxx BVH_Box.lxx BVH_Builder.hxx BVH_Builder.lxx +BVH_BuildQueue.hxx +BVH_BuildQueue.cxx +BVH_BuildThread.hxx +BVH_BuildThread.cxx BVH_DistanceField.hxx BVH_DistanceField.lxx BVH_Geometry.hxx diff --git a/src/OpenGl/OpenGl_SceneGeometry.cxx b/src/OpenGl/OpenGl_SceneGeometry.cxx index 5ae251340d..f1d8ec1a8b 100755 --- a/src/OpenGl/OpenGl_SceneGeometry.cxx +++ b/src/OpenGl/OpenGl_SceneGeometry.cxx @@ -13,16 +13,13 @@ // Alternatively, this file may be used under the terms of Open CASCADE // commercial license or contractual agreement. -#include +#include #include - -#include - +#include #include #include +#include #include -#include -#include #include //! Use this macro to output BVH profiling info @@ -181,6 +178,18 @@ OpenGl_TriangleSet::BVH_BoxNt OpenGl_TriangleSet::Box() const return aBox; } +// ======================================================================= +// function : OpenGl_TriangleSet +// purpose : Creates new OpenGL element triangulation +// ======================================================================= +OpenGl_TriangleSet::OpenGl_TriangleSet (const Standard_Size theArrayID) +: BVH_Triangulation(), + myArrayID (theArrayID) +{ + myBuilder = new BVH_BinnedBuilder + (5 /* leaf size */, 32 /* max height */, Standard_False, OSD_Parallel::NbLogicalProcessors() + 1 /* threads */); +} + // ======================================================================= // function : Clear // purpose : Clears ray-tracing geometry @@ -205,7 +214,7 @@ struct OpenGL_BVHParallelBuilder BVH_ObjectSet* Set; OpenGL_BVHParallelBuilder (BVH_ObjectSet* theSet) - : Set (theSet) + : Set (theSet) { // } diff --git a/src/OpenGl/OpenGl_SceneGeometry.hxx b/src/OpenGl/OpenGl_SceneGeometry.hxx index c83f25671e..74393ddb43 100755 --- a/src/OpenGl/OpenGl_SceneGeometry.hxx +++ b/src/OpenGl/OpenGl_SceneGeometry.hxx @@ -18,6 +18,7 @@ #include #include +#include #include #include #include @@ -166,12 +167,7 @@ public: public: //! Creates new OpenGL element triangulation. - OpenGl_TriangleSet (const Standard_Size theArrayID) - : BVH_Triangulation(), - myArrayID (theArrayID) - { - // - } + OpenGl_TriangleSet (const Standard_Size theArrayID); //! Releases resources of OpenGL element triangulation. ~OpenGl_TriangleSet() -- 2.20.1