EBGeometry::PointCloudBVH< T, K, W > Class Template Reference

A BVH over a point cloud, with a fast build and turnkey queries. More...

#include <EBGeometry_PointCloudBVH.hpp>

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

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

Public Types
using	PointGroup = PointAoSoA< T, W >
	The SoA leaf primitive: a group of up to W points carrying their cloud indices.
using	Packed = BVH::PackedBVH< T, PointGroup, K >
	The packed BVH this class holds over its point groups.
using	Node = typename Packed::Node
	Flat node type of the held BVH.
using	AABB = BoundingVolumes::AABBT< T >
	Axis-aligned bounding box type.
using	Hit = PointCloud::Hit< T >
	One query result: the cloud index of a matched point and its squared distance.

Public Member Functions
	PointCloudBVH ()=delete
	No default construction – a point cloud is required.
	PointCloudBVH (Pool &a_pool, const std::vector< Vec3T< T > > &a_positions, 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 (uint32_t a_point) const noexcept
	Nearest other point to a point already in the cloud (seed-from-own-leaf search).
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.
Packed	getBVH () const noexcept
	The held packed BVH over the point groups.
PointCloudBVH	rebasedView (const Pool &a_pool) const noexcept
	Produce a copy of this object that resolves against a_pool.
PointCloudBVH	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, size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>
class EBGeometry::PointCloudBVH< T, K, W >

A BVH over a point cloud, with a fast build and turnkey queries.

Holds a PackedBVH over SoA point groups (rather than deriving from one) together with the cloud data the queries need. 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. 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, W> groups inline), which is far cheaper than the general path and produces a tree just as tight for near-uniform clouds.

Every leaf lane carries its point's cloud index (its position in the input positions array), and queries return that index in a PointCloud::Hit. Per-point user data lives in the caller's own array, indexed by it. PointCloudHashGrid answers the same queries with the same Hit type. The class hides all of traverse()/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.

The index-based build is several times faster than a full SAH tree, and for near-uniform clouds just as tight to query.

Device portability. The held PackedBVH and every cloud array (positions, the seeding tables, the leaf order) are reserved from the same Pool, and the class stores only offsets into it, so a PointCloudBVH 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.
K	BVH branching factor. Defaults to BVH::DefaultBranchingRatio<T>().
W	Points per SoA leaf lane group. Defaults to PointSoA::DefaultWidth<T>().

Member Typedef Documentation

Hit

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

using EBGeometry::PointCloudBVH< T, K, W >::Hit = PointCloud::Hit<T>

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

Shared with PointCloudHashGrid. 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

PointCloudBVH()

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

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

inline

Build a BVH over a point cloud.

A point's cloud index, which the queries report, is its position in a_positions.

Parameters

[in,out]	a_pool	Pool the packed BVH and the cloud arrays are reserved from; must outlive this object.
[in]	a_positions	Point positions. Fewer than PointCloud::InvalidIndex, all finite.
[in]	a_targetLeafSize	Target points per leaf (the build stops splitting at or below it). Must be at least 1.

Member Function Documentation

allNearestNeighbors()

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

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

base() [1/2]

template<class T , size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<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 , size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<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 , size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

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

closestPoints()

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

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

deepCopy()

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

PointCloudBVH EBGeometry::PointCloudBVH< T, K, W >::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 PointCloudBVH with the same tree and cloud, backed by a_dstPool.

getBVH()

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

Packed EBGeometry::PointCloudBVH< T, K, W >::getBVH ( ) const

inlinenoexcept

The held packed BVH over the point groups.

For callers that want the general PackedBVH interface (bounding volume, a custom traverse(), ...) on top of the turnkey queries above.

Returns

The packed BVH.

nearestNeighbor()

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

Hit EBGeometry::PointCloudBVH< T, K, W >::nearestNeighbor ( uint32_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.

nearestNeighbors()

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

std::size_t EBGeometry::PointCloudBVH< T, K, W >::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 , size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

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

inlinenoexcept

Number of points in the cloud.

Returns

The point count.

position()

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

const Vec3T< T > & EBGeometry::PointCloudBVH< T, K, W >::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 , size_t K = BVH::DefaultBranchingRatio<T>(), size_t W = PointSoA::DefaultWidth<T>()>

PointCloudBVH EBGeometry::PointCloudBVH< T, K, W >::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. The BVH and the cloud arrays are offsets into one pool, so rebasing the one location rebases everything.

Pool devicePool = Pool::mirror(hostPool, deviceMemoryResource());
const auto deviceCloud = cloud.rebasedView(devicePool);
myKernel<<<blocks, threads>>>(deviceCloud, ...);

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_PointCloudBVH.hpp