Inheritance diagram for DtOctreeNode< T >:

Protected Types
typedef std::list < DtOctreeMember< T > * >	MemberContainer
	This class is only for use from DtOctree and DtOctreeDebugger.
typedef std::list < DtOctreeMember< T > * >::iterator	MemberIterator

Protected Member Functions
	DtOctreeNode (const DtExtent &region)
	Constructor. The extent covered by an octree node may not be changed once the octree is created.
	~DtOctreeNode ()
	Destructor. No DtOctreeMember objects are deleted.
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	addMember (DtOctreeMember< T > *member)
	Add a member to this node or one of its children (splitting the node if necessary).
bool	coalesceEmptyChildren ()
	Look for any empty, childless nodes and coalesce them up to their parents.
int	numChildCandidates ()
	Return the number of members of this node that can go into child nodes.
int	intersectionMask (const DtExtent &extent) const
	Returns a bit-mask where the ith bit is set iff the ith child of this node intersects the specified extent.
int	childIndexFor (int mask)
	Convert an intersection mask that only indicates intersection with one child to the index of that child.
void	addMemberToChild (DtOctreeMember< T > *member, int childIndex)
	Add a member to a child of this node, creating the child if necessary.
void	split ()
	Create child nodes to hold all the members that can go into child nodes, and move those members into the child nodes.

