11 KiB
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
- allocateNode
- balance
- computeHeight
- createProxy
- destroyProxy
- freeNode
- getAreaRatio
- getFatAABB
- getHeight
- getMaxBalance
- getUserData
- insertLeaf
- moveProxy
- query
- rayCast
- rebuildBottomUp
- removeLeaf
- shiftOrigin
- validate
- validateMetrics
- validateStructure
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:
- [ id: number]: TreeNode‹T›
m_pool
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