src/BVH/BVH_QueueBuilder.hxx

   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>
  20 #include <BVH_BuildThread.hxx>
  21 #include <NCollection_Vector.hxx>
  22
  23 //! Abstract BVH builder based on the concept of work queue.
  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
  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,
  40                     const Standard_Integer theMaxTreeDepth,
  41                     const Standard_Integer theNumOfThreads = 1)
  42   : BVH_Builder<T, N> (theLeafNodeSize,
  43                        theMaxTreeDepth),
  44     myNumOfThreads (theNumOfThreads) {}
  45
  46   //! Releases resources of BVH queue based builder.
  47   virtual ~BVH_QueueBuilder() {}
  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,
  54                       const BVH_Box<T, N>& theBox) const Standard_OVERRIDE;
  55
  56 protected:
  57
  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.
 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)
 136     : mySet  (theSet),
 137       myBVH  (theBVH),
 138       myBuildQueue (&theBuildQueue),
 139       myAlgo (theAlgo)
 140     {
 141       Standard_ASSERT_RAISE (myAlgo != NULL, "Error! BVH builder should be queue based");
 142     }
 143
 144     //! Performs splitting of the given BVH node.
 145     virtual void Perform (const Standard_Integer theNode) Standard_OVERRIDE
 146     {
 147       const typename BVH_QueueBuilder<T, N>::BVH_ChildNodes aChildren = myAlgo->buildNode (mySet, myBVH, theNode);
 148       myAlgo->addChildren (myBVH, *myBuildQueue, theNode, aChildren);
 149     }
 150
 151   protected:
 152
 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
 157
 158   };
 159
 160 protected:
 161
 162   //! Performs splitting of the given BVH node.
 163   virtual typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>*         theSet,
 164                                                                      BVH_Tree<T, N>*        theBVH,
 165                                                                      const Standard_Integer theNode) const = 0;
 166
 167   //! Processes child nodes of the splitted BVH node.
 168   virtual void addChildren (BVH_Tree<T, N>*        theBVH,
 169                             BVH_BuildQueue&        theBuildQueue,
 170                                                         const Standard_Integer theNode,
 171                             const BVH_ChildNodes&  theSubNodes) const;
 172
 173 protected:
 174
 175   Standard_Integer myNumOfThreads; //!< Number of threads used to build BVH
 176
 177 };
 178
 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 #endif // _BVH_QueueBuilder_Header