2021-05-11 18:30:36 -07:00

11 KiB
Raw Permalink Blame History

Planck.js API Doc › Globals › DynamicTree

Class: DynamicTree ‹T›

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

Type parameters

▪ T

Hierarchy

  • DynamicTree

Index

Constructors

Properties

Methods

Constructors

constructor

+ new DynamicTree(): DynamicTree

Defined in src/collision/DynamicTree.ts:82

Returns: DynamicTree

Properties

m_lastProxyId

• m_lastProxyId: number

Defined in src/collision/DynamicTree.ts:78


m_nodes

• m_nodes: object

Defined in src/collision/DynamicTree.ts:79

Type declaration:


m_pool

• m_pool: Pool‹TreeNode‹T››

Defined in src/collision/DynamicTree.ts:82


m_root

• m_root: TreeNode‹T›

Defined in src/collision/DynamicTree.ts:77

Methods

allocateNode

▸ allocateNode(): TreeNode‹T›

Defined in src/collision/DynamicTree.ts:118

Returns: TreeNode‹T›


balance

▸ balance(iA: TreeNode‹T›): TreeNode‹T›

Defined in src/collision/DynamicTree.ts:395

Perform a left or right rotation if node A is imbalanced. Returns the new root index.

Parameters:

Name Type
iA TreeNode‹T›

Returns: TreeNode‹T›


computeHeight

▸ computeHeight(id?: number): number

Defined in src/collision/DynamicTree.ts:544

Compute the height of a sub-tree.

Parameters:

Name Type
id? number

Returns: number


createProxy

▸ createProxy(aabb: AABB, userData: T): number

Defined in src/collision/DynamicTree.ts:143

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.

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

Parameters:

Name Type
aabb AABB
userData T

Returns: number


destroyProxy

▸ destroyProxy(id: number): void

Defined in src/collision/DynamicTree.ts:164

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

Parameters:

Name Type
id number

Returns: void


freeNode

▸ freeNode(node: TreeNode‹T›): void

Defined in src/collision/DynamicTree.ts:130

Parameters:

Name Type
node TreeNode‹T›

Returns: void


getAreaRatio

▸ getAreaRatio(): number

Defined in src/collision/DynamicTree.ts:516

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

Returns: number


getFatAABB

▸ getFatAABB(id: number): AABB

Defined in src/collision/DynamicTree.ts:112

Get the fat AABB for a node id.

Parameters:

Name Type
id number

Returns: AABB

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


getHeight

▸ getHeight(): number

Defined in src/collision/DynamicTree.ts:505

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

Returns: number


getMaxBalance

▸ getMaxBalance(): number

Defined in src/collision/DynamicTree.ts:638

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

Returns: number


getUserData

▸ getUserData(id: number): T

Defined in src/collision/DynamicTree.ts:101

Get proxy user data.

Parameters:

Name Type
id number

Returns: T

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


insertLeaf

▸ insertLeaf(leaf: TreeNode‹T›): void

Defined in src/collision/DynamicTree.ts:224

Parameters:

Name Type
leaf TreeNode‹T›

Returns: void


moveProxy

▸ moveProxy(id: number, aabb: AABB, d: Vec2): boolean

Defined in src/collision/DynamicTree.ts:183

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.

Parameters:

Name Type Description
id number -
aabb AABB -
d Vec2 Displacement

Returns: boolean

true if the proxy was re-inserted.


query

▸ query(aabb: AABB, queryCallback: DynamicTreeQueryCallback): void

Defined in src/collision/DynamicTree.ts:749

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

Parameters:

Name Type
aabb AABB
queryCallback DynamicTreeQueryCallback

Returns: void


rayCast

▸ rayCast(input: RayCastInput, rayCastCallback: RayCastCallback): void

Defined in src/collision/DynamicTree.ts:786

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:

Name Type Description
input RayCastInput The ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
rayCastCallback RayCastCallback A function that is called for each proxy that is hit by the ray.

Returns: void


rebuildBottomUp

▸ rebuildBottomUp(): void

Defined in src/collision/DynamicTree.ts:660

Build an optimal tree. Very expensive. For testing.

Returns: void


removeLeaf

▸ removeLeaf(leaf: TreeNode‹T›): void

Defined in src/collision/DynamicTree.ts:344

Parameters:

Name Type
leaf TreeNode‹T›

Returns: void


shiftOrigin

▸ shiftOrigin(newOrigin: Vec2): void

Defined in src/collision/DynamicTree.ts:731

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

Parameters:

Name Type Description
newOrigin Vec2 The new origin with respect to the old origin

Returns: void


validate

▸ validate(): void

Defined in src/collision/DynamicTree.ts:627

Validate this tree. For testing.

Returns: void


validateMetrics

▸ validateMetrics(node: TreeNode‹T›): void

Defined in src/collision/DynamicTree.ts:592

Parameters:

Name Type
node TreeNode‹T›

Returns: void


validateStructure

▸ validateStructure(node: TreeNode‹T›): void

Defined in src/collision/DynamicTree.ts:563

Parameters:

Name Type
node TreeNode‹T›

Returns: void