Dynamic Tree

The dynamic tree is a binary AABB tree to organize and query large numbers of geometric objects. More...

Data Structures
struct	b3TreeNodeChildren
	Tree node child indices. For internal usage. More...
struct	b3TreeNode
	A node in the dynamic tree. More...
struct	b3DynamicTree
	The dynamic tree structure. More...
struct	b3TreeStats
	These are performance results returned by dynamic tree queries. More...
union	b3TreeNode.__unnamed0__
union	b3TreeNode.__unnamed1__

Macros
#define	B3_DYNAMIC_TREE_VERSION   0x93EDAF889FD30B4Aull
	Dynamic tree version for compatibility testing.

Typedefs
typedef bool	b3TreeQueryCallbackFcn(int proxyId, uint64_t userData, void *context)
	This function receives proxies found in the AABB query.
typedef float	b3TreeQueryClosestCallbackFcn(float distanceSqrMin, int proxyId, uint64_t userData, void *context)
	This function receives the minimum distance squared so far and proxy to check in the closest query.
typedef float	b3TreeBoxCastCallbackFcn(const b3BoxCastInput *input, int proxyId, uint64_t userData, void *context)
	This function receives clipped AABB cast input for a proxy.
typedef float	b3TreeRayCastCallbackFcn(const b3RayCastInput *input, int proxyId, uint64_t userData, void *context)
	This function receives clipped ray cast input for a proxy.

Enumerations
enum	b3TreeNodeFlags { b3_allocatedNode = 0x0001 , b3_enlargedNode = 0x0002 , b3_leafNode = 0x0004 }
	Flags for tree nodes. For internal usage.

Functions
b3DynamicTree	b3DynamicTree_Create (int proxyCapacity)
	Constructing the tree initializes the node pool.
void	b3DynamicTree_Destroy (b3DynamicTree *tree)
	Destroy the tree, freeing the node pool.
int	b3DynamicTree_CreateProxy (b3DynamicTree *tree, b3AABB aabb, uint64_t categoryBits, uint64_t userData)
	Create a proxy. Provide an AABB and a userData value.
void	b3DynamicTree_DestroyProxy (b3DynamicTree *tree, int proxyId)
	Destroy a proxy. This asserts if the id is invalid.
void	b3DynamicTree_MoveProxy (b3DynamicTree *tree, int proxyId, b3AABB aabb)
	Move a proxy to a new AABB by removing and reinserting into the tree.
void	b3DynamicTree_EnlargeProxy (b3DynamicTree *tree, int proxyId, b3AABB aabb)
	Enlarge a proxy and enlarge ancestors as necessary.
void	b3DynamicTree_SetCategoryBits (b3DynamicTree *tree, int proxyId, uint64_t categoryBits)
	Modify the category bits on a proxy. This is an expensive operation.
uint64_t	b3DynamicTree_GetCategoryBits (b3DynamicTree *tree, int proxyId)
	Get the category bits on a proxy.
b3TreeStats	b3DynamicTree_Query (const b3DynamicTree *tree, b3AABB aabb, uint64_t maskBits, bool requireAllBits, b3TreeQueryCallbackFcn *callback, void *context)
	Query an AABB for overlapping proxies.
b3TreeStats	b3DynamicTree_QueryClosest (const b3DynamicTree *tree, b3Vec3 point, uint64_t maskBits, bool requireAllBits, b3TreeQueryClosestCallbackFcn *callback, void *context, float *minDistanceSqr)
	Query an AABB for the closest object.
b3TreeStats	b3DynamicTree_RayCast (const b3DynamicTree *tree, const b3RayCastInput *input, uint64_t maskBits, bool requireAllBits, b3TreeRayCastCallbackFcn *callback, void *context)
	Ray cast against the proxies in the tree.
b3TreeStats	b3DynamicTree_BoxCast (const b3DynamicTree *tree, const b3BoxCastInput *input, uint64_t maskBits, bool requireAllBits, b3TreeBoxCastCallbackFcn *callback, void *context)
	Sweep an AABB through the tree.
void	b3DynamicTree_Validate (const b3DynamicTree *tree)
	Validate this tree. For testing.
