您的当前位置：首页虚拟现实中三维复杂几何形体的层次细节模型的研究

虚拟现实中三维复杂几何形体的层次细节模型的研究

来源：锐游网

中国科学院软件研究所博士研究生学位论文

虚拟现实中三维复杂几何形体的

层次细节模型的研究

姓名：刘学慧导师：吴恩华研究员专业：计算机软件

一九九八年一月

分类号ＵＤＣ

密级编号

学位论文

虚拟现实中三维复杂几何形体的

层次细节模型的研究

指导教师姓名

申请学位级别

论文提交日期

学位授予单位和日期

评阅人

答辩委员会主席

中国科学院软件研究所

1997年12月

论文答辩日期

1998年1月

博士学位

专业名称

计算机软件

吴恩华

研究员

北京100080

刘学慧

中国科学院软件研究所

本文工作得到

国家自然科学基金重点项目

“真实感图形的事实生成与显示技术”

和

国家863计划重点项目

“基于分布交互仿真的虚拟现实系统研究”

的资助

摘要

虚拟现实技术是一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界面技术。图形的实时生成是VR成为“现实”的关键技术之一。本论文围绕层次细节模型技术这一有效的图形生成加速方法展开了有益的探索，研究各种LoD模型生成方法及实时绘制技术。研究成果包括以下几个方面：1)提出一种新的渐进网格模型的生成方法和表示形式，并提出新的非规则网格LoD模型的实时绘制方法。2)以焦点以及显示面积二者有效的结合建立较为精确的视觉空间模型，改进基于均匀网格表示物体的LoD模型的实时生成及绘制技术。3)提出一种基于辐射度全局光照网格模型的简化方法。全文共分五章。

第一章简单介绍了VR的基本概念、主要特点。对虚拟环境图形生成的各种加速方法作了较为全面的综述，同时阐明了虚拟现实中LoD模型自动生成和绘制技术的研究内容和应用价值。就LoD模型技术的各个相关方面：LoD模型的选择尺度、LoD模型的平滑过渡、LoD模型的选择算法以及LoD模型的自动生成进行了深入的研究，回顾了国内外的研究状况。本论文就各种LoD模型生成方法及实时绘制技术进行了一些尝试和探索，取得了一些成果。下面逐章进行介绍。

以几何元素删除实现模型的简化是多细节层次模型自动生成的常用方法。但由于复杂模型庞大的数据量以及模型简化复杂的计算，使得以往的LoD模型生成方法只能预先产生多个间断的简化模型，从而引起实时绘制时图形画面的跳跃。为解决这个问题，人们相继提出了渐进网格模型概念以及三维复杂模型的实时连续的多分辨率绘制技术。本文提出一种新的渐进网格生成方法和表示形式。该算法记录下整个模型简化过程中顶点删除的信息，并利用顶点删除与模型面片个数的对应关系，建立起渐进网格的表示形式。利用这种渐进网格表示形式我们实现了三维复杂模型的实时连续多分辨率绘制。

地表模型在虚拟现实中有着广泛而重要的应用。非规则网格模型和均匀网格模型作为地表等数字化高度场模型的两种表示形式，在以往的地表模型的层次细节模型生成算法中有着各自独立的特点。Linstorm结合非规则网格表示的高效性和均匀网格模型良好的自适应性，提出一种地表模型的实时连续多分辨率绘制方法。但该方法忽略了人眼对处于不同视觉区域的模型细节的不同分辨能力，对处于不同视觉区域的模型赋予相同的细节，这必然带来图形生成的浪费。本文提出具有聚焦因子的基于图象空间误差的地表模型消减算法，以焦点以及显示面积二者有效的结合建立较为精确的视觉空间模型，以此模型衡量人眼对由于面片合并所带来的误差的分辨能力，并以此作为地表模型细节的重要度评价尺度，有效地简化了地表模型的绘制。同时，算法结合均匀网格模型的多分

辨率细节层次模型，以“块”作为地表模型大面积简化的空间单位，加速地表模型的简化操作，以实现较为复杂的地表模型的实时绘制。

物体表面的光照颜色纹理不仅为人类提供了丰富的视觉效果，而且为人类提供了丰富的形体、邻近及遮挡等视觉效果。但全局光照模型的计算结果往往导致模型复杂度几十甚至几百倍的增加。本文结合辐射度全局光照模型的计算特点，提出一种辐射度全局光照网格模型的简化方法。该方法根据人眼的视觉特点和辐射度计算特点，以最大相对变化值为准则，以面片合并简化操作将最大相对变化在用户定义范围内的面片合并起来，实现辐射度全局光照网格模型的第一步简化，并以原模型顶点的RGB值的变化进一步加大辐射度网格模型的简化，建立起整个环境具有辐射度全局光照效果的多细节层次模型。本算法不仅有效地简化了辐射度全局光照网格模型，而且能较好地保持原光照网格模型的特征。

最后，论文对作者的工作作了总结，并根据当前目前的研究结果提出了进一步的工作方向。

关键词：虚拟现实，细节层次模型，网格模型简化，实时连续多分辨率绘制，地表模型，

视觉模型，全局光照模型，全局光照网格模型

Abstract

Virtual Reality(VR) is an advanced man-machine interface which allows the behaviors of the human being, such as viewing, listening and touching, to be conducted in a natural but virtual environment. Graphics rendering is one of the key techniques for VR. In this thesis, the generation and rendering of models at multiple level of detail(LoD), one of the most efficient methods to accelerate graphics rendering in virtual reality, is studied and achieve some new results, which include Chapter 1 firstly describe the basic concepts and primary characters of VR system, and give a systematic survey on various method for accelerating graphics rendering in VR. At the same time, the importance associated with LoD models is emphasized. After addressing the research contents associated with LoD model, including switch between models at different levels of detail, threshold and heuristics for selecting models at multiple level of detail and method to automatic generate models at multiple level of detail, it review the development of methods of automatic generation and rendering of models at multiple level of detail(LoD), covering previous works, key techniques and main result. Here, we concentrate our research on the generation and rendering of models at multiple level of detail(LoD) and some new results are achieved.

Deleting basic geometric element, such as vertex, edge and polygon, to simplify the original complex mesh is one of the methods to create models at multiple level of detail. Because the extreme complexity of original model and the expensive computation of simplifying process, some key models at different level of detail are generated in advance and stored for rendering, which result in objectionable visual “popping” effect when changing between models at different level of detail in rendering. In order to solve this problem, the concept of progressive mesh(PM) and method of real-time, multi-resolution modeling and rendering of 3D complex virtual environment are proposed. Here, we present a new expression of progressive mesh and new method for constructing PM from an arbitrary mesh. As the initial mesh is simplified into an coarse mesh by applying a sequence of successive vertex removal, a sequence of detail records that indicate how to incrementally refine the coarse

mesh exactly back into the original mesh is stored. Using the relationship between number of vertex decimated and number of triangle removed, the new PM representation is get and a new algorithm for generating continuous levels of detail of a given triangle object in real-time is proposed. The experimental results showed that the methods is useful.

Terrain surface model has its important and wide-ranged application background in virtual reality. As two basic representation of terrain surface, uniform grid surface triangulation and irregular triangulation network had its own merits. By taking advantage of the two kinds of store formats for terrain surface, Linstrom et al. introduced an algorithm of real-time continuous level of detail rendering of height field that combines the large complexity reduction obtained in TIN construction and the flexibility provided by regular grid. However, the algorithm ignores the different sensibility of human vision to images on different view portion and treats all the points at the same horizontal distance alike, which generate a high constant density and waste a lot of model detail where the user is not looking. Here we present a simplification algorithm which combine size and focus criteria to capture the sensibility of human vision to image quality and provide a finer visual model to estimate the sensibility of human vision to model detail to increase the simplification of terrain surface model. At the same time, our algorithm builds the whole model into block-based multi-resolution representation and uses large scale block-based estimation to accelerate the simplification of whole model. The algorithm has been implemented for approximating and rendering digital terrain models and the experimental results show its high efficiency.

The illumination not only give rich visual expression, but also provide the visual effect of shape, vicinity and occlusion etc. But the solution to a global illumination problem consists of an illumination function for each surfaces of the original model, usually represented by an illumination meshes, which result in dramatically increase of model complexity. In this paper, we present an automatic method for simplifying the meshes produced as the solution to global-illumination problem using radiosity method. Based on the character of illumination meshes produced by radiosity and the characteristic of human eyes, maximum relative difference criteria is developed to guide the simplification process. The method consist of three steps: it firstly simplify the original meshes by merging faces and then delete the vertices on the perimeters of the merged face, last triangulate the perimeters. The algorithm not only significantly reduced the complexity of original meshes model, but also performed well to capture the coherent shadow discontinuity feature of illumination meshes. Model

simplification samples based on these method is given and good result is achieved.

Key Words: virtual reality, level of detail model, simplification of mesh model, real-time,

continuous multi-resolution rendering, terrain surface model, visual model, global illumination model, global illumination mesh

摘要 .......................................................................................................................................................... 1 ABSTRACT ............................................................................................................................................. 3 目录 .......................................................................................................................................................... 6

第一章绪论 ..................................................................................................................................... 9

1.1虚拟现实简介 ..................................................................................................................................... 9 1.2图形生成是虚拟现实的重要瓶颈 ................................................................................................... 10 1.3图形生成的加速方法 ....................................................................................................................... 15 1.3.1可见性判定 ............................................................................................................................... 16 1.3.2细节层次模型 ........................................................................................................................... 17 1.3.3动态图像加速技术.................................................................................................................... 20 1.3.4脱机计算 ................................................................................................................................... 22 1.4 LOD模型自动方法综述.................................................................................................................. 23 1.4.1 LOD模型自动生成方法 ........................................................................................................... 24 1.4.2 LOD模型的误差度量 ............................................................................................................... 27 1.5本文工作........................................................................................................................................... 29 第二章一种新的渐进网格模型的生成方法 ....................................................................................... 31 2.1相关工作........................................................................................................................................... 31 2.2基本定义........................................................................................................................................... 34 2.2.1顶点分类 ................................................................................................................................... 35 2.2.2重要度定义 ............................................................................................................................... 36 2.3算法原理........................................................................................................................................... 37 2.4实时绘制........................................................................................................................................... 38 2.5 预处理.............................................................................................................................................. 40 2.5.1预处理过程 ............................................................................................................................... 40 2.5.2顶点删除合法性检测................................................................................................................ 41 2.5.3三角剖分起点的选择................................................................................................................ 41 2.6实验结果........................................................................................................................................... 41

2.7小结 .................................................................................................................................................. 42 第三章基于图象空间判据的地表模型加速绘制技术 ....................................................................... 46 3.1 引言 ................................................................................................................................................. 46 3.2相关算法........................................................................................................................................... 49 3.2.1地表模型的均匀三角网格化 .................................................................................................... 49 3.2.2实时连续地表层次模型生成算法 ............................................................................................ 50 3.3 LOD模型选择尺度 ......................................................................................................................... 51 3.4具有聚焦因子的基于图象空间误差的地表模型消减算法 ........................................................... 52 3.4.1基于图象空间的具有聚焦因子的误差估计 ............................................................................ 52 3.4.2基于物理空间区域分块的模型简化加速方法 ........................................................................ 54 3.4.3具有时间连续性的地表模型的实时简化 ................................................................................ 56 3.4.4网格递归简化的数据结构 ........................................................................................................ 56 3.5实验结果........................................................................................................................................... 57 3.6小结 .................................................................................................................................................. 58 第四章一种辐射度全局光照网格模型的简化方法 ........................................................................... 60 4.1引言 .................................................................................................................................................. 60 4.2辐射度全局光照模型 ....................................................................................................................... 62 4.3相关工作........................................................................................................................................... 63 4.3.1具有全局光照效果的网格模型简化方法 ................................................................................ 63 4.3.2面片合并模型简化法................................................................................................................ 64 4.4算法原理........................................................................................................................................... 64 4.5主要算法........................................................................................................................................... 65 4.5.1超面的生成 ............................................................................................................................... 66 4.5.1.1合并准则 ............................................................................................................................ 66 4.5.1.2“种子”面片的选择 ......................................................................................................... 67 4.5.2超面边界的简化 ....................................................................................................................... 68 4.5.3三角化过程 ............................................................................................................................... 69 4.5.3.1多连通域转化为单连通域 ................................................................................................ 69 4.5.3.2加权的局部优化三角化方法............................................................................................. 70 4.6实验结果........................................................................................................................................... 73 4.7小结 .................................................................................................................................................. 73 第五章结束语 ....................................................................................................................................... 77

参考文献 ................................................................................................................................................ 79 作者在攻读博士学位期间发表的论文 ................................................................................................. 87 致谢 ........................................................................................................................................................ 88

第一章绪论

1.1 虚拟现实简介

随着处理器技术的大幅度提高，以及图形绘制技术、数字信号处理技术、传感技术、人机接口技术的发展，八十年代末、九十年代初国际国内形成了对虚拟现实的研究热潮[Shi94]。所谓虚拟现实技术即利用计算机生成逼真的三维视觉、听觉、触觉等感觉，使得用户可以通过使用专用设备自然地对虚拟环境中的实体进行交互考察与控制[Cruz-Neira93]。

作为一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界面技术虚拟现实技术具有两个基本特征，“交互”特征和“沉浸”特征。VR的“沉浸”特征要求计算机所创建的三维虚拟环境能使“参与者”得到全身心置于该环境的体验。VR的“交互”特征主要指“参与者”利用视觉、听觉、触觉等官能及对话、头部运动、眼动、行走等人类自然技能对虚拟环境中的实体进行交互考察与操作。

无疑，使用户对虚拟环境产生犹如身临其境的可行性技术的应用是虚拟现实走向成功的必要条件。这其中包括人工智能、计算机图形学、人机接口技术、传感技术以及高度并行的实时计算技术等，所有这些技术需要集成起来，由高性能计算机软硬件去创造一个使参与者产生身临其境、具有完善的交互功能的“人工现实”。经过几亿年的进化，人类对于所熟悉的自然环境已具有极为敏锐的感觉，对于环境的变化具有极为复杂的反馈机制。人类的视觉、听觉、前庭感觉（运动和重力感）、整体位置及躯体感觉（皮肤压力）等等作为整个集成系统的一部分而工作，它们在反馈机制的作用下相互制约，相互协调，从而使人可以在日常生活中能够感知事物和适应环境的变化。虚拟环境中任何一个环节做不好都会使用户觉得不自然，产生严重的虚假感和疲劳感，严重影响虚拟现实的“真实感”。只有在计算机技术比较成熟的今天，才使得虚拟现实成为可能。

实际上，虚拟现实的基本思想远不是今天刚刚提出来的。VR技术的起源要追述到计算机图形学之父Ivan Sutherland于1965年在IFIP会议上所作的标题为“The Ultimate Display”的报告。在该报告中，Sutherland提出了今天人们所习以为常的计算机窗口的概念，并且明确指出，这种虚拟世界的窗口要使得其世界看起来、听起来、作起来和感觉起来都是真实的。这一思想奠定了VR研究的基础。

1968年，Ivan Sutherland发表了题为“A Head-Mounted 3D Display”的论文，对头盔式三维显示装置的设计要求、构造原理进行了深入的讨论并给出了这种头盔式三维显示装置的设计原形，成为三维立体显示技术的奠基性成果。

VR的研究从六十年代到八十年代这一时期的发展是十分缓慢的。直到八十年代的后期，由于显示技术已能满足视觉耦合系统的性能要求，液晶显示技术的发展使得生产廉价的头盔式三维显示器成为可能，VR技术才得到加速发展。

VR系统的最大特点就是参与者能与计算机生成的虚拟环境进行自然的交互，能使用人类自然的技能与感知能力与虚拟世界中的对象进行交互。为了使用户产生身临其境的感觉，VR系统必须具备一些不同于传统人机系统的交互技术。这些能使人身临其境的交互技术主要有：大视角的立体显示、头部跟踪、人及姿势跟踪、三维声音、触觉反馈等技术。目前实现这些交互技术的设备主要有：头盔显示器、数据手套、三维位置传感器和三维声音产生器等。

VR系统将提供与计算机通讯的最自然的手段。它很好地将环境的计算机表示与人类进化了数万年的三维空间处理能力相匹配，从而可望成为人类认识世界和改造世界更强有力的武器。

作为一种新的技术生长点，虚拟现实技术受到国内外学者的广泛关注。为了把握VR这一高科技新技术，美、英、日及欧洲各国政府及大公司已投入巨额资金进行该领域的研究与开发工作，并已在许多领域，如远程操作、设计与规划、数据和模型可视化、教育与训练以及娱乐和艺术应用等领域显示出其良好的应用前景。

1.2 图形生成是虚拟现实的重要瓶颈

虚拟现实技术是一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界面技术，以其关键技术所支撑的多维信息空间使参与者产生高度逼真的“现实”感觉。其中，视觉通道是虚拟环境系统中最重要的接口。一般相信，人类从外界获得的信息近80%是通过人的视觉得到的。

人的视觉系统是非常敏感和严格的，任何不满足物理学和光学定律的运动视视景、任何同步不好的视频序列都会给视觉系统带来额外的刺激，严重影响虚拟环境的“现实感”。因而，对于虚拟现实的虚拟环境而言，随着参与者的活动即时产生相应的图形画面的实时图形视觉效果无疑是产生现实感觉的必要条件。

有两种重要指标衡量用户所沉浸于虚拟环境的效果和程度。其一是动态特性，其二是交互延迟特性。自然的动态特性要求每秒生成和显示30帧图形画面，至少不能少于10帧[Bryson93]，否则将会产生严重的不连续和跳动感。交互延迟是影响用户感觉的另一个重要指标。对于人产生的交互动作，如飞行模拟时飞行位置、方向的控制，系统的图形生成必须能立即作出反应产生相应的环境和场景。其间的时间延迟不应大于0.1秒，最多不能大于四分之一秒[Jones95]。否则在长期的工作中，人会产生疲劳、烦躁甚至恶心的感觉，严重地影响“现实”的效果。以上两种指标均依赖于系统生成图形的速度。对于动态图形效果而言，每帧图形的生成时间局限于30~50毫秒；而对于交互延迟，除包含对于交互输入及其处理时间外，图形生成速度亦是重要因素。显而易见，图形生成速度成为虚拟现实的重要瓶颈[Wu94]。

图形生成的速度主要取决于图形处理的软硬件体系结构，特别是硬件加速器的图形处理能力。

自八十年代图形工作站作为计算机新机种出现后，图形工作站的图形处理能力已得到很大的提高。但随着计算机图形学在各领域应用的不断扩展，人们对图形工作站的实时绘制能力提出了更高的要求。据Molnar[Molnar92]估计，以每秒30帧的画面生成速度绘制一个具有100,000个多边形的场景，图形工作站的硬件速度必须达到每秒300兆浮点计算、750兆的整数计算以及450兆次对帧存储器访问的能力。要满足日益增长的要求，图形生成的并行处理势在必行。

就每秒处理多边形的数目而言，目前仍处于研究状态的北卡大学的两种大规模并行图形工作站—PIXEL-PLANE系列机和PIXELFLOW无疑代表了当今高度并行的图形硬件加速器的最高水平。传统的图形硬件加速器一般将图形的生成过程划分为几何处理(包括视见变换、投影及裁剪等)和绘制两部分。传统的图形生成的并行处理主要利用这两个阶段处理的图形单元的无关性，通过多重相同结构的硬件处理器来提高总体运行速度。在几何处理阶段，根据各种分配策略，采用SIMD或MIMD的体系结构，将各图形处理单元均衡地分布在各处理部件上。在绘制阶段，由于帧缓冲存储器存取带宽是制约绘制速度的主要瓶颈，现有的并行结构大多利用商业化高速缓冲存储器—交错存取存储器，为各组存储单元分配自己独有的绘制部件以达到高的并行处理性能。以上在图形生成两阶段实行的并行处理在各并行图形工作站上往往是不相关的。北卡大学的设计者们认为要达到高性能的图形处理，必须打破传统的计算机图形工作站硬件的这种体系结构，利用成熟的图象合成技术将两者有机地结合起来。基于这种思想，北卡大学推出了两

