Creating OOBB from points

Question

How can I create minimal OOBB for given points? Creating AABB or sphere is very easy, but I have problems creating minimal OOBB.

[edit]

First answer didn't get me good results. I don't have huge cloud of points. I have little amount of points. I am doing collision geometry generation. For example, cube has 36 points (6 sides, 2 triangles each, 3 points for each triangle). And algorithm from first post gave bad results for cube. Example points for cube: http://nopaste.dk/download/3382 (should return identity axis)

Answer 1

The PCA/covariance/eigenvector method essentially finds the axes of an ellipsoid that approximates the vertices of your object. It should work for random objects, but will give bad results for symmetric objects like the cube. That's because the approximating ellipsoid for a cube is a sphere, and a sphere does not have well defined axes. So you're not getting the standard axes that you expect.

Perhaps if you know in advance that an object is, for example, a cube you can use a specialized method, and use PCA for everything else.

On the other hand, if you want to compute the true OBB there are existing implementations you can use e.g. http://www.geometrictools.com/LibMathematics/Containment/Containment.html (archived at https://web.archive.org/web/20110817024344/geometrictools.com/LibMathematics/Containment/Containment.html and https://github.com/timprepscius/GeometricTools/blob/master/WildMagic5/LibMathematics/Containment/Wm5ContMinBox3.cpp). I believe this implements the algorithm alluded to in the comments to your question.

Quoting from that page:

The ContMinBox3 files implement an algorithm for computing the minimum-volume box containing the points. This method computes the convex hull of the points, a convex polyhedron. The minimum-volume box either has a face coincident with a face of the convex polyhedron or has axis directions given by three mutually perpendicular edges of the convex polyhedron. Each face of the convex polyhedron is processed by projecting the polyhedron to the plane of the face, computing the minimum-area rectangle containing the projections, and computing the minimum-length interval containing the projections onto the perpendicular of the face. The minimum-area rectangle and minimum-length interval combine to form a candidate box. Then all triples of edges of the convex polyhedron are processed. If any triple has mutually perpendicular edges, the smallest box with axes in the directions of the edges is computed. Of all these boxes, the one with the smallest volume is the minimum-volume box containing the original point set.

If, as you say, your objects do not have a large number of vertices, the running time should be acceptable.

In a discussion at http://www.gamedev.net/topic/320675-how-to-create-oriented-bounding-box/ the author of the above library casts some more light on the topic:

Gottschalk's approach to OBB construction is to compute a covariance matrix for the point set. The eigenvectors of this matrix are the OBB axes. The average of the points is the OBB center. The OBB is not guaranteed to have the minimum volume of all containing boxes. An OBB tree is built by recursively splitting the triangle mesh whose vertices are the point set. A couple of heuristics are mentioned for the splitting.

The minimum volume box (MVB) containing a point set is the minimum volume box containing the convex hull of the points. The hull is a convex polyhedron. Based on a result of Joe O'Rourke, the MVB is supported by a face of the polyhedron or by three perpendicular edges of the polyhedron. "Supported by a face" means that the MVB has a face coincident with a polyhedron face. "Supported by three perpendicular edges" means that three perpendicular edges of the MVB are coincident with edges of the polyhedron.

As jyk indicates, the implementations of any of these algorithms is not trivial. However, never let that discourage you from trying :) An AABB can be a good fit, but it can also be a very bad fit. Consider a "thin" cylinder with end points at (0,0,0) and (1,1,1) [imagine the cylinder is the line segment connecting the points]. The AABB is 0 <= x <= 1, 0 <= y <= 1, and 0 <= z <= 1, with a volume of 1. The MVB has center (1,1,1)/2, an axis (1,1,1)/sqrt(3), and an extent for this axis of sqrt(3)/2. It also has two additional axes perpendicular to the first axis, but the extents are 0. The volume of this box is 0. If you give the line segment a little thickness, the MVB becomes slightly larger, but still has a volume much smaller than that of the AABB.

Which type of box you choose should depend on your own application's data.

Implementations of all of this are at my www.geometrictools.com website. I use the median-split heuristic for the bounding-volume trees. The MVB construction requires a convex hull finder in 2D, a convex hull finder in 3D, and a method for computing the minimum area box containing a set of planar points--I use the rotating caliper method for this.

Answer 2

First you have to compute the centroid of the points, in pseudcode

mu = sum(0..N, x[i]) / N

then you have to compute the covariance matrix

C = sum(0..N, mult(x[i]-mu, transpose(x[i]-mu)));

Note that the mult performs an (3x1) matrix multiplication by (1x3) matrix multiplication, and the result is a 3x3 matrix.

The eigenvectors of the C matrix define the three axis of the OBB.

Answer 3

There is a new library ApproxMVBB in C++ online which computes an approximation for the minimum volume bounding box. Its released under MPL 2.0 Licences, and written by me.

If you have time look at: http://gabyx.github.io/ApproxMVBB/

The library is C++11 compatible and only needs Eigen http://eigen.tuxfamily.org. Tests show that an approximation for 140Million points in 3D can be computed in reasonable time (arround 5-7 seconds) depending on your settings for the approximation.