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

#include <DynamicQuadtree.h>

Public Member Functions
void	CreateTree (const plVec3 &vCenter, const plVec3 &vHalfExtents, float fMinNodeSize)
	Initializes the tree with a fixed size and minimum node dimensions.

bool	IsEmpty () const
	Returns true when there are no objects stored inside the tree.

plUInt32	GetCount () const
	Returns the number of objects that have been inserted into the tree.

plResult	InsertObject (const plVec3 &vCenter, const plVec3 &vHalfExtents, plInt32 iObjectType, plInt32 iObjectInstance, plDynamicTreeObject *out_pObject=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.

void	FindVisibleObjects (const plFrustum &viewfrustum, PL_VISIBLE_OBJ_CALLBACK callback, void *pPassThrough=nullptr) const
	Returns all objects in the visible nodes through the callback.

void	FindObjectsInRange (const plVec3 &vPoint, PL_VISIBLE_OBJ_CALLBACK callback, void *pPassThrough=nullptr) const
	Returns all objects that are located in a node that overlaps with the given point.

void	FindObjectsInRange (const plVec3 &vPoint, float fRadius, PL_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.

void	RemoveObject (plInt32 iObjectType, plInt32 iObjectInstance)
	Removes the given Object. Attention: This is an O(n) operation.

void	RemoveObject (plDynamicTreeObject obj)
	Removes the given Object. This is an O(1) operation.

void	RemoveObjectsOfType (plInt32 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 plBoundingBox &	GetBoundingBox () const
	Returns the tree's adjusted (square) AABB.

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

◆ CreateTree()

void plDynamicQuadtree::CreateTree	(	const plVec3 &	vCenter,
		const plVec3 &	vHalfExtents,
		float	fMinNodeSize )

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

Parameters

vCenter	The center position of the tree.
vHalfExtents	The 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.
fMinNodeSize	The 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).

◆ FindObjectsInRange() [1/2]

void plDynamicQuadtree::FindObjectsInRange	(	const plVec3 &	vPoint,
		float	fRadius,
		PL_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.

◆ FindObjectsInRange() [2/2]

void plDynamicQuadtree::FindObjectsInRange	(	const plVec3 &	vPoint,
		PL_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.

◆ InsertObject()

plResult plDynamicQuadtree::InsertObject	(	const plVec3 &	vCenter,
		const plVec3 &	vHalfExtents,
		plInt32	iObjectType,
		plInt32	iObjectInstance,
		plDynamicTreeObject *	out_pObject = 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 PL_SUCCESS when an object is inserted, PL_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: