三角形带、扇与索引网格

让共享顶点的三角形成组送入管线，可以减少顶点着色器调用。三角形扇和带把每三角形发送的顶点数降到接近 1；现代 GPU 的标准做法是带单一索引缓冲的三角形网格，理论上每三角形只需处理约 0.5 个顶点，实际效果取决于变换后顶点缓存，由三角形顺序优化（Forsyth、Tipsify 等）决定。

三角形扇（16.4.1 节）

顶点列表 $\{v_0,\dots,v_{n-1}\}$，$v_0$ 为中心顶点，第 $i$ 个三角形为 $\triangle v_0 v_{i+1} v_{i+2}$（$0\le i<n-2$）。任何凸多边形都能直接表示为扇。长度为 $m$ 的扇平均每三角形发送顶点数 $v_a = \frac{3+(m-1)}{m} = 1+\frac{2}{m}$ $m\to\infty$ 时趋于 1；$m=5$ 时 $v_a=1.4$。

三角形带（16.4.2 节）

第 $i$ 个三角形为 $\triangle v_i v_{i+1} v_{i+2}$，$n$ 个顶点构成 $n-2$ 个三角形；朝向逐个交替，由首个三角形决定，内部按 [0,1,2]、[1,3,2]、[2,3,4]、[3,5,4]… 保持逆时针。平均顶点数与扇相同，$m=20$ 时 $v_a=1.1$。相比三角形列表最多可省约三分之二的时间（避免重复发送、变换、裁剪）。适合草叶等边缘顶点不被其他带复用的物体，几何着色器输出多个三角形时也用带。可用重复顶点或重启索引在一个缓冲中存多条带。曾有大量研究如何把网格分解成带，随着索引网格普及已经式微。

三角形网格与欧拉公式（16.4.3 节）

连通平面图的 Euler-Poincaré 公式： $v - e + f + 2g = 2$ $g$ 是亏格（洞数，球为 0、环面为 1）；面有多个环时为 $v-e+2f-l+2g=2$。封闭模型每条边两个面、每面至少三条边，$2e\ge 3f$；全三角形时 $2e=3f$，代入 $g=0$ 得 $f=2v-4$。经验法则：大型封闭三角网格的三角形数约为顶点数的两倍，每个顶点平均连接近 6 个三角形（度 / valence 约 6）。因此用带表示时每个顶点平均发送两次，而网格极限下每三角形只需 0.5 个顶点。有边界边、多个平滑组（立方体角点有三条法线 → 三条顶点记录）、纹理等数据变化时，顶点与三角形之比会升高。

顶点缓存与 ACMR

• GPU 把顶点着色器结果放入 FIFO（或近似 LRU）的变换后顶点缓存，命中则不再调用顶点着色器；三角形随机顺序时缓存几乎无用。带算法相当于优化大小为 2 的缓存。缓存很小：PS3 约 24 个顶点，新 GPU 一般最多 32 个。
• 平均缓存未命中率 (ACMR) (Hoppe)：平均每三角形需处理的顶点数，范围从 3 到 0.5；给定缓存大小与顺序可精确计算。

缓存无关的网格布局（16.4.4 节）

• Hoppe 的算法要预知缓存大小，假设偏大时收益明显下降。缓存无关 (cache-oblivious) 布局对任意大小都表现良好，也称通用索引序列。
• Forsyth / Lin & Yu 贪心算法：按顶点在缓存中的位置和尚未处理的相连三角形数打分，处理总分最高的三角形；最近用过的三个顶点分略低，避免退化成带而形成类似 Hilbert 曲线的模式；剩余三角形少的顶点分更高，避免留下孤立三角形。缓存大小 12 时，30 个模型平均 ACMR 从 1.522 降到 0.664 或更低。
• Tipsify (Sander 等)：更快（非缓存无关），还尽量把最外层三角形排在前面以减少过度绘制（如咖啡杯先画外侧）。
• Kapoulkine 在三家 GPU 上的比较：Intel 使用 128 项 FIFO、每顶点占三项或更多，AMD 与 NVIDIA 近似 16 项 LRU；Tipsify 和（稍逊的）Forsyth 跨平台表现较好。
• 结论：离线预处理实际 $O(n)$，无额外存储、不影响工具链，顶点阶段为瓶颈时能明显提升帧率，是成熟开发系统的常规环节（据称 PlayStation 网格工具链使用 Forsyth 算法）。

