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）。我相信这实现了您问题的评论中提到的算法。

从该页面引用：

ContMinBox3 文件实现了一种算法，用于计算包含点的最小体积框。该方法计算点的凸包，即凸多面体。最小体积盒子要么具有与凸多面体的面重合的面，要么具有由凸多面体的三个相互垂直的边给定的轴方向。凸多面体的每个面通过将多面体投影到面的平面，计算包含投影的最小面积矩形，并计算包含投影到面垂线的最小长度间隔来处理。最小面积矩形和最小长度区间组合形成一个候选框。然后处理凸多面体的所有三元组边。如果任何三元组具有相互垂直的边，则计算具有在边方向上的轴的最小框。在所有这些盒子中，体积最小的盒子是包含原始点集的最小体积盒子。

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

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

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

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

正如 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 的。

您选择哪种类型的框应该取决于您自己的应用程序的数据。

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

Answer 2

首先，您必须以伪代码计算点的质心

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

那么你必须计算协方差矩阵

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

请注意，mult 执行 (3x1) 矩阵乘以 (1x3) 矩阵乘法，结果是 3x3 矩阵。

C 矩阵的特征向量定义了 OBB 的三个轴。

Answer 3

ApproxMVBB在线 C++ 中有一个新库，可以计算最小体积边界框的近似值。它根据 MPL 2.0 许可证发布，由我编写。

如果你有时间看看： http: //gabyx.github.io/ApproxMVBB/

该库与 C++11 兼容，只需要 Eigen http://eigen.tuxfamily.org。测试表明，根据您的近似设置，可以在合理的时间（大约 5-7 秒）内计算出 3D 中 1.4 亿点的近似值。