ezEngine  Milestone 7
ezDynamicQuadtree Class Reference

A loose Quadtree implementation that is very lightweight on RAM. More...

#include <DynamicQuadtree.h>

Public Member Functions

void CreateTree (const ezVec3 &vCenter, const ezVec3 &vHalfExtents, float fMinNodeSize)
 Initializes the tree with a fixed size and minimum node dimensions. More...
 
bool IsEmpty () const
 Returns true when there are no objects stored inside the tree.
 
ezUInt32 GetCount () const
 Returns the number of objects that have been inserted into the tree.
 
ezResult InsertObject (const ezVec3 &vCenter, const ezVec3 &vHalfExtents, ezInt32 iObjectType, ezInt32 iObjectInstance, ezDynamicTreeObject *out_Object=nullptr, bool bOnlyIfInside=false)
 Adds an object at position vCenter with bounding-box dimensions vHalfExtents to the tree. If the object is outside the tree and bOnlyIfInside is true, nothing will be inserted. More...
 
void FindVisibleObjects (const ezFrustum &Viewfrustum, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough=nullptr) const
 Returns all objects in the visible nodes through the callback.
 
void FindObjectsInRange (const ezVec3 &vPoint, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough=nullptr) const
 Returns all objects that are located in a node that overlaps with the given point. More...
 
void FindObjectsInRange (const ezVec3 &vPoint, float fRadius, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough=nullptr) const
 Returns all objects that are located in a node that overlaps with the rectangle with center vPoint and half edge length fRadius. More...
 
void RemoveObject (ezInt32 iObjectType, ezInt32 iObjectInstance)
 Removes the given Object. Attention: This is an O(n) operation.
 
void RemoveObject (ezDynamicTreeObject obj)
 Removes the given Object. This is an O(1) operation.
 
void RemoveObjectsOfType (ezInt32 iObjectType)
 Removes all Objects of the given Type. This is an O(n) operation.
 
void RemoveAllObjects ()
 Removes all Objects, but the tree stays intact.
 
const ezBoundingBoxGetBoundingBox () const
 Returns the tree's adjusted (square) AABB.
 

Private Member Functions

bool InsertObject (const ezVec3 &vCenter, const ezVec3 &vHalfExtents, const ezDynamicTree::ezObjectData &Obj, float minx, float maxx, float minz, float maxz, ezUInt32 uiNodeID, ezUInt32 uiAddID, ezUInt32 uiSubAddID, ezDynamicTreeObject *out_Object)
 Recursively checks in which node an object is located and stores it at the node where it fits best.
 
void FindVisibleObjects (const ezFrustum &Viewfrustum, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough, float minx, float maxx, float minz, float maxz, ezUInt32 uiNodeID, ezUInt32 uiAddID, ezUInt32 uiSubAddID, ezUInt32 uiNextNodeID) const
 Recursively checks which nodes are visible and calls the callback for each object at those nodes.
 
bool FindObjectsInRange (const ezVec3 &vPoint, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough, float minx, float maxx, float minz, float maxz, ezUInt32 uiNodeID, ezUInt32 uiAddID, ezUInt32 uiSubAddID, ezUInt32 uiNextNodeID) const
 Recursively checks in which node a point is located and calls the callback for all objects at those nodes.
 
bool FindObjectsInRange (const ezVec3 &vPoint, float fRadius, EZ_VISIBLE_OBJ_CALLBACK Callback, void *pPassThrough, float minx, float maxx, float minz, float maxz, ezUInt32 uiNodeID, ezUInt32 uiAddID, ezUInt32 uiSubAddID, ezUInt32 uiNextNodeID) const
 Recursively checks which node(s) a circle touches and calls the callback for all objects at those nodes.
 

Private Attributes

ezUInt32 m_uiMaxTreeDepth
 The tree depth, used for finding a nodes unique ID.
 
ezUInt32 m_uiAddIDTopLevel
 Also used for finding a nodes unique ID.
 
ezBoundingBox m_BBox
 The square bounding Box (to prevent long thin nodes)
 
float m_fRealMinX
 The actual bounding box (to discard objects that are outside the world)
 
float m_fRealMaxX
 
float m_fRealMinZ
 
float m_fRealMaxZ
 
ezUInt32 m_uiMultiMapCounter
 Used to turn the map into a multi-map.
 
ezMap
< ezDynamicTree::ezMultiMapKey,
ezDynamicTree::ezObjectData
m_NodeMap
 Every node has a unique index, the map allows to store many objects at each node, using that index.
 

Static Private Attributes

static const float s_LooseOctreeFactor = 1.1f
 The amount that cells overlap (this is a loose octree). Typically set to 10%.
 

