Bounding Volume Hierarchy

What is Bounding Volume Hierarchy

#

Bounding Volume Hierarchy (BVH) is a self-balancing binary tree structure, each node stores the information about bounding volume wraps the node and all its children. It was widely used in collision detection by game engines.

BVH is a typical application of self-balancing binary tree, it’s efficient, elegant, and actually simple.

In this article, we will explain how BVH work, and how to implement it. We will explain it in 2D, which is easier to understand, then smoothly extend to 3D. Also, for simplify, we will use Axis-Aligned Bounding Box (AABB) to represent the bounding volume, which is the simplest situation and we will introduce it soon.

Requirements

#

We assume you meet following requirements:

• Familiar with AVL tree and know how to implement it
• Can read C++ code (or you can just skip the implementation and implement it by yourself with your preferred language)

Overview

#

In the classic FC game Battle City, players driving a tank to shoot with enemies. When player pressed the fire button, a cannon shot out from the tank, flying straight to enemies. Then it’s the computer’s (actually programmer’s) duty to checkout if the cannon collided with something.

There are many objects on screen, the player, enemies, walls, etc. And to provide a good experience, we have to output 30-60 frames every second. So we must finish our collision check in a short period with a efficient algorithm.

Let’s simplify our scenario to basic geometries, stars are the objects may be collided, and the arrow is the cannon’s moving direction.

Our goal is to find out the object been hit, which we have filled with red color.

Axis-Aligned Bounding Box (AABB)

#

Here in our demonstration, we use a star representing collision targets, which is much simplified. In real games, objects are much more complicated. It’s very helpful if we use a container to wrap our object, and only check if we have collided with this container. AABB is the simplest container for us.

AABB is the bounding box of a shape, which is axis aligned, as the name indicates. Here we have a 2D geometry in the diagram, it’s AABB is the box made by (minX, minY) and (minY, maxY). So, for a AABB, we can use only two points to represent it.

The node in our tree should looks like:

// Node in the tree
class Node {
	float x1, y1; // the lower point of AABB
	float x2, y2; // the higher point of AABB
	Node *parent; // for backtrack
	Node *left;
	Node *right;
	bool isLeaf; // is leaf or internal node
	
	Node(float x1, float y1, float x2, float y2, bool isLeaf);
}

After applying AABB, we have simplified the complex of object’s shape, and our task now was shown as diagram above.

But then comes with the complex of object’s number. In real games, the number of objects are huge, it’s too inefficient to check collision with them one by one. Since we have said that BVH is a tree structure, you may have come out the idea of dividing them.

Here we have divided our objects into two groups. After checking the collision container, we can quickly drop out the bottom group, which contains 4 objects. It saves a lot of time.

But there are vary ways to groups them, how do we choose the best group way to build the AVL tree most efficient to search hit target? There must be some evaluation.

Surface Area Heuristic (SAH)

#

Think about the question: here we have 3 shapes (a rectangle, a triangle, and a line) in the 2D plane, which shape has the max probability to be hit?

Aware that the bullet may come from any direction.

Intuitively, you may think the one with bigger area is more possibly being hit. But think a minute more, does the line, with zero area, has no possibly to be hit?

The answer is: the object with longer perimeter is more likely to be hit.

Think about these two rectangles, and we only consider bullet come from 4 directions. From each direction, we can only see a side line of the rectangle, longer the line, higher probability to be hit. We sum up the side line in 4 directions, and we got the perimeter.

In real case, bullets come from any directions. So it’s more precise to get the integral of geometry’s projection in every direction. But it’s OK to just use perimeter.

float getSA(Node *node) {
  if (!node) return 0;
  // since AABB is axis aligned,
	// it's easy to compute perimeter
  return 2.0f * (node->x2 - node->x1 + node->y2 - node->y1);
}

In 3D, bullets come from 6 directions to hit the box, bigger the surface area, higher probability to be hit. Also, integral of box’s projection area in every direction is more precise.

This is Surface Area Heuristic (SAH), the probability of a object being hit is proportional to it’s surface area.

Cost metric of a tree

#

We define the cost metric of a tree as the sum of all it’s nodes’ SAH, including root, internal nodes and leaves.

The tree with less cost means that it’s bounding boxes (including internal boxes) are more tight, less waste and more precise.

Here we have two trees representing two different divisions.

Compare these two, we can find out that their root and leaves’ SA have no difference, only internal nodes varies. That is to say, when computing the cost of a tree, we can ignore root and leaves, only compute internal nodes.