顶点缓冲与索引缓冲（16.4.5 节）

• 顶点缓冲：连续内存中的顶点数组，单个顶点字节数称为步长 (stride)。交错缓冲（每顶点数据放一起）在 GPU 上通常更高效，但多流也并非要避免：多流的主要代价是更多 API 调用（CPU 受限时才值得在意）；好处包括便于 SSE/AVX 处理、只有位置随时间变化时只更新该流。
• 绘制方式：点、独立线段、折线、三角形列表、三角形扇、三角形带；DX10 起可附带相邻三角形顶点供几何着色器使用。
• 索引缓冲：16 位无符号整数，网格大且支持时用 32 位。索引三角形列表最常用；索引三角形带省索引空间但生成和工具支持麻烦，实践中很少用。索引的优势：数据共享、三角形顺序任意、传输与存储通常更小。
• 文件格式（如 Wavefront OBJ）用多套索引分别引用位置、法线、纹理坐标，但 GPU 只有一个索引缓冲：立方体在 GPU 上要 24 个顶点（每个角三条法线）和 12 个三角形的索引。把网格存进纹理用顶点拉取更紧凑，但无法利用变换后缓存。
• 顶点缓冲中顶点顺序应与索引首次访问顺序一致，以减少变换前缓存未命中，这与三角形排序同样重要。
• 流输出可以先把网格当点集在顶点着色器中处理、写入新顶点缓冲，再与原索引缓冲配对继续处理和显示。

GEA 的视角：三角形列表、顶点格式与顶点缓存优化（卷 II 11.3.5.3、11.3.6）

为什么是三角形

GEA 列出三角形成为实时渲染首选图元的理由（卷 II 11.3.5.3）：最简单的多边形；永远共面（四个以上顶点不一定）；在仿射变换和透视投影下仍是三角形（最多侧视时退化成线段）；几乎所有图形硬件都围绕三角形光栅化设计，这可以追溯到《Doom》和《Ultima Underworld》的软件光栅器。三角网格是曲面的分段线性近似，把曲面拆成三角形的过程叫曲面细分 (tessellation)，拆成三角形时也叫三角化（见 多边形三角化）。

原书问题（11.3.5.3）：

• 《Doom》（1993）并不光栅化三角形：它用 BSP 树按前后顺序遍历二维地图，把墙画成逐列的竖直纹理条带、把地板天花板画成水平跨度 (visplane)，引擎本身也不支持任意三维多边形（Wikipedia "Doom engine"；Fabien Sanglard《Game Engine Black Book: DOOM》）。《Ultima Underworld》（1992）倒确实是纹理映射的多边形渲染器。把三角形光栅化硬件的源头追到 Doom 不成立。
• "透视投影下仍是三角形"只对完全位于相机前方的三角形成立。跨过相机平面（$w=0$）的三角形投影后不再是一个有界三角形，所以管线必须先在齐次裁剪空间裁剪，裁剪后的多边形可能变成四边形乃至更多边，再重新三角化（见 坐标空间 中的裁剪部分）。

列表、索引列表、带与扇

• 三角形列表：顶点按每三个一组放进顶点缓冲（DirectX）/顶点数组（OpenGL），简单但大量重复顶点，既浪费内存，也让重复顶点被变换和光照多次（卷 II 11.3.6.3）。
• 索引三角形列表：每个顶点只存一次，用轻量的索引三元组组成三角形，索引放在索引缓冲/索引数组中；65,536 个顶点以内可用 16 位索引，更大的网格通常用 32 位（卷 II 11.3.6.4）。
• 带与扇：预先规定顶点顺序，不需要索引缓冲又能减少重复。带中每个新顶点与前两个组成新三角形，前两个顶点每次交换位置以保持环绕方向一致；扇中每个新顶点与前一个顶点和第一个顶点组成三角形（卷 II 11.3.6.5）。
• 补充：GEA 指出如今的 GPU 已不能再渲染三角形扇，因为其收益不足以抵消所需硬件的成本。本页 RTR4 部分仍把扇作为一种可用的图元介绍，阅读时注意这一时代差异。

  原书问题（11.3.6.5）："如今的 GPU 不能再渲染扇"说得过头。Direct3D 10 起确实去掉了三角形扇拓扑（MS Learn "Primitive Topologies"），Metal 也没有；但 Vulkan 核心规范仍有 VK_PRIMITIVE_TOPOLOGY_TRIANGLE_FAN（仅 portability 子集可不支持），OpenGL 有 GL_TRIANGLE_FAN，桌面 GPU 驱动照常支持（Vulkan 规范 "Triangle Fans"）。更准确的说法是：主流 API 和引擎已不再依赖扇，部分 API 已移除。

