src/BVH/BVH_LinearBuilder.lxx

   1 // Created on: 2014-09-11
   2 // Created by: Danila ULYANOV
   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 #include <Standard_Assert.hxx>
  17
  18 // =======================================================================
  19 // function : BVH_LinearBuilder
  20 // purpose  :
  21 // =======================================================================
  22 template<class T, int N>
  23 BVH_LinearBuilder<T, N>::BVH_LinearBuilder (const Standard_Integer theLeafNodeSize,
  24                                             const Standard_Integer theMaxTreeDepth)
  25 : BVH_Builder<T, N> (theLeafNodeSize,
  26                      theMaxTreeDepth)
  27 {
  28   //
  29 }
  30
  31 // =======================================================================
  32 // function : ~BVH_LinearBuilder
  33 // purpose  :
  34 // =======================================================================
  35 template<class T, int N>
  36 BVH_LinearBuilder<T, N>::~BVH_LinearBuilder()
  37 {
  38   //
  39 }
  40
  41 // =======================================================================
  42 // function : LowerBound
  43 // purpose  : Returns index of first element greater than the given one
  44 // =======================================================================
  45 template<class T, int N>
  46 Standard_Integer BVH_LinearBuilder<T, N>::LowerBound (Standard_Integer theStart,
  47                                                       Standard_Integer theFinal,
  48                                                       Standard_Integer theDigit)
  49 {
  50   Standard_Integer aNbPrims = theFinal - theStart;
  51
  52   while (aNbPrims > 0)
  53   {
  54     const Standard_Integer aStep = aNbPrims / 2;
  55
  56     if (myRadixSorter->EncodedLinks().Value (theStart + aStep).first & (1 << theDigit))
  57     {
  58       aNbPrims = aStep;
  59     }
  60     else
  61     {
  62       theStart += aStep + 1;
  63       aNbPrims -= aStep + 1;
  64     }
  65   }
  66
  67   return theStart;
  68 }
  69
  70 // =======================================================================
  71 // function : EmitHierachy
  72 // purpose  : Emits hierarchy from sorted Morton codes
  73 // =======================================================================
  74 template<class T, int N>
  75 Standard_Integer BVH_LinearBuilder<T, N>::EmitHierachy (BVH_Tree<T, N>*        theBVH,
  76                                                         const Standard_Integer theBit,
  77                                                         const Standard_Integer theShift,
  78                                                         const Standard_Integer theStart,
  79                                                         const Standard_Integer theFinal)
  80 {
  81   if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize)
  82   {
  83     const Standard_Integer aPosition = theBit < 0 ?
  84       (theStart + theFinal) / 2 : LowerBound (theStart, theFinal, theBit);
  85
  86     if (aPosition == theStart || aPosition == theFinal)
  87     {
  88       return EmitHierachy (theBVH, theBit - 1, theShift, theStart, theFinal);
  89     }
  90
  91     // Build inner node
  92     const Standard_Integer aNode = theBVH->AddInnerNode (0, 0);
  93
  94     const Standard_Integer aRghNode = theShift + aPosition - theStart;
  95
  96     const Standard_Integer aLftChild = EmitHierachy (theBVH, theBit - 1, theShift, theStart, aPosition);
  97     const Standard_Integer aRghChild = EmitHierachy (theBVH, theBit - 1, aRghNode, aPosition, theFinal);
  98
  99     theBVH->NodeInfoBuffer()[aNode].y() = aLftChild;
 100     theBVH->NodeInfoBuffer()[aNode].z() = aRghChild;
 101
 102     return aNode;
 103   }
 104   else
 105   {
 106     // Build leaf node
 107     return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1);
 108   }
 109 }
 110
 111 namespace BVH
 112 {
 113   //! Calculates bounding boxes (AABBs) for the given BVH tree.
 114   template<class T, int N>
 115   Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0)
 116   {
 117     const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode];
 118
 119     if (aData.x() == 0)
 120     {
 121       const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y();
 122       const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z();
 123
 124       const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild);
 125       const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild);
 126
 127       typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild];
 128       typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild];
 129       typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild];
 130       typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild];
 131
 132       BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 133       BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 134
 135       theTree->MinPointBuffer()[theNode] = aLftMinPoint;
 136       theTree->MaxPointBuffer()[theNode] = aLftMaxPoint;
 137
 138       return Max (aLftDepth, aRghDepth) + 1;
 139     }
 140     else
 141     {
 142       typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode];
 143       typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode];
 144
 145       for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx)
 146       {
 147         const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx);
 148
 149         if (aPrimIdx == aData.y())
 150         {
 151           aMinPoint = aBox.CornerMin();
 152           aMaxPoint = aBox.CornerMax();
 153         }
 154         else
 155         {
 156           BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin());
 157           BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax());
 158         }
 159       }
 160     }
 161
 162     return 0;
 163   }
 164
 165 #ifdef HAVE_TBB
 166
 167   //! TBB task for parallel bounds updating.
 168   template<class T, int N>
 169   class UpdateBoundTask: public tbb::task
 170   {
 171     //! Set of geometric objects.
 172     BVH_Set<T, N>* mySet;
 173
 174     //! BVH tree built over the set.
 175     BVH_Tree<T, N>* myBVH;
 176
 177     //! BVH node to update bounding box.
 178     Standard_Integer myNode;
 179
 180     //! Level of the processed BVH node.
 181     Standard_Integer myLevel;
 182
 183     //! Height of the processed BVH node.
 184     Standard_Integer* myHeight;
 185
 186   public:
 187
 188     //! Creates new TBB parallel bound update task.
 189     UpdateBoundTask (BVH_Set<T, N>*    theSet,
 190                      BVH_Tree<T, N>*   theBVH,
 191                      Standard_Integer  theNode,
 192                      Standard_Integer  theLevel,
 193                      Standard_Integer* theHeight)
 194     : mySet    (theSet),
 195       myBVH    (theBVH),
 196       myNode   (theNode),
 197       myLevel  (theLevel),
 198       myHeight (theHeight)
 199     {
 200       //
 201     }
 202
 203     //! Executes the task.
 204     tbb::task* execute()
 205     {
 206       if (myBVH->IsOuter (myNode) || myLevel > 2)
 207       {
 208         *myHeight = BVH::UpdateBounds (mySet, myBVH, myNode);
 209       }
 210       else
 211       {
 212         Standard_Integer aLftHeight = 0;
 213         Standard_Integer aRghHeight = 0;
 214
 215         tbb::task_list aList;
 216
 217         const Standard_Integer aLftChild = myBVH->NodeInfoBuffer()[myNode].y();
 218         const Standard_Integer aRghChild = myBVH->NodeInfoBuffer()[myNode].z();
 219
 220         Standard_Integer aCount = 1;
 221
 222         if (!myBVH->IsOuter (aLftChild))
 223         {
 224           ++aCount;
 225           aList.push_back (*new ( allocate_child() )
 226             UpdateBoundTask (mySet, myBVH, aLftChild, myLevel + 1, &aLftHeight));
 227         }
 228         else
 229         {
 230           aLftHeight = BVH::UpdateBounds (mySet, myBVH, aLftChild);
 231         }
 232
 233         if (!myBVH->IsOuter (aRghChild))
 234         {
 235           ++aCount;
 236           aList.push_back (*new( allocate_child() )
 237             UpdateBoundTask (mySet, myBVH, aRghChild, myLevel + 1, &aRghHeight));
 238         }
 239         else
 240         {
 241           aRghHeight = BVH::UpdateBounds (mySet, myBVH, aRghChild);
 242         }
 243
 244         if (aCount > 1)
 245         {
 246           set_ref_count (aCount);
 247           spawn_and_wait_for_all (aList);
 248         }
 249
 250         typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = myBVH->MinPointBuffer()[aLftChild];
 251         typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = myBVH->MaxPointBuffer()[aLftChild];
 252         typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = myBVH->MinPointBuffer()[aRghChild];
 253         typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = myBVH->MaxPointBuffer()[aRghChild];
 254
 255         BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint);
 256         BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint);
 257
 258         myBVH->MinPointBuffer()[myNode] = aLftMinPoint;
 259         myBVH->MaxPointBuffer()[myNode] = aLftMaxPoint;
 260
 261         *myHeight = Max (aLftHeight, aRghHeight) + 1;
 262       }
 263
 264       return NULL;
 265     }
 266   };
 267
 268 #endif
 269 }
 270
 271 // =======================================================================
 272 // function : Build
 273 // purpose  :
 274 // =======================================================================
 275 template<class T, int N>
 276 void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
 277                                      BVH_Tree<T, N>*      theBVH,
 278                                      const BVH_Box<T, N>& theBox)
 279 {
 280   Standard_STATIC_ASSERT (N == 3 || N == 4);
 281   const Standard_Integer aSetSize = theSet->Size();
 282   if (theBVH == NULL || aSetSize == 0)
 283   {
 284     return;
 285   }
 286
 287   theBVH->Clear();
 288
 289   // Step 0 -- Initialize parameter of virtual grid
 290   myRadixSorter = new BVH_RadixSorter<T, N> (theBox);
 291
 292   // Step 1 - Perform radix sorting of primitive set
 293   myRadixSorter->Perform (theSet);
 294
 295   // Step 2 -- Emitting BVH hierarchy from sorted Morton codes
 296   EmitHierachy (theBVH, 29, 0, 0, theSet->Size());
 297
 298   // Step 3 -- Compute bounding boxes of BVH nodes
 299   theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 300   theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size());
 301
 302   Standard_Integer aHeight = 0;
 303
 304 #ifdef HAVE_TBB
 305
 306   // Note: Although TBB tasks are allocated using placement
 307   // new, we do not need to delete them explicitly
 308   BVH::UpdateBoundTask<T, N>& aRootTask = *new ( tbb::task::allocate_root() )
 309     BVH::UpdateBoundTask<T, N> (theSet, theBVH, 0, 0, &aHeight);
 310
 311   tbb::task::spawn_root_and_wait (aRootTask);
 312
 313 #else
 314
 315   aHeight = BVH::UpdateBounds (theSet, theBVH, 0);
 316
 317 #endif
 318
 319   BVH_Builder<T, N>::UpdateDepth (theBVH, aHeight);
 320 }