概念页

多边形三角化

Polygon Triangulation

模型数据很少恰好是渲染需要的格式。图形 API 和硬件都针对三角形优化，所以复杂多边形要先剖分 (tessellation)，最常见的是三角化 (triangulation)。本页讲三维数据的来源、三角化算法（耳切法、凸剖分、模板缓冲法）、四边形对角线选择与纹理扭曲，以及边缘裂缝和 T 型顶点。

第 16 章涵盖五类处理，目标都是视觉精度与速度（"精度"取决于场景：工程师要看到每个倒角，游戏中高帧率下单帧小错可以接受）：

flowchart LR
  A["剖分/三角化: 保证正确显示"] --> B["整合: 合并为网格, 生成法线"]
  B --> C["优化: 重排以加速渲染"]
  C --> D["简化: 去掉不重要的三角形"]
  D --> E["压缩: 减少存储与带宽"]

手工输入、过程建模、从其他数据转换（如蛋白质数据转成球和圆柱）、建模软件、摄影测量、三维扫描、从 CT/MRI 等体数据生成等值面，或这些方法的组合。

实体建模器（CAD）用严格的拓扑引擎，靠 faceter 把内部表示转成三角形显示；有时最简单的提速就是调低 faceter 的精度。注意 faceter 是否为图形渲染设计：有限元用的 faceter 追求近似等面积三角形，3D 打印用的常缺顶点法线，这类数据都适合简化。
曲面建模器（Blender、Maya）以表面定义物体；隐式曲面（metaball）建模器用移动立方体等多边形化。点云常适合简化。
关键是理解数据如何、为何而生成；不同文件格式之间转换往往有损。

三角化、凸剖分（算法只处理凸多边形时）、为存储全局光照结果做均匀网格化等。
Delaunay 三角化要求每个三角形外接圆不包含其他顶点，可最大化最小角。细长三角形应尽量避免：远距离顶点间插值易出伪影，光栅化也低效。
非平面多边形：例如侧看扭曲的四边形形成"沙漏 / 领结"。快速补救是把顶点投影到垂直于近似法线的平面上；法线用 Newell 公式求：多边形在 yz、xz、xy 三个平面上的投影面积分别作为法线的 x、y、z 分量。投影后仍可能自相交，需要更昂贵的方法。

方法	复杂度	说明
暴力分割	$O(n^3)$	检查任意两点连线是否与多边形边相交，不相交就用它分成两半递归
耳切法 (ear clipping)	$O(n^2)$	检查顶点 $i,i+1,i+2$ 构成的三角形，若线段 $(i,i+2)$ 不与任何边相交则 $i+1$ 是"耳"；逐个切掉耳并复查相邻两个顶点
更复杂的方法	$O(n\log n)$ ，典型情况近 $O(n)$	Schneider 与 Eberly 给出伪代码
凸剖分	—	比三角化更省存储与后续计算；凸多边形可直接表示为三角扇；星形凹多边形也可当扇处理

多轮廓多边形（带洞）：在环之间生成"桥接边"(keyhole / bridge edge) 合并为单一轮廓，也可逆向恢复。
写出稳健通用的三角化器很难（病态情况、精度问题）。模板缓冲法绕开三角化：把多边形当三角扇画进模板缓冲并用反转模式，被画奇数次的区域是填充区，凹处和洞被画偶数次；第二遍用模板只绘制填充区。可处理多轮廓，但每个多边形两遍、每帧清模板、不能直接用深度缓冲，适合显示用户即时绘制的复杂选区。

凹四边形只有一种分法；否则要选对角线，原则是让新边两端的差异最小：平面四边形无额外数据时选较短对角线；带逐顶点烘焙颜色时选颜色差较小的对角线。
纹理扭曲：三角形只有三个纹理坐标，只能建立仿射变换（剪切），不能表达扭曲；对扭曲四边形，两种对角线和不三角化的水平插值都不能体现设计意图（旋转后外观还会变）。解决办法：预先扭曲纹理并重设坐标；细分网格（只能缓解）；投影纹理即时扭曲（纹理间距不均）；双线性映射（需额外逐顶点数据）。这在几乎所有曲面上都会某种程度出现。
圆锥尖端：多个三角形在尖端有不同法线且不共享，产生着色不连续。

边缘裂缝：样条曲面分别沿曲线步进细分时，共享边上生成的点不一致，能透过缝看到后面，或因插值不同露出接缝。修复称为边缘缝合，确保共享边上的顶点被两个曲面共用（自适应细分见第 17 章）。
T 型顶点：两模型边相接但不共享全部顶点。精度不足会出现裂缝（现代硬件用子像素寻址缓解）；更明显的是着色伪影。修复：找到这些边并与相邻面共享顶点。简单扇形三角化可能生成零面积退化三角形，重新三角化通常更好，因为细长三角形易引发其他着色问题；Cignoni 等给出已知 T 顶点位置时避免退化三角形的 $O(n)$ 算法。

出处