在Unity中为一组3D点找到一个有向边界框

Question

我有一组3D点或小球，需要在Unity 3D中使用最小的三维盒子将其包围。如果封闭盒只能移动和缩放，则解决方案相当简单，只需迭代所有点并封装每个点即可。但我还需要找到盒子的最佳朝向。因此，为了说明ASCII问题，考虑一个基本的2D场景，只有两个点：

Y
| * (0,1)
|
|
|
|               * (1,0)
-------------------- X

使用常规的增长边界框，您最终会得到一个包含大多数空白空间的非常大的外接框，而在这种情况下，我需要一个非常细且绕Z轴旋转约45度的框。基本上只是连接两个点的直线。

但我不知道需要将多少个点分组在一起。并且如前所述，它必须在3D中工作。

到目前为止，我只尝试了基本方法，其中我不旋转封装框以获得最佳匹配。结果与我需要的相差甚远。

我正在考虑一种基于遗传算法的蛮力方法，其中我生成大量随机框，并简单地选择面积最小但仍然包含所有点的那个。但是，那太慢了。

GameObject go = points[0];
Bounds b = new Bounds(go.transform.position,go.transform.localScale);

for (int i=1;i<points.Count;i++)
{
    go = points[i];
    b.Encapsulate(new Bounds(go.transform.position, go.transform.localScale));
}

GameObject containingBox = Instantiate(boxPrefab);
containingBox.transform.position = b.center;
containingBox.transform.localScale = b.size;
containingBox.transform.rotation= Quaternion.Identity; //How to calculate?

- sinsro

---

这是一个有趣的问题，但它可能太广泛了，不适合在Stack Overflow上讨论。如果您能将其分解为较小的问题，我们可能能够帮助您。 - Ruzihm

这篇维基百科文章可能会对您有所帮助：最小外接矩形算法。 - Ruzihm

是的，你所要求的实际上是相当复杂的实现。搜索 Joseph O'Rourke minimal volume algorithm .. 这里提到了一些替代方案 here。 - derHugo

哦，这里有一篇相当不错的“新”短文，提供了非常棒的伪代码，你只需要抓取并将其转换为Unity c#代码，甚至可以采用他们的整个实现，然后将其转换为c#（注意版权问题）。 - derHugo

你可能也对这个帖子非常感兴趣。 - derHugo

Answer 1

嘿，我搜索了一下，找到了一个功能强大的库，基本上可以直接提供您所需的支持，并且还积极支持Unity类型：

geometry3Sharp

将其实现到Unity项目中就像这样简单:

• Download the project as .zip
• unpack the folder geometry3Sharp-master into your Assets folder

• In Unity under ProjectSettings → Player → Other Settings → Configuration → Scripting Define Symbols insert

  G3_USING_UNITY;
  

  Just as also explained in the README:

  geometry3Sharp supports transparent conversion with Unity types. To enable this, define G3_USING_UNITY in your Unity project, by adding this string to the Scripting Define Symbols box in the Player Settings.

您可以通过以下方式计算给定一组 Vector3 点的有向边框：

using UnityEngine;
using g3;

public class Example : MonoBehaviour
{
    // Just for the demo I used Transforms so I can simply move them around in the scene
    public Transform[] transforms;

    private void OnDrawGizmos()
    {
        // First wehave to convert the Unity Vector3 array
        // into the g3 type g3.Vector3d
        var points3d = new Vector3d[transforms.Length];
        for (var i = 0; i < transforms.Length; i++)
        {
            // Thanks to the g3 library implictely casted from UnityEngine.Vector3 to g3.Vector3d
            points3d[i] = transforms[i].position;
        }

        // BOOM MAGIC!!!
        var orientedBoundingBox = new ContOrientedBox3(points3d);

        // Now just convert the information back to Unity Vector3 positions and axis
        // Since g3.Vector3d uses doubles but Unity Vector3 uses floats
        // we have to explicitly cast to Vector3
        var center = (Vector3)orientedBoundingBox.Box.Center;

        var axisX = (Vector3)orientedBoundingBox.Box.AxisX;
        var axisY = (Vector3)orientedBoundingBox.Box.AxisY;
        var axisZ = (Vector3)orientedBoundingBox.Box.AxisZ;
        var extends = (Vector3)orientedBoundingBox.Box.Extent;

        // Now we can simply calculate our 8 vertices of the bounding box
        var A = center - extends.z * axisZ - extends.x * axisX - axisY * extends.y;
        var B = center - extends.z * axisZ + extends.x * axisX - axisY * extends.y;
        var C = center - extends.z * axisZ + extends.x * axisX + axisY * extends.y;
        var D = center - extends.z * axisZ - extends.x * axisX + axisY * extends.y;

        var E = center + extends.z * axisZ - extends.x * axisX - axisY * extends.y;
        var F = center + extends.z * axisZ + extends.x * axisX - axisY * extends.y;
        var G = center + extends.z * axisZ + extends.x * axisX + axisY * extends.y;
        var H = center + extends.z * axisZ - extends.x * axisX + axisY * extends.y;

        // And finally visualize it
        Gizmos.DrawLine(A, B);
        Gizmos.DrawLine(B, C);
        Gizmos.DrawLine(C, D);
        Gizmos.DrawLine(D, A);

        Gizmos.DrawLine(E, F);
        Gizmos.DrawLine(F, G);
        Gizmos.DrawLine(G, H);
        Gizmos.DrawLine(H, E);

        Gizmos.DrawLine(A, E);
        Gizmos.DrawLine(B, F);
        Gizmos.DrawLine(D, H);
        Gizmos.DrawLine(C, G);

        // And Here we ca just be amazed ;)
    }
}

