从点创建OOBB [英] Creating OOBB from points

问题描述

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

How can I create minimal OOBB for given points? Creating AABB or sphere is very easy, but I have problems creating minimal OOBB.

答案没有得到我好的结果。我没有巨大的点云。我有点点数。我在做碰撞几何生成。例如，立方体有36个点（6个边，每个2个三角形，每个三角形3个点）。和第一个帖子的算法给多维数据集的坏结果。多维数据集的示例点： http://nopaste.dk/download/3382 （应返回同一轴）

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)

推荐答案

PCA /协方差/特征向量方法基本上找到近似于对象顶点的椭圆体的轴。它应该为随机对象工作，但会对对称对象（如立方体）产生不良结果。这是因为立方体的近似椭圆体是球体，而球体没有明确定义的轴。所以你没有得到你期望的标准轴。

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.

也许如果你事先知道一个对象是，例如，一个多维数据集，你可以使用一个专门的方法，并使用PCA作为一切。

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.

另一方面，如果你想计算真正的OBB，你可以使用现有的实现 http://www.geometrictools.com/LibMathematics/Containment/Containment.html
（特别是 http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox3.cpp ）。

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 (specifically http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox3.cpp). I believe this implements the algorithm alluded to in the comments to your question.

从该页面引用：

ContMinBox3文件实现了
算法，用于计算包含
点的
minimum-volume框。这个方法计算
凸包的点，一个凸
多面体。最小体积盒
或者具有与凸多面体的
面重合的面或者具有由
相互垂直边缘的三个
给出的
轴方向多面体。
凸多面体的每个面由
处理，将多面体投影到面的平面
，计算包含
投影的
最小面积矩形，以及计算包含
的
最小长度间隔投影到面的
的垂线上。最小面积矩形
和最小长度间隔组合到
形成候选框。然后凸多面体的边的所有三元组
被处理
。如果任何三元组具有相互的
垂直边缘，则计算轴在
边缘的方向上的最小框
。在所有这些框中，
，最小卷的
是包含
原点集的最小卷框。

The ContMinBox3 files implement an algorithm for computing the minimum-volume box containing the points. This method computes the convex hull of the points, a convex polyhedron. The minimum-volume box either has a face coincident with a face of the convex polyhedron or has axis directions given by three mutually perpendicular edges of the convex polyhedron. Each face of the convex polyhedron is processed by projecting the polyhedron to the plane of the face, computing the minimum-area rectangle containing the projections, and computing the minimum-length interval containing the projections onto the perpendicular of the face. The minimum-area rectangle and minimum-length interval combine to form a candidate box. Then all triples of edges of the convex polyhedron are processed. If any triple has mutually perpendicular edges, the smallest box with axes in the directions of the edges is computed. Of all these boxes, the one with the smallest volume is the minimum-volume box containing the original point set.

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

If, as you say, your objects do not have a large number of vertices, the running time should be acceptable.

在 http://www.gamedev.net/topic/320675-how-to-create-oriented-bounding-box/ 上述图书馆的作者对这一主题进行了更多的阐述：

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:

Gottschalk的OBB构建方法是计算点集的协方差矩阵。该矩阵的特征向量是OBB轴。点的平均值是OBB中心。 OBB不保证具有所有包含盒的最小体积。通过递归地分割顶点是点集的三角形网格来构建OBB树。

Gottschalk's approach to OBB construction is to compute a covariance matrix for the point set. The eigenvectors of this matrix are the OBB axes. The average of the points is the OBB center. The OBB is not guaranteed to have the minimum volume of all containing boxes. An OBB tree is built by recursively splitting the triangle mesh whose vertices are the point set. A couple of heuristics are mentioned for the splitting.

包含点集的最小体积框（MVB）是包含点的凸包的最小体积框。船体是凸多面体。基于Joe O'Rourke的结果，MVB由多面体的面或由多面体的三个垂直边缘支撑。 由面支持意味着MVB具有与多面体面一致的面。 由三个垂直边缘支持意味着MVB的三个垂直边缘与多面体的边缘重合。

The minimum volume box (MVB) containing a point set is the minimum volume box containing the convex hull of the points. The hull is a convex polyhedron. Based on a result of Joe O'Rourke, the MVB is supported by a face of the polyhedron or by three perpendicular edges of the polyhedron. "Supported by a face" means that the MVB has a face coincident with a polyhedron face. "Supported by three perpendicular edges" means that three perpendicular edges of the MVB are coincident with edges of the polyhedron.

如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变得稍大，但仍然有一个体积远小于

As jyk indicates, the implementations of any of these algorithms is not trivial. However, never let that discourage you from trying :) An AABB can be a good fit, but it can also be a very bad fit. Consider a "thin" cylinder with end points at (0,0,0) and (1,1,1) [imagine the cylinder is the line segment connecting the points]. The AABB is 0 <= x <= 1, 0 <= y <= 1, and 0 <= z <= 1, with a volume of 1. The MVB has center (1,1,1)/2, an axis (1,1,1)/sqrt(3), and an extent for this axis of sqrt(3)/2. It also has two additional axes perpendicular to the first axis, but the extents are 0. The volume of this box is 0. If you give the line segment a little thickness, the MVB becomes slightly larger, but still has a volume much smaller than that of the AABB.

您选择哪种类型的方块取决于您自己的应用程式资料。

Which type of box you choose should depend on your own application's data.

的所有这些都在我的www.geometrictools.com网站。我使用中间分裂启发式为边界体积树。 MVB结构需要2D中的凸包探测器，3D中的凸包探测器，以及用于计算包含一组平面点的最小面积盒的方法 - 我使用旋转卡尺方法来实现这一点。

Implementations of all of this are at my www.geometrictools.com website. I use the median-split heuristic for the bounding-volume trees. The MVB construction requires a convex hull finder in 2D, a convex hull finder in 3D, and a method for computing the minimum area box containing a set of planar points--I use the rotating caliper method for this.

这篇关于从点创建OOBB的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！