HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_PointGrid< T > Class Template Reference

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< Titerator
 
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< TgetKeysAt (int x, int y, int z, queuetype &queue) const
 
UT_PointGridIterator< TgetInvalidKeys (queuetype &queue) const
 
UT_PointGridIterator< TfindCloseKeys (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_Vector3getVoxelSize () const
 Returns the voxel size of the underlying grid. More...
 

Static Public Member Functions

static queuetypecreateQueue ()
 
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< indextypemyBegins
 
UT_VoxelArray< indextypemyEnds
 
T myAccessor
 
UT_Vector3 myOrig
 
UT_Vector3 mySize
 
UT_Vector3 myVoxelSize
 
UT_Vector3 myInvVoxelSize
 
UT_Vector3T< intmyBBoxMin
 
UT_Vector3T< intmyBBoxMax
 

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  ,
 
)
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: