Forward declaration of the tree-structured BVH, defined in EBGeometry_TreeBVH.hpp. Needed by LeafPredicate and by PackedBVH's constructor from a TreeBVH. More...

#include <EBGeometry_TreeBVH.hpp>

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 ()
	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 (size_t a_targetLeafSize=1)
	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 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
	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.

PackedBVH< T, P, K >	pack (Pool &a_pool) const
	Flatten this tree into a cache-friendly PackedBVH with the same primitive type.

template<class Q , class Converter >
PackedBVH< T, Q, K >	packWith (Pool &a_pool, 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 Array< std::shared_ptr< TreeBVH< T, P, BV, K > >, K > &a_children)
	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.

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, defined in EBGeometry_TreeBVH.hpp. Needed by LeafPredicate and by PackedBVH's constructor from a TreeBVH.

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. The root may live anywhere (on the stack, in a container, behind a shared_ptr); only the nodes below it are held by shared_ptr.

Template Parameters

T	Floating-point precision.
P	Primitive type. Construction imposes no interface requirement on P itself, except that PrimitiveCentroidPartitioner calls P::getCentroid(); the other partitioners and the bottom-up build work from the bounding volumes alone. PackedBVH imposes no interface requirement on P either; any further requirement comes entirely from whatever leaf-eval a caller passes to PackedBVH::traverse() (see PackedBVH).
BV	Bounding volume type, with a constructor taking a std::vector<BV> (a leaf's box, enclosing its primitives' boxes), merged() (an interior node's box, folded from its children's without allocating) and a default-constructed empty box. AABBT is one; pack() requires it.
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 ( size_t a_targetLeafSize = 1 )

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 split evenly into K^d leaves and merged upwards in groups of K to the root, so every leaf is on the same level. d is the smallest depth at which the leaves hold at most a_targetLeafSize primitives, but never so deep that there are more leaves than primitives (K^d <= N). The leaf count can only be a power of K, so the leaves may hold well under the target. The default target, 1, gives the deepest such tree: d = floor(log_K(N)), at most K primitives per leaf.

Template Parameters

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

Parameters

[in] a_targetLeafSize Target primitives per leaf. Must be > 0.

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

PackedBVH< T, P, K > EBGeometry::BVH::TreeBVH< T, P, BV, K >::pack ( Pool & a_pool ) 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.

Parameters

[in,out] a_pool Pool the packed arrays are reserved from; must outlive the result.

Returns: The resulting PackedBVH, a handle into a_pool.

◆ packWith()

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

template<class Q , class Converter >

PackedBVH< T, Q, K > EBGeometry::BVH::TreeBVH< T, P, BV, K >::packWith	(	Pool &	a_pool,
		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, which becomes the resulting PackedBVH's primitive array, preserving 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>.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive the result.
[in]	a_converter	Leaf-conversion function.

Returns: The resulting PackedBVH<T, Q, K>, a handle into a_pool.

◆ 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, folded with BV::merged(). Nothing is allocated: a leaf overwrites its stored per-primitive volumes in place. 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 Array< std::shared_ptr< TreeBVH< T, P, BV, K > >, K > & a_children )

inlineprotected

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

The node's box is folded from the children's boxes with BV::merged(), so nothing is allocated.

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. Every one of the K sub-lists the partitioner returns must hold at least one primitive: an empty one would become a leaf with no primitives, which aborts, in every build, with a message naming the partition.

Parameters

[in]	a_partitioner	Partitioning function. Divides a (primitive, BV) list into K non-empty 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

inline

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 files:

Source/EBGeometry_PackedBVH.hpp
Source/EBGeometry_TreeBVH.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()