EBGeometry 1.0
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
BVH::NodeT< T, P, BV, K > Class Template Reference

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 >:
Inheritance graph
[legend]
Collaboration diagram for BVH::NodeT< T, P, BV, K >:
Collaboration graph
[legend]

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.
 
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.
 
template<typename S >
void bottomUpSortAndPartition () noexcept
 Function for doing bottom-up construction using a specified space-filling curve.
 
bool isLeaf () const noexcept
 Get node type.
 
bool isPartitioned () const noexcept
 Check if BVH is already partitioned.
 
const BVgetBoundingVolume () const noexcept
 Get bounding volume.
 
const PrimitiveListgetPrimitives () const noexcept
 Get the primitives stored in this node.
 
const std::vector< BV > & getBoundingVolumes () const noexcept
 Get the bounding volumes for the primitives in this node (can be empty if regular node)
 
T getDistanceToBoundingVolume (const Vec3 &a_point) const noexcept
 Get the distance from a 3D point to the bounding volume.
 
const std::array< std::shared_ptr< NodeT< T, P, BV, K > >, K > & getChildren () const noexcept
 Return this node's children.
 
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.
 
std::shared_ptr< LinearBVH< T, P, BV, K > > flattenTree () const noexcept
 Flatten everything beneath this node into a depth-first sorted BVH hierarchy.
 

Protected Member Functions

PrimitiveListgetPrimitives () noexcept
 Get the list of primitives in this node.
 
std::vector< BV > & getBoundingVolumes () noexcept
 Get the bounding volumes for the primitives in this node (can be empty if regular node)
 
void setChildren (const std::array< std::shared_ptr< NodeT< T, P, BV, K > >, K > &a_children) noexcept
 Explicitly set this node's children.
 
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.
 

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< BVm_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 > >, Km_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_primsAndBVsPrimitives 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_linearNodesBVH nodes, linearized onto a vector.
[in,out]a_sortedPrimitivesSorted primitives (in leaf node order).
[in,out]a_offsetSupporting 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_point3D 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_childrenChild nodes.

◆ topDownSortAndPartition()

template<class T , class P , class BV , size_t K>
void BVH::NodeT< T, P, BV, K >::topDownSortAndPartition ( const Partitioner a_partitioner = BVCentroidPartitionerTPBVK >,
const StopFunction a_stopCrit = DefaultStopFunctionTPBVK > 
)
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_partitionerPartitioning function. This is a polymorphic function which divides a set of primitives into two or more sub-lists.
[in]a_stopCritTermination 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_updaterUpdate rule (for updating whatever the user is interested in updated)
[in]a_visiterVisiter rule. Must return true if we should visit the node.
[in]a_sorterChildren sort function for deciding which subtrees and investigated first.
[in]a_metaUpdaterUpdater for meta-information.

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