460 lines
11 KiB
Markdown
Raw Permalink Normal View History

2020-07-28 20:21:55 -07:00
[Planck.js API Doc](../README.md) › [Globals](../globals.md) › [DynamicTree](dynamictree.md)
2020-07-27 00:12:01 -07:00
# Class: DynamicTree ‹**T**›
2021-04-16 17:10:15 +02:00
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**
2020-07-27 00:12:01 -07:00
## Hierarchy
* **DynamicTree**
## Index
2021-04-16 17:10:15 +02:00
### 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)
2020-07-27 00:12:01 -07:00
### 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)
2021-04-16 17:10:15 +02:00
## Constructors
### constructor
\+ **new DynamicTree**(): *[DynamicTree](dynamictree.md)*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:82](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L82)*
2021-04-16 17:10:15 +02:00
**Returns:** *[DynamicTree](dynamictree.md)*
## Properties
### m_lastProxyId
• **m_lastProxyId**: *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:78](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L78)*
2021-04-16 17:10:15 +02:00
___
### m_nodes
• **m_nodes**: *object*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:79](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L79)*
2021-04-16 17:10:15 +02:00
#### Type declaration:
* \[ **id**: *number*\]: [TreeNode](treenode.md)‹T›
2021-04-16 17:10:15 +02:00
___
### m_pool
• **m_pool**: *[Pool](pool.md)‹[TreeNode](treenode.md)‹T››*
2021-04-16 17:10:15 +02:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:82](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L82)*
2021-04-16 17:10:15 +02:00
___
### m_root
• **m_root**: *[TreeNode](treenode.md)‹T›*
2021-04-16 17:10:15 +02:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:77](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L77)*
2021-04-16 17:10:15 +02:00
2020-07-27 00:12:01 -07:00
## Methods
### allocateNode
2021-04-16 17:10:15 +02:00
▸ **allocateNode**(): *[TreeNode](treenode.md)‹T›*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:118](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L118)*
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
**Returns:** *[TreeNode](treenode.md)‹T›*
2020-07-27 00:12:01 -07:00
___
### balance
2021-04-16 17:10:15 +02:00
▸ **balance**(`iA`: [TreeNode](treenode.md)‹T›): *[TreeNode](treenode.md)‹T›*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:395](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L395)*
2021-04-16 17:10:15 +02:00
Perform a left or right rotation if node A is imbalanced. Returns the new
root index.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`iA` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
**Returns:** *[TreeNode](treenode.md)‹T›*
2020-07-27 00:12:01 -07:00
___
### computeHeight
2021-04-16 17:10:15 +02:00
▸ **computeHeight**(`id?`: number): *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:544](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L544)*
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
Compute the height of a sub-tree.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`id?` | number |
2020-07-27 00:12:01 -07:00
**Returns:** *number*
___
### createProxy
2021-04-16 17:10:15 +02:00
▸ **createProxy**(`aabb`: [AABB](aabb.md), `userData`: T): *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:143](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L143)*
2021-04-16 17:10:15 +02:00
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.
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
Create a proxy. Provide a tight fitting AABB and a userData pointer.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
`aabb` | [AABB](aabb.md) |
2021-04-16 17:10:15 +02:00
`userData` | T |
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
**Returns:** *number*
2020-07-27 00:12:01 -07:00
___
### destroyProxy
▸ **destroyProxy**(`id`: number): *void*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:164](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L164)*
2021-04-16 17:10:15 +02:00
Destroy a proxy. This asserts if the id is invalid.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
`id` | number |
**Returns:** *void*
___
### freeNode
2021-04-16 17:10:15 +02:00
▸ **freeNode**(`node`: [TreeNode](treenode.md)‹T›): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:130](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L130)*
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`node` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### getAreaRatio
▸ **getAreaRatio**(): *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:516](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L516)*
2021-04-16 17:10:15 +02:00
Get the ratio of the sum of the node areas to the root area.
2020-07-27 00:12:01 -07:00
**Returns:** *number*
___
### getFatAABB
▸ **getFatAABB**(`id`: number): *[AABB](aabb.md)*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:112](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L112)*
2021-04-16 17:10:15 +02:00
Get the fat AABB for a node id.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
`id` | number |
**Returns:** *[AABB](aabb.md)*
2021-04-16 17:10:15 +02:00
the proxy user data or 0 if the id is invalid.
2020-07-27 00:12:01 -07:00
___
### getHeight
▸ **getHeight**(): *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:505](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L505)*
2021-04-16 17:10:15 +02:00
Compute the height of the binary tree in O(N) time. Should not be called
often.
2020-07-27 00:12:01 -07:00
**Returns:** *number*
___
### getMaxBalance
▸ **getMaxBalance**(): *number*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:638](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L638)*
2021-04-16 17:10:15 +02:00
Get the maximum balance of an node in the tree. The balance is the difference
in height of the two children of a node.
2020-07-27 00:12:01 -07:00
**Returns:** *number*
___
### getUserData
2021-04-16 17:10:15 +02:00
▸ **getUserData**(`id`: number): *T*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:101](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L101)*
2020-07-27 00:12:01 -07:00
2021-04-16 17:10:15 +02:00
Get proxy user data.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
`id` | number |
2021-04-16 17:10:15 +02:00
**Returns:** *T*
the proxy user data or 0 if the id is invalid.
2020-07-27 00:12:01 -07:00
___
### insertLeaf
2021-04-16 17:10:15 +02:00
▸ **insertLeaf**(`leaf`: [TreeNode](treenode.md)‹T›): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:224](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L224)*
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`leaf` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### moveProxy
▸ **moveProxy**(`id`: number, `aabb`: [AABB](aabb.md), `d`: [Vec2](vec2.md)): *boolean*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:183](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L183)*
2021-04-16 17:10:15 +02:00
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.
2020-07-27 00:12:01 -07:00
**Parameters:**
2021-04-16 17:10:15 +02:00
Name | Type | Description |
------ | ------ | ------ |
`id` | number | - |
`aabb` | [AABB](aabb.md) | - |
`d` | [Vec2](vec2.md) | Displacement |
2020-07-27 00:12:01 -07:00
**Returns:** *boolean*
2021-04-16 17:10:15 +02:00
true if the proxy was re-inserted.
2020-07-27 00:12:01 -07:00
___
### query
2021-05-08 11:13:58 -07:00
▸ **query**(`aabb`: [AABB](aabb.md), `queryCallback`: [DynamicTreeQueryCallback](../globals.md#dynamictreequerycallback)): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:749](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L749)*
2021-04-16 17:10:15 +02:00
Query an AABB for overlapping proxies. The callback class is called for each
proxy that overlaps the supplied AABB.
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-05-08 11:13:58 -07:00
`aabb` | [AABB](aabb.md) |
`queryCallback` | [DynamicTreeQueryCallback](../globals.md#dynamictreequerycallback) |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### rayCast
2021-05-08 11:13:58 -07:00
▸ **rayCast**(`input`: [RayCastInput](../interfaces/raycastinput.md), `rayCastCallback`: [RayCastCallback](../globals.md#raycastcallback)): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:786](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L786)*
2021-04-16 17:10:15 +02:00
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.
2020-07-27 00:12:01 -07:00
**Parameters:**
2021-05-08 11:13:58 -07:00
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. |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### rebuildBottomUp
▸ **rebuildBottomUp**(): *void*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:660](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L660)*
2021-04-16 17:10:15 +02:00
Build an optimal tree. Very expensive. For testing.
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### removeLeaf
2021-04-16 17:10:15 +02:00
▸ **removeLeaf**(`leaf`: [TreeNode](treenode.md)‹T›): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:344](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L344)*
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`leaf` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### shiftOrigin
▸ **shiftOrigin**(`newOrigin`: [Vec2](vec2.md)): *void*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:731](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L731)*
2021-04-16 17:10:15 +02:00
Shift the world origin. Useful for large worlds. The shift formula is:
position -= newOrigin
2020-07-27 00:12:01 -07:00
**Parameters:**
2021-04-16 17:10:15 +02:00
Name | Type | Description |
------ | ------ | ------ |
`newOrigin` | [Vec2](vec2.md) | The new origin with respect to the old origin |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### validate
▸ **validate**(): *void*
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:627](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L627)*
2021-04-16 17:10:15 +02:00
Validate this tree. For testing.
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### validateMetrics
2021-04-16 17:10:15 +02:00
▸ **validateMetrics**(`node`: [TreeNode](treenode.md)‹T›): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:592](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L592)*
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`node` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
**Returns:** *void*
___
### validateStructure
2021-04-16 17:10:15 +02:00
▸ **validateStructure**(`node`: [TreeNode](treenode.md)‹T›): *void*
2020-07-27 00:12:01 -07:00
2021-05-11 18:30:36 -07:00
*Defined in [src/collision/DynamicTree.ts:563](https://github.com/shakiba/planck.js/blob/acc3bd8/src/collision/DynamicTree.ts#L563)*
2020-07-27 00:12:01 -07:00
**Parameters:**
Name | Type |
------ | ------ |
2021-04-16 17:10:15 +02:00
`node` | [TreeNode](treenode.md)‹T› |
2020-07-27 00:12:01 -07:00
**Returns:** *void*