NL3D::CQuadGrid< T > Class Template Reference

This container is a simple grid, used to quickly find elements. More...

#include <quad_grid.h>

Classes
class	CBaseNode
	A base node (not circular) for the list of selected or unselected node. More...
class	CIterator
class	CNode
	An element inserted in the quadGrid. More...
class	const_iterator
class	CQuadNode
	A circular list node for the list of node per Quad element. More...
Public Types
typedef std::vector< uint >	TSelectionShape
Public Member Functions
	CQuadGrid (uint memoryBlockSize=NL3D_QUAD_GRID_ALLOC_BLOCKSIZE)
	Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1.
	~CQuadGrid ()
	dtor.
CQuadGrid< T > &	operator= (const CQuadGrid< T > &o)
	CQuadGrid (const CQuadGrid< T > &o)
Initialization

void	changeBase (const NLMISC::CMatrix &base)
	Change the base matrix of the quad grid.
void	create (uint size, float eltSize)
	Init the container.
const NLMISC::CMatrix &	getBasis () const
uint	getSize () const
float	getEltSize () const
Container operation

void	clear ()
	Clear the container.
CIterator	erase (CIterator it)
	Erase an interator from the container Speed is in O(1 * LH) where LH is the number of squares surrounded by the element.
CIterator	insert (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)
	Insert a new element in the container.
Selection

void	clearSelection ()
	Clear the selection list Speed is in O(Nelts).
void	selectAll ()
	Select all the container.
void	select (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
	Select element intersecting a bounding box.
void	selectRay (const NLMISC::CVector &rayStart, const NLMISC::CVector &rayEnd)
void	buildSelectionShape (TSelectionShape &dest, const NLMISC::CPolygon2D &poly) const
	Build a selection from a convex polygon.
void	select (const TSelectionShape &shape)
	Select element intersecting a selection shape.
CIterator	begin ()
	Return the first iterator of the selected element list.
CIterator	end ()
	Return the end iterator of the selected element list.
Private Member Functions
void	initCons ()
void	linkToRoot (CBaseNode &root, CBaseNode *ptr)
void	initSelectStamps () const
void	selectQuads (CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1)
void	addToSelection (CNode *ptr)
void	addQuadNodeToSelection (CQuadNode &quad)
Private Attributes
std::vector< CQuadNode >	_Grid
sint	_Size
sint	_SizePower
float	_EltSize
NLMISC::CMatrix	_ChangeBasis
CBaseNode	_SelectedList
CBaseNode	_UnSelectedList
NLMISC::CBlockMemory< CNode >	_NodeBlockMemory
Friends
class	CIterator

Detailed Description

template<class T>
class NL3D::CQuadGrid< T >

This container is a simple grid, used to quickly find elements.

His purpose is similiar to CQuadTree, but it is a simple grid, so test are in O(1), not in O(log n). It is perfect for local lookup (like in collisions). Use it if you want to select small area, not large. Also, for best use, elements should have approximatively the same size, and this size should be little smaller than the size of a grid element...

By default, the quad grid is aligned on XY. (unlike the quadtree!!!)

Unlike the quadtree, the quadgrid is NOT geographicly delimited, ie, its limits "tiles"!! This is why no "center" is required. As a direct consequence, when you select something, you are REALLY not sure that what you select is not a mile away from your selection :) ....

Also, for memory optimisation, no bbox is stored in the quadgrid. Hence no particular selection is made on the Z components...

For maximum allocation speed Efficiency, it uses a CBlockMemory<CNode> to allocate elements at insert(). DefaultBlockSize is 16, but you can change it at construction.

Author:: Lionel Berenguier; Nevrax France

Date:: 2000

Definition at line 87 of file quad_grid.h.

Member Typedef Documentation

template<class T>

typedef std::vector<uint> NL3D::CQuadGrid< T >::TSelectionShape

Definition at line 95 of file quad_grid.h.

Constructor & Destructor Documentation

template<class T >

NL3D::CQuadGrid< T >::CQuadGrid ( uint memoryBlockSize = NL3D_QUAD_GRID_ALLOC_BLOCKSIZE ) [inline]

Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1.

Definition at line 479 of file quad_grid.h.

References NL3D::CQuadGrid< T >::initCons().

template<class T >

NL3D::CQuadGrid< T >::~CQuadGrid ( ) [inline]

