EBGeometry::PointCloudHashGrid< T > Class Template Reference

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

#include <EBGeometry_PointCloudHashGrid.hpp>

Inheritance diagram for EBGeometry::PointCloudHashGrid< T >:

Collaboration diagram for EBGeometry::PointCloudHashGrid< T >:

Public Types
using	Hit = PointCloud::Hit< T >
	One query result: the cloud index of a matched point and its squared distance.

Public Member Functions
	PointCloudHashGrid ()=delete
	No default construction – a point cloud is required.
	PointCloudHashGrid (Pool &a_pool, const std::vector< Vec3T< T > > &a_positions, 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 (uint32_t a_point) const noexcept
	Nearest other point to a point already in the cloud.
std::size_t	nearestNeighbors (uint32_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).
std::size_t	numPoints () const noexcept
	Number of points in the cloud.
const Vec3T< T > &	position (uint32_t a_index) const noexcept
	Position of the point with the given cloud index.
PointCloudHashGrid	rebasedView (const Pool &a_pool) const noexcept
	Produce a copy of this object that resolves against a_pool.
PointCloudHashGrid	deepCopy (Pool &a_dstPool) const
	Duplicate this object's storage into a_dstPool.
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.

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

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, with the same PointCloud::Hit result and the same query methods and accessors, so the two are 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 usually 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, and a query in an empty region visits many empty cells; PointCloudBVH adapts to local density and is the better choice there. Like PointCloudBVH, the grid serves only point queries: neither exposes a signed distance or bounding volume, so neither can be composed as a primitive inside an outer BVH/CSG.

Device portability. Every array (positions and the two CSR arrays) is reserved from one Pool, and the class stores only offsets into it, so a PointCloudHashGrid is trivially copyable. Mirror the pool, call rebasedView(), and pass the returned value into a kernel; every query that answers through a caller-supplied buffer (closestPoint(s), nearestNeighbor(s)) is device-callable. allNearestNeighbors() returns a std::vector and stays host-only.

Template Parameters

T	Floating-point precision.

Member Typedef Documentation

Hit

template<class T >

using EBGeometry::PointCloudHashGrid< T >::Hit = PointCloud::Hit<T>

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

Shared with PointCloudBVH. A miss, and every result slot a multi-result query could not fill, has Hit::valid() false; those queries also return the count found.

Constructor & Destructor Documentation

PointCloudHashGrid()

template<class T >

EBGeometry::PointCloudHashGrid< T >::PointCloudHashGrid ( Pool &  a_pool, const std::vector< Vec3T< T > > &  a_positions, 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. A point's cloud index, which the queries report, is its position in a_positions.

Parameters

[in,out]	a_pool	Pool the grid's arrays are reserved from; must outlive this object.
[in]	a_positions	Point positions. Fewer than PointCloud::InvalidIndex, all finite.
[in]	a_targetPerCell	Target average points per cell (sets the cell size). Must be > 0.

Member Function Documentation

allNearestNeighbors()

template<class T >

std::vector< Hit > EBGeometry::PointCloudHashGrid< T >::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.

base() [1/2]

template<class T >

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 >

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.

closestPoint()

template<class T >

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

closestPoints()

template<class T >

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

deepCopy()

template<class T >

PointCloudHashGrid EBGeometry::PointCloudHashGrid< T >::deepCopy ( Pool &  a_dstPool ) const

inline

Duplicate this object'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 PointCloudHashGrid with the same cells and cloud, backed by a_dstPool.

nearestNeighbor()

template<class T >

Hit EBGeometry::PointCloudHashGrid< T >::nearestNeighbor ( uint32_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.

nearestNeighbors()

template<class T >

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

numPoints()

template<class T >

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

inlinenoexcept

Number of points in the cloud.

Returns

The point count.

position()

template<class T >

const Vec3T< T > & EBGeometry::PointCloudHashGrid< T >::position ( uint32_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.

rebasedView()

template<class T >

PointCloudHashGrid EBGeometry::PointCloudHashGrid< T >::rebasedView ( const Pool &  a_pool ) const

inlinenoexcept

Produce a copy of this object that resolves against a_pool.

Same contract as PackedBVH::rebasedView(): mirror the pool first, then rebase, then copy the returned value into a kernel.

Parameters

[in]

a_pool

Pool to rebase onto: the object's own pool or one in its mirror chain.

Returns

A copy of this object resolving against a_pool.

---

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

• Source/EBGeometry_PointCloudHashGrid.hpp