从点创建OOBB

Question

从点创建OOBB

19

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

[编辑]

第一个答案没有给出好的结果。我没有大量的点，只有少量的点。我正在进行碰撞几何生成。例如，立方体有36个点（6个面，每个面2个三角形，每个三角形3个点）。第一个帖子的算法在立方体上给出了错误的结果。立方体的示例点：http://nopaste.dk/download/3382 （应返回标识轴）。

- Mark

从我的角度考虑，我会做类似于计算凸包，计算外部点（凸包中的点）的方差矩阵，然后从所述协方差矩阵的特征向量构造 OOBB。这不是最优的，但应该能产生不错的结果。有关最佳算法，请参见例如 http://www.springerlink.com/index/L28G0XK0P631U051.pdf（不幸的是需要付费）。 - Staffan

我在大学上过这门课，模糊地记得必须先找到两个最远的点，并将它们之间的直线作为OBB的一个轴，然后从那里构建另外两个轴。这个答案非常不完整，但这就是为什么我把它作为评论留下来的原因。 - Dan F

3D中的OOBB问题比较难，见这里。那里提到的O'Rourke的论文可以在这里找到。 - n. m.

如果您有时间，请查看：http://gabyx.github.io/ApproxMVBB/ - Gabriel

可能将此如何计算多个曲线的OBB？移植到3D，并使用递归提高精度会有所帮助。 - Spektre

3个回答

10

首先你需要计算点的质心，伪代码如下：

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

那么你需要计算协方差矩阵

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

注意，mult是通过(1x3)矩阵乘法和(3x1)矩阵乘法进行计算的，结果是一个3x3的矩阵。

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

- davidnr

1

请注意，这是一种近似的方法。 - n. m.

@n.m. 是的，但考虑到它的易于计算性，对于大多数应用程序来说应该已经足够了。 - Christian Rau

@Mark - 这个答案很好。这个解决方案非常接近主成分分析（PCA）。在最严格的意义上，它是一种“近似”，正如n.m.所述。然而，不要让这个标签阻止你使用它。这种方法将准确地描述数据的统计属性所定义的边界内的3D点集（即点数、采样密度、采样分布等）。 - Throwback1986

@Throw @Christian 这个方法在非常简单的情况下给了我错误的结果。我已经编辑了我的答案，请看一下。 - Mark

@Mark，你认为实现davidnr会得到好的结果吗？我一直在网上追踪obb计算，以便更好地理解它，这是第一个似乎能够给出一些更好理解的例子。 - Franky Rivera

6

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

如果您有时间，请访问：http://gabyx.github.io/ApproxMVBB/

该库与C++11兼容，仅需要Eigenhttp://eigen.tuxfamily.org即可。测试表明，在合理的时间内（约5-7秒，取决于您对近似值的设置），可以计算出3D中1.4亿个点的近似值。

- Gabriel

1

这是一个糟糕的库，非常难以集成。 - Raaj

你有什么问题吗？也许我可以帮忙。在Linux上构建并使用find_package(ApproxMVBB,...很容易将其用于你的项目中。如果与其他库集成困难，请考虑在GitHub上添加一个问题。 - Gabriel

我之前尝试过这个。当时希望能够与PCL集成，但是无法使其正常工作。如果有空的话，我可能会再回头看一下。 - Raaj

1

可以将PCL的点云集成或至少与ApproxMVBB进行接口，我以前曾经使用过它，我会看看能否在库中提供一个示例。 - Gabriel

Gabriel，你有使用 PCL 库的示例代码吗？ - DrunkenMaster

很遗憾，我最近没有在这方面工作过。不过我想有一个分支：https://github.com/tyronedong/ApproxMVBB-backup/blob/master/example/approxMVBB/src/main.cpp 看这里。 - Gabriel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- brainjam · Accepted Answer

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”文件实现了一种计算包含点的最小体积的盒子的算法。此方法计算点的凸包，一个凸多面体。最小体积的盒子要么有一个与凸多面体的一个面重合，要么其轴方向由凸多面体的三条互相垂直的边给出。每个凸多面体的面都通过PCA方法进行处理。将多面体投影到平面上，计算包含投影的最小面积矩形，并计算投影到面垂线上的最小长度区间。最小面积矩形和最小长度区间组成一个候选框。然后处理凸多面体的所有三条边。如果有任何三线互相垂直，则计算具有沿着这些边方向的轴的最小框。在所有这些框中，体积最小的是包含原始点集的最小体积框。

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

在http://www.gamedev.net/topic/320675-how-to-create-oriented-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和 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中找到凸包查找器以及计算包含一组平面点的最小区域框的方法——我使用旋转卡尺法来实现。