Tree

#

Here is the definition of Tree class.

class Tree {
	// dummy node is a commonly-used trick to modify tree safely
	Node *dummyRoot;
	void insertLeaf(Node *newLeaf);
	void removeLeaf(Node *rmLeaf);
	void updateLeaf(Node *updLeaf, float x1, float y1, float x2, float y2);
	
	Tree();
}

Insert

#

A tree begins with a insertion. Don’t be afraid, SAH will guide us to find out the best place to insert.

SAH insertion cost

#

The cost of a insertion is the increased SAH after insertion.

Observe the change after insert leaf node 12 as sibling of node 10. As we marked out, only the internal nodes in the path matters. node C and node G’s SAH changed, and node J is the new created internal node.

So the cost should be:

There are two parts:

• Direct cost: SA(J)

  The SA of new created internal node

• Inherited cost: ΔSA(C) + ΔSA(G)

  The increased SA caused by refitting the ancestor’s bounding boxes

Branch and Bound Algorithm

#

Every node in the tree is a potential sibling of our new leaf. It’s expensive to evaluate all of them. Here is the Branch and Bound Algorithm to speed it up.

The main idea is:

• Search though tree recursively
• Skip sub-trees that cannot possibly better

Every node in the tree is a potential sibling of our new leaf. It’s expensive to evaluate all of them. Here is the Branch and Bound Algorithm to speed it up.

The main idea is:

• Search though tree recursively
• Skip sub-trees that cannot possibly better

Suppose that the new leaf node 12 has arrived the position of node E, we have to make a choice from these 3 options:

• stay here, which means we choose current node as new leaf’s sibling
• go left child and keep seeking
• go right child and keep seeking

What if we choose to stay here?

We will create a new internal node K, and make it be the parent of node E and node 12. The cost of doing this is:

Since the inherited cost ( ΔSA(A) + ΔSA(B) ) will keep the same whatever which position the new leaf was inserted, so we could just ignore them.

Then, what is SA(K)? Apparently, it’s the union of node E and node 12.

Union of two AABBs

// simplified code, some edge cases ignored
float getUnionSA(vector<Node*> nodes) {
	Node *node = nodes[0];
	float x1 = node->x1;
	float y1 = node->y1;
	float x2 = node->x2;
	float y2 = node->y2;
	for (int i = 1; i < nodes.size(); i++) {
		node = nodes[i];
		x1 = min(x1, node->x1);
		y1 = min(y1, node->y1);
		x2 = max(x2, node->x2);
		y2 = max(y2, node->y2);
	}
	return 2.0f * (x2 - x1 + y2 - y1);
}

And the cost of choosing left child (node H) and right child (node I) is:

and, ΔSA(E) = SA(K) - SA(E), because the impact to current hierarchy is the same though the leaf was inserted in children.

Since the costs of all these 3 options have revealed, we now have enough information to make decision.

Once we had found the best sibling, we create a new internal node, make it be the parent of sibling and new leaf. Then we trackback to root, refit all ancestors.

// simplified code, some edge cases ignored
void insertLeaf(Node *newLeaf) {
  if (dummyRoot->left == NULL) {
    dummyRoot->left = newLeaf;
    newLeaf->parent = dummyRoot;
    return;
  }

  // ==== stage 1: find the best sibling ====
  Node *sibling = findBestSibling(dummyRoot->left, newLeaf);
  // ==== stage 2: create new parent add insert ====
  Node *newParent = new Node(
      std::min(sibling->x1, newLeaf->x1),
      std::min(sibling->y1, newLeaf->y1),
      std::max(sibling->x2, newLeaf->x2),
      std::max(sibling->y2, newLeaf->y2),
      false
    );
  Node *oldParent = sibling->parent;
  if (oldParent->left == sibling)
    oldParent->left = newParent;
  else
    oldParent->right = newParent;
  newParent->parent = oldParent;
  newParent->left = sibling;
  newParent->right = newLeaf;
  sibling->parent = newParent;
  newLeaf->parent = newParent;
  // ==== stage 3: trackback ro root, refit and rotate ====
  Node *parent = oldParent;
  while (parent) {
    refit(parent);
    rotate(parent);
    parent = parent->parent;
  }
}

