高精度高速度曲面建模的_3维_地表模拟和漫游算法

第 15卷? 第 7期 2010年 7月 中国图象图形学报 Journal of I mage and Graphics Vo. l 15, No . 7 July , 2010 基金项目: 国家科技支撑计划 ( 2006BAC08B0505) 收稿日期: 2009? ; 改回日期: 2010?04?09 第一作者简介: 闫长青 ( 1978? ?), 男, 讲师。中国科学院地理科学与资源研究所地图学与地理信息系统专业在读博士研究生。主要研 究领域为高精度曲面建模理论及 3维可视化。E? mai: lyancq lreis . ac . cn 高精度高速度曲面建模的 3维 地表模拟和漫游算法 闫长青 1), 2) ? 岳天祥 1) 1) (中国科学院地理科学与资源研究所, 北京?100101) ? ? 2) (山东科技大学信息工程系, 泰安? 271019) 摘? 要?3维真实感地形场景是生态系统模拟、 虚拟地理环境和 3维 GIS不可或缺的要素, 而高精度高速度曲面建 模方法可以动态实时构建高精度曲面模型。论文引入高精度高速度曲面建模方法, 提出了一种可以动态生成地表 模型并实时绘制和漫游 3维真实感地表的方法。该方法实时动态建立高精度 DEM ( digital elevationmodel), 结合改 进的视点依赖多分辨率绘制方法, 随视点改变动态重建并绘制当前 DEM。首先建立当前可见场景的 DEM, 然后通 过依赖于视点的简化等处理建立层次细节模型, 进行实时场景绘制和漫游, 随视点改变, 在当前场景基础上动态加 点和减点更新 DEM 及层次细节模型, 生成当前可见场景, 依次循环。实例测试表明, 算法可产生真实感较强的场 景, 实时漫游效率较高, 模拟精确。 关键词? 高精度高速度曲面建模? 3维地表模拟? 层次细节模型 ? 纹理融合? 场景漫游? 实时绘制 中图法分类号: TP391? ? 文献标志码: A? ? 文章编号: 1006?8961( 2010) 07?1126?07 3D Simulation andW alk?through A lgorithm of Terrain Based on H igh Accuracy and Speed SurfaceM odeling YAN Changqing 1), 2), YUE T ianxiang1) 1)(Institute of Geographic Science andN atural Resource , Chinese Academy of Science , Beijing 100101) 2) (Department of Information Engineering , Shandong University of Science and T echnology, Tai an 271019) Abstract ? Real ?ti me generation of realistic 3D?terrain is essential in ecosyste m modeling, virtualgeographical environment and 3D GIS. Based on high accuracy and speed surface modeling(HASSM ), which can be used to construct surfacemodel dyna m ically ,a new real?ti me si mulation and walk?throughmethod is proposed for constructing terrain modeland rendering in real ti me . Firstly ,the current visible terrain model is constructed accurately and rapidly . Then, multi?resolution model for rendering is built using a modified vie w?dependent level of detail( LOD ) method. Thirdly , while walking through the terrainmode,lthe changing model isgenerated in real?ti me by adding the ne w visible point and deleting the invisible points locally ,and also the corresponding LOD mode. l The procedure is iterated unless walk?through is stopped .Test of data shows themethod canmake nearly real scene and obtain high efficiency and accuracy ofwalk?through. K eywords?high accuracy and speed surface modeling(HASS M ), 3D?terrain si mulation,levels of detai, ltexture fusion, walk?through of scene ,real?ti me rendering 0? 引 ? 言 3维真实感地形场景是地球表层系统模拟、 虚 拟地理环境、 3维 GIS以及近年来兴起的 3维决策 支持系统不可或缺的要素。其实时建立并显示成为 近些年研究的一个热点问题。但因其数据量巨大, 地物类型复杂多样, 在快速建模和实时显示时遇到 不小的挑战。经过十多年的研究, 取得了一系列的 研究成果 1?18, 主要集中在如何建模能够忠实地表 第 7期闫长青等: 高精度高速度曲面建模的 3维地表模拟和漫游算法1127? 达原始曲面, 采用了多分辨率模型减少数据冗余, 数 据结构主要是 T I N和 GRI D, 或者二者的混合 1?18, 其研究焦点之一是如何快速产生较高精度的曲面, 之二是如何对建立的曲面模型进行实时真 3维可视 化, 3维可视化的方法又多采用了视点依赖的层次 细节模型。这两个问题的研究多是独立进行, 即多 分辨率的模型产生和可视化在时间上是脱离的, 即 先产生模型, 再进行可视化。而可视化的焦点主要 集中在数据的组织, 所形成画面的连贯性, 算法的视 觉效果等方面。 高精度曲面建模方法, 是一种新的曲面建模理 论与方法, 该方法是由岳天祥等人提出并逐步发展 完善起来的 19?25。该建模方法和传统经典建模方 法相比, 从根本上解决了曲面建模中的误差问题, 具 有经典方法无法比拟的精度, 且该方法的后续研究 在多个方向均有突破, 解决了求解微分方程的速度 问题。具体发展有快速迭代求解方法、 多重网格方 法、 自适应方法、 实时动态模拟方法等。实时动态方 法可以通过动态加点和减点实时生成 DEM。 对于日益增大的海量地理数据来讲, 如果预先 构建整个高精度 DE M (数字高程模型 ), 必然耗费较 高的时间代价和存储代价。应能够根据需要实时地 产生高精度 DEM模型, 进行实时可视化, 两者同时 或联机进行, 可节省时空成本, 以提高效率。 为解决此问题, 引入高精度高速度曲面建模方 法, 在此基础上对真 3维地表模拟进行研究, 提出了 一种视点依赖的自适应多分辨率真 3维地表模拟方 法, 实时动态地构建当前所需 DEM, 构建视点依赖 的可视化模型, 漫游并实时更新。算法思想为运用 HASS M 方法实时构建初始高精度 DEM, 然后实施 裁剪, 建立层次细节简化模型, 纹理融合, 绘制地物, 进行漫游, 同时根据视线移动方向动态加点减点实 时更新 DEM, 循环操作。 1? 基于 HASS M 的地表模拟漫游方法 1 . 1? DEM 的实时构建及更新 1 . 1 . 1? 基于 HASS M 的 DEM 实时构建 HASS M 的基本思想是, 根据微分几何原理, 曲 面由其第 1类基本量和第 2类基本量唯一确定, 求 解了基本量, 即可求得曲面。有关方程读者可参阅 文献 21?25。基本量通过差分求解, 进而差分求 解代表曲面的高斯非线性偏微分方程, 具体求解方 法最终归结为矩阵运算。而 HASS M 实时算法的思 想是, 要想满足实时要求, 必须在求解偏微分方程方 面尽可能减少计算量, 并充分利用现有计算结果。 采用了矩阵正交三角分解方法, 归结为求解简单的 上三角矩阵和下三角矩阵问题, 具体过程可参阅文 献 24。在视图区的范围内, 利用该方法在计算初 始曲面时可满足实时要求。 1 . 1 . 2? 基于 HASS M 的 DE M 加点减点实时更新 根据文献 24, 加点相当于 HASS M 系数矩阵 增加 Z 行, 即系数矩阵在原来的基础上增加了 Z 行, 其余保持不变。而减点相当于系数矩阵减去 Z 行, 其余保持不变。可以对矩阵进一步分解为当前 已求得系数矩阵部分和代表新加入或者刚减去 DEM 的系数矩阵部分, 因为场景的变化一般是随漫 游渐变的, 故只需求解代表变化的小规模的系数矩 阵。这样就充分保留了原有的已求得的曲面信息。 从而充分利用了上一时刻曲面构建所得的信息, 避 免了大量计算, 高效地构建当前曲面。具体加点和 减点的计算过程见文献 24。 在实际真 3维地表漫游应用当中, 根据位置的不 同, 尤其观察者所在位置的变化, 需要动态变化以满 足观察需求。而这种动态变化, 可以归结为随着视点 的变化, 在视线方向上增加了一部分新的场景, 在视 线反方向上丢弃了一些场景。而场景即为由点构造 的地表曲面, 故可以在视线方向上动态增加点, 而在 视线反方向上动态减点重构高精度 DEM。从而归结 为实时高精度曲面建模的加点减点更新方法。 又因为在绝大多数情况下都是局部区域 (视见 域 )内的曲面构建, 所需点数即数据量会规模比较 小, 使得数据的存储组织比较简单, 因而可以解决大 规模数据量构建真 3维地表的存储组织问题。 DEM 的构建及更新方法为: 首先根据 DEM 实 时构建方法, 构建视图区 DEM, 然后随漫游通过加 点或减点方法补充新增可见部分并去除刚从视图区 消失部分, 实施 DEM 动态更新。 1 . 2? 改进的视点依赖的 LoD模型 要建立 3维显示所需的视点依赖的 LoD模型, 一般需要经过视区裁剪, 层次细节简化, 裂缝修补等 过程。 1 . 2 . 1? 视见区裁剪算法 3维真实感场景模拟中, 一般要处理和渲染大 量数据, 会占用大量 CPU 和 GPU时间, 势必影响实 时模拟的效率。为提高绘制和处理效率, 满足实时 1128?中国图象图形学报第 15卷 模拟要求, 应先实施裁剪。一般采取基于视见体的 裁剪方法, 把视见体之外的不可见部分剔除, 不做后 续处理。采用一种改进的基于视见体裁剪的方法, 具体来说, 就是要根据视见体 6个面的几何方程, 逐 一判断每个图元 (顶点, 多边形或多面体 )是否在视 见体之内, 如果在视见体内, 则显示; 否者, 则剔除。 如果正好与视见体相交, 则显示该整个图元。因若 拆分原来的基本图元单位, 需作求交运算, 得到小于 基本图元的图形, 造成数据管理上的不便, 并降低了 时间效率, 因而, 论文把所有相交图元均保留, 提高 了效率, 并保证了图元的完整性。显示图元数目略 多于实际应显示数目, 保证了视觉完整性和数据管 理效率, 提高了渲染效率。 因处理的数据是 DEM 栅格数据, 所以裁剪方法 作了如下处理: 以往算法大多只能以立方体为单位处理, 这里 加以改进扩充, 可以处理以任意长方体为单位的基 本图元, 但裁剪时仍使用立方体裁剪。 图 1? 远视图 Fig . 1? The far vie w 裁剪立方体的表示方法定义如下: 立方体图元 用中心点和裁剪半径表示, 中心点的高程值为中心 点及其 4个角点中高程最大最小值之和取平均, 令 两个坐标为栅格点原中心坐标, 其裁剪半径取为长 方体中长宽高中最大长度的一半, 这样可保证该立 方体完全包含所要绘制的 DE M 网格。 裁剪时以上述立方体为单位, 依次判断任一这 样的立方体的 6个顶点是否在视见体内, 并规定只 要有一个点在视图体的内部, 则该立方体就认为在 视见体内应予以绘制, 所有的顶点全在视图体的外 部时则认为该立方体不可见。 运用本算法对 DEM 进行裁剪, 结果证明, 该算 法裁剪所得视觉效果良好, 效率较高。 1 . 2 . 2? LOD简化模型 根据人眼的视觉成像原理, 人的眼睛对近处的 景物比对远处的景物敏感, 对视线正对的景物比斜 视的景物敏感。并且根据曲面论原理, 平坦的曲面 部分可以粗略划分即可忠实表达原曲面。由此, 对 DEM 进行简化, 建立了符合视觉原理的层次细节模 型, 提高了显示的效率。其原理描述如下: 距视点距离远, 则根据距离合并相邻栅格, 使显 示栅格大小正比于距离, 相应的分辨率递减。 由曲面的粗糙程度, 平坦的则合并栅格, 相应分 辨率递减, 反之分辨率递增。 由视觉原理, 正视的景物比斜视的景物清晰, 斜 视根据角度合并栅格, 分辨率减小。 综合以上因素, 建立多分辨率模型。对项目区 数据测试结果的显示效果如图 1 , 图 2 。 图 1和图 2分别是从两个不同位置但同一方向 的视点所看到的远近模型视图, 相对于远处突起的 部分, 图 1为远视图, 图 2为近视图, 从图中可以看 到, 随着视点的前移, 网格被加密, 且平坦处的分辨 率低于粗糙处分辨率。 数据测试证明, 针对该实例, 视区裁剪并简化之 后的模型比裁剪之前的栅格数目绘制的图元数可减 少约高达 97?896 %。极大提高了绘制效率。 1 . 2 . 3? 裂缝修补及纹理融合 因同一场景相邻部分使用了不同分辨率, 交界 地方就会产生所谓的裂缝, 影响视觉效果, 所以必须 对裂缝进行修补。设计了简单的修补方法, 该方法 第 7期闫长青等: 高精度高速度曲面建模的 3维地表模拟和漫游算法1129? 图 2? 近视图 F ig . 2? The near vie w 实用高效。具体如下: 依次取待显示的图元, 判断其周围网格, 如果周 围某网格或图元相邻的某图元分辨率较小, 则在其 相应的边上增加顶点, 顶点增加个数根据其分辨率 相差的等级而定。 纹理融合一般采用贴上相应的地物纹理来实 现, 但贴图间的过渡不自然, 要想实现真实感模拟, 必须实现纹理之间的自然渐变融合。解决方案是: 根据某种植被的决定因素而决定该种植被和其他植 被混合时所占部分的大小。首先找出各种植被的决 定因素的量化指标 26; 然后根据此指标计算该种植 被所占的混合比例, 再根据混合比例来进行纹理混 合; 最后把混合之后的纹理加到相应的地貌上边。 OPENGL提供 了一个 方便 的实 现方法, 称之为 ALPHA混合, 颜色可用 4个分量表示, 红、 绿、 蓝和 ? ALPHA, 其中 ALPHA代表透明度或者原来纹理颜 色所占的成分。使用纹理混合时, 可用红、 绿、 蓝取 相同的值控制第 1种纹理所占混合比例, 用 ALPHA 控制二者混合后再和第 3种纹理混合时所占的混合 比例, 如果再有其他地貌, 可以依次混合下去。 1 . 3? 任意方向的漫游算法 要想绕任意方向漫游, 首先要解决的问题是绕 任意轴的旋转问题, 这里主要包括绕垂直方向的旋 转问题, 以及垂直于身体和视线 (一般指垂直于竖 直方向和视线方向所确定平面 )轴向的旋转。绕任 意轴旋转的方法一般来说有两种, 矩阵乘法和四元 数的方法 27, 其中多用矩阵乘法。 根据计算机图形学原理, 绕任意轴 n旋转角度 ? 的方法, 可以分解为分别绕 3个坐标轴的旋转, 其 最终旋转矩阵为 R= nxnx( 1- cos( ? ) + cos( ? )nxny(1- cos( ? ) + nzsin( ? )nxnz(1- cos( ? ) - nysin(?) nxny( 1- cos( ? ) - nzsin(?)nyny(1- cos(?) + cos(?)nynz(1- cos( ? ) + nxsin(?) nxnz(1- cos(?) + nysin(?)nynz( 1- cos( ? ) + nysin( ? )nznz(1- cos(?) + cos( ?) ? ?( 1) 点 (x, y, z)绕 n轴旋转 ?角后所得点 (x! , y! , z!)可以 这样求得: X!= RX( 2) 式中, X= (x, y, z), X!= (x! , y! , z!), nx, ny, nz分别为 标准化的旋转轴分量。具体算法如下: 首先求出从视点到视线上任一点的待旋转向 量, 然后左乘前边的旋转矩阵, 得新的旋转向量。 俯视和仰视的实现算法如下: 首先用竖直向量和视线向量进行叉乘运算求得 旋转轴 , 然后用所得向量左乘旋转矩阵, 得新的视 线向量。 2? 算法流程及实例模拟 算法流程描述如下: 1) 用 HASS M 构建 DEM; 2) 经视景体裁剪取稍大于可视范围的数据; 3) 动态加点进行实时构建高精度 DEM; 1130?中国图象图形学报第 15卷 4) 视见体裁剪只取可视范围内 DEM; 5) 细节层次简化; 6) 添加地物及地面纹理并渲染; 7) 任意方向漫游; 8) 根据漫游方向加点或减点更新高精度 DEM; 9) 转步骤 2)循环。 步骤 2) 为首次裁剪, 计算量稍大且可以预处 理, 不会影响算法效率; 步骤 4) 只对稍大于显示数 据的数据量裁剪, 效率较高; 步骤 8) 因可用栅格数 据顺序存储易更新取得较高效率。 OPENGL是用于真 3维表达的图形函数库, 跨 平台, 效率较高, 可方便实现真 3 维编程 28, 而 C+ 编程效率也较高, 尤其可高效处理有关内存的 分配, 因而选用 VC+ + 和 OPENGL 实现了上述算 法, 并进行了真实感地表模拟。 甘肃庆阳市董志塬地区介于东经 10739!? 10805! , 北纬 3528! ? 3540! 。地处泾水以北, 马 莲河和蒲河之间。南北长 87 km, 东西宽 36 km, 总 面积 2 778 km 2。项目区主要有塬、 墚、 峁等典型黄 土高原地貌, 地形复杂, 非常适合算法实验研究。测 试用例的 DEM 选用了项目区的高程图。分别用 40m, 20m和 10m的栅格大小, 分辨率分别为 1 143 # 2245 , 2284# 4 470 , 4 567 # 8 939 , 相应数据量的大小 分别为 10M, 40M 和 156M 的栅格图像, 进行了测 试。测试结果表明, 用 10m栅格, 数据量达到 156M 时, 本文算法仍然能达到较高的效率, 帧速可达到 55帧 /s以上, 给用户呈现了连续性较好的, 有较强真 实感的场景。最终效果如图 3? 图 5所示。 图 3? 屏幕场景 1 F ig . 3? The first screenshot 图 4? 屏幕场景 2 Fig. 4?Screenshot 2 第 7期闫长青等: 高精度高速度曲面建模的 3维地表模拟和漫游算法1131? 图 5? 屏幕场景 3 Fig. 5?Screenshot 3 3? 结 ? 论 引入高精度高速度曲面构建方法, 动态构建 DEM, 构建视点依赖的 LoD模型, 进行 3维地表模 拟及漫游, 可见场景动态更新。首先构建 DEM, 然 后进行视图体裁剪, 根据视点的距离、 曲面的平坦程 度及视角进行简化, 再采用纹理融合进行真实感地 形场景建模, 接着进行场景漫游, 在漫游过程中根据 视线方向再动态加点、 动态减点进行 DEM 重建, 最 后重建真实感地形场景, 依次重复。一方面, 从理论 上来说, 视区内重建 DEM 所涉及的范围小, 所需计 算量小, 而 HASS M方法采用矩阵分解, 在保留原重 建信息的基础上, 最大限度地提高建模速度, 实时构 建高精度曲面基本不影响整个算法的效率; 另一方 面, 解决了 3维地表的精度问题, 因为本身需读入内 存的数据较少, 且用栅格组织数据, 从而为大规模场 景重建解决了存储组织的问题。而实验结果也表 明, 算法建立的 3维地表模拟准确, 真实感强, 显示 效率高。下一步的工作是, 在算法的基础上, 对大规 模复杂场景重建进行研究, 实现数据的动态调度, 集 成大规模的矢量数据, 以支持大规模复杂场景重建。 参考文献 (References) 1 ? Pajarola R. Large scale terrain v isualization using the restricted quadtree triangulation C / /Proceedings of V isualization 98. LosA lamitos . CA, U SA:IEEE Computer Society Press , 1998 : 19?26 . 2 ? L indstrom P,Pascucci V.V isualization of large terrains made easy C / /Proceedings of the Cconference on V isualization 01 . W ashington .DC, USA:IEEE Computer Society,2001 :363? 370. 3 ? L indstromP,Koller D,R ibarsky W,et a. lReal ?ti me , continuous level of detail rendering of height fields C / / Proceedings of the 23rdAnnualConference onComputerGraphics and InteractiveT echniques . N ew York . NY, USA: ACM, 1996 : 109?118 . 4 ?Jin H L,Lu X P,L iu H J .V iew?dependent fast real ?ti me generating algorithm for large?scale terrain J.Procedia Earth and P lanetary Science , 2009 , 1( 1): 1147?1151 . 5 ? Hoppe H.Smooth view?dependent level?of?deta il control and its application to terrain rendering C / /P roceedingsV isualization 98 ( Cat .No. 98CB36276 ).Los A lam itos .CA,USA:I EEE Computer Society P ress , 1998 : 35?42 . 6 ? Hoppe H.V iew?dependent refinement of progressive meshes C / /Computer G raphics Proceedings ,SIGGRAPH 97.Los Angeles . CA U SA: ACM, 1997 : 89?98. 7 ? Ducha ineau M, W olinsky M,Sigeti D E,et a. lROAM ing terrain : Real?ti me opti mally adapting meshes C / /Proceedings . V isualization 97 ( Cat .No. 97CB36155).Phoenix.Arizona , United States :I EEE Computer Society Press , 1997 : 81?88. 8 ? De FlorianiL, M ag illo P. Puppo E V ariant : A system for terrain modeling at variable resolution J.GeoInfor matica,2000 , 4( 3): 287?315. 9 ? C ignoni P,Ganovelli F,Gobbetti E,et a. lBDAM?Batched dynam icadaptivemeshesforhighperfor manceterrain visualization J.Computer Graphics Forum,2003 ,22( 3 ): 505?514 . 1132?中国图象图形学报第 15卷 10 ? Zhang L, Yang C, L iuD, et a. l A web? mapping system for rea l ? ti me visualization of the global terrain J.Computers & Geosciences , 2005 , 31( 3): 343?352. 11 ? Zhang L Q, Yang C J , Tong X H,et a. l V isualization of large spatial datain networking environments J.Computers & Geosciences , 2007 , 33( 9): 1130?1139 . 12 ? Zhang L Q, Guo Z F, Kang Z Z,et a.l W eb?based visualization of spatial objects in 3DG I S J.Sciencein China Series F?Infor mation Sciences , 2009 , 52( 9): 1588?1597 . 13 ? L iQ Q, W ang Z, Yang B S . Multi?resolution representation of dig ital terrain models with terrain features preservation J. Sciencein China Series E? Technological Sciences ,2008, 51( supp . 1): 145?154 . 14 ? Y ang B , ShiW,Li Q. An integrated T I N and Grid method for constructingmulti?resolutiondigitalterrainmodels J . International Journal ofG eographical Infor mation Science, 2005 , 19( 10): 1019?1038. 15 ? Y ang B S, ShiW Z, L iQ Q. A dynam ic method for generating multi?resolution TI N models J.Photogrammetric Eng ineering and Remote Sensing, 2005 , 71( 8): 917?926 . 16 ? Wang Shiha, i Yue T ianx iang.Research on 3D visualization of v irtual terrain inHAS M J. G eomatics and Infor mation Science ofWuhanUniversity, 2009 , 34( 1): 64?67 , 71 . 王世海, 岳天 祥. 高精度曲面建模的三维地形可视化研究 J. 武汉大学 学报: 信息科学版, 2009 , 34( 1): 64?67, 71 . 17 ? Hoppe H.Efficient i mple mentation of progressive meshes J. Computers& G raphics? Uk ,1998, 22( 1): 27?36 . 18 ? Hoppe H.Progressive meshes C / /ComputerG raphics Proceedings .SI GGRAPH 96. N ew Orleans . LA USA:ACM, 1996 : 99?108 |528 . 19 ? ChenChuanfa ,YueT ianx iang.DEMconstructionand application based on HASM J .Geo?Infor mation Science, 2009 , 11( 3): 319?324 . 陈传法, 岳天祥. 基于 HAS M 算法 的 DEM 建模与应用试验 J. 地球信息科学学报,2009, 11( 3): 319?324 . 20 ? Song Y injun, Yue T ianx iang. H igh accuracy surface modeling based on multigrid method J.G eomatics and Infor mation Science ofW uhan University, 2009, 34( 6):711?714 . 宋印 军, 岳天祥. 基于多重网格法求解的高精度曲面建模模型 J. 武汉大学学报: 信息科学版,2009, 34( 6): 711?714. 21 ? Yue T ianxiang , Du Zhengping. H igh accuracy surface modeling (HASM3): A key module in the new generation GIS and CAD J. Progress in Natural Science , 2005, 15( 4): 41?50 . 岳天 祥, 杜正平. 高精度曲面建模: 新一代 G IS与 CAD的核心模 块 J. 自然科学进展, 2005 , 15( 4): 41?50. 22 ? Yue T ianx iang,Du Zhengping. Numericaltest for selecting the opti mu