基于金字塔模型的地形网格裂缝消除算法AnAlgorithmof.pdfVIP

电子发烧友 电子技术论坛 基于金字塔模型的地形网格裂缝消除算法 An Algorithm of Avoiding Crack for Rendering Terrain Based on Pyramid Model （中国海洋大学信息学院, 青岛 266100）马纯永，陈戈，陈勇，李文 MA Chun-yong, CHEN-Ge ,CHEN-Yong, LI-Wen 摘 要 本文针对基于多分辨金字塔模型绘制海量地形时的网格裂缝问题，提出了一种网 格裂缝消除算法。该算法利用分裂标记表，结合金字塔模型本身分块与多分辨率的特性， 从整体上建立相邻节点的约束关系，控制相邻节点的深度差不超过１，进而消除网格裂缝。 实验结果表明，该算法可以有效的解决基于金字塔模型海量地形绘制中的网格裂缝问题。 关键词 金字塔模型 四叉树 裂缝消除 中图法分类号：TP391.9 文献标识码：A Abstract An algorithm is proposed to eliminate cracks when rendering large-scale terrain based on pyramid model. Considering the multi-block and multi-resolution characteristics of Pyramid Model, the algorithm, using a dividing-sign table, builds constraint relationships among neighboring nodes on the whole, makes the depth difference among neighboring nodes less than one, and thus achieves the goal of crack elimination. Results of experiments show that cracks introduced when rendering large-scale terrain based on pyramid model are effectively eliminated using this algorithm. Keywords pyramid model, quadtree, crack elimination 11 引 言 大规模地形绘制是虚拟城市的重要组成部分，利用数字高程模型（DEM）结合高清晰卫 星或航拍图生成三维虚拟地形是现在比较常用的实现方式。然而对于海量地形，由于硬件限 制，不能将所有的数据一起导入内存进行实时绘制，因此需要采用合理的地形数据组织方式 和有效的加速算法。采用多分辨的金字塔模型[1]来组织地形，被证明是一种合理有效的实现 方法。 采用金字塔模型(multi-resolution hierarchy)来绘制地形，需要把地形的网格数据分 为很多块，然后根据视点的位置选择合适的数据进行拼合。渲染时，不可避免的会因为块内 或块间相邻节点的分辨率不同而产生大量的网格裂缝，影响仿真效果。 [2]；（2）有向无环图 针对网格裂缝问题，目前已有多种解决办法：（1）限制四叉树法 [3] [4] （directed acyclic graphic, DAG）法 ；（3）垂直边缘填充方法 。 其中限制四叉树在构造四叉树的过程中给每个顶点设立约束关系，从而在每个树节点绘 制的时候根据约束关系来激活相应的顶点。该约束关系保证相邻节点之间级数差不超过 1。 但是该方法适用于单块地形的绘制，不适用于地块的动态拼合；而基于 ROAM 算法，依据顶 点引入次序地有向无环图中的依赖关系来消除裂缝，可以拼合许多地形块，但无法解决不同 分辨率的地形块间的拼合问题；垂直边缘填充方法容易造成接缝处陡峭的现象。 本文借鉴限制四叉树的思想，通过给地理位置相邻的节点之间建立一定的约束关系，保