种大规模并行图形工作站—PIXEL-PLANE系列机和PIXELFLOW。其中于1992年推出的PIXELFLOW[Molnar92]利用硬化的图像合成，将由不同处理机绘制的部分场景的全屏幕图像合成为整个场景的图形画面。PIXELPLANE系列机则是八十年代初开始推出的大规模图形生成并行处理工作站。其主要思想是利用物体的边界方程[Goldfeather86]将屏幕空间划分成可并行处理的象素块，落在各子空间范围的物体由多个并行绘制处理器并行绘制，最后拼合为一个全屏幕的图形画面。该大学于1990年推出的PIXEL-PLANE5具有每秒绘制1兆具有phong光照模型的多边形的处理能力[Fuchs89]。目前该系统已被应用于一些VR系统。其中包括北卡开发的名为Nanomanipulator[Taylor93](纳米操作装置)的VR系统。该系统将高精度(纳米级)检测设备所采集的被观察表面的数据转化为用户定义的数量级数据，同时实时生成所观测表面的画面。观察者可根据观察结果对被观测表面进行实时修改，并将检测设备实时采集的经过表面修改后的数据反馈给图形绘制工作站。该系统利用PIXEL-PLANE5对多个图形处理器直接编程的能力，将反馈结果对图形画面的修改局限于局部范围，从而实时生成观察者对观测表面修改后的画面。该系统具有很高的实用价值，如使用在纳米级的电子线路设计中。

虽然高度并行的图形处理硬件具有相当强大的图形处理能力，但如何对于各种应用问题充分地利用并行处理机的并行性常常是一个很大的难题。这意味着如果不能充分地利用其并行处理能力将是对资源的浪费。在实际应用中，大多数的VR系统仍然采用现有的图形工作站作为其图形绘制的平台。

在当前三维图形工作站的群雄竞争中，SGI工作站作为最杰出的代表具有最优越的三维图形功能。事实上，SGI工作站的发展历程代表着研究部门和工业界十多年来在图形硬件方面为计算机图形处理的发展所作的艰苦而卓越的努力。在八十年代初，正是SGI公司的创始人James Clark教授将三维图形生成的最基本功能—几何变换的矩阵运算完全使用大规模集成电路加以实现，从而为三维图形流水线的主要功能，即坐标变换、三维投影和图形裁剪等的实现奠定了硬件实现的基础。在此基础上，一代一代升级的图形硬件加速器为SGI的系列工作站提供了越来越快速的图形处理能力。甚至某些重要而高级的图形特性，如纹理映射、景深等功能也可由硬件实现[Haeberli90],使得诸多领域如地理地貌、建筑漫游、科学计算可视化等VR系统的实时环境具有更强的真实感。当今SGI最先进的图形加速器已具备每秒绘制超过1兆具有浓淡光照的多边形的能力。为此，最典型的VR系统常常是使用高档的SGI工作站作为其实时图形绘制的处理机，而使用单独的微机作为输入/输出的交互处理。二者用Ethernet等局部网联接。当需要为双眼产生不同的立体图像时，往往用两台相同的工作站或多处理机的两台处理机分别作左、右眼的图形生成。使用头盔式显示器作为其视觉环境的虚拟现实系统

通常是采用这样的硬件系统配置。

除采用头盔式显示器作为视觉环境，虚拟现实系统另一种典型视觉环境是创造一种用户身在其中的影视环境。Illinois大学设计实现的CAVE系统[Cruz-Neira93a][ Cruz-Neira93b]是这种VR系统的典型代表。系统开发者从环幕电影得到启发，利用今天高性能的图形工作站平面投影绘制能力和高精度的投影设备，设计出这样一种基于投影的无障碍式、融真实世界与虚拟世界为一体的VR系统。CAVE的可视化环境是一个由四个包围着观察者的投影面(前、后、左、右)组成的四方形空间。系统配备五台SGI工作站。其中四台完成四个投影面的图形生成；另外一台负责信息传输和各处理机的协调工作。观察者只须配备轻便的立体眼镜和头部跟踪器就能感受到投影图像充满着空间。随着观察者在此空间的自由漫游，观察者可以观察到周围“环境”的动态变化，并能观察到自己的身体，给人以较“真实”的沉浸感。同时，系统根据观察者离屏幕的远近，由远端超级计算机实时生成逐步求精的科学可视数据，并由SGI完成绘制。CAVE已成功地应用于各科学可视化系统中。其中由Illinois大学开发的用于观察美国国家航天航空局卫星观测数据FIFE的基于CAVE科学可视化环境的VR系统SANBOX[Johnson94]成功地为人们展示了曼哈顿周围20x20平方公里120GiGa的气象卫星观测数据。

允许多个用户同时进入的虚拟网络系统是虚拟现实的另一种典型体系结构。这种类似于客户/服务器的虚拟网络分布式系统将各种任务的模拟分散在由LAN或EtherNet连接的多个工作站上。该种系统结构不仅能充分利用已有的设备，而且便利于远端计算机的加入，以允许多用户同时进入虚拟环境。例如大规模作战人员参加的虚拟战场演示环境就是这种分布式体系结构的典型应用环境。1989年，美国国家先进技术研究总署基于陆战演示分布式系统SIMNET[Thorpe87]开发了虚拟飞行作战演示系统DIS[McCarty94]。该系统由位于美国本土及加拿大的多个虚拟座舱通过网络连接而成。虚拟座舱由一台SGI公司的多处理器图形工作站4D/440VGTX通过光缆与头盔显示器、头部跟踪器及控制杆连接而成。由于UNIX系统的分时特性，使得系统对飞行动力模型的访问时间间隔较长，从而引起飞行模拟的错误。为减小对飞行动力模型的访问时间间隔，系统将动力模型参数更新进程的访问时间间隔划分为20个更小的时间间隔。同时，系统分配不同的处理器分别管理飞行动力模拟与绘制和网络界面进程以加快系统对飞行动力模型的访问。为减少网络传输量、降低由于网络传输带来的延迟，系统根据预测推算算法(Dead Rechoning)发送消息，并根据最近接受的远端虚拟器的消息来推断其位置和状态。

虚拟现实系统的软硬件结构涉及到如何有机地协调多输入/输出、动态模拟及图形综合等多任务。系统在处理多种输入输出以及大量模拟计算的同时，必须使用户在视点改变后即时感受到场景的变化，这是虚拟现实系统是否成功的决定性因素之一。为保持较高的帧频率，虚拟现实系统通常将各进程放置在异步运行的处理机上。系统必须协调处理好各进程之间的关系，否则系统对用户交互的反应将会受到严重的影响。例如VPL公司的Electric/ISAAS[Blanchard90]因为输入设备交由应用计算进程管理，尽管绘制进程和应用进程分置在不同处理机上，绘制进程却必须等待应用计算进程的信息才能反应用户的交互动作，使得绘制进程受限于应用计算进程的更新率。为改进对用户交互的实时反应，Alberta大学开发的虚拟环境建模系统MR[Green91]将计算进程和应用进程放置于不同的处理机上，并将绘制等输入/输出进程交由应用进程管理。但该系统不提供应用进程和计算进程的协调工作，用户必须花很大精力协调二者。与此相对照的是，Virginia大学开发的虚拟环境建模系统DIVER[Grossweiler93]将输入设备直接与绘制数据库相连，使得系统在应用计算进程进行复杂计算的同时，用户仍能随视点的改变看到连续动态的画面，以伴随虚拟场景的缓慢变化。同时系统提供放置于不同处理机上的应用计算进程和绘制进程的“透明”性协调工作，极大地方便了虚拟现实系统的开发。

1.3 图形生成的加速方法综述

就图形学发展而言，起关键作用的无疑是图形硬件加速器的发展。高性能的图形工作站和高度并行的图形处理硬件及软件体系结构是实现图形实时生成的重要保证。但今天的图形工作站性能距离VR的充足需求仍相当遥远。换句话来说，当前图形生成的速度相对于通常虚拟环境的规模来说仍存在相当大的差距。举例来说，UC.Berkely大学的计算机科学大楼的计算机模型具有1.4兆个多边形的数据；帝国大厦的计算机模型则由167兆个多边形组成；而波音公司最近推出的完全由计算机设计的波音777是一个有着500兆个多边形计算机建模模型。这些应用模型的复杂程度往往超过当前图形工作站的实时处理能力。考虑到VR对场景复杂度几乎无限制的要求，在VR高质量图形的实时生成要求下，如何从软件着手，加速虚拟环境的生成，成为VR图形生成的主要目标。

我们知道，图形硬件流水线划分为几何处理和绘制两个阶段。从主机开始遍历整个虚拟场景到最终生成虚拟场景的图形画面，虚拟环境的图形生成的时间耗费大致包括：主机遍历时间、几何处理时间以及绘制时间。几何处理时间可以由所要处理的图形单元

的顶点数目决定；而绘制时间则由所绘制面片所覆盖的pixel总数决定。虚拟环境的图形生成的时间由这三个阶段组成的流水线中时间耗费最长的阶段决定。如何降低这三个阶段的时间耗费，除了利用图形硬件本身的功能，如利用三角面串以减少几何处理阶段的时间耗费，尽量减少图形特性的设置以减少几何计算的时间等外，图形生成加速的方法大致可以分为可见性的判定、细节层次模型技术、动态图象加速技术以及预计算。下面我们就这几个方面作简单的介绍。

1.3.1 可见性的判定

由于视线方向性、视角的局限性以及物体相互遮挡，人眼所看到的往往只是场景中的一部分。所谓可见性的判定即利用物体空间的相关性、图象空间的相关性和时间空间的相关性加快可见面的判定，减小绘制深度。

* 物体空间的相关性即利用物体空间的分割预先确定景物在空间的分布情况以加速可见面的判定。

* 图象空间的相关性即利用当前已绘制场景决定可见面的判定。 * 时间空间的相关性即利用相邻帧可见面的连贯性加速可见面的判定。

早期的可见性判定主要是指视见体的判定。这一时期的可见性判定主要是利用场景的有效组织来加快位于视见体内物体的判定。七十年代末发展起来的物体分层次表示(hierachical representation)是这一时期的典型代表。层次表示的主要方法是包围盒技术和八叉树技术。这两种方法的主要特点是将场景组织成为一棵树，充分利用空间连贯性以加速场景的遍历，从而大大地减少了画面绘制过程的时间复杂度。

此后，Fuchs[Fuches80]以物体的半空间表示将其空间一分为二，将场景组织为二叉树(BSP)的结构。此方法可利用已建立起来的二叉树很快地决定相对视点面的前后排列，加快由于物体相互遮挡所产生的可见面的判定。但该方法由于以面作为划分单元，因而会产生大量新的面片。

鉴于以上方法的特点，Teller[Teller91]基于建筑CAD的特点，探索了一种基于“房间”结构的可见性预处理方法。此算法以建筑模型中主要的遮挡面为空间划分面，从而将建筑模型划分为以房间为基本单位(cell)的数据模型。在空间划分的基础上，根据基本单位之间共有的可见口(portal)，如门、窗等，建立起cell与cell之间的邻接图。考虑到实时漫游时观察点的任意性，算法定义cell的可见性

为观察者所能看到的区域，即一个观察者在此cell中任一位置、任一方向所能看到的区域。由于cell与cell之间可见就意味着有一条光线能无遮挡地从此cell达到彼cell。算法根据cell与cell之间的邻接图，通过深度遍历建立起cell与cell的可见口序列(portal sequence)，从而得到cell对cell的可见性超集、cell对object的可见性超集。在实时漫游时，算法利用预计算的结果实施内存与外存的调度管理，并从所得的超集计算视点对cell、视点对object的可见性集合，有效地加速了可见性的计算。但本算法的预计算比较复杂，且目前局限于轴向的建筑模型。

不论哪种空间划分技术，都仅仅只利用物体空间的相关性来加快可见性的判定。传统的z-buffer算法利用同一象素的深度信息，决定可见面的判定，有效地利用了图像空间的相关性来加快可见性的判定。但z-buffer算法并没有利用空间的相关性来加速可见性的判定。在利用物体空间、图象空间和时间空间相关性方面，Greene[Greene93]提出了非常有创意性的思想。该方法利用绘制画面的z缓冲存储器，通过物体空间和图象空间两个结构的建立，提出了一个利用物体空间、图象空间和时间空间相关性的算法。我们知道，八叉树中一个单元如其六个面不可见，则此单元所包物体不可见。那么如何判定此单元不可见?Greene利用已绘制场景的z缓冲存储器结果，作为z缓冲存储器层次结构第一级，将上一级数据压缩一倍(即取每相邻四个数据的最大值)就得到第二级数据。依此压缩下去，就得到图象空间的层次结构。可以看出，层次结构中的任一数值都对应于屏幕空间上大小不同区域的最大z值。以八叉树中一单元在屏幕空间所在区域的最大z与此单元的最小z值比较，如果此屏幕空间的最大z值比此单元的最小z值小，那么此单元不可见。否则将此单元分为四个子空间，再将这四个子空间的最小z值与所对应的屏幕空间区域的最大z值分别进行比较，直到子空间的最小z值大于相应屏幕空间区域的最大z值或者相应屏幕空间区域已对应屏幕一象素。虽然此算法的实施依赖于可否对z缓冲存储器进行访问，但其方法在利用物体空间、图象空间和时间空间一致性方面作了很有效的尝试，算法的实施非常便利于并行计算。

1.3.2 细节层次模型

所谓细节层次模型方法即为每个物体建立多个相似的模型，不同的模型对物体的细节描述不同，对物体细节的描述越精细，模型越复杂。

由于今天高精度的遥感测绘技术以及三维扫描技术，复杂物体的建模已不难获取。这些模型通常由大量密集的数据组成。虽然计算机的处理速度在不断提高，存储空间也在不断扩大，但仍远远赶不上模型复杂度的增长，如此庞大的模型存

储、显示、传输上都面临巨大的困难，由此，对细节层次(Lever-of-Detail, LoD)模型的研究应运而生。层次模型由在不同尺度上逼近原始复杂模型的一系列模型组成。在具体应用中，可以根据需要选用相应的模型进行显示或传输。LoD模型具有广泛的应用前景，在实时图象通信[Finkelstein96]、碰撞检测[Cohen92a]、限时图形绘制[Pan95]和虚拟现实[Astheimer94]等领域中已显示其强大的生命力。特别是在虚拟现实等交互式计算机图形应用领域中，细节层次模型技术已成为图形实时生成的关键技术。

LoD模型技术改变了传统的“图象质量越精细越好”的片面观点，而是通过对场景的复杂度以及图形系统的综合评判，以一定的算法为各物体选择适当的细节模型，从而使图形显示在保证实时恒定的帧频率的前提下，最大程度地提高视觉效果。

早在计算机发展的初期，人们已经认识到层次模型表示的重要性。在1976年Clark就已提出了用于可见面判定算法的几何层次模型[Clark76]，并指出该方法有助于解决图形学中其他一些相关问题。在该文中Clark指出，实际场景的复杂性往往超过计算机能进行实时处理的能力，为了在计算机中以较少的时间及较高的图象质量绘制出复杂的场景，当物体仅覆盖屏幕较小区域时，可以用该物体描述较粗的模型进行绘制，以便达到快速、有效的复杂场景绘制。

要成功地使用LoD模型，一个图形系统必须解决以下问题：LoD模型的选择尺度，LoD模型的选择算法，LoD模型的平滑过渡方法。下面我们就当前的常用算法作一简单的介绍。

* LoD模型的选择尺度：在LoD中，通过对场景中每个图形对象的重要性进行分析，使得最重要的图形对象进行较高质量的绘制，而不重要的图形对象则采用较低质量的绘制。在保证恒定实时的图形显示的前提下，最大程度地提高视觉效果。换言之，一个图形对象越重要，其对观察者所观察到的画面的贡献越大；图形对象的重要性取决于对视觉效果的贡献程度。例如，若一个图形对象离观察者很近，或位于观察者眼睛焦点，那么，相对而言它理应具有比其它图形对象更佳的显示效果、更详细的细节。遗憾的是，衡量视觉效果是一个非常复杂的问题，它涉及到视觉生理学和心理学。在实际应用中，人们一般根据经验，将图形对象重要性的评价归结为以下几个因素[Astheimer94][ Funkhouser92][ Rossignac93][ Liu]：

面积(size)尺度：面积是指图形对象在屏幕上所占面积。面积越大，图形对象对图象效果的贡献越大。当然这也是相对而言的。例如，在建筑漫游中，墙所占的面积很大，但观察者并不注意它。在现存的LoD选择算法中，面积通常用图形对象的平均多边形所占象素点的总数来计算[Funkhouser92][ Liu]，或用图形对象距视点距离的方法来计算[Astheimer94][ Blake87]。

焦点(Focus)尺度：焦点指人眼对图形对象的注意程度。显然，视线焦点周围的图形对象应具有更详尽的显示效果。Funkhouser等人曾根据图形对象重心距屏幕中心的距离逐渐降低图形对象的Focus值[Funkhouser93][ Liu]。

相对运动(movement)：相对运动指图形对象在屏幕上的移动速度。速度越快，图形对象的重要性越低。

* LoD的选择算法：要达到逼真的显示效果，不仅要求实时图形显示，还要求系统能维持恒定的显示帧频率。细节选择算法的本质就是要对场景的复杂度作出估算，在保持恒定的实时帧频率的前提下，为各场景中的物体选择适当的层次模型，最大程度地提高视觉效果。现有的LoD选择算法大致可以分为以下三类：

静态式：所谓静态式即仅以以上各种选择尺度计算各物体的重要性并依此选择相应

的模型。这种选择算法在远距离观察场景时可以大幅度地提高系统的帧频率 [Funkhouser92][Rossignnac93]，但这种选择算法因为无法根据所观察到的场景的整体复杂度综合评定物体的重要性，从而无法保证恒定的帧频率。

反馈式：即LoD的选择是基于上一帧场景的绘制时间选择物体的层次模型

[Schachter83]。反馈式选择算法克服了静态式选择算法的缺点，模型的层次选择根据上一帧所需的显示时间对当前帧的模型选择作适当的调节。这种算法适合于前后帧场景复杂度具有一定相关性的环境，如飞行模拟。但该选择算法在处理场景复杂度可能发生突然变化的环境时效果不好。

预估计式：反馈式LoD选择算法虽然可以较好地处理复杂度变化不大的场景，但

当场景复杂度变化较大时，这种方法就不够有效。为此，Funkhouser等提出了预估计式的模型层次选择算法[Funkhouser93]。Funkhouser认为层次模型选择算法不仅应当建立在前后帧的连贯性上，而且应具有一定的预测性。该方法以可见性判定作为并行计算，由此解决了由于场景复杂度发生较大变化所带来的帧频率变化问题。算法根据可见物体对整个画面的效果贡献以及绘制该物体某一层次某一绘制方法所花费的时间求取具有最佳效果的在恒定帧频率时间范围内的解。

* LoD的光滑过渡：由于采用不同层次绘制同一物体，因而如何作到不同模型层次间的光滑过渡一直是LoD中的一个待解决的问题，并由此引发了细节层次模型的实时生成算法的研究。在以往的LoD生成算法中，由于模型的简化不是简单地减少几何元素的数目，而是根据对原模型的逼近精度要求，删除那些对模型几何形状影响不大的顶点，保留那些反映模型中几何特性的特征点。由于要对大量数据逐个作判定，计算量很大，

