Unreal Engine中Voronoi 3D图计算产生退化面的原因排查

问题背景 #

我在Unreal Engine项目中从零实现不依赖Chaos物理引擎的自定义简易破碎机制，采用基于Voronoi的网格破碎方案，使用引擎内置的voro++库。测试时发现Voronoi计算生成的单元存在退化面，导致编辑器预览的网格出现孔洞。

复现代码 #

void AGeneratedDestructibleActor::ApplyVoronoi()
{
    // Sites
    TArray<FVector> Sites;
    Sites.Add({50.f, 50.f, 25.f});
    
    // Bounding box for Voronoi
    FVector InMin {0.f, 0.f, 0.f};
    FVector InMax {100.f, 100.f, 100.f};

    FBox Bounds {InMin,InMax};
    
    TArray<FVoronoiCellInfo> AllCells{};
    
    // Calculate Voronoi Diagram
    Diagram.Initialize(Sites, Bounds, 0.0, 0.0);
    Diagram.ComputeAllCells(AllCells);

    int CurrentCellIdx{0};
    int NumVerticesPrevCells{0};
    FDynamicMesh3 NewMesh{};

    for (auto CellInfo : AllCells)
    {
        UE_LOG(LogTemp, Warning, TEXT("Cella-%d"), CurrentCellIdx);

        int CurrentVertexIdx = 0;
        
        for (auto CellVertex : CellInfo.Vertices)
        {
            UE_LOG(LogTemp, Warning, TEXT("\tVertex %d: (%.2f, %.2f, %.2f)"), CurrentVertexIdx, CellVertex.X, CellVertex.Y, CellVertex.Z);

            // TODO: some vertices can be duplicated
            NewMesh.AppendVertex({CellVertex.X, CellVertex.Y, CellVertex.Z});
            CurrentVertexIdx++;
        }
        
        
        int faceIdx = 0;
        
        UE_LOG(LogTemp, Warning, TEXT("\tNum Face indices %d"), CellInfo.Faces.Num());

        for (int firstVertexIdx = 0; firstVertexIdx <= CellInfo.Faces.Num()-3; firstVertexIdx += 3)
        {
            // vertex indices of the current face
            int vIdx0{CellInfo.Faces[firstVertexIdx]};
            int vIdx1{CellInfo.Faces[firstVertexIdx+1]};
            int vIdx2{CellInfo.Faces[firstVertexIdx+2]};
            // each cell has vertex indices zero-based, but the same vertex in newMesh is shifted by the number of vertices in the previous cells
            int vIdx0_seq{vIdx0 + NumVerticesPrevCells};
            int vIdx1_seq{vIdx1 + NumVerticesPrevCells};
            int vIdx2_seq{vIdx2 + NumVerticesPrevCells};
            
            UE_LOG(LogTemp, Warning, TEXT("\tFace %d/%d: [%d, %d, %d]"), faceIdx, (CellInfo.Faces.Num()/3)-1, vIdx0_seq, vIdx1_seq, vIdx2_seq);

            NewMesh.AppendTriangle(vIdx0_seq, vIdx1_seq, vIdx2_seq);
            faceIdx++;
        }
        CurrentCellIdx++;
        NumVerticesPrevCells += CurrentVertexIdx;
    }

    this->DynamicMeshComponent->GetMesh()->Clear();
    this->DynamicMeshComponent->SetMesh(FDynamicMesh3{NewMesh});
}

问题现象 #

• 仅设置1个站点时，预期生成立方体，但实际网格存在孔洞，调试发现存在退化三角形（如Face 6/9、Face 8/9包含重复顶点）。
• 添加多个站点后，每个Voronoi单元的第7、9个面均为退化面。

原因分析 #

1. Voronoi计算的边界特性 #

voro++在处理靠近边界的站点时，会生成与边界平面重合的退化面。当站点位置紧贴边界（比如示例中Z轴仅25，远低于边界上限100），部分Voronoi面会被压缩到边界平面上，导致三个顶点共线或共面，形成无面积的退化三角形。

2. 代码实现的疏漏 #

• 未过滤退化面：FDynamicMesh3不会自动忽略这类无效面，直接导入会导致渲染孔洞和拓扑错误。
• 顶点重复未处理：不同单元格共享的顶点被重复添加，虽不是当前问题核心，但会浪费内存并可能加剧拓扑混乱。
• 面索引遍历逻辑有风险：firstVertexIdx <= CellInfo.Faces.Num()-3的判断，当Faces.Num()不是3的倍数时会导致越界。

代码改进建议 #

1. 过滤退化三角形 #

在添加三角形前，通过面积阈值判断是否为退化面，跳过无效面：

// 在AppendTriangle前添加判断
FVector V0 = NewMesh.GetVertex(vIdx0_seq);
FVector V1 = NewMesh.GetVertex(vIdx1_seq);
FVector V2 = NewMesh.GetVertex(vIdx2_seq);

// 计算三角形面积，小于阈值则判定为退化
float Area = FVector::CrossProduct(V1 - V0, V2 - V0).Size();
const float DegenerateThreshold = 1e-4f; // 可根据精度需求调整
if (Area > DegenerateThreshold)
{
    NewMesh.AppendTriangle(vIdx0_seq, vIdx1_seq, vIdx2_seq);
}
else
{
    UE_LOG(LogTemp, Warning, TEXT("\tSkipping degenerate face %d"), faceIdx);
}

2. 优化Voronoi计算参数 #

调整站点位置避免紧贴边界，或给边界添加微小扩展，让Voronoi单元更规整：

// 给边界添加1单位扩展，避免单元紧贴边界
Diagram.Initialize(Sites, Bounds, 1.0f, 1.0f);

3. 合并重复顶点 #

使用FDynamicMesh3的顶点合并功能，减少冗余顶点并修复拓扑：

// 在所有顶点添加完成后执行合并
FDynamicMesh3Simplifier Simplifier(&NewMesh);
Simplifier.SetMergeThreshold(1e-3f); // 顶点距离小于此值则合并
Simplifier.MergeCoincidentVertices();

4. 修正面索引遍历逻辑 #

避免索引越界风险，调整遍历条件：

for (int firstVertexIdx = 0; firstVertexIdx < CellInfo.Faces.Num(); firstVertexIdx += 3)
{
    if (firstVertexIdx + 2 >= CellInfo.Faces.Num()) break; // 确保有三个有效索引
    // ... 后续面处理代码
}

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