一种基于不完全四叉树的LOD生成算法

芮小平

doi:10.11834/jig.200509210

学术论文与技术报告 | 浏览量 : 0 下载量: 191 CSCD: 0

PDF
导出
分享
收藏
专辑

一种基于不完全四叉树的LOD生成算法
A LOD Algorithm Based on Unfull Quadtree
2005年10卷第9期页码：1152
纸质出版：2005
DOI： 10.11834/jig.200509210
稿件说明：

移动端阅览

芮小平. 一种基于不完全四叉树的LOD生成算法[J]. 中国图象图形学报, 2005,10(9):1152. DOI： 10.11834/jig.200509210.

A LOD Algorithm Based on Unfull Quadtree[J]. Journal of Image and Graphics, 2005, 10(9): 1152. DOI： 10.11834/jig.200509210.

摘要

为了实时地绘制大规模地形数据

提出了一种改进的实时连续LOD生成算法。该算法首先采用Mortan码的编码方式对地形数据进行简化

并利用不完全四叉树存储简化后的高程数据;然后根据视点位置和网格空间对象误差的关系建立基于不完全四叉树的LOD模型

同时采用逐层找邻法调整不同层次之间的裂缝

并给出了寻找不同类型邻居的实现过程;最后采用背面剔除算法将起伏地形的不可见部分去除。实际编程时

由于采用了H ilbert填充曲线方式存储四叉树结点

并采用隔层四叉树方式访问结点数据

从而提高了大规模地形的绘制效率。使用该方法描述荆江地区的地形

取得了良好的绘制效果。

Abstract

In order to render massive terrain data in real time

this paper presents an improved LOD algorithm.This algorithm firstly simplifies the DEM data by using Mortan coding principle and stores the simplified data with an unfull quadtree.Then

it builds the real-time continuous Lod based on this unfull quadtree according to the relationship between viewer position and grid object space error.The authors bring out a method named "find the neighbors layer by layer" to patch the cracks between different layers and the procedures to find the different type neighbors are presented in this paper.Finally

it wipes off the invisible grids through back-culling algorithm.In order to improve the rendering speed

it uses Hilbert filling curve method to store and interleaved quadtree method to access the unfull quadtree nodes.The authors use the improved method to simulate the terrain of Jingjiang area and obtain a good effect.