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< Triangle >	m_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

vertices	Vertices of mesh to create tree for
faces	Faces 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

vertices	Vertices of mesh to create tree for
faces	Faces 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

vertices	Vertices of mesh to create tree for
faces	Faces 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

work	The current work queue to generate the tree from
depth	The 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

currentNode	Current node to convert to it's cache friendly form
idxBoxes	Number 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:

• BVH.hpp