Day 150: Bounding Volume Hierarchy (BVH)

I'm now starting to work on the collision engine. Until now the collisions were faked (like in the springs for instance). One of the major problems in a complete rigid body system is the collision detection.
It is done in two phases: the broad-phase detection and the narrow phase detection.
The first one detects possible contacts, while the second performs more expensive collision queries in order to find the final contacts.
Right now I'm working on the first phase, and indeed the collisions will be evaluated only with sphere (or at the most box) colliders. The major optimization is to reduce the number of collisions to evaluate, which is Theta(n^2). To do so, it is possible to use two approaches (or even combine them):

- Bounding Volume Hierarchies (BVH): Holds in memory a tree of simple rigidbodies, like spheres. Each parent must be just big enough to contain the children. This is a very good way to reduce contact queries, because if two nodes are not colliding, none of the children will.

Today I wrote a template class to represent this tree, with a method that returns a vector of all the contacts inside a node. The class accept a template collider class, which must satisfy a few conditions, like having a "is_overlapping" method.

What I still don't have is a way to automatically build the BVH, I'll see to that tomorrow.

- Spatial Partitioning: This technique divides the space in a grid, and each cell keeps track of the rigidbodies contained in it. This allows to reduce the number of possible contact.
I'll finish to implement the BVH, then I'll implement it.