Appearance
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
T
Constructors
Constructor
new DynamicTree<
T>():DynamicTree<T>
Returns
DynamicTree<T>
Properties
m_lastProxyId
m_lastProxyId:
number
m_nodes
m_nodes:
object
Index Signature
[id: number]: TreeNode<T>
m_root
m_root:
TreeNode<T>
Methods
allocateNode()
allocateNode():
TreeNode<T>
Returns
TreeNode<T>
balance()
balance(
iA):TreeNode<T>
Perform a left or right rotation if node A is imbalanced. Returns the new root index.
Parameters
iA
TreeNode<T>
Returns
TreeNode<T>
computeHeight()
computeHeight(
id?):number
Compute the height of a sub-tree.
Parameters
id?
number
Returns
number
createProxy()
createProxy(
aabb,userData):number
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
aabb
userData
T
Returns
number
destroyProxy()
destroyProxy(
id):void
Destroy a proxy. This asserts if the id is invalid.
Parameters
id
number
Returns
void
freeNode()
freeNode(
node):void
Parameters
node
TreeNode<T>
Returns
void
getAreaRatio()
getAreaRatio():
number
Get the ratio of the sum of the node areas to the root area.
Returns
number
getFatAABB()
getFatAABB(
id):AABB
Get the fat AABB for a node id.
Parameters
id
number
Returns
the proxy user data or 0 if the id is invalid.
getHeight()
getHeight():
number
Compute the height of the binary tree in O(N) time. Should not be called often.
Returns
number
getMaxBalance()
getMaxBalance():
number
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):T
Get proxy user data.
Parameters
id
number
Returns
T
the proxy user data or 0 if the id is invalid.
insertLeaf()
insertLeaf(
leaf):void
Parameters
leaf
TreeNode<T>
Returns
void
moveProxy()
moveProxy(
id,aabb,d):boolean
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
id
number
aabb
d
Displacement
Returns
boolean
true if the proxy was re-inserted.
query()
query(
aabb,queryCallback):void
Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB.
Parameters
aabb
queryCallback
Returns
void
rayCast()
rayCast(
input,rayCastCallback):void
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
input
The ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
rayCastCallback
A function that is called for each proxy that is hit by the ray. If the return value is a positive number it will update the maxFraction of the ray cast input, and if it is zero it will terminate they ray cast.
Returns
void
rebuildBottomUp()
rebuildBottomUp():
void
Build an optimal tree. Very expensive. For testing.
Returns
void
removeLeaf()
removeLeaf(
leaf):void
Parameters
leaf
TreeNode<T>
Returns
void
shiftOrigin()
shiftOrigin(
newOrigin):void
Shift the world origin. Useful for large worlds. The shift formula is: position -= newOrigin
Parameters
newOrigin
The new origin with respect to the old origin
Returns
void
validate()
validate():
void
Validate this tree. For testing.
Returns
void
validateMetrics()
validateMetrics(
node):void
Parameters
node
TreeNode<T>
Returns
void
validateStructure()
validateStructure(
node):void
Parameters
node
TreeNode<T>
Returns
void