#include <b2_dynamic_tree.h>

Public Member Functions
	b2DynamicTree ()
	Constructing the tree initializes the node pool. More...

void	ClearMoved (int32 proxyId)

int32	CreateProxy (const b2AABB &aabb, void *userData)
	Create a proxy. Provide a tight fitting AABB and a userData pointer. More...

void	DestroyProxy (int32 proxyId)
	Destroy a proxy. This asserts if the id is invalid. More...

float	GetAreaRatio () const
	Get the ratio of the sum of the node areas to the root area. More...

const b2AABB &	GetFatAABB (int32 proxyId) const
	Get the fat AABB for a proxy. More...

int32	GetHeight () const

int32	GetMaxBalance () const

void *	GetUserData (int32 proxyId) const

bool	MoveProxy (int32 proxyId, const b2AABB &aabb1, const b2Vec2 &displacement)

template<typename T >
void	Query (T *callback, const b2AABB &aabb) const

template<typename T >
void	RayCast (T *callback, const b2RayCastInput &input) const

void	RebuildBottomUp ()
	Build an optimal tree. Very expensive. For testing. More...

void	ShiftOrigin (const b2Vec2 &newOrigin)

void	Validate () const
	Validate this tree. For testing. More...

bool	WasMoved (int32 proxyId) const

	~b2DynamicTree ()
	Destroy the tree, freeing the node pool. More...

Private Member Functions
int32	AllocateNode ()

int32	Balance (int32 index)

int32	ComputeHeight () const

int32	ComputeHeight (int32 nodeId) const

void	FreeNode (int32 node)

void	InsertLeaf (int32 node)

void	RemoveLeaf (int32 node)

void	ValidateMetrics (int32 index) const

void	ValidateStructure (int32 index) const

Private Attributes
int32	m_freeList

int32	m_insertionCount

int32	m_nodeCapacity

int32	m_nodeCount

b2TreeNode *	m_nodes

int32	m_root

Detailed Description

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 volume queries and ray casts. Leafs are proxies with an AABB. In the tree we expand the proxy AABB by b2_fatAABBFactor so that the proxy AABB is bigger than the client object. This allows the client object to move by small amounts without triggering a tree update.

Nodes are pooled and relocatable, so we use node indices rather than pointers.

Definition at line 68 of file b2_dynamic_tree.h.

Constructor & Destructor Documentation

◆ b2DynamicTree()

b2DynamicTree::b2DynamicTree ( )

Constructing the tree initializes the node pool.

Definition at line 25 of file b2_dynamic_tree.cpp.

◆ ~b2DynamicTree()

b2DynamicTree::~b2DynamicTree ( )

Destroy the tree, freeing the node pool.

Definition at line 47 of file b2_dynamic_tree.cpp.

Member Function Documentation

◆ AllocateNode()

int32 b2DynamicTree::AllocateNode ( )

private

Definition at line 54 of file b2_dynamic_tree.cpp.

◆ Balance()

int32 b2DynamicTree::Balance ( int32 index )

private

Definition at line 398 of file b2_dynamic_tree.cpp.

◆ ClearMoved()

void b2DynamicTree::ClearMoved ( int32 proxyId )

inline

Definition at line 175 of file b2_dynamic_tree.h.

◆ ComputeHeight() [1/2]

int32 b2DynamicTree::ComputeHeight ( ) const

private

Definition at line 594 of file b2_dynamic_tree.cpp.

◆ ComputeHeight() [2/2]

int32 b2DynamicTree::ComputeHeight ( int32 nodeId ) const

private

Definition at line 579 of file b2_dynamic_tree.cpp.

◆ CreateProxy()

int32 b2DynamicTree::CreateProxy	(	const b2AABB &	aabb,
		void *	userData
	)

Create a proxy. Provide a tight fitting AABB and a userData pointer.

Definition at line 107 of file b2_dynamic_tree.cpp.

◆ DestroyProxy()

void b2DynamicTree::DestroyProxy ( int32 proxyId )

Destroy a proxy. This asserts if the id is invalid.

Definition at line 124 of file b2_dynamic_tree.cpp.

◆ FreeNode()

void b2DynamicTree::FreeNode ( int32 node )

private

Definition at line 94 of file b2_dynamic_tree.cpp.

◆ GetAreaRatio()

float b2DynamicTree::GetAreaRatio ( ) const

Get the ratio of the sum of the node areas to the root area.

Definition at line 552 of file b2_dynamic_tree.cpp.

◆ GetFatAABB()

const b2AABB & b2DynamicTree::GetFatAABB ( int32 proxyId ) const

inline

Get the fat AABB for a proxy.

Definition at line 181 of file b2_dynamic_tree.h.

◆ GetHeight()

int32 b2DynamicTree::GetHeight ( ) const

Compute the height of the binary tree in O(N) time. Should not be called often.

Definition at line 541 of file b2_dynamic_tree.cpp.

◆ GetMaxBalance()