---

当然，还有一些类似的东西。

orientedBoundingBox.Box.Contains(Vector3d)

用于确定给定点是否位于该框内。

---

仅因为Ruzihm问了：

当然，您可以稍微更改上面的脚本，以简单地使用实际的网格顶点：

public MeshFilter[] meshFilters;

private void OnDrawGizmos()
{
    var vertices = new List<Vector3>();
    foreach (var meshFilter in meshFilters)
    {
        // have to multiply the vertices' positions
        // with the lossyScale and add it to the transform.position 
        vertices.AddRange(meshFilter.sharedMesh.vertices.Select(vertex => meshFilter.transform.position + Vector3.Scale(vertex, meshFilter.transform.lossyScale)));
    }

    var points3d = new Vector3d[vertices.Count];

    for (var i = 0; i < vertices.Count; i++)
    {
        points3d[i] = vertices[i];
    }

    // ...
    // From here the code is the same as above

这看起来基本相同

- derHugo

---

哦，嘿，那很好。找得好。 - Ruzihm

@Ruzihm 或者你可以先获取每个球体的“orientedBoundingBox”，然后使用void orientedBoundingBox.Box.Contain(Box3d)（即orientedBoundingBox.Box的类型），该方法会重新计算适应所有这些子框的主框。虽然不完美，但我觉得这样应该足够接近了。 - derHugo

@Ruzihm 刚刚用球形模型测试了一下，只使用了所有顶点（请参见更新）。现在你提到了性能问题，我也很感兴趣，也许稍后我会测试一个更复杂的模型。但到目前为止，我印象非常深刻^^ 对于传递8个顶点的meshColliders，这可能对于复杂模型有一些非常酷的用例。 - derHugo

哦，是的，这就是要的东西。 - Ruzihm

请注意，这并不是提供最小边界框。请看第二个（球体）示例，在第二次移动后，框应该与第一次移动大致相同，只是重新定位，但实际上它会增长，结果是球体占据边界框的相对角落，类似于我自己答案中的第一种方法的结果。 - CosmicGiant

Answer 2

不要局限于现有框架然后试图去适应它，更容易的方式是在这种情况下生成框架。所以先找到点，再考虑框架。

1. 找到距离最远的两个点。

2. 这将是盒子的两个对角线的端点。
3. 计算指向/垂直于对角点的方向/法线。
4. 计算偏移方向，使其指向缺失的点。

5. 生成盒子的其余点。基本上是通过计算它们与相对点的垂线平行相交的方向。
6. 根据顶点生成盒子的面。

---

我在这里举例说明了2D，但与3D的唯一区别是第三个角度，不同的角度偏移和更多需要处理的顶点/面。

---

编辑:

正如评论中指出的那样，这可能不是一个完美的解决方案。在极端点之一或两个极端点都有多个点靠近或等距离分离时，此方法将为您提供最小边界框的合理近似值，但不会给出可能的最小边界框。

Ruzihm的插图：

然而，他的插图有些错误，因为我的解决方案不是轴对齐的。下面是选择其中一个点作为顶点时，右侧以红色或橙色显示的效果：

---

更好/正确的解决方案：

在寻找能够提供数学上完美的最小边界框的解决方案时，我发现了这个（C ++）问题和它的答案。现在我没有时间阅读所有内容并在Unity/C＃中复制解决方案，因此我只会指向它。也许我或其他贡献者以后可以编辑并复制那个解决方案。

- CosmicGiant

---

即使对“两点之间最远距离”的广泛解释，这个答案在每个2D情况下都不是很有效：https://i.imgur.com/rOXMOs4.png - Ruzihm

@Ruzihm 这取决于你是否需要一个轴对齐的框。 - Draco18s no longer trusts SE

@Draco18s OP 明确表示他希望它不是轴对齐的：我还需要找到盒子的最佳可能方向。 - derHugo

@Ruzihm 很好的发现！我没有考虑到那种情况。谢谢！ - CosmicGiant

@Ruzihm 不用在意了...你的图示中点并不等距，所以红色点是唯一的解决方案。 - CosmicGiant

Answer 3

我通过使用OpenCV for Unity解决了这个问题。我使用了minAreaRect方法，它可以计算2D点周围的适合边界框（我首先将它们投影到X/Z平面上）。

这个方法方便地返回一个矩形，包括中心点、角度和宽度/高度。从这里开始，将它扩展成3D盒子就很容易了。

- sinsro

---

您可能需要在问题中添加底部/顶部的盒子必须与x / z平面平行，否则这不能保证最小可能的盒子并且不是有效答案（请参见此示例，其中灰色为x-z投影圆）。从最小边界矩形的边缘向上投影不一定会导致3D空间中的点成为最小的3D盒子的一部分。在这种情况下，最佳盒子的x坐标超出了2D x坐标的范围。 - Ruzihm

不确定为什么我会得到那么多的踩。我明白 z/x 平面对齐的观点，但被接受的答案存在相反的问题，即一个 z/x 对齐的盒子可以旋转，使其体积不是最小的。如果你知道这些点都在一个平面上，那么拉伸的二维解决方案效果很好。 - sinsro