作者：顾露


　　一、程序技术篇：算法和架构（Programming Algorithms Architecture）

　　1. 无限循环的平铺地图（Infinite Tiling）

　　我们就从最平淡无奇的无限循环平铺地图说起吧。这应该是最原始，也是最没有技术含量的开放世界构筑方式了。

　　技术上由于过于朴素，也没什么好说的，就是在同一个坐标系内像铺地砖那样展开，坐标对齐即可，就是接头处需要注意一下，不要穿帮就行。但是千万别因为简单就小看这个技术哟，上面列表里面的不少技术都是在循环平铺的基础上发展起来的，下面我们就来瞧一瞧吧。

　　按照维度的不同，循环平铺有下面三大类：

　　a. 在一维方向上扩展的横版卷轴游戏（以动作类游戏为主）和纵版卷轴游戏（以射击类游戏为主）。这些类型的游戏里，为了避免循环平铺给玩家带来的重复的疲劳，卷轴游戏会添加一些随机或动态的元素，比如超级玛丽里的背景上云朵的位置，分出多个层次以不同速率卷动的背景层，等等。

　　这是俺刚刚到老硬盘里刨出来的大三时写的 GeoMipMapping 代码，编了一下居然还能跑起来。有点土，别介意：P 可以看到不同的 MipMap 级别是用不同的颜色渲染的，也可以看到接头处 T 型裂缝的处理。唉，这代码勾起了俺的青葱回忆啊，那就顺便再来两张 T 型裂缝的示意图和消除过程吧。


　　Progressive Mesh 是后来很流行的技术 Simplygon 的前身，原理上基本也是一致的，就是以某种方式渐变性地化简某个给定的 Mesh。

　　渐进式网格有两种：视点无关的 （View-Independent Progressive Mesh，VIPM） 和视点相关的 （View-Dependent Progressive Mesh，VDPM）。两者的区别就是，前者预先离线生成好所有的渐变过程，运行时直接用就行（也是后来 Simplygon 采用的方案），而后者随着摄像机的位置和角度的变化，生成对应的简化模型。两相对比，VIPM的好处是运行时运算开销低，简化模型的效果好，缺点是费内存（因为数据都存下来了，当然后来增量的方式能省一些），而VDPM在当时是不错的选择，因为跟VIPM相比不用费额外的内存，而且对于视点（就是摄像机）变化不剧烈的应用，不需要每帧处理和更新对应的简化模型（普通的MMO类的一般一秒一次就够了），此外由于一些简单的遮挡剔除和背面剔除，能够比VIPM裁掉多得多的顶点（一般能多裁1/3到一半吧，在当时这可是头等大事）。

　　总的来说，至少在当时，两者的应用都比较广泛，而到了后来，显存越来越大，总线却越来越紧张，VDPM这种典型的刷顶点的算法（比较费总线带宽）就逐渐失去了市场，这是后话了。

　　大家可以在这里看到一些 PM 在地形渲染上的应用。图咱就不上了，大家可以到 Simplygon 的网站上去看。

　　ROAM 可算作是上面提到的 VDPM 更进一步了。这个算法实际上借鉴了当时主流引擎的标配BSP的思路，想利用二叉树这个最简洁的空间描述数据结构，把（CPU端的）顶点消减发挥到极致。整个地表被组织成一个巨大的二叉树，有两个队列，一个是分割队列，一个是合并队列，分别用于处理摄像机移动时，增加进入视野的区域细节和消减退出视野的区域细节。精心设计的 ROAM 效果非常华丽（尤其是在线框模式下），你会看到在各种因素的影响（包括局部坡度，与摄像机的夹角，遮挡情况等等）下，各种三角形像魔术般的不断地变幻，生成和擦除超多的细节，效果非常魔幻。我印象很深的是当时连续打Quake3两个小时完全无感的我，调试这玩意的时候，每每不到十分钟眼就花了。

　　网上找了两张比较典型的 ROAM 大家感受一下吧。



　　4.2 层次的艺术（Quadtree 和 Chunked LOD）

