如何优化体素区域划分的递归函数以解决栈溢出问题

问题根源 #

递归实现的深度优先搜索（DFS）在处理大规模连续体素区域时，递归深度会超过.NET运行时的默认栈容量（通常约1MB，对应递归深度几千次），直接触发StackOverflowException。

优化方案 #

1. 将递归DFS改为迭代实现 #

用显式的栈（Stack<T>）模拟递归调用栈，彻底避免栈溢出问题，同时性能更稳定。

2. 替换Visited存储结构 #

把Dictionary<Tuple<int,int,int>, bool>换成三维布尔数组bool[,,] Visited，利用体素的索引直接访问，查找和修改的时间复杂度从哈希表的近似O(1)优化为真正的O(1)，还能避免Tuple的装箱拆箱开销。

3. 细节优化 #

• 直接遍历所有体素，无需提前创建RegionCellIndex列表，节省内存和初始化时间
• 添加边界检查，避免数组越界访问
• 减少不必要的对象重复创建

修改后的完整代码 #

主函数SeparateRegion #

public bool SeparateRegion(int ID)
{
    // 初始化三维Visited数组，直接匹配体素的索引范围
    Visited = new bool[this.nU, this.nV, this.nW];
    SeparateRegionsList = new List<List<Tuple<int, int, int>>>();
    int blobCount = 0;

    // 遍历所有体素，寻找未访问且属于目标ID的单元
    for (int i = 0; i < this.nU; i++)
    {
        for (int j = 0; j < this.nV; j++)
        {
            for (int k = 0; k < this.nW; k++)
            {
                if (!Visited[i, j, k] && this.voxelCenterNodes[i, j, k].RegionID == ID)
                {
                    var currentRegion = new List<Tuple<int, int, int>>();
                    IterativeDFS(i, j, k, ID, currentRegion);
                    SeparateRegionsList.Add(currentRegion);
                    blobCount++;
                }
            }
        }
    }

    if (blobCount == 0) return false;
    MessageBox.Show("Number of Blocks: " + blobCount);
    return true;
}

迭代版DFS函数 #

private void IterativeDFS(int i, int j, int k, int targetRegionID, List<Tuple<int, int, int>> currentRegion)
{
    // 用栈存储待访问的体素坐标
    var stack = new Stack<Tuple<int, int, int>>();
    var startTuple = Tuple.Create(i, j, k);
    stack.Push(startTuple);
    Visited[i, j, k] = true;

    while (stack.Count > 0)
    {
        var currentTuple = stack.Pop();
        int x = currentTuple.Item1;
        int y = currentTuple.Item2;
        int z = currentTuple.Item3;

        // 添加到当前区域列表
        currentRegion.Add(currentTuple);
        var node = this.voxelCenterNodes[x, y, z];

        // 遍历所有邻居
        foreach (var neighbor in node.NeighbourVertices)
        {
            int nx = neighbor.I;
            int ny = neighbor.J;
            int nz = neighbor.K;

            // 检查邻居是否在边界内、未访问、且属于目标区域
            if (nx >= 0 && nx < this.nU && ny >= 0 && ny < this.nV && nz >= 0 && nz < this.nW
                && !Visited[nx, ny, nz] && neighbor.RegionID == targetRegionID)
            {
                Visited[nx, ny, nz] = true;
                stack.Push(Tuple.Create(nx, ny, nz));
            }
        }
    }
}

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