src/BVH/BVH_BinnedBuilder.lxx

   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 // =======================================================================
  17 // function : BVH_BinnedBuilder
  18 // purpose  :
  19 // =======================================================================
  20 template<class T, int N, int Bins>
  21 BVH_BinnedBuilder<T, N, Bins>::BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize,
  22                                                   const Standard_Integer theMaxTreeDepth)
  23 : BVH_Builder<T, N> (theLeafNodeSize,
  24                      theMaxTreeDepth)
  25 {
  26   //
  27 }
  28
  29 // =======================================================================
  30 // function : ~BVH_BinnedBuilder
  31 // purpose  :
  32 // =======================================================================
  33 template<class T, int N, int Bins>
  34 BVH_BinnedBuilder<T, N, Bins>::~BVH_BinnedBuilder()
  35 {
  36   //
  37 }
  38
  39 // =======================================================================
  40 // function : GetSubVolumes
  41 // purpose  :
  42 // =======================================================================
  43 template<class T, int N, int Bins>
  44 void BVH_BinnedBuilder<T, N, Bins>::GetSubVolumes (BVH_Set<T, N>*         theSet,
  45                                                    BVH_Tree<T, N>*        theBVH,
  46                                                    const Standard_Integer theNode,
  47                                                    BVH_BinVector&         theBins,
  48                                                    const Standard_Integer theAxis)
  49 {
  50   const T aMin = BVHTools::VecComp<T, N>::Get (theBVH->MinPoint (theNode), theAxis);
  51   const T aMax = BVHTools::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), theAxis);
  52
  53   const T anInvStep = static_cast<T> (Bins) / (aMax - aMin);
  54
  55   for (Standard_Integer anIdx = theBVH->BegPrimitive (theNode); anIdx <= theBVH->EndPrimitive (theNode); ++anIdx)
  56   {
  57     typename BVH_Set<T, N>::BVH_BoxNt aBox = theSet->Box (anIdx);
  58
  59     Standard_Integer aBinIndex = static_cast<Standard_Integer> (std::floor ((theSet->Center (anIdx, theAxis) - aMin) * anInvStep));
  60     if (aBinIndex < 0)
  61     {
  62       aBinIndex = 0;
  63     }
  64     else if (aBinIndex >= Bins)
  65     {
  66       aBinIndex = Bins - 1;
  67     }
  68
  69     theBins[aBinIndex].Count++;
  70     theBins[aBinIndex].Box.Combine (aBox);
  71   }
  72 }
  73
  74 namespace BVHTools
  75 {
  76   // =======================================================================
  77   // function : SplitPrimitives
  78   // purpose  :
  79   // =======================================================================
  80   template<class T, int N>
  81   Standard_Integer SplitPrimitives (BVH_Set<T, N>*         theSet,
  82                                     const BVH_Box<T, N>&   theBox,
  83                                     const Standard_Integer theBeg,
  84                                     const Standard_Integer theEnd,
  85                                     const Standard_Integer theBin,
  86                                     const Standard_Integer theAxis,
  87                                     const Standard_Integer theBins)
  88   {
  89     const T aMin = BVHTools::VecComp<T, N>::Get (theBox.CornerMin(), theAxis);
  90     const T aMax = BVHTools::VecComp<T, N>::Get (theBox.CornerMax(), theAxis);
  91
  92     const T anInvStep = static_cast<T> (theBins) / (aMax - aMin);
  93
  94     Standard_Integer aLftIdx (theBeg);
  95     Standard_Integer aRghIdx (theEnd);
  96
  97     do
  98     {
  99       while ((Standard_Integer) std::floor ((theSet->Center (aLftIdx, theAxis) - aMin) * anInvStep) <= theBin && aLftIdx < theEnd)
 100       {
 101         ++aLftIdx;
 102       }
 103       while ((Standard_Integer) std::floor ((theSet->Center (aRghIdx, theAxis) - aMin) * anInvStep) > theBin && aRghIdx > theBeg)
 104       {
 105         --aRghIdx;
 106       }
 107
 108       if (aLftIdx <= aRghIdx)
 109       {
 110         if (aLftIdx != aRghIdx)
 111         {
 112           theSet->Swap (aLftIdx, aRghIdx);
 113         }
 114
 115         ++aLftIdx;
 116         --aRghIdx;
 117       }
 118     } while (aLftIdx <= aRghIdx);
 119
 120     return aLftIdx;
 121   }
 122 }
 123
 124 #if defined (_WIN32) && defined (max)
 125   #undef max
 126 #endif
 127
 128 #include <limits>
 129
 130 // =======================================================================
 131 // function : BuildNode
 132 // purpose  :
 133 // =======================================================================
 134 template<class T, int N, int Bins>
 135 void BVH_BinnedBuilder<T, N, Bins>::BuildNode (BVH_Set<T, N>*         theSet,
 136                                                BVH_Tree<T, N>*        theBVH,
 137                                                const Standard_Integer theNode)
 138 {
 139   const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode);
 140   const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode);
 141
 142   if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize)
 143   {
 144     return; // node does not require partitioning
 145   }
 146
 147   const BVH_Box<T, N> anAABB (theBVH->MinPoint (theNode),
 148                               theBVH->MaxPoint (theNode));
 149
 150   const typename BVH_Box<T, N>::BVH_VecNt aSize = anAABB.Size();
 151
 152   // Parameters for storing best split
 153   Standard_Integer aMinSplitAxis   = -1;
 154   Standard_Integer aMinSplitIndex  =  0;
 155   Standard_Integer aMinSplitNumLft =  0;
 156   Standard_Integer aMinSplitNumRgh =  0;
 157
 158   BVH_Box<T, N> aMinSplitBoxLft;
 159   BVH_Box<T, N> aMinSplitBoxRgh;
 160
 161   Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max();
 162
 163   // Find best split
 164   for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis)
 165   {
 166     if (BVHTools::VecComp<T, N>::Get (aSize, anAxis) <= THE_NODE_MIN_SIZE)
 167       continue;
 168
 169     BVH_BinVector aBins;
 170     GetSubVolumes (theSet, theBVH, theNode, aBins, anAxis);
 171
 172     // Choose the best split (with minimum SAH cost)
 173     for (Standard_Integer aSplit = 1; aSplit < Bins; ++aSplit)
 174     {
 175       Standard_Integer aLftCount = 0;
 176       Standard_Integer aRghCount = 0;
 177
 178       BVH_Box<T, N> aLftAABB;
 179       BVH_Box<T, N> aRghAABB;
 180
 181       for (Standard_Integer anIndex = 0; anIndex < aSplit; ++anIndex)
 182       {
 183         aLftCount += aBins[anIndex].Count;
 184         aLftAABB.Combine (aBins[anIndex].Box);
 185       }
 186
 187       for (Standard_Integer anIndex = aSplit; anIndex < Bins; ++anIndex)
 188       {
 189         aRghCount += aBins[anIndex].Count;
 190         aRghAABB.Combine (aBins[anIndex].Box);
 191       }
 192
 193       // Simple SAH evaluation
 194       Standard_Real aCost = (static_cast<Standard_Real> (aLftAABB.Area()) /* / aNodeArea */) * aLftCount
 195                           + (static_cast<Standard_Real> (aRghAABB.Area()) /* / aNodeArea */) * aRghCount;
 196
 197       if (aCost <= aMinSplitCost)
 198       {
 199         aMinSplitCost   = aCost;
 200         aMinSplitAxis   = anAxis;
 201         aMinSplitIndex  = aSplit;
 202         aMinSplitBoxLft = aLftAABB;
 203         aMinSplitBoxRgh = aRghAABB;
 204         aMinSplitNumLft = aLftCount;
 205         aMinSplitNumRgh = aRghCount;
 206       }
 207     }
 208   }
 209
 210   if (aMinSplitAxis == -1)
 211   {
 212     return;
 213   }
 214
 215   theBVH->SetInner (theNode);
 216
 217   Standard_Integer aMiddle = -1;
 218
 219   if (aMinSplitNumLft == 0 || aMinSplitNumRgh == 0) // case of objects with the same center
 220   {
 221     aMinSplitBoxLft.Clear();
 222     aMinSplitBoxRgh.Clear();
 223
 224     aMiddle = std::max (aNodeBegPrimitive + 1,
 225       static_cast<Standard_Integer> ((aNodeBegPrimitive + aNodeEndPrimitive) / 2.f));
 226
 227     aMinSplitNumLft = aMiddle - aNodeBegPrimitive;
 228
 229     for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMiddle; ++anIndex)
 230     {
 231       aMinSplitBoxLft.Combine (theSet->Box (anIndex));
 232     }
 233
 234     aMinSplitNumRgh = aNodeEndPrimitive - aMiddle + 1;
 235
 236     for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMiddle; --anIndex)
 237     {
 238       aMinSplitBoxRgh.Combine (theSet->Box (anIndex));
 239     }
 240   }
 241   else
 242   {
 243     aMiddle = BVHTools::SplitPrimitives<T, N> (theSet, anAABB,
 244       aNodeBegPrimitive, aNodeEndPrimitive, aMinSplitIndex - 1, aMinSplitAxis, Bins);
 245   }
 246
 247   static const Standard_Integer aLftNode = 1;
 248   static const Standard_Integer aRghNode = 2;
 249
 250   // Setting up tasks for child nodes
 251   for (Standard_Integer aSide = aLftNode; aSide <= aRghNode; ++aSide)
 252   {
 253     typename BVH_Box<T, N>::BVH_VecNt aMinPoint = (aSide == aLftNode)
 254                                                 ? aMinSplitBoxLft.CornerMin()
 255                                                 : aMinSplitBoxRgh.CornerMin();
 256     typename BVH_Box<T, N>::BVH_VecNt aMaxPoint = (aSide == aLftNode)
 257                                                 ? aMinSplitBoxLft.CornerMax()
 258                                                 : aMinSplitBoxRgh.CornerMax();
 259
 260     Standard_Integer aBegPrimitive = (aSide == aLftNode)
 261                                    ? aNodeBegPrimitive
 262                                    : aMiddle;
 263     Standard_Integer aEndPrimitive = (aSide == aLftNode)
 264                                    ? aMiddle - 1
 265                                    : aNodeEndPrimitive;
 266
 267     Standard_Integer aChildIndex = theBVH->AddLeafNode (aMinPoint, aMaxPoint, aBegPrimitive, aEndPrimitive);
 268
 269     theBVH->Level (aChildIndex) = theBVH->Level (theNode) + 1;
 270
 271     // Check to see if child node must be split
 272     const Standard_Integer aNbPimitives = (aSide == aLftNode)
 273                                         ? aMinSplitNumLft
 274                                         : aMinSplitNumRgh;
 275
 276     if (aSide == aLftNode)
 277       theBVH->LeftChild  (theNode) = aChildIndex;
 278     else
 279       theBVH->RightChild (theNode) = aChildIndex;
 280
 281     const Standard_Boolean isLeaf = aNbPimitives <= BVH_Builder<T, N>::myLeafNodeSize
 282                                  || theBVH->Level (aChildIndex) >= BVH_Builder<T, N>::myMaxTreeDepth;
 283
 284     if (!isLeaf)
 285       BVH_Builder<T, N>::myTasksQueue.Append (aChildIndex);
 286   }
 287 }