一个输出恒定的三维地形多分辨率简化算法

1、一个输出恒定的三维地形多分辨率简化算法 本文得到863计划课题大型GIS测试与面向SIG的空间信息服务终端（SIST）2002AA131020资助陈斌1，董士海2，方裕1（1.北京大学遥感与地理信息系统研究所；2.北京大学信息科学技术学院，北京100871）摘要：本文提出了一种输出恒定的基于视点的三维地形动态多分辨率简化算法。该算法根据飞行漫游交互仿真的视点参数对三维地形数据进行裁剪简化，并根据人眼视觉心理和显示设备特性进行多分辨率简化。其简化结果数据的数据量与三维地形总数据量和视点位置无关，从而实现恒定数据量输出，并能够通过参数来调节和评价简化的效果。由于实现了输出质量控制和数据量恒定，本文

2、的算法很适合应用于基于网络的大规模地形实时漫游系统。关键词：三维地形，DEM，简化，多分辨率，GIS在基于网络的大规模地形实时漫游系统中，如何尽可能减少在网络中传输的数据量成为一个关键问题，本文提出了根据在客户端仿真漫游过程中的姿态参数对大规模地形数据进行动态多分辨率简化的算法。本算法的目标是：l 场景数据量受到控制并且尽可能恒定。即无论客户端仿真姿态参数如何变化，为了绘制当前场景需要，使从网络传输的三维地形数据的数据量，能够控制在网络带宽所允许的范围，并且为了有效地进行系统服务质量控制，应能够防止出现数据量的大幅度变化，最好能够保持恒定；l 可控的场景视觉效果。简化算法应该可以控制控制视觉失

3、真，并有失真评价方法对失真的程度进行评价；1 相关工作王宏武12提出了基于视点的动态多分辨率地形模型VDDMT（View-Dependent Dynamic Multiresolution Terrain）以及地形的动态简化算法，模型中采用了四叉树结构来容纳经过多分辨率预处理的地形数据，在地形动态简化算法中按照结点评价函数的计算来为模型中不同区域选取不同分辨率的地形数据，并提供了误差评价方法。但是算法需要对地形数据进行预处理，四叉树的结构对于数据更新代价高昂，结点评价函数的计算也比较复杂。Lindstorm45的连续细节层次简化算法实现了对地形数据和高度场数据实时的连续细节层次简化，引入了屏幕

4、空间误差评价的概念。但是算法仍将整个地形数据作为整体进行处理，不适于大规模的三维地形数据；同时屏幕空间误差用于衡量地形数据中顶点距离差，决定是否进行简化，这样不能保证简化后的模型数据量的恒定。陈斌3等提出的基于网络的大规模地形数据实时漫游系统中，改进了王宏武的动态多分辨率算法，针对大规模地形数据，考虑实时性而采用视场模板来代替结点评价函数，这样既对可视范围进行了裁剪，也显著简化了多分辨率的计算。但是仍然采用了空间四叉树来存储地形数据，需要对地形数据进行大量的预处理。2 漫游交互参数按照仿真效果的不同，地形漫游的交互方式分为飞行交互和行走交互两种，其中飞行交互是将客户端模拟为直升飞机的座舱，用户

5、在机舱内以第一人称视角进行飞行姿态的控制和地面观察；而行走交互则是模拟人行走所进行的观察。大规模地形漫游的主要方式是飞行交互。图 1飞行交互仿真示意图图 1是飞行交互仿真的示意图，由图看出，飞行的高度和视线俯角对可视范围的影响最大。而可视范围决定对应空间范围的地形数据量，可视范围越大，则对应的地形数据量越大。下面我们分析影响可视范围大小的参数，以查明姿态参数和可视范围大小之间的关系。影响可视范围大小的姿态参数有4个，记为：l 视点高度he；l 竖直方向可视角大小；l 水平方向可视角大小；l 视线的俯角；在海拔高度为0的水平面上可视范围为一个梯形，其面积S为（公式经过Mathematica 4.

6、0化简）：公式 1可视范围面积公式在一般的飞行交互中，竖直可视角和水平可视角是确定的，而视线俯角和视点高度he是可以通过用户交互改变的，所以在交互过程中，可视范围的变化主要是由视线俯角和视点高度he来决定的。从公式 1我们可以看出，地面的可视范围面积S与视点高度he的平方成正比。可见，飞行交互高度的成倍上升将引起视野范围覆盖面积平方倍数的增加，同样，需要传递给客户端的地形数据量也将以平方倍数增加。从公式 1中我们难以看出视线俯角和可视范围面积S的关系，不妨设=/3，=2/3，he=1，则公式 1化简如下：公式 2可视范围S和视线俯角的关系（=/3，=2/3，he=1）可视范围面积S（纵轴）和视

