Forward declaration of the tree-structured BVH. Needed by LeafPredicate and the default-partitioner lambdas defined below. More...

#include <EBGeometry_BVH.hpp>

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

[legend]

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

[legend]

Public Types
using	PrimitiveList = BVH::PrimitiveList< P >
	Alias for the primitive list type.

using	Vec3 = Vec3T< T >
	Alias for the 3D vector type.

using	Node = TreeBVH< T, P, BV, K >
	Alias for this node type (used in traversal callbacks).

using	NodePtr = std::shared_ptr< Node >
	Alias for a shared pointer to a node.

using	Partitioner = BVH::Partitioner< P, BV, K >
	Alias for the partitioner type.

using	LeafPredicate = BVH::LeafPredicate< T, P, BV, K >
	Alias for the stop-function type.

Public Member Functions
	TreeBVH () noexcept
	Default constructor. Creates an empty interior node.

	TreeBVH (const std::vector< PrimAndBV< P, BV > > &a_primsAndBVs)
	Construct a leaf node from a set of (primitive, BV) pairs.

	TreeBVH (std::vector< PrimAndBV< P, BV > > &&a_primsAndBVs)
	Construct a leaf node holding the given (primitive, bounding volume) pairs, moved in.

	~TreeBVH () noexcept=default
	Destructor.

	TreeBVH (const TreeBVH &a_other)=delete
	Deleted copy constructor.

TreeBVH &	operator= (const TreeBVH &a_other)=delete
	Deleted copy assignment operator.

	TreeBVH (TreeBVH &&a_other) noexcept=default
	Move constructor.

TreeBVH &	operator= (TreeBVH &&a_other) noexcept=default
	Move assignment operator.

void	topDownSortAndPartition (const Partitioner &a_partitioner=BVCentroidPartitioner< T, P, BV, K >, const LeafPredicate &a_stopCrit=DefaultLeafPredicate< T, P, BV, K >)
	Recursively partition this node top-down.

template<typename S >
void	bottomUpSortAndPartition ()
	Recursively partition this node bottom-up along a space-filling curve.

bool	isLeaf () const noexcept
	Return true if this is a leaf node (no children, non-empty primitive list).

bool	isPartitioned () const noexcept
	Return true if the tree has already been partitioned.

const BV &	getBoundingVolume () const noexcept
	Get the bounding volume for this node.

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

const std::vector< BV > &	getBoundingVolumes () const noexcept
	Get the per-primitive bounding volumes stored in this node.

T	getDistanceToBoundingVolume (const Vec3 &a_point) const noexcept
	Get the distance from a_point to this node's bounding volume.

const std::array< std::shared_ptr< TreeBVH< T, P, BV, K > >, K > &	getChildren () const noexcept
	Get the K child nodes of this interior node.

std::shared_ptr< TreeBVH< T, P, BV, K > >	deepCopy () const
	Produce an independent deep copy of this tree.

template<class NodeKey >
void	traverse (const BVH::LeafEvaluator< P > &a_leafEvaluator, const BVH::PrunePredicate< Node, NodeKey > &a_prunePredicate, const BVH::ChildOrderer< Node, NodeKey, K > &a_childOrderer, const BVH::NodeKeyFactory< Node, NodeKey > &a_nodeKeyFactory) const noexcept
	Recursion-free BVH traversal using an explicit LIFO stack (depth-first order).

template<class StoragePolicy = BVH::SharedPtrStorage<P>>
std::shared_ptr< PackedBVH< T, P, K, StoragePolicy > >	pack () const
	Flatten this tree into a cache-friendly PackedBVH with the same primitive type.

template<class Q , class Converter , class StoragePolicy = BVH::SharedPtrStorage<Q>>
std::shared_ptr< PackedBVH< T, Q, K, StoragePolicy > >	packWith (Converter &&a_converter) const
	Flatten and convert this tree into a PackedBVH with a different primitive type Q.

Protected Member Functions
PrimitiveList &	getPrimitives () noexcept
	Non-const accessor for the primitive list (used during construction).

std::vector< BV > &	getBoundingVolumes () noexcept
	Non-const accessor for the per-primitive bounding volumes (used during construction).

void	setChildren (const std::array< std::shared_ptr< TreeBVH< T, P, BV, K > >, K > &a_children) noexcept
	Set the K child nodes, converting this node from a leaf into an interior node.

