前段时间，有几个虚拟仿真公司跟我请教关于大地形的加载优化问题，它们使用的引擎都是自己研发的，引擎对于开发者来说，大同小异，它们的基本构造是一样的，关键是在于解决问题的方法，正是基于这个前提写了这个课程，希望给读者提供一些解决问题的思路。
目前，大地形动态加载已经成为当前游戏开发或者虚拟仿真领域必须要解决的问题，尤其在虚拟军事仿真领域，由于要涉及到大兵团虚拟演练作战，这对仿真真实性要求比较高，需要根据真实地形数据将其在终端硬件设备上绘制出来，或者是通过美术人员利用建模工具制作大地形，比较流行的做法是利用航拍拍摄城市或者山区地形生成高度图，利用现有的技术按照一定的比例还原城市和山区地形原貌，生成的大地形大部分是上千公里区域，面对这么庞大的数据，由于硬件的限制，需要程序做对地形的加载做一些优化操作，以解决运行效率问题。
该课程主要是提供了大地形动态数据的加载及优化方案，因为在虚拟仿真以及游戏开发中都会涉及到海量数据的加载，由于内存的限制，不可能直接将大地形一次性的加载到内存中，即使硬件满足了需求，除了地形还有其他道具的加载，这样会对内存带来严重的负载问题。解决大地形加载方案：首先想到的做法是将大地形进行分块加载，单单的分块加载并不能完全解决实际问题，比如在飞行仿真中，由于角色飞行速度快，会导致加载地形块不完整的情况出现，当然也会出现程序运行卡顿情况，还有一种情况，角色在场景中做移动操作，如果角色在块与块边界附近不停的旋转视角或者是来回移动，这样也会导致地形频繁的加载卸载，同样会出现地形加载问题，体验非常不好。另外，大地形上面的建筑物非常密集，它们也会随地形加载到内存中，这些建筑物也要进行分块以及遮挡处理的；除了地形和建筑物模型数据，贴图的加载和渲染也是需要解决的问题。大地形以及建筑物二者都会涉及到大量贴图的加载，贴图的加载也会吃掉大量内存的，如何把这么多贴图加载到内存中？以上种种问题，该课程给出了解决问题的答案。下面我们把本篇课程涉及的主要技术给读者介绍一下，后续章节会详细给读者讲解，下面先从大地形数据加载方案说起。
大地形数据加载方案
大地形加载考虑到现有的内存机制， 不可能一次性将其加入到内存中，这个问题是显而易见的，其实在游戏开发中经常遇到，比如我们常见的进度条，加载进度条的目的就是等待程序加载场景，进度条只是一个蒙板遮罩而已。大地形的加载，别无他法，只能用分块，这个是大方向，因此作为程序来说，要做的事情是如何分块？块的大小是多少？这些具体的问题我们要根据需求划分，比如飞行模拟器块大小可能就要大一些，因为俯瞰的视角比较大，场景漫游块可以小一些等等，下面我们就以游戏的经典之作——魔兽世界地形加载方案为例给读者先介绍一下它的实现原理，魔兽世界这款游戏实现的就是无缝地图的拼接，所以非常具有参考价值，先看下图所示：
魔兽世界是如何实现无限地图的？其实它也是很多的场景块拼接而成的，我们通过编辑器分析魔兽世界的地形块的大小划分，魔兽世界场景我们称为MapWorld是由一系列MapTile组成，这些MapTile的大小是1600/3 ≈ 533.33m，而每个MapTile又是由 16x16 个MapChunk组成，由此可以计算出每个MapChunk≈33.33m。再就是每个MapChunk又由9x9＋8x8个地形顶点高度，法线，若干贴图层（一般为4层）组成的地表纹理。魔兽世界地形的大小，在这里我们就不讨论了，但它划分块的思想我们是可以借鉴的。
继续分析魔兽世界的分块方法：它们是根据矩阵的方式进行划分的，在XZ平面上进行的，每个块都会包含一定的信息数据的，比如：在XZ（3，3）位置的MapTile，每个MapTile都包含了该tile内使用的贴图、模型实例等等。所谓模型实例也就是我们的道具，可以理解成相同模型在tile内不同摆放位置、大小、角度的信息，它们都是被保存在二进制文件中的，为了节省文件尺寸，模式实例是通过index模型方式保存的，同顶点索引类似，在每个MapTile里面还有贴图信息比如贴图的名字和UV信息等等。本篇课程的分块思维方式跟魔兽世界的类似，会在后面的章节中详细介绍，块分好了以后，下面就是实现原理了。
实现原理：在任何时刻，程序总是保存着玩家所在的及其周围的3x3个MapTile，随着玩家的移动，这些MapTile会被动态更新，新的MapTile被加载以替换被卸载的旧MapTile。为了提高调度效率，魔兽引入了Cache机制，Cache中保存着最多16个MapTile数据。需要加载新的MapTile时，首先会在Cache中查找；卸载的旧MapTile也不会被立刻删除，而是保存在Cache中以备再次调用。由于一段时间内玩家的活动范围通常不会有太大变化，这一Cache策略在应用中表现的非常出色，这是无缝地图的基本原理。地形的动态加载卸载我们会使用多线程去实现，我们会整两个线程：一个线程专门用于加载地形，另一个线程专门用于卸载或隐藏地形MapTile。让我们再来回忆一下游戏的经典之作，游戏场景效果如下所示：
本篇课程实现的方法可以使用两种方式处理块的加载显示问题，一种是利用对象池的方式，预先加载分块地形，根据视距进行检测判断显示那些地块以及隐藏那些地块，在这里并不删掉它们。这样只需要一个线程就可以。另一种方式是利用多线程，起一个线程专门用于移除卸载不在视线范围内的地块，这样可以提升效率，下面介绍使用多线程的加载方案。多线程实现大地形加载方案
多线程在PC端游戏中使用的比较多，比如可以起一个线程专门进行资源的加载，游戏服务器中同样也会有多线程的使用，下面给读者介绍多线程实现方案，多线程处理问题就是把所有的加载逻辑放到了新的进程中，和主线程做一些进程间的通信，接受主线程的加载建议，做按需加载，也会自主做一些提前预加载，放进分配的内存，就跟魔兽世界的处理方式一样，通过进程间的内存共享机制，把加载的地形数据，共享给主进程使用。主游戏进程，永远只要维护一个很小的内存即可，大量的内存数据，都在另一个进程中处理。这样就可以优化大地形块的加载，实现方式如下所示：
首先主线程会先加载九块地形，主线程只负责维护这九块地形，无论角色怎么移动，角色所在的整个区域永远是九块地形，如上图所示的，这九块可以直接使用主线程加载到内存中，剩下的16块我们通过另一个线程将其放到缓存中，角色的位置是在已经加载好的九块地形中间，也就是在A所在的位置。随着角色的移动，会有新的地形块加入进来，同时现有的地形块会被置换出去，这样一直显示九块地形，被置换的地形并不会马上卸载掉，会根据角色移动情况做预判，它会等主线程通知，按照一定的规则进行卸载地块和加载地块。其实这种实现方式就是我们通常所说的双缓存-多线程技术。实现的效果如下所示：
地形分块加载完事了后，下面就要考虑地形上面的纹理贴图问题了，地形的贴图资源也会占用大的内存，下面介绍如何加载海量贴图数据。
大地形海量图片的加载方案
大地形中的场景图片非常多，地形中的贴图至少会有四层，这么多贴图我们在加载时需要考虑的，我们分块时也需要考虑这些因素，另外场景中使用的LightMap烘培也是要考虑的问题，为了缓解内存压力，我们事先会将不同块中的地形材质以及建筑物材质进行打包，先介绍如何分块加载场景贴图？它实现方式如下所示：
该思路就是将场景中的贴图根据我们划分的块打成不同的图集，当然也可以将两个块中的贴图打成一个图集，图集大小对于PC端来说，最大是4096，在移动端最大是2048。这个也是为了避免内存频繁的加载卸载会导致很多内存碎片，不利于后面大内存的分配。在打图集之前我们需要做点事情就是需要将地形块中的纹理贴图与我们的打包图集之间建立一一对应关系，方便对号入座。因为我们打包的图集跟实际地形之间不会有任何关系，要确立二者之间的对应关系我们需要在它们中间再整一张索引文件表格，它是连接图集与实际地形纹理的桥梁，通过我们建的索引文件，我们可以找到实际地形中纹理与图集纹理之间的对应关系，我们建的索引表格是要加载到内存中的，而我们的图集是根据加载任务后期才加到内存中的，这就要求我们的索引文件尽可能的少，因为它们是常驻内存的，除了海量图片的加载，我们还需要处理密集建筑的加载。- 密集建筑的加载方案
密集的建筑加载，大家试想一下，如果把场景中所有的建筑一次性加载到内存中，内存瞬间就会占满，帧数瞬间下降，这也是为什么大家在游戏场景中移动时，遇到密集的建筑就会卡顿一下的原因。以前处理方式是使用LOD处理，被遮挡的物体使用简模，这样也会加大内存的负载效果，如果角色一直在建筑物之间来回穿梭，这样不同LOD模型就需要来回切换，对内存也是一个负担，效果不理想。这些问题对于程序员面来说必须解决的问题，如何解决呢？很多人想到了合并大Mesh，这种方法行不通的，大网格并不适合做裁剪操作，试想一下，我们合并的网格，如果摄像机只看其一小部分，因为它们是一个整体这样就需要把他们一起加载到内存中，而实际上我们并不需要这么多模型数据，在合并网格时，在这里也给读者一个建议，尽量把靠的很近的模型进行合并，避免上述问题发生。其实最有效解决方案还是划分块，这个划分块可以利用地形划分的思想进行，它是与地形块紧密相关的，每个地形块中的建筑物跟随地形块一起加载。如果块中的建筑非常密集，这种方法还不能够完全解决，还需要进一步的处理，就是要加入OC遮挡算法结合LOD算法，这样就可以完全解决我们当前的问题了，这也是本篇课程
要讲解的方法，再进一步的优化方法是可以将OC遮挡算法和LOD算法放到GPU中计算，这样效率还会提升，在Siggraph2015发表了一篇文章GPU-Driven Rendering Pipelines，它的思想就是使用GPU进行遮挡裁剪处理，主要分两个阶段，使用的是DX12图形API，如下图所示：
它的思想就是第一步先做一个初略的遮挡裁剪列表，而后在此基础上再根据视线距离或者射线检测做进一步的细化裁剪操作，这个思想跟我们的碰撞检测算法类似，引擎中碰撞检测算法也是基于这个原理实现的，给读者介绍一下：实际可用的碰撞检测算法，一般要分2个阶段：
第一阶段，broad phase 快速找出潜在的碰撞物体对列表，不在这个列表里的是绝对没可能碰撞的。broad phase确定了一批需要进一步检查的物体对。
第二阶段，narrow phase 准确找出发生碰撞的物体对列表。因为上一个阶段的部分物体对实际上是没有碰撞的，需要在这个阶段剔除。
broad phase其中有一个简单算法叫sweep and prune(SAP)，本质上是利用了排序算法。第一步是初始化排序列表，列表中的元素是包围盒，可以用任意排序算法完成，例如快排；之后的排序就不是用快排了，而是用冒泡排序，为什么用冒泡排序更好呢？是因为一个默认的前提：物体的运动有时间相关性（temporal coherence），即当前帧和下一帧的位置是相近的，所以在冒泡排序过程中，发生的位置交换预期都很靠近。
其实算法中有很多类似的地方，这里我们也要互相借鉴它们解决问题的思想用于解决我们的问题。笔者以前做的是端游，端游中很多优化思想同样适用于移动端，移动端跟PC端比，就是一台配置比较低的电脑而已。接着我们的遮挡裁剪继续给读者介绍，论文作者也做了一个效率测试，以250’000物体，1G的网格为例，测试效果如下所示：
是不是很酷啊！在项目开发中完全可以用它解决问题，下面我们再谈谈使用GPU去优化我们的大地形场景。
GPU大地形渲染优化解决方案
我们的大地形首先会有自己的地表贴图，常用的地表贴图是四张纹理融合，最多可以有八张贴图融合，地形纹理渲染会涉及到LOD算法，远处的地形网格可以简化一些，对应的贴图也是最低的，这就是MipMap的使用。另外肯定有草有花以及其他大量相同的物件渲染，先说说草和花的绘制，他们在游戏中会非常的多，常用的做法是引擎提供的面片或者是十字交叉，或者三张图片交叉，然后将带有Alpha通道的贴图映射在上面，如下图所示效果：
CPU绘制这些草或者花在PC端是可以的，因为现在的电脑都是多核的，在手机端就会影响到效率问题了。使用CPU绘制，DrawCall会非常的多，而且草或者花还需要摆动，计算量很大的，这严重影响了运行效率，CPU有难，GPU可以帮忙，我们可以将草或者花的绘制放到GPU中执行，效果如下所示：
这些草的绘制都是在GPU中进行的，游戏中花的绘制原理跟草的绘制是类似的。它们的制作并不是美术建模的草或者花而是程序自定义生成Mesh，然后在Mesh上面加上贴图进行渲染处理的，从而降低DrawCall，GPU使用的是几何着色器，DX10图形API使用的就是几何着色器。对于其他相同物件的绘制，我们可以使用GPU Instancing优化处理，除了处理批量物体外，我们还会使用GPU进行材质渲染以及处理角色动画蒙皮等等。如下图模型材质渲染效果所示：
除了这些渲染外，我们还需要针对场景的后处理渲染，Bloom，Blur，SSAO，HDR等等常用后处理渲染。下面给读者展示一个体积光渲染，效果如下所示：
图片来源：https://zhuanlan.zhihu.com/p/39754801
这样渲染的效果让场景更加逼真形象，GPU能帮助我们处理很多事情，这里就不一一列举了。- 总结
本篇课程主要目的是解决大地形数据加载和密集建筑物加载优化问题，本篇课程主要会从以上几方面结合着案例给读者进行讲解，希望通过本篇课程的学习能够给读者提供一些解决问题的思路，做到举一反三。不同的项目需求是不同的，但是遇到的问题都差不多，随着硬件的提升，算法的改进，在大地形的效率运行方面还会有质的提升。