因而算法无法达到实时。大多数的细节层次模型自动生成方法只能预先产生对原模型作不同程度近似的多个逼近模型，在实时绘制中根据当前帧的视觉参数选用相应的逼近模型进行绘制。这样产生的近似模型空间是不连续的，因而在不同层次的变化过程中必然造成绘制图象的不连续变化，产生图形画面明显的跳跃感。虽然可以利用图形硬件的blending功能同时绘制不同的模型或建立不同层次模型间的对应关系进行插值[Helman95]，这无疑都会增加系统的开销。由此引发了对细节层次模型的实时生成算法的研究[Lindstorm96]。

1.3.3 动态图像加速技术

利用动态绘制产生的图形画面来加速整个虚拟场景的图形画面的实时生成是近几年来发展起来的一种基于图形图象混合绘制的图形生成加速方法。该方法充分利用相邻帧画面的相关性加速虚拟场景的图形生成。算法基于这样一个事实：即相对于一个观察者，一个场景的某些部分在一段时间内在该观察者分辨范围内是不变的，如远处的树木、高楼。动态图像加速技术即利用这种相关性，动态几何绘制生成并存储虚拟场景这些区域的生成图形画面。在以后帧，根据当前观察者的实际位置以一定的误差判定决定存储的该区域的图形画面是否有效。如误差允许，则以该图像作为当前帧观察者所看到的该区域的图形画面。最后以几何绘制和已有的各区域的图形画面生成整个虚拟场景的图形画面。该方法适合于任意复杂的虚拟场景。根据如何由已有的图形画面最后生成各区域当前帧的图形画面，该方法又可分为基于纹理映射的动态图像加速法和基于图像合成的动态图像加速法。

基于纹理映射的图像加速法实际上早已存在。在早期，为加强图形画面的真实性而又尽量减少图形生成的负担，人们通常采用一种叫作Billboard的技术[Jones95]来生成一些非常复杂而又具有一定对称性的自然物，如树木。Billboard是这样一个带有纹理的半透明的长方形。其纹理图像为该Billboard所代表的物体的影象，即以带有该物体影象的长方形代替该物体生成该物体的图形画面。Billboard放置于所代表物体的位置中心，并随用户的运动而转动，始终面对用户。早期的Billboard的物体的影象是预先得到的，且只对具有一定对称性的物体而言。[Shade96]将此方法推广，实时动态地生成任意物体的图形画面作为该物体的影象存储起来。只要误差允许，就可以以该影象作为以后帧该物体的影象映射到相应的面上生成观察者当前帧所看到的该物体的图形画面。只是该映射面不再随用户的移动而转动。为了最大程度地减轻图形生成的负担，该算法进一步将以上思想推广应用到整个虚拟场景的一些区域。即认为在一段时间内该区域相对一个观察者在其分辨范围内其图形画面是不变的。为此，算法以二叉树建立整个虚拟

场景的层次结构。在实时绘制时，算法首先遍历二叉树，根据当前观察者的位置决定该结点存储的相应于虚拟场景某区域的影象是否仍有效。如无效，则继续遍历该结点的前后子树，并以当前观察者的运动参数及误差精度估算以决定是否生成此结点当前的图形画面以作为以后帧的影象；否则，以该结点所存储的该区域的影象生成该区域当前的图形画面。该算法以包围该结点的四方体内各空间点最大角度变化来计算由于观察者运动所产生的图形画面的误差，并以此决定所存储的图像是否有效。

基于图像合成的图像加速技术是[Regan94]提出的另一种动态图像加速技术。该方法根据当前观察者与物体的相对运动以及误差精度赋予各物体一定的绘制速率。算法由不同速率绘制生成的各物体的图形画面根据深度值的比较最后生成整个虚拟场景的图形画面。在算法中，作者提出了一种崭新的图形生成流水线框架，最大限度地减少由于随视线方向变化观察者所观察到的图形画面变化所产生的图形生成延迟。作者认为，人的视线变化是引起相邻帧画面变化的最大原因。如果能将视线方向的最后定位与图形绘制过程分开，而仅在确定知道人的视线方向后进行一个视见窗的映射变换，那么图形绘制就可以最大限度地减少由于设备定位所引起的延迟。从而也最大限度地减少由于视线方向变化所引起的图形绘制开销。作者将此思想与图像合成方法相结合，从而免除了仅仅因为视线方向变化所引起的图形画面的重新绘制，大大减轻了图形系统的绘制开销。该算法试验统计数据表明一个场景中大概只有1～2％的物体需要每秒60帧的绘制速度，而大部分的物体只需每秒重新生成3.75～7.5次。为了使所绘制生成的图形画面包括观察者所有的观察方向所能看到的所有的图形画面，该算法利用[Chen95]一文提出的基于图象绘制生成虚拟场景的基本原理，以四方体的六个投影面绘制生成包括观察者所有的观察方向所能观察到的图形画面，只需一个映射变换就能生成当前观察者观察方向所看到的画面。

动态图象加速技术结合了当前加速生成虚拟环境的LoD技术、场景划分技术以及静态图象绘制技术。虽然，动态图象生成技术的研究尚处于初步阶段，但其潜在能力已得到人们的注意。

1.3.4、脱机计算

脱机计算是减轻计算机实时计算负载的常用方法之一。由于VR系统是一个多任务的模拟系统，有必要尽可能地将一些可预先计算好的结果预先计算并贮存在相应的结构中。这其中包括全局光照模型、动态模型的计算等。

就图形生成质量而言，VR所期待的目标自然是高质量真实感的逼真图形，并具有各种自然场景的复杂图形画面。但如前所述，图形处理的硬件能力尚远远满足不了VR的需求，因而在现今的条件下，实时的真实感图形生成几乎是完全不可能的。对于大多数的VR应用来说，仍只是采用简单的局部光照模型，且在硬件部件的支持下实现质量并不高的图形显示。但从将来的发展来看，使用全局光照模型和显示具有复杂场景的真实感图形必然是VR所应追求的目标。就全局光照模型来说，光线跟踪技术由于其计算量大，且因其生成结果固有地与视点相关而很难进行预计算，因而这一技术几乎很难应用于VR.与此相对，辐射度技术因其计算结果与视点无关，大量计算可作为预计算，因而极有可能成为用于真实感图形生成最有希望的工具。

自1984年C.M.Goral等从热辐射工程中引进了辐射度方法，辐射度技术已得到了很大的发展。特别是逐步求精算法的提出，大大加快了辐射度技术的速度，使得辐射度技术成为真正实用的全局光照模型技术。进入90年代后，辐射度技术进一步走向实用。多层次划分技术[Hanranhan91]利用N-body问题的方法将传统辐射度方法的时空复杂度从o(n2)降为o(n)，并根据用户定义的误差，自动建立起面片的划分，进一步提高了辐射度技术的实用性。1994年，Smits在[Smits92]一文中将视点参数引进辐射度计算中，建立起与视点范围有关的importance函数，将视点与辐射度技术结合起来，使辐射度技术向实时计算迈进一步。

物体的动态模拟模型的计算是VR的一大任务。在这些动态模拟中包括一些较有规律的动态特征的模拟，如具有动画特征的随时间变化而变化的动态模型和一些基于特定事件的动态事件的模拟。它们的物理模型的各种参数并不由于各种偶然性发生变化，如物体的独自运动。为减少实时动态模拟计算的负载，可以将这些动态描述作脱机计算，并作为实时计算的输入。在德国Fraunhaffer计算机图形研究所为工业应用设计的VR应用系统Virtual Design[Astheimer93]中利用辐射度计算和动态模拟的脱机计算已有了较为成功的尝试。

Virtual Design是一个面向建筑设计的开放式系统。该系统实现多种CAD、室内设计等的图形文件到自身数据库的转变。系统为满足不同需求，运用不同精度要求的辐射度算法预计算虚拟场景的全局光照模型。系统设计者们认为两层数据结构已足够，多层则不利于绘制速度.为减少动态模拟的实时计算，系统将一些动态模拟作脱机计算，并以矩阵形式作为系统的输入。该系统提供多种输出，其中包括三维真实音响的模拟。用户可感受到在虚拟场景中漫游时不同地点的音响特质。

1.4 LoD模型自动生成方法综述

自动生成复杂物体的多细节层次模型是实现LoD技术的关键所在。虽然早在1976年Clark就指出了多细节层次模型的重要性，但以往算法所述的层次模型一般都是人工建立的。进入九十年代后，随着遥感技术的发展、图形学在大型科学计算中的应用，在全世界范围内形成了对多LoD自动生成技术的研究热潮。人们就如何由原始复杂网格模型简化生成不同尺度上逼近原模型的细节模型的自动算法展开了广泛的研究，并取得了很多有意义的研究成果。下面我们就细节层次模型自动生成方法以及误差程度度量方法作一简单的回顾。

1.4.1 LoD模型自动生成方法

1991年，Dehaemer[Dehaemer91]提出了自适应递归分割法生成基于规则四边形网格表示的物体网格简化方法。自适应递归分割法借鉴逐步求精的曲线曲面生成方法。算法首先建立原始模型的最简化形式，然后根据一定规则通过细分把模型的细节信息增加到简化模型中，从而得到较精细的LooD表示。自适应递归分割法可以生成物体具有多分辩率的层次细节模型。但在一般情况下构造最初网格的最简模型相当困难，而且要求原始模型能建立起简单明了的参数对应关系。因而它主要适用于均匀网格，如高度场。根据所采用分割方法的不同，又分为基于非规则三角网格和基于均匀网格的两种层次细节模型生成方法。前者如三叉树三角化(ternary triangulation)方法[Floriani84] 、Delaunay三角划分方法[Floriani92][Polis92] [Floriani95]等；后者如四叉树三角化(quaternary triangulation)方法[Pottmann90][Dyn90] 、四叉树(Quadtree)方法[Chen86]等。

1992年，Turk提出了重新布点法实现复杂网格模型的自动简化[Turk92]。该算法以一组新的顶点分布到原始网格上，并根据模型的曲率变化决定顶点在原网格不同区域上的分布密度。为保持原模型的拓扑结构，算法由新旧顶点共同生成模型的中间网格，并由此中间网格通过必要的拓扑结构一致性检查移去老顶点，生成由新顶点组成的原复杂模型的简化模型。该方法适用于光滑曲面，且有简化模型中引入了新顶点。

同年，Schroeder[Schroeder92]提出了基于顶点移去的网格简化算法，首次提出了以几何元素删除实现模型简化的多细节层次模型自动生成方法。从此，人们相继提出基于边蜕化[Hoppe93]、基于三角形移去[Hamann94]、基于**面合并[Kalvin96]等几何元素删除法实现复杂网格模型的简化。以几何元素删除法实现模型简化的方法即根据原模型中的几何拓扑信息，在保持一定的几何误差的前提下，以一定的局部欧拉操作，如顶点删除、边删除等，相应地删除模型中较平坦区域的几何元素，然后对删除几何元素所遗

留下的空洞进行局部三角化剖分生成满足一定几何误差的原模型的简化模型。

当然，模型的简化不是简单地减少几何元素的数目，而是根据对原模型的逼近精度要求，删除那些对模型几何形状影响不大的顶点，保留那些反映模型中几何特性的特征点，计算量很大。因而大多数的模型简化方法只能预先产生对原模型作不同程度近似的多个逼近模型。在实时绘制时根据当前帧的视觉参数选用相应的逼近模型进行绘制。这不仅带来了存贮容量的增加，而且为克服由于不同模型绘制所产生的跳跃感必然增加系统的开销。

为避免图形画面的跳跃，几何模型的复杂度在相续帧之间应该是平滑过度的。即被控制的模型的三角面的数目应随视点的连续变化而连续的变化。视点的小变化不会也不应导致模型的大变化。这个性质将会避免动态显示中出现图形画面的跳跃。

1995年，Hoppe在原有的边操作算法基础上提出了累进网格的概念[Hoppe95]，首次较好地解决了模型简化方法在实际应用中所遇到的问题。算法利用顶点分裂这一与模型简化操作─顶点合并相逆的过程来恢复模型简化所删除的信息。为了得到模型细节的删除信息，算法在模型简化的预计算中记录下边蜕化为新顶点这一简化过程中原顶点与新顶点的对应关系，并由预计算中记录下的每一简化过程得到一个由原模型的基本网格和一系列的简化信息组成的渐进网格表示模式。在实时绘制时，通过跟踪记录下的边蜕化为新顶点的对应关系，算法可以根据这一跟踪线索由基本网格模型逐步恢复所删除的模型细节，实时得到原模型连续精度的简化模型。该算法以边蜕化所导致的模型几何误差的大小指导模型简化的顺序，并由此生成几何误差由小到大的渐进网格模型。

渐近网格很大程度上克服了以往模型简化方法的缺点，可以支持不同细节的网格模型的实时生成。但渐近网格在实现同一模型不同区域多分辩率细节的实时生成方面仍缺乏有力的结构，而且由于边删除的前后顺序与边的拓扑信息毫无关联，在模型恢复过程中必须对误差逐一判定，因而无法实现多分辩率的层次细节模型的实时生成。

个关键的简化模型，并对其中的三角面按照它们的视觉重要度进行排序。在实时绘制过程中，算法选择一个最少的但又比所需要的分辨率高的近似模型，按重要度从小到大地删除三角面直到刚满足当前精度为止。算法建立三角面删除队列，记录三角面在实时计算中最近被删除的信息，以此加速实时模型的简化，实时得到原模型连续精度的网格模型。

诸如地表这样大面积复杂模型在实际应用中有着其特殊的处理要求。地表模型是一个有着大规模数据的几何模型，人眼看到的仅仅是虚拟地表模型的一部分。因而地表模型的生成应根据当前视觉参数对模型不同区域赋予不同的分辨率细节，同时，由于在地表模型的应用中经常必须依据地表特征进行判定，因而地表模型的简化必须保证在一定的视觉误差范围内。为此Lindstorm于1996年提出了与视觉误差相关的地表模型简化算法[Lindstorm96]。在该文中，他指出以往算法为达到最大限度地简化模型而采用非均匀网格表达形式作为模型最终的简化形式，而忽略了均匀网格模型良好的多分辨率特性以及良好的拓扑特性。该算法结合均匀网格的特点以及非均匀网格描述的高效性，提出了以视觉空间误差为评判标准的地表模型的实时简化算法。该算法利用均匀网格良好的网格模式不仅避免了一般简化操作必须对所遗留空洞进行复杂三角剖分的过程，而且利用均匀网格的多分辨率特性，实现了大规模地表数据的多分辨细节层次模型的实时生成。小波变换是八十年代后期发展起来的数学分支。小波变换的多分辩率分析特性为网格模型的细节层次模型生成提供了一种一致性的具有坚实理论基础的处理方法。Lounsberg于1995年利用小波变换提出了对具有细分连续性的一类网格的多分辨率细节层次模型的自动生成算法[Lounsbery94]。但小波变换所处理的模型必须具有细分连续性，而实际中所遇到的网格通常不具有这种特性。为此Eck[Eck95]提出一种将任意网格转化为具有细分连续性网格的算法，从而实现了任意网格的多分辨率模型的自动生成。基于小波的多分辨率模型具有良好的局部细节层次控制特性，而且模型具有良好的连续性。但小波变换不能处理表面不连续问题，且由于误差判定的计算复杂性，因而，在实时细节层次控制上基于小波的多分辨率模型尚有待进一步研究。

以上方法都要求生成的简化模型保持拓扑关系和几何关系的正确性。但Rossignac[Rossignac93]认为，简化后的模型只要其图形生成效果与原模型一致，则该简化模型成立。为加快实时图形生成，在该文中提出了以顶点簇合并自动生成物体简化模型的方法。该方法不维护模型的拓扑邻接关系，而仅以物体空间的邻近来合并顶点簇。因而允许产生非规则的模型，算法不仅简化效率高，而且速度快。

1.4.2 LoD模型的误差度量

网格简化的目的是把一个复杂多边形表示的模型用一个近似的模型表示，近似模型基本保持了原模型的可视特点，但顶点数目少于原网格的顶点数目。通常的作法是在保持原模型的拓扑性质情况下把一些不重要的“图元”(顶点、边或三角形)从多边形网格较平坦的区域中删除。

但模型的简化不是简单地减少几何元素的数目，而是根据对原模型的逼近精度要求，最大限度地删除那些对模型几何形状影响不大的顶点，保留那些反映模型中几何特性的特征点。这实质上是一个非常复杂的优化问题。因而在实际应用中，人们通常只是在满足逼近精度要求下，以一定的误差度量排序来指导模型的简化。如在边蜕化算法[Hoppe96]中即以边被删除后导致的几何误差大小进行排序并以此指导对简化单元的先后顺序。[Hamann94]一文中的全局优化算法中亦采用了相似的办法以求取同一近似精度下的最简模型。

点到相关三角面的距离是判定顶点所处区域平坦程度的常用方法之一。但以往算法仅仅只是给出了顶点到当前所生成的中间简化模型的误差计算，却没有控制简化模型与原始复杂模型的误差。[Cohen96]提出了包络盒的误差控制方法。该方法利用等距曲面的概念，给出了对原模型逼近程度的一个十分形象的控制方法。求取一个与原始复杂模型偏差不超过用户指定距离的一个逼近模型，算法以等距曲面概念建立原模型的内外包络盒。在简化过程中，只有简化结果所生成的三角面包围在此内外包络盒中简化操作才成功。包络盒的误差控制方法不仅为算法提供了一个可以控制整体逼近误差的手段，而且通过改变局部的偏差距离，可以针对模型不同区域的模型特点建立具有不同逼近效果的简化模型。同年，Kalvin在[Kalvin96]一文中，在给出了**面简化方法的同时，将上述思想用解析式的表示方法给出。

曲率变化反映了模型平坦变化程度。根据曲率可以很好地区分物体表面的一些特征(如地表模型中的峰、谷、脊)。在进行模型简化过程中，可在高曲率处保留尽量多的点，而在低曲率处删除尽量多的点。Turk通过计算顶点和三角面的曲率，把新顶点分布在曲率较大的三角区域上[Turk92]。

以上介绍的仅是简化模型对原模型几何近似的误差度量方法。然而在实际的模型中，一个模型不仅有几何拓扑的约束，而且有颜色纹理等各种其它性质的约束。特别是在物体的光照颜色纹理不仅能为物体提供真实的外部特征，而且为人眼提供了丰富的邻近、遮挡等视觉信息。因而模型的简化不仅应给出几何的误差限定，而且应给出模型其它约束性质的误差限定。Hoppe在[Hoppe96]一文中首次将物体的几何误差度量函数函数推广至网格模型的其他约束性质。在该文中，作者指网格模型的其他约束性质应具有与几何约束性质同等的重要性。该文将这些性质划分为标量性质和离散性质。离散性质定义了网格模型面的各种性质，如材质等；而标量性质则定

义了网格模型各顶点的约束性质，如顶点的切向量、颜色值等。基于以上分析，算法将一个网格模型表示为具有拓扑性质K、几何性质V、离散性质D以及标量性质S约束的四元组(K, V, D, S)。算法将标量性质与几何性质作了同样的处理，定义了类似于几何点到面的距离函数以作为由于顶点删除所引起的其它约束性质的误差。同时算法根据离散性质的不同识别模型特征以保持模型的特征。

