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
  43   //! Releases resources of BVH queue based builder.
  44   virtual ~BVH_QueueBuilder() = 0;
  45
  46 public:
  47
  48   //! Builds BVH using specific algorithm.
  49   virtual void Build (BVH_Set<T, N>*       theSet,
  50                       BVH_Tree<T, N>*      theBVH,
  51                       const BVH_Box<T, N>& theBox);
  52
  53 protected:
  54
  55   //! Stores range of primitives belonging to a BVH node.
  56   struct BVH_PrimitiveRange
  57   {
  58     Standard_Integer Start;
  59     Standard_Integer Final;
  60
  61     //! Creates new primitive range.
  62     BVH_PrimitiveRange (Standard_Integer theStart = -1,
  63                         Standard_Integer theFinal = -1)
  64     : Start (theStart),
  65       Final (theFinal)
  66     {
  67       //
  68     }
  69
  70     //! Returns total number of primitives.
  71     Standard_Integer Size() const
  72     {
  73       return Final - Start + 1;
  74     }
  75
  76     //! Checks if the range is initialized.
  77     Standard_Boolean IsValid() const
  78     {
  79       return Start != -1;
  80     }
  81   };
  82
  83   //! Stores parameters of constructed child nodes.
  84   struct BVH_ChildNodes
  85   {
  86     //! Bounding boxes of child nodes.
  87     BVH_Box<T, N> Boxes[2];
  88
  89     //! Primitive ranges of child nodes.
  90     BVH_PrimitiveRange Ranges[2];
  91
  92     //! Creates new parameters of BVH child nodes.
  93     BVH_ChildNodes()
  94     {
  95       //
  96     }
  97
  98     //! Creates new parameters of BVH child nodes.
  99     BVH_ChildNodes (const BVH_Box<T, N>&      theLftBox,
 100                     const BVH_Box<T, N>&      theRghBox,
 101                     const BVH_PrimitiveRange& theLftRange,
 102                     const BVH_PrimitiveRange& theRghRange)
 103     {
 104       Boxes[0]  = theLftBox;
 105       Boxes[1]  = theRghBox;
 106       Ranges[0] = theLftRange;
 107       Ranges[1] = theRghRange;
 108     }
 109
 110     //! Returns number of primitives in the given child.
 111     Standard_Integer NbPrims (const Standard_Integer theChild) const
 112     {
 113       return Ranges[theChild].Size();
 114     }
 115
 116     //! Checks if the parameters is initialized.
 117     Standard_Boolean IsValid() const
 118     {
 119       return Ranges[0].IsValid() && Ranges[1].IsValid();
 120     }
 121   };
 122
 123   //! Wrapper for BVH build data.
 124   class BVH_TypedBuildTool : public BVH_BuildTool
 125   {
 126   public:
 127
 128     //! Creates new BVH build thread.
 129     BVH_TypedBuildTool (BVH_Set<T, N>*     theSet,
 130                         BVH_Tree<T, N>*    theBVH,
 131                         BVH_Builder<T, N>* theAlgo)
 132     : mySet  (theSet),
 133       myBVH  (theBVH)
 134     {
 135       myAlgo = dynamic_cast<BVH_QueueBuilder<T, N>* > (theAlgo);
 136
 137       Standard_ASSERT_RAISE (myAlgo != NULL,
 138         "Error! BVH builder should be queue based");
 139     }
 140
 141     //! Performs splitting of the given BVH node.
 142     virtual void Perform (const Standard_Integer theNode)
 143     {
 144       const typename BVH_QueueBuilder<T, N>::BVH_ChildNodes aChildren = myAlgo->BuildNode (mySet, myBVH, theNode);
 145
 146       myAlgo->AddChildren (myBVH, theNode, aChildren);
 147     }
 148
 149   protected:
 150
 151     //! Primitive set to build BVH.
 152     BVH_Set<T, N>* mySet;
 153
 154     //! Output BVH tree for the set.
 155     BVH_Tree<T, N>* myBVH;
 156
 157     //! Queue based BVH builder to use.
 158     BVH_QueueBuilder<T, N>* myAlgo;
 159   };
 160
 161 protected:
 162
 163   //! Performs splitting of the given BVH node.
 164   virtual typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BuildNode (BVH_Set<T, N>*         theSet,
 165                                                                      BVH_Tree<T, N>*        theBVH,
 166                                                                      const Standard_Integer theNode) = 0;
 167
 168   //! Processes child nodes of the splitted BVH node.
 169   virtual void AddChildren (BVH_Tree<T, N>*        theBVH,
 170                             const Standard_Integer theNode,
 171                             const BVH_ChildNodes&  theSubNodes);
 172
 173 protected:
 174
 175   BVH_BuildQueue myBuildQueue; //!< Queue to manage BVH node building tasks
 176
 177   Standard_Integer myNumOfThreads; //!< Number of threads used to build BVH
 178
 179 };
 180
 181 #include <BVH_QueueBuilder.lxx>
 182
 183 #endif // _BVH_QueueBuilder_Header