保持边界的地形网格简化算法与组织格式  

Simplification Algorithm and Format Organization for Terrain Grid Based on Holding-Boundary

作　　者：刘思江[1] 翁璐斌[1] 秦树鑫[1] 杨一平[1] 蒋永实[1] 

机构地区：[1]中国科学院自动化研究所综合信息系统研究中心,北京100190

出　　处：《计算机辅助设计与图形学学报》2013年第1期74-80,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61005067)

摘　　要：针对目前大范围地形绘制中对地形块间裂缝进行图元级精确修补会额外占用计算机资源,或者进行简单视觉掩饰而导致几何与纹理空间缺乏连贯性的问题,基于Melax快速网格简化算法,提出了保持边界的边折叠地形简化算法.首先定义了保持点与控制点概念,给出保持点的数量选择方法与控制点的精简策略,并通过改进边折叠规则和代价计算公式实现了边界不变的网格简化;然后按聚类层次结构表示思想,将简化网格与原规则网格层叠组织,以顶点索引方式保证地形整体快速批量操作,构造出一种具有保持边界特性的地形格式.实验结果证明,该算法在保持地形边界的同时,能有效地缓解边界图元稠密现象,且比Melax算法更好地保留了地形特征;在此基础上形成的地形格式,在飞行模拟测试中既可保证较高帧率,又显示出无缝拼接平滑过渡的良好视觉效果.To deal with cracks between terrain blocks, one approach is to repair them precisely on primitive level, which consumes much computing resource, while another masks them visually, causing incoherence in geometric and texture spaces. Based on Melaxs fast polygon reduction algorithm, a terrain simplification algorithm was proposed that used holding-boundary and edge collapse. Firstly concepts of holding vertex and controlling vertex were defined, and quantity choice of holding vertex and reduction strategy of controlling vertex were provided. By improving edge collapse rules and cost formulae, grid simplification with fixed boundary was realized. Then according to the clustering hierarchy representation, simplified grids were overlapped with original regular grids, using vertex indices to ensure fast and batched terrain manipulations. Thus the terrain format featuring holding-boundary was presented. Experiment results show that the proposed algorithm can lower densities of boundary primitives and maintain more terrain features; the terrain format shows high frame rate and seamless visual effect in flight cruising test.

关 键 词：裂缝避免 保持边界 地形简化 规则网格 不规则三角网 层次结构 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]