基于半边数据结构拆分网格分离组件时遇栈溢出问题求解

我需要在单个网格中对分离的几何组件进行分组，当前采用半边数据结构（half-edge data structure）。思路是选取一条半边，遍历边找到配对的孪生半边，再遍历其关联面，若面已访问则跳过。但由于网格规模过大，当前递归实现出现栈溢出（stackoverflow），附上代码如下：

public Mesh[] SplitDisjointMeshes()
{
    var output = new List<Mesh>();
    var visited = new bool[_faces.Count];

    for(var i = 0; i < _halfedges.Count; i++)
    {
        if (visited[_halfedges[i].AdjacentFace]) continue;

        var faces = new List<int>();
        GetDisjointMeshPart(i, ref visited, faces);
        // Todo: Build new mesh from all connected faces
        
    }

    return null;
}

private void GetDisjointMeshPart(int i, ref bool[] visited, List<int> faces)
{
    int he_first, he_current;

    he_first = i;
    he_current = he_first;

    do
    {
        he_current = _halfedges[he_current].NextHalfedge;

        var tmp = _halfedges.GetPairHalfedge(he_current);

        var face = _halfedges[tmp].AdjacentFace;

        if (face == -1 || visited[face]) continue; // Not found or aready visited
        faces.Add(face);
        visited[face] = true;
        GetDisjointMeshPart(tmp, ref visited, faces);
    }
    while (he_current != he_first);
}

核心解决方案：递归改迭代（DFS/BFS） #

递归的调用栈深度受限于网格连通分量的大小，大规模网格必然触发栈溢出。改用迭代式的深度优先搜索（DFS）或广度优先搜索（BFS），用手动维护的栈/队列替代系统调用栈，就能彻底解决这个问题，同时保证O(N)时间复杂度（每个半边、面只会被访问一次）。

优化后的迭代实现代码 #

public Mesh[] SplitDisjointMeshes()
{
    var output = new List<Mesh>();
    var visited = new bool[_faces.Count];

    // 遍历所有面，避免重复处理半边
    for (int faceIdx = 0; faceIdx < _faces.Count; faceIdx++)
    {
        if (visited[faceIdx]) continue;

        var connectedFaces = new List<int>();
        // 手动维护栈，存储需要处理的半边索引
        var stack = new Stack<int>();

        // 找到当前面的任意一条半边作为起点
        int startHalfedge = _faces[faceIdx].FirstHalfedge;
        stack.Push(startHalfedge);
        visited[faceIdx] = true;
        connectedFaces.Add(faceIdx);

        while (stack.Count > 0)
        {
            int currentHe = stack.Pop();
            int heFirst = currentHe;
            int heCurrent = heFirst;

            do
            {
                // 遍历当前面的所有半边，找孪生半边对应的相邻面
                int twinHe = _halfedges[heCurrent].GetPairHalfedge();
                int adjacentFace = _halfedges[twinHe].AdjacentFace;

                if (adjacentFace != -1 && !visited[adjacentFace])
                {
                    visited[adjacentFace] = true;
                    connectedFaces.Add(adjacentFace);
                    // 将相邻面的起始半边压入栈，处理其连通区域
                    stack.Push(_faces[adjacentFace].FirstHalfedge);
                }

                heCurrent = _halfedges[heCurrent].NextHalfedge;
            } while (heCurrent != heFirst);
        }

        // 这里实现从connectedFaces构建新Mesh的逻辑
        // Mesh newMesh = BuildMeshFromFaces(connectedFaces);
        // output.Add(newMesh);
    }

    return output.ToArray();
}

关键优化点说明 #

• 替换递归为手动栈：用Stack<int>存储待处理的半边索引，完全避开系统调用栈的深度限制
• 遍历面而非半边：原代码遍历所有半边会导致大量重复检查，改为遍历面，每个连通分量只处理一次，效率更高
• O(N)复杂度保证：每个面、半边仅被访问一次，时间复杂度与网格规模线性相关
• 避免重复标记：访问面时立即标记为已访问，防止重复入栈处理

可选：BFS实现（队列替代栈） #

如果担心栈的内存占用（极端情况下栈大小可能接近网格规模），可以改用队列实现BFS，逻辑几乎一致，只是把Stack换成Queue：

// 替换栈为队列
var queue = new Queue<int>();
queue.Enqueue(startHalfedge);
// ...
while (queue.Count > 0)
{
    int currentHe = queue.Dequeue();
    // 后续逻辑与DFS完全相同
}

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