A PackedBVH specialized for point clouds, with a fast build and turnkey queries. More...

#include <EBGeometry_PointCloudBVH.hpp>

Inheritance diagram for EBGeometry::PointCloudBVH< T, Meta, K, W >:

Collaboration diagram for EBGeometry::PointCloudBVH< T, Meta, K, W >:

[legend]

Classes
struct	Hit
	One query result: the cloud index of a matched point and its squared distance. More...

Public Types
using	PointGroup = PointAoSoA< T, std::size_t, W >
	The SoA leaf primitive: a group of up to W points carrying their cloud indices.

using	Base = BVH::PackedBVH< T, PointGroup, K, BVH::ValueStorage< PointGroup > >
	The general packed BVH this specializes.

using	Node = typename Base::Node
	Flat node type inherited from Base.

using	AABB = BoundingVolumes::AABBT< T >
	Axis-aligned bounding box type.

Public Types inherited from EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >
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
	PointCloudBVH ()=delete
	No default construction – a point cloud is required.

	PointCloudBVH (const std::vector< Vec3T< T > > &a_positions, const std::vector< Meta > &a_metadata, std::size_t a_targetLeafSize=16 *W)
	Build a BVH over a point cloud.

Hit	closestPoint (const Vec3T< T > &a_query) const noexcept
	Closest cloud point to an arbitrary query point.

std::size_t	closestPoints (const Vec3T< T > &a_query, std::size_t a_k, Hit *a_out) const noexcept
	The a_k closest cloud points to an arbitrary query point, nearest first.

Hit	nearestNeighbor (std::size_t a_point) const noexcept
	Nearest other point to a point already in the cloud (seed-from-own-leaf search).

std::size_t	nearestNeighbors (std::size_t a_point, std::size_t a_k, Hit *a_out) const noexcept
	The a_k nearest other points to a point already in the cloud, nearest first.

std::vector< Hit >	allNearestNeighbors (std::size_t a_k=1) const
	For every point, its a_k nearest other points (the k-nearest-neighbor graph).

Hit	closestPointBruteForce (const Vec3T< T > &a_query) const noexcept
	Brute-force closest point to an arbitrary query point (O(N) reference for closestPoint()).

std::size_t	closestPointsBruteForce (const Vec3T< T > &a_query, std::size_t a_k, Hit *a_out) const
	Brute-force a_k closest points to an arbitrary query point (O(N) reference for closestPoints()).

Hit	nearestNeighborBruteForce (std::size_t a_point) const noexcept
	Brute-force nearest other point to a cloud point (O(N) reference for nearestNeighbor()).

std::size_t	nearestNeighborsBruteForce (std::size_t a_point, std::size_t a_k, Hit *a_out) const
	Brute-force a_k nearest other points to a cloud point (O(N) reference for nearestNeighbors()).

std::size_t	numPoints () const noexcept
	Number of points in the cloud.

const Vec3T< T > &	position (std::size_t a_index) const noexcept
	Position of the point with the given cloud index.

const Meta &	metadata (std::size_t a_index) const noexcept
	User metadata of the point with the given cloud index.

Public Member Functions inherited from EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >
	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.

Additional Inherited Members
Protected Member Functions inherited from EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >
	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 inherited from EBGeometry::BVH::PackedBVH< T, P, K, StoragePolicy >
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

template<class T, class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>
class EBGeometry::PointCloudBVH< T, Meta, K, W >

A PackedBVH specialized for point clouds, with a fast build and turnkey queries.

Unlike the general PackedBVH constructors (which take a list of pre-made primitives and partition it via SAH/Midpoint/SFC), PointCloudBVH is built directly from a raw point cloud – positions plus a parallel array of user metadata. It uses an index-based, copy-free top-down build (partition an index permutation in place by longest-axis midpoint, pack leaves into PointAoSoA<T, size_t, W> groups inline), which is far cheaper than the general path and produces a tree just as tight for near-uniform clouds.

