Inheritance diagram for DtOctree< T >:

Public Types
typedef std::map< T , DtOctreeMember< T > >	MemberContainer
	Container and iterator typedefs for the STL structures used.
typedef std::map< T , DtOctreeMember< T > >::iterator	MemberIterator
typedef std::list< T * >	OutsideAreaContainer
typedef std::list< T * >::iterator	OutsideAreaIterator

Public Member Functions
	DtOctree (const DtExtent &region)
	Constructor. The extent covered by an octree may not be changed once the octree is created.
virtual	~DtOctree ()
	Destructor. Deletes the octree and any members in it (though not the corresponding objects).
virtual void	visitObjects (const DtExtent &extent, DtSpatialSelectionFunctor &callback)
	Call the given functor for every member that shares a node with the specified extent.
virtual void	addObject (T *object, const DtExtent &extent)
	TODO: Add search key to outside octree list so that objects which fall completely outside the octree region can be filtered out of searches completely within.
virtual void	removeObject (T *object)
	Remove a member from the octree.
virtual void	updatePositions ()
	Process any updates to the objects' positions that have happened since they were added to the octree.
bool	containsObject (T *object)
int	numObjects ()
int	numObjectsOutside ()

Protected Member Functions
bool	removeObjectOutsideArea (T *object)

Protected Attributes
DtOctreeNode< T > *	myRootNode
	Root node of the octree.
OutsideAreaContainer	myObjectsOutsideArea
	List of objects which are at least partially outside the octree's root extent.
MemberContainer	myMemberMap
	Mapping of T* pointers to DtOctreeMember objects in the tree.
unsigned int	mySearchKey

Detailed Description

template<class T>
class DtOctree< T >

DtOctree class.

DtOctree implements an octree, for storing arbitary objects with extents in a way that makes it fast to enumerate objects that intersect a specified extent.

Currently there's some sloppiness in the implementation which will make it difficult to specialize this template to objects other than DtVrfObjects, but it's good to keep that sloppiness to a minimum, as this class would be useful for other things (notably terrain triangles).

The outer octree class does attempt to deal with objects which are outside the octree's defined region, but it does not do so efficiently.

Member Typedef Documentation

template<class T>

typedef std::map<T*, DtOctreeMember<T>*> DtOctree< T >::MemberContainer

Container and iterator typedefs for the STL structures used.

template<class T>

typedef std::map<T*, DtOctreeMember<T>*>::iterator DtOctree< T >::MemberIterator

template<class T>

typedef std::list<T*> DtOctree< T >::OutsideAreaContainer

template<class T>

typedef std::list<T*>::iterator DtOctree< T >::OutsideAreaIterator

Constructor & Destructor Documentation

template<class T>

DtOctree< T >::DtOctree ( const DtExtent & region )

inline

Constructor. The extent covered by an octree may not be changed once the octree is created.

template<class T>

virtual DtOctree< T >::~DtOctree ( )

inlinevirtual

Destructor. Deletes the octree and any members in it (though not the corresponding objects).

Member Function Documentation

template<class T>

virtual void DtOctree< T >::visitObjects	(	const DtExtent &	extent,
		DtSpatialSelectionFunctor &	callback
	)

inlinevirtual

Call the given functor for every member that shares a node with the specified extent.

This does not test for exact intersection; it only iterates over any objects that might intersect the given extent (i.e. there may be extras).

template<class T>

virtual void DtOctree< T >::addObject	(	T *	object,
		const DtExtent &	extent
	)

inlinevirtual

TODO: Add search key to outside octree list so that objects which fall completely outside the octree region can be filtered out of searches completely within.

Add a member to the octree.

template<class T>

virtual void DtOctree< T >::removeObject ( T * object )

inlinevirtual

Remove a member from the octree.

Referenced by DtOctree< DtVrfObject >::updatePositions().

template<class T>

virtual void DtOctree< T >::updatePositions ( )

inlinevirtual

Process any updates to the objects' positions that have happened since they were added to the octree.

If members' extents change, they will still be returned from visitMembers() as if they held the old position until this function is called. Once this function is called, objects will intersect using the newly-specified positions (until the function is called again, obviously).

template<class T>

bool DtOctree< T >::containsObject ( T * object )

inline

template<class T>

int DtOctree< T >::numObjects ( )

inline

template<class T>

int DtOctree< T >::numObjectsOutside ( )

inline

template<class T>

bool DtOctree< T >::removeObjectOutsideArea ( T * object )

inlineprotected