BVH Namespace Reference

Namespace for various bounding volume hierarchy (BVH) functionality. More...

Classes
class	NodeT
	Forward declare the BVH node since it is needed for the polymorphic lambdas. More...
class	LinearNodeT
	Forward declare linear node class. More...
class	LinearBVH
	Forward declare linear BVH class. More...

Typedefs
template<class P >
using	PrimitiveListT = std::vector< std::shared_ptr< const P > >
	List of primitives. More...
template<class P , class BV >
using	PrimAndBV = std::pair< std::shared_ptr< const P >, BV >
	Alias for a list geometric primitive and BV.
template<class P , class BV >
using	PrimAndBVListT = std::vector< PrimAndBV< P, BV > >
	List of primitives and their bounding volumes. More...
template<class P , class BV , size_t K>
using	PartitionerT = std::function< std::array< PrimAndBVListT< P, BV >, K >(const PrimAndBVListT< P, BV > &a_primsAndBVs)>
	Polymorphic partitioner for splitting a list of primitives and BVs into K new subsets. More...
template<class T , class P , class BV , size_t K>
using	StopFunctionT = std::function< bool(const NodeT< T, P, BV, K > &a_node)>
	Stop function for deciding when a BVH node can't be divided into sub-volumes. More...
template<class P >
using	Updater = std::function< void(const PrimitiveListT< P > &a_primitives)>
	Updater for tree traversal. More...
template<class NodeType , class Meta >
using	Visiter = std::function< bool(const NodeType &a_node, const Meta &a_meta)>
	Visiter pattern for LinearBVH::traverse. Must return true if we should visit the node and false otherwise. More...
template<class NodeType , class Meta , size_t K>
using	Sorter = std::function< void(std::array< std::pair< std::shared_ptr< const NodeType >, Meta >, K > &a_children)>
	Sorting criterion for which child node to visit first. This takes an input list of child nodes and sorts it. When further into the sub-tree, the first node is investigated first, then the second, etc. The Meta template parameter is a door left open to the user for attaching additional data to the sorter/visiter pattern.
template<class NodeType , class Meta >
using	MetaUpdater = std::function< Meta(const NodeType &a_node)>
	Updater for when user wants to add some meta-data to his BVH traversal.

Enumerations
enum class	Build { TopDown , Morton , Nested }
	Enum for specifying whether or not the construction is top-down or bottom-up.

Variables
template<class X , size_t K>
auto	equalCounts
	Function for splitting a vector of some size into K almost-equal chunks. This is a utility function. More...
template<class T , class P , class BV , size_t K>
auto	PrimitiveCentroidPartitioner
	Simple partitioner which sorts the primitives based on their centroids, and then splits into K pieces. More...
template<class T , class P , class BV , size_t K>
auto	BVCentroidPartitioner
	Simple partitioner which sorts the BVs based on their bounding volume centroids, and then splits into K pieces. More...
template<class T , class P , class BV , size_t K>
auto	DefaultStopFunction
	Simple stop function which ends the recursion when there aren't enough primitives in the node. More...

Detailed Description

Namespace for various bounding volume hierarchy (BVH) functionality.

Typedef Documentation

PartitionerT

template<class P , class BV , size_t K>

using BVH::PartitionerT = typedef std::function<std::array<PrimAndBVListT<P, BV>, K>(const PrimAndBVListT<P, BV>& a_primsAndBVs)>

Polymorphic partitioner for splitting a list of primitives and BVs into K new subsets.

P is the primitive type bound in the BVH and K is the BVH degrees. BV is the bounding volume type.

Parameters

[in]

a_primsAndBVs

Vector of primitives and their bounding volumes.

Returns

Return a K-length array of subset lists.

PrimAndBVListT

template<class P , class BV >

using BVH::PrimAndBVListT = typedef std::vector<PrimAndBV<P, BV> >

List of primitives and their bounding volumes.

P is the primitive type and BV is the bounding volume enclosing the implicit surface of each P.

PrimitiveListT

template<class P >

using BVH::PrimitiveListT = typedef std::vector<std::shared_ptr<const P> >

List of primitives.

P is the primitive bounded by the BVH.

StopFunctionT

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

using BVH::StopFunctionT = typedef std::function<bool(const NodeT<T, P, BV, K>& a_node)>

Stop function for deciding when a BVH node can't be divided into sub-volumes.

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.

Parameters

[in]

a_node

BVH node

Returns

True if the node can't be divided into subvolumes and false otherwise.

Updater

template<class P >

