Just Cause 2的地形渲染方案
正当防卫（Just Cause）系列一直以开放大世界为核心要点，其中最关键的一项指标就是draw distance，也就是视距，其中正当防卫2（简称JC2）的视距号称是能达到50 Km，而其整张地图的大小也只不过32 Km x 32 Km，相当于一次性将整个地图都渲染进去了。
当然，实际上视距并不等于将整个场景的内容全部都渲染输出，通常来说，近景处的细节会多一些，物件精度也会更高，而远景处，可能就只剩下一些低模，甚至只有地形了。
那么正当防卫2是怎么完成这个超远视距的地形渲染的呢，我们一起来看一下，主要资料来源于文献[1]，有兴趣的同学可以移步原文了解更多细节。
地形渲染在设计之初就设定了如下几个目标：
- 内存消耗低
- 性能消耗低
- 画面品质高
先来看下JC2的一张典型的地形远景渲染效果与对应的wireframe模式：
注意观察海岸线附近的网格密度会比附近的地形密度要稍微高一点。
1. The Concept of Patches
JC2的场景是按照Patch来组织的，Patch尺寸是POT的（比如512 m x 512 m一个Patch），且其方向是与坐标轴平齐的。
根据需求的不同，整个场景会包含多种不同的Patch，比如Terrain Patch, Vergetation Patch等。
JC2会将以相机为中心的N x N个同类Patch称为一个Patch Map，当相机移动时，Patch Map也会发生相应的修正（Patch的增减）。
为了实现Patch的LOD处理，JC2还将多个中心位置重叠且Patch数目完全相同的同类Patch Map称之为一个Patch System（Hierarchical Patch Map），处于这个层级中的相邻两个Patch Map在尺寸上正好是两倍关系，不同层级的Patch Map对应于不同精度的场景数据。
Patch System由一个叫做Patch Manager的class管理，Patch Manager不但会负责Patch Map的更新，同时还会负责Patch的裁剪与内存的管理。
2. Data Pipeline
首先是地形编辑，在编辑阶段，JC2开发了一个地形编辑器，JustEdit，在这个编辑器中，项目组可以创建地图的地形，地形使用一张原始的高度图（raw height map）来实现地形高度逻辑，而地形网格则是使用一张固定分辨率（即单位面积顶点密度固定）的proxy mesh来表示。
地形创建完成后，会将之分割成editor patch来进行存储，在需要的时候只需要勾选就可以完成加载，这种做法使得美术同学可以分别对不同的patch进行编辑而实现协作。
地图编辑制作完成后，则会需要通过一个叫做Terrain Compiler的工具完成从编辑数据到运行时数据的转换（类似于UE的Cook功能），转换成运行时所需要的Stream Patch。
3. Streaming
32 km x 32 km的地图，一次性将所有数据都绘制出来，性能无疑是扛不住的，因此JC2的做法是将地图分割成一个个的Cell，这个Cell就是Stream Patch，每个Stream Patch的尺寸是512 m x 512 m，任一时刻都会保证以相机为中心的8 x 8个Stream Patch组成的Patch Map是可见的（在这种加载策略下，地形的加载范围就是512 x 8 / 2 = 2048 m）。
要做Streaming，就需要从磁盘中将Stream Patch数据读取出来，而为了最大化加载效率，就需要降低读盘时的Seek次数。JC2的做法是分别按照行优先顺序（x/z）与列优先顺序将Stream Patch数据保存一遍，相当于每个Stream Patch都被存储了两次，之后根据是需要加载一行Patch（相机往Z方向移动，假设Z方向表示屏幕的上下方向）还是加载一列Patch来决定是从哪个Stream Patch存储位置进行加载，这样只需要Seek一次，之后顺序加载一行或者一列Patch即可。
最终JC2在角色移动上的速度限制为水平方向512m/s，而每个Stream Patch的数据平均尺寸为128kb，之所以是平均，是因为不同的Stream Patch存储的数据量是不确定的，那么如何保证这个平均数值不会超出128kb呢，这就需要在Terrain Compiler阶段对整个地图的数据消耗进行统计。
每个Stream Patch包含的数据包括三种（每个Stream Patch 512m，贴图分辨率为4m/texel，看来应该是每个Stream Patch一套贴图，可能Weight Map分辨率较高，因此不会出现地表分辨率很低的感觉）：
- Terrain Textures，包括材质与法线贴图
- Height map以及Material Map，经过压缩处理后，每个sample大概消耗16bits。
- Terrain Mesh数据
下面对这些数据的详情进行介绍。
3.1 The Terrain Textures
JC2的地形渲染方案，除了高度图之外，还会用到如下三张贴图：
- Normal map (A8L8 format) ，这是地形的法线贴图
- Material indices (ARGB4444 format)，地形所使用的材质类型的index
- Material weights (ARGB4444 format)，上面的多个材质索引在当前采样点中的权重
Material Indices以及Material weights贴图是PS阶段对多个材质贴图进行采样与混合时使用的。
Terrain Texture的采样密度是按照每个像素覆盖4m来计算的，这种密度无疑是不够的，尤其是近景处，JC2的做法是使用Texture Tiling加上一定的混合策略来实现高清且pattern不会很明显的shading效果。
这里没有介绍贴图混合的实施细节，不过其最终的消耗并不低，实际上有时候会发现场景中树木较多，其性能反而上升，这是因为地形被遮挡住了。。。
3.2 The Height Map and Material Map
Height Map与Material Map的原始密度跟Terrain Texture一样，都是每个像素覆盖4m，而格式则是Height Map采用16bits，Material Map采用8bits，PC上不做任何处理，直接这样存储与使用；而在PS3以及XBox上，则会采用一种类似于DXTC的压缩格式对4x4个Material Map像素block进行有损压缩，从每个像素16+8bits压缩到16bits。
Height Map的压缩则是将格式更改成3:6的浮点格式，其中3bits用作浮点的指数（exponent）数据，每个指数数据则会被2x2个sample（组成一个block）所共享，每个sample的尾数（mantissa）则是6bits的。使用浮点格式的好处是，在一些低频区域（即地形高度变化比较平缓的区域，比如平地）会具有较高的精度，而游戏场景中绝大部分区域都符合这种情况，因此十分划算。将地形高度按照block进行组织的一个好处在于进行raycast的时候可以降低消耗实现性能优化。
当在运行时对height map进行采样时，会通过Catmull-Rom Spline插值对Height进行插值处理，之后使用由Material Map中控制的高分辨率Displacement Map来对结果进行调制，从而可以使用较少的位数来获得较高的画面品质。
为了满足物理计算的需要，在一帧中需要对地形高度数据进行数以千计的采样，为了降低消耗，JC2在PS3/Xbox上设计了一种手工调制过的采样算法，这个算法通过一个SIMD函数来实现，大致上是借用PS3/Xbox的VMX指令集的强大功能，而数量众多的permute指令则进一步增强了这个优化的作用。不过由于x86架构上并没有这种指令集，因此无法进行类似的优化，这也是为什么在PC上需要一套单独的数据格式的原因。
3.3 The Terrain Mesh
Stream Patch是一个覆盖范围为512m x 512m的容器，这个容器中装了很多东西，其中Terrain Mesh就是容器中所装载的数据中的一部分，而Terrain Mesh在JC2的框架下也组成了一套Patch，这个Patch被称之为Terrain Patch，这个Patch包含了对应区域的顶点/索引buffer数据。
Terrain Patch也是按照Patch System来组合的，即包含了一系列的Patch Map。在JC2中，Terrain Patch System包含了总共12级的Patch Map，每个Patch Map都包含了8 x 8个Patch，最小的Patch Map覆盖范围为64 m x 64 m，而最大的Patch Map则覆盖了256 Km x 256 Km的范围，由于Terrain Patch是包含预先生成好的Mesh数据，对于那些超出地图范围之外的Patch是不包含Mesh数据的，对于这些区域的Patch，则会在运行时自动生成一份Mesh数据以实现各个方向的可视距离的一致。
地形网格组织跟上图效果很像，当相机移动时，新的Patch Row/Column会创建并添加到对应的Patch Map中，而对应Patch Map中老的Patch Row/Column则会销毁。
4. Compile-Time Mesh Construction
每个Terrain Patch都包含一个表示这个Patch覆盖区域地形形状的Mesh，出于渲染效率与显示质量考虑，在图形渲染上，这个Mesh的分辨率（单位面积的顶点数）并不是固定的（出于使用简便与计算性能考虑，在物理计算上，则是使用固定分辨率的mesh结构），而是会随着地形的变化而变化，比如高度变化比较快的区域会采用密一点的顶点，高度变化比较平缓的区域则使用稀疏一点的顶点。
基于相机位置，在运行时对地形网格进行调整的算法有很多，比如比较出名的"real-time optimally adapting mesh" (ROAM)算法，但这些算法有几个缺点：
- 会跟着相机的移动而出现地形的跳变（popping），视觉上不够自然
- 由于运行时顶点数量更新的原因，会需要每帧都上传新的地形顶点buffer数据，从而影响渲染效率。
为了解决上述两个问题，JC2采样的是为每个Terrain Patch制作一个不随时间与相机位置而变化的静态Mesh（但是使用Terrain Patch Map本身就会因为Patch之间的密度不同而存在跳变呀？），而这套方案主要考虑两个问题：
- 如果兼顾不同地形的复杂度，这个问题JC2是通过在离线的时候对地形数据进行烘焙来解决的
- 如何根据到相机距离的远近来确定地形网格分辨率，这个问题则是跟模型LOD一样，在运行时根据距离的远近为Terrain Patch选择不同的LOD来做到的，前面说过，Terrain Patch System包含了12套Patch Map，分别对应从近到远的多级LOD，这些Patch Map都是以相机为中心的，因此可以很容易计算出某个位置的地形对应的是哪级LOD的Terrain Patch Map。
下面看下具体的实施细节。
4.1 Terrain Complexity
Mesh的表达上，JC2使用了一种叫做二分三角树（binary triangle trees，简称BTT）的结构，这种结构从一个等腰垂直三角形出发，通过沿着对角线进行均分来对三角形进行不断细分，从而实现不同区域的密度差异，在这种结构下，一张地图或者一个Patch，只需要两棵树即可完成，下面给出了这个结构的与三角形分割结果的对应关系：
树上的绿色节点表示叶子节点，一个大的三角形通过这些叶子节点可以实现无重叠的完全分割。右边的15位二进制编码是将红色非叶子节点以1表示，绿色叶子节点以0表示，之后按照深度优先遍历输出的。
在Terrain Compiler工具中，会根据地形的拓扑复杂度来创建对应的BTT，地形越复杂，对应的BTT深度越高。此外，除了地形复杂度之外，JC2还增加了一些其他的会对BTT深度产生影响的逻辑，比如JC2希望在海岸线上的地形密度稍微高一些，以取得较为平滑的海岛边缘，就会通过对海岸线进行检测，并据此调整对应的BTT深度。
Terrain Compiler的工作机制给出如下，首先从BTT的根节点出发，对BTT上各个顶点的高度数据与根节点所代表的三角面片的平均高度之差（绝对值）进行累加（这个算法比较粗浅，实际应用时还可以设计更为合理的复杂度统计算法），当这个累加值（应该是累加值平均值）超过一定阈值时就对三角形进行细分，之后对于三角形的子节点进行同样的操作，最终划分完成的三角形就用前面给的深度遍历二进制码来表示，这种表示方法十分的紧凑，但是仅仅只用这些数据还无法完全确定网格的形状（比如朝向），实际上每个Patch分成两个三角形，这是固定的，而划分的方式也是事先约定好的，因此只要有了这个二进制码，就能够表示整个Patch的X/Z方向的数据了。
这里的一个问题是，按照这种存储方法，在运行时会需要从二进制码中将三角形形状恢复出来，不过这个过程因为消耗比较小，且只有加载的时候才需要，所以不会造成不良后果。
在JC1中，地形的高度数据也是同样按照这种紧凑结构来存储的，之后再需要的时候根据planar interpolation来恢复某个triangle的高度图数据，虽然数据存储量小了，但是处理逻辑更为复杂了，而到了JC2，由于不需要支持PS2以及original Xbox了，现在有了更高的存储空间，因此不再需要做如此复杂的处理了。
4.2 Terrain Mesh Resolution
在Terrain Compiler处理完成之后，每个Terrain Patch就对应一个二进制码，而Terrain Patch Map则包含了12个Terrain Patch，因此需要进行12次重复处理，输出了12个代表不同覆盖范围与分辨率的Mesh二进制码，那些覆盖范围小于或者等于Stream Patch（512m）的Mesh二进制码是直接存在Stream Patch中的，会跟随Stream Patch的加载而加载（根据距离相机的远近而决定加载哪级Terrain Patch），而超出Stream Patch尺寸的Terrain Patch二进制码则是存储在全局的Always Loaded结构中。
这里的一个问题是Always Loaded Terrain Patch跟Stream Patch中的Terrain Patch的重叠区域是怎么处理的，两者的衔接又是如何完成的？这两个部分分别在下面的第七章跟第五章有介绍。
5. Geomorphing
经过前面的处理，我们现在有了一套包含12个Terrain Patch Map的Patch System，但是我们在渲染的时候不能直接将12个都一一绘制出来，这样不但效果上会存在问题（重叠、穿插等），性能上也不是最优的。
简单来说，这里需要一套融合算法，用于实现当相机移动时，上一帧所选择的Patch Map与当前选择的Patch Map之间的融合过渡，从而避免跳变的发生。JC2的做法是在PS中对某个blend range之内的地形数据使用alpha blend进行融合（具体做法？），但是这种做法的弊端在于当相邻的Terrain Map具有较大的高度差的话，可能会导致裂缝。
为了解决上述问题，JC2最终采用了一种叫做Geomorphing的做法。简单来说，就是在高模版本跟低模版本交界的地方，对高模版本的顶点高度进行调整，使得交界线上两者的数据完全重合，如下图所示：
不过这个做法的一个问题是，可能会在不同LOD Mesh的交界处导致T-junctions，但是实践中并没有发现过于严重的问题（不是在边缘上平齐了吗，为啥还会有T-junction？同一条边的左右两侧绘制使用顶点数不一致，就会出现T-junction，只是因为这里将高度完全平齐了，因此浮点精度损失导致的T-junction就不会很明显）。
实际上之前设计的BTT结构，使得这个Morph过程十分的方便，如下图所示，高分辨率版本的Terrain Patch（Child Patch）与低分辨率版本的Terrain Patch（Parent Patch）本身是有共用节点的，而Parent Patch与相邻的低分辨率版本的Terrain Patch是吻合的（从目前的信息来看，除非是整个地图统一分割，不然还无法做到单个Patch与相邻Patch在边缘上的完全吻合），在这种情况下，只要Child Patch与Parent Patch在分歧点上的顶点高度保持一致即可，也就是下图中的黄色节点上，将两者的高度调整为为一致。
6. Vertex and Index Buffer Generation
生成Terrain Patch的二进制码之后，在运行时需要根据需要构造还原出原始Mesh的VB&IB，这个过程比较简单，就是当某个Terrain Patch需要构造时，会向其从属的Stream Patch查询这个Terrain Patch的二进制码数据以及其Parent Patch的二进制码数据，Parent Patch的数据是用于实现此前说过的Geomorphing使用，这里需要处理的一个问题是，Parent Patch覆盖了四个不同的Terrain Patch，需要费点心思来判定当前需要加载的Terrain Patch是对应于Parent的哪个Child，下面给出实现伪代码：
7. Partially Overlapping Patches
由于存在多级Terrain Patch Map，而每级Patch Map都是以相机为中心创建的，这就会使得一些Patch可以完全被其Child Patch覆盖，而一些Patch则完全没有对应可见的Child Patch，此外还有一些Patch只有部分区域被可见Child Patch覆盖。
对于完全被Child Patch覆盖以及完全没有被Child Patch覆盖的情况，处理起来都比较简单，直接放弃Parent Patch或者Child Patch的绘制即可，而对于部分覆盖的Patch处理起来就稍微麻烦一点，简单来说就是对于这种情况而言，我们需要对Patch拆成四个部分来绘制，每个部分根据是否被Child Patch覆盖来采用不同的绘制方案，这个过程是通过对Index Buffer按照四分方式组织（将整个Patch的Index Buffer按照深度优先算法进行存储，之后给出每个子部分的起始索引）来完成的。
8. Conclusion
JC2的地形方案经过验证在众多的硬件上都有着不错的表现，这是雪崩工作室多年开发迭代的结果，这里对上面的工作做一个总结，地形渲染通常需要处理的数据可以大致分成地形模型与地形着色两块，前者对应的是地形mesh的构建，后者对应的则是地形贴图与材质。
地形mesh方面，JC2的地形方案使用的是12级不同不同覆盖范围（相邻两级覆盖范围翻倍）的Terrain Patch Map组成，覆盖范围从64 m x 64 m到256 km x 256 km，多级Patch Map之间的融合是通过Geomorphing算法实现，而被多级Patch Map覆盖的位置，则会选择分辨率最高的一级进行绘制，这个处理过程的核心为Patch按照Index Buffer四分组织，Parent Patch与Child Patch重合的部分直接使用Child Patch部分，其余部分则使用Parent Patch数据。通过这种方式可以完成2D Terrain Grid的构建，而地形高度则是通过Height Map完成，虽然没有详细介绍，不过推测不同覆盖范围的Terrain Patch Map应该是可以共用同一张Height Map的，这样在边缘处才可以完美衔接上。
地形材质与贴图方面，每个地形采样点（顶点）上可以装载4套材质（从Material Index Map的格式ARGB4444推测），同时使用四个不同的权重来进行混合，Material Map与Weight Map的分辨率都是4m/texel（比如128 x 128的贴图，覆盖了512m x 512m的地图范围？），看起来虽然很低，但是在Tiling的作用下结合不同的Tiling位置使用不同的Weight Map/ Material Map也可以达到不错的效果。
参考文献
[1] Sponsored: The World of Just Cause 2 - Using Creative Technology to Build Huge Open Landscapes
