You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Dynamic AABB tree is a type of broadphase that is borderless, meaning that it does not impose a strict border limit as some other broadphases do, such as explicit grid and implicit grid.
It is very efficient in all aspects in terms of game physics, including ray casting, point picking, region query, and, most importantly, generating a list of collider pairs that are potentially colliding (which is the main purpose of having a broadphase).
In this post, I will explain how a dynamic AABB tree works and show you a sample implementation.
The Structure
First, let’s look at the basic concept of a dynamic AABB tree. From its name, you can already guess that it has something to to with storing AABB-related information in a tree structure, and it is dynamic at run time.
Each collider has its own AABB, and they are stored inside a binary tree as leaf nodes. Each internal node, a.k.a. branch node, holds its own AABB data that represents the union of the AABB of both of its children.
Visual aids are always better than plain text. The picture below shows a spatial configurations of several colliders and a visual representation of a possible corresponding tree structure.
Interface
Based on the base interface from the broadphase overview post, here’s the interface of our dynamic AABB tree.
Similar to conventional binary trees, we would like to keep the AABB tree as balanced as possible, for how balanced an AABB tree is affects its performance on various operations.
However, AABB trees has a different sense of balance compared to conventional binary trees. The balancing of an AABB tree is not based on the depth of leaf nodes, but based on how evenly two child nodes divide their parent’s AABB.
AABB Update
Many things will have moved within a time step, and thus their AABBs need to be updated. However, this means we will have to re-balance the tree after the AABBs are updated. The most naive way to do this is to re-construct the tree from scratch with the updated AABBs within each time step. It is a plausible solution if your scene is consisted of not too many colliders. But we would like our dynamic AABB tree to be more scalable, so here I’m going to employ the so-called “fat AABB” approach.
The idea is very simple: instead of making a node exactly correspond to the AABB it’s associated with, let’s make the node hold an extra piece of “fat AABB” data that is slightly fatter (larger) than the associated AABB, so the associated AABB is contained within the fat AABB. When the collider moves outside of the fat AABB within a time step, we remove the node from the tree, re-insert the node into the tree from the root, and then assign a new fat AABB to the node. The AABBTree::m_margin property indicates how much fatter the fat AABB is to the original AABB; in the code above, I arbitrarily chose to use the value 0.2 meter (20 centimeters).
Thus, the Node::aabb property stores a fat AABB of where the Node::data property points to if the node is a leaf node, and it stores the union of the Node::aabb properties of the node’s child nodes if the node is a branch node.
With fat AABBs, we only have to move around the nodes whose associated colliders are moving far enough between time steps.
void AABBTree::Update(const TimeStep &timeStep)
{
if (m_root)
{
if (m_root->IsLeaf())
m_root->UpdateAABB(m_margin);
else
{
// grab all invalid nodes
m_invalidNodes.clear();
UpdateNodeHelper(m_root, m_invalidNodes);
// re-insert all invalid nodes
for (Node *node: m_invalidNodes)
{
// grab parent link
// (pointer to the pointer that points to parent)
Node *parent = node->parent;
Node *sibling = node->GetSibling();
Node **parentLink =
parent->parent
? (parent == parent->parent->children[0]
? &parent->parent->children[0]
: &parent->parent->children[1])
: &m_root;
// replace parent with sibling
sibling->parent =
parent->parent
? parent->parent
: nullptr; // root has null parent
*parentLink = sibling;
delete parent;
// re-insert node
node->UpdateAABB(m_margin);
InsertNode(node, &m_root);
}
m_invalidNodes.clear();
}
}
void AABBTree::UpdateNodeHelper
(Node *node, NodeList &invalidNodes)
{
if (node->IsLeaf())
{
// check if fat AABB doesn't
// contain the collider's AABB anymore
if (!node->aabb.Contains(node->data->aabb))
invalidNodes.push_back(node);
}
else
{
UpdateNodeHelper(node->children[0], invalidNodes);
UpdateNodeHelper(node->children[1], invalidNodes);
}
}
}
Node Insertion
When inserting a node to an AABB tree, the node is inserted at the root node and propagated down the tree until it reaches a leaf node; then, the leaf node is replaced by a new branch node, whose two children are the inserted node and the leaf node.
When we propagate an inserted node down a tree at a branch, we choose the child node to propagate to that gives the least increase in volume of the branch’s AABB. This gives us a more balanced AABB tree. Of course, you can use other heuristics such as closest AABB centroid when inserting nodes.
void AABBTree::Add(AABB *aabb)
{
if (m_root)
{
// not first node, insert node to tree
Node *node = new Node();
node->SetLeaf(aabb);
node->UpdateAABB(m_margin);
InsertNode(node, &m_root);
}
else
{
// first node, make root
m_root = new Node();
m_root->SetLeaf(aabb);
m_root->UpdateAABB(m_margin);
}
}
// insert to the child that gives less volume increase
if (volumeDiff0 < volumeDiff1)
InsertNode(node, &p->children[0]);
else
InsertNode(node, &p->children[1]);
}
// update parent AABB
// (propagates back up the recursion stack)
(*parent)->UpdateAABB(m_margin);
}
Node Removal
Node removal is more straight forward, so I will just show the code along with the comments.
// remove two-way link
node->data = nullptr;
aabb->userData = nullptr;
RemoveNode(node);
}
void AABBTree::RemoveNode(Node *node)
{
// replace parent with sibling, remove parent node
Node *parent = node->parent;
if (parent) // node is not root
{
Node *sibling = node->GetSibling();
if (parent->parent) // if there's a grandparent
{
// update links
sibling->parent = parent->parent;
(parent == parent->parent->children[0]
? parent->parent->children[0]
: parent->parent->children[1]) = sibling;
}
else // no grandparent
{
// make sibling root
Node *sibling = node->GetSibling();
m_root = sibling;
sibling->parent = nullptr;
}
delete node;
delete parent;
}
else // node is root
{
m_root = nullptr;
delete node;
}
}
Computing Collider Pair List
Now that we have seen how to insert nodes, remove nodes, and update the tree, we can move onto what a broadphase is supposed to do: computing collider pair list, point picking, and ray casts.
The algorithm for computing the collider pair list needs a little bit more explanation. Here I decided to implement it recursively, because the code is more elegant this way. You can always re-implement it iteratively.
Basically, the recursive method AABBTree::ComputePairsHelper takes two nodes as input, and based on the combination of the node types (2 leaf nodes, 1 leaf node plus 1 branch node, or 2 branch nodes), the method either tests for potential collider pair or invoke itself recursively with child nodes of the input nodes.
Here are all the 3 cases:
2 Leaf Nodes – We’ve reached the end of the tree, simply check the AABBs of the corresponding colliders and possibly add them to the pair list
1 Leaf Node plus 1 Branch Node – Cross check the child nodes of the branch node (make a recursive call with the child nodes), and make recursive calls with the leaf node against each child nodes of the branch node.
2 Branch Nodes – Make a recursive call on every combination of 2 nodes out of the 4 child nodes.
With the logic above alone, we can get duplicate pairs added to the list; thus, we use the Node::childrenCrossed Boolean flag to check if the children of a branch node have already been “cross checked (passed into a recursive call)”. This little trick fixes the problem.
while (!q.empty())
{
Node &node = *q.front();
q.pop();
if (node.IsLeaf())
{
if (node.data->Collides(pos))
result.push_back(node.data->Collider());
}
else
{
q.push(node.children[0]);
q.push(node.children[1]);
}
}
}
Ray Casts
The logic flow for ray casting is very similar to point picking, except that there is an extra optimization step, where a node is instantly discarded if the ray intersection parameter t is larger than our current smallest t.
std::queue<Node *> q;
if (m_root)
{
q.push(m_root);
}
while (!q.empty())
{
Node &node = *q.front();
q.pop();
AABB &colliderAABB = *node.data;
AABB &aabb =
node.IsLeaf()
? colliderAABB
: node.aabb;
float t;
if (RayAABB(ray, aabb, maxDistance, t))
{
// the node cannot possibly give closer results, skip
if (result.hit && result.t < t)
continue;
if (node.IsLeaf())
{
Collider &collider = *colliderAABB.Collider();
Vec3 n;
float t;
if (collider.RayCast(ray, maxDistance, t, n))
{
if (result.hit) // compare hit
{
if (t < result.t)
{
result.collider = &collider;
result.t = t;
result.normal = n;
result.intersection = ray.pos
+ t * maxDistance * ray.dir.Normalized();
}
}
else // first hit
{
result.hit = true;
result.collider = &collider;
result.t = t;
result.ray = ray;
result.normal = n;
result.intersection = ray.pos
+ t * maxDistance * ray.dir.Normalized();
}
}
}
else // is branch
{
q.push(node.children[0]);
q.push(node.children[1]);
}
}
}
return result;
}
End of Dynamic AABB Tree
This concludes my example implementation of the dynamic AABB tree broadphase. If you followed my previous advice and already have an N-squared broadphase that can be easily swapped out, you can consider switching to dynamic AABB tree if the number of your rigid bodies is getting too large that the N-Squared broadphase starts dragging the performance of your game.
via Ming-Lun "Allen" Chou | 周明倫
October 8, 2024 at 06:19PM
The text was updated successfully, but these errors were encountered:
Game Physics: Broadphase - Dynamic AABB Tree
https://ift.tt/9jwohyI
This post is part of my Game Physics Series.
Dynamic AABB tree is a type of broadphase that is borderless, meaning that it does not impose a strict border limit as some other broadphases do, such as explicit grid and implicit grid.
It is very efficient in all aspects in terms of game physics, including ray casting, point picking, region query, and, most importantly, generating a list of collider pairs that are potentially colliding (which is the main purpose of having a broadphase).
In this post, I will explain how a dynamic AABB tree works and show you a sample implementation.
The Structure
First, let’s look at the basic concept of a dynamic AABB tree. From its name, you can already guess that it has something to to with storing AABB-related information in a tree structure, and it is dynamic at run time.
Each collider has its own AABB, and they are stored inside a binary tree as leaf nodes. Each internal node, a.k.a. branch node, holds its own AABB data that represents the union of the AABB of both of its children.
Visual aids are always better than plain text. The picture below shows a spatial configurations of several colliders and a visual representation of a possible corresponding tree structure.
Interface
Based on the base interface from the broadphase overview post, here’s the interface of our dynamic AABB tree.
class AABBTree : public Broadphase { public:AABBTree(void)
: m_root(nullptr)
, m_margin(0.2f) // 20cm
{ }
virtual void Add(AABB *aabb);
virtual void Remove(AABB *aabb);
virtual void Update(void);
virtual ColliderPairList &ComputePairs(void);
virtual Collider *Pick(const Vec3 &point) const;
virtual Query(const AABB &aabb, ColliderList &out) const;
virtual RayCastResult RayCast(const Ray3 &ray) const;
private:
typedef std::vector<Node *> NodeList;
void UpdateNodeHelper(Node *node, NodeList &invalidNodes);
void InsertNode(Node *node, Node **parent);
void RemoveNode(Node *node);
void ComputePairsHelper(Node *n0, Node *n1);
void ClearChildrenCrossFlagHelper(Node *node);
void CrossChildren(Node *node);
Node *m_root;
ColliderPairList m_pairs;
float m_margin;
NodeList m_invalidNodes;
};
And below is the implementation of the
Nodestructure.The
Node::dataproperty is a pointer to the actual AABB of a collider, and the purpose of theNode::aabbproperty will be explained later.struct Node { Node *parent; Node *children[2];// these will be explained later
bool childrenCrossed;
AABB aabb;
AABB *data;
Node(void)
: parent(nullptr)
, data(nullptr)
{
children[0] = nullptr;
children[1] = nullptr;
}
bool IsLeaf(void) const
{
return children[0] = nullptr;
}
// make this ndoe a branch
void SetBranch(Node *n0, Node *n1)
{
n0->parent = this;
n1->parent = this;
}
// make this node a leaf
void SetLeaf(AABB *data)
{
// create two-way link
this->data = data;
data->userData = this;
}
void UpdateAABB(float margin)
{
if (IsLeaf())
{
// make fat AABB
const Vec3 marginVec(margin, margin, margin);
aabb.minPoint = data->minPoint - marginVec;
aabb.maxPoint = data->maxPoint + marginVec;
}
else
// make union of child AABBs of child nodes
aabb =
children[0]->aabb.Union(children[1]->aabb);
}
Node *GetSibling(void) const
{
return
this == parent->children[0]
? parent->children[1]
: parent->children[0];
}
};
Balance
Similar to conventional binary trees, we would like to keep the AABB tree as balanced as possible, for how balanced an AABB tree is affects its performance on various operations.
However, AABB trees has a different sense of balance compared to conventional binary trees. The balancing of an AABB tree is not based on the depth of leaf nodes, but based on how evenly two child nodes divide their parent’s AABB.
AABB Update
Many things will have moved within a time step, and thus their AABBs need to be updated. However, this means we will have to re-balance the tree after the AABBs are updated. The most naive way to do this is to re-construct the tree from scratch with the updated AABBs within each time step. It is a plausible solution if your scene is consisted of not too many colliders. But we would like our dynamic AABB tree to be more scalable, so here I’m going to employ the so-called “fat AABB” approach.
The idea is very simple: instead of making a node exactly correspond to the AABB it’s associated with, let’s make the node hold an extra piece of “fat AABB” data that is slightly fatter (larger) than the associated AABB, so the associated AABB is contained within the fat AABB. When the collider moves outside of the fat AABB within a time step, we remove the node from the tree, re-insert the node into the tree from the root, and then assign a new fat AABB to the node. The
AABBTree::m_marginproperty indicates how much fatter the fat AABB is to the original AABB; in the code above, I arbitrarily chose to use the value 0.2 meter (20 centimeters).Thus, the
Node::aabbproperty stores a fat AABB of where theNode::dataproperty points to if the node is a leaf node, and it stores the union of theNode::aabbproperties of the node’s child nodes if the node is a branch node.With fat AABBs, we only have to move around the nodes whose associated colliders are moving far enough between time steps.
void AABBTree::Update(const TimeStep &timeStep) { if (m_root) { if (m_root->IsLeaf()) m_root->UpdateAABB(m_margin); else { // grab all invalid nodes m_invalidNodes.clear(); UpdateNodeHelper(m_root, m_invalidNodes);}
void AABBTree::UpdateNodeHelper
(Node *node, NodeList &invalidNodes)
{
if (node->IsLeaf())
{
// check if fat AABB doesn't
// contain the collider's AABB anymore
if (!node->aabb.Contains(node->data->aabb))
invalidNodes.push_back(node);
}
else
{
UpdateNodeHelper(node->children[0], invalidNodes);
UpdateNodeHelper(node->children[1], invalidNodes);
}
}
}
Node Insertion
When inserting a node to an AABB tree, the node is inserted at the root node and propagated down the tree until it reaches a leaf node; then, the leaf node is replaced by a new branch node, whose two children are the inserted node and the leaf node.
When we propagate an inserted node down a tree at a branch, we choose the child node to propagate to that gives the least increase in volume of the branch’s AABB. This gives us a more balanced AABB tree. Of course, you can use other heuristics such as closest AABB centroid when inserting nodes.
void AABBTree::Add(AABB *aabb) { if (m_root) { // not first node, insert node to tree Node *node = new Node(); node->SetLeaf(aabb); node->UpdateAABB(m_margin); InsertNode(node, &m_root); } else { // first node, make root m_root = new Node(); m_root->SetLeaf(aabb); m_root->UpdateAABB(m_margin); } }void AABBTree::InsertNode(Node *node, Node **parent)
{
Node *p = *parent;
if (p->IsLeaf())
{
// parent is leaf, simply split
Node *newParent = new Node();
newParent->parent = p->parent;
newParent->SetBranch(node, p);
*parent = newParent;
}
else
{
// parent is branch, compute volume differences
// between pre-insert and post-insert
const AABB *aabb0 = p->children[0]->aabb;
const AABB *aabb1 = p->children[1]->aabb;
const float volumeDiff0 =
aabb0->Union(node->aabb).Volume() - aabb0->Volume();
const float volumeDiff1 =
aabb1->Union(node->aabb).Volume() - aabb1->Volume();
}
// update parent AABB
// (propagates back up the recursion stack)
(*parent)->UpdateAABB(m_margin);
}
Node Removal
Node removal is more straight forward, so I will just show the code along with the comments.
void AABBTree::Remove(AABB *aabb) { Node *node = static_cast<Node *>(aabb->userData);// remove two-way link
node->data = nullptr;
aabb->userData = nullptr;
RemoveNode(node);
}
void AABBTree::RemoveNode(Node *node)
{
// replace parent with sibling, remove parent node
Node *parent = node->parent;
if (parent) // node is not root
{
Node *sibling = node->GetSibling();
if (parent->parent) // if there's a grandparent
{
// update links
sibling->parent = parent->parent;
(parent == parent->parent->children[0]
? parent->parent->children[0]
: parent->parent->children[1]) = sibling;
}
else // no grandparent
{
// make sibling root
Node *sibling = node->GetSibling();
m_root = sibling;
sibling->parent = nullptr;
}
delete node;
delete parent;
}
else // node is root
{
m_root = nullptr;
delete node;
}
}
Computing Collider Pair List
Now that we have seen how to insert nodes, remove nodes, and update the tree, we can move onto what a broadphase is supposed to do: computing collider pair list, point picking, and ray casts.
The algorithm for computing the collider pair list needs a little bit more explanation. Here I decided to implement it recursively, because the code is more elegant this way. You can always re-implement it iteratively.
Basically, the recursive method
AABBTree::ComputePairsHelpertakes two nodes as input, and based on the combination of the node types (2 leaf nodes, 1 leaf node plus 1 branch node, or 2 branch nodes), the method either tests for potential collider pair or invoke itself recursively with child nodes of the input nodes.Here are all the 3 cases:
With the logic above alone, we can get duplicate pairs added to the list; thus, we use the
Node::childrenCrossedBoolean flag to check if the children of a branch node have already been “cross checked (passed into a recursive call)”. This little trick fixes the problem.ColliderPairList &AABBTree::ComputePairs(void) { m_pairs.clear();// early out
if (!m_root || m_root->IsLeaf())
return m_pairs;
// clear Node::childrenCrossed flags
ClearChildrenCrossFlagHelper(m_root);
// base recursive call
ComputePairsHelper(m_root->children[0],
m_root->children[1]);
return m_pairs;
}
void AABBTree::ClearChildrenCrossFlagHelper(Node *node)
{
node->childrenCrossed = false;
if (!node->IsLeaf())
{
ClearChildrenCrossFlagHelper(node->children[0]);
ClearChildrenCrossFlagHelper(node->children[1]);
}
}
void AABBTree::CrossChildren(Node *node)
{
if (!node->childrenCrossed)
{
ComputePairsHelper(node->children[0],
node->children[1]);
node->childrenCrossed = true;
}
}
void AABBTree::ComputePairsHelper(Node *n0, Node *n1)
{
if (n0->IsLeaf())
{
// 2 leaves, check proxies instead of fat AABBs
if (n1->IsLeaf())
{
if (n0->data->Collides(*n1->data))
m_pairs.push_back(AllocatePair(n0->data->Collider(),
n1->data->Collider()));
}
// 1 branch / 1 leaf, 2 cross checks
else
{
CrossChildren(n1);
ComputePairsHelper(n0, n1->children[0]);
ComputePairsHelper(n0, n1->children[1]);
}
}
else
{
// 1 branch / 1 leaf, 2 cross checks
if (n1->IsLeaf())
{
CrossChildren(n0);
ComputePairsHelper(n0->children[0], n1);
ComputePairsHelper(n0->children[1], n1);
}
// 2 branches, 4 cross checks
else
{
CrossChildren(n0);
CrossChildren(n1);
ComputePairsHelper(n0->children[0], n1->children[0]);
ComputePairsHelper(n0->children[0], n1->children[1]);
ComputePairsHelper(n0->children[1], n1->children[0]);
ComputePairsHelper(n0->children[1], n1->children[1]);
}
} // end of if (n0->IsLeaf())
}
Point Picking
For point picking, we can just perform a iterative point-AABB check starting from the root node.
void AABBTree::Pick(const Vec3 &pos, PickResult &result) { std::queue<Node *> q; if (m_root) q.push(m_root);while (!q.empty())
{
Node &node = *q.front();
q.pop();
}
}
Ray Casts
The logic flow for ray casting is very similar to point picking, except that there is an extra optimization step, where a node is instantly discarded if the ray intersection parameter
tis larger than our current smallestt.const RayCastResult AABBTree::RayCast (const Ray3 &ray, float maxDistance) { RayCastResult result; result.hit = false; result.t = 1.0f;std::queue<Node *> q;
if (m_root)
{
q.push(m_root);
}
while (!q.empty())
{
Node &node = *q.front();
q.pop();
}
return result;
}
End of Dynamic AABB Tree
This concludes my example implementation of the dynamic AABB tree broadphase. If you followed my previous advice and already have an N-squared broadphase that can be easily swapped out, you can consider switching to dynamic AABB tree if the number of your rigid bodies is getting too large that the N-Squared broadphase starts dragging the performance of your game.
via Ming-Lun "Allen" Chou | 周明倫
October 8, 2024 at 06:19PM
The text was updated successfully, but these errors were encountered: