从点创建 OOBB
如何为给定点创建最小 OOBB？创建 AABB 或球体非常容易，但创建最小的 OOBB 时遇到问题。
[编辑]
第一个答案没有给我带来好的结果。我没有大量的积分。我的积分很少。我正在做碰撞几何生成。例如，立方体有 36 个点（6 个边，每个边 2 个三角形，每个三角形 3 个点）。第一篇文章中的算法给出了立方体的糟糕结果。立方体的示例点： http://nopaste.dk/download/3382 （应返回身份轴）
How can I create minimal OOBB for given points? Creating AABB or sphere is very easy, but I have problems creating minimal OOBB.
[edit]
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)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
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）。我相信这实现了您问题的评论中提到的算法。
引用该页面：
如果正如您所说，您的对象没有大量顶点，则运行时间应该是可以接受的。
在 http://www.gamedev 的讨论中.net/topic/320675-how-to-create-orient-bounding-box/ 上述库的作者对这个主题有更多的了解：
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.
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.
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.
Quoting from that page:
If, as you say, your objects do not have a large number of vertices, the running time should be acceptable.
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:
首先，您必须计算点的质心，
然后用伪代码计算协方差矩阵。
请注意，mult 执行 (3x1) 矩阵乘以 (1x3) 矩阵乘法，结果是一个 3x3 矩阵。
C 矩阵的特征向量定义了 OBB 的三个轴。
First you have to compute the centroid of the points, in pseudcode
then you have to compute the covariance matrix
Note that the mult performs an (3x1) matrix multiplication by (1x3) matrix multiplication, and the result is a 3x3 matrix.
The eigenvectors of the C matrix define the three axis of the OBB.
在线 C++ 中有一个新库
ApproxMVBB，它可以计算最小体积边界框的近似值。它是根据 MPL 2.0 许可证发布的，由我编写。如果您有时间，请查看： http://gabyx.github.io/ApproxMVBB/
该库是兼容 C++11，仅需要 Eigen http://eigen.tuxfamily.org。
测试表明，根据您的近似设置，可以在合理的时间内（大约 5-7 秒）计算出 3D 中 1.4 亿个点的近似值。
There is a new library
ApproxMVBBin C++ online which computes an approximation for the minimum volume bounding box. Its released under MPL 2.0 Licences, and written by me.If you have time look at: http://gabyx.github.io/ApproxMVBB/
The library is C++11 compatible and only needs Eigen http://eigen.tuxfamily.org.
Tests show that an approximation for 140Million points in 3D can be computed in reasonable time (arround 5-7 seconds) depending on your settings for the approximation.