Iteration over a range of elements This class implements a point-in-grid acceleration structure that does a multithreaded build to handle large particle counts and provides linear time lookups into the grid structure. It's similar in spirit to particle acceleration techniques used on GPUs: Green, Simon. Particle Simulation using CUDA. CUDA 4.0 SDK. More...

#include <UT_PointGrid.h>

Classes
class	ut_isGridIdxLess

Public Types
typedef T::indextype	indextype

typedef T::keytype	keytype

typedef exint	grididxtype

typedef T	accessortype

typedef UT_PointGridIterator< T >	iterator

typedef UT_PointGridIterator < T >::queuetype	queuetype

Public Member Functions
	UT_PointGrid (const T &accessor)

bool	build (const UT_Vector3 &orig, const UT_Vector3 &size, int xres, int yres, int zres)

bool	canBuild (int xres, int yres, int zres)

UT_PointGridIterator< T >	getKeysAt (int x, int y, int z, queuetype &queue) const

UT_PointGridIterator< T >	getInvalidKeys (queuetype &queue) const

UT_PointGridIterator< T >	findCloseKeys (const UT_Vector3 &position, queuetype &queuetype, fpreal radius) const

bool	hasCloseKeys (const UT_Vector3 &position, fpreal radius) const

exint	entries () const
	Returns the total number of points. More...

exint	entriesAt (int x, int y, int z) const
	Returns number of points contained in a given voxel. More...

bool	posToIndex (UT_Vector3 position, int &x, int &y, int &z, bool boundsCheck=true) const

bool	isValidIndex (int x, int y, int z) const
	Returns true if the specified index is valid for the underlying grid. More...

int64	getMemoryUsage () const
	Returns the total memory usage (in bytes) of the grid. More...

keytype	getKeyAt (indextype idx) const
	Returns the key at the specified index. More...

int	getXRes () const
	X-resolution of the underlying grid. More...

int	getYRes () const
	Y-resolution of the underlying grid. More...

int	getZRes () const
	Z-resolution of the underlying grid. More...

int	getRes (int axis) const
	Resolution of the underlying grid along the specified axis. More...

const UT_Vector3 &	getVoxelSize () const
	Returns the voxel size of the underlying grid. More...

Static Public Member Functions
static queuetype *	createQueue ()

static void	destroyQueue (queuetype *queue)
	Destroys a queue created with createQueue(). More...

Protected Member Functions
bool	getKeysAt (int x, int y, int z, indextype &begin, indextype &end) const

	SYS_PACKED_STRUCT_HINT_BEGIN (UT_GridIdxKey, 4)

SYS_PACKED_STRUCT_HINT_END grididxtype	indexToGridIdx (int x, int y, int z)

void	gridIdxToIndex (grididxtype idx, int &x, int &y, int &z)

bool	calcBounds (const UT_Vector3 &pos, fpreal radius, int &xmin, int &ymin, int &zmin, int &xmax, int &ymax, int &zmax) const

bool	shouldMultithread () const

	THREADED_METHOD1 (UT_PointGrid< T >, shouldMultithread(), computeGridIdx, UT_ValArray< bool > &, tileoccupied)

void	computeGridIdxPartial (UT_ValArray< bool > &tileoccupied, const UT_JobInfo &info)

	THREADED_METHOD3 (UT_PointGrid< T >, shouldMultithread(), findIdxRanges, UT_ValArray< UT_Vector3T< int > > &, bboxmins, UT_ValArray< UT_Vector3T< int > > &, bboxmaxs, indextype, numValidKeys)

void	findIdxRangesPartial (UT_ValArray< UT_Vector3T< int > > &bboxmins, UT_ValArray< UT_Vector3T< int > > &bboxmaxs, indextype numValidKeys, const UT_JobInfo &info)

	THREADED_METHOD1 (UT_PointGrid< T >, tileoccupied.entries() > 20, uncompressTiles, const UT_ValArray< bool > &, tileoccupied)

void	uncompressTilesPartial (const UT_ValArray< bool > &tileoccupied, const UT_JobInfo &info)

Protected Attributes
UT_ValArray< UT_GridIdxKey >	myIdxKeys

UT_VoxelArray< indextype >	myBegins

UT_VoxelArray< indextype >	myEnds

T	myAccessor

UT_Vector3	myOrig

