一种解决全球地形绘制抖动问题的方法

引 言

抖动问题是像星球仿真、物理计算仿真、大规模军事仿真系统等大型虚拟环境中一个非常棘手的问题[1]。它会导致绘制场景时，出现物体一部分被莫名其妙地裁剪掉，三角网格破碎，纹理错乱等错误现象。全球地形环境是一个典型的大规模虚拟环境，也会遇到抖动问题。特别是在绘制米级高分辨率地面时，抖动问题特别明显，严重削弱地形的绘制效果[2]。

抖动问题是由于浮点数舍入误差过大所造成的[3]。目前解决全球地形环境中抖动问题的方法有两种：多局部坐标系统方法和动态局部坐标系统方法。多局部坐标系统方法为每个地形块都建立一个局部坐标系统，每块的地形顶点都在自己的局部坐标系统中绘制，从而减小顶点的浮点数误差，避免抖动现象的出现[2,3]。然而这种方法会破坏全球统一的地理坐标系统，而且还会带来多坐标系统导致的各种问题[4,5]。动态局部坐标系统方法只需建立一个动态的局部坐标系统，该坐标系统的原点随着视点变化而变化，场景中所有物体都在这个局部坐标系统中定义[1,5,6,8,9]。由于场景中物体一般都离视点不远(如果太远，会被视锥体裁减掉)，所以物体坐标的浮点数误差一般不大，因此避免抖动现象的出现。然而目前的动态局部坐标系统方法都有各自的问题。微软 Flight Simulator[5]采用动态局部坐标系统进行反抖动，但并没有介绍如何设置局部坐标系统的原点，只是定期地更新原点。如果视点移动速度很快，地形块远离上次更新的原点，同样会出现抖动现象。GeoVRML[6]使用GeoOrigin 设置原点建立动态局部坐标系统，但不能阻止用户错误地设置原点，例如设置原点远离视点，仍然会导致抖动现象[1]。另外它对自由导航没有做任何处理，也会出现严重的抖动问题[1]。虽然基于GeoVRML 的 TerraVision[7]对自由导航采用周期地将原点归位于视点，仍会遇到微软Flight Simulator 中视点移动过快时出现的问题。Java3D[8]虽然可以使用场景(locale)坐标系统作为动态局部坐标系统，也会遇到和GeoVRML 一样的问题。 O'Neil [9]，Throne[1]和Lambers[10]以视点为原点建立动态局部坐标系统，但是视点却不是全球地形环境中动态局部坐标系统原点的最佳选择。

本文在目前动态局部坐标系统方法的基础上，提出一种新的更适合全球地形环境的反抖动方法。这种方法选择视点在球面上的投影点代替视点作为局部坐标系统的原点。该方法既能避免多局部坐标系统方法带来的各种问题，又能保证在任何情况下都不会出现抖动现象，同时比以视点为原点的动态局部坐标系统方法有更好地反抖动效果。

1 全球地形数据组织

为了平衡全球海量地形的渲染质量和速度，一般采用面向全球的多分辨率金字塔模型来组织地形[11]。这种技术把全球地形按经纬度分成不同的层和块，如图1 所示。全球地形数据在预处理阶段分成小块的地形数据块存储起来。无论地形块结构是规则网格还是不规则三角网，都使用保存在文件中的对应地形数据块来构建地形网格。所有地形块的地形网格连在一起，就构成全球地形网格。当视点移动时，需要将已经不在视锥体内的地形块从内存中卸载，并用新的地形块替换。当视点向地球靠近时，使用精细的地形块替换粗糙的地形块。相反地，当视点离开地球时，使用粗糙的地形块替换精细的地形块。

2 浮点数舍入误差与抖动问题的成因

舍入误差是量化误差的一种形式[12]，是运算得到的近似值和精确值之间的差值。当使用有限位数的浮点数(理论上存在无限位数的浮点数)来表示实数的时候，就会产生浮点数舍入误差。由于舍入误差的存在，所以计算机系统并不能精确表达所有实数。例如十进制实数 0.25 能被计算机系统精确表达，即(0.25)10 = (0.01)2 ，此时不存在舍入误差;但是实数 0.1 就不能被计 算机系统精 确表达，即(0.1)10 = (0.000110011...)2 ，此时存在舍入误差。假定浮点数x 的舍入误差为?x ，有效数字位数为t，则浮点数的舍入误差可以通过公式(1)计算出来[12]：