Forward declare the BVH node since it is needed for the polymorphic lambdas. More...

#include <EBGeometry_BVH.hpp>

Inheritance diagram for BVH::NodeT< T, P, BV, K >:

Collaboration diagram for BVH::NodeT< T, P, BV, K >:

Public Types
using	PrimitiveList = PrimitiveListT< P >
	Alias for list of primitives.

using	Vec3 = Vec3T< T >
	Alias for list of primitives.

using	Node = NodeT< T, P, BV, K >
	Alias for node type.

using	NodePtr = std::shared_ptr< Node >
	Alias for node type pointer.

using	Partitioner = PartitionerT< P, BV, K >
	Alias for partitioner.

using	StopFunction = StopFunctionT< T, P, BV, K >
	Alias for stop function.

Public Member Functions
	NodeT () noexcept
	Default constructor which sets a regular node.

	NodeT (const std::vector< PrimAndBV< P, BV >> &a_primsAndBVs) noexcept
	Construct a BVH node from a set of primitives and their bounding volumes. More...

virtual	~NodeT () noexcept
	Destructor (does nothing)

void	topDownSortAndPartition (const Partitioner &a_partitioner=BVCentroidPartitioner< T, P, BV, K >, const StopFunction &a_stopCrit=DefaultStopFunction< T, P, BV, K >) noexcept
	Function for using top-down construction of the bounding volume hierarchy. More...

template<typename S >
void	bottomUpSortAndPartition () noexcept
	Function for doing bottom-up construction using a specified space-filling curve. More...

bool	isLeaf () const noexcept
	Get node type.

bool	isPartitioned () const noexcept
	Check if BVH is already partitioned.

const BV &	getBoundingVolume () const noexcept
	Get bounding volume. More...

const PrimitiveList &	getPrimitives () const noexcept
	Get the primitives stored in this node. More...

const std::vector< BV > &	getBoundingVolumes () const noexcept
	Get the bounding volumes for the primitives in this node (can be empty if regular node) More...

T	getDistanceToBoundingVolume (const Vec3 &a_point) const noexcept
	Get the distance from a 3D point to the bounding volume. More...

const std::array< std::shared_ptr< NodeT< T, P, BV, K > >, K > &	getChildren () const noexcept
	Return this node's children. More...

template<class Meta >
void	traverse (const BVH::Updater< P > &a_updater, const BVH::Visiter< Node, Meta > &a_visiter, const BVH::Sorter< Node, Meta, K > &a_sorter, const BVH::MetaUpdater< Node, Meta > &a_metaUpdater) const noexcept
	Recursion-less BVH traversal algorithm. The user inputs the update rule, a pruning criterion, and a criterion of who to visit first. More...

std::shared_ptr< LinearBVH< T, P, BV, K > >	flattenTree () const noexcept
	Flatten everything beneath this node into a depth-first sorted BVH hierarchy. More...

Protected Member Functions
PrimitiveList &	getPrimitives () noexcept
	Get the list of primitives in this node. More...

std::vector< BV > &	getBoundingVolumes () noexcept
	Get the bounding volumes for the primitives in this node (can be empty if regular node) More...

void	setChildren (const std::array< std::shared_ptr< NodeT< T, P, BV, K >>, K > &a_children) noexcept
	Explicitly set this node's children. More...

size_t	flattenTree (std::vector< std::shared_ptr< LinearNodeT< T, P, BV, K >>> &a_linearNodes, std::vector< std::shared_ptr< const P >> &a_sortedPrimitives, size_t &a_offset) const noexcept
	Flatten tree method. More...

Protected Attributes
BV	m_boundingVolume
	Bounding volume object for enclosing everything in this node.

bool	m_partitioned
	Determines whether or not the partitioning function has already been called.

std::vector< std::shared_ptr< const P > >	m_primitives
	Primitives list. This will be empty for regular nodes.

std::vector< BV >	m_boundingVolumes
	List of bounding volumes for the primitives. This will be empty for regular nodes.

std::array< std::shared_ptr< NodeT< T, P, BV, K > >, K >	m_children
	Children nodes.

