src/BVH/BVH_BinaryTree.hxx

   1 // Created on: 2016-06-20
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2016 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_BinaryTree_Header
  17 #define _BVH_BinaryTree_Header
  18
  19 #include <BVH_QuadTree.hxx>
  20
  21 #include <deque>
  22 #include <tuple>
  23
  24 //! Specialization of binary BVH tree.
  25 template<class T, int N>
  26 class BVH_Tree<T, N, BVH_BinaryTree> : public BVH_TreeBase<T, N>
  27 {
  28 public: //! @name custom data types
  29
  30   typedef typename BVH_TreeBase<T, N>::BVH_VecNt BVH_VecNt;
  31
  32 public: //! @name methods for accessing individual nodes
  33
  34   //! Creates new empty BVH tree.
  35   BVH_Tree() : BVH_TreeBase<T, N>() { }
  36
  37   //! Sets node type to 'outer'.
  38   void SetOuter (const int theNodeIndex) { BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 1; }
  39
  40   //! Sets node type to 'inner'.
  41   void SetInner (const int theNodeIndex) { BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex).x() = 0; }
  42
  43   //! Returns index of the K-th child of the given inner node.
  44   //! \tparam K the index of node child (0 or 1)
  45   template<int K>
  46   int Child (const int theNodeIndex) const { return BVH::Array<int, 4>::Value (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; }
  47
  48   //! Returns index of the K-th child of the given inner node.
  49   //! \tparam K the index of node child (0 or 1)
  50   template<int K>
  51   int& ChangeChild (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; }
  52
  53   //! Returns index of the K-th child of the given inner node.
  54   //! \tparam K the index of node child (0 or 1)
  55   template<int K>
  56   int& Child (const int theNodeIndex) { return BVH::Array<int, 4>::ChangeValue (this->myNodeInfoBuffer, theNodeIndex)[K + 1]; }
  57
  58 public: //! @name methods for adding/removing tree nodes
  59
  60   //! Removes all nodes from the tree.
  61   void Clear()
  62   {
  63     this->myDepth = 0;
  64     BVH::Array<T, N>::Clear  (this->myMinPointBuffer);
  65     BVH::Array<T, N>::Clear  (this->myMaxPointBuffer);
  66     BVH::Array<int, 4>::Clear(this->myNodeInfoBuffer);
  67   }
  68
  69   //! Reserves internal BVH storage, so that it
  70   //! can contain the given number of BVH nodes.
  71   void Reserve (const int theNbNodes)
  72   {
  73     BVH::Array<T,   N>::Reserve (this->myMinPointBuffer, theNbNodes);
  74     BVH::Array<T,   N>::Reserve (this->myMaxPointBuffer, theNbNodes);
  75     BVH::Array<int, 4>::Reserve (this->myNodeInfoBuffer, theNbNodes);
  76   }
  77
  78   //! Adds new leaf node to the BVH.
  79   int AddLeafNode (const BVH_VecNt& theMinPoint,
  80                    const BVH_VecNt& theMaxPoint,
  81                    const int        theBegElem,
  82                    const int        theEndElem)
  83   {
  84     BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint);
  85     BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint);
  86     BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
  87     return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
  88   }
  89
  90   //! Adds new inner node to the BVH.
  91   int AddInnerNode (const BVH_VecNt& theMinPoint,
  92                     const BVH_VecNt& theMaxPoint,
  93                     const int        theLftChild,
  94                     const int        theRghChild)
  95   {
  96     BVH::Array<T, N>::Append (this->myMinPointBuffer, theMinPoint);
  97     BVH::Array<T, N>::Append (this->myMaxPointBuffer, theMaxPoint);
  98     BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
  99     return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
 100   }
 101
 102   //! Adds new leaf node to the BVH.
 103   int AddLeafNode (const BVH_Box<T, N>& theAABB,
 104                    const int            theBegElem,
 105                    const int            theEndElem)
 106   {
 107     return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem);
 108   }
 109
 110   //! Adds new inner node to the BVH.
 111   int AddInnerNode (const BVH_Box<T, N>& theAABB,
 112                     const int            theLftChild,
 113                     const int            theRghChild)
 114   {
 115     return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild);
 116   }
 117
 118   //! Adds new leaf node to the BVH with UNINITIALIZED bounds.
 119   int AddLeafNode (const int theBegElem,
 120                    const int theEndElem)
 121   {
 122     BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
 123     return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
 124   }
 125
 126   //! Adds new inner node to the BVH with UNINITIALIZED bounds.
 127   int AddInnerNode (const int theLftChild,
 128                     const int theRghChild)
 129   {
 130     BVH::Array<int, 4>::Append (this->myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
 131     return BVH::Array<int, 4>::Size (this->myNodeInfoBuffer) - 1;
 132   }
 133
 134 public: //! @name methods specific to binary BVH
 135
 136   //! Returns value of SAH (surface area heuristic).
 137   //! Allows to compare the quality of BVH trees constructed for
 138   //! the same sets of geometric objects with different methods.
 139   T EstimateSAH() const;
 140
 141   //! Collapses the tree into QBVH an returns it. As a result, each
 142   //! 2-nd level of current tree is kept and the rest are discarded.
 143   BVH_Tree<T, N, BVH_QuadTree>* CollapseToQuadTree() const;
 144
 145 };
 146
 147 namespace BVH
 148 {
 149   //! Internal function for recursive calculation of
 150   //! surface area heuristic (SAH) of the given tree.
 151   template<class T, int N>
 152   void EstimateSAH (const BVH_Tree<T, N, BVH_BinaryTree>* theTree, const int theNode, T theProb, T& theSAH)
 153   {
 154     BVH_Box<T, N> aBox (theTree->MinPoint (theNode),
 155                         theTree->MaxPoint (theNode));
 156
 157     if (theTree->IsOuter (theNode))
 158     {
 159       theSAH += theProb * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1);
 160     }
 161     else
 162     {
 163       theSAH += theProb * static_cast<T> (2.0);
 164
 165       BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->template Child<0> (theNode)),
 166                              theTree->MaxPoint (theTree->template Child<0> (theNode)));
 167
 168       if (theProb > 0.0)
 169       {
 170         EstimateSAH (theTree, theTree->template Child<0> (theNode),
 171                      theProb * aLftBox.Area() / aBox.Area(), theSAH);
 172       }
 173
 174       BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->template Child<1> (theNode)),
 175                              theTree->MaxPoint (theTree->template Child<1> (theNode)));
 176
 177       if (theProb > 0.0)
 178       {
 179         EstimateSAH (theTree, theTree->template Child<1> (theNode),
 180                      theProb * aRghBox.Area() / aBox.Area(), theSAH);
 181       }
 182     }
 183   }
 184 }
 185
 186 // =======================================================================
 187 // function : EstimateSAH
 188 // purpose  :
 189 // =======================================================================
 190 template<class T, int N>
 191 T BVH_Tree<T, N, BVH_BinaryTree>::EstimateSAH() const
 192 {
 193   T aSAH = static_cast<T> (0.0);
 194   BVH::EstimateSAH<T, N> (this, 0, static_cast<T> (1.0), aSAH);
 195   return aSAH;
 196 }
 197
 198 // =======================================================================
 199 // function : CollapseToQuadTree
 200 // purpose  :
 201 // =======================================================================
 202 template<class T, int N>
 203 BVH_Tree<T, N, BVH_QuadTree>* BVH_Tree<T, N, BVH_BinaryTree>::CollapseToQuadTree() const
 204 {
 205   BVH_Tree<T, N, BVH_QuadTree>* aQBVH = new BVH_Tree<T, N, BVH_QuadTree>;
 206
 207   if (this->Length() == 0)
 208   {
 209     return aQBVH;
 210   }
 211
 212   std::deque<std::pair<int, int> > aQueue (1, std::make_pair (0, 0));
 213
 214   for (int aNbNodes = 1; !aQueue.empty();)
 215   {
 216     const std::pair<int, int> aNode = aQueue.front();
 217
 218     BVH::Array<T, N>::Append (aQBVH->myMinPointBuffer, BVH::Array<T, N>::Value (this->myMinPointBuffer, opencascade::std::get<0> (aNode)));
 219     BVH::Array<T, N>::Append (aQBVH->myMaxPointBuffer, BVH::Array<T, N>::Value (this->myMaxPointBuffer, opencascade::std::get<0> (aNode)));
 220
 221     BVH_Vec4i aNodeInfo;
 222     if (this->IsOuter (opencascade::std::get<0> (aNode))) // is leaf node
 223     {
 224       aNodeInfo = BVH_Vec4i (1 /* leaf flag */,
 225         this->BegPrimitive (opencascade::std::get<0> (aNode)), this->EndPrimitive (opencascade::std::get<0> (aNode)), opencascade::std::get<1> (aNode) /* level */);
 226     }
 227     else
 228     {
 229       NCollection_Vector<int> aGrandChildNodes;
 230
 231       const int aLftChild = Child<0> (opencascade::std::get<0> (aNode));
 232       const int aRghChild = Child<1> (opencascade::std::get<0> (aNode));
 233       if (this->IsOuter (aLftChild)) // is leaf node
 234       {
 235         aGrandChildNodes.Append (aLftChild);
 236       }
 237       else
 238       {
 239         aGrandChildNodes.Append (Child<0> (aLftChild));
 240         aGrandChildNodes.Append (Child<1> (aLftChild));
 241       }
 242
 243       if (this->IsOuter (aRghChild)) // is leaf node
 244       {
 245         aGrandChildNodes.Append (aRghChild);
 246       }
 247       else
 248       {
 249         aGrandChildNodes.Append (Child<0> (aRghChild));
 250         aGrandChildNodes.Append (Child<1> (aRghChild));
 251       }
 252
 253       for (int aNodeIdx = 0; aNodeIdx < aGrandChildNodes.Size(); ++aNodeIdx)
 254       {
 255         aQueue.push_back (std::make_pair (aGrandChildNodes (aNodeIdx), opencascade::std::get<1> (aNode) + 1));
 256       }
 257
 258       aNodeInfo = BVH_Vec4i (0 /* inner flag */,
 259         aNbNodes, aGrandChildNodes.Size() - 1, opencascade::std::get<1> (aNode) /* level */);
 260
 261       aQBVH->myDepth = Max (aQBVH->myDepth, opencascade::std::get<1> (aNode) + 1);
 262
 263       aNbNodes += aGrandChildNodes.Size();
 264     }
 265
 266     BVH::Array<int, 4>::Append (aQBVH->myNodeInfoBuffer, aNodeInfo);
 267     aQueue.pop_front(); // node processing completed
 268   }
 269
 270   return aQBVH;
 271 }
 272
 273 #endif // _BVH_BinaryTree_Header