Collision detection algorithms such as the GJK are expensive operations. A game engine tries to minimize the use of the GJK only on objects that are most likely to collide with one another. To determine which objects are most likely to collide, a game engine parses the space of every model and creates a tree-like structure known as a Boundary Volume Hierarchy (BVH).
The BVH algorithm is a recursive algorithm that parses the space of every object and assigns them to a particular node in the binary tree. The algorithm recursively analyzes each node until each node contains two objects most likely to collide.
I want to help you visualize how the BVH algorithm works. It is not hard to implement. However, having a visual depiction of the algorithm will help you avoid common mistakes.
Let's begin,
BVH Algorithm
1) Create a root node.
2) Create an AABB box bounding every object in the scene.
3) Assign the AABB box to the root node.
4) Find the AABB longest axis and sort each object along this direction.
5) Find a (split index) midpoint that divides the bounding box.
6) Using the split index, divide the scene into a left and right side.
7) For each side, create an AABB bounding volume containing their respective objects.
8) Create a left and right node in the binary tree, and attach its corresponding AABB bounding volume.
9) Repeat steps 4-8 on each node until each node contains at most two objects. For example:
Repeating steps 4-6 for the left node
Repeating steps 6-8 for the left node
Repeat this process for the right node.
The BVH algorithm terminates when each node in the tree contains at most two objects. Hope this helps.
