A sparse 3D grid of point-based data. More...

Classes
class	BoxIterator

class	CellIterator
	Dereference to access the bounds() and size() [element count] of the underlying cell object. More...

class	Iterator

class	SphereIterator

Public Member Functions
	PointHashGrid (float radiusHint, const shared_ptr< MemoryManager > &m=MemoryManager::create())

	PointHashGrid (const Array< Value > &init, float radiusHint=-1.0f, const shared_ptr< MemoryManager > &m=MemoryManager::create())
	If radiusHint is negative, it is automatically chosen to put about 5 values in each grid cell (which means about 27 * 5 values for each beginIntersection call). More...

Iterator	begin () const
	Iterate through all members. More...

SphereIterator	begin (const Sphere &sphere) const
	Finds all values whose positions are within sphere. More...

BoxIterator	beginBoxIntersection (const AABox &box, bool exact=true) const
	Finds all values whose positions are within box. More...

CellIterator	beginCells () const
	Iterates through the non-empty cells. More...

void	clear (float radiusHint)

void	clear (bool shrink=true)
	Removes all data. More...

void	clearAndSetMemoryManager (const shared_ptr< MemoryManager > &m)

void	clearAndSetRadiusHint (float radiusHint)

const AABox &	conservativeBoxBounds () const
	Returns a conservative bounding box around the contents. More...

bool	contains (const Value &v) const
	Returns true if there is a value that is exactly equal to v. More...

float	debugGetAverageBucketSize () const

int	debugGetDeepestBucketSize () const

void	debugPrintStatistics () const

void	deleteAll ()
	Calls delete on all of the values, which are assumed to be pointers. More...

const Iterator &	end () const

const BoxIterator &	endBoxIntersection () const

const CellIterator &	endCells () const

void	getCellCoord (const Point3 &pos, Point3int32 &cellCoord) const
	Compute the grid cell index of a real position. More...

void	getIntersectingMembers (const Sphere &sphere, Array< Value > &result) const
	Appends results. More...

void	insert (const Value &v)
	Insert v at position p given by `getPosition(v, p)`. More...

void	insert (const Array< Value > &v)
	Inserts all elements of the array. More...

float	radiusHint () const

bool	remove (const Value &v, bool shrinkIfNecessary=true)
	If there are multiple copies of an element, you must delete them multiple times. More...

void	remove (const Array< Value > &v, bool shrink=true)
	Removes all elements of v. More...

int	size () const
	Returns the number of elements. More...

Protected Member Functions
void	initOffsetArray ()
	Initializes m_offsetArray. More...

Detailed Description

template<class Value, class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>
class G3D::PointHashGrid< Value, PosFunc, EqualsFunc >

A sparse 3D grid of point-based data.

The space cost for n elements is O(n). For data with approximately uniform density (with respect to the radius hint), the time cost of searching for neighbors is O(1).

You can move members of the data set by first removing them and then adding them with a new location.

Template argument PosFunc must provide a static getPosition method and EqualsFunc must provide a static equals method, as described below.
You can either write classes that support these yourself, provide template specializations of G3D::PositionTrait and G3D::EqualsTrait, or rely on the default template specializations, which already exist for common G3D classes like G3D::Point3. For example:

class PosFunc {
public:
    static void getPosition(const Data& d, Vector3& pos) {
        pos = d.location;
    }
};
class EqualsFunc {
public:
    static bool equals(const Data& p, const Data& q) {
        return p == q;
    }
};
PointHashGrid<Data, Data::PosFunc, Data::EqualsFunc> grid;

If the Value class defines operator==, then the Equalsfunc is optional, so you can just write:

PointHashGrid<Data, Data::PosFunc> grid;

The simplest way to define these is often to make them both methods of the parameter class itself, e.g.,

 class Data {
 public:
     Point3     location;
     ...
     bool operator==(const Data& other) const {
         return (location == other.location) && ...;
     }
     static void getPosition(const Data& p, Vector3& pos) {
         pos = p.location;
     } 
};
typedef PointHashGrid<Data, Data> DataGrid;

Constructor & Destructor Documentation