UT_Vector3	mySize

UT_Vector3	myVoxelSize

UT_Vector3	myInvVoxelSize

UT_Vector3T< int >	myBBoxMin

UT_Vector3T< int >	myBBoxMax

Static Protected Attributes
static const indextype	INVALIDINDEX = std::numeric_limits<typename UT_PointGrid<T>::indextype>::max()

static const grididxtype	INVALIDGRIDIDX = std::numeric_limits<typename UT_PointGrid<T>::grididxtype>::max()

Detailed Description

template<typename T>
class UT_PointGrid< T >

Iteration over a range of elements This class implements a point-in-grid acceleration structure that does a multithreaded build to handle large particle counts and provides linear time lookups into the grid structure. It's similar in spirit to particle acceleration techniques used on GPUs: Green, Simon. Particle Simulation using CUDA. CUDA 4.0 SDK.

Definition at line 21 of file UT_PointGrid.h.

Member Typedef Documentation

template<typename T>

typedef T UT_PointGrid< T >::accessortype

Definition at line 115 of file UT_PointGrid.h.

template<typename T>

typedef exint UT_PointGrid< T >::grididxtype

Definition at line 113 of file UT_PointGrid.h.

template<typename T>

typedef T::indextype UT_PointGrid< T >::indextype

The index and key type for the point grid, derived from the accessor type.

Definition at line 110 of file UT_PointGrid.h.

template<typename T>

typedef UT_PointGridIterator<T> UT_PointGrid< T >::iterator

Definition at line 116 of file UT_PointGrid.h.

template<typename T>

typedef T::keytype UT_PointGrid< T >::keytype

Definition at line 111 of file UT_PointGrid.h.

template<typename T>

typedef UT_PointGridIterator<T>::queuetype UT_PointGrid< T >::queuetype

Definition at line 117 of file UT_PointGrid.h.

Constructor & Destructor Documentation

template<typename T>

UT_PointGrid< T >::UT_PointGrid ( const T & accessor )

inline

Create a point grid with the specified accessor.

Note: The point grid is not valid until build() is called.

Definition at line 101 of file UT_PointGrid.h.

Member Function Documentation

template<typename T >

bool UT_PointGrid< T >::build	(	const UT_Vector3 &	orig,
		const UT_Vector3 &	size,
		int	xres,
		int	yres,
		int	zres
	)

Constructs the point grid over the specified world-space coordinates and resolution. The points will be read from the accessor provided when the object was created.

Note: This function asserts on canBuild(), to catch the case that the indextype or keytype types can not represent the number of points or the size of the grid.

Definition at line 341 of file UT_PointGridImpl.h.

template<typename T >

bool UT_PointGrid< T >::calcBounds	(	const UT_Vector3 &	pos,
		fpreal	radius,
		int &	xmin,
		int &	ymin,
		int &	zmin,
		int &	xmax,
		int &	ymax,
		int &	zmax
	)		const

protected

Definition at line 563 of file UT_PointGridImpl.h.

template<typename T >

bool UT_PointGrid< T >::canBuild	(	int	xres,
		int	yres,
		int	zres
	)

Returns true if all point elements will fit into the specified indextype and keytpe data types without overflow, given the provided resolution.

Definition at line 463 of file UT_PointGridImpl.h.

template<typename T >

void UT_PointGrid< T >::computeGridIdxPartial	(	UT_ValArray< bool > &	tileoccupied,
		const UT_JobInfo &	info
	)

protected

Definition at line 172 of file UT_PointGridImpl.h.

template<typename T>

static queuetype* UT_PointGrid< T >::createQueue ( )

inlinestatic

Creates a queue that can be used for querying this point grid. Any number of queueus can be created for a point grid, but only one iterator can use a particular queue at a time. Typically each thread in a multithreaded operation will have its own queue.

Definition at line 203 of file UT_PointGrid.h.

template<typename T>

static void UT_PointGrid< T >::destroyQueue ( queuetype * queue )

inlinestatic

Destroys a queue created with createQueue().

Definition at line 206 of file UT_PointGrid.h.

template<typename T>

exint UT_PointGrid< T >::entries ( ) const

inline

Returns the total number of points.

Definition at line 164 of file UT_PointGrid.h.

template<typename T >

exint UT_PointGrid< T >::entriesAt	(	int	x,
		int	y,
		int	z
	)		const