int	b3DynamicTree_GetHeight (const b3DynamicTree *tree)
	Get the height of the binary tree.
float	b3DynamicTree_GetAreaRatio (const b3DynamicTree *tree)
	Get the ratio of the sum of the node areas to the root area.
b3AABB	b3DynamicTree_GetRootBounds (const b3DynamicTree *tree)
	Get the bounding box that contains the entire tree.
int	b3DynamicTree_GetProxyCount (const b3DynamicTree *tree)
	Get the number of proxies created.
int	b3DynamicTree_Rebuild (b3DynamicTree *tree, bool fullBuild)
	Rebuild the tree while retaining subtrees that haven't changed. Returns the number of boxes sorted.
int	b3DynamicTree_GetByteCount (const b3DynamicTree *tree)
	Get the number of bytes used by this tree.
void	b3DynamicTree_ValidateNoEnlarged (const b3DynamicTree *tree)
	Validate this tree has no enlarged AABBs. For testing.
void	b3DynamicTree_Save (const b3DynamicTree *tree, const char *fileName)
	Save this tree to a file for debugging.
b3DynamicTree	b3DynamicTree_Load (const char *fileName, float scale)
	Load a file for debugging.
uint64_t	b3DynamicTree_GetUserData (const b3DynamicTree *tree, int proxyId)
	Get proxy user data.
b3AABB	b3DynamicTree_GetAABB (const b3DynamicTree *tree, int proxyId)
	Get the AABB of a proxy.

Detailed Description

The dynamic tree is a binary AABB tree to organize and query large numbers of geometric objects.

Box3D uses the dynamic tree internally to sort collision shapes into a binary bounding volume hierarchy. This data structure may have uses in games for organizing other geometry data and may be used independently of Box3D rigid body simulation.

A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt. A dynamic tree arranges data in a binary tree to accelerate queries such as AABB queries and ray casts. Leaf nodes are proxies with an AABB. These are used to hold a user collision object. Nodes are pooled and relocatable, so I use node indices rather than pointers. The dynamic tree is made available for advanced users that would like to use it to organize spatial game data besides rigid bodies.

---

Data Structure Documentation

b3TreeNodeChildren

struct b3TreeNodeChildren

Tree node child indices. For internal usage.

Data Fields
int	child1	child node index 1
int	child2	child node index 2

b3DynamicTree

struct b3DynamicTree

The dynamic tree structure.

This should be considered private data. It is placed here for performance reasons.

Collaboration diagram for b3DynamicTree:

Data Fields
int *	binIndices	Bins for sorting during rebuild.
int	freeList	Node free list.
b3AABB *	leafBoxes	Leaf bounding boxes for rebuild.
b3Vec3 *	leafCenters	Leaf bounding box centers for rebuild.
int *	leafIndices	Leaf indices for rebuild.
int	nodeCapacity	The allocated node space.
int	nodeCount	The number of nodes.
b3TreeNode *	nodes	The tree nodes.
int	proxyCount	Number of proxies created.
int	rebuildCapacity	Allocated space for rebuilding.
int	root	The root index.
uint64_t	version	The dynamic tree version. Always the first field. Useful if the tree is serialized.

b3TreeStats

struct b3TreeStats

These are performance results returned by dynamic tree queries.

Data Fields
int	leafVisits	Number of leaf nodes visited during the query.
int	nodeVisits	Number of internal nodes visited during the query.

b3TreeNode.__unnamed0__

union b3TreeNode.__unnamed0__

Data Fields
b3TreeNodeChildren	children	Children (internal node).
uint64_t	userData	User data (leaf node).

b3TreeNode.__unnamed1__

union b3TreeNode.__unnamed1__

Data Fields
int	next	The node freelist next index (free node).
int	parent	The node parent index (allocated node).

Typedef Documentation

b3TreeBoxCastCallbackFcn

typedef float b3TreeBoxCastCallbackFcn(const b3BoxCastInput *input, int proxyId, uint64_t userData, void *context)

This function receives clipped AABB cast input for a proxy.

The function returns the new cast fraction.

