src/BVH/BVH_Tree.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 : Clear
  18 // purpose  :
  19 // =======================================================================
  20 template<class T, int N>
  21 void BVH_Tree<T, N>::Clear()
  22 {
  23   myDepth = 0;
  24
  25   BVH::Array<T, N>::Clear (myMinPointBuffer);
  26   BVH::Array<T, N>::Clear (myMaxPointBuffer);
  27
  28   BVH::Array<Standard_Integer, 4>::Clear (myNodeInfoBuffer);
  29 }
  30
  31 // =======================================================================
  32 // function : AddLeafNode
  33 // purpose  :
  34 // =======================================================================
  35 template<class T, int N>
  36 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const Standard_Integer theBegElem,
  37                                               const Standard_Integer theEndElem)
  38 {
  39   BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
  40
  41   return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
  42 }
  43
  44 // =======================================================================
  45 // function : AddInnerNode
  46 // purpose  :
  47 // =======================================================================
  48 template<class T, int N>
  49 Standard_Integer BVH_Tree<T, N>::AddInnerNode (const Standard_Integer theLftChild,
  50                                                const Standard_Integer theRghChild)
  51 {
  52   BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
  53
  54   return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer)  - 1);
  55 }
  56
  57 // =======================================================================
  58 // function : AddLeafNode
  59 // purpose  :
  60 // =======================================================================
  61 template<class T, int N>
  62 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_VecNt&       theMinPoint,
  63                                               const BVH_VecNt&       theMaxPoint,
  64                                               const Standard_Integer theBegElem,
  65                                               const Standard_Integer theEndElem)
  66 {
  67   BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint);
  68   BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint);
  69
  70   BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
  71
  72   return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
  73 }
  74
  75 // =======================================================================
  76 // function : AddInnerNode
  77 // purpose  :
  78 // =======================================================================
  79 template<class T, int N>
  80 Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_VecNt&       theMinPoint,
  81                                                const BVH_VecNt&       theMaxPoint,
  82                                                const Standard_Integer theLftChild,
  83                                                const Standard_Integer theRghChild)
  84 {
  85   BVH::Array<T, N>::Append (myMinPointBuffer, theMinPoint);
  86   BVH::Array<T, N>::Append (myMaxPointBuffer, theMaxPoint);
  87
  88   BVH::Array<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
  89
  90   return static_cast<Standard_Integer> (BVH::Array<Standard_Integer, 4>::Size (myNodeInfoBuffer)  - 1);
  91 }
  92
  93 // =======================================================================
  94 // function : AddLeafNode
  95 // purpose  :
  96 // =======================================================================
  97 template<class T, int N>
  98 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_Box<T, N>&   theAABB,
  99                                               const Standard_Integer theBegElem,
 100                                               const Standard_Integer theEndElem)
 101 {
 102   return AddLeafNode (theAABB.CornerMin(),
 103                       theAABB.CornerMax(),
 104                       theBegElem,
 105                       theEndElem);
 106 }
 107
 108 // =======================================================================
 109 // function : AddInnerNode
 110 // purpose  :
 111 // =======================================================================
 112 template<class T, int N>
 113 Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_Box<T, N>&   theAABB,
 114                                                const Standard_Integer theLftChild,
 115                                                const Standard_Integer theRghChild)
 116 {
 117   return AddInnerNode (theAABB.CornerMin(),
 118                        theAABB.CornerMax(),
 119                        theLftChild,
 120                        theRghChild);
 121 }
 122
 123 namespace BVH
 124 {
 125   //! Internal function for recursive calculation of
 126   //! surface area heuristic (SAH) of the given tree.
 127   template<class T, int N>
 128   void EstimateSAH (const BVH_Tree<T, N>*  theTree,
 129                     const Standard_Integer theNode,
 130                     T                      theProb,
 131                     T&                     theSAH)
 132   {
 133     BVH_Box<T, N> aBox (theTree->MinPoint (theNode),
 134                         theTree->MaxPoint (theNode));
 135
 136     if (theTree->IsOuter (theNode))
 137     {
 138       theSAH += theProb * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1);
 139     }
 140     else
 141     {
 142       theSAH += theProb * static_cast<T> (2.0);
 143
 144       BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->LeftChild (theNode)),
 145                              theTree->MaxPoint (theTree->LeftChild (theNode)));
 146
 147       if (theProb > 0.0)
 148       {
 149         EstimateSAH (theTree, theTree->LeftChild (theNode),
 150                      theProb * aLftBox.Area() / aBox.Area(), theSAH);
 151       }
 152
 153       BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)),
 154                              theTree->MaxPoint (theTree->RightChild (theNode)));
 155
 156       if (theProb > 0.0)
 157       {
 158         EstimateSAH (theTree, theTree->RightChild (theNode),
 159                      theProb * aRghBox.Area() / aBox.Area(), theSAH);
 160       }
 161     }
 162   }
 163 }
 164
 165 // =======================================================================
 166 // function : EstimateSAH
 167 // purpose  :
 168 // =======================================================================
 169 template<class T, int N>
 170 T BVH_Tree<T, N>::EstimateSAH() const
 171 {
 172   T aSAH = static_cast<T> (0.0);
 173   BVH::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH);
 174   return aSAH;
 175 }
 176
 177 // =======================================================================
 178 // function : Reserve
 179 // purpose  :
 180 // =======================================================================
 181 template<class T, int N>
 182 void BVH_Tree<T, N>::Reserve (const Standard_Integer theNbNodes)
 183 {
 184   BVH::Array<T,                N>::Reserve (myMinPointBuffer, theNbNodes);
 185   BVH::Array<T,                N>::Reserve (myMaxPointBuffer, theNbNodes);
 186   BVH::Array<Standard_Integer, 4>::Reserve (myNodeInfoBuffer, theNbNodes);
 187 }