Namespace for various bounding volume hierarchy (BVH) functionalities. More...

Namespaces
namespace	detail
	Build-phase helpers shared by PackedBVH's constructors and static builds. Not part of the public API.

Classes
struct	AsStored
	Visit the children within the bound in the order they are stored (first slot first), without sorting: for an any-hit query or a search that collects every leaf it reaches, where order does not matter. More...

struct	ChildBoxes
	The boxes of the K children of one interior node, in SoA layout: m_lo[axis][child] and m_hi[axis][child], so that one axis of all K children loads as one SIMD register. More...

struct	ClusterSpec
	Configuration for the ClusterSAH direct PackedBVH construction path. More...

struct	ConstructionOptions
	Leaf-size settings for the preset construction methods, one per family of methods. More...

struct	DescendAll
	The default visit callback of PackedBVH::traverse(): enter every node that passes the bound. More...

struct	FarthestFirst
	Visit the children within the bound farthest first (largest key first). More...

struct	IsQuery
	Whether a type is a query type: it names its precision (Scalar) and keys a node's children. More...

struct	IsQuery< Q, std::void_t< typename Q::Scalar, decltype(std::declval< const Q & >().key(std::declval< const BoundingVolumes::AABBT< typename Q::Scalar > & >()))> >
	A type with Scalar and a root key(box) is a query type. More...

struct	NearestFirst
	Visit the children within the bound nearest first (smallest key first). The default: a nearest-primitive search or a closest-hit ray tightens its bound fastest this way. More...

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

struct	PointQuery
	A point tracked through a BVH: the key of a box is the squared distance from the point to it (0 inside it). More...

struct	QueryKey
	The key type of a query type: Q::Key if it declares one, else Q::Scalar. More...

struct	QueryKey< Q, std::void_t< typename Q::Key > >
	A query type that declares its key type. More...

struct	QueryLanes
	How many queries a query type carries. 1 unless the type says otherwise. More...

struct	QueryLanes< Q, std::void_t< decltype(Q::Lanes)> >
	A query type that declares `static constexpr uint32_t Lanes`. More...

struct	RayQuery
	A ray tracked through a BVH: the key of a box is the distance along the ray at which it enters the box, or +infinity if it misses it. More...

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

Typedefs
template<class P >
using	PrimitiveList = std::vector< std::shared_ptr< const P > >
	Convenience alias for a list of shared primitive pointers.

template<class P , class BV >
using	PrimAndBV = std::pair< std::shared_ptr< const P >, BV >
	Convenience alias for a (primitive, bounding-volume) pair.

template<class P , class BV >
using	PrimAndBVList = std::vector< PrimAndBV< P, BV > >
	Convenience alias for a list of (primitive, bounding-volume) pairs.

template<class P , class BV , size_t K>
using	Partitioner = std::function< Array< PrimAndBVList< P, BV >, K >(PrimAndBVList< P, BV > a_primsAndBVs)>
	Polymorphic partitioner: splits a list of (primitive, BV) pairs into K sub-lists.

template<class T , class P , class BV , size_t K>
using	LeafPredicate = std::function< bool(const TreeBVH< T, P, BV, K > &a_node)>
	Predicate for deciding when a TreeBVH node should become a leaf (i.e., no further splitting).

template<class P >
using	LeafEvaluator = std::function< void(const PrimitiveList< P > &a_primitives)>
	Leaf-evaluation callback for TreeBVH::traverse.

template<class NodeType , class NodeKey >
using	PrunePredicate = std::function< bool(const NodeType &a_node, const NodeKey &a_nodeKey)>
	Node-visit predicate for TreeBVH::traverse().

template<class NodeType , class NodeKey , size_t K>
using	ChildOrderer = std::function< void(Array< std::pair< std::shared_ptr< const NodeType >, NodeKey >, K > &a_children)>
	Child-ordering callback for TreeBVH traversal.

