Forward declaration of the linearised BVH, defined below. More...

#include <EBGeometry_PackedBVH.hpp>

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

[legend]

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

Classes
struct	Layout
	The BVH's arrays as offsets into its pool, and its root box: a PackedBVH minus its location. More...

struct	Node
	Compact BVH node stored in the flat node array. More...

Public Types
using	BV = EBGeometry::BoundingVolumes::AABBT< T >
	AABB type used for all bounding volumes in this BVH.

Public Member Functions
	PackedBVH ()=delete
	Deleted default constructor. Use build() (or another static build), TreeBVH::pack() or TreeBVH::packWith() to construct.

	PackedBVH (const Layout &a_layout, const PoolLocation &a_location) noexcept
	Rebuild a handle from a stored layout and the location of the pool that holds it.

Layout	layout () const noexcept
	The BVH's arrays without its location, for storing it inside another pool-resident object.

	PackedBVH (Pool &a_pool, const TreeBVH< T, P, BV, K > &a_tree)
	Construct by packing a TreeBVH (identity primitive type).

template<class Q , class Converter >
	PackedBVH (Pool &a_pool, const TreeBVH< T, Q, BV, K > &a_tree, Converter &&a_converter)
	Construct by packing a TreeBVH with primitive-type conversion.

	PackedBVH (Pool &a_pool, const std::vector< Node > &a_linearNodes, const std::vector< BV > &a_nodeBoxes, const std::vector< P > &a_primitives)
	Adopt a node array, its boxes and a primitive array built elsewhere.

	~PackedBVH ()=default
	Destructor.

	PackedBVH (const PackedBVH &a_other)=default
	Copy constructor.

PackedBVH &	operator= (const PackedBVH &a_other)=default
	Copy assignment operator.

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

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

PODSpan< const P >	getPrimitives () const noexcept
	Get the global primitive list (in leaf-traversal order).

PODSpan< P >	getPrimitives () noexcept
	Get the global primitive list for modification (in leaf-traversal order).

PODSpan< const Node >	getNodes () const noexcept
	Get the flat node array (depth-first pre-order, root at index 0).

PackedBVH	rebasedView (const Pool &a_pool) const noexcept
	Produce a copy of this BVH that resolves against `a_pool`.

PackedBVH	deepCopy (Pool &a_dstPool) const
	Duplicate this BVH's storage into `a_dstPool`.

const BV &	getBoundingVolume () const noexcept
	Get the bounding volume of the root node.

BV	getBoundingVolume (const Node &a_node) const noexcept
	Get the bounding volume of one of this BVH's nodes.

T	getDistanceToBoundingVolume2 (const Node &a_node, const Vec3T< T > &a_point) const noexcept
	Get the squared distance from `a_point` to one of this BVH's nodes' bounding volume.

T	getDistanceToChildBoundingVolume2 (const Node &a_parent, size_t a_k, const Vec3T< T > &a_point) const noexcept
	Get the squared distance from `a_point` to the bounding volume of child `a_k` of an interior node.

BV	computeBoundingVolume () const noexcept
	Compute and return the bounding volume of this BVH.

template<class Query , class State , class LeafEvaluator , class BoundFn , class VisitFn = DescendAll, class Order = NearestFirst>
void	traverse (const Query &a_query, State &a_state, LeafEvaluator &&a_leaf, BoundFn &&a_bound, VisitFn &&a_visit=DescendAll(), Order a_order=Order()) const noexcept
	Walk the tree with a query, depth first: the general traversal.

template<class BVConstructor >
void	refit (const BVConstructor &a_bvConstructor)
	Refit every node's bounding volume in place after the primitives have moved.

void *	base () noexcept
	The base address this object's arrays are offsets from; see PoolHandle::base().

const void *	base () const noexcept
	The base address this object's arrays are offsets from; see PoolHandle::base().

Public Member Functions inherited from EBGeometry::PoolHandle
PoolLocation	location () const noexcept
	Where this handle's arrays live.

bool	isAttachedTo (const Pool &a_pool) const noexcept
	Check whether this handle's arrays were reserved from `a_pool`.

Static Public Member Functions
static BVH::ConstructionOptions	defaultConstructionOptions () noexcept
	The leaf-size settings build() uses when it is given none.

static PackedBVH	build (Pool &a_pool, std::vector< std::pair< P, BV > > a_primsAndBVs, BVH::Construction a_construction, const BVH::ConstructionOptions &a_options=defaultConstructionOptions())
	Build directly from a flat primitive list with one of the preset methods.

