C#三维三角网生成实战：从Delaunay算法到性能优化

1次阅读

共计 1818 个字符，预计需要花费 5 分钟才能阅读完成。

在 GIS 地形建模中，三维三角网将离散高程点转化为连续曲面；游戏开发中则用于生成动态地形碰撞体。传统暴力算法（如 O(n⁴)的枚举法）处理 1000 个点就需要数分钟，而实际项目常需处理百万级点云数据。

Delaunay 三角剖分：保证最小角最大化，避免狭长三角形
贪心算法：实现简单但无法保证拓扑正确性
Bowyer-Watson 算法 ：O(n log n) 预期时间，支持增量插入

选择 Bowyer-Watson 的核心优势：

动态维护外接圆空腔性质
天然支持流式数据输入
便于后续扩展为并行算法

public struct Point3D {
    public double X, Y, Z;

    // 重写 Equals 用于 KD-Tree 比较
    public override bool Equals(object obj) 
        => obj is Point3D p && Math.Abs(X-p.X)<1e-10 
                          && Math.Abs(Y-p.Y)<1e-10
                          && Math.Abs(Z-p.Z)<1e-10;
}

class Tetrahedron {public Point3D[] Vertices = new Point3D[4];
    public Sphere Circumsphere {get;} // 外接球计算

    public bool Contains(Point3D p) {
        // 用行列式判断点在外接球内外
        double[,] matrix = ...;
        return Matrix4x4.Determinant(matrix) > 0;
    }
}

构建包含所有点的初始超四面体
对每个新点 P：
查找所有外接球包含 P 的四面体（形成星形空腔）
删除这些四面体
用空腔边界与 P 组成新四面体
移除与初始超四面体相关的所有单元

关键优化点：

使用跳跃指针加速点定位
预计算外接球参数
增量更新邻接关系

[
T(n) = O(n \log n) \text{(平均情况)} + O(n^2) \text{(最坏情况)}
]

public class KDNode {
    public Point3D Point;
    public KDNode Left, Right;
    public int Axis;

    public KDNode Build(Point3D[] points, int depth=0) {
        int axis = depth % 3;
        Array.Sort(points, (a,b) => 
            axis==0 ? a.X.CompareTo(b.X) : 
            axis==1 ? a.Y.CompareTo(b.Y) : 
            a.Z.CompareTo(b.Z));

        int mid = points.Length/2;
        return new KDNode {Point = points[mid],
            Left = Build(points.Take(mid).ToArray(), depth+1),
            Right = Build(points.Skip(mid+1).ToArray(), depth+1),
            Axis = axis
        };
    }
}

数据规模	原始算法(ms)	KD-Tree 优化(ms)
1,000	120	25
10,000	15,000	320

数值稳定性 ：使用Math.Abs(det)<1e-10 替代det==0
内存优化：
对象池复用 Tetrahedron 实例
避免 LINQ 产生临时集合
线程安全：
分离拓扑修改与几何计算
读写锁保护共享 KD-Tree

[BurstCompile]
struct DelaunayJob : IJobParallelFor {[ReadOnly] public NativeArray<Point3D> Points;
    public NativeList<Tetrahedron> Result;

    public void Execute(int index) {// 分块处理点集}
}