template<class NodeType , class NodeKey >
using	NodeKeyFactory = std::function< NodeKey(const NodeType &a_node)>
	Node-key factory called once per node during TreeBVH::traverse().

Enumerations
enum class	Construction { CentroidSplit , MidpointSplit , SAH , ClusterSAH , Morton , Nested , Hilbert }
	The preset BVH construction methods that the library's own BVH users accept. More...

Functions
template<class T >
	PointQuery (Vec3T< T >) -> PointQuery< T >
	Deduce PointQuery's precision from its point: BVH::PointQuery{p}.

template<typename T >
constexpr size_t	DefaultBranchingRatio () noexcept
	The default branching factor K: 4, for both float and double, in every translation unit.

template<typename T >
constexpr size_t	HostBranchingRatio () noexcept
	The branching factor K that fills one SIMD register for type T under the compiler's SIMD flags.

template<class T , class P , class BV >
size_t	SAH2WaySplit (PrimAndBVList< P, BV > &a_list, const size_t a_begin, const size_t a_end, const bool a_longestAxisOnly=false) noexcept
	Internal helper: 2-way binned SAH split on the sub-range [a_begin, a_end).

template<class T , class P , class BV >
void	SAHKWaySplit (PrimAndBVList< P, BV > &a_list, const size_t a_begin, const size_t a_end, const size_t a_K, std::vector< std::pair< size_t, size_t > > &a_groups, const bool a_longestAxisOnly=false)
	Internal helper: recursively split [a_begin, a_end) into a_K groups via 2-way SAH.

template<class T , class P , class BV >
size_t	Midpoint2WaySplit (PrimAndBVList< P, BV > &a_list, const size_t a_begin, const size_t a_end) noexcept
	Internal helper: 2-way spatial-midpoint split on the sub-range [a_begin, a_end).

template<class T , class P , class BV >
void	MidpointKWaySplit (PrimAndBVList< P, BV > &a_list, const size_t a_begin, const size_t a_end, const size_t a_K, std::vector< std::pair< size_t, size_t > > &a_groups)
	Internal helper: recursively split [a_begin, a_end) into a_K groups via 2-way midpoint splits.

Variables
constexpr size_t	HostTraversalDepth = 256
	Deepest tree, in node levels (the root alone is one level), that a host traversal handles.

constexpr size_t	DeviceTraversalDepth = 32
	Deepest tree, in node levels, that a device traversal handles.

template<class X , size_t K>
auto	EqualCounts
	Utility: split a vector into K almost-equal contiguous chunks.

template<class T , class P , class BV , size_t K>
auto	PrimitiveCentroidPartitioner
	Partitioner that sorts primitives by centroid along the longest axis and splits into K pieces.

template<class T , class P , class BV , size_t K>
auto	BVCentroidPartitioner
	Partitioner that sorts primitives by bounding-volume centroid along the longest axis and splits into K pieces.

template<class T , class P , class BV , size_t K, bool LongestAxisOnly = false>
auto	BinnedSAHPartitioner
	Partitioner using binned SAH with recursive 2-way subdivision into K groups.

template<class T , class P , class BV , size_t K>
auto	MidpointPartitioner
	Partitioner that recursively bisects primitives by spatial midpoint (no sorting).

template<class T , class P , class BV , size_t K>
auto	DefaultLeafPredicate
	Default stop function: stop partitioning when the node holds fewer than K primitives.

Detailed Description

Namespace for various bounding volume hierarchy (BVH) functionalities.

Typedef Documentation

◆ ChildOrderer

template<class NodeType , class NodeKey , size_t K>

using EBGeometry::BVH::ChildOrderer = typedef std::function<void(Array<std::pair<std::shared_ptr<const NodeType>, NodeKey>, K>& a_children)>

Child-ordering callback for TreeBVH traversal.

Sorts an array of (child-node-pointer, key) pairs in-place so that the most promising child is visited first.

Template Parameters

