Does anyone know of a database of known minimal oriented bounding boxes for a set of models? I’m working on some OBB fitting code that needs to come in at < 1% of the minimal answer. Since calculating the minimal answer is computationally expensive I’m hoping someone has already created such a database.
How do you define “minimal answer”? By volume? By surface area? By cross-section?
were looking for the least volume answer.
I wonder why you mentioned “database”, instead of algorithm.
Anyway, my first idea is to brute-force it initially, on a gpu.
Create a 3x3 rotational matrix with rotations around X and Y axis from 0…359 degrees, 1 degree per step (129600 possibilities). For each iteration, transform the model’s vertices by that matrix. Collect the min/max x/y/z from the vertices, to generate an AABB. Measure its volume.
Later revisit a few of the rotations with smallest volumes, iterate again , this time 100x100 times with 0.01 degree per step.
This approach might give you precision better than 0.001%, I think.
A little improvement on brute force is brute force on boundary vertexes.
You can find the convex mesh in n log(n).
Just an idea, if you compute the covariance axis you have a good starting point so you don’t have to rotate in all direction but only around an axis. But in this case I can’t demonstrate that you will get the minimum obb
The book Real-Time Collision Detection and site provides a good survey of global algorithms.
The books itself starts with a guess and then proceeds with an empirical optimization algorithm (prone to “fall” into local minima). I think Ilan Dinev’s 1 degree idea (you can make it a one-radian or whatever idea), followed by such an algorithm pass will produce good results.
Try some other bounding volume as well (say k-DOP), if the results are not satisfying.
BTW: Rosario, Ilan, why do books always discuss finding minimal OBBs, why not minimal parallelepipeds? When I was implementing my OBB finder I saw the minimal parallelepipeds sometimes gave better results and it is trivial to look for them instead of OBBs.