LoD算法最大的特征是利用人的视觉特征，以最小的图形绘制开销取得最好的图形画面视觉效果，删除那些视觉分辨不出的图形细节。如何利用人的视觉特点最大程度减化模型，减轻图形系统的负载仍是一个待解决的问题。以往的LoD模型自动生成算法由于无法达到实时，只能根据几何误差判定生成多个不连续的简化模型，而在实时绘制时根据模型在屏幕的投影大小等因素来选择不同细节模型。Lindstorm于1996年[Lindstorm96]首次提出了与视觉误差相关的模型简化算法，但此算法只是针对均匀网格而言。对任意网格模型的基于视觉误差的模型简化算法仍有待于人们的研究。

国内在层次细节模型的各个方面也展开了一些有益的研究。例如，对已有的网格简化算法尽心能够改进或提出新的多面体模型简化方法[Pan96][Zhou96]，给出了虚拟环境中恒定帧频率自适应显示算法[Liu98]，以及三维复杂模型的实时连续多分辨率绘制算法[Li97]。

1.5本论文的工作

虚拟现实技术是一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界面技术。图形的实时生成是VR成为“现实”的关键技术之一。本论文围绕层次细节模型技术展开了有益的探索，研究各种LoD模型生成方法及实时绘制技术。研究成果包括以下几个方面：1)提出一种新的渐进网格模型的生成方法。2)提出新的非规则网格LoD模型的实时绘制方法。3)以焦点以及显示面积二者有效的结合建立较为精确的视觉空间模型，改进基于均匀网格表示物体的LoD模型的实时生成及绘制技术。4)提出一种基于辐射度全局光照网格模型的简化方法。全文共分五章。

第一章简单介绍了VR的基本概念、主要特点。对虚拟环境图形生成的各种加速方法作了较为全面的综述，同时阐明了虚拟现实中LoD模型自动生成和绘制技术的研究内容和应用价值。就LoD模型技术的各个相关方面：LoD模型的选择尺度、LoD模型的平滑过渡以及LoD模型的自动生成进行了深入的研究，回顾了国内外在的研究状况。本论文就各种LoD模型生成方法及实时绘制技术进行了一些尝试和探索，取得了一些成果。下面逐章进行介绍。

以几何元素删除实现模型的简化是多细节层次模型自动生成的常用方法。但由于复杂模型庞大的数据量以及模型简化复杂的计算，使得以往的LoD模型生成方法只能预先产生多个间断的简化模型，从而引起实时绘制时图形画面的跳跃。为解决这个问题，人们相继提出了渐进网格模型概念以及三维复杂模型的实时连续的多分辨率绘制技术。本文结合以上方法提出一种新的渐进网格生成方法和表示形式。利用这种渐进网格表示形式，我们实现了三维复杂模型的实时连续多分辨率绘制。

地表模型在虚拟现实中有着广泛而重要的应用。非规则网格模型和均匀网格模型作为地表等数字化高度场模型的两种表示形式，在以往的地表模型的层次细节模型生成算法中有着各自的特点。Linstorm结合非规则网格表示的高效性和均匀网格模型良好的自适应性，提出一种地表模型的实时连续多分辨率绘制方法。但该方法忽略了人眼对处于不同视觉区域的模型细节的不同分辨能力，对处于不同视觉区域的模型赋予相同的细节，这必然带来图形生成的浪费。本文提出具有聚焦因子的基于图象空间误差的地表模型消减算法，以焦点以及显示面积二者有效的结合建立较为精确的视觉空间模型，以此模型衡量人眼对由于面片合并所带来的误差的分辨能力，并以此作为地表模型细节的重要度评价尺度，有效地简化了地表模型的绘制。同时，算法结合均匀网格模型的多分辨率细节层次模型，以“块”作为地表模型大面积简化的空间单位，加速地表模型的简化操作，以实现较为复杂的地表模型的实时绘制。

物体表面的光照颜色纹理不仅为人类提供了丰富的视觉效果，而且为人类提供了丰富的形体、邻近及遮挡等视觉效果。但全局光照模型的计算结果往往导致模型复杂度的几十甚至几百倍的增加。本文结合辐射度全局光照模型的计算特点。提出一种基于辐射度全局光照网格模型的简化方法。该方法根据人眼的视觉特点和辐射度计算特点，以最大相对变化值为准则，以面片合并简化操作将最大相对变化在用户定义范围内的面片合并起来，实现辐射度全局光照网格模型的第一步简化，并以原模型顶点的RGB值的变化进一步加大辐射度网格模型的简化，建立起整个环境具有辐射度全局光照效果的多细节层次模型。本算法不仅有效地简化了辐射度全局光照网格模型，而且能较好地保持原光照网格模型的特征。

第二章一种新的渐进网格生成方法

借助高精度的三维扫描仪和CT扫描仪，可以获取真实物体的大量数据，为快速三维建模提供了一种高效的手段。这些模型通常有大量的数据组成。虽然今天的计算机处理速度在不断提高，存储空间也在不断扩大，但仍远远赶不上模型复杂度的增长，如此庞大的模型存储、显示、传输上都面临巨大的困难。特别是在虚拟现实中，虚拟环境必须实时生成以使能进行交互式的控制、观察和操纵；否则将严重地影响虚拟现实的“现实感”。为此人们采用了各种技术来解决这个矛盾。其中，细节层次模型技术就是其中一种非常有效的方法。本章首先讨论基于几何删除的LoD模型自动生成方法的利弊，介绍渐进网格模型的概念。同时提出一种渐进网格模型的生成及绘制方法。

2.1相关工作

网格简化的目的是把一个复杂多边形表示的模型用一个近似的模型表示，近似模型基本保持了原模型的可视特点，但顶点数目少于原网格的顶点数目。基于几何元素删除的模型简化算法即通过一定的误差判定，删除那些对模型几何形状影响不大的几何“图元”(顶点、边或三角形)，达到模型简化的目的，得到在不同精度上逼近原复杂模型的近似模型。为了保证拓扑特性，算法必须对几何元素删除后所遗留的空洞、进行复杂的三角化过程。

1992年，Schroeder首次提出以顶点删除这种基于几何元素删除的模型简化方法[Schroeder92]。该方法首先根据模型局部的几何拓扑特性，将顶点划分为简单顶点、复杂顶点、边界顶点以及位于特征边上的内部点和尖角点。然后根据各类顶点删除所导致的误差决定该顶点的删除。如误差允许，则删除该顶点并对删除该顶点所遗留下的空洞进行三角化。顶点删除法算法简单，执行效率高。Schroeder将该技术应用于医学CT数据中抽取的等距面模型及地表模型的简化，大量消减了原模型中的三角形数目，同时算法保留了原模型的几何特征。

1993年，Hoppe提出以边操作实现模型简化的LoD模型自动生成算法[Hoppe93]。该方法最大的特点即通过对边的各种操作（边蜕化为点、边对换、顶点分裂）来求取能量意义上的原模型的最优逼近模型。该方法以边蜕化为一新的顶点，以被蜕化的边的两端点对应新顶点，由原端点的连接关系就可得到简化区

域的保持原连接关系的三角面模型，避免简化操作后的三角化问题。Hoppe方法首次提出了以顶点合并，即边的顶点合并为一个新顶点这一复杂模型简化方式，避免模型简化后复杂的三角化过程，为任意网格模型的层次细节模型的实时生成的提出作了良好的先期工作。

1994年，Hamann提出了基于面删除的模型简化方法[Hamann94]。该方法以三角面各顶点的主曲率判定模型中各三角面所处区域的平坦程度，并由此决定各三角面对原模型的重要程度。算法以各三角面的重要性的大小决定各三角面删除的先后。为避免对三角面删除所遗留的空洞进行复杂的三角化过程，算法采取了类似于边退化为顶点的方法来避免局部区域的复杂三角化过程。算法将所删除的三角面的顶点合并为一新的顶点，由此新顶点对应所删除三角面的三个顶点，按原顶点的连接关系即生成该局部区域的三角化模型。

此后，人们又提出了基于面合并的模型简化方法[Kalvin94]。虽然这些方法能有效地简化各种复杂模型，但所有这些方法由于必须对原模型大量数据进行逐个的判定且必须对简化后所遗留的空洞进行复杂的三角化过程，使得算法无法达到实时，尽管基于边蜕化的模型简化方法以及基于面删除的模型简化方法在避免复杂的三角化过程方面作了一定的改进。因而算法不得不预先产生原模型间断的简化模型空间，即预先生成满足不同几何精度的多个简化模型。这不仅带来了存储空间的耗费，而且由于绘制模型的不同必然带来图形画面的跳跃。

1995年，Hoppe在原有的边操作算法基础上提出了累进网格的概念[Hoppe95]，首次较好地解决了模型简化方法在实际应用中所遇到的问题。该算法根据边蜕化简化操作的可逆性及边蜕化方法良好的局部拓扑维护性，将三维模型中每条边按照它们被删除后导致的几何误差大小排列，从小到大进行删除得到一个可逆的原模型的累边网格表示。而利用顶点分裂这一与模型简化操作─顶点合并相逆的过程来恢复模型简化所删除的信息。为了得到模型细节的删除信息，算法在模型简化的预计算中记录下边蜕化为新顶点这一简化过程中原顶点与新顶点的对应关系，并由预计算中记录下的每一简化过程得到一个由原模型的基本网格和一系列的简化信息组成的渐进网格表示模式。在实时绘制时，通过跟踪记录下的边蜕化为新顶点的对应关系，算法可以根据这一跟踪线索由基本网格模型逐步恢复所删除的模型细节，实时得到原模型连续精度的简化模型。该算法以边蜕化所导致的模型

几何误差的大小指导模型简化的顺序，并由此生成几何误差由小到大的渐进网格模型。

此后，Isler基于以上算法特点，根据面删除以及边蜕化简化算法的特点，提出了一种实时的多分辩率方法[Isler96]。该方法首先以围绕各顶点的三角面之间的夹角大小判定各顶点所处区域的平坦程度，并由此决定各三角面的视觉重要度。该方法根据三角面各顶点所处区域的平坦度决定三角面蜕化的方式，即是否此三角面蜕化为一新顶点或此三角面的一边蜕化为一新顶点。为减少计算，算法有三角面上的一顶点作为新顶点，从而避免了三角化过程。当然，由于复杂模型庞大的数据量，如果算法必须对各三角面作逐一的判定，算法是无法达到实时的。为避免对复杂模型的各个三角面逐一判定，算法采用了静态简化方法预先产生几个关键的简化模型，并对其中的三角面按照它们的视觉重要度进行排序。在实时绘制过程中，算法选择一个最少的但又比所需要的分辨率高的近似模型，按重要度从小到大地删除三角面直到刚满足当前精度为止。算法建立三角面删除队列，记录三角面在实时计算中最近被删除的信息，以此加速实时模型的简化，实时得到原模型连续精度的网格模型。

根据以上算法的特点，我们以顶点删除算法为基础，提出一种渐进网格模型的生成算法。算法以顶点删除简化方法实现原模型的简化。为避免复杂的三角化过程，算法选择与被删除顶点相关的一顶点作为起始点对遗留的空洞进行局部三角剖分。根据不同顶点分类，算法计算相应顶点的重要度，由小到大顺序删除各顶点，并以一定的结构记录下模型简化的过程，得到一种新的渐进网格模型的表示。该种渐进网格模型的表示方法可以根据当前视点参数实时产生当前视点的适当简化模型，克服了Isler算法必须预先产生多个简化模型的不足。为保证所得到的三角化模型保持原模型的拓扑特性，算法进行相应的半空间检测。

2.2基本定义

为了便于进一步叙述，我们首先给出一些基本定义：

定义1：空间中一组三角形，于公共边及顶点处相邻接，把这样的一组三角形定义为三

角形网格M。M可以由顶点集合V={v1, v2, ..., vn}和三角形集合T={T1, T2, ..., Tm}所组成的二元组（V，T）来表示。

定义2：对TM中任一顶点v，有一个或多个三角形与顶点v相关，把这些三角形定义

为与顶点v相关的三角形Tv，简称为相关三角形。

定义3：对M中的任一顶点vi，将与vi相关的所有三角形Tik按逆时针方向排列。如果

构成一个有序三角环，则称此顶点为中间顶点；如构成一个半环，则该顶点为边界顶点。

定义4：如果与顶点v相关的三角形Tv能构成一个有序的三角形环，并且此三角形环中

的三角形的边只与两个三角形相邻接，那么此顶点v称为简单顶点。

定义5：如果与顶点v相关的三角形Tv能构成一个有序的三角形环，并且此三角形环中

的三角形的边不只与两个三角形相邻接，那么此顶点v称为复杂顶点。

定义6：两个相邻的三角形Ti和Tj，如果其两面角大于某个指定的特征角，那么这两个

三角形所公共的公共边称为特征边。

定义7：对于TM中的简单顶点，可以根据局部的几何特性进一步分为内边顶点或角顶

点。如果简单顶点与两条特征边相关，则此顶点称为内边顶点。如果简单顶点与一条或多条特征边相关，则此顶点称为角顶点。

定义8：设与顶点相关的有序三角形环或半环中的每个三角形的法向量为ni，中心坐标

为xi，面积为Ai。定义由式1）确定的法向量n和中心点x所构造的平面为该

三角形环或半环的平均平面

niAiiN ， nAiN， xNxiAiAi 1）

2.2.1顶点的分类

三角性网格简化算法的第一步是计算每个顶点的局部几何和拓扑特性，并由此决定各顶点的分类（见图一）。这一过程的输出结果是决定各顶点是否为可删除的候选顶点。如果是候选顶点，则根据不同的顶点类型决定各顶点的重要度。

顶点的分类过程可以用以下的算法来描述。算法：

步骤1：对TM中的每一顶点v，求与v相关的三角形Tv，作步骤2。

步骤2：使用上面给出的定义，判定顶点v是否为边界顶点，复杂顶点或简单顶点。

对简单顶点再作步骤3。

步骤3：使用前面的定义，判定相邻三角形的公共边是否为特征边，并根据特征边

的数量确定顶点为内边顶点还是一般的简单顶点。对三角形网格中每个顶点执行算法后，每个顶点被定义为五类顶点中之一（见图一）。

vvv 简单顶点复杂顶点边界点vv 内边顶点图一角顶点

2.2.2 重要度定义

我们以简单顶点和边界顶点作为顶点删除的候选顶点，定义该点的重要度定义如下： 1。如果点P为简单顶点，则该点的重要度为该点到该点相关顶点所形成的环的平均平

面f的距离（见图二）。设该平均平面的单位法向量和中心点分别为n和x，则点的P重要度即为

I (p)=d(p, f)=n(px) 2）

平均平面d(p, f)图二

2。如果该顶点为边界点，则该点的重要度为该点到相关顶点所形成的半环的平均平面的距离d(p, f)和该点到相关的边界顶点所形成的直线l的距离d(p, l)(见图三)中的最大值。即

I(p)=max(d(p, f), d(p, l))

设点p相关的边界顶点为s和e。如图三所示。那么点p到直线se的距离可由下面公式求取。

设u=sp, w=se, u=a, w=b

那么：c=

uw, d(p, l)=a2c2 bsd(p, l)ve图三

2.3 算法原理

算法以顶点删除法实现对原模型的简化，并以与该顶点相关的某一顶点与不相邻顶点相连实现对顶点删除后所遗留空洞的三角化（见图四）。我们将这一过程记为Merge(vs,

vs1, I(vs), ns)。这里ns为平均平面的单位法向量或顶点vs到相关的边界顶点的连线的垂线的单位法向量。把顶点vs1叫作三角化的起始点。从图中可以看出，顶点vs的删除相应于两个三角形vs vs2 vs1和vs vs1vs6的删除。

vs1vs2vsvs5vs3vs4vs6vs5vs4 Mergevsvs1vs3 Splitvs2vs1vs2vs3vs6vs5vs4 Splitvs3vs4 Mergevs2vs5vs1 图四

MergeMn-1M=MnMn-1MergeMn-2.....M1MergeM0M0

算法以各顶点的重要度决定各顶点的删除顺序。由此，通过顶点删除我们得到原始复杂模型的一个连续的简化模型序列: 这里M0为原物体的基本网格模型。

随着顶点的删除，算法按顺序记下删除顶点的过程队列LMerge（Merge(vsn, vsn1, I (vsn),



Merge(vs（n-1), vs（n-1）, I (vs（n-1)), ns(n1)), ...., Merge(vs1, v11, I (vs1), ns1)），并根据原模ns1)，

型三角形被删除的先后得到原模型所有三角形的按删除先后排列的三角形队列LTri。我们将这两个队列表示作为本算法渐进网格模型的表示形式。由于每个顶点的删除相应于两个三角形的删除，我们可以很快得到顶点删除个数与简化模型的对应关系。从图四可以看出，顶点的删除过程Merge是一个可逆的过程，记为Split。根据所记录的内容我们可以得到该简化区域原来的细节。那么，根据基本网格模型M0及顶点删除过程队列LMerge的信息就可以恢复得到原网格模型相应的简化模型序列：

SplitM0M0M1SplitM1.....Mn-1SplitMn-1Mn=M

2.4实时绘制

在实时绘制时，我们根据当前视点参数，以前一帧的简化模型由渐进网格模型的表示信息可以很快地得到当前帧相应的细节模型。算法在过程队列LMerge设置上一帧简化模型最后被删除顶点的位置指针。如果当前帧物体远离视点，则算法从位置指针向下移动，删除相应的顶点得到进一步的简化模型。如果物体靠近视点，则根据过程队列中被删除的顶点信息恢复被删除的细节，直至满足当前精度为止。算法依顶点删除中记录下的误差值（即顶点的重要度）在屏幕上的投影决定当前帧所应恢复或删除的信息。

为说明起见，我们作如下设定：

设世界坐标系以地平面为xy轴平面，垂直向上为Z轴。

设视点V在世界坐标系下的坐标为view。视点坐标系各坐标轴单位向量在世界坐标

系下的表示为x(x1,y1,z1)，y(x2,y2,z2)，z(x3,y3,z3)。

设视点与投影平面距离为d。

考虑顶点vs。设过程队列Lrem中所记录的该点的删除信息为Rem(vs, vt, I (vs), n)。

那么，根据所考虑顶点的位置及删除信息我们可以计算此顶点误差在屏幕上的投影大小（见图五），并由此决定是否删除或增加。

vsview图五

设顶点vs到视点view的水平距离为hd(vs, view )。根据法向量n与屏幕坐标轴z可

以得到法向量与屏幕坐标z轴的夹角( n·z )，因而可以得到顶点误差I (vs)在屏幕上

的投影大小Projection(I (vs))公式为：

Projection(I (vs))=d* I (vs)*( n·z ) hd(vs, view ) d* I (vs)*( n·z ) hd(vs, view ) 1)

如果Projection(I (vs))小于用户定义的误差范围，即

则认为该顶点vs可以删除。

当然，在实际应用中，模型并非总是从最基本的网格模型开始。因而，如果仅根据顶点删除信息一步步跟踪实时生成适合于当前视觉参数的精度模型是不可能的。从图四我们知道每个顶点的删除相应于两个三角形的删除，由此我们可以根据顶点删除的个数很快地找到相应的简化模型在三角形队列Ltri中的指针，由此得到相应的简化模型。在实时绘制过程中，算法选择一个最少的但又比所需要的分辨率高的近似模型，按重要度从小到大地从位置指针开始删除三角面直到刚满足当前精度为止。

为尽快找到顶点的删除个数，我们计算出一个物体内误差段投影长度不超过用户定义误差范围的最小长度值Is，即此物体内分别具有最大投影处不超过用户定义范围内的误差段长度值。根据这个值，我们可以根据顶点的重要度在顶点删除过程队列LMerge中找到当前简化模型最后删除的顶点指针。再根据顶点的删除个数很快地找到相应的简化模型在三角形队列Ltri中的指针，由此得到相应的简化模型。