template<class S = SFC::Morton>
static PackedBVH	buildBottomUp (Pool &a_pool, std::vector< std::pair< P, BV > > a_primsAndBVs, size_t a_targetLeafSize)
	Build directly from a flat primitive list along a space-filling curve, without ever building a TreeBVH.

static PackedBVH	buildTopDown (Pool &a_pool, std::vector< std::pair< P, BV > > a_primsAndBVs, const BVH::Partitioner< P, BV, K > &a_partitioner, const BVH::LeafPredicate< T, P, BV, K > &a_stopCrit)
	Build directly from a flat primitive list via top-down (optionally SAH) recursive partitioning, without ever building a TreeBVH.

static PackedBVH	buildTopDown (Pool &a_pool, std::vector< std::pair< P, BV > > a_primsAndBVs, const BVH::Partitioner< P, BV, K > &a_partitioner)
	Build directly from a primitive list, top-down, with DefaultLeafPredicate.

static PackedBVH	buildClusterSAH (Pool &a_pool, std::vector< std::pair< P, BV > > a_primsAndBVs, BVH::ClusterSpec a_spec)
	Build directly via ClusterSAH: cluster primitives, then SAH over the clusters.

static constexpr size_t	traversalStackDepth () noexcept
	Traversal stack size, in entries, for the current compilation pass.

Static Public Attributes
static constexpr uint32_t	RootBoxSlot = UINT32_MAX
	The box slot of the root, which has no parent row: its box is the BVH's own.

Additional Inherited Members
Protected Member Functions inherited from EBGeometry::PoolHandle
	PoolHandle () noexcept=default
	An unset location; the first reservation attaches it.

	PoolHandle (const PoolLocation &a_location) noexcept
	Adopt a location, as a handle rebuilt from a stored layout does.

	PoolHandle (const PoolHandle &) noexcept=default
	Copy a handle, as a derived handle's copy does.

	PoolHandle (PoolHandle &&) noexcept=default
	Move a handle; the same as a copy.

PoolHandle &	operator= (const PoolHandle &) noexcept=default
	Copy-assign a handle, as a derived handle's assignment does.

PoolHandle &	operator= (PoolHandle &&) noexcept=default
	Move-assign a handle; the same as a copy.

	~PoolHandle () noexcept=default
	Destructor; protected, since a PoolHandle exists only as the base of a handle.

void *	base () noexcept
	The base address this handle's offsets resolve against; see PoolLocation::base().

const void *	base () const noexcept
	The base address this handle's offsets resolve against, for read-only access.

void	attach (const Pool &a_pool, const char *a_who) noexcept
	Follow `a_pool`, as the first reservation does; see PoolLocation::attach().

PoolLocation	rebasedLocation (const Pool &a_pool, uint64_t a_endByte, const char *a_who) const noexcept
	The location of this handle's arrays in another pool of its mirror chain; see PoolLocation::rebasedOnto().

void	setLocation (const PoolLocation &a_location) noexcept
	Replace the location, for a view or a copy made by a derived handle.

Detailed Description

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

Forward declaration of the linearised BVH, defined below.

Linearised, AABB-backed BVH with SIMD-accelerated traversal.

PackedBVH is the runtime query class. It stores a flat depth-first array of Node structs, a contiguous primitive list, one SoA row of child boxes per interior node (what the SIMD child tests read), and the root's box. Every box is stored once, in its parent's row; a node holds no box of its own.

Instances are built directly from a list of (primitive, bounding volume) pairs with build(), buildTopDown(), buildBottomUp() or buildClusterSAH(), by packing a TreeBVH with TreeBVH::pack() (same primitive type) or TreeBVH::packWith() (type-converting pack), or by adopting a node array built elsewhere.

PackedBVH imposes no interface requirement on P by itself – it holds primitives opaquely and only ever hands their range back to a caller-supplied leaf callback of traverse(). Nearest-surface (signed-distance-style) queries are not a PackedBVH member; callers build their own thin wrapper around traverse() with a query type (PointQuery for a point, RayQuery for a ray, or their own), supplying whatever primitive interface their own query needs.

The query type tests a node's K child boxes, read from the parent's SoA row in one pass. For PointQuery the SIMD paths are selected at compile time (BVH::QueryDetail::pointDistances2()):

K==4, T==float → SSE4.1 (__m128)
K==4, T==double → AVX (__m256d)
K==8, T==float → AVX (__m256)
K==8, T==double → AVX-512F (__m512d), or AVX (two __m256d passes) without AVX-512F
K==16, T==float → AVX-512F (__m512) All other combinations, and device compilation, use a scalar loop. RayQuery's slab test runs on SIMD::Pack lanes where a register's width divides K.