◆ PointHashGrid() [1/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::PointHashGrid	(	float	radiusHint,
		const shared_ptr< MemoryManager > &	m = `MemoryManager::create()`
	)

inline

Parameters

radiusHint the radius that will typically be used with beginBallIntersection and beginBoxIntersection. If two Values are equal, their positions must be within this radius as well. You can later change this value with clearAndSetRadiusHint().

◆ PointHashGrid() [2/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::PointHashGrid	(	const Array< Value > &	init,
		float	radiusHint = `-1.0f`,
		const shared_ptr< MemoryManager > &	m = `MemoryManager::create()`
	)

inline

If radiusHint is negative, it is automatically chosen to put about 5 values in each grid cell (which means about 27 * 5 values for each beginIntersection call).

See also: clearAndSetRadiusHint()

Member Function Documentation

◆ begin() [1/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

Iterator G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::begin ( ) const

inline

Iterate through all members.

It is an error to mutate the HashGrid while iterating through it. Each member can be accessed by "dereferencing" the iterator:

for (Grid::Iterator i = grid.begin(); i != grid.end(), ++i) {
const Value& = *i;
...
}

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::deleteAll(), and G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::getIntersectingMembers().

◆ begin() [2/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

SphereIterator G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::begin ( const Sphere & sphere ) const

inline

Finds all values whose positions are within sphere.

It is an error to mutate the PointHashGrid while iterating through it.

◆ beginBoxIntersection()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

BoxIterator G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::beginBoxIntersection	(	const AABox &	box,
		bool	exact = `true`
	)		const

inline

Finds all values whose positions are within box.

It is an error to mutate the PointHashGrid while iterating through it.

Parameters

exact If false, the iterator will execute more quickly but will likely return some values that lie outside the box. Set exact = false if you are going to test the results against the yourself box anyway.

◆ beginCells()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

CellIterator G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::beginCells ( ) const

inline

Iterates through the non-empty cells.

This is intended primarily for debugging and visualizing the data structure.

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clear().

◆ clear() [1/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clear ( float radiusHint )

inline

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clearAndSetRadiusHint(), and G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::deleteAll().

◆ clear() [2/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clear ( bool shrink = true )

inline

Removes all data.

Parameters

shrink If true, underlying structures are deallocated as they are freed.

◆ clearAndSetMemoryManager()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clearAndSetMemoryManager ( const shared_ptr< MemoryManager > & m )

inline

◆ clearAndSetRadiusHint()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clearAndSetRadiusHint ( float radiusHint )

inline

◆ conservativeBoxBounds()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

const AABox& G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::conservativeBoxBounds ( ) const

inline

Returns a conservative bounding box around the contents.

This is conservative because it is not updated when elements are removed.

◆ contains()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

bool G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::contains ( const Value & v ) const

inline

Returns true if there is a value that is exactly equal to v.

This will check all neighboring cells to avoid roundoff error at cell boundaries.

◆ debugGetAverageBucketSize()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

float G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::debugGetAverageBucketSize ( ) const

inline

◆ debugGetDeepestBucketSize()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

int G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::debugGetDeepestBucketSize ( ) const

inline

◆ debugPrintStatistics()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::debugPrintStatistics ( ) const

inline

◆ deleteAll()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::deleteAll ( )

inline

Calls delete on all of the values, which are assumed to be pointers.

This is a helper to avoid requiring you to iterate through the data structure, removing and deleting each one. Clears the PointHashGrid at the end.

Using objects (instead of pointers) or reference counted pointers is recommended over using pointers and this deleteAll method.

◆ end()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

const Iterator& G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::end ( ) const

inline

◆ endBoxIntersection()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

const BoxIterator& G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::endBoxIntersection ( ) const

inline

◆ endCells()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

const CellIterator& G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::endCells ( ) const

inline

◆ getCellCoord()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::getCellCoord	(	const Point3 &	pos,
		Point3int32 &	cellCoord
	)		const

inline

Compute the grid cell index of a real position.

This is used extensively internally by PointHashGrid. It is useful to calling code to determine when an object is about to move between cells.

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::insert().

◆ getIntersectingMembers()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::getIntersectingMembers	(	const Sphere &	sphere,
		Array< Value > &	result
	)		const

inline

Appends results.

◆ initOffsetArray()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::initOffsetArray ( )

inlineprotected

Initializes m_offsetArray.

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::PointHashGrid().

◆ insert() [1/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::insert ( const Value & v )

inline

Insert v at position p given by getPosition(v, p).

Multiple elements that are equal may be inserted; all copies will be in the data structure.

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::insert(), and G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::PointHashGrid().

◆ insert() [2/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::insert ( const Array< Value > & v )

inline

Inserts all elements of the array.

◆ radiusHint()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

float G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::radiusHint ( ) const

inline

See also: clearAndSetRadiusHint()

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clear(), G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::clearAndSetRadiusHint(), and G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::PointHashGrid().

◆ remove() [1/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

bool G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::remove	(	const Value &	v,
		bool	shrinkIfNecessary = `true`
	)

inline

If there are multiple copies of an element, you must delete them multiple times.

Parameters

shrinkIfNecessary If true, deallocate underlying data structures as they are emptied. False increases performace at the cost of memory overhead for dynamic structures.

Returns: true if the element was found.

◆ remove() [2/2]

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

void G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::remove	(	const Array< Value > &	v,
		bool	shrink = `true`
	)

inline

Removes all elements of v.

◆ size()

template<class Value , class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>

int G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::size ( ) const

inline

Returns the number of elements.

Referenced by G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::insert().

Classes

Public Member Functions

Protected Member Functions

Detailed Description

template<class Value, class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>> class G3D::PointHashGrid< Value, PosFunc, EqualsFunc >

Constructor & Destructor Documentation

◆ PointHashGrid() [1/2]

◆ PointHashGrid() [2/2]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ beginBoxIntersection()

◆ beginCells()

◆ clear() [1/2]

◆ clear() [2/2]

◆ clearAndSetMemoryManager()

◆ clearAndSetRadiusHint()

◆ conservativeBoxBounds()

◆ contains()

◆ debugGetAverageBucketSize()

◆ debugGetDeepestBucketSize()

◆ debugPrintStatistics()

◆ deleteAll()

◆ end()

◆ endBoxIntersection()

◆ endCells()

◆ getCellCoord()

◆ getIntersectingMembers()

◆ initOffsetArray()

◆ insert() [1/2]

◆ insert() [2/2]

◆ radiusHint()

◆ remove() [1/2]

◆ remove() [2/2]

◆ size()

template<class Value, class PosFunc = PositionTrait<Value>, class EqualsFunc = EqualsTrait<Value>>
class G3D::PointHashGrid< Value, PosFunc, EqualsFunc >