NodeType	Node type (TreeBVH).
NodeKey	Per-node key attached to each stack entry.
K	Tree branching factor.

Parameters

[in,out] a_children K child nodes together with their node keys.

◆ LeafEvaluator

template<class P >

using EBGeometry::BVH::LeafEvaluator = typedef std::function<void(const PrimitiveList<P>& a_primitives)>

Leaf-evaluation callback for TreeBVH::traverse.

Called once for every leaf node visited during traversal.

Template Parameters

P	Primitive type.

Parameters

[in] a_primitives Primitive list stored in the leaf.

◆ LeafPredicate

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

using EBGeometry::BVH::LeafPredicate = typedef std::function<bool(const TreeBVH<T, P, BV, K>& a_node)>

Predicate for deciding when a TreeBVH node should become a leaf (i.e., no further splitting).

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding volume type.
K	Tree branching factor.

Parameters

[in] a_node BVH node under consideration.

Returns: True if the node should not be sub-divided further.

◆ NodeKeyFactory

template<class NodeType , class NodeKey >

using EBGeometry::BVH::NodeKeyFactory = typedef std::function<NodeKey(const NodeType& a_node)>

Node-key factory called once per node during TreeBVH::traverse().

Produces the NodeKey value that will be passed to PrunePredicate and ChildOrderer for each child of the current node.

Template Parameters

NodeType	Node type (TreeBVH).
NodeKey	Per-node key type to produce.

Parameters

[in] a_node Current node.

Returns: NodeKey value for a_node's children.

◆ Partitioner

template<class P , class BV , size_t K>

using EBGeometry::BVH::Partitioner = typedef std::function<Array<PrimAndBVList<P, BV>, K>(PrimAndBVList<P, BV> a_primsAndBVs)>

Polymorphic partitioner: splits a list of (primitive, BV) pairs into K sub-lists.

The input list is taken by value (a sink): callers move their list in, and an implementation should partition it in place and move the K sub-lists out – so a whole top-down build reorders primitive handles rather than repeatedly copying them (the built-in partitioners all do this). The split arithmetic is the cheap part; avoiding the copies is what keeps construction fast.

Template Parameters

P	Primitive type.
BV	Bounding volume type.
K	Tree branching factor.

Parameters

[in] a_primsAndBVs Input primitives and their bounding volumes (consumed).

Returns: K-element array of sub-lists.

◆ PrimAndBV

template<class P , class BV >

using EBGeometry::BVH::PrimAndBV = typedef std::pair<std::shared_ptr<const P>, BV>

Convenience alias for a (primitive, bounding-volume) pair.

Template Parameters

P	Primitive type.
BV	Bounding volume type.

◆ PrimAndBVList

template<class P , class BV >

using EBGeometry::BVH::PrimAndBVList = typedef std::vector<PrimAndBV<P, BV> >

Convenience alias for a list of (primitive, bounding-volume) pairs.

Template Parameters

P	Primitive type.
BV	Bounding volume type enclosing the implicit surface of each primitive.

◆ PrimitiveList

template<class P >

using EBGeometry::BVH::PrimitiveList = typedef std::vector<std::shared_ptr<const P> >

Convenience alias for a list of shared primitive pointers.

Template Parameters

P	Primitive type bounded by the BVH.

◆ PrunePredicate

template<class NodeType , class NodeKey >

using EBGeometry::BVH::PrunePredicate = typedef std::function<bool(const NodeType& a_node, const NodeKey& a_nodeKey)>

Node-visit predicate for TreeBVH::traverse().

Must return true to descend into the node and false to prune it. (PackedBVH::traverse() takes a query type and template callbacks instead.)

Template Parameters

NodeType	Node type (TreeBVH).
NodeKey	Caller-supplied per-node key attached to each stack entry (e.g. a running minimum distance).

Parameters

[in]	a_node	Node under consideration.
[in]	a_nodeKey	Caller-supplied key for this stack entry.

