Unityでメッシュのエッジコラスプ法を実装する　その①　メッシュの辺の取得

本日はUnity枠です。

〇エッジコラスプ法とは？

エッジコラスプ法は①簡略化するエッジの選択、②エッジの縮退および頂点の統合、③ジオメトリを評価し縮退させるエッジを選択

という順で頂点を減らしデシメートを行うアルゴリズムです。

redhologerbera.hatenablog.com

〇Unityでメッシュを構成する辺の中で最も短い辺を検出する

エッジコラスプ法をUnityで実装するためにはまずメッシュの辺へアクセスし、最も短い辺を抽出する必要があります。

まずはメッシュのエッジを取得します。

これは頂点とポリゴンの情報をもとにポリゴンごとに辺の長さを求めています。

   // メッシュを取得
        Mesh mesh = GetComponent<MeshFilter>().mesh;

        // メッシュの全頂点を取得
        Vector3[] vertices = mesh.vertices;

        // メッシュの三角形インデックスを取得
        int[] triangles = mesh.triangles;

        // 辺情報を保存するリスト (Dictionaryで重複を避ける)
        Dictionary<Edge, float> edges = new Dictionary<Edge, float>();

        // 三角形を一つずつ処理
        for (int i = 0; i < triangles.Length; i += 3)
        {
            // 各三角形の頂点インデックスを取得
            int v0 = triangles[i];
            int v1 = triangles[i + 1];
            int v2 = triangles[i + 2];

            // 辺を計算 (重複を避けるため、常に小さいインデックスが前に来るようにする)
            AddEdge(v0, v1, vertices, edges);
            AddEdge(v1, v2, vertices, edges);
            AddEdge(v2, v0, vertices, edges);
        }

エッジを作成するコードは以下のようになります。

ここでは頂点座標をもとにDistanceを使用して計算しています。

 private void AddEdge(int v1, int v2, Vector3[] vertices, Dictionary<Edge, float> edges)
    {
        // 常に小さい頂点インデックスを前にしてエッジを作成
        Edge edge = new Edge(Mathf.Min(v1, v2), Mathf.Max(v1, v2));

        // 辺の長さを計算
        float length = Vector3.Distance(vertices[v1], vertices[v2]);

        // 辺がすでにリストにあるか確認し、なければ追加
        if (!edges.ContainsKey(edge))
        {
            edges.Add(edge, length);
        }
    }

またUnityのMeshクラスではEdge自体をサポートしていないため、Edgeを定義しています。

public class Edge
{
    public int VertexIndex1;
    public int VertexIndex2;

    public Edge(int v1, int v2)
    {
        VertexIndex1 = v1;
        VertexIndex2 = v2;
    }

    // Dictionaryのキーとして使用できるようにEqualsとGetHashCodeをオーバーライド
    public override bool Equals(object obj)
    {
        Edge other = obj as Edge;
        return other != null && VertexIndex1 == other.VertexIndex1 && VertexIndex2 == other.VertexIndex2;
    }

    public override int GetHashCode()
    {
        return VertexIndex1 * 31 + VertexIndex2;
    }
}

ここでGetHashCodeでは31という一見マジックナンバーが出てきますが31は素数（Prime Number）であり、ハッシュ計算において重要です。

素数を使うことで、ハッシュ値の分布がより均等になり、ハッシュ衝突が減る可能性があります

最後に最も短い辺を出力します。

 // 最も短い辺を探す
        Edge shortestEdge = null;
        float shortestLength = float.MaxValue;

        foreach (KeyValuePair<Edge, float> edge in edges)
        {
            if (edge.Value < shortestLength)
            {
                shortestLength = edge.Value;
                shortestEdge = edge.Key;
            }
        }

        // 結果を出力
        if (shortestEdge != null)
        {
            Debug.Log($"最も短い辺の頂点ID: {shortestEdge.VertexIndex1}, {shortestEdge.VertexIndex2}");
            Debug.Log($"最も短い辺の長さ: {shortestLength}");
        }

ここではエッジの長さを比較して最も短いエッジのValueとKeyを出力しています。