　　其实用于空间管理的树状结构有四叉树和八叉树（还有上面的二叉树），但地表通常以前者居多。是因为，从小范围来看，变化剧烈的地形是3D的，适合八叉树在xyz三个方向上扩展；但当尺度大到一定规模之后，地形通常退化为相对扁平的2D空间，就像摊平了的地球表面那样，在竖直的Z方向上变化相对不大，而XY平面则是可能无限延伸的。

　　Quadtree 四叉树很直白，具体的细节我就不讲了。值得一提的是四叉树往往也同时用于场景管理的快速剔除和查找，从理论上来讲，四叉树是一个平面上最迅速的用于剔除空间，定位一个物体，内存开销也是相对较低的数据结构。当用于地形渲染时，顶点剔除的效率也很高，我印象中仅次于高度优化的 ROAM。内存开销低主要是因为四叉树是可以完美展开到一个位数组里的，这样的话意味着整个树的利用率达到了百分之百——所有的空间都用来存储数据而不是维持结构。

　　不过四叉树也不是啥都好，T型裂缝就比 GeoMipMapping 难处理，因为存在跨级的多段 T 缝，如下图：


　　除此之外还有一些细节问题，这里就不一一说明了，地形的四叉树渲染还是有很多细节需要细心处理的，此处暂且放下不表。

　　Chunked LOD 是一种杂合改良的 LOD，其实糅合了上面说的不少细节，本质上是一种分区块地消减细节的技术。所谓 Chunk 是批量处理的一种方式，只是一种粒度划分的单位而已，跟现在 Java 的 GC 里分区回收概念上差不多。

　　下面是典型的 Chunked LOD 后的效果：


　　顶点多次过滤优化后的效果：


　　效果在当时还是很惊艳的。通常不到50k的渲染数据量已经能有非常逼真的效果了。

　　4.3 以GPU为主的技术（从 Paging，Clipmap 到 GPU Terrain）

　　上面的基本上都是传统方案，这一节我们将逐渐过渡并挨个介绍一下以 GPU 为运算主体的算法。

　　所谓分页（Paging）实际上是仿效虚拟内存的运行机制的一种方法。由于地表的顶点数据都是静态数据，适合常驻显存。当世界尺度较大时，显存没法一次放入所有数据，那么系统就像虚拟内存那样，把那些暂时没有用到的数据交换出去。随着游戏的进行，Paging In/Out 也在不断进行，辅以一定的异步机制，加载到显存的延迟可以被很好地掩盖。玩家的直观感受就是：哇，海量的细节。


　　而 Clipmap 则比 Paging 更进一步，以金字塔的形式逐级把数据排列好，直接整体更新和渲染。从这里也可以看出 GPU 时代人们的思维方式的逐步变迁。从以前顶点级别（Vertex Level）的“锱铢必较”，到后来的一次多塞一点也无所谓，只要批次（Batch）少就 OK。下图可以看出 Clipmap 的基本思路。


　　所谓的 GPU Terrain Rendering 就是把高度图从内存里经由 2D Vertex Texture 搬到 VS 里去生成三角面，这样的好处是 CPU 和内存就被彻底解放出来了。只是访问上有一些限制，不像直接处理内存那样方便。具体的细节可以看这里：GPU Gems 2: Terrain Rendering Using GPU-Based Geometry Clipmaps

　　在 GPU 上做还有个巨大的好处是可以借助 Gaussian Noise 即时生成更多的细节了。直接拿一小块预生成的高斯噪点图在需要的时候叠加一下，就能在没太大额外开销的情况下，增加各种细节。如下图所示：


　　随着大家对 GPU 理解的深入，地形的处理又有很多的小技巧可以做，尤其是在 PS 里面，比如法线生成，动态uv展开，光照按需叠加/衰减什么的。不过呢据我所知没有什么非常别具一格的架构上的新思路了，所以就不再深入了。

　　5. id tech 5 的 megatexture （超大地表上的非重复性海量贴图）

