张 俊 峰，孙 大 鹏，许 德 合

（华北水利水电大学资源与环境学院，河南 郑州 450045）

从数据基础考虑，当前的地形三维细节层次显示可分为基于规则格网RSG的LOD算法和基于不规则三角网TIN的LOD算法。由于RSG结构简单，是地形三维显示的研究重点，国内外三维软件大都以此为基础进行地形的虚拟展示，但其数据本身固有的冗余度大、表达不够精确的问题始终无法避免［1－3］；TIN的LOD算法是一种约束较少且自由度高的地形三角化方法，但由于构网的全局性和拓扑的复杂性，当前还没有一个较为完善的算法能实现基于TIN的大范围地形自适应LOD显示［4－7］。笔者将地貌综合的三维 Douglas-Peucker（3D＿DP）方法引入地形LOD中，通过构建基于四叉树的TIN模型（Quad＿TIN），以结合四叉树在地形动态模拟中的快速性和TIN的准确性，提出了一种针对三维离散点的地形实时自适应LOD的新算法。

1 算法设计

本文的LOD算法针对大规模三维离散点的视相关自适应表达，在已有算法基础上，通过3D＿DP和地形分块，从全局角度确定每一个离散点的重要性等级，再运用Quad＿TIN结构构建地形块内离散点的四叉树模型，最后结合可见性判断和增量更新机制，实现大数据量的快速自适应漫游。算法关键在于离散点的全局重要性判断和数据的高效组织上。

1.1 3D＿DP算法提取特征点的分块加速法

3D＿DP算法从空间分布的三维离散点集出发，通过指定初始原点和初始基平面作为获取特征点的视点和视平面，提取当前情况下最有意义的特征点集，再利用递归算法不断变换视点和视平面得到最终的空间特征点集［8－10］，其基本算法原理如图1所示。……