src/BVH/BVH_Tree.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_TreeBase_Header
  17 #define _BVH_TreeBase_Header
  18
  19 #include <BVH_Box.hxx>
  20
  21 template<class T, int N> class BVH_Builder;
  22
  23 //! A non-template class for using as base for BVH_TreeBase
  24 //! (just to have a named base class).
  25 class BVH_TreeBaseTransient : public Standard_Transient
  26 {
  27   DEFINE_STANDARD_RTTIEXT(BVH_TreeBaseTransient, Standard_Transient)
  28 protected:
  29   BVH_TreeBaseTransient() {}
  30 };
  31
  32 //! Stores parameters of bounding volume hierarchy (BVH).
  33 //! Bounding volume hierarchy (BVH) organizes geometric objects in
  34 //! the tree based on spatial relationships. Each node in the tree
  35 //! contains an axis-aligned bounding box of all the objects below
  36 //! it. Bounding volume hierarchies are used in many algorithms to
  37 //! support efficient operations on the sets of geometric objects,
  38 //! such as collision detection, ray-tracing, searching of nearest
  39 //! objects, and view frustum culling.
  40 template<class T, int N>
  41 class BVH_TreeBase : public BVH_TreeBaseTransient
  42 {
  43   friend class BVH_Builder<T, N>;
  44
  45 public: //! @name custom data types
  46
  47   typedef typename BVH_Box<T, N>::BVH_VecNt BVH_VecNt;
  48
  49 public: //! @name general methods
  50
  51   //! Creates new empty BVH tree.
  52   BVH_TreeBase() : myDepth (0) { }
  53
  54   //! Releases resources of BVH tree.
  55   virtual ~BVH_TreeBase() {}
  56
  57   //! Returns depth (height) of BVH tree.
  58   int Depth() const
  59   {
  60     return myDepth;
  61   }
  62
  63   //! Returns total number of BVH tree nodes.
  64   int Length() const
  65   {
  66     return BVH::Array<int, 4>::Size (myNodeInfoBuffer);
  67   }
  68
  69 public: //! @name methods for accessing individual nodes
  70
  71   //! Returns minimum point of the given node.
  72   BVH_VecNt& MinPoint (const int theNodeIndex)
  73   {
  74     return BVH::Array<T, N>::ChangeValue (myMinPointBuffer, theNodeIndex);
  75   }
  76
  77   //! Returns maximum point of the given node.
  78   BVH_VecNt& MaxPoint (const int theNodeIndex)
  79   {
  80     return BVH::Array<T, N>::ChangeValue (myMaxPointBuffer, theNodeIndex);
  81   }
  82
  83   //! Returns minimum point of the given node.
  84   const BVH_VecNt& MinPoint (const int theNodeIndex) const
  85   {
  86     return BVH::Array<T, N>::Value (myMinPointBuffer, theNodeIndex);
  87   }
  88
  89   //! Returns maximum point of the given node.
  90   const BVH_VecNt& MaxPoint (const int theNodeIndex) const
  91   {
  92     return BVH::Array<T, N>::Value (myMaxPointBuffer, theNodeIndex);
  93   }
  94
  95   //! Returns index of first primitive of the given leaf node.
  96   int& BegPrimitive (const int theNodeIndex)
  97   {
  98     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).y();
  99   }
 100
 101   //! Returns index of last primitive of the given leaf node.
 102   int& EndPrimitive (const int theNodeIndex)
 103   {
 104     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).z();
 105   }
 106
 107   //! Returns index of first primitive of the given leaf node.
 108   int BegPrimitive (const int theNodeIndex) const
 109   {
 110     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).y();
 111   }
 112
 113   //! Returns index of last primitive of the given leaf node.
 114   int EndPrimitive (const int theNodeIndex) const
 115   {
 116     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).z();
 117   }
 118
 119   //! Returns number of primitives in the given leaf node.
 120   int NbPrimitives (const int theNodeIndex) const
 121   {
 122     return EndPrimitive (theNodeIndex) - BegPrimitive (theNodeIndex) + 1;
 123   }
 124
 125   //! Returns level (depth) of the given node.
 126   int& Level (const int theNodeIndex)
 127   {
 128     return BVH::Array<int, 4>::ChangeValue (myNodeInfoBuffer, theNodeIndex).w();
 129   }
 130
 131   //! Returns level (depth) of the given node.
 132   int Level (const int theNodeIndex) const
 133   {
 134     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).w();
 135   }
 136
 137   //! Checks whether the given node is outer.
 138   bool IsOuter (const int theNodeIndex) const
 139   {
 140     return BVH::Array<int, 4>::Value (myNodeInfoBuffer, theNodeIndex).x() != 0;
 141   }
 142
 143 public: //! @name methods for accessing serialized tree data
 144
 145   //! Returns array of node data records.
 146   BVH_Array4i& NodeInfoBuffer()
 147   {
 148     return myNodeInfoBuffer;
 149   }
 150
 151   //! Returns array of node data records.
 152   const BVH_Array4i& NodeInfoBuffer() const
 153   {
 154     return myNodeInfoBuffer;
 155   }
 156
 157   //! Returns array of node minimum points.
 158   typename BVH::ArrayType<T, N>::Type& MinPointBuffer()
 159   {
 160     return myMinPointBuffer;
 161   }
 162
 163   //! Returns array of node maximum points.
 164   typename BVH::ArrayType<T, N>::Type& MaxPointBuffer()
 165   {
 166     return myMaxPointBuffer;
 167   }
 168
 169   //! Returns array of node minimum points.
 170   const typename BVH::ArrayType<T, N>::Type& MinPointBuffer() const
 171   {
 172     return myMinPointBuffer;
 173   }
 174
 175   //! Returns array of node maximum points.
 176   const typename BVH::ArrayType<T, N>::Type& MaxPointBuffer() const
 177   {
 178     return myMaxPointBuffer;
 179   }
 180
 181 public: //! @name protected fields
 182
 183   //! Array of node data records.
 184   BVH_Array4i myNodeInfoBuffer;
 185
 186   //! Array of node minimum points.
 187   typename BVH::ArrayType<T, N>::Type myMinPointBuffer;
 188
 189   //! Array of node maximum points.
 190   typename BVH::ArrayType<T, N>::Type myMaxPointBuffer;
 191
 192   //! Current depth of BVH tree (set by builder).
 193   int myDepth;
 194
 195 };
 196
 197 //! Type corresponding to quad BVH.
 198 struct BVH_QuadTree { };
 199
 200 //! Type corresponding to binary BVH.
 201 struct BVH_BinaryTree { };
 202
 203 //! BVH tree with given arity (2 or 4).
 204 template<class T, int N, class Arity = BVH_BinaryTree>
 205 class BVH_Tree
 206 {
 207   // Invalid type
 208 };
 209
 210 #endif // _BVH_TreeBase_Header