为什么先学单纯形网格

三角形和四面体具有最简单的仿射坐标，任意多边形/多面体也较容易被它们细分。自动三角网格与四面体网格已经相对成熟，但“相对成熟”不等于所有 CAD、各向异性和高阶情形都解决。

Delaunay 的局部判据

平面点集的三角剖分是 Delaunay，当且仅当每个三角形外接圆内部不含其他输入点。对相邻三角形 $abc$ 与 $abd$ ，边 $ab$ 可翻转的局部判据是

\angle acb+\angle adb>\pi.

等价地，用带方向的 incircle 行列式判断 $d$ 是否进入 $abc$ 的外接圆。数值实现不能直接用普通浮点“差不多为零”；接近共圆时必须使用自适应精确谓词或受控符号扰动。

给定当前 Delaunay 剖分，插入新点 $p$ ：

算法骨架很短，真正困难在鲁棒谓词、退化处理、快速点定位与边界约束。

工程输入通常是 PSLG/PLC：点、线段、曲面片定义了必须保留的边界。普通 Delaunay 会跨过约束边。常见处理是：

三维中并非任意 PLC 都可直接得到不加 Steiner 点的约束 Delaunay 四面体剖分，这也是二维直觉不能直接照搬的地方。

二维 Delaunay refinement 循环处理两类坏对象：

while 存在侵占的约束线段或坏三角形:
    if 某约束线段被侵占:
        插入线段中点
    else:
        取一个坏三角形的外心
        若外心侵占约束线段: 先分裂该线段
        否则: 插入外心
    恢复 Delaunay

“侵占”意味着候选点落入以约束线段为直径的圆。优先处理它避免后续插点破坏边界。终止和最小角保证依赖输入小角、尺寸函数与阈值；不能把论文中的保证无条件外推到任意脏 CAD。

前沿推进维护当前未封闭边界 $F$ ，不断从一条前沿边生成新单元。它天然尊重边界和局部尺寸，容易产生边界质量高的单元；难点是前沿相撞时的空腔闭合、拓扑检查和全局鲁棒性。

Delaunay 与 AFT 常被混合：前沿控制新点位置，Delaunay 决定连接关系；大连理工 MeshGene 公开资料也明确列出 AFT–Delaunay 路线。

树方法递归细分与几何相交的方格/立方格：

\text{cell}\longrightarrow 2^d\text{ children}.

优点是层次结构、并行性和覆盖鲁棒；代价是阶梯边界、悬挂节点、尺度过渡模板和复杂奇异结构。工程上通常还要 snapping、模板替换、pillowing 与平滑。

给定密度 $\rho(x)$ 与生成点 $z_i$ ，Voronoi 区为 $V_i$ 。CVT 能量

E(z)=\sum_i\int_{V_i}\rho(x)\|x-z_i\|^2\,dx.

固定分区时，对 $z_i$ 求导得

\frac{\partial E}{\partial z_i} =2\int_{V_i}\rho(x)(z_i-x)\,dx,

令其为零， $z_i$ 等于 $V_i$ 的质量质心。Lloyd 迭代就是反复“建 Voronoi → 移到质心”。它通常下降能量，但只保证到局部驻点；边界、特征和各向异性需要额外约束。

答案：Delaunay只约束点集连接，不知道必须保留的线段；避免候选点破坏输入边界并维持终止分析；空球性质不禁止四点近乎共面。

算法的历史来源、理论保证、三维 sliver 问题和工程实现入口，见单纯形生成、鲁棒性与质量文献谱系。