　　megatexture 在当年（2007）是一个非常值得一提的技术。在这个技术出现之前，几乎所有的地表渲染用到的贴图都是若干张 blend 到一起后，以 tiling 的形式重复平铺在地表上的（包括比较典型的魔兽世界也是如此），这样的直接后果是图片的种类用多了耗资源，用少了又很容易感到单调和重复。而 megatexture 则是一张全局的超大贴图，从根本上避免了重复这个问题，理论上（实践上也是）能够生成非常壮丽和独特的地质风貌，是传统的刷地表无法创作出的效果。可以说这个技术让真正的全景地貌成为可能。

　　技术上的细节puzzy老师写过一个 pdf，强烈推荐感兴趣的同学搜来看一下（可以搜“ ID Tech 5 中Megatexture针对地形的D3D9 基本实现原理 - 姚勇”），珠玉在前，我就不啰嗦了。就来一张效果图吧（好吧我知道能坚持看到这儿的同学，这图基本上肯定都看过了）


　　全局超大贴图对一个开放性世界的价值不言而喻。想象一下，跟拿乐高积木拼接出来的视觉效果（传统的 texture blending and tiling）相比，一幅万米画卷上，每个像素都可以随意描绘，是一种什么感受。 比如，你可以相对轻松地实现“整个世界的地貌瞬间被密集核弹蹂躏了一场之后”的效果。如果你想模拟整个生态环境的变迁，在不同粒度上的整体性修改更是无价之宝。

　　6. 过程式的内容 （Procedural Content Generation）

　　“过程式生成”是一个不是很恰当的翻译，实际上更贴近本意的说法是“以程序的手段生成”，这里我们简洁起见，仍使用过程式生成的字样吧。

　　过程式的内容生成是随机技术的在视觉效果上的一个重要衍生。这个技术虽然到最近才被广泛应用，但实际上从技术角度讲，在很久以前就已经有比较成熟的实现了。我手头的 2003 年出版的翻译版 Game Programming Gems III 中 就有 4.16 和 4.17 连续两篇文章以“程序手段生成的纹理”作为主题。这是构建超大规模的世界的一个重要的技术工具，尤其是与上面的 megatexture 技术结合起来，可以创造出非常令人震撼的视觉复杂度。

　　下面是 sourceforge 上一个开源的项目 PCity - Procedural Modeling and Rendering of Cities


　　可以看出，对于过程式生成来讲，只要有非常小的初始数据集（meta-data），可以在宏观上达到很大尺度和复杂度的视觉效果。

　　过程式生成有两大分支，一个是过程式纹理，另一个是过程式建模（上面的 PCity 属于后者），下面我们分别来谈一谈。

　　6.1 过程式纹理（Procedural Texturing）

　　人们发现，自然界中有很多视觉效果是可以用数学公式加上一些简单的随机性来模拟的，比如云彩，水流，火焰，木纹，大理石，草地，夜空，大气等等，程序生成的纹理效果大大丰富了普通纹理能表现的效果，就好像是物理引擎给游戏增加了活力一样。一个普通的噪点图，在不同的情境下，作为辅助参数来参与生成动态纹理，可以产生出近乎无穷无尽的变化。

　　这是过程式生成的云，出处在这里。


　　这里是一些分解材质，相当于过程式纹理的图素，出处在这里。


　　截图中的素材基本上都是使用了过程式自动生成的（不是美术手放上去的），树是用 speedtree 生成的。


　　总得来说，过程式建模是一项潜力远远没有得到释放的技术，现有的工具还处于比较原始的阶段。在当年 PPT 的技术展望（Beyond the Tech）一节中，我写到“（过程式建模带来的）更高级的抽象使我们可以控制更高的复杂度，从而带来更丰富的细节 (Higher abstraction makes much more details and complexities manageable) ”时至今日，受限于技术的发展，这仍只在某个特定的主题（如 Speedtree 的植被模拟和一般的城市模拟）内有效。对于随机性的粒度，我们仍缺乏有效的手段去控制。当年展望时的两大 Expectation（一个是建立起模式和库抽象从而满足不同层次上的复用需求，另一个是如何统一过程式技术中的无序和有序，有效地控制随机性的粒度），现在据我所知仍是所缺甚多，颇为渺茫。当然了，对有志之士，这也不失为一大探索方向。

锐亚教育，游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