Detailed Description

template<class T, class P, class BV, size_t K>
class BVH::NodeT< T, P, BV, K >

Forward declare the BVH node since it is needed for the polymorphic lambdas.

Class which encapsulates a node in a bounding volume hierarchy.

T is the precision used in the BVH computations, P is the enclosing primitive and BV is the bounding volume used in the BVH. K is the tree degree.

T is the precision, P is the primitive type you want to enclose, BV is the bounding volume type used at the nodes. The parameter K (which must be

1) is the tree degree. K=2 is a binary tree, K=3 is a tertiary tree and so

on.

Constructor & Destructor Documentation

◆ NodeT()

template<class T , class P , class BV , size_t K>

BVH::NodeT< T, P, BV, K >::NodeT ( const std::vector< PrimAndBV< P, BV >> & a_primsAndBVs )

noexcept

Construct a BVH node from a set of primitives and their bounding volumes.

Parameters

[in] a_primsAndBVs Primitives and their bounding volumes

Member Function Documentation

◆ bottomUpSortAndPartition()

template<class T , class P , class BV , size_t K>

template<typename S >

void BVH::NodeT< T, P, BV, K >::bottomUpSortAndPartition ( )

inlinenoexcept

Function for doing bottom-up construction using a specified space-filling curve.

The template parameter is the space-filling curve type. This function will partition the BVH by first sorting the bounding volume centroids along the space-filling curve. The tree is then constructed by placing at least K primitives in each leaf, and the leaves are then merged upwards until we reach the root node.

Note: S must have an encode and decode function which returns an SFC index. See the SFC namespace for examples for Morton and Nested indices.

◆ flattenTree() [1/2]

template<class T , class P , class BV , size_t K>

std::shared_ptr<LinearBVH<T, P, BV, K> > BVH::NodeT< T, P, BV, K >::flattenTree ( ) const

inlinenoexcept

Flatten everything beneath this node into a depth-first sorted BVH hierarchy.

This will compute the flattening of the standard BVH tree and return a pointer to the linear corresponding to the current node.

◆ flattenTree() [2/2]

template<class T , class P , class BV , size_t K>

size_t BVH::NodeT< T, P, BV, K >::flattenTree	(	std::vector< std::shared_ptr< LinearNodeT< T, P, BV, K >>> &	a_linearNodes,
		std::vector< std::shared_ptr< const P >> &	a_sortedPrimitives,
		size_t &	a_offset
	)		const

inlineprotectednoexcept

Flatten tree method.

This function will flatten everything beneath the current node and linearize all the nodes and primitives beneath it to a_linearNodes and a_sortedPrimitives. This function is called recursively.

Parameters

[in,out]	a_linearNodes	BVH nodes, linearized onto a vector.
[in,out]	a_sortedPrimitives	Sorted primitives (in leaf node order).
[in,out]	a_offset	Supporting integer for figuring out where in the tree we are.

Note: When called from the root node, a_linearNodes and a_sortedPrimitives should be empty and a_offset=0UL.

◆ getBoundingVolume()

template<class T , class P , class BV , size_t K>

const BV& BVH::NodeT< T, P, BV, K >::getBoundingVolume ( ) const

inlinenoexcept

Get bounding volume.

Returns: m_bv

◆ getBoundingVolumes() [1/2]

template<class T , class P , class BV , size_t K>

const std::vector<BV>& BVH::NodeT< T, P, BV, K >::getBoundingVolumes ( ) const

inlinenoexcept

Get the bounding volumes for the primitives in this node (can be empty if regular node)

Returns: m_boundingVolumes

◆ getBoundingVolumes() [2/2]

template<class T , class P , class BV , size_t K>

std::vector<BV>& BVH::NodeT< T, P, BV, K >::getBoundingVolumes ( )

inlineprotectednoexcept

Get the bounding volumes for the primitives in this node (can be empty if regular node)

Returns: m_boundingVolumes

◆ getChildren()

template<class T , class P , class BV , size_t K>

