460 lines
11 KiB
Markdown
460 lines
11 KiB
Markdown
[Planck.js API Doc](../README.md) › [Globals](../globals.md) › [DynamicTree](dynamictree.md)
|
||
|
||
# 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
|
||
|
||
* [constructor](dynamictree.md#constructor)
|
||
|
||
### Properties
|
||
|
||
* [m_lastProxyId](dynamictree.md#m_lastproxyid)
|
||
* [m_nodes](dynamictree.md#m_nodes)
|
||
* [m_pool](dynamictree.md#m_pool)
|
||
* [m_root](dynamictree.md#m_root)
|
||
|
||
### Methods
|
||
|
||
* [allocateNode](dynamictree.md#allocatenode)
|
||
* [balance](dynamictree.md#balance)
|
||
* [computeHeight](dynamictree.md#computeheight)
|
||
* [createProxy](dynamictree.md#createproxy)
|
||
* [destroyProxy](dynamictree.md#destroyproxy)
|
||
* [freeNode](dynamictree.md#freenode)
|
||
* [getAreaRatio](dynamictree.md#getarearatio)
|
||
* [getFatAABB](dynamictree.md#getfataabb)
|
||
* [getHeight](dynamictree.md#getheight)
|
||
* [getMaxBalance](dynamictree.md#getmaxbalance)
|
||
* [getUserData](dynamictree.md#getuserdata)
|
||
* [insertLeaf](dynamictree.md#insertleaf)
|
||
* [moveProxy](dynamictree.md#moveproxy)
|
||
* [query](dynamictree.md#query)
|
||
* [rayCast](dynamictree.md#raycast)
|
||
* [rebuildBottomUp](dynamictree.md#rebuildbottomup)
|
||
* [removeLeaf](dynamictree.md#removeleaf)
|
||
* [shiftOrigin](dynamictree.md#shiftorigin)
|
||
* [validate](dynamictree.md#validate)
|
||
* [validateMetrics](dynamictree.md#validatemetrics)
|
||
* [validateStructure](dynamictree.md#validatestructure)
|
||
|
||
## Constructors
|
||
|
||
### constructor
|
||
|
||
\+ **new DynamicTree**(): *[DynamicTree](dynamictree.md)*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:82](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L82)*
|
||
|
||
**Returns:** *[DynamicTree](dynamictree.md)*
|
||
|
||
## Properties
|
||
|
||
### m_lastProxyId
|
||
|
||
• **m_lastProxyId**: *number*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:78](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L78)*
|
||
|
||
___
|
||
|
||
### m_nodes
|
||
|
||
• **m_nodes**: *object*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:79](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L79)*
|
||
|
||
#### Type declaration:
|
||
|
||
* \[ **id**: *number*\]: [TreeNode](treenode.md)‹T›
|
||
|
||
___
|
||
|
||
### m_pool
|
||
|
||
• **m_pool**: *[Pool](pool.md)‹[TreeNode](treenode.md)‹T››*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:82](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L82)*
|
||
|
||
___
|
||
|
||
### m_root
|
||
|
||
• **m_root**: *[TreeNode](treenode.md)‹T›*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:77](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L77)*
|
||
|
||
## Methods
|
||
|
||
### allocateNode
|
||
|
||
▸ **allocateNode**(): *[TreeNode](treenode.md)‹T›*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:118](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L118)*
|
||
|
||
**Returns:** *[TreeNode](treenode.md)‹T›*
|
||
|
||
___
|
||
|
||
### balance
|
||
|
||
▸ **balance**(`iA`: [TreeNode](treenode.md)‹T›): *[TreeNode](treenode.md)‹T›*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:395](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L395)*
|
||
|
||
Perform a left or right rotation if node A is imbalanced. Returns the new
|
||
root index.
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`iA` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *[TreeNode](treenode.md)‹T›*
|
||
|
||
___
|
||
|
||
### computeHeight
|
||
|
||
▸ **computeHeight**(`id?`: number): *number*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:544](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L544)*
|
||
|
||
Compute the height of a sub-tree.
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`id?` | number |
|
||
|
||
**Returns:** *number*
|
||
|
||
___
|
||
|
||
### createProxy
|
||
|
||
▸ **createProxy**(`aabb`: [AABB](aabb.md), `userData`: T): *number*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:143](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L143)*
|
||
|
||
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](aabb.md) |
|
||
`userData` | T |
|
||
|
||
**Returns:** *number*
|
||
|
||
___
|
||
|
||
### destroyProxy
|
||
|
||
▸ **destroyProxy**(`id`: number): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:164](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L164)*
|
||
|
||
Destroy a proxy. This asserts if the id is invalid.
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`id` | number |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### freeNode
|
||
|
||
▸ **freeNode**(`node`: [TreeNode](treenode.md)‹T›): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:130](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L130)*
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`node` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### getAreaRatio
|
||
|
||
▸ **getAreaRatio**(): *number*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:516](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L516)*
|
||
|
||
Get the ratio of the sum of the node areas to the root area.
|
||
|
||
**Returns:** *number*
|
||
|
||
___
|
||
|
||
### getFatAABB
|
||
|
||
▸ **getFatAABB**(`id`: number): *[AABB](aabb.md)*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:112](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L112)*
|
||
|
||
Get the fat AABB for a node id.
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`id` | number |
|
||
|
||
**Returns:** *[AABB](aabb.md)*
|
||
|
||
the proxy user data or 0 if the id is invalid.
|
||
|
||
___
|
||
|
||
### getHeight
|
||
|
||
▸ **getHeight**(): *number*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:505](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L505)*
|
||
|
||
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](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L638)*
|
||
|
||
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](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L101)*
|
||
|
||
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](treenode.md)‹T›): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:224](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L224)*
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`leaf` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### moveProxy
|
||
|
||
▸ **moveProxy**(`id`: number, `aabb`: [AABB](aabb.md), `d`: [Vec2](vec2.md)): *boolean*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:183](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L183)*
|
||
|
||
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](aabb.md) | - |
|
||
`d` | [Vec2](vec2.md) | Displacement |
|
||
|
||
**Returns:** *boolean*
|
||
|
||
true if the proxy was re-inserted.
|
||
|
||
___
|
||
|
||
### query
|
||
|
||
▸ **query**(`aabb`: [AABB](aabb.md), `queryCallback`: [DynamicTreeQueryCallback](../globals.md#dynamictreequerycallback)): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:749](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L749)*
|
||
|
||
Query an AABB for overlapping proxies. The callback class is called for each
|
||
proxy that overlaps the supplied AABB.
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`aabb` | [AABB](aabb.md) |
|
||
`queryCallback` | [DynamicTreeQueryCallback](../globals.md#dynamictreequerycallback) |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### rayCast
|
||
|
||
▸ **rayCast**(`input`: [RayCastInput](../interfaces/raycastinput.md), `rayCastCallback`: [RayCastCallback](../globals.md#raycastcallback)): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:786](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L786)*
|
||
|
||
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](../interfaces/raycastinput.md) | The ray-cast input data. The ray extends from `p1` to `p1 + maxFraction * (p2 - p1)`. |
|
||
`rayCastCallback` | [RayCastCallback](../globals.md#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](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L660)*
|
||
|
||
Build an optimal tree. Very expensive. For testing.
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### removeLeaf
|
||
|
||
▸ **removeLeaf**(`leaf`: [TreeNode](treenode.md)‹T›): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:344](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L344)*
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`leaf` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### shiftOrigin
|
||
|
||
▸ **shiftOrigin**(`newOrigin`: [Vec2](vec2.md)): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:731](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L731)*
|
||
|
||
Shift the world origin. Useful for large worlds. The shift formula is:
|
||
position -= newOrigin
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type | Description |
|
||
------ | ------ | ------ |
|
||
`newOrigin` | [Vec2](vec2.md) | The new origin with respect to the old origin |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### validate
|
||
|
||
▸ **validate**(): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:627](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L627)*
|
||
|
||
Validate this tree. For testing.
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### validateMetrics
|
||
|
||
▸ **validateMetrics**(`node`: [TreeNode](treenode.md)‹T›): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:592](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L592)*
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`node` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *void*
|
||
|
||
___
|
||
|
||
### validateStructure
|
||
|
||
▸ **validateStructure**(`node`: [TreeNode](treenode.md)‹T›): *void*
|
||
|
||
*Defined in [src/collision/DynamicTree.ts:563](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L563)*
|
||
|
||
**Parameters:**
|
||
|
||
Name | Type |
|
||
------ | ------ |
|
||
`node` | [TreeNode](treenode.md)‹T› |
|
||
|
||
**Returns:** *void*
|