Returns: True if the subtree rooted at a_node should be visited.

Enumeration Type Documentation

◆ Construction

enum class EBGeometry::BVH::Construction

strong

The preset BVH construction methods that the library's own BVH users accept.

Each value names the algorithm that groups the primitives; its comment says in which direction the tree is built. Top-down methods split the root's primitives recursively until a leaf predicate stops them; bottom-up methods sort the primitives along a space-filling curve, cut the sorted list into leaves, and merge K neighbors at a time up to the root.

MeshSDF, TriMeshSDF, BVHUnion and BVHSmoothUnion (and the parser functions that build them) accept every value. Each of them aborts, in every build, on a value outside this list. A custom partitioner or leaf predicate is not a preset: build a TreeBVH with it and pack() it instead.

Enumerator
CentroidSplit	Top-down: split at the median bounding-volume centroid along the longest axis (BVCentroidPartitioner).
MidpointSplit	Top-down: split at the spatial midpoint of the centroids' longest axis, with no sorting (MidpointPartitioner). The fastest top-down build; does not adapt to clustered input.
SAH	Top-down: binned surface area heuristic (BinnedSAHPartitioner). The recommended default: generally the lowest traversal cost.
ClusterSAH	Top-down: group the primitives into small spatial clusters, then run binned SAH over the clusters (see ClusterSpec). Builds several times faster than SAH, at the cost of leaves of up to (K-1) clusters.
Morton	Bottom-up: leaves of consecutive primitives along a Morton (Z-order) curve.
Nested	Bottom-up: leaves of consecutive primitives along a Nested (row-major) curve.
Hilbert	Bottom-up: leaves of consecutive primitives along a Hilbert curve.

Function Documentation

◆ DefaultBranchingRatio()

template<typename T >

constexpr size_t EBGeometry::BVH::DefaultBranchingRatio ( )

constexprnoexcept

The default branching factor K: 4, for both float and double, in every translation unit.

This is the value the library's class templates default to. It never depends on compiler flags, so a type spelled with it has the same layout in a host-only file, in a file compiled with AVX, and in both passes of a CUDA or HIP compile – which is what lets an object be built on the host and used on a device. On the benchmarks in the Sphinx page on configuration options, it is also as fast on the host as the ISA-tuned value.

For host-only code, HostBranchingRatio<T>() gives the value tuned to the compiler's SIMD flags instead. EBGEOMETRY_HOST_TUNED_DEFAULTS does not change this value: it only widens the triangle groups (TriangleSoA::DefaultWidth), since a wider K measured no faster. Usage: size_t K = BVH::DefaultBranchingRatio<T>() as a template-parameter default.

Template Parameters

T	Floating-point precision type (float or double).

Returns: 4.

◆ HostBranchingRatio()

template<typename T >

constexpr size_t EBGeometry::BVH::HostBranchingRatio ( )

constexprnoexcept

The branching factor K that fills one SIMD register for type T under the compiler's SIMD flags.

Opt-in, for host-only code:

ISA	T=float	T=double
AVX-512F	16	8
AVX	8	4
SSE4.1	4	4
fallback	4	4

The value depends on the flags each translation unit is compiled with, so a type spelled with it can mean different types in different files, and different layouts in the host and device passes of one CUDA or HIP compile. Never use it for a type that is shared with device code or with another translation unit built with different flags; use DefaultBranchingRatio<T>() there.

Template Parameters

T	Floating-point precision type (float or double).

Returns: K for T under the current ISA.

◆ Midpoint2WaySplit()

template<class T , class P , class BV >

size_t EBGeometry::BVH::Midpoint2WaySplit	(	PrimAndBVList< P, BV > &	a_list,
		const size_t	a_begin,
		const size_t	a_end
	)

inlinenoexcept

Internal helper: 2-way spatial-midpoint split on the sub-range [a_begin, a_end).

