Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
lvr2::BVHTree< BaseVecT > Class Template Reference

Implementation of an Bounding Volume Hierarchy Tree used for ray casting. More...

#include <BVH.hpp>

Classes

struct  AABB
 
struct  BVHInner
 
struct  BVHLeaf
 
struct  BVHNode
 
struct  Triangle
 

Public Member Functions

 BVHTree (const floatArr vertices, size_t n_vertices, const indexArray faces, size_t n_faces)
 
 BVHTree (const MeshBufferPtr mesh)
 
 BVHTree (const vector< float > &vertices, const vector< uint32_t > &faces)
 Constructs the tree itself and it's cache friendly representation. More...
 
const vector< uint32_t > & getIndexesOrTrilists () const
 
const vector< float > & getLimits () const
 
const vector< float > & getTrianglesIntersectionData () const
 Returns precalculated values for the triangle intersection tests. More...
 
const vector< uint32_t > & getTriIndexList () const
 

Private Types

using BVHInnerPtr = unique_ptr< BVHInner >
 
using BVHLeafPtr = unique_ptr< BVHLeaf >
 
using BVHNodePtr = unique_ptr< BVHNode >
 

Private Member Functions

BVHNodePtr buildTree (const floatArr vertices, size_t n_vertices, const indexArray faces, size_t n_faces)
 Builds the tree without it's cache friendly representation. Utilizes the buildTreeRecursive method. More...
 
BVHNodePtr buildTree (const vector< float > &vertices, const vector< uint32_t > &faces)
 Builds the tree without it's cache friendly representation. Utilizes the buildTreeRecursive method. More...
 
BVHNodePtr buildTreeRecursive (vector< AABB > &work, uint32_t depth=0)
 Recursive method to build the tree. More...
 
void convertTrianglesIntersectionData ()
 Converts the precalculated triangle intersection data to a SIMD friendly structure. More...
 
void createCFTree ()
 Creates the cache friendly representation of the tree. Needs the tree itself! More...
 
void createCFTreeRecursive (BVHNodePtr currentNode, uint32_t &idxBoxes)
 Recursive method for cache friendly tree creation. More...
 

Private Attributes

vector< uint32_t > m_indexesOrTrilists
 
vector< float > m_limits
 
BVHNodePtr m_root
 
vector< Trianglem_triangles
 
vector< float > m_trianglesIntersectionData
 
vector< uint32_t > m_triIndexList
 

Detailed Description

template<typename BaseVecT>
class lvr2::BVHTree< BaseVecT >

Implementation of an Bounding Volume Hierarchy Tree used for ray casting.

This class generates a BVHTree from the given triangle mesh represented by vertices and faces. AABB are used as bounding volumes. The Tree Contains inner nodes and leaf nodes. The leaf nodes are grouped into inner nodes using the surface area heuristic. The tree is represented in two ways: the normal tree structure and the cache friendly index representation.

Template Parameters
BaseVecT

Definition at line 61 of file BVH.hpp.

Member Typedef Documentation

◆ BVHInnerPtr

template<typename BaseVecT >
using lvr2::BVHTree< BaseVecT >::BVHInnerPtr = unique_ptr<BVHInner>
private

Definition at line 173 of file BVH.hpp.

◆ BVHLeafPtr

template<typename BaseVecT >
using lvr2::BVHTree< BaseVecT >::BVHLeafPtr = unique_ptr<BVHLeaf>
private

Definition at line 182 of file BVH.hpp.

◆ BVHNodePtr

template<typename BaseVecT >
using lvr2::BVHTree< BaseVecT >::BVHNodePtr = unique_ptr<BVHNode>
private

Definition at line 161 of file BVH.hpp.

Constructor & Destructor Documentation

◆ BVHTree() [1/3]

template<typename BaseVecT >
lvr2::BVHTree< BaseVecT >::BVHTree ( const vector< float > &  vertices,
const vector< uint32_t > &  faces 
)

Constructs the tree itself and it's cache friendly representation.

Parameters
verticesVertices of mesh to create tree for
facesFaces of mesh to create tree for

◆ BVHTree() [2/3]

template<typename BaseVecT >
lvr2::BVHTree< BaseVecT >::BVHTree ( const floatArr  vertices,
size_t  n_vertices,
const indexArray  faces,
size_t  n_faces 
)

◆ BVHTree() [3/3]

template<typename BaseVecT >
lvr2::BVHTree< BaseVecT >::BVHTree ( const MeshBufferPtr  mesh)

Member Function Documentation

◆ buildTree() [1/2]

template<typename BaseVecT >
BVHNodePtr lvr2::BVHTree< BaseVecT >::buildTree ( const floatArr  vertices,
size_t  n_vertices,
const indexArray  faces,
size_t  n_faces 
)
private

Builds the tree without it's cache friendly representation. Utilizes the buildTreeRecursive method.