Every leaf carries the point's cloud index (its position in the input arrays) as metadata, so queries return that index; the user's own metadata is stored alongside and reachable via metadata(). The class hides all of pruneTraverse()/the SoA leaf kernel/the seed-from-own-leaf optimization behind a few high-level query methods.

Note: Queries come in two flavours. External queries (closestPoint / closestPoints) take an arbitrary point and traverse top-down. Self queries (nearestNeighbor / nearestNeighbors), and the batch allNearestNeighbors(), take a point already in the cloud and additionally seed the search bound from the leaf that point lives in (skipping that leaf during traversal) – a strictly cheaper search that an external point cannot use.

Template Parameters

T	Floating-point precision.
Meta	User metadata type stored per point and returned via metadata(). Defaults to the cloud index itself (std::size_t).
K	BVH branching factor. Defaults to the SIMD-optimal value for T.
W	Points per SoA leaf lane group. Defaults to the SIMD-optimal width for T.

Constructor & Destructor Documentation

◆ PointCloudBVH()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

EBGeometry::PointCloudBVH< T, Meta, K, W >::PointCloudBVH	(	const std::vector< Vec3T< T > > &	a_positions,
		const std::vector< Meta > &	a_metadata,
		std::size_t	a_targetLeafSize = `16 *W`
	)

inline

Build a BVH over a point cloud.

Parameters

[in]	a_positions	Point positions.
[in]	a_metadata	Per-point user metadata (same length/order as a_positions).
[in]	a_targetLeafSize	Target points per leaf (the build stops splitting at or below it).

Member Function Documentation

◆ allNearestNeighbors()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::vector< Hit > EBGeometry::PointCloudBVH< T, Meta, K, W >::allNearestNeighbors ( std::size_t a_k = 1 ) const

inline

For every point, its a_k nearest other points (the k-nearest-neighbor graph).

Processes points in leaf (build) order – already spatially coherent, so consecutive queries touch nearby leaves and stay hot in cache, with no per-call sort – and seeds each from its own leaf, so the whole batch is cheaper than the sum of independent queries. Result is flattened row-major: entry [i*a_k + j] is the j-th nearest neighbor of point i (ascending by distance).

Parameters

[in] a_k Number of neighbors per point.

Returns: A vector of size numPoints()*a_k of Hits.

◆ closestPoint()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

Hit EBGeometry::PointCloudBVH< T, Meta, K, W >::closestPoint ( const Vec3T< T > & a_query ) const

inlinenoexcept

Closest cloud point to an arbitrary query point.

Parameters

[in] a_query Query point (need not be in the cloud).

Returns: The nearest point and its squared distance.

◆ closestPointBruteForce()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

Hit EBGeometry::PointCloudBVH< T, Meta, K, W >::closestPointBruteForce ( const Vec3T< T > & a_query ) const

inlinenoexcept

Brute-force closest point to an arbitrary query point (O(N) reference for closestPoint()).

Full linear scan. Same result contract as closestPoint().

Parameters

[in] a_query Query point (need not be in the cloud).

Returns: The nearest point and its squared distance.

Warning: For debugging and testing only – an O(N) reference implementation, never a hot path.

◆ closestPoints()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::size_t EBGeometry::PointCloudBVH< T, Meta, K, W >::closestPoints	(	const Vec3T< T > &	a_query,
		std::size_t	a_k,
		Hit *	a_out
	)		const

inlinenoexcept

The a_k closest cloud points to an arbitrary query point, nearest first.

Parameters

[in]	a_query	Query point (need not be in the cloud).
[in]	a_k	Number of neighbors requested.
[out]	a_out	Buffer of at least a_k Hits; filled [0, returned count), ascending by distance.

Returns: The number of neighbors found (min(a_k, cloud size)).

◆ closestPointsBruteForce()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::size_t EBGeometry::PointCloudBVH< T, Meta, K, W >::closestPointsBruteForce	(	const Vec3T< T > &	a_query,
		std::size_t	a_k,
		Hit *	a_out
	)		const

inline

Brute-force a_k closest points to an arbitrary query point (O(N) reference for closestPoints()).

Full linear scan. Same result contract as closestPoints().

