 |
VR-Forces 4.8 Class Documentation
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
|
VR-Forces 4.8 Class Documentation
|
Octree support. More...
Protected Types | |
| typedef std::list < DtOctreeMember< T > * > | MemberContainer |
| This class is only for use from DtOctree and DtOctreeDebugger. More... | |
| typedef std::list < DtOctreeMember< T > * >::iterator | MemberIterator |
Protected Member Functions | |
| DtOctreeNode (const DtExtent ®ion, const unsigned int depth) | |
| Constructor. The extent covered by an octree node may not be changed once the octree is created. More... | |
| ~DtOctreeNode () | |
| Destructor. No DtOctreeMember objects are deleted. More... | |
| virtual void | visitObjects (const unsigned int key, const DtExtent &extent, DtSpatialSelectionFunctorTemplate< T > &callback) |
| Call the given functor for every member that shares a node with the specified extent. More... | |
| virtual void | addMember (DtOctreeMember< T > *member, int &depth) |
| Add a member to this node or one of its children (splitting the node if necessary). More... | |
| bool | coalesceEmptyChildren () |
| Look for any empty, childless nodes and coalesce them up to their parents. More... | |
| int | numChildCandidates () |
| Return the number of members of this node that can go into child nodes. More... | |
| 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. More... | |
| void | addMemberToChild (DtOctreeMember< T > *member, int childIndex, int &depth) |
| Add a member to a child of this node, creating the child if necessary. More... | |
| void | split (int &depth) |
| Create child nodes to hold all the members that can go into child nodes, and move those members into the child nodes. More... | |
Protected Attributes | |
| const DtExtent | myRegion |
| The region intersecting members contained by this node (and this node's children). More... | |
| const DtPoint | myCenter |
| The center of myRegion. More... | |
| unsigned int | myDepth |
| DtOctreeNode< T > ** | myChildren |
| Child nodes of this node, if any. More... | |
| MemberContainer | myMembers |
| Members which are in this node. More... | |
Static Protected Attributes | |
| static int | sNumNodes = 0 |
| static const int | MAX_NUM_NODES = 1000 |
Friends | |
| template<class U > | |
| class | DtOctree |
| template<class U > | |
| class | DtOctreeMember |
| template<class U > | |
| class | DtOctreeDebugger |
Octree support.
DtOctreeNode class.
There are several classes defined in this file:
DtOctreeMember - holds data about a single object (currently always a DtVrfObject*) in the octree DtOctreeNode - represents a node in the octree; holds pointers to child nodes and members of that node DtOctree - the top-level interface to the octree functionality (this is the only class external users of this file need to use) DtOctreeDebugger - a subclass of DtOctree that adds some self-check functionality
So DtOctrees contain a tree of DtOctreeNode instances, each of which contains a list of DtOctreeMember instances, each of which contains one member (a DtVrfObject*).
DtOctreeMember objects are owned (created and deleted) by the DtOctree code.
You should use createOctree() to get a new octree object. You should delete the object when you're done with it.
You may define OCTREE_DEBUG in this file to 1 to turn on octree debugging, in which case you'll get a DtOctreeDebugger instance from createOctree(), and your log will be filled with very copious breadcrumbs.
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]
|
protected |
This class is only for use from DtOctree and DtOctreeDebugger.
|
protected |
|
inlineprotected |
Constructor. The extent covered by an octree node may not be changed once the octree is created.
Referenced by DtOctreeNode< const DtVrfObject >::addMemberToChild().
|
inlineprotected |
Destructor. No DtOctreeMember objects are deleted.
|
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.
|
inlineprotectedvirtual |
Add a member to this node or one of its children (splitting the node if necessary).
|
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< const DtVrfObject >::coalesceEmptyChildren().
|
inlineprotected |
Return the number of members of this node that can go into child nodes.
Referenced by DtOctreeNode< const DtVrfObject >::addMember().
|
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< const DtVrfObject >::addMember(), DtOctreeNode< const DtVrfObject >::numChildCandidates(), DtOctreeNode< const DtVrfObject >::split(), and DtOctreeNode< const DtVrfObject >::visitObjects().
|
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< const DtVrfObject >::addMember(), and DtOctreeNode< const DtVrfObject >::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< const DtVrfObject >::addMember().
|
friend |
|
staticprotected |
|
staticprotected |
Referenced by DtOctreeNode< const DtVrfObject >::addMember().
|
protected |
The region intersecting members contained by this node (and this node's children).
Referenced by DtOctreeNode< const DtVrfObject >::addMember(), DtOctreeNode< const DtVrfObject >::addMemberToChild(), DtOctreeNode< const DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< const DtVrfObject >::split(), DtOctreeNode< const DtVrfObject >::visitObjects(), and DtOctreeNode< const DtVrfObject >::~DtOctreeNode().
|
protected |
The center of myRegion.
Referenced by DtOctreeNode< const DtVrfObject >::addMemberToChild(), and DtOctreeNode< const DtVrfObject >::intersectionMask().
|
protected |
Referenced by DtOctreeNode< const DtVrfObject >::addMemberToChild().
|
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< const DtVrfObject >::addMember(), DtOctreeNode< const DtVrfObject >::addMemberToChild(), DtOctreeNode< const DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< const DtVrfObject >::split(), DtOctreeNode< const DtVrfObject >::visitObjects(), and DtOctreeNode< const DtVrfObject >::~DtOctreeNode().
|
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< const DtVrfObject >::coalesceEmptyChildren(), DtOctreeNode< const DtVrfObject >::numChildCandidates(), DtOctreeNode< const DtVrfObject >::split(), DtOctreeMember< T >::unbind(), and DtOctreeNode< const DtVrfObject >::visitObjects().