• return a value of 0 to terminate the cast
• return a value less than input->maxFraction to clip the cast
• return a value of input->maxFraction to continue the cast without clipping

b3TreeQueryCallbackFcn

typedef bool b3TreeQueryCallbackFcn(int proxyId, uint64_t userData, void *context)

This function receives proxies found in the AABB query.

Returns

true if the query should continue

b3TreeQueryClosestCallbackFcn

typedef float b3TreeQueryClosestCallbackFcn(float distanceSqrMin, int proxyId, uint64_t userData, void *context)

This function receives the minimum distance squared so far and proxy to check in the closest query.

Returns

minimum distance squared to user objects in the proxy

b3TreeRayCastCallbackFcn

typedef float b3TreeRayCastCallbackFcn(const b3RayCastInput *input, int proxyId, uint64_t userData, void *context)

This function receives clipped ray cast input for a proxy.

The function returns the new ray fraction.

• return a value of 0 to terminate the ray cast
• return a value less than input->maxFraction to clip the ray
• return a value of input->maxFraction to continue the ray cast without clipping

Function Documentation

b3DynamicTree_BoxCast()

b3TreeStats b3DynamicTree_BoxCast	(	const b3DynamicTree *	tree,
		const b3BoxCastInput *	input,
		uint64_t	maskBits,
		bool	requireAllBits,
		b3TreeBoxCastCallbackFcn *	callback,
		void *	context )

Sweep an AABB through the tree.

The box is in the tree's world float frame and the callback re-differences each shape at full precision against the query origin. Used by the large world spatial queries so the tree traversal stays float while the narrow phase stays precise.

b3DynamicTree_Query()

b3TreeStats b3DynamicTree_Query	(	const b3DynamicTree *	tree,
		b3AABB	aabb,
		uint64_t	maskBits,
		bool	requireAllBits,
		b3TreeQueryCallbackFcn *	callback,
		void *	context )

Query an AABB for overlapping proxies.

The callback function is called for each proxy that overlaps the supplied AABB.

Returns

performance data

b3DynamicTree_QueryClosest()

b3TreeStats b3DynamicTree_QueryClosest	(	const b3DynamicTree *	tree,
		b3Vec3	point,
		uint64_t	maskBits,
		bool	requireAllBits,
		b3TreeQueryClosestCallbackFcn *	callback,
		void *	context,
		float *	minDistanceSqr )

Query an AABB for the closest object.

The callback function is called for each proxy that might be closest to the supplied point.

Parameters

tree	the dynamic tree to query
point	the query point
maskBits	nodes are skipped if the bit-wise AND with the node category bits is zero
requireAllBits	nodes are skipped if the bit-wise AND with the node category bits does not equal the maskBits
callback	a user provided instance of b3TreeQueryClosestCallbackFcn
context	a user context object that is provided to the callback
minDistanceSqr	the initial and final minimum squared distance. Provide a small initial to restrict the search and improve performance. If the value is large this query has performance that scales linearly with the number of proxies and would be slower than a brute force search.

Returns

performance data

b3DynamicTree_RayCast()

b3TreeStats b3DynamicTree_RayCast	(	const b3DynamicTree *	tree,
		const b3RayCastInput *	input,
		uint64_t	maskBits,
		bool	requireAllBits,
		b3TreeRayCastCallbackFcn *	callback,
		void *	context )

Ray cast against the proxies in the tree.

This relies on the callback to perform an exact ray cast in the case where the proxy contains a shape. The callback also performs any collision filtering. This has performance roughly equal to k * log(n), where k is the number of collisions and n is the number of proxies in the tree. Bit-wise filtering using mask bits can greatly improve performance in some scenarios. However, this filtering may be approximate, so the user should still apply filtering to results.

Parameters

tree	the dynamic tree to ray cast
input	the ray cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1)
maskBits	bit mask test: bool accept = (maskBits & node->categoryBits) != 0;
requireAllBits	modifies bit mask test: bool accept = (maskBits & node->categoryBits) == maskBits;
callback	a callback function that is called for each proxy that is hit by the ray
context	user context that is passed to the callback

Returns

performance data