从点创建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 (特别是http://www.geometrictools.com/) LibMathematics/Containment/Wm5ContMinBox3.cpp).我相信这可以实现您的问题评论中提到的算法.

从该页面引用:

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

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

在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中的凸形船体探测器,以及计算包含一组平面点的最小区域框的方法 - 我使用旋转卡尺方法.

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秒）内计算出1.4亿个3D点的近似值。