Parameters
verticesVertices of mesh to create tree for
facesFaces of mesh to create tree for
Returns
Root node of the tree

◆ buildTree() [2/2]

template<typename BaseVecT >
BVHNodePtr lvr2::BVHTree< BaseVecT >::buildTree ( const vector< float > &  vertices,
const vector< uint32_t > &  faces 
)
private

Builds the tree without it's cache friendly representation. Utilizes the buildTreeRecursive method.

Parameters
verticesVertices of mesh to create tree for
facesFaces of mesh to create tree for
Returns
Root node of the tree

◆ buildTreeRecursive()

template<typename BaseVecT >
BVHNodePtr lvr2::BVHTree< BaseVecT >::buildTreeRecursive ( vector< AABB > &  work,
uint32_t  depth = 0 
)
private

Recursive method to build the tree.

Parameters
workThe current work queue to generate the tree from
depthThe current depth of the tree
Returns
Root node of the current tree

◆ convertTrianglesIntersectionData()

template<typename BaseVecT >
void lvr2::BVHTree< BaseVecT >::convertTrianglesIntersectionData ( )
private

Converts the precalculated triangle intersection data to a SIMD friendly structure.

◆ createCFTree()

template<typename BaseVecT >
void lvr2::BVHTree< BaseVecT >::createCFTree ( )
private

Creates the cache friendly representation of the tree. Needs the tree itself!

◆ createCFTreeRecursive()

template<typename BaseVecT >
void lvr2::BVHTree< BaseVecT >::createCFTreeRecursive ( BVHNodePtr  currentNode,
uint32_t &  idxBoxes 
)
private

Recursive method for cache friendly tree creation.

Parameters
currentNodeCurrent node to convert to it's cache friendly form
idxBoxesNumber of boxes created for the current tree. This has to be increased every time a box is processed.

◆ getIndexesOrTrilists()

template<typename BaseVecT >
const vector<uint32_t>& lvr2::BVHTree< BaseVecT >::getIndexesOrTrilists ( ) const
Returns
Four values per node:
  1. value: 1st bit of first value indicates, wether the current node is a leaf node or inner node. If it's a leaf node the rest of the bits indicate the number of triangles in this node.
  2. value: Only set, if the node is an inner node. Indicates the start index of the left sub tree in this vector.
  3. value: Only set, if the node is an inner node. Indicates the start index of the right sub tree in this vector.
  4. value: Only set, if the node is a leaf node. Contains the start index for triangles in getTriIndexList

◆ getLimits()

template<typename BaseVecT >
const vector<float>& lvr2::BVHTree< BaseVecT >::getLimits ( ) const
Returns
Boundaries of the the AABB of all nodes

◆ getTrianglesIntersectionData()

template<typename BaseVecT >
const vector<float>& lvr2::BVHTree< BaseVecT >::getTrianglesIntersectionData ( ) const

Returns precalculated values for the triangle intersection tests.

Returns
16 values per triangle: 1-3: x, y, z of normal 4: normal.dot(point1) 5-7: x, y, z of edge plane vector 1 8: scalar product of point 1 and edge plane vector 1 9-11: x, y, z of edge plane vector 2 12: scalar product of point 2 and edge plane vector 2 13-15: x, y, z of edge plane vector 3 16: scalar product of point 3 and edge plane vector 3

◆ getTriIndexList()

template<typename BaseVecT >
const vector<uint32_t>& lvr2::BVHTree< BaseVecT >::getTriIndexList ( ) const
Returns
Index list (for getTrianglesIntersectionData) of triangles in the leaf nodes

Member Data Documentation

◆ m_indexesOrTrilists

template<typename BaseVecT >
vector<uint32_t> lvr2::BVHTree< BaseVecT >::m_indexesOrTrilists
private

Definition at line 191 of file BVH.hpp.

◆ m_limits

template<typename BaseVecT >
vector<float> lvr2::BVHTree< BaseVecT >::m_limits
private

Definition at line 190 of file BVH.hpp.

◆ m_root

template<typename BaseVecT >
BVHNodePtr lvr2::BVHTree< BaseVecT >::m_root
private

Definition at line 185 of file BVH.hpp.

◆ m_triangles

template<typename BaseVecT >
vector<Triangle> lvr2::BVHTree< BaseVecT >::m_triangles
private

Definition at line 186 of file BVH.hpp.

◆ m_trianglesIntersectionData

template<typename BaseVecT >
vector<float> lvr2::BVHTree< BaseVecT >::m_trianglesIntersectionData
private

Definition at line 192 of file BVH.hpp.

◆ m_triIndexList

template<typename BaseVecT >
vector<uint32_t> lvr2::BVHTree< BaseVecT >::m_triIndexList
private

Definition at line 189 of file BVH.hpp.


The documentation for this class was generated from the following file:


lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Wed Mar 2 2022 00:37:27