从点创建 OOBB [英] Creating OOBB from points

问题描述

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

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

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

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)

推荐答案

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

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.

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

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.

另一方面，如果您想计算真正的 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).我相信这实现了您问题评论中提到的算法.

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.

引用该页面:

ContMinBox3 文件实现了一个计算算法包含点.该方法计算点的凸包，一个凸多面体.最小体积盒子要么有一张脸与凸多面体的面或具有三个给定的轴方向相互垂直的边缘凸多面体.每一张脸凸多面体由将多面体投影到平面人脸，计算最小面积矩形包含预测，并计算包含投影到垂直的脸.最小面积矩形和最小长度间隔结合到形成一个候选框.然后所有三元组凸多面体的边是处理.如果任何三元组相互垂直边，最小的盒子与轴的方向计算边缘.在所有这些盒子中，体积最小的是包含原点集.

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.

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

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 构建 OBB 的方法是计算点集的协方差矩阵.该矩阵的特征向量是 OBB 轴.点的平均值是OBB中心.不保证 OBB 具有所有包含盒子的最小体积.通过递归分割以点集为顶点的三角形网格来构建 OBB 树.提到了一些用于拆分的启发式方法.

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.

包含点集的最小体积框 (MVB) 是包含点的凸包的最小体积框.外壳是一个凸多面体.根据 Joe O'Rourke 的结果，MVB 由多面体的一个面或多面体的三个垂直边支撑.由面支撑"意味着MVB具有与多面体面重合的面.由三个垂直边支撑"是指MVB的三个垂直边与多面体的边重合.

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.

正如 jyk 所指出的，任何这些算法的实现都不是微不足道的.但是，永远不要让这阻止您尝试 :) AABB 可能非常适合，但也可能非常不适合.考虑一个端点在 (0,0,0) 和 (1,1,1) 的薄"圆柱体[想象圆柱体是连接这些点的线段].AABB 为 0 <= x <= 1, 0 <= y <= 1, and 0 <= z <= 1, 体积为 1.MVB 有中心 (1,1,1)/2，轴 (1,1,1)/sqrt(3)，以及该轴的范围 sqrt(3)/2.它还有两个垂直于第一个轴的附加轴，但范围为 0.这个盒子的体积为 0.如果给线段一点粗细，MVB 会变得稍大，但体积仍然比AABB 的.

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.

所有这些的实现都在我的 www.geometrictools.com 网站上.我对边界体积树使用中值分割启发式.MVB 构造需要一个 2D 凸包查找器，一个 3D 凸包查找器，以及一种计算包含一组平面点的最小面积框的方法——我为此使用了旋转卡尺方法.

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.

这篇关于从点创建 OOBB的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！