Unity执行GenerateFloodFillData时Mesh顶点数过高致无响应问题

没错，这完全是时间复杂度和低效操作导致的性能灾难，你的代码里存在几个致命的性能瓶颈，直接导致顶点数上升后耗时呈爆炸式增长，最终让Unity编辑器主线程卡住无响应。

核心性能问题拆解 #

我们来逐个拆解代码里的低效点：

1. 反复调用Array.IndexOf(verts, cNode)
   每次从队列取出一个Vector3节点后，你要调用4次Array.IndexOf来找到它在顶点数组中的索引——这个方法是线性查找，每次耗时O(N)（N是顶点总数）。当N是59k时，每次查找就要遍历59k个元素，而每个顶点都会被处理一次，这部分的总耗时直接来到O(N²)，光是这一步就会产生3.4e9次操作，完全超出了主线程的处理能力。

2. 用List<Vector3>.Contains()判断是否已访问
   List.Contains()同样是线性查找，每次要遍历整个已访问列表来判断顶点是否存在，随着访问的顶点数增加，这个操作的耗时也会越来越长，进一步加剧了O(N²)的时间复杂度。

3. 用Vector3作为队列/列表元素
   Vector3是值类型，每次比较都要检查x/y/z三个分量，而且Array.IndexOf和List.Contains都会依赖这些分量的比对，比直接用整数索引慢得多。

优化方案：重构算法，把时间复杂度降到O(N) #

我们可以通过几个关键修改把算法的时间复杂度降到线性，彻底解决性能问题：

1. 用索引代替Vector3存储访问状态

• 把Queue<Vector3>改成Queue<int>，存储顶点的索引而不是Vector3本身
• 用一个bool[] visited数组来记录某个顶点是否已经被访问过，这样判断是否已访问的操作变成O(1)的直接数组查询

2. 避免Array.IndexOf，直接用索引计算邻居

既然我们存储的是索引，就可以直接通过索引加减来计算左右、上下邻居，完全不需要查找操作。

重构后的核心代码示例

private static Queue<int> q = new Queue<int>();
private static bool[] visited;
private static int traversalCount;

private static void CheckIfQueueNeighbor(int index, float limit, Vector3[] allVertices, Vector3 currentNodePos) {
    if (!visited[index] && allVertices[index].y - currentNodePos.y <= limit) {
        visited[index] = true;
        traversalCount++;
        q.Enqueue(index);
    }
}

public static float GenerateFloodFillData(float heightThresholdValue, MeshFilter meshFilter) {
    Vector3[] verts = meshFilter.sharedMesh.vertices;
    int totalVerts = verts.Length;
    int width = (int)meshFilter.sharedMesh.bounds.size.x;

    // 初始化状态（复用对象减少GC）
    q.Clear();
    visited = new bool[totalVerts];
    traversalCount = 0;

    // 从第一个顶点开始
    q.Enqueue(0);
    visited[0] = true;
    traversalCount++;

    while (q.Count > 0) {
        int currentIndex = q.Dequeue();
        Vector3 currentNodePos = verts[currentIndex];

        // 检查左邻居
        if (currentIndex - 1 >= 0) {
            CheckIfQueueNeighbor(currentIndex - 1, heightThresholdValue, verts, currentNodePos);
        }
        // 检查右邻居
        if (currentIndex + 1 < totalVerts) {
            CheckIfQueueNeighbor(currentIndex + 1, heightThresholdValue, verts, currentNodePos);
        }
        // 检查上邻居（假设width是横向顶点数）
        if (currentIndex - width >= 0) {
            CheckIfQueueNeighbor(currentIndex - width, heightThresholdValue, verts, currentNodePos);
        }
        // 检查下邻居
        if (currentIndex + width < totalVerts) {
            CheckIfQueueNeighbor(currentIndex + width, heightThresholdValue, verts, currentNodePos);
        }
    }

    return (float)traversalCount / totalVerts;
}

额外优化建议 #

1. 避免在循环中频繁创建对象：原来的代码每次调用GenerateFloodFillData都会重新创建Queue和List，改成复用对象（比如Clear()代替重新实例化），减少GC压力。
2. 分帧处理或后台计算：如果顶点数特别大（比如百万级），可以把 flood fill 的过程拆分成多帧执行（用Coroutine），或者用Unity的Job System在后台线程计算，避免主线程卡住。
3. 验证邻居逻辑：注意你的width计算是基于mesh.bounds.size.x，这可能和实际的顶点排列顺序不匹配——如果网格的顶点不是严格按行排列的，这个邻居计算逻辑会出错，建议用网格的triangles数组来构建正确的邻接表，或者确认顶点的排列顺序和width的关系。

经过这些优化后，即使是59k顶点的场景，GenerateFloodFillData的执行时间也会从几十分钟降到几毫秒，完全不会导致编辑器无响应。

内容的提问来源于stack exchange，提问作者Nero