Parameters

[in]	a_query	Query point (need not be in the cloud).
[in]	a_k	Number of neighbors requested.
[out]	a_out	Buffer of at least a_k Hits; filled [0, returned count), ascending by distance.

Returns: The number of neighbors found (min(a_k, cloud size)).

Warning: For debugging and testing only – an O(N*k) reference implementation, never a hot path.

◆ metadata()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

const Meta & EBGeometry::PointCloudBVH< T, Meta, K, W >::metadata ( std::size_t a_index ) const

inlinenoexcept

User metadata of the point with the given cloud index.

Parameters

[in] a_index Cloud index.

Returns: The point's user metadata.

◆ nearestNeighbor()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

Hit EBGeometry::PointCloudBVH< T, Meta, K, W >::nearestNeighbor ( std::size_t a_point ) const

inlinenoexcept

Nearest other point to a point already in the cloud (seed-from-own-leaf search).

Parameters

[in] a_point Cloud index of the query point; excluded from its own result.

Returns: The nearest other point and its squared distance.

◆ nearestNeighborBruteForce()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

Hit EBGeometry::PointCloudBVH< T, Meta, K, W >::nearestNeighborBruteForce ( std::size_t a_point ) const

inlinenoexcept

Brute-force nearest other point to a cloud point (O(N) reference for nearestNeighbor()).

Full linear scan excluding the point itself. Same result contract as nearestNeighbor().

Parameters

[in] a_point Cloud index of the query point; excluded from its own result.

Returns: The nearest other point and its squared distance.

Warning: For debugging and testing only – an O(N) reference implementation, never a hot path.

◆ nearestNeighbors()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::size_t EBGeometry::PointCloudBVH< T, Meta, K, W >::nearestNeighbors	(	std::size_t	a_point,
		std::size_t	a_k,
		Hit *	a_out
	)		const

inlinenoexcept

The a_k nearest other points to a point already in the cloud, nearest first.

Parameters

[in]	a_point	Cloud index of the query point; excluded from its own result.
[in]	a_k	Number of neighbors requested.
[out]	a_out	Buffer of at least a_k Hits; filled [0, returned count), ascending.

Returns: The number of neighbors found (min(a_k, cloud size - 1)).

◆ nearestNeighborsBruteForce()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::size_t EBGeometry::PointCloudBVH< T, Meta, K, W >::nearestNeighborsBruteForce	(	std::size_t	a_point,
		std::size_t	a_k,
		Hit *	a_out
	)		const

inline

Brute-force a_k nearest other points to a cloud point (O(N) reference for nearestNeighbors()).

Full linear scan excluding the point itself. Same result contract as nearestNeighbors().

Parameters

[in]	a_point	Cloud index of the query point; excluded from its own result.
[in]	a_k	Number of neighbors requested.
[out]	a_out	Buffer of at least a_k Hits; filled [0, returned count), ascending.

Returns: The number of neighbors found (min(a_k, cloud size - 1)).

Warning: For debugging and testing only – an O(N*k) reference implementation, never a hot path.

◆ numPoints()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

std::size_t EBGeometry::PointCloudBVH< T, Meta, K, W >::numPoints ( ) const

inlinenoexcept

Number of points in the cloud.

Returns: The point count.

◆ position()

template<class T , class Meta = std::size_t, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

const Vec3T< T > & EBGeometry::PointCloudBVH< T, Meta, K, W >::position ( std::size_t a_index ) const

inlinenoexcept

Position of the point with the given cloud index.

Parameters

[in] a_index Cloud index.

Returns: The point's position.

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

Source/EBGeometry_PointCloudBVH.hpp

Classes

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ PointCloudBVH()

Member Function Documentation

◆ allNearestNeighbors()

◆ closestPoint()

◆ closestPointBruteForce()

◆ closestPoints()

◆ closestPointsBruteForce()

◆ metadata()

◆ nearestNeighbor()

◆ nearestNeighborBruteForce()

◆ nearestNeighbors()

◆ nearestNeighborsBruteForce()

◆ numPoints()

◆ position()