Protected Attributes
const DtExtent	myRegion
	The region intersecting members contained by this node (and this node's children).
const DtPoint	myCenter
	The center of myRegion.
DtOctreeNode< T > **	myChildren
	Child nodes of this node, if any.
MemberContainer	myMembers
	Members which are in this node.

Static Protected Attributes
static const int	NUM_BRANCHES = 8
	The number of children of each node. Don't change this without rewriting everything.
static const int	MAX_CHILD_MEMBERS = 10
	The maximum length of myChildMembers; see implementation notes at the top of the class.

Friends
class	DtOctree
class	DtOctreeMember
class	DtOctreeDebugger

Detailed Description

template<class T>
class DtOctreeNode< T >

DtOctreeNode class.

This class implements nodes of the octree. Each node corresponds to a region (hopefully a cube) in space, contains a collection of objects which reside completely within that region, and may contain up to eight child nodes, each of which covers one of the eight subregions made by dividing the region along the X/Y/Z planes through the region's center. If there are children, then any objects that can go completely into a child do.

This octree implementation will perform poorly (but correctly) if objects are added outside the root extent, or if many small objects intersect the boundaries between large octree nodes (for example, if an octree is created from [-1000, -1000, -1000] to [1000, 1000, 1000], and many small objects are added with their Z-coordinate set to 0, all those objects will go into the root node, and all intersection calls will return all those objects). It is highly recommended to avoid both of those situations.

Children of an octree node are assigned indices which correspond to their positions in space. The union of the regions of the children of a node is equal to the region of that node. This is the mapping from child indices to regions of space (for a node covering [-1, -1, -1] - [1, 1, 1]):

0 = [-1, -1, -1] - [ 0, 0, 0] 1 = [-1, -1, 0] - [ 0, 0, 1] 2 = [-1, 0, -1] - [ 0, 1, 0] 3 = [-1, 0, 0] - [ 0, 1, 1] 4 = [ 0, -1, -1] - [ 1, 0, 0] 5 = [ 0, -1, 0] - [ 1, 0, 1] 6 = [ 0, 0, -1] - [ 1, 1, 0] 7 = [ 0, 0, 0] - [ 1, 1, 1]

Member Typedef Documentation

template<class T>

typedef std::list<DtOctreeMember<T>*> DtOctreeNode< T >::MemberContainer

protected

This class is only for use from DtOctree and DtOctreeDebugger.

template<class T>

typedef std::list<DtOctreeMember<T>*>::iterator DtOctreeNode< T >::MemberIterator

protected

Constructor & Destructor Documentation

template<class T>

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

inlineprotected

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

Referenced by DtOctreeNode< DtVrfObject >::addMemberToChild().

template<class T>

DtOctreeNode< T >::~DtOctreeNode ( )

inlineprotected

Destructor. No DtOctreeMember objects are deleted.

Member Function Documentation

template<class T>

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

inlineprotectedvirtual

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

This does not test for exact intersection; it only returns a list of objects that might intersect the given extent.

It is assumed that the given extent does intersect myRegion, and that condition is not checked within this function, for speed. Performance will be poor if the two do not intersect. The calling code should verify that the requested extent does intersect the specified region before calling this function.

template<class T>

virtual void DtOctreeNode< T >::addMember ( DtOctreeMember< T > * member )

inlineprotectedvirtual

Add a member to this node or one of its children (splitting the node if necessary).

template<class T>

bool DtOctreeNode< T >::coalesceEmptyChildren ( )

inlineprotected

Look for any empty, childless nodes and coalesce them up to their parents.

Returns true if this node can now be deleted (i.e. if there's no member at this node or anywhere lower in the tree)

Referenced by DtOctreeNode< DtVrfObject >::coalesceEmptyChildren().

template<class T>

int DtOctreeNode< T >::numChildCandidates ( )

inlineprotected

Return the number of members of this node that can go into child nodes.

Referenced by DtOctreeNode< DtVrfObject >::addMember().

template<class T>

int DtOctreeNode< T >::intersectionMask ( const DtExtent & extent ) const

inlineprotected

Returns a bit-mask where the ith bit is set iff the ith child of this node intersects the specified extent.

The specified extent is assumed to intersect this node's region at some point; otherwise the result will be incorrect.

See the top-level class documentation for how indexing of children works.

Referenced by DtOctreeNode< DtVrfObject >::addMember(), DtOctreeNode< DtVrfObject >::numChildCandidates(), DtOctreeNode< DtVrfObject >::split(), and DtOctreeNode< DtVrfObject >::visitObjects().

template<class T>

int DtOctreeNode< T >::childIndexFor ( int mask )

inlineprotected

Convert an intersection mask that only indicates intersection with one child to the index of that child.

Returns -1 for an intersection mask that indicates intersection with other than exactly one child. See the top-level class documentation for how indexing of children works.

Referenced by DtOctreeNode< DtVrfObject >::addMember(), DtOctreeNode< DtVrfObject >::numChildCandidates(), and DtOctreeNode< DtVrfObject >::split().

template<class T>

void DtOctreeNode< T >::addMemberToChild	(	DtOctreeMember< T > *	member,
		int	childIndex
	)

inlineprotected

Add a member to a child of this node, creating the child if necessary.

This function will call addMember() on the child, so it is okay if the child is not the final destination for this member.

Referenced by DtOctreeNode< DtVrfObject >::addMember(), and DtOctreeNode< DtVrfObject >::split().

template<class T>

void DtOctreeNode< T >::split ( )

inlineprotected

Create child nodes to hold all the members that can go into child nodes, and move those members into the child nodes.

Referenced by DtOctreeNode< DtVrfObject >::addMember().

Friends And Related Function Documentation

template<class T>

friend class DtOctree

friend

template<class T>

friend class DtOctreeMember

friend

template<class T>

friend class DtOctreeDebugger

friend

Member Data Documentation

template<class T>

const int DtOctreeNode< T >::NUM_BRANCHES = 8

staticprotected

The number of children of each node. Don't change this without rewriting everything.

Referenced by DtOctreeNode< DtVrfObject >::childIndexFor(), DtOctreeNode< DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< DtVrfObject >::split(), DtOctreeNode< DtVrfObject >::visitObjects(), and DtOctreeNode< DtVrfObject >::~DtOctreeNode().

template<class T>

const int DtOctreeNode< T >::MAX_CHILD_MEMBERS = 10

staticprotected

The maximum length of myChildMembers; see implementation notes at the top of the class.

Referenced by DtOctreeNode< DtVrfObject >::addMember().

template<class T>

const DtExtent DtOctreeNode< T >::myRegion

protected

The region intersecting members contained by this node (and this node's children).

Referenced by DtOctreeNode< DtVrfObject >::addMember(), DtOctreeNode< DtVrfObject >::addMemberToChild(), DtOctreeNode< DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< DtVrfObject >::split(), DtOctreeNode< DtVrfObject >::visitObjects(), and DtOctreeNode< DtVrfObject >::~DtOctreeNode().

template<class T>

const DtPoint DtOctreeNode< T >::myCenter

protected

The center of myRegion.

Referenced by DtOctreeNode< DtVrfObject >::addMemberToChild(), and DtOctreeNode< DtVrfObject >::intersectionMask().

template<class T>

DtOctreeNode<T>** DtOctreeNode< T >::myChildren

protected

Child nodes of this node, if any.

This is NULL for a childless node. For nodes with children, this is an 8-element array of DtOctreeNode pointers, each of which is NULL if the specified child does not exist.

Referenced by DtOctreeNode< DtVrfObject >::addMember(), DtOctreeNode< DtVrfObject >::addMemberToChild(), DtOctreeNode< DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< DtVrfObject >::split(), DtOctreeNode< DtVrfObject >::visitObjects(), and DtOctreeNode< DtVrfObject >::~DtOctreeNode().

template<class T>

MemberContainer DtOctreeNode< T >::myMembers

protected

Members which are in this node.

If myChildren is not NULL, then this must not contain any members that could go into a child node.

Referenced by DtOctreeMember< T >::bind(), DtOctreeNode< DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< DtVrfObject >::numChildCandidates(), DtOctreeNode< DtVrfObject >::split(), and DtOctreeNode< DtVrfObject >::visitObjects().

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

/exports/nfedora7-1/nightly/docs/vrforcesDevelopment.tot/include/vrfobjcore/octree.h

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Detailed Description

template<class T> class DtOctreeNode< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T>
class DtOctreeNode< T >