How to create Oriented Bounding Box

What do you mean by 'create it'. Do you mean how to find an optimal or near-optimal OBB for a point set?

Yes :-)

It's not too bad

1) Orientate the object to it's identity.
2) Search through all the vertices finding the min(x,y,z) and the max(x,y,z). This will be the min and max of your obb.
3) Then simply rotate it back.

Pardon me if I'm wrong.
But that's work only if AABB is optimal OBB in objects identity.

You're correct, should have stated that assumption. To truely, create a tight fitting OBB is much more complicated then the solution I presented.

I don't know the actual solution to find the tightest fit - but here is an adhoc one I came up with.

1) Pick the 3 basis axis(x,y,z) project each vertex onto those axis finding the min and max for each. Store these values

2) Rotate the basis axis by some small step(or perhaps large like 45 degree's)

3) Repeat step 1 and check if the area of the min to max is smaller then the new one calculated.


If you continue to do that for a full circle you should get the best fitting.

I found one algorithm in czech language but only slides, so I don't know how to do it exactly, i only know it can be done :-))
But there is one reference to [gottschalk 96]

Maybe this is it
http://www.cs.unc.edu/~geom/theses/gottschalk/main.pdf
There is chapter called "Fitting an OBB".

The Gottschalk paper is a standard reference on OBB fitting, but the algorithm is not trivial to implement. Unless you really need to fit to an arbitrary model for some reason, the modelspace AABB (as mentioned previously) might be a better (or at least easier) choice.

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.

I have book "Mathematics for 3D Game Programming and Computer Graphics" and there is one algorithm for finding OBB, based on statics.
You can look on results
Good result
And when few vertices is far from others:
Bad result
It was pretty fun to do it.
Yellow is AABB. White is OBB.

Ok, I was really upset with PCA ;-))
So I came up with better solution, first of all find convex hull, and then OBB. Because OBB has one face in the same plane as face from convex hull.
And the results are 100% accurate ;-)