Unlike SAH2WaySplit (which evaluates 32 binned candidate planes) or BVCentroidPartitioner (which sorts by centroid), this computes exactly one split plane – the midpoint of the centroid bounding box along its longest axis – and partitions around it with a single std::partition pass. No sorting and no per-plane cost evaluation, at the cost of not adapting to the primitive distribution the way SAH does: entirely sort-less, O(N) per split.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type.

Parameters

[in,out]	a_list	Primitives and their bounding volumes; partitioned in place around the split.
[in]	a_begin	First index of the sub-range to split.
[in]	a_end	One-past-the-last index of the sub-range to split.

Returns: Split index (index of the first element of the right group).

◆ MidpointKWaySplit()

template<class T , class P , class BV >

void EBGeometry::BVH::MidpointKWaySplit	(	PrimAndBVList< P, BV > &	a_list,
		const size_t	a_begin,
		const size_t	a_end,
		const size_t	a_K,
		std::vector< std::pair< size_t, size_t > > &	a_groups
	)

inline

Internal helper: recursively split [a_begin, a_end) into a_K groups via 2-way midpoint splits.

Splits into std::floor(a_K/2) and std::ceil(a_K/2) sub-groups recursively – exact for power-of-two K; a reasonable approximation for other values. Structurally identical to SAHKWaySplit, just calling Midpoint2WaySplit instead of SAH2WaySplit at each level.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type.

Parameters

[in,out]	a_list	Primitives and their bounding volumes; partitioned in place.
[in]	a_begin	First index of the sub-range to split.
[in]	a_end	One-past-the-last index of the sub-range to split.
[in]	a_K	Number of groups to split the sub-range into.
[out]	a_groups	Resulting groups as [begin, end) index pairs.

◆ PointQuery()

template<class T >

EBGeometry::BVH::PointQuery ( Vec3T< T > ) -> PointQuery< T >

Deduce PointQuery's precision from its point: BVH::PointQuery{p}.

Template Parameters

T	Floating-point precision.

◆ SAH2WaySplit()

template<class T , class P , class BV >

size_t EBGeometry::BVH::SAH2WaySplit	(	PrimAndBVList< P, BV > &	a_list,
		const size_t	a_begin,
		const size_t	a_end,
		const bool	a_longestAxisOnly = `false`
	)

inlinenoexcept

Internal helper: 2-way binned SAH split on the sub-range [a_begin, a_end).

Evaluates 32 bins per axis and picks the split plane that minimizes SA(left)*N_left + SA(right)*N_right. Partitions a_list in-place and returns the split index (first element of the right group).

Note: Requires BV == AABBT<T>: BV must support getLowCorner(), getHighCorner(), getArea(), and construction from two Vec3T<T> corner arguments.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type (must be AABBT<T>).

Parameters

[in,out]	a_list	Primitives and their bounding volumes; partitioned in place around the split.
[in]	a_begin	First index of the sub-range to split.
[in]	a_end	One-past-the-last index of the sub-range to split.
[in]	a_longestAxisOnly	If true, evaluate candidate planes on only the longest centroid-bbox axis instead of all three – roughly a third of the binning work, for a small tree-quality cost that is negligible on near-uniform inputs (e.g. point clouds). Default false (full 3-axis SAH).

Returns: Split index (index of the first element of the right group).

◆ SAHKWaySplit()

template<class T , class P , class BV >

void EBGeometry::BVH::SAHKWaySplit	(	PrimAndBVList< P, BV > &	a_list,
		const size_t	a_begin,
		const size_t	a_end,
		const size_t	a_K,
		std::vector< std::pair< size_t, size_t > > &	a_groups,
		const bool	a_longestAxisOnly = `false`
	)

inline

Internal helper: recursively split [a_begin, a_end) into a_K groups via 2-way SAH.

