Lock-free spatial acceleration structure with atomic snapshot publication. More...

#include <SpatialIndex.hpp>

Collaboration diagram for MayaFlux::Kinesis::SpatialIndex< PointT >:

Public Types
using	DistanceFn = std::function< float(const PointT &, const PointT &)>

Public Member Functions
std::vector< std::pair< uint32_t, PointT > >	all () const
	Return all entity ids and positions from the published snapshot.

void	clear ()
	Remove all entities from the write side.

size_t	count () const
	Entity count in the published snapshot.

uint32_t	insert (const PointT &position)
	Insert a new entity at the given position.

std::vector< QueryResult >	k_nearest (const PointT &center, uint32_t k) const
	Find the k nearest entities to a point.

SpatialIndex &	operator= (const SpatialIndex &)=delete

SpatialIndex &	operator= (SpatialIndex &&)=delete

std::optional< PointT >	position_of (uint32_t id) const
	Read the position of an entity from the published snapshot.

void	publish ()
	Atomically publish the current write-side state as a new read snapshot.

void	remove (uint32_t id)
	Remove an entity from the index.

	SpatialIndex (const SpatialIndex &)=delete

	SpatialIndex (float cell_size, DistanceFn distance)
	Construct a spatial index.

	SpatialIndex (SpatialIndex &&)=delete

void	update (uint32_t id, const PointT &position)
	Move an existing entity to a new position.

std::vector< QueryResult >	within_radius (const PointT &center, float radius) const
	Find all entities within a radius of a point.

	~SpatialIndex ()

Private Member Functions
uint64_t	hash_cell (const PointT &p) const

void	query_brute (const SpatialSnapshot< PointT > &snap, const PointT &center, float radius_sq, std::vector< QueryResult > &out) const

void	query_grid (const SpatialSnapshot< PointT > &snap, const PointT &center, float radius_sq, std::vector< QueryResult > &out) const

void	rebuild_grid (SpatialSnapshot< PointT > &snap) const

Private Attributes
float	m_cell_size

DistanceFn	m_distance_fn

std::vector< uint32_t >	m_free_slots

std::unordered_map< uint32_t, uint32_t >	m_id_to_slot

float	m_inv_cell

uint32_t	m_next_id { 0 }

std::vector< PointT >	m_positions

std::vector< uint32_t >	m_slot_to_id

std::atomic< std::shared_ptr< const SpatialSnapshot< PointT > > >	m_snapshot

bool	m_use_grid { true }

Detailed Description

template<typename PointT>
class MayaFlux::Kinesis::SpatialIndex< PointT >

Lock-free spatial acceleration structure with atomic snapshot publication.

Template Parameters

PointT Coordinate type. glm::vec3 for 3D scenes, Eigen::VectorXd for N-dimensional descriptor spaces.

Single-writer thread (typically graphics) calls insert(), update(), remove(), then publish() once per frame. Any reader thread (typically audio) calls within_radius() or k_nearest() against the last published snapshot with no synchronization overhead.

Backed by a uniform spatial hash grid for PointT = glm::vec3, and brute-force scan for PointT = Eigen::VectorXd with dimensionality > 6. Grid cell neighbor enumeration scales as 3^D, so the grid is only practical for low dimensionality.

Publication model: Non-macOS: std::atomic<std::shared_ptr<const SpatialSnapshot<PointT>>> macOS: raw atomic pointer with hazard pointer array (Apple Clang lacks std::atomic<std::shared_ptr<T>>)

Definition at line 104 of file SpatialIndex.hpp.

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description