加速算法

核心思想: 正如“红色皇后”效应所言，图形硬件性能的增长永远追不上我们对更高帧率、更高分辨率、更逼真效果和更复杂场景的追求。因此，我们永远需要加速算法来弥合性能差距，在有限的时间内完成渲染任务。本章的核心就是如何通过“更聪明地工作”而非“更费力地工作”来渲染复杂场景。

19.1 空间数据结构 (Spatial Data Structures)

核心观点: 为了避免对场景中所有物体进行暴力测试（例如，每个物体都和视锥体求交），我们需要一种方法来高效地组织场景中的几何体。空间数据结构就是答案，它通过在空间上对物体进行划分和组织，能将许多查询操作的时间复杂度从 $O (n)$ 优化到 $O (lo g n)$ 。

关键术语:

层次化 (Hierarchical): 数据结构像一棵树，顶层包含底层，查询时可以快速排除掉整个分支，无需逐一检查。
空间细分 (Space Subdivision): 这类结构（如BSP树、八叉树）将整个场景空间递归地切分成更小的区域。
包围几何体 (Bounding Geometry): 这类结构（如BVH）不是划分空间，而是用简单的几何体（包围盒）将复杂的物体包裹起来。

19.1.1 层次包围体 (Bounding Volume Hierarchy, BVH)

核心观点: BVH 是通过用简单的几何体（包围体, BV）层层包裹复杂物体来加速查询的一种树状结构。其基本原则是：如果查询（如光线、视锥体）没有碰到父节点的包围体，那么它也绝不可能碰到该父节点下的任何子物体。

关键术语:

包围体 (Bounding Volume, BV): 用于包裹物体的简单几何体，常见的有轴对齐包围盒 (AABB)、定向包围盒 (OBB) 和球体。它的相交测试成本远低于内部的复杂几何体。
树结构:
- 根节点 (Root Node): 包围整个场景。
- 内部节点 (Internal Node): 包围其所有子节点。
- 叶子节点 (Leaf Node): 包围具体的几何图元（如三角形）。
k叉树 (k-ary tree): 每个内部节点有k个子节点。k值越大，树的高度越低，遍历步数越少，但每个节点处理更复杂。实践中k=2, 4, 8较为常见。

工作原理 (以光线追踪为例):

光线从根节点开始测试。
如果光线未命中当前节点的BV，则该节点下的整个子树都被剪枝 (Prune)，无需再测。
如果光线命中，则递归地对其所有子节点进行测试。
到达叶子节点时，才对内部的实际几何体进行精确的相交测试。
在寻找最近交点时，可以利用已找到的最近距离来进一步剪枝：如果一个BV的相交点比已知的最近距离还远，那么这个BV及其子树也可以被忽略。

动态场景处理:

当物体移动时，可以自下而上地调整 (Refit) BV，或者对变化剧烈的部分进行局部重建 (Rebuild)。

19.1.2 BSP树 (Binary Space Partitioning Tree)

核心观点: BSP 树通过一个分割平面 (Splitting Plane) 将空间递归地一分为二。它的显著特点是能够根据观察点位置，对场景中的物体进行有序遍历。

轴对齐的BSP树 (k-D树)

核心特点: 分割平面始终与坐标轴（X, Y, Z）垂直。
构建过程: 递归地选择一个轴和一个位置来分割当前空间的AABB，直到满足停止条件。
物体处理: 跨越分割平面的物体可以被：(1) 存储在父节点中；(2) 同时属于两个子节点；(3) 沿平面被切割成两部分。
关键应用: 能提供粗略的前后排序 (approximate front-to-back order)。这对于遮挡剔除 (Occlusion Culling) 和减少过度绘制 (Overdraw) 非常有用。

多边形对齐的BSP树