Node* findBestSibling(Node *node, Node *leaf) {
  while (node && !node->isLeaf) {
    float cost = getUnionSA({node, leaf});
    float delta = cost - getSA(node);
    float costLeft = node->left ? getUnionSA({node->left, leaf}) : cost + 1.0f;
    float costRight = node->right ? getUnionSA({node->right, leaf}) : cost + 1.0f;
    if (cost < costLeft && cost < costRight)
      break;
    if (costLeft < costRight)
      node = node->left;
    else
      node = node->right;
  }
  return node;
}

Remove

#

Removing a leaf is intuitional, we just delete it from parent, and backtrack to root, refit all ancestors in path.

// simplified code, some edge cases ignored
void removeLeaf(Node *rmLeaf) {
  // delete
  Node *parent = rmLeaf->parent;
  if (parent->left == rmLeaf)
    parent->left = NULL;
  else
    parent->right = NULL;

  // trackback to root, refit and rotate
  while (parent) {
    refit(parent);
    rotate(parent);
    parent = parent->parent;
  }
}

Update

#

To update a leaf, we just remove it from the tree, and insert a new one with updated value.

// simplified code, some edge cases ignored
void updateLeaf(Node *updLeaf, float x1, float y1, float x2, float y2) {
  // remove
  removeLeaf(updLeaf);
  // insert with updated value
  insertLeaf(new Node(x1, y1, x2, y2, true));
}

Rotate

#

We have not finish yet, we need another operation named rotation. Without it, the scenario named sorted input could easily wreck our tree.

There are 4 objects in a row, and was added to scene one by one, from 1 to 4. After 4 times of insertion, our tree becomes the right. I has no difference to a linked list.

We have to dynamically rotate our tree to avoid this.

There are 4 kinds of rotations:

• type 1: exchange C and D

  only SA(B) changed: SA(D∪E) → SA(F∪G∪E)

• type 2: exchange C and E

  only SA(B) changed: SA(D∪E) → SA(D∪F∪G)

• type 3: exchange B and F

  only SA(C) changed: SA(F∪G) → SA(D∪E∪G)

• type 4: exchange B and G

  only SA(C) changed: SA(F∪G) → SA(F∪D∪E)

Once we have inserted or removed a node, while backtracking to root, for every ancestor, try to rotate it with max SA drop (if exist), after refitting.

// simplified code, some edge cases ignored
void rotate(Node *node) {
  Node *left = node->left;
  Node *right = node->right;
  if (!(left && right)) return;

  Node *ll = left->left;
  Node *lr = left->right;
  Node *rl = right->left;
  Node *rr = right->right;

  // ==== compute delta SA for 4 types of rotations ====
  float SA_B = getSA(left);
  float SA_C = getSA(right);

  float SA_FGE = getUnionSA({rl, rr, lr});
  float SA_DFG = getUnionSA({ll, rl, rr});
  float SA_DEG = getUnionSA({ll, lr, rr});
  float SA_FDE = getUnionSA({rl, ll, lr});

  float delta1 = SA_FGE - SA_B;
  float delta2 = SA_DFG - SA_B;
  float delta3 = SA_DEG - SA_C;
  float delta4 = SA_FDE - SA_C;

  // ==== choose the one with max drop ====
  std::array<float, 4> deltas = { delta1, delta2, delta3, delta4 };
  float minDelta = 0;
  int pickIndex = -1;
  for (int i = 0; i < 4; i++) {
    if (deltas[i] < minDelta) {
      minDelta = deltas[i];
      pickIndex = i;
    }
  }

  switch (pickIndex) {
    case -1:
      // do not rotate
      break;
    case 0:
      // rotate type 1
      node->right = ll;
      ll && (ll->parent = node);
      left->left = right;
      right->parent = left;
      refit(left);
      break;
    case 1:
      // rotate type 2
      node->right = lr;
      lr && (lr->parent = node);
      left->right = right;
      right->parent = left;
      refit(left);
      break;
    case 2:
      // rotate type 3
      node->left = rl;
      rl && (rl->parent = node);
      right->left = left;
      left->parent = right;
      refit(right);
      break;
    case 3:
      // rotate type 4
      node->left = rr;
      rr && (rr->parent = node);
      right->right = left;
      left->parent = right;
      refit(right);
      break;
    default:
      break;
  }
}

Code

#

We have covered all the key concepts of BVH. With the key codes provided above, it’s not hard to implement the whole thing by yourself.

And here is the complete code for your reference.

CodeSnippets/BVH at main · Oh-noodles/CodeSnippets

To 3D

#

References

#

box2d.org