A uniform spatial grid specialized for point clouds, with a fast build and turnkey queries. More...

#include <EBGeometry_PointCloudHashGrid.hpp>

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

Public Member Functions
	PointCloudHashGrid ()=delete
	No default construction – a point cloud is required.

	PointCloudHashGrid (const std::vector< Vec3T< T > > &a_positions, const std::vector< Meta > &a_metadata, T a_targetPerCell=T(1))
	Build a uniform grid 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.

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.

Detailed Description

template<class T, class Meta = std::size_t>
class EBGeometry::PointCloudHashGrid< T, Meta >

A uniform spatial grid specialized for point clouds, with a fast build and turnkey queries.

PointCloudHashGrid answers the same nearest-neighbor / closest-point queries as PointCloudBVH and exposes the same public interface (same Hit type, same query methods and accessors), so the two are drop-in interchangeable – but it circumvents the tree entirely. Points are counting-sorted into a dense grid of cells (a CSR bucket array keyed by integer cell coordinates), which is an O(N) build with no recursive partitioning and no tree nodes.

Queries use an expanding-shell search: starting from the query point's cell, cells are visited shell by shell (Chebyshev radius 0, 1, 2, ...). The search stops as soon as the k-th best distance found is provably closer than any unvisited cell can hold – an exact bound, so no neighbor is ever missed. With the default cell size (~1 point/cell) this is almost always one or two shells.

Note: This is the bounded-domain form of spatial hashing: cells are stored in a dense array sized to the cloud's bounding box, which is O(N) memory for a compact cloud. A cloud that is sparse but spread over a very large box would want true spatial hashing (a hash map keyed by cell id) instead.; Density matters. The cell size is global, so PointCloudHashGrid is fastest on near-uniform clouds. On strongly clustered / multi-scale clouds a single cell size is simultaneously too coarse in dense regions and too fine in sparse ones; PointCloudBVH adapts to local density and is the better choice there. The grid also serves only point queries – unlike PointCloudBVH it is not a BVH and cannot be composed as a primitive inside an outer BVH/CSG.

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).

Constructor & Destructor Documentation

◆ PointCloudHashGrid()

template<class T , class Meta = std::size_t>

EBGeometry::PointCloudHashGrid< T, Meta >::PointCloudHashGrid	(	const std::vector< Vec3T< T > > &	a_positions,
		const std::vector< Meta > &	a_metadata,
		T	a_targetPerCell = `T(1)`
	)

inline

Build a uniform grid over a point cloud.

The cell size is derived from a_targetPerCell: cells are sized so that, at the cloud's average density, each holds about that many points. ~1 point/cell is the query-time sweet spot; larger values shrink the grid (less memory) at the cost of bigger per-cell scans.

Parameters

[in]	a_positions	Point positions.
[in]	a_metadata	Per-point user metadata (same length/order as a_positions).
[in]	a_targetPerCell	Target average points per cell (sets the cell size). Must be > 0.

Member Function Documentation

◆ allNearestNeighbors()

template<class T , class Meta = std::size_t>

std::vector< Hit > EBGeometry::PointCloudHashGrid< T, Meta >::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 cell (spatial) order so consecutive queries touch nearby cells and stay hot in cache. 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>

Hit EBGeometry::PointCloudHashGrid< T, Meta >::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>

Hit EBGeometry::PointCloudHashGrid< T, Meta >::closestPointBruteForce ( const Vec3T< T > & a_query ) const

inlinenoexcept

Brute-force closest point to an arbitrary query point (O(N) reference for 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>

std::size_t EBGeometry::PointCloudHashGrid< T, Meta >::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>

std::size_t EBGeometry::PointCloudHashGrid< T, Meta >::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()).

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>

const Meta & EBGeometry::PointCloudHashGrid< T, Meta >::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>

Hit EBGeometry::PointCloudHashGrid< T, Meta >::nearestNeighbor ( std::size_t a_point ) const

inlinenoexcept

Nearest other point to a point already in the cloud.

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>

Hit EBGeometry::PointCloudHashGrid< T, Meta >::nearestNeighborBruteForce ( std::size_t a_point ) const

inlinenoexcept

Brute-force nearest other point to a cloud point (O(N) reference for 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>

std::size_t EBGeometry::PointCloudHashGrid< T, Meta >::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>

std::size_t EBGeometry::PointCloudHashGrid< T, Meta >::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()).

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>

std::size_t EBGeometry::PointCloudHashGrid< T, Meta >::numPoints ( ) const

inlinenoexcept

Number of points in the cloud.

Returns: The point count.

◆ position()

template<class T , class Meta = std::size_t>

const Vec3T< T > & EBGeometry::PointCloudHashGrid< T, Meta >::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_PointCloudHashGrid.hpp

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ PointCloudHashGrid()

Member Function Documentation

◆ allNearestNeighbors()

◆ closestPoint()

◆ closestPointBruteForce()

◆ closestPoints()

◆ closestPointsBruteForce()

◆ metadata()

◆ nearestNeighbor()

◆ nearestNeighborBruteForce()

◆ nearestNeighbors()

◆ nearestNeighborsBruteForce()

◆ numPoints()

◆ position()