当然我们无法得到原模型精确的Is值。我们根据公式1)及模型的范围得到Is的大致取值范围。假定此模型包围在点Bmin=(xmin,ymin,zmin)和Bmax=(xmax,ymax,zmax)形成的长方体中。其中，(xmin,ymin,zmin)、(xmax,ymax,zmax)分别为此长方体包围盒的最小最大坐标。设：

f(I) = d  ( n·z )  hd(vs, view ) 2)

求取Is，即求取满足等式

Is  f(I) = 

的最小值。即求取f(I)的最大值，在包围盒[Bmin,Bmax]范围内。

设 ( n·z )=1，则f(I)的最大值即相应于hd(vs, view )。根据包围盒的范围我们可

以很快得到此值。

2.5预处理

算法预处理过程中由顶点删除产生原复杂网格模型的基本网格模型。算法按顶点的重要度从小到大指导顶点的删除先后。

2.5.1预处理过程

我们给出预处理中建立有序渐进网格的过程：

1。初始化：计算模型上每个顶点的重要度，并根据重要度的大小建立所有顶点从小

到大进行排序的顶点序列。

2。从顶点队列中选取一个具有最小重要度的顶点。

3。检查该顶点删除的合法性。如果合法，转步骤4；否则转步骤5。

4。从该顶点相关的顶点中选取一个顶点作为起始点对该顶点删除所遗留的空洞进

行三角化。如果找不到一个顶点可以对所遗留的空洞进行三角化，则转步骤5；否则，再计算所有相关顶点的重要度，重新对所余顶点进行排序。同时算法将相应的简化过程和删除的三角形填入简化队列LMerge和三角形队列LTri中，转步骤6。

5。算法暂时不对该顶点进行处理，选择其后的顶点，转步骤3。

6。返回步骤2直至模型中只余最基本的三角形，将其放在三角形队列中。结束算法。

2.5.2顶点删除合法性检测

为保证顶点v删除后模型的拓扑特性，算法必须保证所遗留的空洞的边界不相互自交。算法作下述判定：

1。获取点v的所有相关点的位置坐标。

2。将点v的所有相关顶点投影到点v的切平面上，组成一个封闭的多边形。 3。根据该切平面与XY平面、YZ平面、ZX平面夹角的大小，选择在那个平面上

对多边形再次进行投影。

选择方法比较简单。设点v的单位法向量为n，其x、y、z坐标为n(x)，n(y)，n(z)，

它们分别为单位法向量与x轴、y轴、z轴夹角的余。

设x=arccos (n(x))，y=arccos (n(y))，z=arccos (n(z))，取x、y、z三者中最小的角度的平面作为投影平面。

4。判定投影平面上的投影多边形的边界是否自交。

2.5.3三角剖分起始点的选择

为保证得到最佳的三角剖分，我们选取所有相关顶点中能使三角化得到最大平均形态比的顶点作为三角化的起始点。

所谓三角形平均形态比即三角形的内切圆半径与外切圆半径之比。平均形态比最大准则是有限元网格划分中网格划分质量的重要评判标准[Min94]。它与Circle准则以及最小角最大准则等价，都产生Delaunay三角划分。在这里我们借用此概念定义多边形顶点的权值，控制多边形剖分所获得的三角形形态质量。

2.6实验结果

我们以兔子模型验证我们的算法，建立兔子模型的渐进网格模型表示，并给出实时绘制时根据渐进网格模型产生连续分辨率近似模型所采集的数据。

我们以为，连续分辨率近似模型的复杂度在相续帧之间应该是平滑过度的。即被控制的模型的三角面的数目应随视点的连续变化而连续的变化。视点的小变化不会也不应导致模型的大变化。通过实验我们验证了本算法给出的渐进网格模型实时绘制算法的有效性。图六给出在一定误差范围下实时绘制时连续帧所产生的近似模型的面片数目变化的性态曲线图。

从以上图中可以看出，随视点的变化我们可以得到一系列的近似模型，近似模型的面片数与视点的变化基本成线性关系。在彩图2.1中我们给出连续帧下所得到的一些近似模型的绘制效果图。从彩图2.2中我们可以看出这些近似模型随视点的移近模型细节的不断增加。

2.7小结

本章给出了一种渐进网格模型的生成算法。该算法记录下整个模型简化过程中顶点删除的信息，并利用顶点删除与模型面片个数的对应关系，建立起渐进网格的表示形式。该算法使用于任意三角网格表示的三维模型。其最要的特点是可以根据当前视点参数产生连续的多分辨率近似模型，使得被绘制的三角网格模型的面片数目随视点的位置改变而产生连续的变化。实验证明这个算法是有效的。

彩图2-1兔子从远及近移动的多分辨率模型a)69396个三角形d)15400个三角形b)43473个三角形e)9476个三角形g)3272个三角形彩图2-2 彩图2-1中的多分辨率模型c)23543三角形f)5984个三角形

第三章基于图象空间判据的地表模型加速绘制技术

3.1引言

虚拟现实技术是近几年计算机图形学领域中发展起来的一种高度逼真地模拟人在自然环境中视、听、动等行为的一种人机交互技术[Cruz-Neira93]。它在实时仿真领域，如飞机汽车驾驶训练，战场作战模拟等具有重要的应用。这些系统皆涉及大规模复杂虚拟地表模型的动态生成，因而地表模型的实时绘制技术有着其重大的应用背景。

地表模型是一个有着一般多边形网格模型特点而又具有其自身鲜明特征的复杂几何模型。地表的LoD模型的自动生成有着不同于一般物体的LoD模型生成的要求。

首先，由于飞机或汽车驾驶者必须依据所观察到的地表特征来判定所在位置等，这就要求虚拟环境系统在满足实时显示的同时，算法应确保由近似网格模型生成的画面在一定的误差范围内。即算法应提供一种方法来确定由近似网格模型而引入的图形画面质量的误差。这就要求物体模型细节的选择应根据实时的视觉参数决定，而不仅仅是根据模型的几何误差来决定模型细节的选择。

其次，地表模型是一个有着大规模数据的大面积复杂几何模型，人眼所看到的仅仅是虚拟地表模型的一部分。因而，地表模型的绘制生成不仅应根据视点参数来简化不同远近的地表模型，而且，应根据视线方向、视域的不同赋予地表模型不同区域以不同的分辨率细节，以最大限度地减少地表模型的复杂程度，加速地表模型的绘制。

第三，为了实时跟踪地表面上的运动物体，地表网格模型的几何描述应可以进行直接有效的访问，即有关多边形和顶点的信息可以进行快速的空间索引。同时，在一般战场作战模型系统中，由于武器的摧毁作用，地表模型数据随时可能变化，因网格几何的动态改变而导致的曲面参数或几何的重新计算都不应影响系统的效率。

此外，地表模型的复杂性在相邻帧之间应该是平滑过度的。模型细节的简化以及模型细节的增加都不应引起网格的不连续现象，从而导致图形画面的跳跃，影响实时仿真训练的效果。

在以往的地表模型的层次细节模型的自动生成的研究工作中，人们通常采用规则网格和均匀网格作为地表的面模型的表示方式，利用一般模型的简化方法，如顶点删除法[Schroder94]，层次划分技术和小波方法生成地表模型的层次细节模型。其中，由于层

次划分技术可以生成地表模型具有多分辨率的层次细节模型而受到广泛的注意[Floriani95]。

非规则网格(Triangular-Irregular-Net)是由一组无规则散落在空间的点各自与其邻近点相连所生成的几何模型的三角面描述。其特点是可根据几何模型不同区域的平缓陡峭变化，形成大小各异、疏密不同的三角网格描述。由于其描述效率高，用非规则三角网格实现造型长期以来受到人们的普遍关注。这其中包括前面提到的各种基于层次划分技术的具有多分辨率的层次细节模型的自动生成方法。这些算法的一个共同点是对原区域实施进一步分割的点是从该区域选择出来的最能减少与原模型的误差的点，并由这些点实施对该区域的三角化。如[Polis96]一文中用点到平面距离作为误差值，以此值抽取特征点构成轮廓线，并以在此上轮廓线上的顶点作为对该区域分割的控制点，对这些点作Delaunay三角划分得到该区域具有更高分辨率的三角面细节模型。虽然非规则网格描述效率高，但由于三角化过程本身的复杂性以及非规则网格拓扑关系的繁杂性，使得各种基于非规则网格模型的细节层次模型的自动生成算法难以达到实时，仅仅只能根据原模型的几何拓扑特性，预先计算生成物体的多细节层次模型，而不能根据实时的视觉参数决定模型细节的取舍。

这里值得一提的是小波分析。自从1989年建立了多分辨率分析的严格基本理论基础，小波已成功地应用于计算机图形学中一系列问题的求解。小波分析为复杂网格模型的存储、传输、绘制及编辑提供了一种简单而一致的方法。Eck等人在Lounsbery[Lounsbery94]的工作基础上提出了一种将任意网格转化为具有细分连续性的网格，从而将小波方法的多分辨率表示扩充到任意网格[Eck95]，虽然均匀地表模型具有良好的空间结构，符合小波方法的细分连续性要求，但小波方法的误差判定仍是一个计算庞大的过程，因而要根据小波系数还无法作到根据视觉参数实时地生成地表模型的多分辨率模型。

均匀网格是地形等数字化高度模型(Digital-Elevation-Model, DEM)的一种常用面模型。其数据由一系列等间隔的地形高程值表示，代表一块方形网格地形。在这种模型中，格网交叉点处的高度就是对应地面某点的高程值，这些点的水平坐标值可从方形区域的行列号及间隔值推导出来。均匀网格由于其数据存贮位置能够反映实际数据的空间位置，因而这种数据格式非常便利于对数据的操作。其最大优点还在于可以非常便利地生成具有多分辨率的层次细节模型。因为对子空间实施固定模式的分割就可得到较高分辨率的细节模型，而不必象非规则三角网格那样必须从该子区域选择控制点并对其进行复杂的三角化处理。因而，均匀网格非常便利于实现地表特征物与地形间的自适应匹配。[Falby93]一文中的系统即采用其作为地表模型的具多分辨率细节模型的表示方式。但均匀网格局部区域的取样精度往往影响其周围区域的分辨率，因而其简化程度受到一定限制。

鉴于以上模型表示的特点及地表模型生成的要求，Linstorm等[Linstorm96]基于均匀网格模型良好的自适应性以及非规则网格表示的高效性，以面片合并法作为地表模型简化的基本方法，提出了实时连续的地表细节层次模型生成算法。该算法利用均匀网格良好的网格模式，递归地合并三角面，产生越来越粗的网格。这种微小的、增量式的改变提供了连续的细节层次，不仅避免了图形画面的跳跃，而且为图形系统保持恒定的帧频率提供了保证。这种基于规则网格表示的实时连续细节层次生成算法具有如下的特征：

* 细节层次是动态实时生成的：由于采用规则网格模型表示，算法不仅免去了一般简化操作中对模型拓扑关系的查询修改工作，而且避免了简化操作后必须对该简化区域实施复杂的三角化过程，从而使得面片合并操作得以实时动态的进行。

* 支持图象空间的质量度量：实时动态的LoD生成算法使得算法得以实现由近似网格模型而引入的图形画面质量的误差估量，并可根据绘制时间和绘制的图形画面质量生成相应的细节层次。算法以面片合并后简化模型所引起的视觉空间的误差作为面片合并简化操作的评判标准，生成了描述效率高且具有一定“真实性”的简化地表模型

* 曲面的几何复杂度在相邻帧之间是平滑过度的：视点的小变化不会导致模型复杂度的。更确切地说，对于视点的任意充分小的变化，模型中的三角形的数目的变化量最多为1。这个性质避免了动态显示中出现图形画面的跳变现象。

本章第二节慨要介绍Linstorm的算法及其主要不足；第三节介绍作者提出的基于精确视觉模型的地表模型加速绘制技术。

3.2 相关算法

由于非规则三角网格点、线、面关系的复杂性以及三角化过程的复杂性，使得基于非规则三角网格表示的面片合并多边形消减算法难以实时动态生成。因而实现地表模型的实时简化，就应设计好整个地表网格模型的点、线、面关系，避免复杂的三角化过程。Lindstorm的实时连续地表细节层次模型生成算法利用均匀网格良好的网格模式和非均匀网格表示的高效性，不仅避免了简化操作后必须对所遗留的空洞实施复杂的三角化过程，而且利用均匀网格模式良好的自适应性加快模型的简化。算法分为两步：首先进行粗简化，用来对曲面网格中的“块”选择具体的细节层次；然后进行细简化，算法递归地合并三角面，对块中的相应顶点进行移去操作，产生越来越粗的网格。

3.2.1 地表模型的均匀三角网格化

在Lindstorm算法中，数字地形模型可以用x-y平面上对称的三角形网格表示，离散的取样间隔为xres和yres。将此均匀对称的三角网格看作由最粗的三角形网格经过相同层次l(l  0且为奇数)的划分得到的（见图一）。将直角顶点与其对边中点相连即将此三角形分割为一对三角形，得到该区域更精细的三角网格。这一对三角形互为“三角形对”。而由其分割的那个三角形叫作此三角形对的“父亲”；反过来，它们又叫作其“父亲”的“孩子”。在网格递归过程中，对任何层n，顶点数目为(2n＋1)*(2n＋1)。

l = 0 l = 1 图一 l = 2 l = 3

将固定层次导致的网格定义为一个“块”。整个高度数据场划分为许多的这样的“块”，其中相邻块间的边界行列是共享的。通过相邻的四个高分辨率“块”隔行隔列粗取样便得到相应于此四个相邻“块”空间区域的较粗分辨率的“块”。此“块”与其相邻的同分辨率的“块”又可进一步粗取样得到更粗分辨率的“块”模型。算法由此建立基于“块”结构的整个高度数据场的多分辨率层次模型。

由此，Lindstorm首先将整个地表数据场组织为一个以“块”为空间单位的四叉树结构。而“块”内的数据有组织为一棵完全二叉树。其底层即为该“块”内区域最精细的三角面模型。中间层的三角面相应于较粗分辩率的三角面模型，它们通过各自三角空间中的一点，即相应于平面直三角对边中点的点“引入”各自的一对“孩子”；而此三角形对又以同样的方式“引入”各自的“孩子”。

3.2.2 实时连续地表细节层次模型生成算法

以上数据的组织为地表细节层次模型的实时连续生成提供了良好的基础。算法首先从整个数据场首先进行粗简化，用来对曲面网格中的“块”选择具体的细节层次；然后进行细简化，算法递归地合并三角面，对块中的相应顶点进行移去操作，产生越来越粗的网格。如果一对三角形合并后在图象空间所产生的误差小于用户定义的范围，则该对三角形在视觉分辨能力范围内可合并为一个三角形；此三角形又可与其相邻的三角形组成的三角形对进一步进行合并，直至其三角形对不再满足合并条件。以上算法在数据结构上是从二叉树底层开始，不断合并三角形对，直至三角形对合并条件不再满足或者其对应的三角形不能从最低层三角形对合并生成。

但该算法仅以视点位置与所考虑数据的距离建立简化的视觉空间模型，以此估计模型细节删除所带来的视觉空间的误差，删除那些对视觉效果影响不大的顶点，保留那些反映模型中几何特性的特征点。算法仅仅考虑到人眼由于距离远近所产生不同分辨率，即仅考虑LoD模型选择重要性因素的面积尺度因素，而忽略了人眼对处于不同视觉区域的模型细节的不同分辨能力。生理学告诉我们，在位于视网膜中心的位置人眼具有最敏锐的视觉分辨能力；一旦偏离视觉中心，人眼的视觉分辨力将急速下降[Cruz-Neira93]。因而对处于不同的视觉区域的模型区域赋予同一的分辨率细节将是很大的浪费。我们以为，为提高动态模型的生成速度，应充分利用人的视觉特点，对处于视觉不同区域的模型赋予不同的显示效果，最大限度地减少绘制模型的复杂程度。

为此，我们提出具有聚焦因子的基于图象空间误差的地表模型消减算法。算法以Lindstorm均匀网格模式为基础，以焦点以及显示面积二者有效的结合建立较为精确的视觉空间模型，以此模型衡量人眼对由于面片合并所带来的误差的分辨能力，并以此作为地表模型细节的重要度评价尺度，有效地加大了地表模型的简化。同时，算法结合均匀网格模型的多分辨率细节层次模型，以“块”作为地表模型大面积简化的空间单位，加速地表模型的简化操作，以实现较为复杂的地表模型的实时绘制。

本算法具有以下特点：

1)充分利用人眼的视觉特点加大地表模型简化。同时建立较为精确的视觉空间模型来确定由近似网格所带来的图象质量的损失。

1)视觉参数（视点、视线方向）的微小变化对地表模复杂度仅有微小的变化，以便维持恒定(或接近恒定)的帧频率。

3.3 LoD模型选择尺度

LoD算法的最大特点是根据人的视觉特点，以最小的图形生成代价获取最丰富的图形视觉效果。在以往的LoD模型选择算法中，由于层次模型不能实时地生成，因而人们通常只能根据整个图形对象对观察者所观察到的画面的贡献大小决定该模型的重要度，以此决定人眼对模型细节的分辨能力，并以此决定整个模型的细节层次的选择。换言之，模型细节的选择取决于整个模型对视觉效果的贡献程度。例如，若一个图形对象离观察者很近，或位于观察者眼睛焦点，那么，相对而言它理应具有比其它图形对象更佳的显示效果、更详细的细节。

图形对象的重要性取决于多个因素，虽然在不同环境中采用了各种尺度，但面积、焦点都是这些系统共同采用的物体重要性的重要尺度。这些尺度可以定义如下：

面积(size)尺度：屏幕上越大的物体对图象效果的贡献越大。在现存的LOD选择算法中，面积通常用物体的平均多边形所占象素点的总数来计算[Funkhouser92][Liu96]，或用物体距视点距离的方法来计算[Astheimer94][ Blake87]。

焦点(Focus)尺度：眼睛更加专注焦点周围的物体。因此，视线焦点周围的物体应具有更详尽的显示效果。Funkhouser等人曾根据物体重心距屏幕中心的距离逐渐降低物体的Focus值[Funkhouser93][ Liu96]。

在本算法中，我们以透视投影计算模型细节删除所导致的模型几何误差在视觉空间的投影大小，即细节模型的面积因素，并加上聚焦因子，建立较为精确的视觉空间模型，以此判定人眼对该细节的分辨能力，并以此决定该模型细节的删除，最大限度地简化地表模型的复杂度，加快地表模型的实时绘制。

3.4 具有聚焦因子的基于图象空间误差的地表模型消减算法

3.4.1 基于图象空间的具有聚焦因子的误差估计

当图一均匀网格中的一对三角形ΔABD和ΔACD合并为其“父亲”三角形ΔABC时，所产生的物理空间的误差应为ΔABC到ΔACD的最大距离，即为图二中D点到

ZAYMD 图二CX

BBC中点M的垂直距离，我们记为D。我们将世界坐标系的Z轴视为垂直向上，则

D=zD(zBzC)2。同时，我们把DM这条有向线段叫作数据点D的误差段。在

地表模型的简化过程中，如果此对三角形在数据点D的误差段在投影平面上的投影长度小于给定值，那么我们认为此对三角形可合并，即可由其“父亲”代替。

由前面叙述我们知道，Focus是LoD选择重要性的关键尺度之一，因而对应于不同视区范围的地表模型应具有不同的显示效果。为此，我们引入基于图象空间的具有Focus因子的误差估计。为说明起见，首先我们作如下设定： 设世界坐标系以地平面为xy轴平面，垂直向上为Z轴。

设视点V在世界坐标系下的坐标为v(xv,yv,zv)。视点坐标系各坐标轴单位向量在世

界坐标系下的表示为x(x1,y1,z1)，y(x2,y2,z2)，z(x3,y3,z3)。

