在 Unity 中查找一组 3D 点的定向边界框

Question

我有一组 3D 点，或者实际上是小球体，我需要使用 Unity 3D 将它们用尽可能小的 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?

Answer 1

嘿，我搜索了一下，发现了一个非常强大的库，它或多或少直接提供了您正在寻找的内容，甚至积极支持 Unity 类型：

几何3锐利

Unity 项目的实现非常简单

• 将项目下载为.zip
• 将文件夹解压geometry3Sharp-master到您的Assets文件夹中

• 在Unity下ProjectSettings→→→→插入Player​Other SettingsConfigurationScripting Define Symbols

  G3_USING_UNITY;
  

  正如自述文件中所解释的那样：

  geometry3Sharp支持与Unity类型的透明转换。要启用此功能，请G3_USING_UNITY在 Unity 项目中进行定义，方法是将此字符串添加到“播放器设置”中的“脚本定义符号”框中。

然后，您可以简单地计算给定点数组的定向边界框的边缘，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)

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

只因为鲁兹姆问：

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

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

看起来基本一样