Splits into std::floor(a_K/2) and std::ceil(a_K/2) sub-groups recursively. For power-of-two K this is equivalent to a balanced binary subdivision tree applied a_K times.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type (must be AABBT<T>).

Parameters

[in,out]	a_list	Primitives and their bounding volumes; partitioned in place.
[in]	a_begin	First index of the sub-range to split.
[in]	a_end	One-past-the-last index of the sub-range to split.
[in]	a_K	Number of groups to split the sub-range into.
[out]	a_groups	Resulting groups as [begin, end) index pairs.
[in]	a_longestAxisOnly	Forwarded to SAH2WaySplit: bin only the longest centroid-bbox axis.

Variable Documentation

◆ BinnedSAHPartitioner

template<class T , class P , class BV , size_t K, bool LongestAxisOnly = false>

auto EBGeometry::BVH::BinnedSAHPartitioner

Initial value:

= [](PrimAndBVList<P, BV> a_primsAndBVs) -> Array<PrimAndBVList<P, BV>, K> {
  EBGEOMETRY_EXPECT(!a_primsAndBVs.empty());
 
  
  
  std::vector<std::pair<size_t, size_t>> groups;
  groups.reserve(K);
 
  SAHKWaySplit<T, P, BV>(a_primsAndBVs, 0, a_primsAndBVs.size(), K, groups, LongestAxisOnly);
 
  Array<PrimAndBVList<P, BV>, K> result;
  for (size_t k = 0; k < K; k++) {
    const auto [b, e] = groups[k];
    result[k]         = PrimAndBVList<P, BV>(std::make_move_iterator(a_primsAndBVs.begin() + b),
                                     std::make_move_iterator(a_primsAndBVs.begin() + e));
  }
 
  return result;
}

Partitioner using binned SAH with recursive 2-way subdivision into K groups.

For each split, evaluates 32 candidate planes per axis and picks the one minimizing SA(left)*N_left + SA(right)*N_right (the standard ray-tracing SAH cost without the traversal constant). K groups are produced by recursively splitting into std::floor(K/2) and std::ceil(K/2) subsets — exact for power-of-two K; a reasonable approximation for other values.

The K whose child boxes fill one SIMD register, by ISA (what HostBranchingRatio() returns; the default K = 4, DefaultBranchingRatio(), measured as fast on the host and is the one device code can share):

AVX-512F, float → K=16 (one _mm512_load_ps covers all K children)
AVX-512F, double → K=8 (one _mm512_load_pd covers all K children)
AVX, float → K=8 (one _mm256_load_ps)
AVX, double → K=4 (one _mm256_load_pd)
SSE4.1, float → K=4 (one _mm_load_ps)

Note: Requires BV == AABBT<T>.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type (must be AABBT<T>).
K	Number of output sub-lists (branching factor of the resulting BVH).
LongestAxisOnly	If true, bin candidate planes on only the longest centroid-bbox axis per split instead of all three – ~a third of the binning work (measured ~20% faster builds on point clouds) for a tree-quality cost that is negligible on near-uniform inputs. Default false.

Parameters

[in] a_primsAndBVs Input (primitive, BV) pairs.

Returns: K sub-lists.

◆ BVCentroidPartitioner

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

auto EBGeometry::BVH::BVCentroidPartitioner

Initial value:

= [](PrimAndBVList<P, BV> a_primsAndBVs) -> Array<PrimAndBVList<P, BV>, K> {
  EBGEOMETRY_EXPECT(!a_primsAndBVs.empty());
 
  Vec3T<T> lo = +Vec3T<T>::max();
  Vec3T<T> hi = -Vec3T<T>::max();
 
  for (const auto& pbv : a_primsAndBVs) {
    lo = min(lo, pbv.second.getCentroid());
    hi = max(hi, pbv.second.getCentroid());
  }
 
  const size_t splitDir = (hi - lo).maxDir(true);
 
  
  std::sort(a_primsAndBVs.begin(),
            a_primsAndBVs.end(),
            [splitDir](const PrimAndBV<P, BV>& pbv1, const PrimAndBV<P, BV>& pbv2) -> bool {
              return pbv1.second.getCentroid()[splitDir] < pbv2.second.getCentroid()[splitDir];
            });
 
  return BVH::EqualCounts<PrimAndBV<P, BV>, K>(std::move(a_primsAndBVs));
}

