I'd like to present a research paper that I worked on earlier this year. It relates to a common problem in game/graphics dev so it might be useful to some of you guys as well.
In short: I have implemented a new algorithm for finding tight-fitting enclosing OBBs for 3D meshes. For suitably "nice" inputs, it runs in O(n * sqrt(n) * log^2(n)) time compared to previous best O(n^3) from O'Rourke. For degenerate/adversarial inputs, it runs in worst case O(n^3 * log n) time. A formal proof of the optimality of this new algorithm is unfortunately beyond reach, but for all tested cases, the algorithm has been able to find the optimal minimum volume OBB.
Find the links here:
- the paper: An Exact Algorithm for Finding Minimum Oriented Bounding Boxes, Jukka Jylänki, 2015.
- source code in MathGeoLib: https://github.com/juj/MathGeoLib/blob/master/src/Geometry/OBB.cpp, search for OBB::OptimalEnclosingOBB.
- live web page to try it out: Minimum Volume OBB Calculator.
- a blog post about the paper: clb.demon.fi: An Exact Algorithm for Finding Minimum Oriented Bounding Boxes.
I hope you find this interesting and useful!