c++ - 从点创建 OOBB

Question

如何为给定点创建最小的 OOBB？创建 AABB 或球体非常容易，但创建最小 OOBB 时遇到问题。

[编辑]

第一个答案没有给我带来好的结果。我没有大量的点云。我的积分很少。我正在做碰撞几何生成。例如，立方体有 36 个点(6 个边，每个三角形 2 个，每个三角形 3 个点)。第一篇文章的算法对立方体给出了不好的结果。立方体的示例点:http://nopaste.dk/download/3382 (应该返回标识轴)

Answer 1

PCA/协方差/特征向量方法本质上是找到近似于对象顶点的椭圆体的轴。它应该适用于随机对象，但对于像立方体这样的对称对象会产生不好的结果。这是因为立方体的近似椭球是球体，而球体没有明确定义的轴。所以你没有得到你期望的标准轴。

也许如果您事先知道一个对象是一个立方体，例如，您可以使用一种专门的方法，并将 PCA 用于其他一切。

另一方面，如果您想计算真正的 OBB，您可以使用现有的实现，例如http://www.geometrictools.com/LibMathematics/Containment/Containment.html (存档于 https://web.archive.org/web/20110817024344/geometrictools.com/LibMathematics/Containment/Containment.html 和 https://github.com/timprepscius/GeometricTools/blob/master/WildMagic5/LibMathematics/Containment/Wm5ContMinBox3.cpp)。我相信这实现了您问题评论中提到的算法。

引用该页面:

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.

如您所说，如果您的对象没有大量顶点，则运行时间应该是可以接受的。

在 http://www.gamedev.net/topic/320675-how-to-create-oriented-bounding-box/ 的讨论中上述库的作者对该主题进行了更多说明:

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.