Partitioner that sorts primitives by bounding-volume centroid along the longest axis and splits into K pieces.

Template Parameters

T	Floating-point precision used for centroid comparisons.
P	Primitive type.
BV	Bounding volume type.
K	Number of output sub-lists (tree branching factor).

Parameters

[in] a_primsAndBVs Input (primitive, BV) pairs.

Returns: K sub-lists.

◆ DefaultLeafPredicate

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

auto EBGeometry::BVH::DefaultLeafPredicate

Initial value:

=

[](const BVH::TreeBVH<T, P, BV, K>& a_node) noexcept -> bool { return (a_node.getPrimitives()).size() < K; }

Default stop function: stop partitioning when the node holds fewer than K primitives.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding volume type.
K	Tree branching factor.

Parameters

[in] a_node BVH node.

Returns: True if the node has fewer than K primitives.

◆ DeviceTraversalDepth

constexpr size_t EBGeometry::BVH::DeviceTraversalDepth = 32

inlineconstexpr

Deepest tree, in node levels, that a device traversal handles.

Smaller than the host value, since device stack memory is per thread: 31 entries of 4 + K bytes rounded up to a multiple of 4, 248 bytes at K = 4. PackedBVH::rebasedView() checks every device view against it.

◆ EqualCounts

template<class X , size_t K>

auto EBGeometry::BVH::EqualCounts

Initial value:

= [](std::vector<X> a_primitives) -> Array<std::vector<X>, K> {
  static_assert(K >= 2, "EqualCounts<X, K>: branching factor K must be at least 2");
 
  EBGEOMETRY_EXPECT(!a_primitives.empty());
 
  const int length = a_primitives.size() / K;
  int       remain = a_primitives.size() % K;
 
  int begin = 0;
  int end   = 0;
 
  Array<std::vector<X>, K> chunks;
 
  for (size_t k = 0; k < K; k++) {
    end += (remain > 0) ? length + 1 : length;
    remain--;
 
    
    
    chunks[k] = std::vector<X>(std::make_move_iterator(a_primitives.begin() + begin),
                               std::make_move_iterator(a_primitives.begin() + end));
 
    begin = end;
  }
 
  return chunks;
}

Utility: split a vector into K almost-equal contiguous chunks.

Template Parameters

X	Element type.
K	Number of chunks.

Parameters

[in] a_primitives Input vector.

Returns: Array of K sub-vectors whose sizes differ by at most 1.

◆ HostTraversalDepth

constexpr size_t EBGeometry::BVH::HostTraversalDepth = 256

inlineconstexpr

Deepest tree, in node levels (the root alone is one level), that a host traversal handles.

The traversals keep a fixed stack with one entry per level below the root, so the limit is the same for every K. Every PackedBVH is checked against it when it is built. The stack takes 255 entries of 4 + K bytes rounded up to a multiple of 4: 2 KB at K = 4.

◆ MidpointPartitioner

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

auto EBGeometry::BVH::MidpointPartitioner

Initial value:

= [](PrimAndBVList<P, BV> a_primsAndBVs) -> Array<PrimAndBVList<P, BV>, K> {
  EBGEOMETRY_EXPECT(!a_primsAndBVs.empty());
 
  
  
  
  
  std::vector<std::pair<size_t, size_t>> groups;
  groups.reserve(K);
 
  MidpointKWaySplit<T, P, BV>(a_primsAndBVs, 0, a_primsAndBVs.size(), K, groups);
 
  Array<PrimAndBVList<P, BV>, K> result;
  for (size_t k = 0; k < K; k++) {
    const auto [b, e] = groups[k];
    result[k]         = PrimAndBVList<P, BV>(std::make_move_iterator(a_primsAndBVs.begin() + b),
                                     std::make_move_iterator(a_primsAndBVs.begin() + e));
  }
 
  return result;
}