Primitives are stored by value, inline in the flat array: no per-primitive heap allocation and no pointer chase on a leaf visit. P must therefore be a self-contained, trivially copyable value type – a prerequisite for mirroring the whole BVH into a device address space with a byte copy. That rules out a polymorphic primitive: a BVH over primitives of different types (a CSG union of a mesh and a sphere, say) needs the runtime dispatch of the tape. A primitive that itself lives in a Pool, such as a TriMeshSDF inside a BVHUnion, is stored as its layout and paired with this BVH's location() when it is evaluated; storing the handle itself is a compile error (see PoolHandle). TreeBVH is unaffected by any of this – it always stores primitives as shared_ptr.

Template Parameters

T	Floating-point precision.
P	Primitive type.
K	BVH branching factor.

Constructor & Destructor Documentation

◆ PackedBVH() [1/6]

template<class T , class P , size_t K>

EBGeometry::BVH::PackedBVH< T, P, K >::PackedBVH	(	const Layout &	a_layout,
		const PoolLocation &	a_location
	)

inlinenoexcept

Rebuild a handle from a stored layout and the location of the pool that holds it.

How an outer pool-resident object evaluates a BVH it stores as a layout: it pairs the layout with its own location. a_location must belong to the pool the layout was reserved from, or to a mirror of it; nothing is checked, since a device has no pool to check against.

Parameters

[in]	a_layout	The BVH's arrays.
[in]	a_location	Where they live.

◆ PackedBVH() [2/6]

template<class T , class P , size_t K>

EBGeometry::BVH::PackedBVH< T, P, K >::PackedBVH	(	Pool &	a_pool,
		const TreeBVH< T, P, BV, K > &	a_tree
	)

inline

Construct by packing a TreeBVH (identity primitive type).

Walks the tree depth-first into host-side node, box and primitive arrays, then copies them into the pool and builds the SIMD box rows (as every build does). The source tree must have been built with BV == AABBT<T>; bounding volumes are reused without conversion.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive this object.
[in]	a_tree	Source tree.

◆ PackedBVH() [3/6]

template<class T , class P , size_t K>

template<class Q , class Converter >

EBGeometry::BVH::PackedBVH< T, P, K >::PackedBVH	(	Pool &	a_pool,
		const TreeBVH< T, Q, BV, K > &	a_tree,
		Converter &&	a_converter
	)

inline

Construct by packing a TreeBVH with primitive-type conversion.

The source tree holds primitives of type Q; the packed BVH holds primitives of type P. The most common reason for this mismatch is an SoA packing step: a tree built over individual triangles (Q = Triangle<T>) can be repacked into a BVH whose leaves hold SIMD-width groups (P = TriangleAoSoA<T, W>, as TriMeshSDF does), enabling vectorized distance evaluation at every leaf visit.

The converter is called once per leaf of the source tree and must return a std::vector<P> containing all target primitives for that leaf:

a_converter(leafPrims, offset, count) → std::vector<P>

where leafPrims is the leaf's PrimitiveList<Q>, offset is the index of the leaf's first primitive within leafPrims (always 0U, since the whole leaf list is passed), and count is the number of primitives in the leaf. All returned vectors are appended to one contiguous buffer, which is then copied into this PackedBVH's pool-backed primitive array.

The source tree must have been built with BV == AABBT<T>; bounding volumes are reused without conversion.

Template Parameters

Q	Source primitive type stored in the source tree.
Converter	Callable: (PrimitiveList<Q>, uint32_t offset, uint32_t count) → std::vector<P>.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive this object.
[in]	a_tree	Source tree.
[in]	a_converter	Leaf-conversion function.

◆ PackedBVH() [4/6]

template<class T , class P , size_t K>

EBGeometry::BVH::PackedBVH< T, P, K >::PackedBVH	(	Pool &	a_pool,
		const std::vector< Node > &	a_linearNodes,
		const std::vector< BV > &	a_nodeBoxes,
		const std::vector< P > &	a_primitives
	)

inline

Adopt a node array, its boxes and a primitive array built elsewhere.

For a specialized builder that produces the flat representation itself – e.g. PointCloudBVH, which runs its own index-based point-cloud build – rather than going through a TreeBVH or a list of (primitive, bounding volume) pairs. The arrays are copied into a_pool and the SIMD box rows are built from the boxes, exactly as for every other constructor.

