四叉树切分#

为了解决面数问题，我们采用了四叉树作为地形 Mesh 的组织方式。四叉树可以理解为二叉树在二维空间的扩展，每个节点拥有四个子节点，常用做二维空间的切分，如下图所示。

具体实现过程，是以整个地形作为四叉树的根节点，按照当前节点到相机的距离来决定是否继续划分，如果需要，则会划分为四个相同大小的子节点，重复迭代划分直到叶子节点为止，叶子节点的大小可以自由定义，比如 16 米、64 米等。所有的节点都对应了一块相同大小的 Mesh，也就是说，父节点的面积是子节点的四倍，但是 Mesh 面数是相同的。 如下图所示，绿色三角是玩家视角的可视范围，地形以玩家位置为中心进行四叉树划分，离玩家距离越近的节点，精度就越高。最后经过视锥裁剪，渲染可见范围内的节点，也就是图中的蓝色节点。

下图是一个大小为 4km*4km 的地形，我们在场景中放置了一个相机，并以该相机作为玩家位置加载地形。为了观察方便，我们拉高了编辑器视角，并分别以 Local UV 和 Wireframe 模式输出。结合这两张图能够清楚的看到，离相机越近的节点面积越小，网格精度也越高。

该视角下的地形面数为 20.8W 面，Draw Call 数为 26，这个数据已经基本在一个可接受的范围内。通过四叉树结构，我们已经有效的控制了地形的面数和 Draw Call 数，接下来会通过一些方法继续优化相关数据。

减面算法#

在实际的地形中，除了陡峭的山区，大多数区域都以平原和丘陵为主，这些区域的高度变化相对平缓，使用均匀网格是比较浪费的。因此我们采用了一套运行时动态减面的方案，在几乎不损失地形精度的前提下，达到了减少地形面数的目的。 我们创建了一个大小为 64m*64m、坡度较为平缓的地形，然后分别测试了关闭和开启减面时的面数。下图左侧为原地形，右侧为开启减面前后的 Mesh 对比。开启减面前需要 8.2K 面，开启减面后是 6.1K 面，减少了约 25% 的面数消耗。

这里简单介绍一下减面算法。 首先根据高度图可以计算出所有顶点的法线方向，然后合并顶点法线差值小于阈值的顶点。合并过程可以理解为四叉树切分的逆过程，以相邻的四个顶点为一组判断是否可以合并，递归处理直到不能合并为止。合并完成后，每个被合并的顶点组对应一个 quad，最后对 quad 进行三角化，这个过程主要是进行缝边的处理。

该减面算法相比一些离线减面算法，复杂度要低很多，但仍然是存在一定消耗，我们目前是放到了 Background 线程中去计算，不会造成游戏卡顿，只是会略微提升耗电量。

裂缝问题#

在不同等级的四叉树节点之间，由于 Mesh 分辨率不一样，会带来裂缝的问题（见下图）。由于我们是在 CPU 预先计算高度生成的 Mesh，所以也无法通过在 Shader 中进行 Morph 来解决。

我们的解决方案是在四叉树更新完成后，计算每个节点与周围节点的 LOD 差值，然后删除可能产生裂缝的顶点并更新 Index Buffer。下图展示了如何处理一级和二级 LOD 差值。

考虑到在处理裂缝的同时，还要对 Mesh 进行减面，所以我们将 Mesh 分成了五个部分，中间部分和四条边，中间部分采用减面算法生成，四条边则根据相邻节点 LOD 级差生成，这五个部分共用相同的 Vertex Buffer 和 Index Buffer，所以仍然是一个 Draw Call 去绘制。 通常四叉树相邻节点之间的级差不会超过三级，所以我们只处理三级以内的缝边。我们对这几种边的 Index Buffer 进行了预生成，在生成节点 Index Buffer 的时候直接拷贝到中间部分的 Index Buffer 后面即可，效率很高。

Mesh LOD#

四叉树中，不同级别节点之间的精度差为 2 倍，这会导致在边界处产生比较明显的精度变化，为了缓解该问题，我们在两级 LOD 之间，插入了 Mesh 级别的 LOD，如下图所示。除了平滑 LOD 精度外，也会减少地形的面数，LOD 0 一个 2x2 的 quad，会由原本 8 个面会减少到 4 个面，减少了一半。

下图为同等级 LOD 节点不同 Mesh LOD，左侧为 6.1K 面，右侧为 3.7K 面，相比减少了 40% 左右。

现在再回顾一下前面的 4K 场景，对比优化前面的 Mesh，经过一系列的优化，相同视角的面数从之前的 20.8W 面，下降到了 8.8W 面，减少了 60%。另外，我们还可以通过对参数的修改，在地形精细度和性能之间去做出调整，选择进一步降低面数和 Draw Call 以减少消耗，或者提升面数和 Draw Call 以提升效果。

地表层与权重图#

首先需要准备多组地表贴图，涵盖所有要用到地表类型，比如草地、雪地、沙地等等，每组地表贴图包括了 Albedo 贴图、法线贴图、粗糙度贴图、AO 贴图和高度贴图，这些贴图必须是四方连续的。

权重图来用于表示每种地表在所有位置的混合比例。每个地表类型需要对应一张权重图，权重图一般是 8bit 的，这样一张 R8G8B8A8 的贴图就可以表示四种地表类型的混合。以下图为例，一共添加了两层地表，第一层泥地使用了权重图的 R 通道，第二层草地使用了权重图的 G 通道。