Protected Attributes
BV	m_boundingVolume
	Bounding volume enclosing all primitives in this subtree.

bool	m_partitioned
	True after topDownSortAndPartition() or bottomUpSortAndPartition() has been called.

std::vector< std::shared_ptr< const P > >	m_primitives
	Primitives stored in this node. Non-empty for leaf nodes only.

std::vector< BV >	m_boundingVolumes
	Per-primitive bounding volumes. Non-empty for leaf nodes only.

std::array< std::shared_ptr< TreeBVH< T, P, BV, K > >, K >	m_children
	K child nodes. Non-null for interior nodes only.

Detailed Description

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

Forward declaration of the tree-structured BVH. Needed by LeafPredicate and the default-partitioner lambdas defined below.

Tree-structured BVH node used during construction.

Each node stores a bounding volume, a list of primitives (non-empty for leaf nodes only), and K child pointers (non-null for interior nodes only).

Build the tree by constructing a root node from a set of (primitive, BV) pairs and then calling topDownSortAndPartition() or bottomUpSortAndPartition(). Once built, call pack() to obtain a cache-friendly PackedBVH for traversal.

Template Parameters

T	Floating-point precision.
P	Primitive type. Must provide getCentroid() – construction/partitioning never calls any other method on it. PackedBVH itself imposes no interface requirement on P either; any further requirement comes entirely from whatever leaf-eval a caller passes to PackedBVH::pruneTraverse() or PackedBVH::traverse() (see PackedBVH below).
BV	Bounding volume type.
K	Tree branching factor (must be >= 2).

Constructor & Destructor Documentation

◆ TreeBVH() [1/4]

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

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

Construct a leaf node from a set of (primitive, BV) pairs.

Parameters

[in] a_primsAndBVs Primitives and their bounding volumes.

◆ TreeBVH() [2/4]

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

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

Construct a leaf node holding the given (primitive, bounding volume) pairs, moved in.

