A BVH over spheres of differing radii (polydisperse particles), with the signed distance to their union and the closest sphere. More...

#include <EBGeometry_SphereCloudBVH.hpp>

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

[legend]

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

[legend]

Public Types
using	Sphere = SphereCloud::Sphere< T >
	A sphere: a center and a radius.

using	Hit = SphereCloud::Hit< T >
	One query result: the cloud index of a sphere and the signed distance to its surface.

using	SphereGroup = SphereAoSoA< T, W >
	The SoA leaf primitive: a group of up to W spheres carrying their cloud indices.

using	Packed = BVH::PackedBVH< T, SphereGroup, K >
	The packed BVH this class holds over its sphere groups.

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

Public Types inherited from EBGeometry::PointCloudDetail::CloudBVH< T, K, W, Prim >
using	Item = typename Prim::Item
	What a source of the primitives returns.

using	Group = typename Prim::Group
	The SoA leaf primitive: a group of up to W primitives carrying their cloud indices.

using	Packed = BVH::PackedBVH< T, Group, K >
	The packed BVH over the groups.

using	Node = typename Packed::Node
	Flat node type of the held BVH.

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

Public Member Functions
	SphereCloudBVH (Pool &a_pool, const std::vector< Sphere > &a_spheres, std::size_t a_targetLeafSize=16 *W)
	Build a BVH over spheres on the host: shorthand for build(a_pool, a_spheres, a_targetLeafSize).

	SphereCloudBVH (Pool &a_pool, const std::vector< Vec3T< T > > &a_centers, const std::vector< T > &a_radii, std::size_t a_targetLeafSize=16 *W)
	Build a BVH over spheres given as centers and radii, on the host: shorthand for build(a_pool, a_centers, a_radii, a_targetLeafSize).

template<class Source >
void	rebuild (const Source &a_source, uint32_t a_numSpheres)
	Build the BVH again, in the arrays build() reserved, from new spheres.

uint32_t	maxSpheres () const noexcept
	The most spheres rebuild() can take.

T	signedDistance (const Vec3T< T > &a_point) const noexcept
	Signed distance to the union of the spheres: min_i(\|p - c_i\| - r_i); see the class.

Hit	closestSphere (const Vec3T< T > &a_point) const noexcept
	The sphere whose surface is nearest to a point, in the signed sense of signedDistance().

AABB	computeBoundingVolume () const noexcept
	The box of all the spheres.

uint32_t	numSpheres () const noexcept
	Number of spheres in the cloud.

Sphere	sphere (uint32_t a_index) const noexcept
	The sphere with a cloud index.

Packed	getBVH () const noexcept
	The held packed BVH over the sphere groups.

SphereCloudBVH	rebasedView (const Pool &a_pool) const noexcept
	Produce a copy of this object that resolves against `a_pool`.