然而，当地形大了之后，这种方式的弊端就会显现出来。假设地形的大小是 4km*4km，混合贴图精度 1pixel/m，当使用 16 种地表时，一共需要 4 张 4096 的贴图，这在性能上是不可接受的。

权重图优化#

我们可以观察一下正当防卫4的地图，虽然它的生态类型很丰富，包含了沙漠、雪山、雨林等等，但每种生态都只会覆盖某一区域，比如雪地这层地表，只会在雪山上出现，其他区域的权重都是 0，这显然是对贴图的浪费。结合我们前面的 Mesh 策略，很容易想到将权重图进行切分，每块 Mesh 对应单独的权重贴图。

我们先看一下堡垒之夜采用的方案，其使用的是 UE4 引擎，会将地图切分成地块，每个地块都有单独的权重贴图。在切分之后，每个地块约有 5 到 9 层地表类型混合，对比之前的方案，已经大大减少了权重贴图的大小，但对于移动端来说，这个混合层数还是太多了。因此堡垒之夜在移动端上进行了优化，每个地块尽量控制在 4 层之内，通过牺牲效果来保障性能。

除了效果牺牲外，因为每个地块的面积比较大，地表控制在 4 层之内还会给美术制作带来比较大的限制。对此我们进行了改进，采用了一张全局索引贴图，索引贴图的每个像素对应一个较小的面积，比如 8m8m、4m4m 等，像素编码了该区域使用了哪几层地表。 如下图所示，使用了一张 8x8 的 IndexMap 和一张 64x64 的权重图，实现了在 64m*64m 地块上混合 6 层地表的效果。因为权重和为 1，也就是 sum(r,b,g,a)=1，所以 a 通道可以被舍弃掉。权重图只使用了三个通道就表示六层地表的权重，大大减少了权重图贴图大小。

同时，我们也会为四叉树的所有 LOD 节点都生成混合贴图，每个父节点的混合贴图都可以由子节点合并得到。基于远处地块的屏占比较低的原理，权重图在较低等级的 LOD 地块上，也会与 Mesh 一样降低分辨率，减少贴图大小。 在原始的方案中，4K 地图 16 层地表需要 4 张 4096 的贴图，未压缩大小达到了 256M。而在用了权重图优化后，4K 地图的权重图累计共 84M，压缩后只需要约 20M，并且由于实际渲染时只会加载小部分地块，实际加载的内存还要少很多。

去重复感算法#

下图是和平精英中的截图，可以看到，地表有比较明显的重复感，尤其是在跳伞视角。这是因为地表通常是将贴图以 Repeat 的方式平铺在地形上来实现的，受限于贴图精度，一般几米就会重复一次。

为了解决重复感问题，我们参考了 SIGGRAPH 2018 上一篇 Paper 中的算法，称为 ByExample Noise。篇幅原因这里只介绍一下算法的基本思想，对算法原理感兴趣的同学可以阅读一下原 Paper。该算法利用了随机采样的思想，将贴图在 UV 空间进行三角划分，然后随机寻找三个三角形，采样对应区域的颜色进行混合，特别的权重设计保证了混合后权重和仍然为 1。

混合操作会使目标贴图的方差降低，反应在结果上就是混合后的贴图比原图模糊。Paper 中为了解决该问题，提出了基于直方图来恢复方差的算法，但这种算法需要预生成映射贴图，并在采样时使用 LUT 转换，这会带来额外的消耗。综合对比之后，我们还是使用了没有 LUT 的版本，在地表贴图这种特征不明显的贴图上，带来的模糊不会很明显，下图是几个示例。

左边是简单 Tiling，重复感明显，右边加入了 By-Example Noise，重复感已经非常低。 我们将地形分为了独占局域和混合区域，独占区域指的是当前区域只存在一层地表，混合区域则是有多层地表混合而成。ByExample Noise 只会在独占区域使用，这是因为重复感主要出现在独占区域，而混合区域由于多层地表叠加，并不会有明显的重复感。还有一个原因是这样不会带来额外的消耗，Shader 中会进行判断，在独占区域采样相同层三次进行混合去重复感，混合区域则是正常采样四层不同地表进行混合。 下图是实际应用到地形后的对比，可以看到左侧重复感明显，而右侧使用了 ByExample Noise 之后，已经几乎感觉不到重复感。

基于高度的混合#

上面在地表材质混合的章节中提到，地形通常会采用权重图去进行多层地表的混合，这种方式比较直接，但也会带来一些问题。 首先权重图是有精度限制的，假如权重图的 1 个像素对应 1 米，那也就是说不同地表之间至少需要 1 米的过渡带，如果美术想表示更硬的地表边缘，就需要提高权重图的精度，带来额外的消耗。第二个问题就是这种混合方式在现实世界中往往是错误的，比如说现实中沙石路，并不是石子和沙地按权重去混合，而是石子中嵌在沙地中，这种效果只通过权重混合是无法实现的。

为了解决这个问题，我们在权重混合的基础上，加入了高度混合，每种地表需要额外提供一张高度图，在混合时和权重图加权后计算最终的混合比例。下图中，左侧只使用了权重混合，右侧则加入了高度混合，基本上实现了上面提到的石子嵌在沙地中的效果，真实感有了很大提升。