The node array must be a depth-first pre-order flattening with the root at index 0: every interior node's K children lie strictly after it and inside the array, and every leaf's primitive range lies inside a_primitives. refit() and the traversal-depth bound both rely on that shape. It is checked by requireWellFormed(), always on rather than as an EBGEOMETRY_EXPECT, because a malformed array would otherwise surface as an out-of-bounds read in Release; an empty node array (an empty BVH) is accepted only with an empty primitive array.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive this object.
[in]	a_linearNodes	Flattened node array (copied into the pool). A node's box row and box slot are assigned here, whatever the array held.
[in]	a_nodeBoxes	The box of every node, indexed like `a_linearNodes:` a node does not store its own box, so the boxes are passed alongside. Copied into the SIMD rows and the root box.
[in]	a_primitives	Global primitive list in leaf-traversal order (copied into the pool).

◆ ~PackedBVH()

template<class T , class P , size_t K>

EBGeometry::BVH::PackedBVH< T, P, K >::~PackedBVH ( )

inlinedefault

Destructor.

Not virtual: PackedBVH is final and is not used polymorphically. A class that needs a BVH over its own payload holds one by value instead – see PointCloudBVH.

◆ PackedBVH() [5/6]

template<class T , class P , size_t K>

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

default

Copy constructor.

Copies the descriptor only: m_linearNodes, m_primitives, m_childAabbSoA and m_rootBox are PODVector handles into pool memory, so the copy resolves against the same pool storage as the original rather than owning its own. Nothing is duplicated, and a refit() through either object is seen by both. Use deepCopy() for genuinely independent storage.

Parameters

[in] a_other Other instance to copy.

◆ PackedBVH() [6/6]

template<class T , class P , size_t K>