SphereCloudBVH	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`.

Static Public Member Functions
template<class Source >
static SphereCloudBVH	build (Pool &a_pool, const Source &a_source, uint32_t a_numSpheres, std::size_t a_targetLeafSize=16 *W, uint32_t a_maxSpheres=0)
	Build a BVH over spheres, where the pool's memory is.

static SphereCloudBVH	build (Pool &a_pool, const std::vector< Sphere > &a_spheres, std::size_t a_targetLeafSize=16 *W, uint32_t a_maxSpheres=0)
	Build a BVH over spheres on the host, where the pool's memory is; see the build() above.

static SphereCloudBVH	build (Pool &a_pool, const std::vector< Vec3T< T > > &a_centers, const std::vector< T > &a_radii, std::size_t a_targetLeafSize=16 *W, uint32_t a_maxSpheres=0)
	Build a BVH over spheres given as centers and radii, on the host, where the pool's memory is; see the build() above.

Additional Inherited Members
Protected Member Functions inherited from EBGeometry::PointCloudDetail::CloudBVH< T, K, W, Prim >
	CloudBVH () noexcept=default
	An empty BVH, to be reserved and filled.

template<class Source >
void	initialize (Pool &a_pool, const Source &a_source, uint32_t a_numItems, std::size_t a_targetLeafSize, uint32_t a_maxItems, const char *a_who)
	Build over the primitives of a source, where the pool's memory is: the body of PointCloudBVH::build().

void	initialize (Pool &a_pool, const std::vector< Item > &a_items, std::size_t a_targetLeafSize, uint32_t a_maxItems, const char *a_who)
	Build over the primitives of a host array, where the pool's memory is: for a pool in device memory, the primitives are checked on the host and copied to scratch there first.

template<class Source >
void	reinitialize (const Source &a_source, uint32_t a_numItems, const char *a_who)
	Build again in the arrays initialize() reserved: the body of PointCloudBVH::rebuild().

void	rebase (const Pool &a_pool) noexcept
	Resolve this object against `a_pool:` the body of PointCloudBVH::rebasedView(), on a copy.

void	copyInto (CloudBVH &a_copy, Pool &a_dstPool) const
	Duplicate this object's storage into `a_dstPool`, for `a_copy`, a copy of this object: the body of PointCloudBVH::deepCopy().

void	reserveArrays (Pool &a_pool, const Sizes &a_sizes, uint32_t a_numItems)
	Reserve the BVH's and the cloud's arrays from `a_pool`.

template<class Source >
Sizes	shape (const Scratch &a_scratch, void a_base, const Source &a_source, uint32_t a_numItems, const char a_who)
	Build steps 1 to 5 (see PointCloudBVH): the box, the sorted keys, the tree's levels, the subtree sizes, boxes and depth-first indices, and the scans that place the rows and the groups.

template<class Source >
void	write (const Scratch &a_scratch, void *a_base, const Sizes &a_sizes, const Source &a_source, uint32_t a_numItems)
	Build step 6 (see PointCloudBVH): write the arrays reserved for the tree shape() gave.

template<class F >
void	run (std::size_t a_count, const F &a_f) const
	Run a build step: through GPU::parallelFor() for a build there, and in a host loop otherwise.

std::uint32_t	scan (std::uint32_t a_values, std::uint32_t a_count, std::uint32_t a_scratch) const
	An exclusive scan, where the build runs; see GPU::exclusiveScan().

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, const bool a_deviceWritten=false) 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.

Static Protected Member Functions inherited from EBGeometry::PointCloudDetail::CloudBVH< T, K, W, Prim >
static Sizes	sizesFor (uint32_t a_numItems, uint32_t a_leafSize, const char *a_who) noexcept
	Bounds on the array sizes of a build over `a_numItems` primitives.

static Scratch	reserveScratch (Pool &a_pool, uint32_t a_numItems, uint32_t a_leafSize, const char *a_who)
	Reserve a build's scratch from `a_pool`, for up to `a_numItems` primitives.

template<class U >
static std::vector< U >	toHost (const PODVector< U > &a_array, const void *a_base)
	Copy one pool-resident array back into a host std::vector.

Protected Attributes inherited from EBGeometry::PointCloudDetail::CloudBVH< T, K, W, Prim >
Packed::Layout	m_bvhLayout
	The packed BVH over the groups, as a layout: it shares this object's location.

PODVector< Item >	m_items
	The primitives, indexed by cloud index.

PODVector< std::uint32_t >	m_leafOff
	Per-primitive own-leaf group offset (for seeding).

PODVector< std::uint32_t >	m_leafCnt
	Per-primitive own-leaf group count (for seeding).

PODVector< std::uint32_t >	m_order
	Cloud indices in leaf (build) order; the spatially coherent batch-query order.

Scratch	m_scratch
	The scratch arrays a rebuild uses; empty for a BVH without room for one.

std::uint32_t	m_maxItems = 0
	The most primitives a rebuild can take, 0 for none.

std::uint32_t	m_leafSize = 0
	The largest leaf, max(a_targetLeafSize, K): a node of more primitives is cut.

std::uint32_t	m_depth = 0
	The tree's depth in node levels (the root is level 1), 0 for an empty cloud.

bool	m_parallel = false
	Whether the build runs through GPU::parallelFor() (the pool's memory is device-accessible).

Detailed Description

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

A BVH over spheres of differing radii (polydisperse particles), with the signed distance to their union and the closest sphere.

A shape: signedDistance() and computeBoundingVolume(), negative inside a sphere. The distance is min_i(|p - c_i| - r_i) over the spheres: exact outside their union, and inside it a bound in magnitude (where spheres overlap, the union's surface can be farther than every sphere's own), as for a Union of the spheres. Spheres of one radius need no SphereCloudBVH: the distance from a PointCloudBVH of the centers, less the radius, is the same.

The build is PointCloudBVH's linear build (see there), over the centers: the Morton keys and cuts come from the centers, and every box is grown by its spheres' radii. It runs where the pool's memory is, on a device included, and every side gives the same tree. The leaves are SphereAoSoA groups carrying each sphere's cloud index, which closestSphere() reports.

Note: Device portability, as for PointCloudBVH: the packed BVH and the cloud's arrays are reserved from one Pool and the class stores only offsets into it, so it is trivially copyable. Freeze and mirror the pool, call rebasedView(), and pass the value into a kernel; signedDistance(), closestSphere() and computeBoundingVolume() are device-callable. The pool must outlive the BVH and every copy of it.

Template Parameters

T	Floating-point precision.
K	BVH branching factor. Defaults to BVH::DefaultBranchingRatio<T>().
W	Spheres per SoA leaf group. Defaults to PointSoA::DefaultWidth<T>().

Constructor & Destructor Documentation

◆ SphereCloudBVH() [1/2]

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

EBGeometry::SphereCloudBVH< T, K, W >::SphereCloudBVH	(	Pool &	a_pool,
		const std::vector< Sphere > &	a_spheres,
		std::size_t	a_targetLeafSize = `16 *W`
	)

inline

Build a BVH over spheres on the host: shorthand for build(a_pool, a_spheres, a_targetLeafSize).

A sphere's cloud index, which the queries report, is its position in a_spheres.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive this object.
[in]	a_spheres	The spheres. At most 2^31; centers and radii finite, radii at least 0.
[in]	a_targetLeafSize	Target spheres per leaf. Must be at least 1.

◆ SphereCloudBVH() [2/2]

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

EBGeometry::SphereCloudBVH< T, K, W >::SphereCloudBVH	(	Pool &	a_pool,
		const std::vector< Vec3T< T > > &	a_centers,
		const std::vector< T > &	a_radii,
		std::size_t	a_targetLeafSize = `16 *W`
	)

inline

Build a BVH over spheres given as centers and radii, on the host: shorthand for build(a_pool, a_centers, a_radii, a_targetLeafSize).

A sphere's cloud index is its position in a_centers and a_radii.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive this object.
[in]	a_centers	The centers. At most 2^31, all finite.
[in]	a_radii	The radii, as many as the centers. All finite and at least 0.
[in]	a_targetLeafSize	Target spheres per leaf. Must be at least 1.

Member Function Documentation

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

◆ build() [1/3]

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

template<class Source >

static SphereCloudBVH EBGeometry::SphereCloudBVH< T, K, W >::build	(	Pool &	a_pool,
		const Source &	a_source,
		uint32_t	a_numSpheres,
		std::size_t	a_targetLeafSize = `16 *W`,
		uint32_t	a_maxSpheres = `0`
	)

inlinestatic

Build a BVH over spheres, where the pool's memory is.

As PointCloudBVH::build(), over the centers, with every box grown by the radii: it runs through GPU::parallelFor() for a pool in device-accessible memory (reading a_source on the device in a CUDA or HIP translation unit), and on the host otherwise, and both give the same tree. A sphere with a non-finite center or radius, or a negative radius, is rejected (on the host by its index). With a_maxSpheres, the arrays are reserved for any cloud of that many spheres, so that rebuild() reserves nothing and works on a frozen pool.

Template Parameters

Source A source of spheres: a trivially copyable type whose const call operator takes a cloud index (uint32_t) and returns that sphere; SphereCloud::FromArray, or SphereCloud::FromCentersAndRadii for centers and radii kept apart.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive the BVH.
[in]	a_source	The spheres.
[in]	a_numSpheres	Number of spheres. At most 2^31.
[in]	a_targetLeafSize	Target spheres per leaf (a node of at most max(a_targetLeafSize, K) spheres is a leaf). Must be at least 1.
[in]	a_maxSpheres	Most spheres a rebuild() may have; 0 for no rebuild(), and the arrays this cloud needs only. At least a_numSpheres otherwise.

Returns: The BVH.

◆ build() [2/3]

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

static SphereCloudBVH EBGeometry::SphereCloudBVH< T, K, W >::build	(	Pool &	a_pool,
		const std::vector< Sphere > &	a_spheres,
		std::size_t	a_targetLeafSize = `16 *W`,
		uint32_t	a_maxSpheres = `0`
	)

inlinestatic

Build a BVH over spheres on the host, where the pool's memory is; see the build() above.

For a pool in device memory, the spheres are first copied to scratch there.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive the BVH.
[in]	a_spheres	The spheres. At most 2^31; centers and radii finite, radii at least 0.
[in]	a_targetLeafSize	Target spheres per leaf. Must be at least 1.
[in]	a_maxSpheres	Most spheres a rebuild() may have (see the build() above).

Returns: The BVH.

◆ build() [3/3]

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

static SphereCloudBVH EBGeometry::SphereCloudBVH< T, K, W >::build	(	Pool &	a_pool,
		const std::vector< Vec3T< T > > &	a_centers,
		const std::vector< T > &	a_radii,
		std::size_t	a_targetLeafSize = `16 *W`,
		uint32_t	a_maxSpheres = `0`
	)

inlinestatic

Build a BVH over spheres given as centers and radii, on the host, where the pool's memory is; see the build() above.

For a pool in device memory, the centers and radii are first copied to scratch there.

Parameters

[in,out]	a_pool	Pool the BVH's arrays are reserved from; must outlive the BVH.
[in]	a_centers	The centers. At most 2^31, all finite.
[in]	a_radii	The radii, as many as the centers. All finite and at least 0.
[in]	a_targetLeafSize	Target spheres per leaf. Must be at least 1.
[in]	a_maxSpheres	Most spheres a rebuild() may have (see the build() above).

Returns: The BVH.

◆ closestSphere()

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

Hit EBGeometry::SphereCloudBVH< T, K, W >::closestSphere ( const Vec3T< T > & a_point ) const

inlinenoexcept

The sphere whose surface is nearest to a point, in the signed sense of signedDistance().

Ties go to the lower cloud index.

Parameters

[in] a_point Query point. Must be finite (checked only with assertions on).

Returns: The sphere's cloud index and the signed distance to its surface; a miss for an empty cloud.

◆ computeBoundingVolume()

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

AABB EBGeometry::SphereCloudBVH< T, K, W >::computeBoundingVolume ( ) const

inlinenoexcept

The box of all the spheres.

Returns: The root box: every sphere, grown by its radius. An empty box for an empty cloud.

◆ deepCopy()

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

SphereCloudBVH EBGeometry::SphereCloudBVH< T, K, W >::deepCopy ( Pool & a_dstPool ) const

inline

Duplicate this object's storage into a_dstPool.

Parameters

[in,out] a_dstPool Pool the copy's arrays are reserved from; must outlive the copy.

Returns: An independent BVH over the same spheres. It has no room for a rebuild().

◆ getBVH()

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

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

inlinenoexcept

The held packed BVH over the sphere groups.

Returns: A PackedBVH that shares this object's location.

◆ maxSpheres()

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

uint32_t EBGeometry::SphereCloudBVH< T, K, W >::maxSpheres ( ) const

inlinenoexcept

The most spheres rebuild() can take.

Returns: build()'s a_maxSpheres; 0 for a BVH built without room for a rebuild.

◆ numSpheres()

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

uint32_t EBGeometry::SphereCloudBVH< T, K, W >::numSpheres ( ) const

inlinenoexcept

Number of spheres in the cloud.

Returns: The number of spheres.

◆ rebasedView()

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

SphereCloudBVH EBGeometry::SphereCloudBVH< T, K, W >::rebasedView ( const Pool & a_pool ) const

inlinenoexcept

Produce a copy of this object that resolves against a_pool.

For a pool mirrored from this object's pool (Pool::mirror()): the returned value reads the mirror, on a device included. Copies nothing.

Parameters

[in] a_pool The pool to resolve against: this object's pool, or a mirror of it.

Returns: The view.

◆ rebuild()

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

template<class Source >

void EBGeometry::SphereCloudBVH< T, K, W >::rebuild	(	const Source &	a_source,
		uint32_t	a_numSpheres
	)

inline

Build the BVH again, in the arrays build() reserved, from new spheres.

As PointCloudBVH::rebuild(): the same tree as a new build() from these spheres, reserving nothing in the pool, so it works on a frozen pool. Needs room reserved by build()'s a_maxSpheres; more spheres than maxSpheres() is rejected. A view taken with rebasedView() before the rebuild still describes the old tree: take a new one. Call it on the BVH build() returned, not on a view or a deepCopy().

Template Parameters

Source A source of spheres, as for build().

Parameters

[in]	a_source	The spheres.
[in]	a_numSpheres	Number of spheres, at most maxSpheres().

◆ signedDistance()

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

T EBGeometry::SphereCloudBVH< T, K, W >::signedDistance ( const Vec3T< T > & a_point ) const

inlinenoexcept

Signed distance to the union of the spheres: min_i(|p - c_i| - r_i); see the class.

Parameters

[in] a_point Query point. Must be finite (checked only with assertions on).

Returns: The signed distance, negative inside a sphere; Math::Limits<T>::max() for an empty cloud.

◆ sphere()

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

Sphere EBGeometry::SphereCloudBVH< T, K, W >::sphere ( uint32_t a_index ) const

inlinenoexcept

The sphere with a cloud index.

Parameters

[in] a_index Cloud index, less than numSpheres().

Returns: The sphere.

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

Source/EBGeometry_SphereCloudBVH.hpp

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SphereCloudBVH() [1/2]

◆ SphereCloudBVH() [2/2]

Member Function Documentation

◆ base() [1/2]

◆ base() [2/2]

◆ build() [1/3]

◆ build() [2/3]

◆ build() [3/3]

◆ closestSphere()

◆ computeBoundingVolume()

◆ deepCopy()

◆ getBVH()

◆ maxSpheres()

◆ numSpheres()

◆ rebasedView()

◆ rebuild()

◆ signedDistance()

◆ sphere()