设视点与投影平面距离为d。投影平面坐标以xy坐标衡量。以下推导过程中各字母的下标view 、proj分别代表在视点坐标系和投影平面坐标系下；否则为世界坐标系下。利用两向量之间的点积公式，我们知道世界坐标系下任一点p(xp,yp,zP)在视点坐标系下的坐标Pview(xviewp,yviewp,zviewp)为：

xviewp(PV)x(xp,yp,zp)(x1,y1,z1)(xV,yV,zV)(x1,y1,z1)yviewP(PV)y(xp,yp,zp)(x2,y2,z2)(xV,yV,zV)(x2,y2,z2)1)

z(PV)z(xp,yp,zp)(x3,y3,z3)(xV,yV,zV)(x3,y3,z3)viewP按透视投影，点P在投影平面上的坐标为Pproj(dxviewpzviewp,dyviewpzviewp)。所以点D的误差段DM在投影平面上的投影长度为：

screenD =

d(xviewDzviewDxviewMzviewM)2(yviewDzviewDyviewMzviewM)2

我们假定图二中点D在世界坐标系下的坐标为(xD,yD,zD)，D点误差段长度为D。那么可知，点M的世界坐标系坐标为(xD,yD,zD＋D)。由1)知： Mview－Dview ＝ (xviewM,yviewM,zviewM)－(xviewD,yviewD,zviewD)

＝D*(z1,z2,z3) 2)

而‖Mview－Dview‖=

D，所以z12＋z22＋z32 = 1 3)

为了提高实时显示的效率，我们可以利用人的视觉特点以减少绘制模型的复杂性。眼睛焦点区域应比其它区域有更好的显示效果，周围视觉区域可以以较粗分辨率的模型表示。而依一般透视投影变换公式计算，处于不同视觉区域、与视点距离相同的误差段的投影相差很小，因而不足以使算法得到较大的区别。所以，如按严格计算的误差段的投影长度来合并三角形对，将使得处于周围视觉区域的网格具有与焦点区域网格同样的显示效果。为此，我们以视线方向与点D到视点连线的夹角的余弦cos作为权值，计算D点的误差段的投影长度。我们知道 z(DV)z cos = = viewD

DVDV同时，我们注意到2)中zviewM与zviewD之间的差值仅为Dz3值，其中｜z3｜≤1，D＜＜zviewD，所以我们可以假设zviewMzviewD。

由以上推导，我们可以得到D点误差段在图象空间的投影长度

scree n= Dd(xviewDxviewM)2(yviewDyviewM)2zviewD

dDz1z2zviewD22

加上Focus因子，这时有：

= screenD*cos scrn D = 

dD1z32222(xDxV)(yDyV)(zDzV)

如果scrnD小于用户定义的误差范围ε，即

dD1z32222(xDxV)(yDyV)(zDzV)   4)

则认为D点引入的一对“孩子”可以合并，即为其“父亲”所取代。

3.4.2 基于物体空间区域分块的模型简化加速方法

DEM数据往往由上万甚至上百万个数据组成，如果仅凭前一节描述的简化算法在正常条件下是很难实现地表模型的实时简化的。为此我们引入Linstorm算法中的“块”的定义，并把此块内引入最低层三角面对的数据点叫做此“块”的最精细顶点。从相邻四个这样的“块”删除它们的最精细顶点，便得到一个“块”相应于原来四个“块”空间区域的粗分辨率“块”网格模型。如此，整个数据场便组成了以“块”为空间划分单位的具有多分辨率的层次细节模型。

在施行简化算法时，为加速简化实施过程，首先对块进行判断，以“块”为评判单位。如果通过对一个“块”的估计可以大致知道此“块”的哪些顶点可以删除，那么，我们可以很快地得到此“块”的简化模型；进一步，如果此“块”及其周围三“块”的最精细顶点都可删除，那么，我们可以立即以此四“块”区域的较粗分辨率“块”模型拟合该四块区域；而此“块”模型又可以“块”为评判单位加速简化。从而避免了对大量数据点的误差段进行逐点投影计算，大大加速了地表模型的简化过程。

为此，我们分别计算出一个“块”内误差段投影长度不超过用户定义误差范围的最大长度值l和最小长度值s，即此块内分别具有最大投影处和最小投影处的不超过用

户定义范围内的误差段长度值。因而，对此“块”内所有误差段长度小于s的数据点，我们可立即断定其误差段的投影小于用户定义范围，即其可能“删除”；对大于l的数据点，则知其误差段的投影必定大于用户定义范围，不可“删除”；对介于s与l之间的数据点我们则需依公式4)进一步作判定。如果此“块”内所有最精细顶点的误差段长度值都小于s，且其周围三块也都如此，那么可判定该四块区域可由该区域较粗分辨率“块”表示。而此“块”又可重复上述操作加速地表网格模型的简化。

从以上可知，整个地表模型的实时简化关键在于数据块的l和s的计算。当然，我们无法实时逐点地计算各点的投影，以求取“块”内误差段投影长度不超过用户定义误差范围的最大长度值l和最小长度值s。但我们可以利用一个“块”的空间位置来求取一个“块”内误差段投影长度不超过用户定义误差范围的大致上下界。假定一数据块包围在点Bmin=(xmin,ymin,zmin)和Bmax=(xmax,ymax,zmax)形成的长方块中。其中，(xmin,ymin,zmin)、(xmax,ymax,zmax)分别为此长方体包围盒的最小最大坐标。令fD =

z12z22zviewD

要求满足于4）式的最短与最长的l与s，即要求满足方程 dDfD*cos 的D的最大最小值。其中

xD[xmin,xmax]，yD[ymin,ymax]，zD[zmin,zmax]，且 (xDxV)(yDyV)(zDzV)  d

为方便求解，我们作如下假设，以快速求得大致的上下界。假设D点总处于视觉

中心，即视点坐标系-z轴方向。故z =（VD)VD，即视点坐标系z轴坐标为(（VxDx)VD，（VyDy)VD，（VzDz)VD)，有zviewD = DV。根据式3）我们有： fD =

2222(xDxV)2(yDyV)2(xDxV)(yDyV)(zDzV)222

因而求解l与s，即求解满足上述条件的fD和cos的最大最小值，然后根据D =

(dDfD*cos)求取相应的l与s。

依fD的定义知，要求取fD的最大值，(zDzV)2必须取最小值。根据最大最小值原理，(xDxV)2(yDyV)2(zDzV)2时，fD有最大值，如果(xD,yD,zD)满足条件；否则，(xDxV)2(yDyV)2相应增大减小求得fD的最大值。fD的最小值以相同方法求得。

3.4.3 具有时间连续性的地表模型的实时简化

由于观察者运动的连续性，人眼所观察到的场景在时间空间具有一定的连续性，因而前后帧画面具有一定的相关性。为加速地表模型的实时简化，必须充分利用前后帧画面的相关性，以达到地表模型的实时生成。为此，我们为上一帧画面设立一个活动块指针队列，记录上一帧画面以块为单位的地表简化模型，作为当前帧以块为单位的地表模型简化的初始值。在当前帧，根据当前视觉参数决定初始块的分辨率是否满足视觉要求，否则以更精细或更粗的块模型代替，避免了以块为单位的地表模型的简化必须从最精细的模型开始。同时，我们为前一帧每个活动块记录当时所计算的l与s值，记为ll与

ls。那么，根据当前帧所得的此数据块(如果此数据块在当前帧仍为活动块)的l，我们立即知道误差段长度值小于ls且小于s的数据点即为当前帧与前一帧画面共有的共同点；而大于ls小于s的数据点则是当前帧需对前一帧的修改处。对ll与l也一

样。

3.4.4 网格递归消减的数据结构

从以上叙述我们知道，三角面对的合并过程实质即引入此三角面对的数据点的删除过程，也就是父面片取代子面片对的过程。因此，引入此三角面对的数据点的可删除状态实质决定了此三角面对的父面片的“存在”。为此，我们又把此数据点叫作此父面片的“控制点”。地表网格模型的简化过程，即二叉树三角面对从下向上的合并过程，就是决定各数据点所“控制”的父面片的“存在”过程，也是各“控制点”的“删除”过程。所以，子面片的“控制点”可删除状态将是其父面片的的“控制点”可删除状态的决定因素之一。以下我们把子面片的“控制点”叫做父面片“控制点”的“子数据点”；反过来，父面片的“控制点”叫做子面片的“控制点”的“父数据点”。

从图一中我们可以看出，除正方形区域的边界数据点及中心点外，正方形区域内每个数据点都引入二对三角形对，共四个三角面片。而这四个三角面片的“存在”又取决于各自的“控制点”的可删除状态。故每个数据点的可删除状态将由其自身误差段在图象空间的投影决定外，还将由其四个子数据点的可删除状态决定。为此，每个数据点除设置高度值和值位外，还设置五个状态位：attribute位—值在图象空间的判断位；child1→4—四个子数据点的可删除状态位。

根据以上数据设置，对正方形区域任一数据点首先判定其所引起的视觉误差而置其attribute位。如果该视觉误差小于用户定义的误差范围，即attribute位为真，且其四个child位也同时为真，那此点可删；即该数据点控制的三角面可“存在”。此面片可进

一步合并为其父面片。因而置此点的父数据点的相应child位为真并进一步判定此父数据点是否可删。如果不可删，则停止。当我们对正方形区域内所有数据点都进行了如此判断，就得到整个区域的简化模型，而不需真正建立二叉树。在实时绘制时，只需根据特定正方形区域的四角顶点下标及数据间隔，经过简单的下标中点计算即到相应于二叉树根三角面片的控制点。由该控制点的可删除状态即可知该三角面片的“存在”与否，即该面片所覆盖区域的其它数据点是否在图象空间的误差判断下都可删除，而以此三角面片拟合该区域数据。如果不可，则依此三角面片的顶点下标值得到各子面片对，依上进一步判定，得到该区域更精细的三角面模型。

3.5 实验结果

我们通过一个由1025*1025个数据点组成的地形高度数据场（取样精度为2*2平方米）的实验地表模型验证了本文算法的效率，以下是其实验结果。以下列表数据分别给出相应于不同值具有聚焦因子(见表一)和没有聚焦因子(见表二)的地表细节层次模型实时生成算法在相同路径下连续帧内对地表模型简化后所绘制的三角面片数目。

表一

的取值  = 0.5  = 1.  = 2.  = 4. 第一帧第二帧第三帧第四帧第五帧 129146 131829 134653 137150 141592 51983 53729 55253 56612 57896 表二

的取值  = 0.5  = 1.  = 2.  = 4. 第一帧第二帧第三帧第四帧第五帧

150558 152582 154655 156753 158629 62023 62686 63480 64150 64871 20876 21122 21365 21414 21315 7286 7264 7291 7327 7295 17581 18288 19026 19661 19959 6143 6399 6492 6784 6843 从列表数据可以看出，基于图象的误差判据并以“块”为单位的层次数据结构的使用能非常有效地控制场景的细节。当屏幕投影的高差值限制放宽时，所需绘制的场景复杂度有可能以数量级的级别递减。

彩图3-1、3-2分别为=1和=2时生成的相应地表模型画面，彩图3-3为=2时与彩图3-2相隔两帧的同一数据场的不同地表画面。

3.6 小结

本章以焦点以及显示面积二者有效的结合为视觉空间建立较为精确的模型，衡量人眼对地表模型细节的分辨能力，并以此作为地表模型细节的重要性评价尺度，决定地表模型细节的删除，有效地简化了地表模型的绘制。同时，算法结合均匀网格模型的多分辨率细节层次模型，以“块”作为地表模型大面积简化的空间单位，利用前后帧画面的相关性，加速地表模型的简化操作以实现较为复杂的地表模型的实时绘制。

彩图3-1彩图3-3彩图3-2

第四章一种辐射度全局光照网格模型的简化方法

4.1引言

虚拟现实技术是一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界面技术。无疑，使用户对虚拟环境产生犹如身临其境的可行性技术的应用是虚拟现实走向成功的必要条件。这其中包括先进的交互技术、传感技术、视频技术等的发展和应用。而对于虚拟现实的虚拟环境而言，高度真实的图形视觉效果无疑是产生“现实”感觉的必要条件。VR所期待的目标自然是高质量真实感的逼真图形。

物体的光照颜色纹理不仅能为物体提供真实的外部特征，而且为人眼提供了丰富的邻近、遮挡等视觉信息。在图形学中，光照明模型主要研究的是如何用数据模型和计算机来模拟自然界中的光照明的物理过程。它是生成真实感图形画面的关键。图形学中使用的光照明模型可以分为局部光照明模型(local illumination model)和全局光照明模型(global illumination model)。局部光照明模型仅考虑光源对物体表面的直接照射，而忽略了光能在环境景物之间的传递。虽然局部光照明模型计算比较简单，但它们所生成的图形难以真实地反映环境中的光能分布，很难生成表现自然界复杂场景的高质量真实感图形。为了增加图形的真实感，必须考虑环境的漫射、镜面反射和规则透射等对景物表面产生的全局照明效果。使用全局光照模型显示具有复杂场景的真实感图形必然是VR所追求的目标。

全局光照明模型的计算主要有两种方法：光线跟踪方法和辐射度方法。光线跟踪方法是Whitted为求解环境中来自镜面反射方向和规则透射方向的入射光对物体表面光亮度懂得影响由光线投射技术发展而来的一种全局光照模型的计算方法[Whitted80]。该方法光线的逆向跟踪模拟自然界中光在环境中的传播。为了能处理一般的非理想镜面环境，人们相续提出了分布式光线跟踪算法和双向光线跟踪算法。由于光线跟踪方法考虑了从镜面反射方向和规则投射方向附近区域中来的入射光对物体表面光亮度的贡献，光线跟踪能够真实地模拟镜面映象、模糊透明、运动模糊、景深、半影等效果。这是局部光照明模型所望尘莫及的。光线跟踪巨大的潜力在于它可以模仿自然界中光的传播，但它存在两个主要的缺点。首先，由于光线跟踪技术建立在空间采样的基础上，采样光线的数目受到很大的限制，因而它无法模拟光能在景物表面间由漫反射到漫反射的能量传播形式，大大

地影响了生成图形画面的真实性，因而该方法仍有很大的局限性。其次，光线跟踪在计算每个象素光亮度时都要生成一棵庞大的光线树，建立光线树以及计算每个结点光亮度都要进行大量的直线与曲面的求交计算。庞大的求交计算量使得图形绘制耗费大大增加。而这些计算固有地与视点相关，因而光线跟踪技术的实用性受到很大的限制。这也是光线跟踪在相当长的一段时间内不可能作为VR可用的光照模型的主要原因。

1984年，Goral等从热辐射工程中引进辐射度方法，提出了封闭环境的漫反射分量的整体求解思想，从而有效地克服了在求解漫射分量时由于光线采样带来的巨大计算量。辐射度技术根据能量平衡原理以环境中曲面之间的能量传递形式计算每一曲面上的能量分布，因而能从整体上来正确计算环境中每一曲面上的光能分布。并由此求出被观察点的光亮度。由于辐射度以环境中的曲面片之间的能量传递来计算曲面的能量分布，曲面光亮度的计算与画面绘制所选择的观察位置和方向无关，因而辐射度是一种与视点无关的计算方法。其大量计算可作为预计算，所以辐射度极有可能成为虚拟现实技术中真实感图形生成的工具。为此国外已有一些试验性系统成功地使用辐射度技术作为VR的光照模型[Astheimer93]。

然而，在辐射度计算中，为了模拟环境中物体相互辐射能量的光照效果，环境中的表面往往被分解得足够细以精确地捕捉由于物体间相互遮挡所引起的阴影效果及其它一些光照效果。虽然人们相继提出自适应划分[Cohen86] 以及各种阴影生成方法[Campbell90][Heckbert92]以较有效地减少整个场景的复杂度，但辐射度计算结果的模型复杂度往往是原有场景的几十倍甚至上百倍。以当今计算机图形工作站的绘制能力是无法实现一个具有辐射度全局光照效果的复杂场景的实时绘制的。

在本章中，我们给出一种辐射度全局光照网格模型的简化算法，自动生成虚拟场景具有辐射度全局光照效果的多细节层次模型，以加速具有辐射度全局光照效果的真实感图形画面的绘制。

4.2辐射度全局光照模型

在辐射度技术中，假设环境中的物体表面为理想漫射面。所谓辐射度B即指物体表面单位面积向外辐射的能量。根据能量守恒，环境中任一点x向外辐射的能量除自身作为光源向外辐射的能量外，还包括经物体表面反射周围环境对其辐射的能量。即：

B(x) = E(x) +(x)SB(x')G(x,x')V(x,x')dA' 1）

其中：B(x)为场景中物体表面中任一点x的辐射度，(x)是该点的漫反射系数；

x’为x周围环境表面中的任一点，dA’为该点所在微面元的面积； G(x, x’)=

cosi* cosoxx'2;

V(x, x’)为x 与x’的遮挡因子； S为环境中所有表面的集合。

为求解整个环境的光能分布，辐射度方法将整个环境分划成若干个面片Pi(i=0, ..., n)，并假设每一面片Pi具有常值的辐射度Bi，对x所在面片求积分并以有限的和近似方程1)，得到以下一组方程:

Bi *Ai= Ei *Ai +i*

j0nAj*Bj*Fji, i=0, ..., n;

其中：Ak是面片k的面积；

Fij是面片Pi对面片Pj的形状因子，且

Fij =

1AiAiAjcosi*cosodAidAj 2r求解上述方程即可得到整个景物空间的光能分布。而场景的色彩明暗变化即反应在各面片的辐射度大小变化上。

因而辐射度计算的结果即是原物体表面的网格化，且网格中的面片具有常值辐射度。当然，运用上述方法求出的是每一面片的平均辐射度。若直接用于绘制会引起画面上面片之间的明暗跳跃。为此在实际应用中一般采用各种插值法重新建立物体表面的光能分布。为利用图形加速器的图形生成能力，人们通常采用C0插值。首先以顶点周围面片的辐射度值的面积平均求取面片各顶点的光强，然后在图像空间以各面片顶点的光强线性插值生成整个环境的图形画面。

4.3 相关工作

4.3.1 具有全局光照效果的网格模型简化方法

我们在前几章所介绍网格模型的简化算法皆以几何误差约束的变化来指导模型的简化。然而网格模型的其它各种约束性质，如光照颜色纹理，应具有与几何

约束性质同等重要的地位。特别是光照颜色纹理，它为人们提供了丰富的形体、邻近、遮挡等视觉效果。基于这些算法，人们在具有全局光照效果的网格模型的自动简化上也作了一些尝试，取得了一些成果。

Hoppe在[Hoppe96]一文中首次提出保持除原网格模型的几何性质以外的其它性质的多细节层次模型生成方法的重要性，并将[Hoppe93]中的几何误差度量函数推广至网格模型的其他约束性质, 以边蜕化简化模式实现保持原网格模型各种性质的模型简化。该文将网格模型的所有性质划分为几何性质、标量性质和离散性质。离散性质定义了网格模型面的各种性质，如材质等；而标量性质则定义了网格模型各顶点的约束性质，如顶点的切向量、颜色值等。算法将标量性质与几何性质作了同样的处理，定义了类似于几何点到面的距离函数以作为由于顶点删除所引起的其它约束性质的误差。如，为衡量由于点删除所引起的光照变化，算法以点的RGB值对应于模型的几何约束，定义了点到面的RGB距离函数，以此衡量由于边删除所带来的模型光照效果的变化。同时，算法根据离散性质的不同识别模型特征以保持模型的特征。该算法对具有辐射度全局光照效果的网格模型进行简化取得了较为满意的效果。

