从点创建OOBB

Question

如何为给定点创建最小的OOBB？创建AABB或sphere非常简单，但我在创建最小的OOBB时遇到了问题。

编辑

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

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-oriented-bounding-box/的一次讨论中，上面的库的作者对这个主题进行了更多的阐述：

Gottschalk的方法是计算点集的协方差矩阵。该矩阵的特征向量是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的凸包搜索器，以及一种计算包含一组平面点的最小面积框的方法--为此，我使用旋转卡尺方法。

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

C++ online中有一个新的库ApproxMVBB，用于计算最小体积边界框的近似。它是在MPL 2.0许可下发布的，由我编写。

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

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