using BVH::Updater = typedef std::function<void(const PrimitiveListT<P>& a_primitives)>

Updater for tree traversal.

Parameters

[in]

a_primitives.

Visiter

template<class NodeType , class Meta >

using BVH::Visiter = typedef std::function<bool(const NodeType& a_node, const Meta& a_meta)>

Visiter pattern for LinearBVH::traverse. Must return true if we should visit the node and false otherwise.

The Meta template parameter is a door left open to the user for attaching additional data to the sorter/visiter pattern.

Parameters

[in]	a_node	Node to visit or not
[in]	a_meta	Meta-data for node visit.

Variable Documentation

BVCentroidPartitioner

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

auto BVH::BVCentroidPartitioner

Initial value:

= [](const PrimAndBVListT<P, BV>& a_primsAndBVs) -> std::array<PrimAndBVListT<P, BV>, K> {
    Vec3T<T> lo = Vec3T<T>::max();
    Vec3T<T> hi = -Vec3T<T>::max();
 
    for (const auto& pbv : a_primsAndBVs) {
      lo = min(lo, pbv.second.getCentroid());
      hi = max(hi, pbv.second.getCentroid());
    }
 
    const size_t splitDir = (hi - lo).maxDir(true);
 
    
    PrimAndBVListT<P, BV> sortedPrimsAndBVs(a_primsAndBVs);
 
    std::sort(sortedPrimsAndBVs.begin(),
              sortedPrimsAndBVs.end(),
              [splitDir](const PrimAndBV<P, BV>& pbv1, const PrimAndBV<P, BV>& pbv2) -> bool {
                return pbv1.second.getCentroid()[splitDir] < pbv2.second.getCentroid()[splitDir];
              });
 
    return BVH::equalCounts<PrimAndBV<P, BV>, K>(sortedPrimsAndBVs);
  }

Simple partitioner which sorts the BVs based on their bounding volume centroids, and then splits into K pieces.

Parameters

[in]

a_primsAndBVs

Input primitives and their bounding volumes

DefaultStopFunction

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

auto BVH::DefaultStopFunction

Initial value:

=
    [](const BVH::NodeT<T, P, BV, K>& a_node) noexcept -> bool { return (a_node.getPrimitives()).size() < K; }

Simple stop function which ends the recursion when there aren't enough primitives in the node.

Parameters

[in]

a_node

Input BVH node

equalCounts

template<class X , size_t K>

auto BVH::equalCounts

Initial value:

= [](const std::vector<X>& a_primitives) noexcept -> std::array<std::vector<X>, K> {
    int length = a_primitives.size() / K;
    int remain = a_primitives.size() % K;
 
    int begin = 0;
    int end   = 0;
 
    std::array<std::vector<X>, K> chunks;
 
    for (size_t k = 0; k < K; k++) {
      end += (remain > 0) ? length + 1 : length;
      remain--;
 
      chunks[k] = std::vector<X>(a_primitives.begin() + begin, a_primitives.begin() + end);
 
      begin = end;
    }
 
    return chunks;
  }

Function for splitting a vector of some size into K almost-equal chunks. This is a utility function.

PrimitiveCentroidPartitioner

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

auto BVH::PrimitiveCentroidPartitioner

Initial value:

=
    [](const PrimAndBVListT<P, BV>& a_primsAndBVs) noexcept -> std::array<PrimAndBVListT<P, BV>, K> {
    Vec3T<T> lo = Vec3T<T>::max();
    Vec3T<T> hi = -Vec3T<T>::max();
 
    for (const auto& pbv : a_primsAndBVs) {
      lo = min(lo, pbv.first->getCentroid());
      hi = max(hi, pbv.first->getCentroid());
    }
 
    const size_t splitDir = (hi - lo).maxDir(true);
 
    
    PrimAndBVListT<P, BV> sortedPrimsAndBVs(a_primsAndBVs);
 
    std::sort(sortedPrimsAndBVs.begin(),
              sortedPrimsAndBVs.end(),
              [splitDir](const PrimAndBV<P, BV>& pbv1, const PrimAndBV<P, BV>& pbv2) -> bool {
                return pbv1.first->getCentroid(splitDir) < pbv2.first->getCentroid(splitDir);
              });
 
    return BVH::equalCounts<PrimAndBV<P, BV>, K>(sortedPrimsAndBVs);
  }

Simple partitioner which sorts the primitives based on their centroids, and then splits into K pieces.

Parameters

[in]

a_primsAndBVs

Input primitives and their bounding volumes