剔除技术

基本概念（19.2 节）

• 剔除理论上可发生在管线任何阶段，越早越好；"最快渲染的三角形是从未发送给 GPU 的那个"。剔除也可用于碰撞检测、物理、AI 等非渲染部分。
• 理想的剔除只把精确可见集 (EVS)——所有部分或完全可见的图元——送入管线。能给出 EVS 的方面图 (aspect graph) 最坏复杂度可达 $O(n^9)$，不实用。实际算法计算潜在可见集 (PVS)：若 PVS 完全包含 EVS（只丢弃不可见几何）则是保守的，总能得到正确图像，因此更常用；近似 PVS 可能漏掉可见物体导致错误图像。PVS 找到后仍由 z-buffer 解决逐像素可见性。
• 粒度可以是三角形、整个物体或物体组。

背面剔除（19.3 节）

对实心不透明物体（且相机在物体外、没有近裁剪穿入），背向观察者的三角形看不见。三种等价判定：

1. 屏幕空间：计算投影后三角形的有符号面积，按约定方向（如顺时针）为负即剔除，在屏幕映射后立即进行。
2. 视空间：从三角形所在平面上一点（取一个顶点）指向视点的向量与三角形法线点积为负即背向（正交投影用负视线方向代替）；等价于视点到三角形平面的有符号距离的符号，法线无需归一化。
3. 裁剪空间：取 $v=(v_x,v_y,v_w)$，计算行列式 $d=|v_0,v_1,v_2|$，$d\le 0$ 则剔除。

Blinn 指出前两者几何上相同，只是计算空间不同；实践中屏幕空间测试更安全，因为视空间里略微背向的侧视三角形在取整到亚像素坐标后可能变成略微朝前。

注意事项：

• 镜像变换（负缩放）会把背面变正面，反之亦然。像素着色器可用 gl_FrontFacing / SV_IsFrontFace 判断正反面；以前要显示双面物体只能渲染两遍。
• 常见误解是背面剔除能减半三角形。室内的墙、地板、天花板大多朝向观察者，地形也大多可见，只有山背面受益。
• 运动模糊时顶点线性运动的三角形可能在一帧内背向→朝前→背向，只按帧首尾判定会出错；可改写为 Bernstein 形式，用贝塞尔曲线凸包性质做保守测试。景深情况下，若整个镜头都在三角形平面的负半空间（背后），可安全剔除。

成簇背面剔除与法线锥

一次测试剔除一整组三角形。法线锥由法线 $\mathbf{n}$、半角 $\alpha$、锚点 $\mathbf{c}$ 定义（截断锥还需沿法线的两个偏移距离）。Shirman 与 Abi-Ezzi 证明：视点位于"正面锥"中则锥内所有面都朝前，位于"背面锥"中则全部背向。

对不截断的锥，若所有几何都位于 $\mathbf{c}$，视点 $\mathbf{e}$ 看到整锥背向的条件为：

若几何位于以 $\mathbf{c}$ 为中心、半径 $r$ 的球内，则为

（式 19.2、19.3 在提取文本中排版错乱，按可完全确定的结构重建。）锥的计算：把所有三角形法线平移到同一点，求单位球面上包含它们的最小圆。量化后法线锥可存进 $8\times 4$ 位。

静态网格立方体掩码（Haar 与 Aaltonen，《刺客信条：大革命》）：给 $n$ 个三角形算一个最小立方体，每个面分成 $r\times r$ 个"像素"，每个像素存 $n$ 位掩码表示从该像素对应锥台内看哪些三角形可见。相机在立方体外时直接查掩码即可保守剔除背面；在内部时全部视为可见。他们每面只用一个掩码、一次编码 64 个三角形，并用置位计数为未剔除三角形高效分配内存。

视锥剔除（19.4 节）

把物体的 BV 与视锥比较：完全在外则跳过，在内或相交则送入管线。配合 空间数据结构 可层次化：对 BVH 前序遍历，BV 在外则剪掉整棵子树；完全在内则其子树不再需要任何视锥测试；相交则继续测试子节点，叶节点相交时其几何被送入管线（但不保证都在视锥内）。

优化手段：

• 多级 BV：球与视锥相交时，若已知 OBB 小得多，可再做更精确的 OBB 测试。
• 平面掩码 (plane masking)：记录 BV 完全位于哪些视锥平面内侧（位掩码），子节点只需测仍相交的平面；根测 6 个平面，越往下越少。
• 时间相干：把上一帧拒绝该 BV 的平面存起来，下一帧先测它。
• CPU 上做逐物体剔除、GPU 上还有更细粒度剔除时，CPU 只需测左右上下四个平面；还可用 apex point map 得到更紧的包围体。
• 远处常用雾掩盖物体在远平面突然消失。

有些游戏引擎不用层次 BVH，而是每个物体一个 BV 组成线性列表，因为更容易用 SIMD 和多线程实现；但 CAD 这类大部分几何都在视锥内的应用应避免，层次剔除可在节点完全在内时立即绘制。

入口剔除（19.5 节）

针对建筑模型：墙是室内的大遮挡物，所以入口剔除是一种遮挡剔除，也是视锥剔除的扩展。场景预处理为单元 (cell)（房间、走廊）和连接它们的入口 (portal)（门、窗），存成邻接图。自动化划分对现代复杂场景极难，目前多为手工定义。