Returns number of points contained in a given voxel.

Definition at line 490 of file UT_PointGridImpl.h.

template<typename T >

UT_PointGridIterator< T > UT_PointGrid< T >::findCloseKeys	(	const UT_Vector3 &	position,
		queuetype &	queuetype,
		fpreal	radius
	)		const

Queries the grid voxels within radius of position. Returns an iterator over the keys corresponding to the points.

Note: The iterator will be created rewound. It may return keys from points that are in the voxels but outside the provided radius. The caller must cull these out manually if so desired.; The queue object should be created with createQueue(), and only one iterator at a time can be created with a particular queue.

Definition at line 597 of file UT_PointGridImpl.h.

template<typename T >

void UT_PointGrid< T >::findIdxRangesPartial	(	UT_ValArray< UT_Vector3T< int > > &	bboxmins,
		UT_ValArray< UT_Vector3T< int > > &	bboxmaxs,
		indextype	numValidKeys,
		const UT_JobInfo &	info
	)

protected

Definition at line 241 of file UT_PointGridImpl.h.

template<typename T >

UT_PointGridIterator< T > UT_PointGrid< T >::getInvalidKeys ( queuetype & queue ) const

Returns an iterator over all points that have invalid keys or did not fit in the bounding box of the grid.

Note: The iterator will be created rewound.; The queue object should be created with createQueue(), and only one iterator at a time can be created with a particular queue.

Definition at line 537 of file UT_PointGridImpl.h.

template<typename T>

keytype UT_PointGrid< T >::getKeyAt ( indextype idx ) const

inline

Returns the key at the specified index.

Definition at line 185 of file UT_PointGrid.h.

template<typename T >

UT_PointGridIterator< T > UT_PointGrid< T >::getKeysAt	(	int	x,
		int	y,
		int	z,
		queuetype &	queue
	)		const

Returns an iterator over the points occupying the grid voxel at the specified index.

Note: The iterator will be created rewound.; The queue object should be created with createQueue(), and only one iterator at a time can be created with a particular queue.

Definition at line 520 of file UT_PointGridImpl.h.

template<typename T>

bool UT_PointGrid< T >::getKeysAt	(	int	x,
		int	y,
		int	z,
		indextype &	begin,
		indextype &	end
	)		const

protected

template<typename T >

int64 UT_PointGrid< T >::getMemoryUsage ( ) const

Returns the total memory usage (in bytes) of the grid.

Definition at line 160 of file UT_PointGridImpl.h.

template<typename T>

int UT_PointGrid< T >::getRes ( int axis ) const

inline

Resolution of the underlying grid along the specified axis.

Definition at line 194 of file UT_PointGrid.h.

template<typename T>

const UT_Vector3& UT_PointGrid< T >::getVoxelSize ( ) const

inline

Returns the voxel size of the underlying grid.

Definition at line 197 of file UT_PointGrid.h.

template<typename T>

int UT_PointGrid< T >::getXRes ( ) const

inline

X-resolution of the underlying grid.

Definition at line 188 of file UT_PointGrid.h.

template<typename T>

int UT_PointGrid< T >::getYRes ( ) const

inline

Y-resolution of the underlying grid.

Definition at line 190 of file UT_PointGrid.h.

template<typename T>

int UT_PointGrid< T >::getZRes ( ) const

inline

Z-resolution of the underlying grid.

Definition at line 192 of file UT_PointGrid.h.

template<typename T>

void UT_PointGrid< T >::gridIdxToIndex	(	grididxtype	idx,
		int &	x,
		int &	y,
		int &	z
	)

protected

Definition at line 146 of file UT_PointGridImpl.h.

template<typename T >

bool UT_PointGrid< T >::hasCloseKeys	(	const UT_Vector3 &	position,
		fpreal	radius
	)		const

Returns true if any voxels within radius of the position contain points.

Definition at line 638 of file UT_PointGridImpl.h.

template<typename T >

UT_PointGrid< T >::grididxtype UT_PointGrid< T >::indexToGridIdx	(	int	x,
		int	y,
		int	z
	)

protected

Definition at line 138 of file UT_PointGridImpl.h.

template<typename T>

bool UT_PointGrid< T >::isValidIndex	(	int	x,
		int	y,
		int	z
	)		const

inline

