摘 要

地形渲染是图形学领域的热点问题，在模拟仿真应用中随着对沉浸性和仿真性的追求，地形渲染的速度和精度要求也在提高。虽然图形显示的硬件条件已经取得了巨大的发展，但我们还需要软件的处理才能达到应用的要求。而加快地形渲染速度是最为关键的要求。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帧左右，这对大规模地形的实时渲染提出了很大的要求。

OpenGL作为一个性能优越的图形应用程序设计界面，广泛适用于计算环境，从个人电脑到工作站，OpenGL都能实现高性能的三维图形功能，其优秀的可拓展性成为了目前三维图形的开发标准。

1.2 研究的意义

虚拟仿真技术是对真实的自然环境进行逼真模拟的人机交互技术，在虚拟仿真场景中常要求能够展现出场景的动态特性，也就是及时更新的动态画面。而评价虚拟仿真场景效果的有两个重要指标：一是动态特性，FPS是反映动态特性最直观的表现，成品虚拟仿真场景的最低标准应该是每秒30帧左右，否则人类观看会产生严重的不连续和跳动感；另一个是交互延迟，系统的图像生成系统对用户的交互动作做出反应的延迟应该不大于0.1秒。以上两种指标军依赖于系统生成图形的速度。图形生成速度的快慢对模拟仿真环境的构建产生了极大的影响。

图像的生成速度取决于图形处理的软硬件体系结构，特别是硬件加速器的图形处理能力和生成图像的加速技术。虽然现在图形工作站的工作性能由于高速发展的CPU和GPU性能得到很大的提高，但却不能满足日新月异的图像处理需求。模拟仿真对于场景的复杂度可以说是没有限制，所以要想实时生成高质量图形，要从更容易实现的软件着手，在不影响场景精确的情况下减少图形画面的复杂度。

虚拟场景中构建地形网络的三角形树目极其巨大，所以如果想在这样的仿真环境中保持较高的交互帧数且不会明显降低图像质量是很困难的。解决的办法必须是设计高效的算法，用恰当的数据结构组织海量的地形结构和数据，在实时交互漫游时动态改变地形网格的表现层数，增强场景真实感。本论文从这一解决方案出发，对两种层次细节算法进行研究，并对其中一种算法进行改进。

1.3 国内外研究现状

LOD（Levels of Detail细节层次）的提出是在1976年，Clark认为物体覆盖屏幕较小区域时可以使用该物体描述较粗的模型，以便对复杂场景进行快速绘制。在90年代初，图形学关于虚拟现实和科学计算可视化的革新中被作为图形生成加速的手段之一，进而全世界掀起了对LOD技术研究的热潮。1996年P.Lindstrom第一次实现了视点的连续层次细节算法，他们使用基于四叉树的边剖分方法来表现地形网格，该算法的框架为自底向上的迭代合并三角形，是屏幕投影误差不停地接近阈值直至超过，进而减少构建地形系统的三角形数目。在此基础上，Duchaineau等又提出了ROAM算法，是和四叉树相反的自顶向下自适应剖分，采用的是三角形二叉树形式来表现地形网络，它的主要特点是在三角形之间建立现实的相邻关系，强制的避免了裂缝。

近几年来随之GPU硬件条件以及可编程能力的提升，个人电脑对三维图形算法的处理更为迅速，现在更多的利用GPU的显存从而减少CPU三角形化时的负载。Hoppe提出了在geometry clipmaps技术基础上的基于GPU硬件加速的静态多分辨率地形渲染算法。这种算法在摄像机移动时，clipmap层次改变并且不断重新填充数据，因此也有着渲染过程更为复杂的缺点。J.Schneider等实现了基于GPU的高质量地形渲染，该方法用“0区域多边形”来填充裂缝，并用GPU编程来解码顶点，是GPU编程的一大进步。同事Yotam Livny等提出了另一种基于GPU的四叉树算法，他将每四个方块分为四个直角三角形，并且将其与邻居节点以分辨率的形式进行匹配，在计算量上达到了CPU与GPU的平衡。

另外还有一些顶点优化和拓扑优化的研究用于对LOD算法的简化，Will Evans和Gregg Townsent为每个顶点分配了12个字节的空间存储属性和两个字节用于存储高程数据，这样复杂的存储算法结构化了传统LOD的存储分配，使存储结构更加明确。Peter Lindstorm和Valerio Pascucci提出了新的内存索引算法和分割构造三角形带的方法。Paolo Cignoni提出的使用批处理任务模式搭建主机显卡通讯方法能够保证更好的全局几何连续性。

这些优化措施被应用于各种LOD算法中，是对算法的发展与补充，根据新图形硬件的特性来研究LOD算法在目前的图形学研究领域也是热门方向。

1.4 本文的主要内容

第一章介绍了论文问题的提出和意义以及国内外目前对LOD的研究现状。

第二章对地形编程进行了基础性概述，并对地形编程的实现提出了方案，介绍了本文中所使用的工具：高度图、Cimage类、GL_TRIANGLE_STRIP方法。