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 BVConstructor >
const BV &	refit (const BVConstructor &a_bvConstructor)
	Refit this subtree's bounding volumes in place after its primitives have moved.

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>.

◆ refit()

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

template<class BVConstructor >

const BV & EBGeometry::BVH::TreeBVH< T, P, BV, K >::refit ( const BVConstructor & a_bvConstructor )

inline

Refit this subtree's bounding volumes in place after its primitives have moved.

Keeps the tree topology – the node hierarchy and each leaf's primitive assignment – exactly as it is, recomputing only the bounding volumes bottom-up: at every leaf, each primitive's bounding volume is recomputed via a_bvConstructor and the leaf's node volume is set to their union; at every interior node, the node volume is set to the union of its K children's (already-refitted) volumes. This is the cheap way to keep a BVH valid for a moving geometry – primitives that shift a little between frames without changing which leaf they belong to – avoiding a full rebuild-and-repack. Because it never re-partitions, a geometry that has deformed enough for primitives to migrate across the tree will accumulate looser (lower query quality) bounding volumes over time and should periodically be rebuilt from scratch instead.

The primitives are reached by handle (std::shared_ptr<const P>): a_bvConstructor is called with each primitive and must return that primitive's current bounding volume. Whatever moved the geometry is expected to have updated the state the primitives read (e.g. a shared DCEL mesh's vertex positions) before refit() is called.

Template Parameters

BVConstructor Callable: (const P&) -> BV, returning one primitive's current bounding volume.

Parameters

[in] a_bvConstructor Bounding-volume constructor for a single primitive.

Returns: Reference to this node's refitted bounding volume (so a parent can union its children).

◆ 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()

◆ refit()

◆ setChildren()

◆ topDownSortAndPartition()

◆ traverse()