《基于roam无限大地形实现思想》由会员分享，可在线阅读，更多相关《基于roam无限大地形实现思想（9页珍藏版）》请在金锄头文库上搜索。
1、基于 ROAM 的无限大地形实现思想前言：什么是无限大地图？无限大地图的产生是在 3D 游戏中，为了给玩家带来全方位的真实游戏感觉而产生的。在 3D 游戏中决定是否使用无限大地图技术的关键并不是我们的游戏世界的大小，而是游戏是否需要模拟人类的视线，能再视椎体中需要渲染深度很高的地形区域。如下图：图 1-1一般在普通的 MMORPG 中（不需要无限大地图）的游戏中，d 的值为 100-150 左右，所需渲染的三角形数量在 10-20 万之间。而在真实世界里面，我们的眼睛会看到几百米，甚至几千米之外的景色。假设我们要提高玩家的体验，将渲染的距离提高到 500 米，从数字上看起并没有增加太多，但是我
2、们如果使用跟普通的游戏一样的场景管理方式，所需要渲染的三角形数量将增加 25 倍。图 1-2那么所需要渲染的三角形数量将变成 25*15 = 375 万个三角形。这个使我们的显卡所不能支持的。所以，我们要对无限大地形进行特殊的管理与优化。一 要实现无限大地形，需要实现哪些技术难点1. 内存的组织决定要分块处理世界地形2. 后台加载决定要使用多线程对资源进行全方位管理3. Patch 之间的无缝拼接 对地形网格的三角形复杂度进行按需分配4. 大场景物体的管理碰撞，快速拾取5. 一些除地形以外的降低渲染压力的方法让我们的场景跑得更加流畅6. 无限大地图的寻路方法二 各个击破这些难点1. 内存的组织
3、决定要分块处理世界地形原因：无限大地形的游戏世界一般是非常的广阔的（因为看得远，否则走没有几步就走完整个世界了） 。魔兽世界的地图高达 320000000 平方米。这么大的地形上面得有多少的数据信息（还不包含副本与外域等） 。我们的游戏中一个场景为262144（512*512 ）的大小，资源从 300-600M 不等。按这个比例，那么如果一次性将整个无限大地图的游戏资源都加载到内存里面，那么需要600*(320000000/262144)= 732421.875M 的内存大小。汗，这个数据绝对是用户所不能承受的。具体方法：既然在像 WOW 这么大的世界中，我们跑个 30 分钟我们也不一定能跑到
4、地图的另一边，那么我们干嘛吧这块地形加载到内存中呢？所以，解决这个问题的关键在于一部分一部分的加载我们所需要的资源，看到哪里就加载哪里的资源，卸载已经看不到的地方的资源。这样我们不就可以让游戏的内存保持到很少的大小么？所以，问题的关键在于，怎么分割世界，以及什么时候加载，什么时候卸载。关于分割世界的方式有很多，最简单的方式就是先分割成一个一个区域（area）, 比如荆棘谷、暴风城、等等。区域与区域之间以门的方式连接。每个区域分割成一个一个的页片（TILE ） 。比如 36*36 大小的一块地形数据（包括场景数据） ，tile 被作为游戏中的一个加载卸载的整体进行管理。图 1-3怎么决定一个场景
5、对象是属于哪个 tile？有 2 中方法：精确的、或者松散的。这里介绍第 2 种方法。在场景编辑器中导出某个 Area 的时候，根据某个物体的包围盒来决定物体属于哪个 TILE，导出成场景资源配置文件。决定什么时候加载某个 TILE。图 1-4如上图，当 tile 进入蓝色的区域的时候加载器才需要加载，当 tile 离开绿色区域才能卸载资源。这样设计的原因是因为角色的移动速度是非常快的，如果角色在移动中反复的来回于跨越 2 个区域，那么这 2 个 AREA 里面的资源将会被频繁的被加载与卸载，非常不划算。增加了资源进出阀门，那么这样的频繁卸载加载的情况就不会出现。2. 后台加载决定要使用多线程
6、对资源进行全方位管理如果决定要使用分块加载的方法，那么一定会使用多线程资源加载。需要完成一个资源管理器，对所有的贴图，模型，高度图信息，动画文件等等进行分别的后台加载。3. Patch 之间的细分 对地形网格的三角形复杂度进行按需分配前言中说到，无限大地图需要渲染的视野范围非常大，三角形数量非常大，地形就占了其中非常大的一部分。我们必须要降低这部分的三角形数量。有 2 种方式来决定三角形数量：1） 离摄像机的远近。试想，一个离我们非常远（500）米远处的一块地形，经过投影矩阵的计算，映射到我们的屏幕上，像素也就 3、4 个，我们为什么要为它绘制好几十个三角形呢？这样的一块地形（36*36） ，
7、我们绘制一个 1-2 面就足够了。那么我们眼前的三角形又为了保持精度，需要甚至36*36 的格子大小。2） 地面自身的复杂度。一个地面非常复杂的区域，比如山区、丘陵等地方，地形复杂，我们需要更高的三角形密度，然而像平原，沙漠，这样的地方，平平的，就只需要很低的三角形密度足够了。那么，我们怎么来利用上面 2 个条件来决定一个三角形到底应该具有多少的复杂度呢？我们给地形的复杂度来个定义。权值是一个很好的解决方案。Far*w1+Comp*w2 = weight for tile; 公式 1W1+w2 = 1.0;Far 表示离摄像机远近，Comp 表示这块三角形的复杂度，w1w2 表示系数。复杂度的
8、计算方式如下图： 图 1-5我们定义每一个三角形的复杂度为三角形长边的中点高度，与中点处的实际高度之差表示。具体的分割方式。采用 ROAM 的方法（递归二叉分割三角形）图 1-5对于任何有一个三角形 A 如图（1） ，根据上面的公式 1 计算出 A 具有多少的权值，如果权值临界值，那么我们就需要分割这个 A。具体的分割见图（ 2）.这样 A 就被直角顶点与长边中点分割为左右 2 个同样的等腰直角三角形 a-left 与 a-right。继续递归新的 2 个三角形，决定是否分割他，直到所有的三角形都不需要再被分割。具体的类设计结构：图 1-6struct TriNodeTriNode *Left
9、Child; /左孩子TriNode *RightChild; /右孩子TriNode *BaseNeighbor;/与斜边相邻的三角形TriNode *LeftNeighbor;/与左直边相邻的三角形TriNode *RightNeighbor;/与右直边相邻的三角形4. 大场景物体的管理碰撞，裁剪无限大地图的场景很大，物品与角色可能非常之多，当我们需要在这些大量的物品里面判断对象是否发生碰撞，或者剔除掉我们场景中不需要渲染的部分，就会变得非常困难。因此，无限大地图必须建立自己的场景管理机制。一般来说场景管理的方法有很多。这里我主要介绍松散八叉树算法（loose octree） 。首先，要了
10、解松散八叉树，我们需要先了解什么是八叉树。图 1-7如上图，一个密闭的立方体空间，被横纵两个面被分割成 8 个小的立方体空间，然后子立方体因为还具有分割需求，继续被 2 个面又分割成了 8 个更小的立方体空间，就这样一直分割下去，知道需求停止。需求停止的原因有很多，比如，最小子空间内三角形数量达到最小界限，或者最小子空间内没有可分割的更多的物体，只有一个被包含的对象。或者分割深度达到一定的下限，或者是遇到不可分割的对象，等等原因。但是这样的基本八叉树分割有一定的缺陷，如下图 图 1-8对于上图的情况，大立方体空间的分割，因为一个非常小的物体跨越了分割界限，而被停止了。这样的情况，必然会导致分割
11、的层次与效率地下，也达不到我们的目标。这种现象被称之为八叉树的粘性（sticky） 。松散的八叉树，就是基于八叉树而产生的一种变形形式。它的优点就是分割结构是松散的，不是固定的被分割为等同大小的立方体子块。每一个子块甚至可与邻居子块共享一部分空间。即，每一个字块节点，可以通过调整自身的体积大小来使细小物体不被分割。在这样的情况下，每一个节点既不改变节点子块的中心位置，也不需要改变分割的层次。如下图： 图 1-9虚线为传统的一个四分结构，第一个为实现为四分之后的四个子节点都进行了放大操作。第二个为右下子节点进行放大操作。松散八叉树的应用：碰撞或者剔除： 图 1-10一条射线穿过了场景节点块（紫色
12、） ，递归检测孩子，知道检测到射线所穿过的所有最小孩子，则可判定射线穿过了那些物体。这个算法既可以用来判定碰撞，也可以用来判定裁剪（包括视域剔除与遮挡剔除等等，很多算法，不一一列举） 。5. 一些除地形以外的降低渲染压力的方法让我们的场景跑得更加流畅 除了降低了地形的三角面数量，大场景中大量的对象也会让显卡承受不起。那么我们需要采取哪些方法来减少场景物体所产生的三角面数量呢？1） MeshLod: 针对模型，进行层次化细节分级显示。离摄像机 100 米远处的一个物体，映射到屏幕上只有数十个像素点，那么我们不需要数千面的对象，我们只需要一百多个面的模型即可。对不同的对象设定不同精度等级的 Mes
13、h，场景管理器，根据对象离摄像机的距离，自动调整成不同的模型。2） 公告板树。6. 无限大地图的寻路方法大场景中的寻路很困难，原因是地图大了，常规的一些寻路方法则不适用.那么我们可以采取搭地铁算法与 NAV 网格寻路结合的方式来解决这个问题。一般来说无限大地图会被根据策划等原因分割为一块一块的区域（Area）,在Area 之中，我们需要适用 NAV 网格寻路的算法计算拐点信息，在跨越 Area 之间，一般是通过 Area 与 Area 之间的门来进行寻路。 图 1-11三 展望新技术介绍的这些技术还算是比较新的技术。但是技术的发展是很快的，软件算法的更替也是跟着硬件的更新来的。于是在我们等待这些算法进入国内运用的过程中，国外又产生了许许多多的新算法。比如，我们的场景地形 LOD 算法ROAM 。ROAM 算法的本质是在使用 CPU 的计算来换取 GPU 的低负担。但是随着 GPU 的发展，工程师们逐渐认为这样的方式很不划算，他们开始设计基于 GPU 的地形 LOD 技术。比如细分网格等等，但是一般是用于近距离增加网格的。以及一些基于三角形的裁剪技术。有兴趣的大家可以去找些资料看看。何姝姝2011-7-3 上海
