Bounding Box Evolved

Making collision objects in 3D games is one of those time-consuming chores, but it is an absolute performance requisite for physics simulators. The early releases of our engine only supported simple primitive collisions (e.g. boxes, spheres, … etc), which was quite efficient to test against at run-time. We had to produce collision objects for a lot of different meshes. So to simplify the creation of those objects at that time, I implemented a collision generator tool for Softimage. The tool generates both axis-aligned bounding box (AABB) and oriented bounding box (OBB) for any number of selected vertices.

The following video shows the tool in action.

This is a self-installed plugin (2.8KB) for the tool.

As you might notice from the code, the AABB implementation is about getting the min and max for each axis for the selected vertices. The OBB is a brute-force searching algorithm. It starts from AABB then incrementally rotate and scale the BBox until it reaches the minimum volume. This algorithm was very effective and easy to implement. However, for a large number of points it was noticeably slow (as one might expect).

To optimize this calculation time, instead of blindly searching for the solution using the brute-force algorithm, another version was done using Genetic Algorithms (GA) to have a more efficient search that reaches the solution much faster. The GA starts by randomly sampling a few states for the BBox. Each state is composed of scaling and rotation. Similar to brute-force, all states are evaluated based on their corresponding BBox volume. Only two best-states (parent states) are chosen for the next iteration (in GA called next generation). The same process is repeated for the next generation. However, this time children states are sampled within the range of their parents. As this process continues for a few generations, grand-children will evolve towards a best-fitting BBox.
Keep in mind that limiting children sampling between their parents can sometimes cause convergence to a local minima. Thus it is useful to introduce mutant states that are sampled outside parents range. This might introduce a few more extra generations before reaching the final solution, however it globally helps getting the best solution.
As I learned more about the topic later, I found other algorithms can be used to generate OBBs efficiently. One is using Principle Component Analysis (PCA). This would be the next evolution of this bounding box tool.