摘 要

地形渲染是图形学领域的热点问题，在模拟仿真应用中随着对沉浸性和仿真性的追求，地形渲染的速度和精度要求也在提高。虽然图形显示的硬件条件已经取得了巨大的发展，但我们还需要软件的处理才能达到应用的要求。而加快地形渲染速度是最为关键的要求。LOD技术通过舍弃不必要的细节来减轻了地形系统的网格规模，他可以在不影响画面对人类视觉的影响情况下，逐步减少绘制地形系统的三角形来提高渲染的效率，他保证了近距离的物体采用高分辨率，而远距离的物体采用低分辨率，是目前最为有效的优化技术。

本文主要对地形编程和LOD渲染算法进行实现和改进。在第二章介绍了采用的地形生成算法和地形网格顶点的设计方案，并在第三和第四章分别阐述了四叉树算法和ROAM算法的数据结构设计以及实现。第五章是对四叉树算法的裂缝问题提出了讨论并给予了消除方案，并进一步讨论在四叉树的生成时就进行裂缝消除的限定四叉树想法，并给出了修改四叉树数据结构的意见，通过限定顶点生成的条件来实现裂缝消除。

关键字：LOD、地形、四叉树、ROAM、限制四叉树

Abstract

Terrain rendering is a hot topic in the field of graphics, in the simulation application with the immersion and simulation of the pursuit of terrain rendering speed and accuracy requirements are also improving. Although the graphics display hardware conditions have made great progress, but we also need to deal with the software to meet the application requirements. And speed up terrain rendering speed is the most critical requirements. LOD technology to reduce the terrain system by discarding the unnecessary details of the grid size, he can not affect the screen on the impact of human vision, the gradual reduction of the terrain system to improve the rendering of the triangle to improve the efficiency of rendering, he assured the close Of the objects using high resolution, and long-range objects with low resolution, is the most effective optimization technology.

This paper mainly realizes terrain programming and LOD rendering algorithm and improves. In the second chapter, the design scheme of terrain generation algorithm and the topography of terrain mesh is introduced. The data structure design and realization of quadtree algorithm and ROAM algorithm are described in the third and fourth chapters respectively. In the fifth chapter, we discuss the crack problem of the quadtree algorithm and give the elimination scheme, and further discuss the quadratic tree idea of ​​crack elimination when the quadtree is generated, and give the modified quadtree Data structure of the views, by limiting the conditions generated by the vertex to achieve crack elimination.

Key words: LOD,Terrain ,QuadTree,ROAM,Limit quadtree

目录

1 绪论 5

1.1问题的提出 5

1.2 研究的意义 5

1.3 国内外研究现状 6

1.4 本文的主要内容 7

2 地形编程 7

2.1 高度图 7

2.2 Cimage类 7

2.3顶点处理 7

2.3.1 定义顶点 8

2.3.2 顶点索引 8

2.3.3 基于顶点缓冲和索引缓冲创造建地形 9

3 四叉树算法 10

3.1 LOD技术 10

3.1.1 LOD技术简介 10

3.1.2 LOD模型的实现方法 10

3.2 四叉树算法数据结构 11

3.2.1 四叉树的概念 11

3.2.2 四叉树的层次编号 11

3.2.3 数据存储 12

3.3 生成四叉树 13

3.4 实时动态网格的渲染 13

4 ROAM算法 14

4.1 ROAM简介 14

4.2 ROAM数据结构 14

4.3 生成二元三角树 16

5 四叉树算法的改进限制四叉树算法 16

5.1 裂缝的出现 16

5.2 LOD层级大于1时的解决方案 18

5.2.1 算法设计 18

5.2.2 数据存储与管理 19

5.2.3 消除裂缝 19

5.3 限制四叉树 20

5.3.1 限制四叉树的提出 20

5.3.2 限制四叉树数据结构 20

5.4 限制四叉树算法实现 20

结论 20

参考文献 20

1 绪论

1.1问题的提出

可视化技术是图形生成和图像理解相结合的一种技术，它赋予了人们一种仿真的、三维的并且具有实时交互的能力，尤其是以可视化技术为基础发展起来的虚拟现实技术、三维仿真技术和科学计算可视化技术。它的发展极大的延伸了人类认识和驾驭世界的能力。其中最明显的是工程师可以摆脱二维平面图而进入三维世界中进行工程设计，建立实时的三维模型，在设计效果上所见即得，大大提高了设计质量和设计速度。

地形模型在虚拟仿真的应用方面是最为基础的模型之一，在仿真环境中往往需要在不同网络条件下协同完成分布式交互任务，这就要求在客户端计算机上实时的反映不同角色所在的三维场景，以致于需求大规模三维虚拟场景的实时切换和漫游。但是，在大规模复杂场景的很多应用领域中，上百万的多边形才能组成一个地形模型，地形数据极其庞大，超过了目前图形实时绘制和内存管理能力，我们往往需要花费大量实现渲染精致的画面。而地形的实时显示要尽量保持在30帧左右，这对大规模地形的实时渲染提出了很大的要求。