Returns true if the specified index is valid for the underlying grid.

Definition at line 176 of file UT_PointGrid.h.

template<typename T >

bool UT_PointGrid< T >::posToIndex	(	UT_Vector3	position,
		int &	x,
		int &	y,
		int &	z,
		bool	boundsCheck = `true`
	)		const

Convert a world space position to a grid index. Always returns true if boundsCheck is false, else returns true only if the index is valid for the grid

Definition at line 113 of file UT_PointGridImpl.h.

template<typename T>

bool UT_PointGrid< T >::shouldMultithread ( ) const

inlineprotected

Definition at line 248 of file UT_PointGrid.h.

template<typename T>

UT_PointGrid< T >::SYS_PACKED_STRUCT_HINT_BEGIN	(	UT_GridIdxKey	,
		4
	)

inlineprotected

Definition at line 222 of file UT_PointGrid.h.

template<typename T>

UT_PointGrid< T >::THREADED_METHOD1	(	UT_PointGrid< T >	,
		shouldMultithread()	,
		computeGridIdx	,
		UT_ValArray< bool > &	,
		tileoccupied
	)

protected

template<typename T>

UT_PointGrid< T >::THREADED_METHOD1	(	UT_PointGrid< T >	,
		tileoccupied.	entries(),
		20	,
		uncompressTiles	,
		const UT_ValArray< bool > &	,
		tileoccupied
	)

protected

template<typename T>

UT_PointGrid< T >::THREADED_METHOD3	(	UT_PointGrid< T >	,
		shouldMultithread()	,
		findIdxRanges	,
		UT_ValArray< UT_Vector3T< int > > &	,
		bboxmins	,
		UT_ValArray< UT_Vector3T< int > > &	,
		bboxmaxs	,
		indextype	,
		numValidKeys
	)

protected

template<typename T >

void UT_PointGrid< T >::uncompressTilesPartial	(	const UT_ValArray< bool > &	tileoccupied,
		const UT_JobInfo &	info
	)

protected

Definition at line 219 of file UT_PointGridImpl.h.

Member Data Documentation

template<typename T>

const UT_PointGrid< T >::grididxtype UT_PointGrid< T >::INVALIDGRIDIDX = std::numeric_limits<typename UT_PointGrid<T>::grididxtype>::max()

staticprotected

Definition at line 210 of file UT_PointGrid.h.

template<typename T>

const UT_PointGrid< T >::indextype UT_PointGrid< T >::INVALIDINDEX = std::numeric_limits<typename UT_PointGrid<T>::indextype>::max()

staticprotected

Definition at line 209 of file UT_PointGrid.h.

template<typename T>

T UT_PointGrid< T >::myAccessor

protected

Definition at line 280 of file UT_PointGrid.h.

template<typename T>

UT_Vector3T<int> UT_PointGrid< T >::myBBoxMax

protected

Definition at line 285 of file UT_PointGrid.h.

template<typename T>

UT_Vector3T<int> UT_PointGrid< T >::myBBoxMin

protected

Definition at line 285 of file UT_PointGrid.h.

template<typename T>

UT_VoxelArray<indextype> UT_PointGrid< T >::myBegins

protected

Definition at line 279 of file UT_PointGrid.h.

template<typename T>

UT_VoxelArray<indextype> UT_PointGrid< T >::myEnds

protected

Definition at line 279 of file UT_PointGrid.h.

template<typename T>

UT_ValArray<UT_GridIdxKey> UT_PointGrid< T >::myIdxKeys

protected

Definition at line 278 of file UT_PointGrid.h.

template<typename T>

UT_Vector3 UT_PointGrid< T >::myInvVoxelSize

protected

Definition at line 284 of file UT_PointGrid.h.

template<typename T>

UT_Vector3 UT_PointGrid< T >::myOrig

protected

Definition at line 281 of file UT_PointGrid.h.

template<typename T>

UT_Vector3 UT_PointGrid< T >::mySize

protected

Definition at line 282 of file UT_PointGrid.h.

template<typename T>

UT_Vector3 UT_PointGrid< T >::myVoxelSize

protected

Definition at line 283 of file UT_PointGrid.h.

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

UT/UT_PointGrid.h
UT/UT_PointGridImpl.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

template<typename T> class UT_PointGrid< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class UT_PointGrid< T >