Detailed Description

A loose Quadtree implementation that is very lightweight on RAM.

This Quadtree does not store any bookkeeping information per node.
Memory usage is linear in the number of objects inserted.
An empty tree only needs few bytes. This is accomplished by making the tree static in it's dimensions and maximum subdivisions, such that each node can be assigned a unique index. A map is then used to store objects through the node-index in which they are located.
At traversals each node's bounding-box needs to be computed on-the-fly thus adding some CPU overhead (though, fewer memory use usually also means fewer cache-misses).
Inserting an object is O(log d), with d being the tree-depth.
Removing an object is either O(1) or O(n), with n being the number of objects inserted, depending on whether an iterator to the object is available.

The nodes get indices in such a way that when it is detected, that a whole subtree is visible, all objects can be returned quickly, without further traversal.
If a subtree does not contain any data, traversal is not continued further, either.

In general this quadtree implementation is made to be very flexible and easily usable for many kinds of problems. All it stores are two integers for an object (GroupID, InstanceID). The object data itself must be stored somewhere else. You can easily store very different types of objects in the same tree.
Once objects are inserted, you can do range queries to find all objects in some location. Since removal is usually O(1) and insertion is O(d) the tree can be used for very dynamic data that changes frequently at run-time.

Member Function Documentation

void ezDynamicQuadtree::CreateTree ( const ezVec3 vCenter,
const ezVec3 vHalfExtents,
float  fMinNodeSize 
)

Initializes the tree with a fixed size and minimum node dimensions.

Parameters
vCenterThe center position of the tree.
vHalfExtentsThe dimensions along each axis. The tree is always axis aligned. The tree will enclose all space from (vCenter - vHalfExtents) to (vCenter + vHalfExtents). Note that the tree will always use the maximum extent for all three extents, making the tree square, which affects the total number of nodes.
However, the original (non-square) bounding box is used to determine whether some objects is inside the tree, at all, which might affect whether they are rejected during tree insertion.
fMinNodeSizeThe length of the cell's edges at the finest level. For a typical game world, where your level might have extents of 100 to 1000 meters, the min node size should not be smaller than 1 meter. The smaller the node size, the more cells the tree has. The limit of nodes in the tree is 2^32. A tree with 100 meters extents in X and Z direction and a min node size of 1 meter, will have 10000 nodes on the finest level (and roughly 15000 nodes in total).
void ezDynamicQuadtree::FindObjectsInRange ( const ezVec3 vPoint,
EZ_VISIBLE_OBJ_CALLBACK  Callback,
void *  pPassThrough = nullptr 
) const

Returns all objects that are located in a node that overlaps with the given point.

Note
This function will most likely also return objects that do not overlap with the point itself, because they are located in a node that overlaps with the point. You might need to do more thorough overlap checks to filter those out.
void ezDynamicQuadtree::FindObjectsInRange ( const ezVec3 vPoint,
float  fRadius,
EZ_VISIBLE_OBJ_CALLBACK  Callback,
void *  pPassThrough = nullptr 
) const

Returns all objects that are located in a node that overlaps with the rectangle with center vPoint and half edge length fRadius.

Note
This function will most likely also return objects that do not overlap with the rectangle itself, because they are located in a node that overlaps with the rectangle. You might need to do more thorough overlap checks to filter those out.
ezResult ezDynamicQuadtree::InsertObject ( const ezVec3 vCenter,
const ezVec3 vHalfExtents,
ezInt32  iObjectType,
ezInt32  iObjectInstance,
ezDynamicTreeObject *  out_Object = nullptr,
bool  bOnlyIfInside = false 
)

Adds an object at position vCenter with bounding-box dimensions vHalfExtents to the tree. If the object is outside the tree and bOnlyIfInside is true, nothing will be inserted.

Returns EZ_SUCCESS when an object is inserted, EZ_FAILURE when the object was rejected. The latter can only happen when bOnlyIfInside is set to true. Through out_Object the exact identifier for the object in the tree is returned, which allows for removing the object with O(1) complexity later. iObjectType and iObjectInstance are the two user values that will be stored for the object. With RemoveObjectsOfType() one can also remove all objects with the same iObjectType value, if needed.

The object lies at vCenter and has vHalfExtents as its bounding box. If bOnlyIfInside is false, the object is ALWAYS inserted, even if it is outside the tree.

Note
In such a case it is inserted at the root-node and thus ALWAYS returned in range/view-frustum queries.

If bOnlyIfInside is true, the object is discarded, if it is not inside the actual bounding box of the tree.

The min and max Y value of the tree's bounding box is updated, if the object lies above/below previously inserted objects.


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