Seamless world with LOD


Davis 的咖啡杯 MSN:nsdavid_lj@hotmail.com

LOD是细节层次化技化,用于简化模型的网格结构,LOD分为两大系,分为封闭模型与非封闭模型简化两类技术,这里主要介绍超大地形的LOD实现方法。
由于地形通常是一个巨大的网格来表示的,大量的数据会对画面渲染处理造成很大的瓶颈,因此地形LOD的好坏关系到野外场景程序的主要性能指标。
下面列出两种主要的地形LOD的实现方法,从有限规模场景到无限大地形,并提供一些参考内容。


一、使用四叉树

地形通常可以用一个四叉树来表示,也有用伪八叉树(介于四与八叉树之间),如果是一个有限大的地形,并且满足条件长=宽=2n次方+1,那么它可以看出一颗类似Tree的组织结构,每个节点都包含了四个子节点,每个节点都可以找到中心顶点索引与周围的八个边点索引,只需要通过递归或与回溯,就可以很容易的实现单个节点的渐变的细节进化或退化的过程,通常ROAM都使用四叉树式的数据结构来表示。
通过四叉树的表示方法,一个9x9共81个顶点的网格,从四叉树的顶部开始遍历,分别可以得到1x1,3x3,5x5,9x9四个细节层次,SO:ROAM的LOD层次数 = log2(n-1)+1
无疑,越深的子节点,它对应的网格与顶点的间隔距离越小,即细节越丰富。实现LOD的主要思想就是离人眼距离越近的地方,地形细节越丰富,越远的地方越简洁,但是可能有的物体较远但是它的细节很丰富,例如远处的山峰,如果只根据距离来选择与反馈,在视觉上会引起严重的物体变形,即通常所称的呼吸效应


二、粗糙度评估方法

因此我们需要为每个节点增加一个粗糙度慨念,并找到一个合适的粗糙度表示方法。以细节最高的节点为例,它拥有9个顶点,共构成8个三角形(TriangleFan),这是一个最基本的不能再被简化的节点。
为了评估粗糙度,我们必须找到一个基准点,就以中心的顶点为基准点,周围8个顶点与各比较,共存在8个高度差信息,假设粗糙度C=fabs(V[0].height-V[c].height)+fabs(V[1].height-V[c].height)+...,
如果C的值较小,我们就认为这个节点是平坦的,如果C的值较大,我们称之为陡峭的。有了C后,父节点的粗糙度就比较好定义,父节点的粗糙度必须大于子节点,较适合的方法就是父节点的C=各子节点的C的总和。因此越是接近root的节点,它的细节越丰富,因而它受视距的影响就越小。
 
 
三、T型裂缝处理

基于以上两个方法,就可以根据摄像机(即人眼)的位置来对整个地形进行逐级处理,根据不同的距离与粗糙度选择合适的节点,但是在产生最终的渲染列表的时候,会发现各节点可能存在细节差别较大的邻节点,则相邻的边就无法正确的匹配到各相邻的节点上,如果出现这种情况,那么渲染的时候将会出现T型裂缝的问题,如图所示:左边与右边的三角形的缝合是不完整的。

我们必须消除这种情况,为了消除这个T型裂缝,可以选择在合适的位置加一条边或者减去相邻的一条边,实际情况下加边操作远远快于减边操作。不管哪种方案,为了减少复杂度,我们规定相邻节点的LOD级别小于2,即差1或相等。我们在每个顶点上增加一个状态属性,中心与四角的顶点设为必须渲染,如果相邻的LOD差1,则激活相对应边的中间顶点,这样在最终三角形索引的生成过程中,就能将每个三角形的边都缝合在一起,如图所示(红色边为增加的边):
 
 
 



 
 
 
四、裁剪

1) 背面预裁剪
if dot(triangle.normal,eye.normal) > 0
  render;
end if

2) 视截裁剪

if Node.AABB in Frustum
  render
end if

为了正确的截剪,除了测试AABB的8个顶点外,还需要测试AABB的中心点

五、ROAM综述

1. 复位每次计算前顶点状态
2. 摄像机位置的改变需要从ROOT开始,遍历所有可能的节点
3. 生成最终的三角形索引序列

六、TileLocking 方法

1. 平坦式拼接
ROAM是一个realtime的LOD方法,因此大部分的时间都消耗在了计算上,TileLocking方法相当于一个简单的ROAM,使用联锁的方法来处理不同细节的Tile。
TileLocking中,并不使用四叉树结构,而是一种平坦的Tile拼接模式,一个Tile只包含三种不同级别的三角序列,它的Grid大小一般为32x32,Tile中的顶点分布的级别依次为33x33,17x17,9x9。
关键在于三种不同级别的索引排列已经预先计算好,处理的时候根据需要选择一个LOD级别即可,所有可能的索引表是提前统一的,并不是每个TILE都会生成自己的索引表。

2. 联锁处理T型裂缝
TileLocking处理T型裂缝的典型方法,也是为每个不同级别的TILE计算好邻近8个TILE可能存在的低(高)一级别的三角排列索引表,因此虽然只有3级LOD,但是3级LOD包含了至少十几种的变化,摄像机位置改变的时候,需要做的就是从这十几种变化中选择一个合适的索引表即可。因此,它比ROAM少了1,3步骤,2的步骤相比也简单了非常多,因此使用TileLocking对系统效率的提高是非常明显的,只是由于3级LOD与ROAM的多LOD级别相比相对匮乏一些,因此在"呼吸效应"上比ROAM要高一些,解决的方法就是增加更多的索引表。

TileLocking由Nivida提出,在Game Programming Gem2中有介绍

3.Geometry Mipmaps 几何修复
GeoMipmap是根据TileLocking特点新提出的一个解决T型裂缝的方案,它会自动在相邻不同级别的Tile间构造新的三角形,计算方法并不复杂,并且也能获得较好的效果,速度比联锁方式略慢,但是可以使TileLocking很方便的构造更多的LOD,这个技术同样能应用在ROAM上。
GeoMipmap的缺点在生成接缝时,由于是增加了一个新的三角形,这个三角形不属于任何一个node,也无法合适的将它放到哪个node中,因此在对地形作快速碰撞,提取高度,贴花等问题时,需要额外处理这部分内容,除非能够想出一个好的解决方法。


相关资料 google Geomipmap 即能找到

七、Seamless Worlds

1. TileLocking的构成非常容易就能实现无缝世界,只需要横向纵向增加Tile数量即可,因此不在累述。
2. Roam是一个四叉树结构,但我们可以定义9个ROAM块,每块看作一个PATCH,首先计算EYE的PATCH,计算后会锁定边界顶点,因此在计算其它PATCH的时候,就能生成相适应的ROAM数据。
(Roam的效率本身还是很高的,在我在自己的笔记本上,用DEBUG,也能做到MS Lab DEMO中每秒吞吐40万三角形的效率,在采用每帧重算的机制下,1024x1024的Grid能达到30个fps,Release版的效率则在DEBUG版的五到六倍左右,实际游戏中LOD每秒重算5次足矣~)