Table of Contents

Class DynamicTree<TNode>

Namespace
Alis.Core.Physic.Collision
Assembly
Alis.dll

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 Settings.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.

public class DynamicTree<TNode>

Type Parameters

TNode

Inheritance

Inherited Members

Constructors

DynamicTree()

Constructing the tree initializes the node pool.

public DynamicTree()

Fields

NullNode

The null node

internal const int NullNode = -1

Field Value

int

_freeList

The free list

private int _freeList

Field Value

int

_nodeCapacity

The node capacity

private int _nodeCapacity

Field Value

int

_nodeCount

The node count

private int _nodeCount

Field Value

int

_nodes

The nodes

private TreeNode<TNode>[] _nodes

Field Value

TreeNode<TNode>[]

_queryStack

The stack

private readonly Stack<int> _queryStack

Field Value

Stack<int>

_raycastStack

The stack

private readonly Stack<int> _raycastStack

Field Value

Stack<int>

_root

The root

private int _root

Field Value

int

Properties

AreaRatio

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

public float AreaRatio { get; }

Property Value

float

Height

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

public int Height { get; }

Property Value

int

MaxBalance

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

public int MaxBalance { get; }

Property Value

int

Methods

AddProxy(ref AABB)

Create a proxy in the tree as a leaf node. We return the index of the node instead of a pointer so that we can grow the node pool. ///

public int AddProxy(ref AABB aabb)

Parameters

aabb AABB

The aabb.

Returns

int

Index of the created proxy

AllocateNode()

Allocates the node

private int AllocateNode()

Returns

int

The node id

Balance(int)

Perform a left or right rotation if node N is imbalanced.

private int Balance(int iN)

Parameters

iN int

Returns

int

the new root index.

ComputeHeight(int)

Compute the height of a sub-tree.

public int ComputeHeight(int nodeId)

Parameters

nodeId int

The node id to use as parent.

Returns

int

The height of the tree.

ComputeHeight()

Compute the height of the entire tree.

public int ComputeHeight()

Returns

int

The height of the tree.

FreeNode(int)

Frees the node using the specified node id

private void FreeNode(int nodeId)

Parameters

nodeId int

The node id

GetFatAABB(int, out AABB)

Get the fat AABB for a proxy.

public void GetFatAABB(int proxyId, out AABB fatAABB)

Parameters

proxyId int

The proxy id.

fatAABB AABB

The fat AABB.

GetFatAABB(int)

Get the fat AABB for a proxy.

public AABB GetFatAABB(int proxyId)

Parameters

proxyId int

The proxy id.

Returns

AABB

The fat AABB.

GetUserData(int)

Get proxy user data.

public TNode GetUserData(int proxyId)

Parameters

proxyId int

The proxy id.

Returns

TNode

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

InsertLeaf(int)

Inserts the leaf using the specified leaf

private void InsertLeaf(int leaf)

Parameters

leaf int

The leaf

MoveProxy(int, ref AABB, Vector2)

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.

public bool MoveProxy(int proxyId, ref AABB aabb, Vector2 displacement)

Parameters

proxyId int

The proxy id.

aabb AABB

The aabb.

displacement Vector2

The displacement.

Returns

bool

true if the proxy was re-inserted.

Query(BroadPhaseQueryCallback, ref AABB)

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

public void Query(BroadPhaseQueryCallback callback, ref AABB aabb)

Parameters

callback BroadPhaseQueryCallback

The callback.

aabb AABB

The aabb.

RayCast(BroadPhaseRayCastCallback, ref RayCastInput)

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.

public void RayCast(BroadPhaseRayCastCallback callback, ref RayCastInput input)

Parameters

callback BroadPhaseRayCastCallback

A callback class that is called for each proxy that is hit by the ray.

input RayCastInput

The ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).

RebuildBottomUp()

Build an optimal tree. Very expensive. For testing.

public void RebuildBottomUp()

RemoveLeaf(int)

Removes the leaf using the specified leaf

private void RemoveLeaf(int leaf)

Parameters

leaf int

The leaf

RemoveProxy(int)

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

public void RemoveProxy(int proxyId)

Parameters

proxyId int

The proxy id.

SetUserData(int, TNode)

Set proxy user data.

public void SetUserData(int proxyId, TNode userData)

Parameters

proxyId int

The proxy id.

userData TNode

The proxy user data.

ShiftOrigin(Vector2)

Shift the origin of the nodes

public void ShiftOrigin(Vector2 newOrigin)

Parameters

newOrigin Vector2

The displacement to use.

TestFatAABBOverlap(int, int)

Test overlap of fat AABBs.

public bool TestFatAABBOverlap(int proxyIdA, int proxyIdB)

Parameters

proxyIdA int

The proxy id A.

proxyIdB int

The proxy id B.

Returns

bool

Validate()

Validate this tree. For testing.

public void Validate()

ValidateMetrics(int)

Validates the metrics using the specified index

public void ValidateMetrics(int index)

Parameters

index int

The index

ValidateStructure(int)

Validates the structure using the specified index

public void ValidateStructure(int index)

Parameters

index int

The index