7、线俯角（横轴）的关系如图 2所示：图 2可视范围面积S（纵轴）和视线俯角（横轴）的关系（=/3，=2/3，he=1）不难看出当视线俯角接近/2时，可视范围面积S迅速趋向无穷大，可视范围所对应的地形数据也以同样的趋势增加。3 带失真的可视范围控制裁剪客户端仿真姿态参数中的竖直视角、水平视角限制了客户端所可能观察到的地面范围，在海拔高度为零的水平面上，地面范围的边界是一个四棱锥和平面相交的梯形轮廓，如图 3所示：图 3竖直视角、水平视角和视线俯角形成的梯形可视范围我们将梯形的短平行边称作近景界，记为av，将梯形的长平行边称作远景界，记为bv。那么，如果地面是一个平面，在梯形范围以外的地面都应该排除

8、在可视范围之外。公式 2可视范围S和视线俯角的关系（=/3，=2/3，he=1）和图 2可视范围面积S（纵轴）和视线俯角（横轴）的关系（=/3，=2/3，he=1）表明如果在飞行交互中视线俯角接近/2，则远景界bv将迅速远离视点，使得可视梯形范围的面积迅速趋向无穷大。为了解决上述问题，我们在引入可视范围失真的前提下，提出一种带失真的竖直视角差裁剪算法，对可视范围的面积进行控制。这里的竖直视角差指一定的地面范围经过透视投影以后在视口的竖直方向上所占据的视角范围。本算法的基本思路在于将远景界以内视角差小于一定阈值的梯形地面范围排除在可视范围之外，以一定的失真度换取对可视范围增大趋势的控制。由于客户

9、端用来显示三维地形场景的光栅显示设备其分辨率是有限的，地面范围的投影尺寸如果小于一个像素的大小，这个范围内的地面将不会被显示设备所表示。因此需要将远景界bv拉近，假设显示设备垂直方向上的像素数为p，由于垂直方向所有的像素所对应的视角是竖直视角，那么垂直方向上的一个像素所对应的视角是，我们可以安全地将远景界以内视角差小于的部分排除在可视范围之外，使得最终的显示效果和没有排除这些部分的显示效果完全一样；如果我们进一步将视角差小于的部分排除在可视范围之外，则最终显示效果在远景界附近的失真将可以控制在n个像素之内。我们将公式 1可视范围面积公式中的竖直视角替换为，得到：公式 3竖直视角差裁剪后的可视范

10、围面积公式可以证明，公式 3在区间内有非负的最大最小值，这样就解决了飞行交互中当视线俯角接近/2的时候可视范围趋向无穷大的问题。在竖直视角差裁剪算法中，n的取值对可视范围的面积影响在接近/2的时候非常大，图 4直观地描绘了这种趋势，图中的10条曲线从上到下分别对应=/3，=2/3，he=1，p=600，=/2，n=1到10，横轴为视线俯角，纵轴为可视范围面积S：图 4像素误差n对可视范围面积的影响（横轴为，纵轴为S）4 基于视点的多分辨率简化基于视角的裁剪可以将客户端交互仿真可视范围限制到一个具有近景界、远景界和侧景界的有限面积的封闭区域，但由于可视范围的面积随着视点高度he增加以及随着视线俯

11、角靠近/2而急剧增加的趋势，如果不对地形数据进行简化处理，对大规模地形的交互漫游仍然难以实现。这里我们就姿态参数中的视点高度he和视点提出一个地形数据的多分辨率简化方案。在交互过程中，可视范围的面积虽然可以成平方倍数地增长，但最终会在客户端的光栅显示设备上绘制出来，这样，客户端显示设备的分辨率限制同样可应用到地形数据的简化方案中。假设客户端光栅显示设备垂直方向的分辨率是p个像素，纵横比是r。单个像素能够表达的有效三角面片数量为1。这样，这个显示设备所能够表达的三角面片数量最多为，这些三角面片的数据采样点个数最多为。也就是说，无论可视范围多大，客户端光栅显示设备所能够表达的有效地形数据点个数为，

12、问题是如何在可视范围内选取这些地形数据点。如图 5所示，将竖直方向视角进行p等分，相应地将对应于显示设备垂直方向的近景界和远景界之间的距离分为p个部分，我们将靠近近景界的部分编号为1，依次远离的部分分别编号为2、3p。图 5根据光栅显示设备特性对可视范围进行划分可以算出，第n个部分的宽度为：公式 4可视范围划分的宽度对每个部分的范围在水平视角方向进行等分，在每个等分部分的范围内，如果原始地形数据存在多于三个数据点，则可以简化为三个数据点。从公式 4中还可以看出，在p个划分中，可视范围中离视点越远y的划分，宽度越大，面积也越大，但是都被统一简化为个数据点。根据人的视觉心理特征，人在观察图像，特别