Luebke 与 Georges 的方法：

flowchart TD
  A["渲染视点所在单元"] --> B["遍历该单元的入口"]
  B --> C{"入口在当前视锥内?"}
  C -- "否" --> D["忽略该入口及其后单元"]
  C -- "是" --> E["把视锥缩小到紧贴入口"]
  E --> F["用缩小后的视锥剔除并渲染相邻单元"]
  F --> B

如上图递归进行，例如透过门看到房间的三扇窗，只有门与某扇窗都能看到的部分才渲染。要点：

• 用帧号给已渲染物体打标记，避免透过两个窗口被渲染两次（低效，透明物体还会出错），也免去每帧清空标记。
• 实际入口用 AABB 高估，可用模板缓冲遮掉真实入口外的部分，或设置剪裁矩形；这样透明物体即使渲染两次也只影响各入口的可见像素一次，可省去打标记。
• 把视锥在镜面处反射，可用于平面反射的内容裁剪；其他变换可做简单折射。

细节剔除与小三角形剔除（19.6 节）

• 细节剔除（屏幕尺寸剔除）：把 BV 投影到屏幕估算像素面积，低于阈值就不处理。依据是视点运动时小细节几乎没有贡献，视点静止时通常关闭。可在场景图上层次化进行，游戏引擎常用。
• 小三角形剔除：每像素中心一个采样时，小三角形很可能落在采样点之间，而且光栅化效率低。在 GPU 剔除代码中可计算三角形二维 AABB，若

为真则剔除（像素中心在 $(x+0.5, y+0.5)$，x 或 y 方向取整到同一坐标即说明不覆盖任何采样点）。这是保守的：有些不覆盖采样的三角形也剔除不掉。

取舍

GEA 的视角：应用层的剔除（卷 II 11.5.1）

GEA 把剔除放在应用层的第一项职责里："最便宜的三角形是你永远不画的那个"；构建可见网格实例列表的过程叫可见性判定（卷 II 11.5.1，应用层见 图形栈与渲染引擎架构）。

背面剔除

• 用环绕顺序判断朝向：沿约定的环绕顺序走过顶点时，法线 $\mathbf{n}$ 按右手方向指向三角形"正面"。取三角形法线与观察向量 $\mathbf{v}$ 的点积，$\mathbf{n}\cdot\mathbf{v}\ge 0$ 即视为背向（卷 II 11.5.1.1）。这里 $\mathbf{v}$ 是相机的观察方向；本页 RTR4 的视空间判定用的是从三角形指向视点的向量，方向相反，所以符号也相反，两者等价。
• 双面三角形就是不做背面剔除的三角形，D3D11 中把剔除模式设为 D3D11_CULL_NONE。
• 原书问题（D3D11 剔除模式说反了）：GEA 写道 D3D11 默认把顺时针当正面（这一点正确，D3D11_RASTERIZER_DESC::FrontCounterClockwise 默认 FALSE），但又说设为 D3D11_CULL_FRONT 时"背向三角形不会被画"、设为 D3D11_CULL_BACK 时"正向三角形不会被画"，正好说反。微软文档（MS Learn「D3D11_CULL_MODE enumeration」）明确：D3D11_CULL_FRONT = 不画正向三角形，D3D11_CULL_BACK = 不画背向三角形（默认光栅化状态就是 D3D11_CULL_BACK）。要做常规背面剔除应设 D3D11_CULL_BACK。
• 环绕顺序和法线方向要在全部几何中保持一致（例如封闭物体法线一律朝外），背面剔除才能工作（卷 II 11.3.6.1）。

视锥剔除：球体测试

• 用物体包围体与视锥六个平面做简单测试，完全在外的从渲染列表中剔除。包围体通常用球，因为特别好剔除（也用 AABB 等）。
• 思路：把每个平面向外推出球半径的距离，看球心在每个平面的哪一侧。实际不用移动平面：把球心代入平面方程 $h=ax+by+cz+d=\mathbf{n}\cdot\mathbf{P}-\mathbf{n}\cdot\mathbf{P}_0$ 得到到平面的有符号距离 $h_i$，与半径比较即可（若平面法线朝视锥内侧，任一平面上 $h_i<-r$ 即球完全在外可剔除，六个平面都满足 $h_i\ge -r$ 才保留；这一判断是保守的，靠近视锥角落的球可能被误留）（卷 II 11.5.1.2，平面方程见 几何图元的表示）。场景图可以先排除离视锥很远的物体，见 空间数据结构。

入口与反入口

• 入口 (portal)：把世界分成由门窗等开口连接的半封闭区域，开口用多边形表示。先渲染相机所在区域，再对区域里的每个入口，从焦点穿过入口多边形各边伸出平面，构成类似视锥的体积，邻区内容按它剔除（卷 II 11.5.1.4）。这与本页「入口剔除」一致。
• 遮挡体/反入口 (antiportal)：反过来，从焦点穿过遮挡物的轮廓边伸出平面，得到被遮挡的锥形区域，完全落在其中的远处物体被剔除（卷 II 11.5.1.5）。
• 取舍：入口适合门窗不多的室内，入口只占视锥体积的一小部分，入口外的大量物体被剔掉；反入口适合室外大场景，近处物体常挡住大片视锥。PVS 见 遮挡剔除 中的 GEA 部分。