src/BVH/BVH_BinnedBuilder.hxx

   1 // Created on: 2013-12-20
   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_BinnedBuilder_Header
  17 #define _BVH_BinnedBuilder_Header
  18
  19 #include <BVH_QueueBuilder.hxx>
  20
  21 #include <algorithm>
  22
  23 #if defined (_WIN32) && defined (max)
  24   #undef max
  25 #endif
  26
  27 #include <limits>
  28
  29 //! Stores parameters of single bin (slice of AABB).
  30 template<class T, int N>
  31 struct BVH_Bin
  32 {
  33   //! Creates new node bin.
  34   BVH_Bin() : Count (0) {}
  35
  36   Standard_Integer Count; //!< Number of primitives in the bin
  37   BVH_Box<T, N>    Box;   //!< AABB of primitives in the bin
  38 };
  39
  40 //! Performs construction of BVH tree using binned SAH algorithm. Number
  41 //! of bins controls BVH quality in cost of construction time (greater -
  42 //! better). For optimal results, use 32 - 48 bins. However, reasonable
  43 //! performance is provided even for 4 - 8 bins (it is only 10-20% lower
  44 //! in comparison with optimal settings). Note that multiple threads can
  45 //! be used only with thread safe BVH primitive sets.
  46 template<class T, int N, int Bins = BVH_Constants_NbBinsOptimal>
  47 class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
  48 {
  49 public:
  50
  51   //! Type of the array of bins of BVH tree node.
  52   typedef BVH_Bin<T, N> BVH_BinVector[Bins];
  53
  54   //! Describes split plane candidate.
  55   struct BVH_SplitPlane
  56   {
  57     BVH_Bin<T, N> LftVoxel;
  58     BVH_Bin<T, N> RghVoxel;
  59   };
  60
  61   //! Type of the array of split plane candidates.
  62   typedef BVH_SplitPlane BVH_SplitPlanes[Bins + 1];
  63
  64 public:
  65
  66   //! Creates binned SAH BVH builder.
  67   BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault,
  68                      const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth,
  69                      const Standard_Boolean theDoMainSplits = Standard_False,
  70                      const Standard_Integer theNumOfThreads = 1)
  71   : BVH_QueueBuilder<T, N> (theLeafNodeSize, theMaxTreeDepth, theNumOfThreads),
  72     myUseMainAxis (theDoMainSplits)
  73   {
  74     //
  75   }
  76
  77   //! Releases resources of binned SAH BVH builder.
  78   virtual ~BVH_BinnedBuilder() {}
  79
  80 protected:
  81
  82   //! Performs splitting of the given BVH node.
  83   virtual typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>*         theSet,
  84                                                                      BVH_Tree<T, N>*        theBVH,
  85                                                                      const Standard_Integer theNode) const Standard_OVERRIDE;
  86
  87   //! Arranges node primitives into bins.
  88   virtual void getSubVolumes (BVH_Set<T, N>*         theSet,
  89                               BVH_Tree<T, N>*        theBVH,
  90                               const Standard_Integer theNode,
  91                               BVH_BinVector&         theBins,
  92                               const Standard_Integer theAxis) const;
  93
  94 private:
  95
  96   Standard_Boolean myUseMainAxis; //!< Defines whether to search for the best split or use the widest axis
  97
  98 };
  99
 100 // =======================================================================
 101 // function : getSubVolumes
 102 // purpose  :
 103 // =======================================================================
 104 template<class T, int N, int Bins>
 105 void BVH_BinnedBuilder<T, N, Bins>::getSubVolumes (BVH_Set<T, N>*         theSet,
 106                                                    BVH_Tree<T, N>*        theBVH,
 107                                                    const Standard_Integer theNode,
 108                                                    BVH_BinVector&         theBins,
 109                                                    const Standard_Integer theAxis) const
 110 {
 111   const T aMin = BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
 112   const T aMax = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
 113   const T anInverseStep = static_cast<T> (Bins) / (aMax - aMin);
 114   for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
 115   {
 116     typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
 117     Standard_Integer aBinIndex = BVH::IntFloor<T> ((theSet->Center (anIdx, theAxis) - aMin) * anInverseStep);
 118     if (aBinIndex < 0)
 119     {
 120       aBinIndex = 0;
 121     }
 122     else if (aBinIndex >= Bins)
 123     {
 124       aBinIndex = Bins - 1;
 125     }
 126
 127     theBins[aBinIndex].Count++;
 128     theBins[aBinIndex].Box.Combine (aBox);
 129   }
 130 }
 131
 132 namespace BVH
 133 {
 134   template<class T, int N>
 135   Standard_Integer SplitPrimitives (BVH_Set<T, N>*         theSet,
 136                                     const BVH_Box<T, N>&   theBox,
 137                                     const Standard_Integer theBeg,
 138                                     const Standard_Integer theEnd,
 139                                     const Standard_Integer theBin,
 140                                     const Standard_Integer theAxis,
 141                                     const Standard_Integer theBins)
 142   {
 143     const T aMin = BVH::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
 144     const T aMax = BVH::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
 145
 146     const T anInverseStep = static_cast<T> (theBins) / (aMax - aMin);
 147
 148     Standard_Integer aLftIdx (theBeg);
 149     Standard_Integer aRghIdx (theEnd);
 150
 151     do
 152     {
 153       while (BVH::IntFloor<T> ((theSet->Center (aLftIdx, theAxis) - aMin) * anInverseStep) <= theBin && aLftIdx < theEnd)
 154       {
 155         ++aLftIdx;
 156       }
 157       while (BVH::IntFloor<T> ((theSet->Center (aRghIdx, theAxis) - aMin) * anInverseStep) > theBin && aRghIdx > theBeg)
 158       {
 159         --aRghIdx;
 160       }
 161
 162       if (aLftIdx <= aRghIdx)
 163       {
 164         if (aLftIdx != aRghIdx)
 165         {
 166           theSet->Swap (aLftIdx, aRghIdx);
 167         }
 168
 169         ++aLftIdx;
 170         --aRghIdx;
 171       }
 172     } while (aLftIdx <= aRghIdx);
 173
 174     return aLftIdx;
 175   }
 176
 177   template<class T, int N>
 178   struct BVH_AxisSelector
 179   {
 180     typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
 181     static Standard_Integer MainAxis (const BVH_VecNt& theSize)
 182     {
 183       if (theSize.y() > theSize.x())
 184       {
 185         return theSize.y() > theSize.z() ? 1 : 2;
 186       }
 187       else
 188       {
 189         return theSize.z() > theSize.x() ? 2 : 0;
 190       }
 191     }
 192   };
 193
 194   template<class T>
 195   struct BVH_AxisSelector<T, 2>
 196   {
 197     typedef typename BVH::VectorType<T, 2>::Type BVH_VecNt;
 198     static Standard_Integer MainAxis (const BVH_VecNt& theSize)
 199     {
 200       return theSize.x() > theSize.y() ? 0 : 1;
 201     }
 202   };
 203 }
 204
 205 // =======================================================================
 206 // function : buildNode
 207 // purpose  :
 208 // =======================================================================
 209 template<class T, int N, int Bins>
 210 typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BVH_BinnedBuilder<T, N, Bins>::buildNode (BVH_Set<T, N>*         theSet,
 211                                                                                           BVH_Tree<T, N>*        theBVH,
 212                                                                                           const Standard_Integer theNode) const
 213 {
 214   const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
 215   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
 216   if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
 217   {
 218     return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning
 219   }
 220
 221   const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
 222                               theBVH->MaxPoint (theNode));
 223   const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();
 224
 225   // Parameters for storing best split
 226   Standard_Integer aMinSplitAxis   = -1;
 227   Standard_Integer aMinSplitIndex  =  0;
 228   Standard_Integer aMinSplitNumLft =  0;
 229   Standard_Integer aMinSplitNumRgh =  0;
 230
 231   BVH_Box<T, N> aMinSplitBoxLft;
 232   BVH_Box<T, N> aMinSplitBoxRgh;
 233
 234   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
 235   const Standard_Integer aMainAxis = BVH::BVH_AxisSelector<T, N>::MainAxis (aSize);
 236
 237   // Find best split
 238   for (Standard_Integer anAxis = myUseMainAxis ? aMainAxis : 0; anAxis <= (myUseMainAxis ? aMainAxis : Min (N - 1, 2)); ++anAxis)
 239   {
 240     if (BVH::VecComp<T, N>::Get (aSize, anAxis) <= BVH::THE_NODE_MIN_SIZE)
 241     {
 242       continue;
 243     }
 244
 245     BVH_BinVector aBinVector;
 246     getSubVolumes (theSet, theBVH, theNode, aBinVector, anAxis);
 247
 248     BVH_SplitPlanes aSplitPlanes;
 249     for (Standard_Integer aLftSplit = 1, aRghSplit = Bins - 1; aLftSplit < Bins; ++aLftSplit, --aRghSplit)
 250     {
 251       aSplitPlanes[aLftSplit].LftVoxel.Count = aSplitPlanes[aLftSplit - 1].LftVoxel.Count + aBinVector[aLftSplit - 1].Count;
 252       aSplitPlanes[aRghSplit].RghVoxel.Count = aSplitPlanes[aRghSplit + 1].RghVoxel.Count + aBinVector[aRghSplit + 0].Count;
 253
 254       aSplitPlanes[aLftSplit].LftVoxel.Box = aSplitPlanes[aLftSplit - 1].LftVoxel.Box;
 255       aSplitPlanes[aRghSplit].RghVoxel.Box = aSplitPlanes[aRghSplit + 1].RghVoxel.Box;
 256
 257       aSplitPlanes[aLftSplit].LftVoxel.Box.Combine (aBinVector[aLftSplit - 1].Box);
 258       aSplitPlanes[aRghSplit].RghVoxel.Box.Combine (aBinVector[aRghSplit + 0].Box);
 259     }
 260
 261     // Choose the best split (with minimum SAH cost)
 262     for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
 263     {
 264       // Simple SAH evaluation
 265       Standard_Real aCost =
 266         (static_cast<Standard_Real> (aSplitPlanes[aSplit].LftVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].LftVoxel.Count
 267       + (static_cast<Standard_Real> (aSplitPlanes[aSplit].RghVoxel.Box.Area()) /* / S(N) */) * aSplitPlanes[aSplit].RghVoxel.Count;
 268
 269       if (aCost <= aMinSplitCost)
 270       {
 271         aMinSplitCost   = aCost;
 272         aMinSplitAxis   = anAxis;
 273         aMinSplitIndex  = aSplit;
 274         aMinSplitBoxLft = aSplitPlanes[aSplit].LftVoxel.Box;
 275         aMinSplitBoxRgh = aSplitPlanes[aSplit].RghVoxel.Box;
 276         aMinSplitNumLft = aSplitPlanes[aSplit].LftVoxel.Count;
 277         aMinSplitNumRgh = aSplitPlanes[aSplit].RghVoxel.Count;
 278       }
 279     }
 280   }
 281
 282   theBVH->SetInner (theNode);
 283   Standard_Integer aMiddle = -1;
 284   if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0 || aMinSplitAxis == -1) // case of objects with the same center
 285   {
 286     aMinSplitBoxLft.Clear();
 287     aMinSplitBoxRgh.Clear();
 288
 289     aMiddle = std::max (aNodeBegPrimitive + 1,
 290       static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));
 291
 292     aMinSplitNumLft = aMiddle - aNodeBegPrimitive;
 293     for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
 294     {
 295       aMinSplitBoxLft.Combine (theSet->Box (anIndex));
 296     }
 297
 298     aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;
 299     for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
 300     {
 301       aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
 302     }
 303   }
 304   else
 305   {
 306     aMiddle = BVH::SplitPrimitives<T, N> (theSet,
 307                                           anAABB,
 308                                           aNodeBegPrimitive,
 309                                           aNodeEndPrimitive,
 310                                           aMinSplitIndex - 1,
 311                                           aMinSplitAxis,
 312                                           Bins);
 313   }
 314
 315   typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range;
 316   return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft,
 317                                                           aMinSplitBoxRgh,
 318                                                           Range (aNodeBegPrimitive, aMiddle - 1),
 319                                                           Range (aMiddle,     aNodeEndPrimitive));
 320 }
 321
 322 #endif // _BVH_BinnedBuilder_Header