此外，Huges[Huges96]分析了具有光照效果的网格模型与一般网格模型中特殊网格模型地表网格模型的特点，指出二者的相似之处，即两种模型简化皆可看作二维平面上一簇带某种约束的点的网格模型。该文将基于几何约束的一般网格模型简化方法—顶点删除法应用于光照网格模型的简化。作者利用变换将全局光照计算所得到网格模型中点的三维RGB约束值与地表模型中的一维高度约束值对应，将光照网格模型变为纯粹的几何模型，并以点到相关三角面的平均平面的距离决定该点是否可删除。

本章我们根据辐射度计算的特点，结合基于几何误差的模型简化方法给出一种辐射度全局光照网格模型的简化方法。本方法的特点在于：

第一，我们首先利用面片合并简化算法简化程度高的特点，以辐射度计算结果，而不是利用辐射度重新插值计算后所得到的网格模型各顶点的RGB值对全局光照网格模型进行第一步简化。基于这一点，我们提出以辐射度最大相对变化为准则，以面片合并简化操作实现辐射度全局光照网格模型的进一步简化。该准则不仅能较好地反映原光照网格模型的能量分布，有效地简化辐射度全局光照网格模型，而且能较好地保持原光照网格模型的特征。

第二，算法经过面片合并简化操作后得到的是一组由原模型顶点及原模型边组成的、能量的相对变化在用户定义误差范围内的多边形区域。为进一步加大模型的简化程度，算法以原模型中各顶点的RGB值决定多边形区域边界顶点的删除，实现超面区域的边界简化，进一步加大模型的简化。

4.3.2 面片合并模型简化法

面片合并模型简化法是Kalvin于1994年提出的一种复杂模型的简化方法[Kalvin94]。该方法的基本思想是把近似位于同一平面上的相邻三角形进行合并，形成一个大的多边形。再用数目较少的三角形网格来表示这个大的多边形。面片合并算法不仅适用于任意三角面片表示的复杂网格模型的简化，而且还可以适用于其他多边形表示的模型。其简化速度明显快于其他算法。

我们利用面片合并简化算法简化程度高的特点，以面片合并简化算法作为新算法的基算法，实现辐射度全局光照网格模型的简化。下面我们通过分析辐射度计算的特点给出本算法的基本原理，并给出算法中所用到的相关概念。

4.4 算法原理

从方程1)我们知道，由于环境中物体的相互遮挡，物体表面的辐射度分布存在着各类间断点。这些间断点，特别是第一、二类间断点为人类视觉提供了丰富的形体、邻近及遮挡等视觉信息。因而在光照网格模型的简化中不但应最大限度地简化模型，而且在简化过程中应充分认识并保持原光照网格模型的特征。

根据以上辐射度全局光照模型计算的特点，我们提出以辐射度最大相对变化值为合并准则、利用面片合并简化操作实现辐射度全局光照网格模型的第一步简化。这样得到的是一组由原模型顶点原模型边组成的、能量相对变化在用户定义范围内的多边形区域。为进一步加大模型的简化程度，算法以原模型顶点的RGB值的变化决定超面边界点的删除，实现原光照网格模型的进一步简化。为描述清楚，我们引入如下基本定义：

定义1、空间中一组多边形沿公共边及顶点处相邻接，把这样的一组多边形形定义

为网格模型TM。

定义2、三角网格TM中一组邻接的多边形构成的集合M称为此网格模型TM的一

个板块。

定义3、称以网格模型TM中一个板块的所有边界顶点构成的空间多边形为相应于

此板块的超面SuperfSM。构成此多边形的边称为此超面的边界。而与此超面邻接的原网格模型TM中的多边形叫作此超面的边界面片。

辐射度光照网格模型的简化过程即是面片自顶向上不断合并的过程，也即是相应超

面不断合并周围面片的过程，算法主要分以下几个步骤：

1、首先利用面片简化机制将辐射度全局光照网格模型划分为满足一定合并条件的板块，生成相应的超面，实现模型的第一步简化。

2、利用原模型顶点的RGB值，通过递归分割法实现超面的边界简化，完成模型的第二步简化。

3、然后以平均形态比加权的局部三角化方法实现超面的三角剖分，完成辐射度光照网格模型的简化。

4.5 主要算法

4.5.1 超面的生成

超面的生成过程即是其边界的不断扩张过程，也即是其边界面片不断被合并的过程。算法首先选择原模型中的面片作为初始值。随着其边界面片不断被合并，其边界不断扩张直至其所有边界面片不再满足合并条件。在这里我们称初始值面片为“种子”面片。

4.5.1.1 合并准则

从上节辐射度计算的介绍中我们知道辐射度计算的结果是原物体表面的网格化，并在画面最后的绘制中采用C0插值生成较光滑的图形画面。但由于采用线性插值，对间断点边缘处必须采用较密的网格，否则生成的画面会产生较明显的“漏光”现象。基于以上因素，本算法提出基于辐射度最大相对变化值的合并准则，并以所合并的面片的辐射度最大相对变化值的平均作为相应超面的辐射度最大相对变化值。试验证明辐射度最大相对变化值准则不仅能较好地识别位于间断点边缘处的面片，而且能较准确地反映物体表面光能的变化。

假设面片Pi具有辐射度值Bi，面积为Ai。它与n个面片Pij邻接。各面片Pij面积分别为Aij，辐射度值为Bij(j=1, ..., n)。我们定义面片Pi的辐射度最大相对变化值Ci为

Ci = max ( abs( Bi  Bij )  ( ( Ai + Aij )*Bi ), abs( Bi  Bij )  ( ( Ai + Aij )*Bij ) )，

j = 1, …, n.

如果超面SuperSM的某个边界面片Pj满足：

Cj < && (Cj *Aj + CSuperSM*ASuperSM)  ( Aj +ASuperSM)<

则边界面片Pj 满足合并条件，可以为超面SuperSM所合并；否则，不能为此超面合并。这里为用户定义的误差允许范围值。ASuperSM为超面SuperSM的面积，它为所合并的面片的面积和。

但以上合并准则仅能处理位于辐射度最大相对变化值在用户定义误差范围内的面片，却不能简化位于间断点边缘处的辐射度最大相对变化值大于用户定义误差范围但却具有相同的变化特性的面片。为此我们相对于超面SuperSM重新定义其周围面片P的辐射度相对变化值Cj’如下：

Cj’ ＝ max ( abs( Bi BSuperSM)  ( ( Ai＋ASuperSM)*Bi ),

abs( Bi－BSuperSM)  ( ( Ai+ASuperSM)*BSuperSM) )

这里BSuperSM为超面SuperSM的辐射度值，它为超面所合并的各面片的辐射度值的面积平均。如果该值小于用户定义的误差范围，则此面片可被超面SuperSM合并；否则，此面片不能合并。

综上所述，面片合并条件的测试可以总结为以下伪程序代码： int Merged(SuperS S, Patch P, float threshold) { float C’;

if ( P—>merged) retrun(0);

if ( (CP*AP+ CS*AS )  ( AP+AS )< threshold ) else }

CP’ ＝ max ( abs( BPBS )  ( ( AP＋AS)*BP ),

abs( BP－BS )  ( ( AP+AS)*BS ) )

}

if (CP’ < threshold )

return(1); return(0); else

return(0);

if ( CP < threshold ){ return(1);

else{

}

4.5.1.2 “种子”面片的选择

正如[Hoppe93]一文中所指出的，网格模型的简化问题是一个完全NP问题。本算法在网格模型的简化合并过程中仅以局部误差度量指导简化，“种子”面片的选择顺序对模型的简化结果将产生一些影响。因而本算法在模型的简化过程中由小到大顺序建立整个网格模型所有面片的辐射度最大相对变化值队列，并以此指导“种子”面片的选择。算法每次以队列头结点相应的面片为“种子”面片，不断合并周围面片，直至周围面片不再满足合并条件。如面片已被合并则不再参与“种子”面片的选择，并删除其在辐射度最大相对误差值队列中的相应结点。算法重复以上操作直至辐射度最大相对误差队列为空。

当然，以上算法仅以单一频率光的能量分布对网格模型进行简化。而在实际应用中，辐射度的计算结果一般为RGB三种单色光的能量分布。对此，人们通常采用两种方法来处理。第一种方法即如[Hughes96]一文中所作的一样，将RGB三色约束值与地表模型的一维高度约束值对应。第二种方法则将RGB三值同等对待，如[Hoppe96]。在本文中我们采用第二种方法。在面片合并过程中同时考虑RGB三色光能的最大相对变化，只有在三色的光能的最大相对变化在用户定义误差范围内，面片合并操作才能实施；否则边界面片不能为超面合并。而辐射度最大相对变化值队列则以RGB三色光能中最大的最大相对变化值作为队列位值进行由小到大的排列。

4.5.2 超面边界的简化

通过上节的超面生成算法，我们将原模型简化为一些相对变化在用户定义误差范围内的区域，并得到相应区域由原模型顶点、原模型边组成的平面多边形—超面。两个超面共享一个或者多个顶点，这些顶点有的不仅位于一条直线上，而且在用户定义的视觉分辨能力内其色彩值呈线性或近似线性变化。因而有必要简化所得到的超面边界

假设超面SuperSM有边界顶点集V={v1, v2, v3, ...vn.}，它们按顺序逆时针组成超面SuperSM的边界边。超面SuperSM’为其邻接多边形中的一个，顶点集V’=(vj,, vj+1, vj+2, …, vj+r)是这两个多边形所共有边界顶点，vj0vj0+1组成它们的公共边界边(j0=j, .., j+r-1)。我们采用递归分割法实现超面边界的简化。算法首先以线段vjvj+r近似表示超面SuperSM与SuperSM’的边界,如果中间顶点 vj+1, vj+2, …, vj+r-1的RGB值与经两端点的RGB值线性插值后得到的相应点的RGB值之差小于用户定义范围且各中间顶点到线段vjvj+r的距离小于用户定义误差d；否则，以这些中间顶点中与端点RGB值插值相差最大的顶点或距离线段vjvj+r最大的点vj1分割边vjvj+r得到边vjvj1和vj1vj+r。对这两条边我们重复以

上操作直至介于各边的中间顶点与边端点的RGB值插值的差在用户定义误差范围近似为一条直线或者不再存在中间顶点。

在本算法中由于采用的试验光照网格模型都是均匀网格模型，因而在算法中仅考虑各顶点的色彩因素，即仅以各顶点的颜色值作为边界简化的条件，而不考虑几何距离因素。

4.5.3 三角化过程

从上述面片合并的过程描述可知，所生成的超面区域将是原模型中能量相对变化在用户定义误差范围内的所有面片区域，有可能为多连通域。因而所生成的超面有可能是带内环的多边形。为实现带内环的多边形的三角剖分，我们首先通过内环与外环之间的连通线将多连通域转化为广义的凹多边形，然后利用以平均形态比加权的局部优化三角化方法实现超面的三角剖分，以较少的三角面逼近原模型。

4.5.3.1 多连通域转化为单连通域

多连通域是其内部具有孔洞的域。通过连接外环的一个边界点与内环的一个边界点生成连通线我们将多连通域划分为广义的凹多边形(见图一)。连通线是对一个个内环依次生成的。为避免产生与环相交的连通线必须首先对环排序。在这里我们将内环P记为InP，外环P记为OutP。因为生成的超面多边形是一平面多边形，因而我们这里假设该超面位于XY平面上。

图一

我们对平面上的点定义一种如下的顺序：如果y>v，或y=v且x>u，则称(x, y) > (u, v)。按以上顺序定义，我们记环P的最大顶点为TOP(P)。

为保证所生成的凹多边形具有良好的形状，同时保证所生成的连通线除端点外不与其它环相交，我们定义函数D(l, v)，l为一线段，v是一个点。如从v到l的垂线的垂足在线段内，则D(l, v)的值为v到l的距离；否则，D(l, v)的值为点v到l的两个端点的距离的较小值。

算法首先将所有内环按其y坐标值最大的点从大到小定义排序。然后依次取序列中

的内环InnP。为生成外环OutP与内环InnP的连通线，算法首先在外环中寻找一条最佳边l，然后从边l上寻找最佳端点与TOP(InnP)相连产生一条连通线，并将该内环并入外环。逐个处理内环，最后将多连通域转化为单连通域。

寻找最佳边l时，并不是OutP的所有边都可作为候选边，只有那些至少有一个端点的y坐标值大于TOP(InnP)的y坐标值的边才可作为候选边。从这些候选边中选择一条边l，使得D(l, TOP(InnP))的值最小。然后在此边的端点中寻找一个最佳端点，使得这个端点到TOP(InnP)的距离最小。连接此端点与TOP(InnP)即为外环OutP与内环InnP的连通线。

4.5.3.2 加权的局部优化三角化方法

平面多边形的三角剖分即将简单多边形分解为一系列不相重叠的三角形，同时不产生新的顶点。多边形三角剖分的实质是在原多边形的顶点间连线，使得这些连线完全位于原多边形的内部，连线间互不相交，同时，将原多边形分割为一定数目的三角形。这类算法已提出了很多[Kong90][Tarjan88][Chazelle90]。其中，有概念上最简单的切耳算法[Kong90]，也是迄今为止理论上时间复杂度最低的算法。本文以Kong切耳算法为基础，结合Delaunay三角剖分中形态质量的度量方法，实现自己设计的平均形态比局部优化三角化方法。我们首先介绍Kong切耳算法。

4.5.3.2.1 Kong切耳算法

假设多边形P表示为P={v0, v1, ..., vn}。其中vi称为P的顶点，线段(vi, vi+1)称为P的边(0in-1)。多边形三角剖分的实质是在原多边形P的顶点间连线，使得这些连线完全位于原多边形的内部，连线间互不相交，同时，将原多边形P分割为一定数目的三角形。完全位于内部的不相邻顶点vi、vj1间的连线在计算几何中称为引线di, ,j。P上相邻三点vi-1, vi和 vi+1，如果(vi-1, vi+1)是P的一条引线di-1, i+1，则称vi,为耳朵点，即三角形vi-1,vi vi+1中不包含的其它顶点。显然，耳朵点属于凸点。下面著名的“双耳定理”是1975年由Meister证明的，它成为简单多边形问题研究的理论基础。

双耳定理：除了三角形外，任何一个简单多边形至少包含两个不相重叠的耳朵点如何构造引线成为多边形三角剖分的关键步骤。根据双耳定理，Kong构造了切耳算法以快速求取引线。其核心思想即为寻找耳朵点并将其切去。

该算法在循环切耳时，使用了Graham扫描法：只对顶点坐标扫描一次。在扫描的每一步，要么从表中删除一个顶点，要么扫描下一个顶点。由于多边形的顶点数为n，

删除和向前扫描的次数均不超过n次。因此，切耳算法的时间复杂度是线性的，即O(n)。

Kong切耳算法使用双向链表来组织多边形的顶点。同时，算法将凹点单独表示出来，为集合R。而判定一个顶点是否是耳朵点时，证明下面的一个定理：

定理1：如果顶点vi不是耳朵点，则三角形vi-1vi vi+1中包含了P的凹点。根据定理，可以构造函数Ear如下： boolean Ear(P, R, vi) { }

4.5.3.2.1 加权的局部优化三角化方法

Kong算法简单易行，算法描述简单，使用的双向链表这一数据结构也较简单。但该算法的剖分结果与扫描起点的选择有关。也就是说，扫描起点的不同算法所得到的三角剖分也不同。同时，它还很难保证剖分所获得的三角形的形态质量，容易出现狭长的三角形。

Menzel和Monien首先提出了加权剖分思想[]Menzel92]。实际上，Delaunay三角剖分就是加权剖分的一个特殊实例。使用加权函数对多边形进行分析，然后根据权值的优劣进行剖分，控制剖分获得的三角形的形态质量。

本算法借鉴Delaunay三角剖分的准则，构造顶点的权函数，以简单的Kong切耳算法为基础，寻找耳朵点并切除之，最终获取形态质量优化的多边形三角剖分结果。算法的核心思想是：将多边形的P的顶点vi按权值从大到小排序，以Kong切耳算法为基础，根据的权值进行加权扫描，得到P的三角剖分。

在平面多边形的三角剖分中，所获得的三角形的形态质量是各种三角化方法的一个重要衡量指标。在这方面，Delaunay三角剖分是最优的。但它只适合于平面点集的最优剖分。为实现三角外接圆内不包含其它点，Delaunay三角剖分允许在剖分过程中引入新的点，从这一点上看，它是不适合与模型简化中的多边形剖分的。所谓三角形平均形态比即三角形的内切圆半径与外切圆半径之比。平均形态比最大准则是有限元网格划分中

if R=NIL then return(True) else if vi是凸点 then

if vi-1vi vi+1不包含中的顶点then

return(TRUE) else rturn(FALSE)

else return(FALSE)

网格划分质量的重要评判标准[Min94]。它与Circle准则以及最小角最大准则等价，都产生Delaunay三角划分。在这里我们借用此概念定义多边形顶点的权值，控制多边形剖分所获得的三角形形态质量。

算法使用环形链表组织多边形顶点，并建立多边形的所有凹点的集合。为控制多边形剖分所获得的三角形形态质量，算法从大到小顺序建立各顶点的权值队列。各顶点权值定义如下：若vj0为凹点，则点vj0的权值为0；否则，从循环链表中顺序取出顶点vj0及其相邻顶点vj0-1、vj0+1，计算三角形vj0-1vj0vj0+1的平均形态比Ratio(vj0-1vj0vj0+1)作为该点的权值。Ratio(vj0-1vj0vj0+1)的计算如下：

Ratio(vj0-1vj0vj0+1) = cos(vj0-1vj0vj0+1) + cos(vj0vj0+1vj0-1) + cos(vj0+11vj0-1vj0) -1 在多边形的三角剖分过程中，每次取队列的头结点的相应顶点vj进行三角剖分操作。如果该顶点及其相邻顶点vj-1、vj+1组成的三角形vj-1vjvj+1不包含多边形中的其他顶点，则剖分成功。从链表和队列中删除顶点vj的相应结点，并重新计算相邻顶点vj-1与vj+1的凸凹性及权值，以重新计算的各顶点权值重排权值队列，重复以上操作直至权值队列为空。否则，以权值队列中的下一个结点的相应顶点作剖分操作。

我们以上算法实现对如图二中的多边形(a)进行加权剖分，获得了较好的剖分结果(见图二(b))。

(a)图二 (b)

4.6 实验结果

通过以上算法我们得到在用户定义误差内的由原模型顶点的子集组成的原辐射度全局光照网格模型的简化模型。我们用两个模型room模型和office模型验证我们的算法(见彩图)，并给出相应简化模型绘制的效果图。

彩图4-2、4-3、4-4是当取常值2，分别取0.08、0.1、0.8时，算法对room模型

简化的带网格和不带网格的效果图。彩图4-5、4-6是当取常值0.8，分别取10、50时，算法对room模型简化的带网格和不带网格的效果图。从中可以看出，随着用户误差限制的放宽，辐射度光照网格模型的简化程度亦随之增大，而整个场景的光能分布亦趋于单一，位于相对变化在用户误差范围内的软阴区的面片不断为周围面片所合并。我们对office模型实施了同样的实验。这里仅给出=0.06，=1与=0.8，=4的最后效果图（见彩图4-8、4-9）。

根据以上两个模型的试验数据，我们绘制了算法在取常值2时，算法的简化程度随变化的性态曲线图，以及算法在取常值0.8时，算法的简化程度随变化的性态曲线图(见图二、三、四、五)。

4.7 小结

