Forward declaration of the linearised BVH. Needed so that TreeBVH::pack() and TreeBVH::packWith() can name their return types before PackedBVH is fully defined. More...
#include <EBGeometry_BVH.hpp>
Classes | |
| struct | ChildAABBSoA |
| SoA layout of K children's AABBs for a single interior node. 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. | |
| using | StorageType = typename StoragePolicy::StorageType |
| Storage representation of one entry in the primitive array, as determined by StoragePolicy (std::shared_ptr<const P> for the default SharedPtrStorage. | |
Public Member Functions | |
| PackedBVH ()=delete | |
| Deleted default constructor. Use TreeBVH::pack() or TreeBVH::packWith() to construct. | |
| PackedBVH (const TreeBVH< T, P, BV, K > &a_tree) | |
| Construct by packing a TreeBVH (identity primitive type). | |
| template<class Q , class Converter > | |
| PackedBVH (const TreeBVH< T, Q, BV, K > &a_tree, Converter &&a_converter) | |
| Construct by packing a TreeBVH with primitive-type conversion. | |
| template<class S = SFC::Morton> | |
| PackedBVH (std::vector< std::pair< P, BV > > a_primsAndBVs, size_t a_targetLeafSize, S a_sfc=S{}) | |
| Construct directly from a flat primitive list, without ever building a TreeBVH. | |
| PackedBVH (std::vector< std::pair< P, BV > > a_primsAndBVs, const BVH::Partitioner< P, BV, K > &a_partitioner=BVCentroidPartitioner< T, P, BV, K >, const BVH::LeafPredicate< T, P, BV, K > &a_stopCrit=DefaultLeafPredicate< T, P, BV, K >) | |
| Construct directly from a flat primitive list via top-down (optionally SAH) recursive partitioning, without ever building a TreeBVH. | |
| PackedBVH (std::vector< std::pair< P, BV > > a_primsAndBVs, BVH::ClusterSpec a_spec) | |
| Construct directly via ClusterSAH: cluster primitives, then SAH over the clusters. | |
| ~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. | |
| const std::vector< StorageType > & | getPrimitives () const noexcept |
| Get the global primitive list (in leaf-traversal order). | |
| const BV & | getBoundingVolume () const noexcept |
| Get the bounding volume of the root node. | |
| BV | computeBoundingVolume () const noexcept |
| Compute and return the bounding volume of this BVH. | |
| template<class NodeKey > | |
| void | traverse (const BVH::PackedLeafEvaluator< P, StoragePolicy > &a_leafEvaluator, const BVH::PrunePredicate< Node, NodeKey > &a_prunePredicate, const BVH::PackedChildOrderer< NodeKey, K > &a_childOrderer, const BVH::NodeKeyFactory< Node, NodeKey > &a_nodeKeyFactory) const noexcept |
| Recursion-free BVH traversal using a vector-backed LIFO stack (depth-first order). | |
| template<class State , class LeafEvaluator , class PruneDistSquared > | |
| void | pruneTraverse (const Vec3T< T > &a_point, State &a_state, LeafEvaluator &&a_evalLeaf, PruneDistSquared &&a_pruneDist2) const noexcept |
| Generic SIMD-accelerated, distance-pruned traversal. | |
| template<class BVConstructor > | |
| void | refit (const BVConstructor &a_bvConstructor) |
| Refit every node's bounding volume in place after the primitives have moved. | |
Protected Member Functions | |
| PackedBVH (std::vector< Node > &&a_linearNodes, std::vector< StorageType > &&a_primitives) noexcept | |
| Adopt pre-built node and primitive arrays, then finalize the SoA child-AABB layout. | |
| void | buildSoA () |
| Populate m_childAabbSoA from the completed m_linearNodes array. | |
Protected Attributes | |
| std::vector< Node > | m_linearNodes |
| Flat depth-first node array. | |
| std::vector< StorageType > | m_primitives |
| Global primitive list in leaf-traversal order. | |
| std::vector< ChildAABBSoA > | m_childAabbSoA |
| Per-node SoA AABB cache used by the SIMD traversal in pruneTraverse(). | |
Detailed Description
class EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >
Forward declaration of the linearised BVH. Needed so that TreeBVH::pack() and TreeBVH::packWith() can name their return types before PackedBVH is fully defined.
Linearised, AABB-backed BVH with SIMD-accelerated traversal.
StoragePolicy defaults to SharedPtrStorage
, preserving today's exact behaviour for every existing 3-argument PackedBVH<T, P, K> instantiation.
PackedBVH is the runtime query class. It stores a flat depth-first array of Node structs, a contiguous primitive list, and a per-node SoA AABB cache that enables SIMD child tests.
Instances are obtained by calling TreeBVH::pack() (same primitive type) or TreeBVH::packWith<Q>(converter) (type-converting pack).
PackedBVH imposes no interface requirement on P by itself – it holds primitives opaquely and only ever hands them back to a caller-supplied callback (traverse()'s LeafEvaluator, or pruneTraverse()'s LeafEvaluator). Nearest-surface (signed-distance-style) queries are not a PackedBVH member; callers build their own thin wrapper around pruneTraverse(), supplying whatever primitive interface their own query needs.
SIMD paths are selected at compile time via if constexpr, in pruneTraverse():
- K==4, T==float → SSE4.1 (__m128)
- K==4, T==double → AVX (__m256d)
- K==8, T==float → AVX (__m256)
- K==8, T==double → AVX (two __m256d passes) All other combinations fall back to scalar traversal.
What StoragePolicy governs: purely the representation of PackedBVH's own primitive array (StorageType – std::shared_ptr<const P> by default, or a raw P with ValueStorage
). It has no effect on TreeBVH (always shared_ptr-based) or on tree construction/traversal – see SharedPtrStorage/ValueStorage above for the exact operations a storage policy provides.
- Template Parameters
-
T Floating-point precision. P Primitive type. K BVH branching factor. StoragePolicy Governs how the primitive array is stored (default: SharedPtrStorage
).
Member Typedef Documentation
◆ StorageType
| using EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >::StorageType = typename StoragePolicy::StorageType |
Storage representation of one entry in the primitive array, as determined by StoragePolicy (std::shared_ptr<const P> for the default SharedPtrStorage.
, or P itself for ValueStorage
).
Constructor & Destructor Documentation
◆ PackedBVH() [1/8]
|
inline |
Construct by packing a TreeBVH (identity primitive type).
Walks the tree depth-first, fills m_linearNodes and m_primitives directly, then builds the SoA AABB cache. The source tree must have been built with BV == AABBT<T>; bounding volumes are reused without conversion.
- Parameters
-
[in] a_tree Source tree.
◆ PackedBVH() [2/8]
|
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 = TriangleSoAT<T,W>), enabling vectorised 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:
where leafPrims is the leaf's PrimitiveList<Q>, offset is the index of the first primitive in the global list, and count is the number of primitives in the leaf. All returned vectors are stored contiguously in one buffer, which this PackedBVH's storage policy then materialises into its own primitive array – via aliased shared_ptr (no extra copies) for the default SharedPtrStorage
, or by taking ownership of the buffer directly for ValueStorage
.
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] a_tree Source tree. [in] a_converter Leaf-conversion function.
◆ PackedBVH() [3/8]
|
inline |
Construct directly from a flat primitive list, without ever building a TreeBVH.
Bypasses TreeBVH entirely: no per-node shared_ptr<TreeBVH> allocation, and (with StoragePolicy = ValueStorage
) 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 cut into leaves by one linear left-to-right scan at a_targetLeafSize – unlike TreeBVH::bottomUpSortAndPartition(), which derives a leaf count of K^floor(log_K(N)) purely from N and K, this lets the caller control leaf size directly.
Because the resulting leaf count generally isn't a power of K, the K-ary merge pads up to the next power of K by re-using the last real leaf's index in place of a missing child – so every interior node still has exactly K children (no change to Node's shape or to traverse()/ pruneTraverse(), which assume this), at the cost of that one leaf's primitives potentially being visited more than once by a query in the (bounded, rare) case where the real leaf count isn't already a power of K. This never duplicates primitive data, only (cheap) Node entries.
- Template Parameters
-
S Space-filling curve type (e.g. SFC::Morton, SFC::Nested). Defaults to SFC::Morton; a constructor template's own parameters cannot be explicitly specified the way a named function template's can (constructors have no name of their own to attach a template-argument list to), so a_sfcis a stateless tag value purely soScan be deduced from it – pass e.g.SFC::Nested{}to select a different curve, or omit it entirely for the default.
- Parameters
-
[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 regardless of this PackedBVH's StoragePolicy. [in] a_targetLeafSize Target number of primitives per leaf. Must be > 0. [in] a_sfc Unused tag value; see S.
◆ PackedBVH() [4/8]
|
inline |
Construct 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 m_linearNodes in depth-first pre-order as the recursion unwinds, instead of building a persistent, shared_ptr<TreeBVH>-linked tree first. Unlike the SFC-build constructor above, 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 constructor 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] 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, regardless of this PackedBVH's StoragePolicy. [in] a_partitioner Partitioning function. Divides a (primitive, BV) list into K sub-lists. Defaults to BVCentroidPartitioner; pass BinnedSAHPartitioner for an SAH build. [in] a_stopCrit Stop function. Returns true when a node should become a leaf. Defaults to DefaultLeafPredicate.
◆ PackedBVH() [5/8]
|
inline |
Construct 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. Disambiguated from the SFC-build constructor by the ClusterSpec parameter type.
- Parameters
-
[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 regardless of StoragePolicy. [in] a_spec Clustering configuration (bucket size). See ClusterSpec.
◆ ~PackedBVH()
|
inlinedefault |
Destructor.
Not virtual: PackedBVH is not intended to be subclassed or used polymorphically.
◆ PackedBVH() [6/8]
|
default |
Copy constructor.
Explicitly defaulted for documentation purposes: unlike TreeBVH, PackedBVH's members (m_linearNodes, m_primitives, m_childAabbSoA) are all owned value containers with no shared mutable substructure, so the implicitly-generated deep copy is correct and safe under both BVH::SharedPtrStorage (primitives are aliased shared_ptr, the same sharing model as TreeBVH) and BVH::ValueStorage (primitives are copied by value – safe as long as the primitive type's own copy constructor is complete; see DCEL::FaceT's copy-constructor documentation for a case where it deliberately is not, which is why MeshSDF never uses BVH::ValueStorage).
- Parameters
-
[in] a_other Other instance to copy.
◆ PackedBVH() [7/8]
|
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.
◆ PackedBVH() [8/8]
|
inlineprotectednoexcept |
Adopt pre-built node and primitive arrays, then finalize the SoA child-AABB layout.
Not part of the public API. It exists so a specialized builder in a derived class (e.g. PointCloudBVH, which fills the arrays with its own index-based build) can construct the packed representation directly, without going through a TreeBVH or a PrimAndBVList. The node array must be a valid depth-first pre-order flattening (root at index 0) referencing a_primitives.
- Parameters
-
[in] a_linearNodes Flattened node array (moved in). [in] a_primitives Global primitive list in leaf-traversal order (moved in).
Member Function Documentation
◆ buildSoA()
|
inlineprotected |
Populate m_childAabbSoA from the completed m_linearNodes array.
Called at the end of every constructor after m_linearNodes is fully built.
◆ computeBoundingVolume()
|
inlinenoexcept |
Compute and return the bounding volume of this BVH.
Identical to getBoundingVolume() but presents a getCentroid()-compatible interface, enabling PackedBVH to serve as a primitive in an outer TreeBVH hierarchy.
- Returns
- Root node bounding volume.
◆ getBoundingVolume()
|
inlinenoexcept |
Get the bounding volume of the root node.
- Returns
- Reference to the root node's bounding volume.
◆ getPrimitives()
|
inlinenoexcept |
Get the global primitive list (in leaf-traversal order).
- Returns
- Reference to m_primitives.
◆ operator=() [1/2]
|
default |
Copy assignment operator.
- Parameters
-
[in] a_other Other instance to copy.
- Returns
- Reference to *this.
◆ operator=() [2/2]
|
defaultnoexcept |
Move assignment operator.
- Parameters
-
[in,out] a_other Other instance to move from.
- Returns
- Reference to *this.
◆ pruneTraverse()
|
inlinenoexcept |
Generic SIMD-accelerated, distance-pruned traversal.
Same box-pruning strategy as traverse() above (skip subtrees already farther than the current best; visit the closest-looking child first), but the box-vs-point distance test is vectorised across all K children at once (if constexpr dispatch on (K, T); falls back to the generic traverse() above when no compiled ISA path matches), and the search itself is expressed through three caller-supplied pieces instead of four fixed callbacks. State is whatever the search remembers between leaf visits. LeafEvaluator is called only at leaves and is the sole place State may change. PruneDistSquared turns the current State into a squared-distance pruning bound; it is re-read fresh at every node visited (never cached), so a leaf visited anywhere earlier on the stack immediately tightens the pruning applied to nodes visited afterwards, regardless of which subtree it came from. Splitting the bound from the leaf scan like this is what lets a primitive with no notion of "signed distance" reuse the same SIMD box test – e.g. a nearest-neighbor search can track a plain running squared distance in State (no abs(), no sqrt anywhere in the hot path), while MeshSDF::signedDistance() and TriMeshSDF::signedDistance() track a signed value and square its magnitude for the bound. Both are ordinary instantiations of this one method.
- Note
- Only the pruning bound (
PruneDistSquared) is customisable; the per-child quantity it is compared against – Euclidean squared distance to a child's AABB – is not, since that is the one computation vectorised uniformly acrossKchildren, and branch-and-bound pruning is only sound if it is a true lower bound on the distance to anything inside that box. PackedBVH also hardcodes AABBT<T> as its sole bounding volume. See https://github.com/rmrsk/EBGeometry/issues/96 for a sketch of what generalizing this would look like, if that is ever needed.
- Template Parameters
-
State Caller-defined running search state, carried by reference through the whole traversal. LeafEvaluator Callable: (State&, size_t offset, size_t count) noexcept -> void. Scans primitives [offset, offset+count) and updates a_state in place. PruneDistSquared Callable: (const State&) noexcept -> T. Returns the current squared-distance pruning bound derived from a_state; a node farther than this (in squared distance) is pruned.
- Parameters
-
[in] a_point Query point. [in,out] a_state Running search state; mutated by a_evalLeaf, read by a_pruneDist2. [in] a_evalLeaf Leaf-visit callback. [in] a_pruneDist2 Pruning-bound callback.
◆ refit()
|
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. The per-node SoA AABB cache used by the SIMD traversal is rebuilt at the end, so pruneTraverse() stays consistent.
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 via the storage policy) 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.
◆ traverse()
|
inlinenoexcept |
Recursion-free BVH traversal using a vector-backed LIFO stack (depth-first order).
The traversal mirrors TreeBVH::traverse() in structure but works directly on the flat node array, using 32-bit indices instead of shared_ptr<const Node>. This halves the stack-entry size and avoids reference-count traffic on every push and pop.
The stack is a std::vector used as a LIFO queue via push_back/pop_back, pre-reserved to 64 entries to avoid reallocation for typical tree depths. It is seeded with node index 0 (the root) paired with a_nodeKeyFactory applied to the root node. On each iteration:
- Pop the back entry to obtain a (nodeIdx, nodeKey) pair.
- Look up the node at m_linearNodes[nodeIdx].
- Call
a_prunePredicate(node, nodeKey). If it returns false the entire subtree rooted at that node is skipped (pruned) and the loop continues. - If the node is a leaf, call
a_leafEvaluatorwith the global primitive list m_primitives, the leaf's primitive offset, and its primitive count. The leafEvaluator receives a view into the shared list rather than a freshly allocated sub-list, avoiding a heap allocation per leaf visit. - If the node is an interior node: a. Collect the K child indices from node.getChildOffsets(), look each child up in m_linearNodes, and call
a_nodeKeyFactoryon each to produce a NodeKey value. b. Bundle the K (childIdx, NodeKey) pairs into a local array and pass it toa_childOrderer, which reorders the array in-place. c. Push all K pairs onto the back of 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 at the back of the vector 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 global primitive list, offset, and count. [in] a_prunePredicate Called at each node; return true to descend, false to prune. [in] a_childOrderer Reorders the K (childIdx, 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