const std::array<std::shared_ptr<NodeT<T, P, BV, K> >, K>& BVH::NodeT< T, P, BV, K >::getChildren ( ) const

inlinenoexcept

Return this node's children.

Returns: m_children.

◆ getDistanceToBoundingVolume()

template<class T , class P , class BV , size_t K>

T BVH::NodeT< T, P, BV, K >::getDistanceToBoundingVolume ( const Vec3 & a_point ) const

inlinenoexcept

Get the distance from a 3D point to the bounding volume.

Parameters

[in] a_point 3D point

Returns: Returns distance to bounding volume. A zero distance implies that the input point is inside the bounding volume.

◆ getPrimitives() [1/2]

template<class T , class P , class BV , size_t K>

const PrimitiveList& BVH::NodeT< T, P, BV, K >::getPrimitives ( ) const

inlinenoexcept

Get the primitives stored in this node.

Returns: m_primitives.

◆ getPrimitives() [2/2]

template<class T , class P , class BV , size_t K>

PrimitiveList& BVH::NodeT< T, P, BV, K >::getPrimitives ( )

inlineprotectednoexcept

Get the list of primitives in this node.

Returns: Primitives list

◆ setChildren()

template<class T , class P , class BV , size_t K>

void BVH::NodeT< T, P, BV, K >::setChildren ( const std::array< std::shared_ptr< NodeT< T, P, BV, K >>, K > & a_children )

inlineprotectednoexcept

Explicitly set this node's children.

This will turn this node into the parent node of the input children, i.e. a regular node.

Parameters

[in] a_children Child nodes.

◆ topDownSortAndPartition()

template<class T , class P , class BV , size_t K>

void BVH::NodeT< T, P, BV, K >::topDownSortAndPartition	(	const Partitioner &	a_partitioner = `BVCentroidPartitioner< T, P, BV, K >`,
		const StopFunction &	a_stopCrit = `DefaultStopFunction< T, P, BV, K >`
	)

inlinenoexcept

Function for using top-down construction of the bounding volume hierarchy.

The rules for terminating the hierarchy construction, and how to partition them are encoded in the input arguments (a_partitioner, a_stopCrit).

Parameters

[in]	a_partitioner	Partitioning function. This is a polymorphic function which divides a set of primitives into two or more sub-lists.
[in]	a_stopCrit	Termination function which tells us when to stop the recursion.

◆ traverse()

template<class T , class P , class BV , size_t K>

template<class Meta >

void BVH::NodeT< T, P, BV, K >::traverse	(	const BVH::Updater< P > &	a_updater,
		const BVH::Visiter< Node, Meta > &	a_visiter,
		const BVH::Sorter< Node, Meta, K > &	a_sorter,
		const BVH::MetaUpdater< Node, Meta > &	a_metaUpdater
	)		const

inlinenoexcept

Recursion-less BVH traversal algorithm. The user inputs the update rule, a pruning criterion, and a criterion of who to visit first.

Parameters

[in]	a_updater	Update rule (for updating whatever the user is interested in updated)
[in]	a_visiter	Visiter rule. Must return true if we should visit the node.
[in]	a_sorter	Children sort function for deciding which subtrees and investigated first.
[in]	a_metaUpdater	Updater for meta-information.

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

/home/runner/work/EBGeometry/EBGeometry/Source/EBGeometry_BVH.hpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class T, class P, class BV, size_t K> class BVH::NodeT< T, P, BV, K >

Constructor & Destructor Documentation

◆ NodeT()

Member Function Documentation

◆ bottomUpSortAndPartition()

◆ flattenTree() [1/2]

◆ flattenTree() [2/2]

◆ getBoundingVolume()

◆ getBoundingVolumes() [1/2]

◆ getBoundingVolumes() [2/2]

◆ getChildren()

◆ getDistanceToBoundingVolume()

◆ getPrimitives() [1/2]

◆ getPrimitives() [2/2]

◆ setChildren()

◆ topDownSortAndPartition()

◆ traverse()

template<class T, class P, class BV, size_t K>
class BVH::NodeT< T, P, BV, K >