Skip to main content
ARShow
ARShow
 首页 » 资源教程

使用四叉树实现超大规模地形动态生成

2017年03月07日 17:29:4114510蛮牛网

实现的效果:从外部读取一张高度图或动态生成一张高度图,根据此高度图实时生成网格且离角色越近面片数越高,即LOD整个地形采用四叉树结构来处理地形初始化时为一个正方形结构

使用四叉树实现超大规模地形动态生成 资源教程 第1张

当角色离此正方形足够近时,此正方形又会分成四个小正方形,如此递归,且每个正方形会对应一个网格,图中白线为正方体,黑线为网格顶点的y坐标根据高度图来确定

使用四叉树实现超大规模地形动态生成 资源教程 第2张

是否继续划分的条件为:角色到此正方形中心的距离/正方形边长Cl为我们设定的一个值,cl越大越易划分

此处还可以加入对地形平缓程度的判断来确定是否划分,因为如果一个地形为一个标准平面,那么,划分多次和划分一次效果是一样的

观察上图可知,只有叶子节点,即没有继续划分的节点,才会被渲染,所以,在初始化时,当我们检测到叶子节点时,把它加入一个存储待生成网格的节点list中,待划分完毕后生成所有叶子对应的网格,同时还要将其加入一个存储可视节点的list中,方便之后操作

这里我没有马上生成网格,是因为考虑到缝隙的问题,此问题到下面再讲

划分完毕后,就可以遍历待生成网格的节点list,根据其中心和边长生成对应网格

到这里,初始化就完毕了,我们可以得到一个实现了lod的地形网格

在更新时,我们需要遍历可视节点list,检查其中的节点是否可继续划分或者回退,当:角色到此正方形父节点中心的距离/正方形父节点边长>=CL+i  时,即为可回退,消除其父节点所有子节点及它们对应的网格,同时将其父节点作为新的可视节点加入到两个list中,i起到一个缓冲的作用用来防止玩家在边界处不断往复运动,这里要考虑,根节点是没有父节点的,注意判断父节点是否为空

好,现在我们实现了最基本的部分,接下来说裂缝的问题

当两个相邻节点的lod层级不一样时,如下图

使用四叉树实现超大规模地形动态生成 资源教程 第3张

其中最上面和最下面的节点y坐标为0,对左边的正方形而言,它们的中点y坐标也为0

而对右边的三角形而言,由于他在中点有一个顶点,所以它的y坐标为1

这时,同一位置,对不同的三角形有两个不同的y坐标,它们的交界处就会出现一个空洞

使用四叉树实现超大规模地形动态生成 资源教程 第4张

对于只差一个层级的两个三角形而言,解决这个问题也是比较简单的,只要检测邻居正方形的lod层级,然后根据层级对网格进行调整就好了

这里我引用网上的资料:

使用四叉树实现超大规模地形动态生成 资源教程 第5张

在上面这个图中左右两个网格的划分层次相差为1,也就是右侧的网格比左侧的多划分一次。这时候问题出现了,当以顶点1 2 3渲染三角形和以顶点2 4  5渲染三角形以及以顶点5 4 3渲染三角形时候就出现了裂缝。图上面是在xz平面上看不出问题,但是当给顶点赋予y坐标值的时候问题就出现了,因为点4可能和点2  点3不在一个高度,所以点2 点4点3组成的可能是一条折线。假如点2 点3的高度相同,点4比点2 点3 高,那么点2 点3  点4便组成了一个三角形,这个三角形就是

地形二

上面的裂缝。大家可以看下比较大的裂缝会发现正好是个三角形,这就是很多诸如点2 点3 点4组成的三角形裂缝。那么怎么解决这个问题呢?可以在点1  点4之间增加一条线段,这个处理起来比较麻烦,本文采取的是将点4点5组成的线段取消,也即删除点4,这个时候裂缝便会消失,如地形一那样。

使用四叉树实现超大规模地形动态生成 资源教程 第6张

注意中间的交界处

这个方法很有效,效果也很好,但是,当两个相邻正方形lod层级相差2及以上时,此方法就失效了

使用四叉树实现超大规模地形动态生成 资源教程 第7张

在这幅图里面,右侧的网格比左侧的网格多划分了2次,这个时候顶点3 顶点6 顶点5 顶点4组成的边比先前那个例子更加复杂了。即使删除点5,点3 点6  点4仍然可能组成一个三角形裂缝。点6不能删除,因为点6是正方形网格的顶点,删除它就等于删除网格了,所以只能删除边的中点。这下怎么办呢?如果有一种方法保证左右两侧的两个正方形网格划分层次相差小于等于1,那么就可以按照前文所说的那样通过删除点来消除三角形裂缝。能做到这一点吗?答案是肯定的。假设左侧的网格划分值为f2,右侧的网格的父亲节点划分值为f1,当f1网格需要划分的时候必须保证f2也划分

所以,我们要检测每个正方形其四个邻居的lod层级,当层级相差2及以上时,就需要对其强制划分

注意,此强制划分绝不能在第一次遍历(及判断可视节点是否可划分)时进行,因为这时可能只对一个正方形划分了一部分,此时邻居正方形可能还未生成

当第一次遍历完毕后,我们进行第二次遍历,专门进行强制划分

在最后,我们还需要再次遍历可视节点,将现在邻居正方体的层级与上帧邻居正方体的层级进行对比,如果不一致,更新网格

优化技巧:在生成网格时,需要创建顶点和面的数组,如果每次都new的话,会导致极高的gc  alloc,我在一开始没注意到这个问题,导致单帧最高达到了将近200kb的gc alloc!

其实,不同正方形节点的顶点数组大小是一样的,我们只需在初始化“创建网格的类”时new一个顶点数组即可,之后不必再new,

而面数组比较特殊,因为他的大小和邻居正方形有关,我们需要按最大来new这个数组,而且要注意,每次用之前必须把后面几位置为0,否则会受到上次数据的干扰经过几个类似于此的优化,gc  alloc降到了0

除此之外,在生成网格时,为了方便,我采用了二维的方式来确定顶点,但顶点数组是一维的,所以需要二维向一维的转换,m = x+y*count

这里我创建了一个二维查找表,预先计算所有xy对应的m,用时直接去表里取就好了,在4w平方米时,这样每帧大约少了1w次左右的乘法和加法运算

评论列表暂无评论
发表评论