这是“揭秘PVS”系列的第一部分。
- 传送门与《雷神之锤》
- 粗略的基础可见性
- 通过裁剪实现的精细可见性
- 传送门流将所有内容整合在一起（待发布）
《雷神之锤》第一关的预计算可见性。摄像机位置用红色标出。
你是否曾想知道《雷神之锤》的预计算可见性究竟是如何工作的？我也有同样的疑问，所以我编写了vis.py，这是一个用Python重新实现其算法的工具。本指南包含了理解vis所需的所有信息，vis是《雷神之锤》、《半条命》和Source引擎游戏使用的工具。
在《雷神之锤》的开发过程中，过度绘制成为了一个问题。过度绘制指的是在渲染一帧时，同一个像素被多次写入。只有最后一次写入的颜色会保留，之前的写入都会被浪费掉。如果你的游戏是软件渲染的，并且已经将90年代中期的PC推到了极限，这种情况就非常糟糕。
如何减少过度绘制？让我们从解决方案的宏观概述开始。
传送门剔除有助于减少过度绘制
在3D游戏中，减少绘制的物体数量是一个好主意。视锥剔除是其中一种基本方法，即在渲染过程中跳过确认在虚拟摄像机视野之外的物体。
这可以通过物体的包围盒或包围球来实现。
视锥剔除仍然留下了一些性能问题。许多物体可能仍然在摄像机的视野范围内，即使它们对最终图像没有任何贡献。如果所有物体都从前到后渲染，这不会导致性能灾难。GPU的早期z测试会有所帮助。然而，在大型世界中，最好一开始就不要提交这些物体进行渲染。
遮挡剔除是一个过程，在这个过程中，你会丢弃那些你认为位于场景中其他物体后面的物体。其目的是尽可能多地丢弃被遮挡的物体。这并不是严格必需的，因为无论如何，z缓冲区会确保你得到正确的图像。有几种方法可以实现这一点，例如层次化z缓冲区、遮挡查询、传送门剔除和潜在可见集（PVS）。在本文中，我将讨论最后两种方法：传送门和PVS。
在传送门剔除中，世界被划分为虚拟摄像机可以移动的空间和它们之间的开口。这些空间被称为单元、视单元、区域、簇或扇区，而开口被称为传送门。这种划分在建筑模型中特别有用，尤其是那些通过门或窗户连接的独立房间。它也适用于大多数室内游戏关卡 ：
我们示例关卡的地图，显示了三个手动放置的传送门。单元的颜色与其入口传送门相同。在这种情况下，摄像机所在的单元也是可见的。
传送门渲染从摄像机的单元开始。游戏渲染该单元内的所有物体，然后递归地查看从该单元引出的传送门，以确定还需要绘制什么。它渲染每个单元中的所有物体，然后检查该单元的传送门。如果一个传送门在屏幕上没有与另一个传送门对齐，它就不会被访问。每个连续的传送门都会将可见的屏幕区域缩小，直到整个传送门被裁剪掉。
测试传送门可见性的一种直接方法是相交它们的屏幕空间包围盒。这些包围盒在下图中以白色显示。如果两个包围盒重叠，我们可以通过相应的传送门看到。更精确的测试可以通过3D裁剪或逐像素操作进行。
这是游戏中三个传送门的样子。传送门开口显示为彩色多边形，它们的屏幕空间包围盒为白色。物体的包围盒用虚线表示。星形物体被剔除，因为它没有与红色传送门重叠。
《雷神之锤》引擎使用了传送门，但仅在地图准备阶段使用。在运行时，传送门是不可见的。这种技术是Seth Teller在其1992年的论文中提出的PVS方法的变体，该方法仅适用于轴对齐的墙壁。
《雷神之锤》地图中的传送门消失了
传送门通常由关卡设计师手动放置。《雷神之锤》的bsp地图编译工具会自动放置传送门，这很好，但不幸的是，它创建了大量的传送门！
在TrenchBroom地图编辑器中查看的《雷神之锤》第一张地图，传送门以红色显示。正如你所见，不仅仅是门道充当传送门。
在《雷神之锤》中，单元非常小。但在运行时不会测试任何传送门。相反，每个单元都会获得一个预计算的其他单元列表，这些单元可以从它看到。这就是该单元的潜在可见集（PVS）。
在《雷神之锤》中，单元是一个小的凸空间体积，因此一个房间通常会被分割成多个单元。这些单元对应于二叉空间分区（BSP）树的叶子。BSP树用于将地图划分为单元和传送门。对我们来说，具体的方法并不重要。但BSP确实使得在运行时找到摄像机所在的单元变得容易。
既然我们现在已经进入了《雷神之锤》的领域，我将开始称单元为叶子。叶子是源代码、关卡编辑器、错误消息和其他《雷神之锤》资源中使用的术语。含义完全相同，它只是一个通过传送门连接到其他单元的凸单元。这是我们的示例关卡中叶子的样子：
示例地图被划分为凸叶子。叶子的颜色是随机的。
传送门出现在叶子之间，正如预期的那样：
由bsp工具自动放置的传送门。这张地图基本上是2D的，但讨论的所有内容在3D中也同样适用。叶子索引以白色显示。
没有什么能阻止他们将多个叶子组合成更大的单元，从而减少传送门的数量。事实上，这正是他们在《雷神之锤2》中所做的，使用了“簇”来组合叶子。
使用更大的叶子簇，确实会导致更多的过度绘制。此外，由凸叶子组成的簇本身可能不再是凸的。但即使在这种情况下，你仍然可以假装它仍然是凸的，并假设簇内的传送门可以从簇的任何地方看到。这虽然不太准确，但可行。
vis的高级概述
《雷神之锤》地图工具vis接收由另一个工具bsp生成的传送门，预计算一个叶子到叶子的可见性矩阵，并将该矩阵写回编译后的地图文件。本系列文章描述了vis的功能。
我们知道，叶子只能通过传送门相互看到。所以我们甚至不需要知道叶子的具体样子，只需要知道它们是如何连接的。
在最基本的层面上，vis进行两次递归的深度优先遍历，然后在将可见性结果写回编译后的地图文件之前进行快速解析。三个步骤：
- 基础可见性。 估计粗略的叶子到传送门的可见性。
- 完全可见性。 通过传送门裁剪细化粗略结果。
- 解析。 将细化的传送门到叶子的结果合并为最终的叶子到叶子可见性。
为了快速了解，我推荐Matthew Earl的关于《雷神之锤》PVS的精彩视频。
传送门有方向
在传送门系统中，单元和传送门被结构化为单元和传送门图。《雷神之锤》的地图工具遵循这种模式，并通过传送门连接叶子，尽管这种结构在运行时并不存在。叶子通过传送门连接：
叶子（节点）通过传送门（边）在单元和传送门图中连接。
每个传送门都是一个3D多边形。它们由bsp写入一个纯文本文件，文件包含版本代码、叶子和传送门的数量，然后每行一个传送门。如下所示：
PRT1
11
12
4 0 1 (880 -224 -8 ) (880 -272 -8 ) (880 -272 72 ) (880 -224 72 )
4 1 2 (832 -224 -8 ) (832 -272 -8 ) (832 -272 72 ) (832 -224 72 )