13、是运动图像的时候，在视觉中心附近的区域视觉敏感度最高，越远离视觉中心的区域视觉敏感度越低，如图 6所示。图 6视觉敏感度分区示意根据这个原理，我们在视点距离简化的基础上进一步对可视范围内的地形数据进行简化。图 5所划分的p个部分分为如下几类：1. 视觉中心区：以视线与地面的交点为中心，前后各个划分部分，即划分编号到，对应客户端显示设备的中心三分之一的显示区域；2. 前景区：从近景界开始的共个划分，即划分编号1到，对应客户端显示设备的下三分之一的显示区域；3. 中景区：从视觉中心区开始的共个划分，即划分编号到，对应客户端显示设备中心偏上的六分之一处；4. 远景区：从中景区开始开始的共个划分，即划

14、分编号到p，对应客户端显示设备最顶端的六分之一处；图 7可视范围的分区和客户端显示的对应对于视觉敏感度高的视觉中心区，保持原有的数据简化不变；对于视觉敏感度一般的近景区和中景区，将数据在原有的简化基础上再简化一倍；而对于视觉敏感度低的远景区，地形数据比中景区再简化一倍。这样，能够将整个可视范围的地形数据减少到：减少的幅度为一倍以上。为了进一步简化可视范围的地形数据，我们设定一个采样步长s，即对视觉中心区每个水平划分的等分的采样组合，当s=1，对每个等分进行采样简化，情况同上面所述，当采样步长s>1，则对s个等分进行采样简化，这样地形数据的简化率进一步降低到：图 8采样步长进一步简化地形数

15、据（横轴为采样步长，纵轴为简化倍数）5 算法实现与评价我们实现了上述的基于视点的动态多分辨率简化算法，测试数据采用美国1度DEM数据中GOLDFIELD1987和DEATH VALLEY1970两块，覆盖的空间范围是经度跨度2度，纬度跨度2度，约38,000平方公里。DEM数据共2,400*2,400个采样点，连成11,520,000个三角形。分别采用竖直象素误差为1，采样步长为1、3进行计算，算法生成的结果与初始场景的大小以及视点位置都没有关系，只和竖直象素误差以及采样步长相关。实际的测试结果如下，其中简化率为简化后的三角形个数与未简化个数的比值，场景绘制时间对应的计算机配置为AMD Dur

16、on650+Geforce256：采样步长场景三角形个数简化率场景绘制时间1651,0025.65%0.27秒3109,1620.95%0.03秒图 9 原场景明暗图图 10 采样步长为1的简化结果明暗图（简化率5.65%）图 11 采样步长为3的简化结果明暗图（简化率0.95%）6 结论本文提出的基于视点的动态多分辨率简化算法根据客户端显示设备分辨率特性和人眼视觉心理特性对地形数据进行简化，实现了输出结果数据量与源地形数据大小无关和视点位置无关的特性。算法设置了结果数据质量调整参数，可以在选择较低质量数据的同时获得数据量较小的简化数据。由于算法的输出结果数据量恒定，输出质量可以控制，很适合应

17、用于基于网络的大规模地形实时漫游系统。7 参考文献1 王宏武，面向数字地球的虚拟现实系统及若干问题研究，北京大学博士研究生学位论文，北京，1999年5月2 王宏武，董士海，一个与视点相关的动态多分辨率地形模型，计算机辅助设计与图形学学报2000年08期3 Chen Bin, MA Zhi-Gang, WANG Guo-Ping, DONG Shi-Hai，Network Based Realtime Flythrough on Massive Terrain Dataset，CAD/Graphics2001国际会议论文集第七届计算机辅助设计与图形学国际学术会议文集4 Peter Lindstr

18、om, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, and Gregory Turner. Real-time, continuous level of detail rendering of height fields. In Holly Rushmeier, editor, Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, pages 109118. Addison Wesley, New Or

19、leans, Louisiana, August 1996. ISBN 0-201-94800-1.5 Peter Lindstrom. Out-of-core simplification of large polygonal models. In Kurt Akeley, editor, Proceedings of SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, pages 259262. ACM Press / ACM SIGGRAPH / Addison Wesley Longman, N

20、ew Orleans, Louisiana, July 2000. ISBN 1-58113-208-5.A 3D Terrain Multi-resolution Simplify Algorithm With Stable OutputCHEN Bin1, DONG Shi-Hai2, FANG Yu1(1.Institute of Remote Sensing and GIS, Peking Univ.; 2.School of Electronic Engineering and Computer Science, Peking Univ., Beijing 100871)Summary: This paper introduced a view p