int32 b2DynamicTree::GetMaxBalance ( ) const

Get the maximum balance of an node in the tree. The balance is the difference in height of the two children of a node.

Definition at line 695 of file b2_dynamic_tree.cpp.

◆ GetUserData()

void * b2DynamicTree::GetUserData ( int32 proxyId ) const

inline

Get proxy user data.

Returns: the proxy user data or 0 if the id is invalid.

Definition at line 163 of file b2_dynamic_tree.h.

◆ InsertLeaf()

void b2DynamicTree::InsertLeaf ( int32 node )

private

Definition at line 197 of file b2_dynamic_tree.cpp.

◆ MoveProxy()

bool b2DynamicTree::MoveProxy	(	int32	proxyId,
		const b2AABB &	aabb1,
		const b2Vec2 &	displacement
	)

Move a proxy with a swepted AABB. If the proxy has moved outside of its fattened AABB, then the proxy is removed from the tree and re-inserted. Otherwise the function returns immediately.

Returns: true if the proxy was re-inserted.

Definition at line 133 of file b2_dynamic_tree.cpp.

◆ Query()

template<typename T >

void b2DynamicTree::Query	(	T *	callback,
		const b2AABB &	aabb
	)		const

inline

Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.

Definition at line 188 of file b2_dynamic_tree.h.

◆ RayCast()

template<typename T >

void b2DynamicTree::RayCast	(	T *	callback,
		const b2RayCastInput &	input
	)		const

inline

Ray-cast against the proxies in the tree. This relies on the callback to perform a exact ray-cast in the case were the proxy contains a shape. The callback also performs the 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.

Parameters

input	the ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
callback	a callback class that is called for each proxy that is hit by the ray.

Definition at line 223 of file b2_dynamic_tree.h.

◆ RebuildBottomUp()

void b2DynamicTree::RebuildBottomUp ( )

Build an optimal tree. Very expensive. For testing.

Definition at line 717 of file b2_dynamic_tree.cpp.

◆ RemoveLeaf()

void b2DynamicTree::RemoveLeaf ( int32 node )

private

Definition at line 337 of file b2_dynamic_tree.cpp.

◆ ShiftOrigin()

void b2DynamicTree::ShiftOrigin ( const b2Vec2 & newOrigin )

Shift the world origin. Useful for large worlds. The shift formula is: position -= newOrigin

Parameters

newOrigin the new origin with respect to the old origin

Definition at line 793 of file b2_dynamic_tree.cpp.

◆ Validate()

void b2DynamicTree::Validate ( ) const

Validate this tree. For testing.

Definition at line 674 of file b2_dynamic_tree.cpp.

◆ ValidateMetrics()

void b2DynamicTree::ValidateMetrics ( int32 index ) const

private

Definition at line 635 of file b2_dynamic_tree.cpp.

◆ ValidateStructure()

void b2DynamicTree::ValidateStructure ( int32 index ) const

private

Definition at line 600 of file b2_dynamic_tree.cpp.

◆ WasMoved()

bool b2DynamicTree::WasMoved ( int32 proxyId ) const

inline

Definition at line 169 of file b2_dynamic_tree.h.

Member Data Documentation

◆ m_freeList

int32 b2DynamicTree::m_freeList

private

Definition at line 158 of file b2_dynamic_tree.h.

◆ m_insertionCount

int32 b2DynamicTree::m_insertionCount

private

Definition at line 160 of file b2_dynamic_tree.h.

◆ m_nodeCapacity

int32 b2DynamicTree::m_nodeCapacity

private

Definition at line 156 of file b2_dynamic_tree.h.

◆ m_nodeCount

int32 b2DynamicTree::m_nodeCount

private

Definition at line 155 of file b2_dynamic_tree.h.

◆ m_nodes

b2TreeNode* b2DynamicTree::m_nodes

private

Definition at line 154 of file b2_dynamic_tree.h.

◆ m_root

int32 b2DynamicTree::m_root

private

Definition at line 152 of file b2_dynamic_tree.h.

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ b2DynamicTree()

◆ ~b2DynamicTree()

Member Function Documentation

◆ AllocateNode()

◆ Balance()

◆ ClearMoved()

◆ ComputeHeight() [1/2]

◆ ComputeHeight() [2/2]

◆ CreateProxy()

◆ DestroyProxy()

◆ FreeNode()

◆ GetAreaRatio()

◆ GetFatAABB()

◆ GetHeight()

◆ GetMaxBalance()

◆ GetUserData()

◆ InsertLeaf()

◆ MoveProxy()

◆ Query()

◆ RayCast()

◆ RebuildBottomUp()

◆ RemoveLeaf()

◆ ShiftOrigin()

◆ Validate()

◆ ValidateMetrics()

◆ ValidateStructure()

◆ WasMoved()

Member Data Documentation

◆ m_freeList

◆ m_insertionCount

◆ m_nodeCapacity

◆ m_nodeCount

◆ m_nodes

◆ m_root