Partitioner that recursively bisects primitives by spatial midpoint (no sorting).

At every split, computes the midpoint of the centroid bounding box along its longest axis and partitions primitives around it in one O(N) std::partition pass – unlike BVCentroidPartitioner (sorts by centroid) or BinnedSAHPartitioner (evaluates 32 candidate planes per axis), no sorting or per-plane cost evaluation happens anywhere. K groups are produced by recursively splitting into std::floor(K/2) and std::ceil(K/2) subsets, mirroring BinnedSAHPartitioner's own K-way structure exactly (see MidpointKWaySplit).

This is the fastest of the three top-down partitioners to build (no sort, no per-axis binning), at the cost of build quality: it does not adapt to the primitive distribution at all, so a heavily clustered or skewed input can produce noticeably less balanced (and less query-efficient) trees than BVCentroidPartitioner or BinnedSAHPartitioner would.

Template Parameters

T	Floating-point precision.
P	Primitive type.
BV	Bounding-volume type.
K	Number of output sub-lists (branching factor of the resulting BVH).

Parameters

[in] a_primsAndBVs Input (primitive, BV) pairs.

Returns: K sub-lists.

◆ PrimitiveCentroidPartitioner

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

auto EBGeometry::BVH::PrimitiveCentroidPartitioner

Initial value:

= [](PrimAndBVList<P, BV> a_primsAndBVs) -> Array<PrimAndBVList<P, BV>, K> {
  EBGEOMETRY_EXPECT(!a_primsAndBVs.empty());
 
  Vec3T<T> lo = +Vec3T<T>::max();
  Vec3T<T> hi = -Vec3T<T>::max();
 
  for (const auto& pbv : a_primsAndBVs) {
    lo = min(lo, pbv.first->getCentroid());
    hi = max(hi, pbv.first->getCentroid());
  }
 
  const size_t splitDir = (hi - lo).maxDir(true);
 
  
  std::sort(a_primsAndBVs.begin(),
            a_primsAndBVs.end(),
            [splitDir](const PrimAndBV<P, BV>& pbv1, const PrimAndBV<P, BV>& pbv2) -> bool {
              return pbv1.first->getCentroid(splitDir) < pbv2.first->getCentroid(splitDir);
            });
 
  return BVH::EqualCounts<PrimAndBV<P, BV>, K>(std::move(a_primsAndBVs));
}

Partitioner that sorts primitives by centroid along the longest axis and splits into K pieces.

Template Parameters

T	Floating-point precision used for centroid comparisons.
P	Primitive type.
BV	Bounding volume type.
K	Number of output sub-lists (tree branching factor).

Parameters

[in] a_primsAndBVs Input (primitive, BV) pairs.

Returns: K sub-lists.

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ ChildOrderer

◆ LeafEvaluator

◆ LeafPredicate

◆ NodeKeyFactory

◆ Partitioner

◆ PrimAndBV

◆ PrimAndBVList

◆ PrimitiveList

◆ PrunePredicate

Enumeration Type Documentation

◆ Construction

Function Documentation

◆ DefaultBranchingRatio()

◆ HostBranchingRatio()

◆ Midpoint2WaySplit()

◆ MidpointKWaySplit()

◆ PointQuery()

◆ SAH2WaySplit()

◆ SAHKWaySplit()

Variable Documentation

◆ BinnedSAHPartitioner

◆ BVCentroidPartitioner

◆ DefaultLeafPredicate

◆ DeviceTraversalDepth

◆ EqualCounts

◆ HostTraversalDepth

◆ MidpointPartitioner

◆ PrimitiveCentroidPartitioner