EBGeometry::BVH::PackedBVH< T, P, K >::PackedBVH ( PackedBVH< T, P, 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

◆ base() [1/2]

template<class T , class P , size_t K>

const void * EBGeometry::PoolHandle::base ( ) const

inlinenoexcept

The base address this object's arrays are offsets from; see PoolHandle::base().

Returns: The base address: const void* for a const object, void* otherwise.

◆ base() [2/2]

template<class T , class P , size_t K>

void * EBGeometry::PoolHandle::base ( )

inlinenoexcept

The base address this object's arrays are offsets from; see PoolHandle::base().

Returns: The base address: const void* for a const object, void* otherwise.

◆ build()

template<class T , class P , size_t K>

static PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::build	(	Pool &	a_pool,
		std::vector< std::pair< P, BV > >	a_primsAndBVs,
		BVH::Construction	a_construction,
		const BVH::ConstructionOptions &	a_options = `defaultConstructionOptions()`
	)

inlinestatic

Build directly from a flat primitive list with one of the preset methods.

Dispatches to buildTopDown() (SAH, CentroidSplit, MidpointSplit, stopping at a_options.maxLeafSize primitives per leaf), buildBottomUp() (Morton, Nested, Hilbert, aiming for a_options.targetLeafSize) or buildClusterSAH() (a_options.cluster). The chosen method reads only its own field of a_options, and a zero setting for it aborts.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive the result.
[in]	a_primsAndBVs	Primitives and their bounding volumes, taken by value (must be non-empty).
[in]	a_construction	Preset construction method.
[in]	a_options	Leaf-size settings.

Returns: The packed BVH.

◆ buildBottomUp()

template<class T , class P , size_t K>

template<class S = SFC::Morton>

static PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::buildBottomUp	(	Pool &	a_pool,
		std::vector< std::pair< P, BV > >	a_primsAndBVs,
		size_t	a_targetLeafSize
	)

inlinestatic

Build directly from a flat primitive list along a space-filling curve, without ever building a TreeBVH.

Bypasses TreeBVH entirely: no per-node shared_ptr<TreeBVH> allocation, and no per-primitive shared_ptr allocation either. Primitives are sorted along the space-filling curve S (same normalization as TreeBVH::bottomUpSortAndPartition(), via SFC::computeBins()), then split into consecutive leaves and merged bottom-up into a K-ary tree.

Every interior node has exactly K children, and such a tree has a leaf count L with L = 1 (mod K - 1). The build takes the smallest such L that keeps every leaf at or below a_targetLeafSize primitives, and splits the primitives as evenly as possible, so leaf sizes differ by at most one. When that L would exceed the number of primitives, it takes the largest such L below it instead, and leaves may then hold slightly more than the target (for example, five primitives with K = 4 and a target of one give four leaves). When a level of the merge has a node count that is not a multiple of K, the remainder is carried up to the next level. Every node has exactly one parent, so a traversal reaches each primitive exactly once.

Template Parameters

S	Space-filling curve type (e.g. SFC::Morton, SFC::Nested), given explicitly: `PackedBVH::buildBottomUp<SFC::Nested>(pool, prims, 4)`. Defaults to SFC::Morton.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive the result.
[in]	a_primsAndBVs	Primitives and their bounding volumes, taken by value (a sink parameter the caller can std::move in) – never requires shared_ptr-wrapping.
[in]	a_targetLeafSize	Target (maximum, where the leaf-count rule above allows it) number of primitives per leaf. Must be > 0.

Returns: The packed BVH.

◆ buildClusterSAH()

template<class T , class P , size_t K>

static PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::buildClusterSAH	(	Pool &	a_pool,
		std::vector< std::pair< P, BV > >	a_primsAndBVs,
		BVH::ClusterSpec	a_spec
	)

inlinestatic

Build directly via ClusterSAH: cluster primitives, then SAH over the clusters.

A single-threaded build that gets close to full-SAH tree quality at a fraction of the build cost, by shrinking what SAH has to partition. In two passes, both keeping P by value (no shared_ptr anywhere): (1) group the primitives into buckets of at most a_spec.maxClusterSize each, using a cheap density-adaptive midpoint subdivision that stops as soon as a bucket is small enough – so buckets are spatially tight and follow the primitive density (robust on surface/clustered data, where a fixed Cartesian grid would overcrowd); (2) run binned SAH top-down over the buckets (their bounding boxes) to build the flat node array, with each leaf holding one or a few buckets' primitives. SAH thus partitions ~N/maxClusterSize boxes rather than all N primitives – the source of the speedup. 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.
[in]	a_primsAndBVs	Primitives and their bounding volumes, taken by value (a sink parameter the caller can std::move in) – never requires shared_ptr-wrapping.
[in]	a_spec	Clustering configuration (bucket size). See ClusterSpec.

Returns: The packed BVH.

◆ buildTopDown() [1/2]

template<class T , class P , size_t K>

static PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::buildTopDown	(	Pool &	a_pool,
		std::vector< std::pair< P, BV > >	a_primsAndBVs,
		const BVH::Partitioner< P, BV, K > &	a_partitioner
	)

inlinestatic

Build directly from a primitive list, top-down, with DefaultLeafPredicate.

Same as the four-argument buildTopDown() with a_stopCrit = DefaultLeafPredicate. This overload stands in for a default argument, which would make this header depend on the partitioners in EBGeometry_TreeBVH.hpp.

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive the result.
[in]	a_primsAndBVs	Primitives and their bounding volumes.
[in]	a_partitioner	Partitioning function.

Returns: The packed BVH.

◆ buildTopDown() [2/2]

template<class T , class P , size_t K>

static PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::buildTopDown	(	Pool &	a_pool,
		std::vector< std::pair< P, BV > >	a_primsAndBVs,
		const BVH::Partitioner< P, BV, K > &	a_partitioner,
		const BVH::LeafPredicate< T, P, BV, K > &	a_stopCrit
	)

inlinestatic

Build directly from a flat primitive list via top-down (optionally SAH) recursive partitioning, without ever building a TreeBVH.

Reuses the existing (shared_ptr-based) Partitioner/LeafPredicate machinery – BVCentroidPartitioner, BinnedSAHPartitioner, PrimitiveCentroidPartitioner, or any caller-supplied one – exactly as TreeBVH::topDownSortAndPartition() does, but writes nodes directly into the flat node array in depth-first pre-order as the recursion unwinds, instead of building a persistent, shared_ptr<TreeBVH>-linked tree first. Unlike buildBottomUp(), no relayout pass is needed here: top-down recursion visits the root before its children, matching PackedBVH's "root at index 0" invariant for free.

This still shared_ptr-wraps each primitive once up front (needed to reuse the existing Partitioner/LeafPredicate signatures, which operate on PrimAndBVList), and a lightweight, stack-local TreeBVH is constructed (and immediately discarded) at every split purely to evaluate the LeafPredicate and read off its primitive list – exactly the same primitive-handle copying TreeBVH::topDownSortAndPartition() already does at every node. What this build avoids is the persistent, heap-allocated shared_ptr<TreeBVH> node kept alive for the tree's lifetime at every level – measured as the dominant cost of the traditional build-then-pack() path (see the "Direct construction" section of the Sphinx docs).

Parameters

[in,out]	a_pool	Pool the packed arrays are reserved from; must outlive the result.
[in]	a_primsAndBVs	Primitives and their bounding volumes, taken by value (a sink parameter the caller can std::move in) – never requires shared_ptr-wrapping by the caller.
[in]	a_partitioner	Partitioning function. Divides a (primitive, BV) list into K non-empty sub-lists (an empty one aborts; see TreeBVH::topDownSortAndPartition()), e.g. BinnedSAHPartitioner for an SAH build.
[in]	a_stopCrit	Stop function. Returns true when a node should become a leaf. The overload without it uses DefaultLeafPredicate.

Returns: The packed BVH.

◆ computeBoundingVolume()

template<class T , class P , size_t K>

BV EBGeometry::BVH::PackedBVH< T, P, K >::computeBoundingVolume ( ) const

inlinenoexcept

Compute and return the bounding volume of this BVH.

Identical to getBoundingVolume(), but returns by value under the computeBoundingVolume() name other bounded objects use (BVHUnion forwards to it), and returns the empty (inverted) box for an empty BVH instead of reading a root that does not exist.

Returns: Root node bounding volume.

◆ deepCopy()

template<class T , class P , size_t K>

PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::deepCopy ( Pool & a_dstPool ) const

inline

Duplicate this BVH's storage into a_dstPool.

The copy constructor copies descriptors only, leaving both objects resolving against the same pool memory. This is the operation that gives genuinely independent storage.

Parameters

[in,out] a_dstPool Pool to reserve the copy's arrays from.

Returns: A BVH with the same structure, backed by a_dstPool.

◆ defaultConstructionOptions()

template<class T , class P , size_t K>

static BVH::ConstructionOptions EBGeometry::BVH::PackedBVH< T, P, K >::defaultConstructionOptions ( )

inlinestaticnoexcept

The leaf-size settings build() uses when it is given none.

A top-down leaf holds at most K - 1 primitives (as DefaultLeafPredicate), a space-filling-curve build aims for K per leaf, and ClusterSAH uses the default ClusterSpec. Start from these to change one method's setting; see ConstructionOptions.

Returns: The default options.

◆ getBoundingVolume() [1/2]

template<class T , class P , size_t K>

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

inlinenoexcept

Get the bounding volume of the root node.

An empty BVH has no root, so calling this on one aborts, in every build; computeBoundingVolume() handles that case.

Returns: Reference to the root node's bounding volume.

◆ getBoundingVolume() [2/2]

template<class T , class P , size_t K>

BV EBGeometry::BVH::PackedBVH< T, P, K >::getBoundingVolume ( const Node & a_node ) const

inlinenoexcept

Get the bounding volume of one of this BVH's nodes.

A node does not store its own box. Every box but the root's is stored once, in the parent's row of the SIMD box array, and the node's box slot says where; the root's box is the BVH's own. a_node must be a node of this BVH, e.g. an element of getNodes() or the node a traverse() callback is given; a node of another BVH is caught only with assertions on.

Parameters

[in] a_node A node of this BVH.

Returns: The node's bounding volume.

◆ getDistanceToBoundingVolume2()

template<class T , class P , size_t K>

T EBGeometry::BVH::PackedBVH< T, P, K >::getDistanceToBoundingVolume2	(	const Node &	a_node,
		const Vec3T< T > &	a_point
	)		const

inlinenoexcept

Get the squared distance from a_point to one of this BVH's nodes' bounding volume.

The same box as getBoundingVolume(a_node), without assembling it. For a caller-written scalar branch-and-bound that compares against a squared pruning bound (e.g. PointCloudBVH's seeded single-nearest search). traverse() with a PointQuery tests all K children at once instead. a_node must be a node of this BVH, as for getBoundingVolume(a_node); a node of another BVH is caught only with assertions on.

Parameters

[in]	a_node	A node of this BVH.
[in]	a_point	Query point.

Returns: Squared distance to the box, or zero if a_point is inside it.

◆ getDistanceToChildBoundingVolume2()

template<class T , class P , size_t K>

T EBGeometry::BVH::PackedBVH< T, P, K >::getDistanceToChildBoundingVolume2	(	const Node &	a_parent,
		size_t	a_k,
		const Vec3T< T > &	a_point
	)		const

inlinenoexcept

Get the squared distance from a_point to the bounding volume of child a_k of an interior node.

The same as getDistanceToBoundingVolume2() on that child, but read from a_parent's row of the SIMD box array, where the child's box is stored, without loading the child node to find it. For a caller-written scalar descent that tests a node's children one at a time (e.g. PointCloudBVH's seeded single-nearest search). a_parent must be an interior node of this BVH.

Parameters

[in]	a_parent	An interior node of this BVH.
[in]	a_k	The child's position among `a_parent's` children, below K.
[in]	a_point	Query point.

Returns: Squared distance to the child's box, or zero if a_point is inside it.

◆ getNodes()

template<class T , class P , size_t K>

PODSpan< const Node > EBGeometry::BVH::PackedBVH< T, P, K >::getNodes ( ) const

inlinenoexcept

Get the flat node array (depth-first pre-order, root at index 0).

Read-only: a node's child and primitive offsets define the tree's shape, which is fixed at build time. For a class that holds a PackedBVH and walks it with its own traversal rather than through traverse() – PointCloudBVH's seeded self-query, for instance. Same lifetime caveat as getPrimitives(): the span must not outlive the next Pool::reserve.

Returns: Span over the node array; empty for an empty BVH.

◆ getPrimitives() [1/2]

template<class T , class P , size_t K>

PODSpan< const P > EBGeometry::BVH::PackedBVH< T, P, K >::getPrimitives ( ) const

inlinenoexcept

Get the global primitive list (in leaf-traversal order).

The returned span is a resolved address into pool memory. It must not outlive the next Pool::reserve on the owning pool, which may move the block; re-obtain it rather than caching it across a build step.

Returns: Span over m_primitives.

◆ getPrimitives() [2/2]

template<class T , class P , size_t K>

PODSpan< P > EBGeometry::BVH::PackedBVH< T, P, K >::getPrimitives ( )

inlinenoexcept

Get the global primitive list for modification (in leaf-traversal order).

The packed BVH owns its primitives outright – packing copies them out of whatever they were built from – so this is the only way to move a packed geometry in place. Mutating a primitive's position invalidates every node bounding volume that encloses it, so a caller that moves primitives must follow up with refit() before querying again.

Note that changing which leaf a primitive belongs to is not supported: the node array's primitive ranges are fixed at build time, and refit() only recomputes bounding volumes. Moving primitives far enough to want a different partitioning needs a rebuild.

Same lifetime caveat as the const overload: the span must not outlive the next Pool::reserve.

Returns: Mutable span over m_primitives.

◆ layout()

template<class T , class P , size_t K>

Layout EBGeometry::BVH::PackedBVH< T, P, K >::layout ( ) const

inlinenoexcept

The BVH's arrays without its location, for storing it inside another pool-resident object.

Returns: The layout.

◆ operator=() [1/2]

template<class T , class P , size_t K>

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

default

Copy assignment operator.

Parameters

[in] a_other Other instance to copy.

Returns: Reference to *this.

◆ operator=() [2/2]

template<class T , class P , size_t K>

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

defaultnoexcept

Move assignment operator.

Parameters

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

Returns: Reference to *this.

◆ rebasedView()

template<class T , class P , size_t K>

PackedBVH EBGeometry::BVH::PackedBVH< T, P, K >::rebasedView ( const Pool & a_pool ) const

inlinenoexcept

Produce a copy of this BVH that resolves against a_pool.

The one sanctioned crossing, mirroring DCEL::MeshT::rebasedView(). Mirror the pool first, then rebase, then copy the returned value into a kernel – never copy a host-resident BVH into a kernel and try to repair it afterwards.

Pool devicePool = Pool::mirror(hostPool, deviceMemoryResource());
const auto deviceBVH = bvh->rebasedView(devicePool);
myKernel<<<blocks, threads>>>(deviceBVH, ...);

A host-to-host mirror is supported too and follows the target's control block instead of snapshotting its base. The rules are DCEL::MeshT::rebasedView()'s (see PoolLocation::rebasedOnto()).

Parameters

[in] a_pool Pool to rebase onto: this BVH's own pool or one in its mirror chain.

Returns: A copy of this BVH resolving against a_pool.

◆ refit()

template<class T , class P , size_t K>

template<class BVConstructor >

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

inline

Refit every node's bounding volume in place after the primitives have moved.

The flat-array counterpart of TreeBVH::refit(): keeps the node array, the primitive array, and every leaf's primitive range exactly as they are, recomputing only the bounding volumes. Because m_linearNodes is a depth-first pre-order flattening (root at index 0, every child at a higher index than its parent), a single reverse sweep over the array refits children before parents with no recursion or explicit stack: each leaf's box becomes the union of its primitives' boxes (recomputed via a_bvConstructor), and each interior node's box the union of its K children's freshly-refitted boxes. Each box is written where it is stored, in its parent's SIMD row (the root's in the BVH), so every traversal sees the new boxes, and nothing is allocated.

Same use and caveats as TreeBVH::refit(): cheap per-frame maintenance for a geometry whose primitives shift without migrating between leaves, and not a substitute for a rebuild once a deformation is large enough to degrade the tree. a_bvConstructor receives each primitive (drawn from the primitive array) and must return its current bounding volume.

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.

◆ traversalStackDepth()

template<class T , class P , size_t K>

static constexpr size_t EBGeometry::BVH::PackedBVH< T, P, K >::traversalStackDepth ( )

inlinestaticconstexprnoexcept

Traversal stack size, in entries, for the current compilation pass.

The bound traverse() sizes its stack by: one entry per level below the root of a tree HostTraversalDepth levels deep in a host pass, and DeviceTraversalDepth levels in a device pass. Every BVH is checked against the host depth when it is built, and against the device depth when rebasedView() produces a device view, so a caller's own traversal that keeps one entry per interior node on the path from the root to the node it visits – the siblings still to visit at that level – cannot overflow a stack of this many entries.

Returns: Number of stack entries.

◆ traverse()

template<class T , class P , size_t K>

template<class Query , class State , class LeafEvaluator , class BoundFn , class VisitFn = DescendAll, class Order = NearestFirst>

void EBGeometry::BVH::PackedBVH< T, P, K >::traverse	(	const Query &	a_query,
		State &	a_state,
		LeafEvaluator &&	a_leaf,
		BoundFn &&	a_bound,
		VisitFn &&	a_visit = `DescendAll()`,
		Order	a_order = `Order()`
	)		const

inlinenoexcept

Walk the tree with a query, depth first: the general traversal.

The caller chooses what is tracked through the tree (a_query: a PointQuery, a RayQuery, or a query type of their own; see EBGeometry_BVHQuery.hpp), what is remembered between leaves (a_state), what happens at a leaf (a_leaf), how near a node must be to be entered (a_bound), what to do with a node before entering it (a_visit), and the order a node's children are visited in (a_order).

At each interior node the query gives the K children their keys in one pass (Query::keys(), SIMD on the host). A child is entered if its key is <= the bound and, for a floating-point key, not +infinity (which means the query cannot reach it, e.g. a ray that misses its box; so a bound that starts at +infinity does not let the walk into every box a ray misses); those are visited in the order a_order gives, the first at once and the rest from a stack. The bound is read again at every node, so a leaf visited anywhere earlier tightens the pruning of every node after it. When the walk returns to a level it recomputes the next child's key (Query::key(row, k), bit for bit the same) and compares it with the current bound; under NearestFirst the first child out of bound drops the rest of the level.

Every node about to be entered (the root, an interior node, a leaf), once it has passed the bound, is handed to a_visit with its index, the node and its key. Returning false skips it and its subtree; the callback may update the state first, for instance to account for the whole subtree at once from the caller's own per-node data. The default, DescendAll, always descends and compiles away.

The stack keeps one entry per level (the node and the order of the children still to visit), sized from traversalStackDepth(), so it is a fixed array on a device. An empty BVH visits nothing.

One query per walk: QueryLanes<Query>::value must be 1.

Template Parameters

Query	Query type: keys(row), key(row, k), key(box); see BVH::PointQuery.
State	The caller's search state.
LeafEvaluator	Callable as (State&, size_t offset, size_t count) -> void: scans primitives [offset, offset + count) of getPrimitives() and updates the state.
BoundFn	Callable as (const State&) -> Key: the current bound. A child whose key is above it is not entered; a bound below every key (e.g. -infinity) ends the walk.
VisitFn	Callable as (State&, uint32_t nodeIndex, const Node&, const Key&) -> bool, or DescendAll.
Order	NearestFirst (default), FarthestFirst, AsStored (first slot first), or a comparator (keyA, keyB) -> bool or (keyA, nodeIndexA, keyB, nodeIndexB) -> bool, true when the first child is to be visited before the second.

Parameters

[in]	a_query	The query.
[in,out]	a_state	The search state.
[in]	a_leaf	Leaf callback.
[in]	a_bound	Bound callback.
[in]	a_visit	Visit callback.
[in]	a_order	Visit order.

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

Source/EBGeometry_PackedBVH.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ PackedBVH() [1/6]

◆ PackedBVH() [2/6]

◆ PackedBVH() [3/6]

◆ PackedBVH() [4/6]

◆ ~PackedBVH()

◆ PackedBVH() [5/6]

◆ PackedBVH() [6/6]

Member Function Documentation

◆ base() [1/2]

◆ base() [2/2]

◆ build()

◆ buildBottomUp()

◆ buildClusterSAH()

◆ buildTopDown() [1/2]

◆ buildTopDown() [2/2]

◆ computeBoundingVolume()

◆ deepCopy()

◆ defaultConstructionOptions()

◆ getBoundingVolume() [1/2]

◆ getBoundingVolume() [2/2]

◆ getDistanceToBoundingVolume2()

◆ getDistanceToChildBoundingVolume2()

◆ getNodes()

◆ getPrimitives() [1/2]

◆ getPrimitives() [2/2]

◆ layout()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ rebasedView()

◆ refit()

◆ traversalStackDepth()

◆ traverse()