核心特点: 使用场景中的某个多边形所在的平面作为分割平面。
构建过程: 构建过程复杂且耗时，通常是离线完成的。与分割平面相交的其他多边形会被切割。
关键应用: 能提供精确的遮挡顺序 (exact occlusion order)。在没有硬件 Z-Buffer 的时代（如游戏《DOOM》），这是实现三维场景渲染的关键，配合画家算法 (Painter's Algorithm)（从后往前绘制）可以正确处理遮挡关系。

19.1.3 八叉树 (Octree)

核心观点: 八叉树是一种特殊的、规则化的轴对齐BSP树。它总是将一个立方体空间同时沿三个轴的中心点进行分割，精确地生成8个大小相等的子立方体。二维版本称为四叉树 (Quadtree)。

优点: 结构非常规整，节点的空间位置和大小可以隐式计算，无需存储，因此内存更紧凑，某些查询操作更高效。
缺点: 对于分布不均匀的几何体，可能会产生很多不必要的空节点。一个位于父节点中心的小物体会被存储在层级很高的节点中，导致其包围盒过大，降低了剔除效率。

改进：松散八叉树 (Loose Octree)

核心思想: 每个节点的包围盒比常规八叉树的区域稍大一些（例如，边长乘以一个因子 $k > 1$ ）。
优点:
1. 物体跨越边界的可能性大大降低，一个物体可以被完整地放入更深层的节点中。
2. 简化了动态物体的插入和删除操作，因为物体通常只属于一个节点。

19.1.4 缓存无关和缓存感知的表示

核心观点: 现代CPU的计算速度远超内存访问速度，因此数据在内存中的布局对性能至关重要。优化空间数据结构的内存布局可以显著减少缓存未命中 (Cache Miss)，从而提升性能。

缓存感知 (Cache-Aware): 针对已知的缓存大小进行优化。例如，将树节点数据压缩到恰好能放入一个缓存行（如64字节）的大小。
缓存无关 (Cache-Oblivious): 算法设计不依赖特定的缓存大小，但在各种缓存体系下都能表现良好。
- van Emde Boas 布局: 是一种经典的缓存无关布局策略。它不是按深度优先或广度优先存储树节点，而是递归地将树按高度对半分割，并将这些子树块连续存储在内存中。这使得在遍历树时，父节点和其紧邻的子孙节点在内存中的物理位置也更近，提高了数据局部性 (Data Locality)。
- 公式表达: $v (T) = {{T}, {v (T_{0}), v (T_{1}), \dots, v (T_{n})}, if T has a single node else$ 其中 $T_{0}$ 是树的上半部分， $T_{1}, \dots, T_{n}$ 是从 $T_{0}$ 叶子节点延伸出的各个子树。

19.1.5 场景图 (Scene Graph)

核心观点: 场景图是一个更高层次的、面向开发者的树状结构，它组织的不仅仅是几何体，更是整个场景的逻辑关系、属性和层级。它关心的是“是什么”，而BVH/BSP等结构关心的是“在哪里”。

组织内容: 变换（位置、旋转、缩放）、材质、光源、LOD（细节层次）、动画数据等。
核心功能:
- 层次变换 (Hierarchical Transformations): 移动父节点（如汽车），其所有子节点（如轮子）会跟着移动，同时子节点自身还可以有独立运动（轮子自转）。
- 实例化 (Instancing): 允许多个节点引用同一个几何数据，从而在场景中创建多个副本而无需复制数据，极大节省内存。当多个节点指向同一个子节点时，结构变为有向无环图 (DAG)。

与加速结构的关系:

场景图本身可以通过节点包围盒提供一定的剔除能力，但它主要为了场景管理的便利性。
为了达到最高的渲染效率，通常会基于场景图中的几何信息，额外构建一个或多个专门的加速结构（如BVH或k-D树）。这个过程称为空间化 (Spatialization)。你可以把场景图看作是“源数据”，而加速结构是为特定查询任务（如渲染、物理）编译出的“优化后的数据”。

19.2 剔除技术 (Culling Techniques)

核心观点: 剔除的本质就是在渲染管线的早期阶段，识别并丢弃那些对最终图像没有贡献的几何体。剔除得越早、越快，性能提升就越显著。最理想的剔除发生在CPU端，这样可以避免将无效数据发送给GPU，节省带宽和GPU处理时间。

关键术语:

剔除 (Culling): 从需要处理的物体集合中移除不可见部分的过程。
可见性剔除 (Visibility Culling): 专指为渲染而进行的剔除。主要分为三类：
1. 背面剔除 (Backface Culling): 剔除背对摄像机的多边形。
2. 视锥体剔除 (View Frustum Culling): 剔除摄像机视野范围（视锥体）之外的物体。
3. 遮挡剔除 (Occlusion Culling): 剔除被其他不透明物体遮挡的物体。

理论基础：PVS vs. EVS

精确可见集 (Exact Visible Set, EVS): 理论上所有可见图元的完美集合。实时计算EVS的开销极大，几乎不现实。
潜在可见集 (Potentially Visible Set, PVS): 对 EVS 的一种快速估算。我们的目标是高效地计算出一个“足够好”的PVS。
- 保守的 (Conservative) PVS: PVS 完全包含 EVS。这意味着可能会渲染一些最终看不见的物体，但保证图像是正确的。这是最常用、最实用的策略。
- 近似的 (Approximate) PVS: PVS 可能不完全包含 EVS。这可能导致画面出错（如物体突然消失），但计算速度可能更快。

19.3 背面剔除 (Backface Culling)

核心观点: 对于一个封闭的不透明物体，我们永远只能看到其朝向我们的那一面。因此，那些法线方向背离摄像机的三角形可以被安全地剔除。这是最基本、开销最低的剔除技术，通常由硬件在光栅化阶段自动完成。

判断方法:

屏幕空间测试: 在投影到2D屏幕后，检查三角形顶点的环绕顺序 (Winding Order)。例如，可以预先规定所有正面三角形的顶点按逆时针排序，那么在屏幕上呈现为顺时针的三角形就是背面，可以剔除。这是GPU的常用做法，且更稳健。
世界/观察空间测试: 计算从三角形到摄像机的向量 v 与三角形法线 n 之间的点积。如果点积结果小于或等于零（取决于坐标系和向量定义），则表示夹角大于等于90度，即三角形背对摄像机。

高级技巧：集群背面剔除 (Clustered Backface Culling)

核心思想: 与其逐个测试三角形，不如将一组三角形（一个Mesh Part或一个Cluster）作为一个整体来测试，从而一次性剔除一批三角形。
关键概念：法线锥 (Normal Cone):
- 为一组三角形的所有法线计算一个最小包围圆锥。这个锥体由一个中心法线 n 和一个半角 α 定义。
- 通过一次测试判断整个法线锥是否背对摄像机。如果整个锥体都背对，那么这组内的所有三角形都可以被安全剔除。
测试公式 (考虑包围球): 假设几何体被一个中心为 c、半径为 r 的球体包围，摄像机位置为 e，法线锥为 (n, α)，则当满足以下条件时，整个集群可被视为背面剔除： $n \cdot (c - e) > sin (α + β), 其中 sin β = \frac{r}{∥ c - e ∥}$ 这个公式本质上是检查从摄像机看向包围球的视线，是否能“绕过”法线锥的边界。

19.4 视锥体剔除 (View Frustum Culling)

核心观点: 摄像机的视野是一个被六个平面（上、下、左、右、近、远）所包围的金字塔形空间，称为视锥体 (Frustum)。任何完全位于此空间之外的物体都无需渲染。

层级化剔除流程 (Hierarchical Culling): 这是空间数据结构（如BVH）的经典应用场景。

从根节点开始，测试其包围体（BV）与视锥体的六个平面的关系。
会出现三种结果：
- 完全外部 (Outside): 该节点及其所有子节点全部被剔除。这是性能提升的关键。
- 完全内部 (Inside): 该节点及其所有子节点全部保留，并且其子节点无需再进行视锥体测试，直接视为可见。
- 相交 (Intersecting): 无法确定，需要递归地对其子节点进行同样的测试。

优化技巧：平面遮挡 (Plane Masking)

当一个父节点与视锥体相交时，我们可以记录下它具体在哪些平面的内部。
在测试其子节点时，仅需对那些父节点与之相交或位于其外部的平面进行测试，而无需重复测试它已完全处于内部的那些平面。这能有效减少每个节点的测试次数。

19.5 入口剔除 (Portal Culling)

核心观点: 这是一种针对室内或建筑场景的特殊遮挡剔除技术。它将场景预处理为由单元格 (Cells)（如房间）和入口 (Portals)（如门窗）组成的结构，利用墙体作为天然的巨大遮挡物。

工作原理:

预处理: 将场景手动或自动划分为 Cells，并定义连接它们的 Portals，形成一个邻接图。
运行时: a. 首先渲染摄像机所在的当前Cell中的所有物体。 b. 检查当前Cell中所有可见的Portals。 c. 对于每一个可见的Portal，将其边界作为新的、更小的裁剪平面，来收紧当前的视锥体。 d. 递归地进入该Portal连接的下一个Cell，并使用这个被收紧后的新视锥体继续进行渲染和剔除。 e. 整个过程就像是你透过一扇门去看另一个房间，你的视野被门框所限制。

实现要点:

需要标记已渲染的物体，防止一个物体因从不同Portal可见而被重复渲染。
可以使用模板缓冲区 (Stencil Buffer) 或裁剪矩形 (Scissor Rectangle) 来在硬件层面精确地执行Portal的裁剪，避免渲染被Portal边框遮挡的像素，效率更高。

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

核心观点: 这是一种以牺牲少量视觉质量为代价来换取性能的技术。其基本思想是，那些在屏幕上看起来非常小的物体或三角形，对最终画面的贡献微乎其微，可以被剔除。

细节剔除 (Detail Culling)

也称为屏幕尺寸剔除 (Screen-Size Culling)。
方法: 计算一个物体的包围体投影到屏幕上所占的像素面积。如果这个面积小于一个预设的阈值（比如100个像素），就直接剔除该物体。
应用场景: 常用于LOD系统，或在玩家快速移动时，此时玩家难以注意到远处小细节的变化。

小三角形剔除 (Small Triangle Culling)

动机: 极小的三角形（例如，面积小于一个像素）不仅视觉上无贡献，而且其光栅化效率非常低，会浪费GPU资源。
一个简单的剔除方法: 计算三角形在屏幕空间的AABB（min, max），如果在着色器中满足以下条件，则可将其剔除： $any (round (min) == round (max))$
- 解释: 这个公式检查三角形AABB的 x 坐标范围或 y 坐标范围在取整后是否是同一个整数。如果是，就意味着这个三角形非常“窄”或“扁”，窄到无法跨越任何一个像素的中心采样点，因此可以安全地剔除。

19.7 遮挡剔除 (Occlusion Culling)

核心观点: Z-Buffer 虽然能正确处理像素级别的遮挡，但它是一种“暴力”解法。对于深度复杂度 (Depth Complexity) 高的场景（即一个像素后面层层叠叠有很多物体），Z-Buffer 依然会处理和着色大量最终被覆盖的物体，造成巨大的性能浪费。遮挡剔除的目标就是在物体被发送到渲染管线之前，就判断出它是否被其他物体完全遮挡，从而从源头上避免这种浪费。

关键术语:

遮挡物 (Occluder): 遮挡住其他物体的物体。
被遮挡物 (Occludee): 被其他物体遮挡的物体。
过度绘制 (Overdraw): 同一个像素被着色多次的现象。遮挡剔除旨在显著降低过度绘制。
基于点的可见性 (Point-based Visibility): 从单个观察点出发判断可见性，是实时渲染的标准模式。
基于单元格的可见性 (Cell-based Visibility): 从一个空间区域（Cell）内的所有点出发判断可见性。如果一个物体对Cell内所有点都不可见，才能剔除它。计算昂贵，通常离线预计算。

通用算法思想:

维护一个遮挡表示 (Occlusion Representation)，可以理解为当前场景中“遮挡物”的简化信息。
以大致从前到后 (front-to-back) 的顺序遍历物体。
对于每个物体，先用遮挡表示来测试它是否被遮挡。
如果被遮挡，则直接剔除。
如果不被遮挡（或无法确定），则渲染它，并将其更新到遮挡表示中，因为它现在也可能成为新的遮挡物。

19.7.1 遮挡查询 (Occlusion Queries)

核心观点: 这是利用 GPU 硬件 来进行遮挡测试的一种高效方法。其本质是向 GPU 发起一个“提问”：“如果我渲染这个简单的包围盒，会有任何像素通过深度测试吗？”

工作流程:

CPU 发起查询: CPU 命令 GPU 渲染一个复杂物体的代理几何体（通常是其AABB包围盒）。
GPU 测试: GPU 在光栅化这个包围盒时，只进行深度测试，但不写入颜色和深度缓冲。它会统计通过了深度测试的像素（或片元）数量。
GPU 返回结果: GPU 将“可见像素数量”的结果返回。如果结果为 0，意味着包围盒被完全遮挡，其内部的复杂物体就可以安全地剔除。

关键挑战与解决方案:

延迟 (Latency): CPU 发出查询后，不能立即得到 GPU 的答案，如果原地等待会造成“阻塞”。
异步查询 (Asynchronous Queries): CPU 发出查询后不等待，继续处理其他任务，稍后再回来检查结果。
条件渲染 (Conditional Rendering): 这是更优的方案。CPU 将遮挡查询和正式的绘制命令一起提交给 GPU，并附带一个条件：“只有当这个遮挡查询的结果显示可见时，你才执行那个正式的绘制命令”。这完美地解决了延迟问题，将判断逻辑完全交给了 GPU。

19.7.2 层次Z缓冲 (Hierarchical Z-Buffering, HZB)

核心观点: HZB 是一种经典且影响深远的图像空间 (image-space) 遮挡剔除算法，是现代许多软硬件遮挡剔除技术的基础。它通过构建深度图的图像金字塔来实现快速的、分层的遮挡测试。

关键数据结构：Z金字塔 (Z-Pyramid)

可以理解为 Z-Buffer 的 Mipmaps。
最精细的一层（Level 0）就是普通的 Z-Buffer。
每一层更粗糙的 Mip-level，其每个像素值存储的是下一层更精细的对应 $2 \times 2$ 区域内最远 (Farthest / Max) 的 Z 值。

现代 HZB 剔除流程 (简化版):

生成 HZB:
- 首先，渲染场景中一些主要的、大型的遮挡物，得到一个基础的 Z-Buffer。
- 或者，更常见的是，直接利用上一帧渲染完成的 Z-Buffer。
- 基于这个 Z-Buffer，在 GPU 上通过计算着色器快速生成完整的 Z金字塔。
测试物体 (Occlusion Test):
- 将待测物体的包围盒投影到屏幕空间。
- 根据其投影后的屏幕尺寸，计算出一个合适的 Mip-level λ 来进行测试。尺寸越大，使用的 Mip-level 越精细（λ 越小）。选择 λ 的目标是让投影区域在对应 Mip-level 上只覆盖少数几个像素（如 $2 \times 2$ ）。 $λ = min (⌈ lo g_{2} (max (l, 1))⌉, n - 1)$ (其中 l 是投影包围盒的最长边像素数，n 是 Mip-level 总数)
- 获取包围盒最近的深度值 $z_{min}$ 。
比较与判断:
- 将 $z_{min}$ 与在 Z金字塔 λ 层上对应区域的最远深度值进行比较。
- 如果物体的最近点 ( $z_{min}$ ) 比遮挡物的最远点还要远，那么这个物体一定被完全遮挡。

重要实践技巧:

双重测试 (Two-Pass Method): 为了解决使用上一帧Z-Buffer可能因物体移动而产生的“突然出现”的错误，可以采用两步法：
1. 用上一帧的 HZB 剔除并渲染第一批“可能可见”的物体。
2. 用这批物体生成当前帧的精确 HZB，然后再次测试在第一步中被剔除的物体，将其中通过测试的物体补充渲染出来。这样可以保证渲染结果的正确性。

19.8 剔除系统 (Culling Systems)

核心观点: 现代渲染引擎中的剔除不是单一算法，而是一个多阶段、多粒度的复杂系统，通常结合了 CPU 的粗粒度剔除和 GPU 的细粒度剔除，以最大化效率。

典型的剔除流水线:

物体级别 (Object Level):
- 在 CPU 上对整个物体列表进行粗略剔除。
- 常用技术：视锥体剔除、细节剔除（屏幕尺寸）、基于 HZB 的粗略遮挡剔除。
集群级别 (Cluster/Chunk Level):
- 将通过第一阶段的物体的网格（Mesh）划分为更小的块 (Cluster)。
- 在 GPU 的计算着色器中，对这些 Cluster 进行更精细的剔除。
- 常用技术：更精确的视锥体剔除、集群背面剔除、基于 HZB 的遮挡剔除。
三角形级别 (Triangle Level):
- 对通过第二阶段的 Cluster 中的每一个三角形进行最终的剔除。
- 常用技术：硬件自动的背面和视锥体裁剪、小三角形剔除等。

现代 GPU 驱动的剔除流程: 这是一个非常关键的现代渲染管线模式：

计算着色器剔除 (Compute Shader Culling): 一个 Compute Shader 接收一个物体（或 Cluster）的全部顶点/索引数据。
并行处理: 该 Shader 并行地对每个图元（三角形）执行剔除测试。
结果压缩 (Compaction): 将所有通过测试的图元（三角形）的索引写入到一个新的、紧凑的 GPU 缓冲区中。
间接绘制 (Indirect Draw): Compute Shader 的最后一步是更新一个特殊的绘制命令结构体，其中包含了“要绘制的图元数量”（即通过测试的三角形数量）和“从哪个缓冲区读取索引”。然后，它会触发一个间接绘制命令。
渲染: 渲染管线根据这个间接命令，不多不少，只处理那些真正存活下来的三角形。

核心优势: 整个“剔除-压缩-发起绘制”的过程完全在 GPU 内部完成，无需 CPU 与 GPU 之间的数据回读和同步，效率极高。这是现代引擎处理海量几何体的关键技术之一。

19.9 细节层次 (Level of Detail, LOD)

核心观点: 一个物体对最终画面的贡献越小，我们就可以用越简单的模型来表示它。 当物体距离摄像机很远、在屏幕上只占几个像素时，渲染一个百万面的高精度模型是极大的浪费。LOD 技术通过使用一系列从精细到粗糙的模型版本，来动态地匹配物体的视觉重要性，从而在不牺牲太多视觉质量的前提下，大幅提升渲染性能。

LOD的应用范畴 (不止是几何): LOD 是一个广义的概念，它可以应用于渲染的多个方面：

几何LOD: 最常见的形式，使用不同三角形数量的网格模型。
纹理LOD: 为远处的物体使用分辨率更低的纹理（Mipmapping 就是一种自动化的纹理LOD）。
着色器LOD (Shader LOD): 为远处的物体使用计算开销更低的简化版着色器。
动画LOD: 为远处的角色使用更少的骨骼进行蒙皮计算。
渲染方法LOD: 在极远处，用一个简单的广告牌 (Billboard) 或 Impostor 来代替完整的三维模型。

LOD 系统的三个核心组成部分:

生成 (Generation): 创建一个物体的多个LOD版本。可以通过网格简化 (Mesh Simplification) 算法自动生成，也可以由美术师手动制作。
选择 (Selection): 在运行时，根据特定标准（如距离、屏幕占比）决定当前帧应该使用哪个LOD版本。
切换 (Switching): 在不同LOD版本之间进行平滑过渡，避免明显的视觉跳变。

19.9.1 LOD 切换 (LOD Switching)

核心问题: 在不同LOD模型间切换时，可能会产生瞬间的、令人分心的视觉跳变，这个问题被称为**“ popping ”**。以下是几种应对 popping 的策略。

离散几何LOD (Discrete Geometry LOD)

工作方式: 最简单直接的方法。在某一帧，渲染LOD0；下一帧，如果条件变化，立即切换并渲染LOD1。
优点: 实现简单，对GPU友好（每个LOD都是静态网格，可以高效缓存）。
缺点: Popping 现象最严重。只适用于LOD之间差异极小，或者切换距离非常远的情况。

混合LOD (Blended LOD)

工作方式: 在切换的瞬间，在短时间内同时渲染两个LOD模型，并对它们进行交叉淡入淡出（Cross-fading）。
优点: 过渡平滑，可以有效掩盖 popping。
缺点: 在过渡期间，单个物体的渲染开销会翻倍，在一定程度上违背了LOD的初衷。不过，只要过渡时间足够短，且场景中同时进行切换的物体不多，这种开销通常是可以接受的。

Alpha LOD

工作方式: 当一个物体即将因为距离太远而被剔除时，不是让它突然消失，而是逐渐将其Alpha值从1降到0，实现平滑的淡出效果。
优点: 解决了物体被剔除时的“pop-out”问题。
缺点:
1. 需要处理半透明，可能需要深度排序。
2. 性能增益只有在物体完全消失（不被渲染）后才能实现。
- 替代方案: 点阵剔除半透明 (Screen-door Transparency)，通过随机丢弃像素来模拟半透明，可以避免深度排序，实现类似“溶解”的效果。

CLOD 和地貌LOD (Geomorph LOD)

核心思想: 实现模型细节的连续变化，而非离散的跳变。
连续LOD (CLOD): 基于边坍缩 (edge collapse) 和顶点分裂 (vertex split) 操作，可以动态地、逐个三角形地增减模型的复杂度。
地貌LOD (Geomorph LOD): 在两个离散的LOD模型之间切换时，通过顶点插值的方式，让高精度模型的顶点平滑地移动到低精度模型顶点的位置上，实现形态上的平滑过渡。
现状: 这两种技术在概念上很完美，但实践中很少使用。因为它们通常需要动态修改顶点数据，对GPU缓存不友好，且模型持续的“蠕动”也可能分散玩家注意力。

19.9.2 LOD 选择 (LOD Selection)

核心观点: LOD选择机制负责回答一个问题：“对于这个物体，在当前帧我应该用哪个LOD？”。这个决策基于一个度量标准 (Metric) 或 效益函数 (Benefit Function)。

基于范围 (Range-based)

工作方式: 最常用且最简单的方法。为每个LOD预设一个距离范围。例如，0-50米用LOD0，50-200米用LOD1，以此类推。
问题: 当物体在距离边界（如50米）附近来回移动时，会导致LOD模型频繁地来回切换，产生闪烁。
解决方案：延迟切换 (Hysteresis)
- 设置不同的切换阈值。例如，从LOD0切换到LOD1的距离是50米，但从LOD1切回LOD0的距离是48米。这样就在边界处创建了一个“缓冲带”，防止了频繁切换。

基于投影面积 (Projected Area-based)

工作方式: 一个更鲁棒的度量标准。计算物体包围体投影到屏幕上所占的像素面积。面积越大，说明物体在屏幕上越重要，应使用更高精度的LOD。
优点: 它同时考虑了距离和视野角度 (FOV)。一个在屏幕边缘的远处物体，其投影面积会比在屏幕中心的小，这种方法能自然地处理这种情况。
球体投影半径估算公式: $p = \frac{n \cdot r}{d \cdot ( c - v )}$ 其中， $p$ 是投影半径， $n$ 是近裁剪平面距离， $r$ 是包围球半径， $d$ 是观察方向， $c$ 是球心， $v$ 是视点位置。

其他选择方法

重要性 (Importance): 场景中的核心物体（如玩家角色）可以被赋予更高的重要性，即使在远处也使用较高的LOD。
焦点 (Focus): 结合眼动追踪技术，可以只在玩家注视的区域使用高精度LOD。
可见性 (Visibility): 一个被树叶部分遮挡的近处物体，也可以适当降低其LOD。

19.9.3 限时的LOD渲染 (Time-Critical LOD Rendering)

核心观点: 将LOD选择从“追求最佳画质”提升到“保证稳定帧率”的系统性层面。系统被赋予一个目标帧时间（如16.6ms对应60FPS），并动态调整场景中所有物体的LOD，以确保渲染任务能在此时间内完成。

优化问题:

目标: 在满足时间预算的前提下，最大化整个画面的总效益 (Total Benefit)。 $Maximize \sum Benefit (O, L)$
约束: 整个场景的总成本 (Total Cost) 必须小于等于目标时间。 $\sum Cost (O, L) \leq T$

贪婪算法 (Greedy Algorithm): 由于这是一个NP完全问题，无法实时求得最优解。实践中采用贪婪算法来获得近似最优解：

定义效益和成本:
- 效益 (Benefit): 通常用物体的屏幕投影面积来衡量其对画面的贡献。
- 成本 (Cost): 通常用LOD的顶点数或三角形数来估算其渲染开销。
计算“性价比”:
- 对于每个物体的每个LOD，计算一个Value值： $Value = \frac{Benefit ( O , L )}{Cost ( O , L )}$ 这代表了“每单位渲染成本能换来多少画面贡献”。
选择LOD:
- 从零成本开始，不断地为场景中的物体提升LOD等级。每一次提升，都选择那个能带来最大Value增量的选项，直到总成本接近或达到时间预算T。
- 一个重要技巧是，为每个物体设置一个成本为0的“空LOD”，这样当预算紧张时，算法可以选择完全不渲染那些“性价比”最低的物体。

19.10 渲染大型场景

核心观点: 当游戏世界的数据量（纹理、模型等）达到数百GB，远超当前硬件的内存（RAM）和显存（VRAM）容量时，我们必须放弃“一次性全部加载”的思路。解决方案是只将当前视点附近、即将需要的资源从硬盘动态加载到内存中，这个过程称为流式传输 (Streaming)。

19.10.1 虚拟纹理和流式传输 (Virtual Texturing and Streaming)

核心观点: 虚拟纹理技术允许我们使用一张分辨率极高（如128k x 128k）的巨型纹理，而显存中只需存储当前摄像机视野内实际需要被渲染的纹理部分。这本质上是将操作系统的“虚拟内存”概念应用到了GPU纹理管理上。

关键术语:

虚拟纹理 (Virtual Texturing) / 稀疏纹理 (Sparse Textures) / Megatexture: 指代这项技术或其使用的巨型纹理。
瓦片 (Tile): 巨型虚拟纹理和物理显存都被划分为固定大小的小块（如128x128），Tile是数据传输和管理的基本单位。
页表 (Page Table): 一个核心的查找表，负责将虚拟纹理空间中的Tile地址映射到它在物理显存中的实际存储位置。

工作流程:

虚拟地址空间: 应用程序认为自己拥有一块巨大的、完整的纹理显存。
物理缓存: 实际上，物理显存只是一块相对较小的缓存区。
映射: 当渲染需要某个虚拟纹理区域时，系统通过页表查找对应的Tile。
- 如果Tile已在物理显存中（“常驻”），则直接采样。
- 如果Tile不在物理显存中，则发生“缺页”，系统会从硬盘中将这个Tile加载（流式传输）到物理显存的一个空闲位置，并更新页表。
淘汰: 当物理缓存满了，需要加载新Tile时，系统会根据某种策略（如LRU - 最近最少使用）将一个旧的Tile从物理显存中淘汰。

核心挑战：如何知道需要哪些Tile？

反馈渲染 (Feedback Rendering): 在正式渲染前，先进行一个极低分辨率的“反馈”预渲染遍（z-prepass）。这个Pass不输出颜色，而是输出每个像素将会访问的虚拟纹理坐标和Mipmap层级。通过分析这张反馈图，系统就能生成一个当前帧所需Tile的精确列表，并发起加载请求。

19.10.2 纹理转码 (Texture Transcoding)

核心观点: 这是虚拟纹理系统的一个重要优化。为了在磁盘占用和GPU采样效率之间取得最佳平衡，我们对纹理使用两种不同的压缩格式。

工作流程:

磁盘存储: 纹理在硬盘上以一种高压缩率的格式（如JPEG或专门的格式如Basis）存储，以减小游戏包体大小和磁盘读取时间。
实时转码: 当一个Tile从硬盘被流式读入内存时，系统会快速地将其解压，然后再重新编码（即转码, Transcoding）成GPU硬件原生支持的块压缩格式（如BC7, ASTC等）。
显存存储: 转码后的Tile被存入物理显存，GPU可以对其进行高效的硬件采样。

优势: 既享受了小文件体积带来的好处，又保证了GPU渲染时的高性能纹理读取。

19.10.3 通用流式传输 (Generic Streaming)

核心观点: 将流式传输的思想从纹理扩展到所有类型的游戏资产，包括几何模型、AI脚本、粒子效果等。

实现方式:

将整个游戏世界地图划分为一个二维网格，网格单元通常是正方形或六边形。
每个网格单元（Tile）关联了该区域内的所有资产。
流式系统始终保持玩家当前所在的Tile以及其所有相邻的Tile被加载到内存中。
当玩家移动到新的Tile时，系统会异步地开始加载新邻居的资产，并卸载已经远去的Tile的资产，从而实现无缝的大世界体验。

19.10.4 地形渲染 (Terrain Rendering)

核心观点: 地形是超大场景最典型的代表，其渲染需要专门的、高效的LOD和流式传输方案。

几何Clipmap (Geometric Clipmap)

核心思想: 类似于纹理Clipmap，它维护一组以摄像机为中心的嵌套的正方形网格。
最中心的网格分辨率最高，往外的网格分辨率逐级降低。
当摄像机移动时，整个嵌套网格结构跟随移动，新的地形数据被“裁剪”并流式读入网格的边缘，旧数据则被丢弃。
不同分辨率层级之间的接缝通过在过渡区域进行顶点和纹理的平滑插值来消除。

分块LOD (Chunked LOD)

核心思想: 一种非常流行且灵活的方案。将整个地形划分为一个四叉树 (Quadtree)，每个节点代表一个地形块 (Chunk)。
LOD选择:
1. 从四叉树的根节点开始递归遍历。
2. 对每个节点（Chunk），计算其屏幕空间误差 (Screen-space Error)。这个误差值衡量了如果使用当前Chunk的LOD来近似表达地形，在屏幕上会产生多大的像素偏差。
3. 如果误差小于预设阈值（如1个像素），则说明当前LOD足够精细，直接渲染这个Chunk，并停止递归。
4. 如果误差大于阈值，则继续递归到四个子节点，以寻求更高精度的表达。
屏幕空间误差公式: $s = \frac{ϵ \cdot w}{2 \cdot d \cdot tan ( \frac{θ}{2} )}$ 其中， $s$ 是屏幕空间误差（像素）， $ϵ$ 是几何误差（世界单位）， $w$ 是屏幕宽度， $d$ 是到Chunk的距离， $θ$ 是视野角度。
几何误差 $ϵ$ : 通常用**豪斯多夫距离 (Hausdorff distance)**来衡量，它代表了简化网格与原始高精度网格之间的最大偏差。

核心挑战：裂缝修复 (Crack Fixing)

当一个高LOD的Chunk与一个低LOD的Chunk相邻时，它们共享的边界顶点数量不同，会导致地形上出现可见的裂缝。
解决方案:
1. 缝合 (Stitching): 动态生成额外的三角形来“缝合”裂缝。
2. 变形 (Morphing): 让高LOD Chunk边界上的顶点平滑地插值移动到低LOD Chunk对应顶点的位置上，消除高度差。
3. 受限四叉树 (Restricted Quadtree): 强制规定相邻Chunk的LOD等级最多只能相差一级。这大大简化了裂缝情况，可以用预计算的索引缓冲来直接生成无裂缝的连接。

NothingToSay0031

Explorer

Graph View

19 Acceleration Algorithms

加速算法

19.1 空间数据结构 (Spatial Data Structures)

19.1.1 层次包围体 (Bounding Volume Hierarchy, BVH)

19.1.2 BSP树 (Binary Space Partitioning Tree)

轴对齐的BSP树 (k-D树)

多边形对齐的BSP树

19.1.3 八叉树 (Octree)

19.1.4 缓存无关和缓存感知的表示

19.1.5 场景图 (Scene Graph)

19.2 剔除技术 (Culling Techniques)

19.3 背面剔除 (Backface Culling)

19.4 视锥体剔除 (View Frustum Culling)

19.5 入口剔除 (Portal Culling)

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

细节剔除 (Detail Culling)

小三角形剔除 (Small Triangle Culling)

19.7 遮挡剔除 (Occlusion Culling)

19.7.1 遮挡查询 (Occlusion Queries)

19.7.2 层次Z缓冲 (Hierarchical Z-Buffering, HZB)

19.8 剔除系统 (Culling Systems)

19.9 细节层次 (Level of Detail, LOD)

19.9.1 LOD 切换 (LOD Switching)

离散几何LOD (Discrete Geometry LOD)

混合LOD (Blended LOD)

Alpha LOD

CLOD 和 地貌LOD (Geomorph LOD)

19.9.2 LOD 选择 (LOD Selection)

基于范围 (Range-based)

基于投影面积 (Projected Area-based)

其他选择方法

19.9.3 限时的LOD渲染 (Time-Critical LOD Rendering)

19.10 渲染大型场景

19.10.1 虚拟纹理和流式传输 (Virtual Texturing and Streaming)

19.10.2 纹理转码 (Texture Transcoding)

19.10.3 通用流式传输 (Generic Streaming)

19.10.4 地形渲染 (Terrain Rendering)

几何Clipmap (Geometric Clipmap)

分块LOD (Chunked LOD)

Table of Contents

CLOD 和地貌LOD (Geomorph LOD)