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

460 lines
11 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

[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*