顶点格式与属性交错

• 一个顶点的属性集合可写成 C 结构体，其布局叫顶点格式，例如只有位置的 Vertex1P（用于阴影体挤出、卡通描边、z 预通道等），位置-法线-UV 的 Vertex1P1N1UV，以及带漫反射色、镜面色、两套 UV、4 个关节索引和 3 个权重（第 4 个权重由前三个算出）的蒙皮顶点（卷 II 11.3.6.6）。
• 属性组合的排列数会爆炸，管理大量顶点格式曾是图形程序员的头疼事。如今 GPU 能把多个同构属性数组动态交错：位置、法线、UV 分别放在三个顶点缓冲（或一个大缓冲的三段）里，由 API 拼成着色器看到的结构体——D3D11 用 ID3D11Device::CreateInputLayout 加 D3D11_INPUT_ELEMENT_DESC，OpenGL 用 glVertexAttribPointer。

顶点缓存优化

• 顶点着色器的结果会被缓存，后续三角形引用缓存中的顶点就不必重算。三角形带一方面省索引缓冲，一方面访存更连贯；带索引的三角形带还能几乎消除顶点重复，同时保留带的缓存友好顺序（卷 II 11.3.6.7）。
• 不拘泥于带的顺序也能优化：顶点缓存优化器是离线几何处理工具，考虑特定 GPU 的顶点缓存大小和替换策略来重排三角形。GEA 举例：索尼 PlayStation 的 Edge 几何处理库中的优化器比三角形带的吞吐高至多 4%；其他平台可用 NVIDIA Nsight 和微软 DirectXMesh。
• 这与本页「顶点缓存与 ACMR」一致。GEA 还指出，传统管线即使用了优化器也有根本上限，这是网格着色器出现的原因之一，见 网格着色器管线。

PBRT 的视角：为什么用索引网格，以及离线渲染器怎样存三角形（PBRT 4e 6.5.1–6.5.2）

用欧拉-庞加莱公式估算存储

封闭网格满足 $V-E+F=2(1-g)$（$g$ 为亏格，即"把手"数）。三角网格每个面有 3 条半边、每条边由 2 条半边组成，所以 $E=\frac32F$。亏格的影响对大网格可以忽略，取 $g=0$ 代入得 $F\approx2V$：面数约为顶点数的两倍，每个顶点平均被 6 个三角形引用。于是共享顶点时每个三角形约需 12 字节索引（3 个 32 位整数）加半个顶点的位置（6 字节），共 18 字节；直接存三个位置要 36 字节。每顶点法线和纹理坐标越多，节省比例越大。

pbrt 的做法

• TriangleMesh 存位置、索引、可选的法线 n、切线 s、uv；加载时就把顶点变换到渲染空间，省去每条射线变到物体空间、再把交点变回来的开销（二次曲面则相反，在物体空间求交）。
• BufferCache 对内容相同的数组只存一份（即使场景没有用实例化）；书中的风景场景因此节省 400 MB 以上。缓存分成 64 个分片、各有读写锁，读时 lock_shared()，写时升级为独占锁并处理"另一线程先插入"的情况。位置变换到渲染空间后命中率低，索引和 uv 命中率高。
• 每个 Triangle 只存两个 int（网格编号、三角形编号），共 8 字节；若用虚函数，虚表指针就会让它翻倍，这也是 pbrt 用标签指针而不用虚函数的原因之一（见 C++ 内存布局与对齐）。
• 网格是否翻转法线（ReverseOrientation、变换是否改变手性）对整个网格相同，只存一次。
• InteractionFromIntersection() 是独立函数（参数为网格指针和三角形索引）而不是成员函数，这样 GPU 路径在硬件求交返回三角形索引和重心坐标后可以复用同一份 CPU 代码。
• 着色法线和切线按重心插值，切线经两次叉积正交化：保持 $\mathbf n$ 不变，修正 $\mathbf s$。

原书问题

• 6.5 节引言写"三角网格上，边数与顶点数还满足 $E=\frac32F$"，该等式联系的是边数与面数。见 pbr-book-website issue #23：https://github.com/mmp/pbr-book-website/issues/23