dtor.

Definition at line 580 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_Grid, and NL3D::CQuadGrid< T >::clear().

template<class T>

NL3D::CQuadGrid< T >::CQuadGrid ( const CQuadGrid< T > & o ) [inline]

Definition at line 485 of file quad_grid.h.

References NL3D::CQuadGrid< T >::initCons(), and NL3D::CQuadGrid< T >::operator=().

Member Function Documentation

template<class T>

void NL3D::CQuadGrid< T >::addQuadNodeToSelection ( CQuadNode & quad ) [inline, private]

Definition at line 384 of file quad_grid.h.

Referenced by NL3D::CQuadGrid< T >::select(), and NL3D::CQuadGrid< T >::selectRay().

template<class T>

void NL3D::CQuadGrid< T >::addToSelection ( CNode * ptr ) [inline, private]

Definition at line 365 of file quad_grid.h.

Referenced by NL3D::CQuadGrid< CPatchIdentEx >::addQuadNodeToSelection().

template<class T >

CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::begin ( void ) [inline]

Return the first iterator of the selected element list.

begin and end are valid till the next insert. Speed is in O(1)

Definition at line 880 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::CIterator, and NL3D::CQuadGrid< T >::CBaseNode::Next.

Referenced by NL3D::CLightingManager::addDynamicLight(), NL3D::CStaticQuadGrid< T >::build(), NL3D::CLandscape::buildPatchBlocksInBBox(), NL3D::CLandscape::buildTrianglesInBBox(), NL3D::CQuadGrid< T >::clear(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CShadowPolyReceiver::computeClippedTrisWithPolyClip(), NL3D::CLandscape::computeDynamicLighting(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CScene::findCameraClusterSystemFromRay(), NL3D::CClipTrav::fullSearch(), NL3D::CVisualCollisionManager::getCameraCollision(), NL3D::CShadowPolyReceiver::getCameraCollision(), NL3D::CLightingManager::getDynamicPointLightList(), NL3D::CMiniCol::getFaces(), NL3D::CMiniCol::getGroundNormal(), NL3D::CVisualCollisionManager::getMeshs(), NL3D::CVisualCollisionManager::getRayCollision(), NL3D::CInstanceLighter::processIGPointLightRT(), NL3D::CZoneLighter::processZonePointLightRT(), NL3D::CVisualCollisionManager::receiveShadowMap(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CLandscape::removeZone(), NL3D::CShadowPolyReceiver::render(), NL3D::CShadowMapManager::renderProject(), NL3D::CShadowPolyReceiver::renderSelection(), NL3D::CMiniCol::snapToGround(), and NL3D::CClipTrav::traverse().

template<class T >

void NL3D::CQuadGrid< T >::buildSelectionShape	(	TSelectionShape &	dest,
		const NLMISC::CPolygon2D &	poly
	)			const `[inline]`

Build a selection from a convex polygon.

The resulting selection can then be used for a subsequent call to 'select'

Definition at line 808 of file quad_grid.h.

References NL3D::CQuadGridBase::_AlreadySelected, NL3D::CQuadGrid< T >::_ChangeBasis, NL3D::CQuadGrid< T >::_EltSize, NL3D::CQuadGridBase::_PolyBorders, NL3D::CQuadGridBase::_ScaledPoly, NL3D::CQuadGridBase::_SelectStamp, NL3D::CQuadGrid< T >::_Size, NL3D::CQuadGrid< T >::_SizePower, NLMISC::CPolygon2D::computeOuterBorders(), NL3D::CQuadGrid< T >::initSelectStamps(), nlassert, and NLMISC::CPolygon2D::Vertices.

Referenced by NL3D::CShadowPolyReceiver::selectPolygon().

template<class T >

void NL3D::CQuadGrid< T >::changeBase ( const NLMISC::CMatrix & base ) [inline]

Change the base matrix of the quad grid.

For exemple this code init the grid tree in the plane XZ:

 CQuadGrid          grid;
 NLMISC::CMatrix        tmp;
 NLMISC::CVector        I(1,0,0);
 NLMISC::CVector        J(0,0,1);
 NLMISC::CVector        K(0,-1,0);

 tmp.identity();
 tmp.setRot(I,J,K, true);
 quadTree.changeBase (tmp);

Parameters:

base

Base of the quad grid

Definition at line 586 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_ChangeBasis.

Referenced by NL3D::CCubeGrid< TCell >::CCubeGrid(), and NL3D::CInstanceLighter::computeSunContribution().

template<class T >

void NL3D::CQuadGrid< T >::clear ( void ) [inline]

Clear the container.

Elements are deleted, but the quadgrid is not erased. Speed is in O(Nelts)

Definition at line 618 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::_UnSelectedList, NL3D::CQuadGrid< T >::begin(), NL3D::CQuadGrid< T >::end(), NL3D::CQuadGrid< T >::erase(), NL3D::CQuadGrid< T >::CBaseNode::Next, and NL3D::CQuadGrid< T >::selectAll().

Referenced by NL3D::CLandscape::clear(), NL3D::CShadowMapManager::clearAllShadowCasters(), NL3D::CLightingManager::clearDynamicLights(), NL3D::CQuadGrid< T >::create(), and NL3D::CQuadGrid< T >::~CQuadGrid().

template<class T >

void NL3D::CQuadGrid< T >::clearSelection ( ) [inline]

Clear the selection list Speed is in O(Nelts).

Definition at line 733 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_SelectedList, NL3D::CQuadGrid< T >::_UnSelectedList, NL3D::CQuadGrid< T >::linkToRoot(), NL3D::CQuadGrid< T >::CBaseNode::Next, and NL3D::CQuadGrid< T >::CBaseNode::Selected.

Referenced by NL3D::CStaticQuadGrid< T >::build(), NL3D::CLandscape::buildPatchBlocksInBBox(), NL3D::CLandscape::buildTrianglesInBBox(), NL3D::CLandscape::computeDynamicLighting(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CLandscape::removeZone(), NL3D::CQuadGrid< T >::select(), and NL3D::CQuadGrid< T >::selectRay().

template<class T >

void NL3D::CQuadGrid< T >::create	(	uint	size,
		float	eltSize
	)			`[inline]`

Init the container.

container is first clear() ed.

Parameters:

	size	is the width and the height of the initial quad tree, in number of square. For performance view, this should be a power of 2, and <=32768. (eg: 256,512, 8, 16 ...)
	eltSize	is the width and height of an element. Must be >0. Notice that the quadgrid MUST be square!!

Definition at line 591 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_EltSize, NL3D::CQuadGrid< T >::_Grid, NL3D::CQuadGrid< T >::_Size, NL3D::CQuadGrid< T >::_SizePower, NL3D::CQuadGrid< T >::clear(), NLMISC::getPowerOf2(), NLMISC::isPowerOf2(), and nlassert.

Referenced by NL3D::CClipTrav::CClipTrav(), NL3D::CLightingManager::CLightingManager(), NL3D::CMiniCol::CMiniCol(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CCubeGrid< TCell >::create(), NL3D::CShadowPolyReceiver::CShadowPolyReceiver(), NL3D::CVisualCollisionManager::CVisualCollisionManager(), NL3D::CLandscape::init(), NL3D::CQuadGrid< T >::initCons(), NL3D::CZoneLighter::makeQuadGridFromWaterShapes(), NL3D::CQuadGrid< T >::operator=(), and NL3D::CShadowMapManager::setQuadGridSize().

template<class T >

CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::end ( void ) [inline]

Return the end iterator of the selected element list.

begin and end are valid till the next insert. Speed is in O(1)

Definition at line 885 of file quad_grid.h.

References NL3D::CQuadGrid< T >::CIterator.

Referenced by NL3D::CStaticQuadGrid< T >::build(), NL3D::CLandscape::buildPatchBlocksInBBox(), NL3D::CLandscape::buildTrianglesInBBox(), NL3D::CQuadGrid< T >::clear(), NL3D::CZoneLighter::compilePointLightRT(), NL3D::CInstanceLighter::compilePointLightRT(), NL3D::CShadowPolyReceiver::computeClippedTrisWithPolyClip(), NL3D::CLandscape::computeDynamicLighting(), NL3D::CInstanceLighter::computeSunContribution(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CQuadGrid< T >::erase(), NL3D::CScene::findCameraClusterSystemFromRay(), NL3D::CClipTrav::fullSearch(), NL3D::CVisualCollisionManager::getCameraCollision(), NL3D::CShadowPolyReceiver::getCameraCollision(), NL3D::CLightingManager::getDynamicPointLightList(), NL3D::CMiniCol::getFaces(), NL3D::CMiniCol::getGroundNormal(), NL3D::CVisualCollisionManager::getMeshs(), NL3D::CVisualCollisionManager::getRayCollision(), NL3D::CInstanceLighter::processIGPointLightRT(), NL3D::CZoneLighter::processZonePointLightRT(), NL3D::CVisualCollisionManager::receiveShadowMap(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CShadowPolyReceiver::removeTriangle(), NL3D::CLandscape::removeZone(), NL3D::CShadowPolyReceiver::render(), NL3D::CShadowMapManager::renderProject(), NL3D::CShadowPolyReceiver::renderSelection(), NL3D::CMiniCol::snapToGround(), and NL3D::CClipTrav::traverse().

template<class T >

CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::erase ( typename CQuadGrid< T >::CIterator it ) [inline]

Erase an interator from the container Speed is in O(1 * L*H) where L*H is the number of squares surrounded by the element.

Parameters:

it

is the iterator to erase.

Returns:: if element is currently selected, the next selected element is returned, (or end()). if the element is not selected, end() is returned.

Definition at line 632 of file quad_grid.h.

Referenced by NL3D::CQuadGrid< T >::clear(), NL3D::CLightingManager::eraseStaticLightedModel(), NL3D::CMiniCol::removeLandScapePart(), NL3D::CVisualCollisionManager::removeMeshCollision(), NL3D::CShadowPolyReceiver::removeTriangle(), NL3D::CLandscape::removeZone(), and NL3D::CClipTrav::unregisterCluster().

template<class T>

const NLMISC::CMatrix& NL3D::CQuadGrid< T >::getBasis ( ) const [inline]

Definition at line 137 of file quad_grid.h.

Referenced by NL3D::CStaticQuadGrid< T >::build().

template<class T>

float NL3D::CQuadGrid< T >::getEltSize ( ) const [inline]

Definition at line 139 of file quad_grid.h.

Referenced by NL3D::CStaticQuadGrid< T >::build().

template<class T>

uint NL3D::CQuadGrid< T >::getSize ( void ) const [inline]

Definition at line 138 of file quad_grid.h.

Referenced by NL3D::CStaticQuadGrid< T >::build().

template<class T >

void NL3D::CQuadGrid< T >::initCons ( ) [inline, private]

Definition at line 494 of file quad_grid.h.

References NL3D::CQuadGrid< T >::_ChangeBasis, NL3D::CQuadGrid< T >::create(), and NLMISC::CMatrix::identity().

Referenced by NL3D::CQuadGrid< T >::CQuadGrid().

template<class T>

void NL3D::CQuadGrid< T >::initSelectStamps ( ) const [inline, private]

Definition at line 309 of file quad_grid.h.

Referenced by NL3D::CQuadGrid< T >::buildSelectionShape(), and NL3D::CQuadGrid< T >::selectRay().

template<class T>

CQuadGrid< T >::CIterator NL3D::CQuadGrid< T >::insert	(	const NLMISC::CVector &	bboxmin,
		const NLMISC::CVector &	bboxmax,
		const T &	val
	)			`[inline]`

Insert a new element in the container.

Speed is in O(1 * L*H) where L*H is the number of squares surrounded by the element

Warning! : bboxmin and bboxmax are multiplied by matrix setuped by changeBase. This work for any matrix with 90deg rotations (min and max are recomputed internally), but not with any rotation (43� ...) because of the nature of AABBox. To do this correclty you should compute the bbox min and max in the basis given in changeBase, and insert() with multiplying min and max with inverse of this basis. eg: CMatrix base= getSomeBase(); CMatrix invBase= base.inverted(); // create quadGrid. CQuadGrid<CTriangle> quadGrid; quadGrid.changeBase(base); quadGrid.create(...); // Insert a triangle tri correctly CAABBox bbox; bbox.setCenter(base * tri.V0); bbox.extend(base * tri.V1); bbox.extend(base * tri.V2); quadGrid.insert(invBase*bbox.getMin(), invBase*bbox.getMax(), tri);

Parameters:

	bboxmin	is the corner of the bounding box of the element to insert with minimal coordinates.
	bboxmax	is the corner of the bounding box of the element to insert with maximal coordinates.
	val	is a reference on the value to insert.

Definition at line 669 of file quad_grid.h.