Rvalue overload: transfers the elements without copying or shared_ptr refcount churn. Used where a caller can relinquish its list (e.g. topDownSortAndPartition moving a partitioner's sub-list into a child node).

Parameters

[in,out] a_primsAndBVs Primitives and their bounding volumes (consumed).

◆ TreeBVH() [3/4]

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

EBGeometry::BVH::TreeBVH< T, P, BV, K >::TreeBVH ( const TreeBVH< T, P, BV, K > & a_other )

delete

Deleted copy constructor.

A TreeBVH is a recursive structure of shared_ptr-linked children (m_children); a compiler-generated copy would only alias the same child subtrees rather than cloning them. topDownSortAndPartition()/bottomUpSortAndPartition() mutate a node's children in place, so such a "copy" could silently share mutable state with the original instead of being independent. Disallowed outright rather than doing the wrong thing; use deepCopy() to replicate a tree independently.

Parameters

[in] a_other Other instance (unused; deleted).

◆ TreeBVH() [4/4]

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

EBGeometry::BVH::TreeBVH< T, P, BV, K >::TreeBVH ( TreeBVH< T, P, BV, K > && a_other )

defaultnoexcept

Move constructor.

Explicitly defaulted: the user-declared destructor above would otherwise suppress the implicitly-generated move constructor.

Parameters

[in,out] a_other Other instance to move from.

Member Function Documentation

◆ bottomUpSortAndPartition()

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

template<typename S >

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

inline

Recursively partition this node bottom-up along a space-filling curve.

S must provide encode() and decode() functions returning SFC indices. Primitives are sorted by their bounding-volume centroid projected onto the curve, then grouped into leaves of size K and merged upwards to the root.

Template Parameters

S	Space-filling curve type (e.g. Morton, Nested).

◆ deepCopy()

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

std::shared_ptr< TreeBVH< T, P, BV, K > > EBGeometry::BVH::TreeBVH< T, P, BV, K >::deepCopy ( ) const

inline

Produce an independent deep copy of this tree.

Recursively clones the node hierarchy: the returned tree owns brand-new nodes, so it can be partitioned or otherwise mutated without affecting this tree (and vice versa). The copy constructor is deleted precisely because a shallow copy would instead alias these mutable child nodes; this is the explicit, correct way to replicate a tree. Primitives are shared, not cloned – each node's std::shared_ptr<const P> entries are copied by handle, matching how a TreeBVH normally references its (immutable) primitives, e.g. faces shared with a DCEL mesh. Works in either state: an unpartitioned tree clones to an unpartitioned leaf (build once, then partition the copies differently), and a partitioned tree clones its full sub-structure.

Returns: Shared pointer to an independent clone of this tree.

◆ getBoundingVolume()

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

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

inlinenoexcept

Get the bounding volume for this node.

Returns: Reference to m_boundingVolume.

◆ getBoundingVolumes() [1/2]

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

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

inlinenoexcept

Get the per-primitive bounding volumes stored in this node.

Non-empty only for leaf nodes.

Returns: Reference to m_boundingVolumes.

◆ getBoundingVolumes() [2/2]

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

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

inlineprotectednoexcept

Non-const accessor for the per-primitive bounding volumes (used during construction).

Returns: Reference to m_boundingVolumes.

◆ getChildren()

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

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

inlinenoexcept

Get the K child nodes of this interior node.

All K children are non-null for interior nodes; the array is unused for leaf nodes.

Returns: Reference to m_children.

◆ getDistanceToBoundingVolume()

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

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

inlinenoexcept

Get the distance from a_point to this node's bounding volume.

Returns zero if a_point is inside the bounding volume.

Parameters

[in] a_point Query point.

Returns: Distance to the bounding volume surface, or zero if inside.

◆ getPrimitives() [1/2]

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

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

inlinenoexcept

Get the primitives stored in this node.

Non-empty only for leaf nodes.

Returns: Reference to m_primitives.

◆ getPrimitives() [2/2]

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

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

inlineprotectednoexcept

Non-const accessor for the primitive list (used during construction).

Returns: Reference to m_primitives.

◆ isLeaf()

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

bool EBGeometry::BVH::TreeBVH< T, P, BV, K >::isLeaf ( ) const

inlinenoexcept

Return true if this is a leaf node (no children, non-empty primitive list).

Returns: True if this node holds primitives directly (i.e. is a leaf).

◆ isPartitioned()

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

bool EBGeometry::BVH::TreeBVH< T, P, BV, K >::isPartitioned ( ) const

inlinenoexcept

Return true if the tree has already been partitioned.

Returns: True if topDownSortAndPartition() or bottomUpSortAndPartition() has been called.

◆ operator=() [1/2]

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

TreeBVH & EBGeometry::BVH::TreeBVH< T, P, BV, K >::operator= ( const TreeBVH< T, P, BV, K > & a_other )

delete

Deleted copy assignment operator.

See the copy constructor for why copying is disallowed.

Parameters

[in] a_other Other instance (unused; deleted).

Returns: Reference to *this (unused; deleted).

◆ operator=() [2/2]

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

TreeBVH & EBGeometry::BVH::TreeBVH< T, P, BV, K >::operator= ( TreeBVH< T, P, BV, K > && a_other )

defaultnoexcept

Move assignment operator.

Parameters

[in,out] a_other Other instance to move from.

Returns: Reference to *this.

◆ pack()

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

template<class StoragePolicy = BVH::SharedPtrStorage<P>>

std::shared_ptr< PackedBVH< T, P, K, StoragePolicy > > EBGeometry::BVH::TreeBVH< T, P, BV, K >::pack ( ) const

inline

Flatten this tree into a cache-friendly PackedBVH with the same primitive type.

Requires BV == AABBT<T>; enforced by static_assert at instantiation.

Template Parameters

StoragePolicy Storage policy for the resulting PackedBVH's primitive array (default: BVH::SharedPtrStorage<P>, matching every existing caller that does not name one explicitly).

Returns: Shared pointer to the resulting PackedBVH.

◆ packWith()

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

template<class Q , class Converter , class StoragePolicy = BVH::SharedPtrStorage<Q>>

std::shared_ptr< PackedBVH< T, Q, K, StoragePolicy > > EBGeometry::BVH::TreeBVH< T, P, BV, K >::packWith ( Converter && a_converter ) const

inline

Flatten and convert this tree into a PackedBVH with a different primitive type Q.

a_converter is called once per leaf: a_converter(leafPrims, 0, count) → std::vector<Q> All returned values are accumulated into a single contiguous buffer, then exposed through the resulting PackedBVH's storage policy (StorageType) to preserve cache locality. Requires BV == AABBT<T>; enforced by static_assert at instantiation.

Template Parameters

Q	Destination primitive type.
Converter	Callable: (PrimitiveList

, uint32_t offset, uint32_t count) → std::vector<Q>.

Template Parameters

StoragePolicy Storage policy for the resulting PackedBVH's primitive array (default: BVH::SharedPtrStorage<Q>, matching every existing caller that does not name one explicitly).

Parameters

[in] a_converter Leaf-conversion function.

Returns: Shared pointer to the resulting PackedBVH<T, Q, K, StoragePolicy>.

◆ setChildren()

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

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

inlineprotectednoexcept

Set the K child nodes, converting this node from a leaf into an interior node.

Parameters

[in] a_children New child nodes.

◆ topDownSortAndPartition()

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

void EBGeometry::BVH::TreeBVH< T, P, BV, K >::topDownSortAndPartition	(	const Partitioner &	a_partitioner = `BVCentroidPartitioner< T, P, BV, K >`,
		const LeafPredicate &	a_stopCrit = `DefaultLeafPredicate< T, P, BV, K >`
	)

inline

Recursively partition this node top-down.

The stop criterion and partitioner determine the tree shape.

Parameters

[in]	a_partitioner	Partitioning function. Divides a (primitive, BV) list into K sub-lists.
[in]	a_stopCrit	Stop function. Returns true when a node should become a leaf.

◆ traverse()

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

template<class NodeKey >

void EBGeometry::BVH::TreeBVH< T, P, BV, K >::traverse	(	const BVH::LeafEvaluator< P > &	a_leafEvaluator,
		const BVH::PrunePredicate< Node, NodeKey > &	a_prunePredicate,
		const BVH::ChildOrderer< Node, NodeKey, K > &	a_childOrderer,
		const BVH::NodeKeyFactory< Node, NodeKey > &	a_nodeKeyFactory
	)		const

inlinenoexcept

Recursion-free BVH traversal using an explicit LIFO stack (depth-first order).

The traversal maintains a stack of (node, NodeKey) pairs. It is seeded with the root node paired with a_nodeKeyFactory applied to the root. On each iteration:

Pop the top (node, nodeKey) pair.
Call a_prunePredicate(node, nodeKey). If it returns false the entire subtree rooted at that node is skipped (pruned) and the loop continues with the next stack entry.
If the node is a leaf, call a_leafEvaluator with the leaf's primitive list.
If the node is an interior node: a. Compute a NodeKey value for each of the K children by calling a_nodeKeyFactory on each child. b. Collect the K (child, NodeKey) pairs into a local array and pass them to a_childOrderer, which reorders the array in-place. c. Push all K pairs onto the stack in sorted order.

Because the stack is LIFO, the child pushed last is visited first. a_childOrderer should therefore place the most promising child last in the array. For a nearest-distance query this means sorting children in descending order of distance — farthest child first, nearest child last — so the nearest child sits on top of the stack and is expanded next.

Template Parameters

NodeKey Auxiliary data type carried on the traversal stack (e.g. a running minimum distance).

Parameters

[in]	a_leafEvaluator	Called at each leaf with the leaf's primitive list.
[in]	a_prunePredicate	Called at each node; return true to descend, false to prune.
[in]	a_childOrderer	Reorders the K (child, NodeKey) pairs in-place before they are pushed; the last element after sorting is visited first.
[in]	a_nodeKeyFactory	Produces a NodeKey value for a node; called once for the root and once per child of every interior node that is visited.

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

Source/EBGeometry_BVH.hpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TreeBVH() [1/4]

◆ TreeBVH() [2/4]

◆ TreeBVH() [3/4]

◆ TreeBVH() [4/4]

Member Function Documentation

◆ bottomUpSortAndPartition()

◆ deepCopy()

◆ getBoundingVolume()

◆ getBoundingVolumes() [1/2]

◆ getBoundingVolumes() [2/2]

◆ getChildren()

◆ getDistanceToBoundingVolume()

◆ getPrimitives() [1/2]

◆ getPrimitives() [2/2]

◆ isLeaf()

◆ isPartitioned()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pack()

◆ packWith()

◆ setChildren()

◆ topDownSortAndPartition()

◆ traverse()