本算法根据人眼的视觉特点和辐射度计算特点，以最大相对变化值为准则，以面片合并简化操作将最大相对变化在用户定义范围内的面片合并起来，实现辐射度全局光照网格模型的第一步简化，并以原模型顶点的RGB值的变化进一步加大辐射度网格模型的简化，建立起整个环境具有辐射度全局光照效果的多细节层次模型。本算法不仅有效地简化了辐射度全局光照网格模型，而且能较好地保持原光照网格模型的特征。算法随着用户误差限制的放宽，模型的简化程度亦随之增大。试验表明这个算法是令人满意的。

彩图4-1模型room彩图4-2 =0.08, =2彩图4-3 =0.1, =2彩图4-4 =0.8, =2彩图4-5 =0.8, =10彩图4-6 =0.8, =50

彩图4-7 原模型office彩图4-8 = 0.06, =1彩图4-9 = 0.8, =4

第五章结束语

自八十年代图形硬件作为当时新出现的计算机机种──计算机图形工作站的硬件系统的必备功能部件后，图形工作站的图形处理能力与显示能力已得到很大的提高。然而随着计算机图形学领域的不断发展，特别是图形学派生领域虚拟现实的提出，今天的计算机图形工作站的图形处理能力已远远不能满足实际的需求。本论文围绕层次细节模型技术这一有效的图形生成加速方法展开了有益的探索，研究各种LoD模型生成方法及实时绘制技术。

一步加大辐射度网格模型的简化，建立起整个环境具有辐射度全局光照效果的多细节层次模型。本算法不仅有效地简化了辐射度全局光照网格模型，而且能较好地保持原光照网格模型的特征。

本论文的研究内容涉及LoD模型技术的多个相关方面：LoD模型的选择尺度，LoD模型的自动生成，LoD模型的平滑过渡方法。并就各种LoD模型生成方法及实时绘制技术提出新的算法。

作为一种新的技术生长点，虚拟现实技术受到国内外学者的广泛关注。可以预见，在不久的将来VR将提供与计算机通讯的最自然的手段，成为人类认识世界和改造世界更强有力的武器。

参考文献

[Algorri96]

Maria-Elena Algorri and Francis Schmitt, “Mesh Simplification”, Eurographics’96, 15(3), 1996, pp77-86

[Astheimer93] Peter Astheimer, “Virtual Design:A Generic V.R. System for

[Astheimer94] [Blake87]

[Blanchard90]

[Bryson93] [Campbell90] [Certain96]

[Chazelle90]

[Chen86] [Chen95] [Clark76]

[Cohen86]

[Cohen92]

Industrial Application”, Computer&Graphics, Vol.17, No.6, 1993, pp671-678. Astheimer, P., Poche M., “Level-of-Detail Generation and Its Application in Virtual Reality”. Proc. of VRST’94, pp299-309.

Blake, E.H., \"A Metric for Computing Adaptive Detail in Animated Scenes Using Object-Oriented Programming\Eurographics'87, G.Marechal(Ed.), Elsevier Science, B.V.(North-Holland), 1987

Chuck Blanchard, \"Reality Built for Two: A Virtual Reality Tool\SIGGRAPH 1990 Symposium on Interactive 3D Graphics, March 1990, pp35-36.

Steve Bryson, \"Virtual Reality in Scientific Visualization\& Graphics, Vol.17, No.6, 1993.

Campbell, A., Fussell, D. S., “Adaptive Mesh Generation for Global Diffuse Illumination”, SIGGRAPHICS’90, pp155-164

Andrew Certain, Jovan Popovic, Tony DeRose, Tom Duchamp, David Salesin, Werner Stuezle, “Interactive Multiresolution Surface Viewing”, Pro. of SIGGRAPH’96, pp91-98

Chazelle, b., “Triangulating a Simple Polygon in linear Time”, Proc. 31st Annual Symposium on Foundation of Computer Science, IEEE Press, New York, 1990, pp220-230

Chen, Z. T., and Tobler,W. R., “Quadtree Representation of Digital Terrain”. In Proceedings of Autocarto(London), 1986, pp475-484

Chen,S.E. “QuickTime VR --- An Image-based Approach to Virtual Environment Navigation”, Proc. SIGGRAPH'95, 15-38.

Clark,James H., \"Hierachical Geometric Models for Visible Surface Algorithm\Communications of the ACM, Vol.19, No.10, 1976, pp547-554.

Cohen, M., Greenberg, D., P., Immel, D. S., and Brock, P., J., “An efficient Radiosity Approach for Realistic Image Synthesis”, IEEE Computer Graphics and Application, vol.6, No.3, 1986, pp26-35

M.F.Cohen, “Interactive Spacetime Control for Animation”, In proc. of SIGGRPAH’92, pp293-302

[Cohen96]

Janathen Cohen, Amitabh Varshney, Diresh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, William Wright, “Simplification Envelopes”, Proc. of SIGGRAPH’96, pp119-128

Carolina Cruz-Neira, \"Virtual Reality Overview\SIGGRAPH'93, Couse Notes 23.

[Cruz-Neira93]

[Cruz-Neira93a] Carolina Cruz-Neira et al., \"Scientist in Wonderland: A Report on

[Cruz-Neira93b] [Dehaemer91]

[Dyn90]

[Eck95]

[Falby93]

[Fergusen90] [Finkelstein96] [Floriani84]

[Floriani92]

[Floriani95]

[Fuches80]

Visualization Application in CAVE Virtual Reality Environment\IEEE Symposium on : Research Frontiers in Virtual Reality, 1993, pp59-66. Carolina Cruz-Neira, Daniel J. Sandin, Thomas A. Defanti,

\"Surround-Screen Projection-Based Virtual Reality: the Design and Implementation of the CAVE\Computer Graphics Proceeding Annual Conference Series, 1993, pp135-142. M.J.Dehaemer, J R. And M. J. Zyda, \"Simplification of Object Rendered by Polygonal Approximations\Computer Graphics, 15(2), 1991, pp175-184.

Dyn, N., Levin, D., and Gregory, J. A., “A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control”, ACM Trans. on Graphics, 9(2), April 1990, pp160-169

Matthias Eck, Tony DeRose , Tom Duchamp, Hugues Hoppe, Michael Lounsbery, Werner Stuetzle, \"Multiresolution Analysis of Arbitrary Meshes\

John S. Falby, Michael J. Zyda, Daud R. Pratt and Randy L. Mackey, “NPSNET:Hierarchical Data Structures for Real-Time Three-Dimensional Visual Simulation”, Computers & Graphics 17(1), pp65-69, 1993

R.L.Fergusen, \"Continuous Terrain Level of Detail for Visual Simulation\Proceeding of the 1990 IMAGE V Conference, June 1990, pp145-151. A. Finkelstein, C.E.Jacobs, and D.H.Salsin, “Multiresolution Video”, In proc. of SIGGRAPH’96

De Floriani, L., Falcidieno, B., Pienovi, C., and Nagy, G., “A Hierarchical Data Structure for Surface Approximation”, Computers & Graphics, 8(2), 1984, pp475-484

De Floriani, L., and Puppo, E., “A Hierarchical Triangle-Based Model for Terrain Description”, In Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, A.U.Frank, I. Campari, and U.Formentini, Eds. Lecture Notes in Computer Science, 639, Springer-Verlag, New York, 1992, pp236-251

L. De. Floriani and E. Puppo, “Hierarchical Triangulation for Multiresolution Surface Description”, ACM Transactions On Graphics, 14(4), October 1995, pp362-410

H.Fuches, Z.Kedem, and B.Naylor, \"On Visible Surface Generation by A Priori Tree Structure\Computer Graphics(Proc. SIGGRAPH'80),

14(3),July 1980, pp124-133 .

[Fuchs89]

Henry Fuchs, \"Pixel-Plane5:A Heterogeneous Multiprocessor Graphics System Using Processor-Enhanced Memoried\SIGGRAPH'89, Vol.23, No.3, pp79-81.

[Funkerhouser93] Thomas A. Funkhouser and Carlo H. Sequin, \"Adaptive Display Algorithm

for Interactive Frame Rates During Visualization of Complex Virtual Environments\[Funkhouser92] Funkhouser, Thomas A., Sequin, Carlo H., and Teller, Seth J.,

“Management of Large Amounts Data in Interactive building Walkthroughs”, ACM SIGGRAPH Special Issue on 1992 Symposium on Interactive 3D Graphics, pp11-20 [Gemot96]

Gemot Schaufler and Wolfgang Sturzlinger, \"A Three Dimensional Image Cache for Virtual Reality\

[Goldfeather86] Goldfeather, Jack and Henry Fuchs, “Quadratic Surface Rendering

on a Logic-Enhanced Frame-buffer Memory Systm”, IEEE CG &A, Vol.6, No. 1, 1986, pp48-59. [Green91]

Mark Green, \"Minimal Reality(MR):A Toolkit for Virtual Applications, MR v1.0\ Programmer's Mannual, University of Alberta, September 1991.

Greene, N. Creating Raster Ominmax Images from Multiple Perspective Views Using the Elliptical Weighted Average Filter. IEEE Computer Graphics and Applications, 6(6):21-27, June 1986.

Greene, N. Environment Mapping and Other Applications of World Projections. IEEE Computer Graphics and Applications, 6(11):21-29. Nov.1986.

Ned Greene, \"Hierarchical Z-Buffer Visibility\Computer Graphics Proceedings, 1993, pp231-238.

Turk Greg, \"Re-tiling Polygonal Surface\1992, pp55-64.

M. H. Gross, R. Gatti, O. Staadt, “Fast Multiresolution Surface Meshing”, IEEE Proc. of Visualization’95, pp135-142

Markus H.Gross, Roger Gatti, “Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structure”, IEEE Transactions on Visualization and Computer Graphics, 2(2), June 1996, pp130-143

[Greene86a]

[Greene86b]

[Greene93] [Greg92] [Gross95] [Gross96]

[Grossweiler93] Rich Grossweiler, Chris Long, Shuichi Koga, Randy Pausch, \"DIVER: A

Distributed Virtual Environment Research Platform\Research Frontiers in Virtual Reality, 1993, p10-15. [Haeberli90]

Paul Haeberli, Kurt Akeley, \"The Accumulation Buffer: Hardware Support for High-Quality Rendering\

[Hamann94]

Bernd Hamann, “A Data Reduction Scheme for Triangulate Surfaces”, Computer Aided Geometric Design, 11, 1994, pp197-214

[Hanranhan91] Pat Hanranhan, “A Rapid Hierachical Radiosity Algorithm”,

[Helman95]

[Hinker93] [Hoppe93] [Hoppe96] [Hughes96] [Iseler96]

[Johnson94]

[Jones95] [Kalvin96]

[Kong94]

[Li97]

[Lindstrom96]

[Liu96] [Liu97]

Computer Graphics, 25(4), July 1991, pp197-206. James Helman, “Graphics Techniques for Walkthrough Application”, SIGGRSPH’95, Course Notes 32 on Interactive Walkthrough of Large Geometric Databases

Paul Hinker, and Charles Hansen, “Geometric Optimization”, IEE Proc. of Visualization’93, pp189-195

Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle,“Mesh Optimization”, Proc. of SIGGRAPH’93, pp19-26 Hugues Hoppe, \" Progressive Mesh\Merlin Hughes, Anselmo A. Lastra, Edward Saxe, \"Simplification of Global-illumination Mesh\

Veysi Isler, Rynson W.H.Lau, Mark Green, \"Real-time Multi-resolution Modeling for Complex Virtual Environments\VRST'96, July 1-4, 1996, pp11-19

Andrew Johnson and Farshad Forouhi, \"SANBOX: Interface to Scientific Data Based on Experimentation\Fifth Eurographics Workshop on Visualization in Scientific Computing, May30-June 1, 1994.

Michael Jones, \"Lesson Learned from Visual Simulation\Couse Notes 6 on Designing Real-Time 3D Graphics for Entertainment Alan D.Kalvin, “Supersurface:Polygonal Mesh Simplification with Bounded Error”, IEEE Computer Graphics and Applications, May 1996, pp64-77.

Kong, X., Everrett, H. And Toussaint G., “The Graham Scan Triangulates Simple Polygon”, Pattern Recognizition Letters 11, Nov. 1990, pp713-716

Jie Li, Zesheng Tang and Honghui Guo, “Real-time, Continuous Level of Detail Rendering for Complex Models”, Proceeding of the Fifth International Conference on CAD/CG’97, Dec. 2-5, 1997, ShenZhen, China:101-106

Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, Gregory A. Turner, “Real-Time, Continuous Level of Detail Rendering of Height Fields”, Proc. of SIGGRAPH’96, pp109-118 WenWei Liu and Jintao Li, “Image-Space Based Criteria for Level-of-Detail Selection”, 软件学报英文版（已录用)

刘学慧, 吴恩华, \"虚拟现实的图形生成技术\中国图象图形学报, 2(4), 1997, pp 205-212

[Lounsbery 96] Michael Lounsbery, T.DeRose and J.Warrenn, “Multiresolution

Surfaces of Arbitrary Topological Type”, ACM Transaction on Graphics, 1996 [Lounsbery94] Michael Lounsbery, “Multiresolution Analysis for Surface of

[Ma97]

[McCarty94] [Menzel92]

[Min94] [Molnar92] [Pan95] [Pan96] [Polis92]

[Pottmann90]

[Regan94] [Rossignac93]

[Schachter83] [Schaufler96]

Arbitrary Topological Type”, Ph.D dissertation, Univ. Of Washington, 1994 Xiaohu Ma, Zhigeng Pan anf Jiiaoying Shi, “Mesh Simplification Method Based on Triangle Removal Criterion”, Proceeding of the Fifth International Conference on CAD/CG’97, Dec. 2-5, 1997, ShenZhen, China: 131-134

W.Deen McCarty, et al., \"A Vitual Cockpit for A Distributed Interactive Simulation\

Menzel, K. and Monien, B., “Weighted Parallel Triangulation of Simple Polygon”, Lecture Notes in Computer Science, 15th International Workshop WG, Beilin Springer-Verleg, 1992, pp302-315

闵卫东，唐泽圣，“二维Delaunays三角划分形态比最大性质”, 计算机学报, 1994(增刊), vol.17，pp20-25

Steven Molnar, \"PixelFlow: High-Speed Rendering Using Image Composition\ol.26, No.2, pp237-240.

Pan, Zhigeng, Zhang, Mingmin et al., “Time-critical Computing in Virtual Environment”, In proc. of CAD/CG’95, Wuhan, Oct. 1995, pp1078-1083 潘志庚，马小虎，石教英，“虚拟环境中多细节层次模型自动生成算法”，软件学报，Vol 7, No.9, 1996. pp532-536 Michael F. Polis and David M. Mckeown, Jr., “Interactive TIN Generation from Digital Elevation Models”, Proc. of IEEE Conf. on CVPR, 1992, pp787-790

Pottmann, H., and Eck，M., “Modified Multiquadric Methods for Scattered Data Interpolation over a Sphere”, Computer Aided Geom. Des., 7, 1990, pp313-321

Matthew Regan, Ronald Pose, \"Priority Rendering with a Virtual Reality Address Recalculation Pipeline\

Rossignac, J., and Borrel,P., “Multi-resolution 3D Approximations for Rendering Complex Scenes”, IFIP TC 5. WG 5.10 II Conference on Geometric Modeling in Computer Graphics, Genova, Italy, 1993: pp455-465

Schachter, Bruce J.(Ed.), Computer Image Generation, John Wiley and Sons, New York, NY, 1983

Gernot Schaufler, Wolfgang Sturzlinger, “A Three Dimensional Image Cache for Virtual Reality”, In Proc. of Eurographics’96, pp227-235

[Schmitt86]

[Schroder94] [Schroeder92] [Shade96]

[Shi94] [Smits92] [Soucy96]

[Tarjan]

[Taylor93]

[Teller91] [Thorpe87]

[Turk92] [Whitted80] [Wu94] [Wu95] [Zhou96]

Francis J.M.Schmitt, Brian A. Barsky, Wen-Hui Du, \"An Adaptive Subdivision Method for Surface-fitting from sampled Data\SIGGRAPH’86, 20(4), 1986, pp179-188.

Florian Schroder and Patrick RoBBach, \"Managing the Complexity of Digital Terrain Models\William J. Schroeder, Jonathan A. Zarge, William E. Lorensen, \"Decimation of Triangle Mesh\Jonathan Shade, Dani Lischinski, David H. Salesin, Tony Derose, john Snyder, \"Hierachical Image Caching for Accelerated Walkthroughs of Complex Environments\

石教英, \"虚拟环境（VE）技术及其应用\全国第一届虚拟环境研讨会论文集，杭州，1994

Brain E. Smits, “An Importance-Driven Radiosity Algorithm”, Computer Graphics , 26(2), July 1992, pp273-282.

Marc Soucy and Denis Laurendveau, “Multiresolution Surface Modeling Based on Hierarchical Triangulation”, Computer Vision and Image Understanding, 63(1), January 1996, pp1-14

Tarjan, R., VanWyk C, “An O(nloglogn)-time Algorithm for Triangulating a Simple Polygon”, SIAMI, Comput., 1988, pp143-178

Russell M. Taylor II et al., \"The Nanomanipulator: A Virtual-Reality Interface for a Scanning Tunneling Microscope\Proceeding of SIGGRAPH'93, pp127-13.

Seth J. Teller, \"Visibility Preprocessing for Interactive Walkthroughs\Computer Graphics, Vol.25, No. 4, July 1991.

J.A.Thorpe, \"The New Technology of Large Scale Simulator Networking: Implication for Mastering the Art of Warfighting\Pro. Ninth Interservice/Industry Training System conf., Defence Technical Information Center, Nov. 1987, pp492-501.

Greg Turk, “Re-tiling Polygonal Surfaces”, Proc. of SIGGRAPH’92, pp55-64

Whitted, T., “An improved Illumination Model for Shaded Display”, Comm. ACM, vol.23, No.3, 1980

吴恩华，“VR中三维图形绘制及其加速技术”，全国第一届虚拟环境研讨会论文集，杭州，1994

吴恩华， “论图形生成和虚拟现实”，中国科学院软件研究所学术报告集，vol.2, 1995年四月。

周晓云，刘慎权，“基于特征角准则的多面体模型简化方法”, 计算机学

报（增刊），1996，19(9): 217-223

致谢

本论文是在导师吴恩华研究员精心指导和帮助下完成的。光阴似箭，时光飞逝，转眼学生已受教于师门三年又半。这期间，学生所取得的每一点进步无不包含着老师的心血，这一切学生当永志不忘。每当我遇到挫折，是导师对事业的执着追求和敬业精神深深地鼓舞着我。吴老师严谨求实、雅儒温厚、谦逊和蔼，令学生景仰；老师深厚的学术功底、敏锐的学术洞察力、严谨的治学作风和精亦求精的工作精神，给学生留下了深刻的印象，并将永远激励和鞭策学生在未来的工作和科研中发奋努力，以不负导师的教诲和培养。

感谢王文成、任敬、蔡勇、周定红、李洪举、冯金辉、张晓鹏、陈彦云、严涛、刘列明、孙庆杰各师兄弟给予我的诸多帮助和关心。这是一个非常友好而又具有活力的集体。工作时的认真讨论和闲暇时的欢歌笑语，使得学习生涯充满乐趣。三年半中，收获的不仅仅是学业，而且还有纯真的友谊和美好的回忆。

感谢中科院软件所计算机科学实验室为本文工作提供的优越工作环境。

最后特别感谢深爱我的父母。“慈母手中线，游子身上衣”。他们无尽的关怀、全心全意的支持和鼓励是我在漫漫学海中不断进取的动力。衷心感谢，感谢他们多年的养育之恩。

衷心感谢所有关心和帮助过我的各位老师和朋友！

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

首页

旅游热点

线路攻略

景点大全

国内游

境外游

美食特产

虚拟现实中三维复杂几何形体的层次细节模型的研究