（计算机应用技术专业论文）数据高度场的实时生成与渲染研究.pdf

哈尔滨工程大学硕士学位论文 捅要 参数曲线曲面随着计算机图形应用的不断普及已广泛地应用到各领域。 在一定的数字化描述形式下，可以使用参数曲线曲面进行3 d 建模，从而达到 物体的虚拟重构或可视化映射。如何解决真实感、观测精度与生成速度的矛 盾成为自由曲面广泛应用的重要课题。本文主要解决的问题是数据高度场如 何应用参数曲面进行图形显示，同时以实时显示作为表现要求。 本文提出了一种基于中心差分技术进行高度场镶嵌的系统方法，并结合 视点相关技术实现了多分辨率模型的生成，以适应实时应用的需要。而且， 对高度场数据使用了适于实时显示的高效四叉树存储方式，并给出了裂缝消 除、视锥体裁剪以及提高图形真实感和生成效率的适用方法。此外，还通过 数据的预处理使本文的方法也能适用于真实采样数据的图形生成。 本文的方法实现了综合运用相关技术达到对数据高度场进行实时图形显 示的目的。与同类方法相比，本方法灵活性高，能够适于多种应用。本方法 应用于某声振测试分析仪显示系统，其视觉质量好并且执行效率高。 关键词；科学可视化；虚拟现实：高度场：自由曲面；细节层次 哈尔滨工程大学硕士学位论文 a b s t r a c t p a r a m e t r i cc u r v ea n dc u r v e ds u r f a c eb e c o m em o r ea n dm o r ei m p o r t a n ti n c o m p u t e rg r a p h i c sa p p l i c a t i o n ，a n dt h e yc a nb eu s e di n3 dm o d e l i n g h o wt om a k e t h eg r a p h i c sl o o kl i k e r e a lo b j e c t sw i t hc e r t a i np r e c i s i o n , y e th a v eah i g hr u n n i n g s p e e di sah i g h l i g h t e dp r o b l e mi nr e c e n ty e a r s ，t h i sp a p e rd e v o t e st op r e s e n ta m e t h o dw i t ht h e s ec h a r a c t e r si nh e i g h tf i e l d sa p p p l i c a t i o n i n t h i s p a p e r , as y s t e m i cm e t h o du s i n gc e n t r a ld i f f e r e n c et e c h n o l o g yi s p r e s e n t e dt ot e s s e l l a t eh e i g h tf i e l d sa n dg e n n e r a t ev i e w - d e p e n d e n tm u l t i r e s o l u d o n m o d e l s r e l a t e da s p e c t ss u c ha sq u a d t r e eh e i g h tf i e l d ss t o r a g e ，c r a c kf i x i n ga n d m e t h o d si nf a v o ro fi m p r o v i n ge f f i e n c ya n dr e a l i t ya r ea l s od i s c u s s e d i na d d i t i o n t o i t ，t h r o u g hd a t ap r e - p r o c e s s i n g , t h i sm e t h o da l s oa d a p t st o d a t as a m p l e di n p r a c t i c em o d e l i n g c o m p a r i n gt op r e v i o u sm e t h o d s ，t h em e t h o dp r e s e n t e di n t h i sp a p e r p r o v i d e sg o o df l e x i b i l i t yi nv a r i o u sa p p l i c a t i o n s i tw o r k sw e l li nr e a l t i m ed i s p l a y a p p l i c a t i o nw h i l eh a sg o o dv i s u a lq u a l i t y k e y w o r d s ：s c i e n t i f i cv i s u a l i z a t i o n ；v i r t u a lr e a l i t y ；h e i g h tf i e l d ；f r e e f o r ms u r f a c e ； l e v e lo f d e t a i 】 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：年月日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题的目的和意义 1 1 1 问题概述 随着计算机应用的不断普及，参数曲线曲面已广泛地应用到许多工业领 域。例如：飞机外形设计汽车外形设计船体的数学放样等等。这些曲线 曲面的应用、实质上是曲线曲面的计算机辅助设计。但除了这些应用，近年 的一些实时或半实时的应用如虚拟现实、科学计算可视化等应用愈来愈 广，并在一些领域快速普及。这其中也包括计算机辅助设计的逆问题 1 ，即 从真实事物推出其数字化的描述，这一过程将其称为采样扫描。更为重要的 是，在一定的数字化描述形式下，使用参数曲线曲面进行3 d 建模，从而达到 物体的虚拟重构或可视化映射。虽然可能还有人对还原各种各样的3 d 物体的 属性感兴趣，比如颜色、材料的物理特性等，但如何解决真实感、观测精度 与生成速度的矛盾成为自由曲面普及应用的重要课题。 在实时图形应用中，各种视点无关l o d 模型( 见1 1 4 节) 适于多种应 用，但在大规模模型的应用条件下，例如可能分布于观察者周围的环境的渲 染，其使用就会出现问题： ( 1 ) 模型的许多面处于视锥体之外，因而对最终显示的图像没有贡献， 而渲染管线提供的通用裁剪操作花费较大。 ( 2 ) 在视锥体之内，模型的某些区域可能比其他部分在更大程度上接近 观察者。在整体模型的意义上，视点无关l o d 模型无法提供合适的细节层次。 ( 3 ) 在采样数据给定的前提下，如何使模型与观察者间的距离不断缩小 的情况下，依然保持平滑的观感及较高的视觉质量。 所以，本篇论文主要解决的问题是高度场如何应用参数曲面进行图形显 哈尔滨工程大学硕士学位论文 示，同时以实时显示作为表现要求。因此，随着自由曲面的表现方法越来越 多地渗入了此类应用，其生成方法及速度优化问题的研究具有非常现实的意 义。 1 1 2 虚拟现实与可视化 虚拟现实( v i r t u a lr e a l i t y ) 技术在近年成为信息领域科技工作者和产 业界的研究、开发和应用的热点，发展得也很快，它改变了人与计算机之间 传统的交互方式，具有广阔的应用前景。所谓虚拟现实，就是将人与计算机 系统集成到一个环境中，由计算机生成交互式的三维视景仿真，通过视、听、 触觉作用到人，使人产生身临其境的感觉。 虚拟现实技术的经典定义包含以下三个基本特征： ( 1 ) 计算机生成看起来像真的、听起来像真的、触摸起来像真的虚拟世 界( 又称模型世界) ，也就是说计算机生成的模型世界将向介入者人， 提供视觉、听觉、触觉等多种感官刺激。 ( 2 ) 计算机生成的虚拟世界应给人一种身临其境的沉浸感。 ( 3 ) 人能以自然方式与虚拟世界中的对象进行交互操作，即不使用键盘 鼠标等常规输入设备，而强调使用手势( 数据手套) 、体势( 数据衣服) 和 自然语言等自然方式的交互操作。 虚拟现实是计算机生成的给人多种感官刺激的虚拟世界( 环境) ，是一 种高级的人机交互系统。和其他的计算机系统相比，垤系统可提供实时交互 性操作、三维视觉空间和多通道( 目前主要限于视觉和听觉，但触觉和嗅觉方 面的研究也正在不断取得进展) 的人机界面。作为一种新型的人机接口，v r 不仅可使参与者沉浸于计算机所产生的虚拟世界，而且还提供用户与虚拟世 界之间的直接通讯手段。利用v r 系统，可以对真实世界进行动态模拟，产生 的动态环境能对用户的姿势、语言命令等做出实时响应，也就是说计算机能 够跟踪用户的输入，并及时按照输入修改模拟获得的虚拟环境，使用户和模 拟环境之间建立起一种实时交互性关系，进而使用户产生一种身临其境的感 2 哈尔滨工程大学硕士学位论文 觉。由此可见，v r 技术将会改变人类获取信息的方式，提高人机之间的和谐 程度。 科学计算可视化技术( v i s c v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ，) 实 现对数据进行图形映射表示，以获得对数据的理解与洞察。它为抽象的观测 数据赋予了图形化解释。通常， ( v i s u a l i z a t i o n ) ，根据不同的数据集， 科学计算可视化也简称为可视化 可视化的图形表现方式有多种，高度 场映射技术是其中应用广泛的一种方式。从过程上来看，可视化技术的发展 中的技术积累也成为了虚拟现实技术发展不可或缺的基础，因此，从技术方 法上来说，二者有诸多共通之处。 1 1 3 真实感图形的实时绘制 虚拟现实技术的最终目标是使用户置身于一个由计算机生成的虚拟环境 中，产生一种各种感觉达到身临其境的全方位感受。与传统真实感图形绘制 算法追求图形的真实感和高质量，而对每帧画面的绘制速度并没有严格的限 制的要求不同，虚拟现实系统要求的实时图形绘制技术必须在给定的时间内， 完成对场景的绘制。鉴于目前软、硬件的发展水平，往往通过损失图形质量 来快速绘制画面，这里图形质量的损失主要指图形真实感的降低和走样程度 的加重。例如，采用简单局部光照明模型和降低画面分辨率来加速绘制等等。 真实感图形的生成一般需经历场景造型、取景变换、视域裁剪、消除隐 藏面及可见面光亮度计算等步骤 2 。对其中的一些步骤的实现算法进行选择 和改进，是实现真实感图形的实时图形绘制的必要条件。 1 1 4 多细节层次模型 即便采用了视域裁剪及可见消隐等技术，有时视点所覆盖的场景仍很复 杂，为此细节层次( ( l e v e lo f d e t a i l ，简称l o d ) 模型方法应运而生。所谓l o d 模型方法，即为每个物体建立多个相似的模型，不同模型对物体的细节描述 3 哈尔滨工程大学硕士学位论文 不同，对物体细节的描述越精确，模型也越复杂，l o d 模型方法具有普适性。 应用范围极广。l o d 模型的自动生成和绘制技术己成为一个很有前途的研究 方向，受到了全世界范围内相关研究人员的重视。 场景的多细节层次模型( l o d ) 的存在基于以下现实：尽管可见性计算使 得不需绘制那些看不见的物体，然而还有一些在屏幕上占据不到一个像素的 物体，它们对场景的视觉贡献极小，注意到这些物体并非本身很小，只是视 点很远，造成投影很小。随视点的移动变化，投影大小也会相应改变。因此， 控制物体绘制的分辨率或层次细节很有必要。 如前所述，细节层次l o d ( l e v e lo f d e t a i l ) 是指对同一场景或场景中的物 体，使用具有不同细节的描述方法得到一组模型，供绘制时选择使用。从2 0 世纪9 0 年代开始，研究人员在这方面开展了大量的工作。一般采用离线处理 技术建立l o d 模型的情形较为普遍。近几年，出现了许多高效的l o d 模型 生成算法。这些算法技能简化复杂的地形数据、又能简化复杂的拓扑模型。 且简化结果既可以是视点依赖的，亦可以是视点无关的。 l o d 模型通常通过网格简化算法来生成。简化流程描述数据简化的过 程，一般分为删除简化( d e c i m a t i o n ) 和添加细化( r e f i n e m e n t ) 两大类。其中， 有一种算法称为自适应细分型算法，这种方法要求首先建立原始模型的最简 化形式，然后根据一定的规则通过细分把细节信息增加到简化模型中，从而 得到较细的l o d 表示( 如图1 1 所示) 。主要适用于均匀的网格( _ 立口高度场) 。 图1 1 高度场的自适应细分 4 哈尔滨工程大学硕士学位论文 为物体提供不同的l o d 描述是控制场景复杂度和加速图形绘制速度的一 个非常有效的方法 3 。l o d 模型的使用过程中，充分体现了人们对视觉效果 的要求，l o d 模型的应用是多方面的，例如，因应虚拟现实系统特别强调真实 感图形的实时生成的需求，l o d 模型在其中得到了广泛应用 4 ，很多虚拟 现实系统都把场景用多l o d 模型描述，有些虚拟现实开发工具也支持l o d 特征， 甚至虚拟现实造型语言v r m l 中也包括对l o d 描述的支撑。另外，交互式可视 化中也有大量应用，除了等值面抽取算法产生的大量由三角面片构成的三角 网格可应用l o d 技术交互观察外，在高度场映射的四边网格中也可利用相应的 l o d 技术。飞行模拟器、3 d 动画和交互式仿真中也应用了l o d 技术，例如，在 地形可视化应用中，地形网格中的面片数目也很大，经常使用多l o d 方法来描 述地形数据。l o d 技术的应用范围还包括c a d 和虚拟快速成型系统和网络图形 应用等。 1 2 国内外研究概况 在高度场的实时建模和渲染领域，近年随着计算机视觉、科学计算可视 化、扫描技术、计算机图形学等相关学科的发展，国内外研究人员进行了广 泛、深入的研究。由遥感获取的地形数据生成具有高度细节层次的三维地形 模型已经十分普遍。这些由上百万或更多三角形面片表示的各种地形模型， 满足了人们对地形真实性所提出的越来越高的要求，但由于这些数据很少从 绘制效率方面考虑进行优化，因此对计算机的性能提出了新的挑战。随着图 形硬件技术的快速发展，图形处理能力不断的增强，但仍远远不能满足实际 需求。如何实现大规模真实数据高度场的实时显示已经成为此领域的一个瓶 颈问题。对此，就目前研究的方向而言，主要集中于高度场数据的组织管理 如何满足实时渲染的要求、实时渲染、纹理和光照的使用方式改进、地形数 据的l o d 控制、视锥体可见域的裁剪等多个方面。就目前己发表的研究和应 用成果来看，地形简化算法基本分为两种：一是基于四叉树结构的简化算法： 二是基于三角网的简化算法。前者速度快，但是简化效果不如后者；后者的 效果应该可以达到最优，但速度却要比前者慢一个甚至几个数量级。地形多 5 哈尔滨工程大学硕士学位论文 分辨率模型是地形实时绘制系统中的核心组成部分，具有非常重要的作用， 而且模型的优劣将直接影响系统功能的实现。 基于真实地形数据的地形生成及实时显示技术是实际工作中使用最多的 一类。目前大多采用数字高程模型( d i g i t a le l e v a t i o nm o d e l ，d e m ) 来生成， d e m 数据由在规则网格地形图上采样所得的高程值构成。例如，与飞机或卫 星上所拍摄的遥感纹理图像数据相对应，这些纹理图像在重构地形表面时被 映射到相应的部位。简单的地景渲染算法 5 ，是将相邻的4 个网格点定义的 d e m 单元变换成二个三维空间的三角形，然后将视景体内部区域的所有这样 的三角形送入图形流水线进行绘制。这种算法还可将图像纹理数据以它的最 高分辨率映射到对应的多边形上，这是一个效率很低的方法。通常对d t m 数据要进行一定的简化，早期生成l o d 模型的基本方法有两种：简化方法 ( s i m p li f i c a t i o n ) 和细化方法( r e f i n e m e n t ) 6 。7 。早期的简化工作主要集 中在离散l o d ( l e v e l so f d e t a i l ，l o d ) 模型的生成及实时显示方面。简言之， 这类方法就是离线生成多个离散的不同细节层次模型，实时显示过程中，以 当时的条件进行选择调用。这些条件包括地景整体距视点的距离远近、投影 后地形在图像空间所占像素面积的大小以及光照强弱等。交互过程中，对于 每个特定的场景，只需选择一个合适的l o d 模型进行渲染即可。由于不同 l o d 模型之间在拓扑结构上互不相关，因此这种离散l o d 技术有一个明显的 缺点，即在实时显示中，不同l o d 模型之间进行切换时，在视觉上会引起明 显的突跳感。为了克服这一现象，出现了许多改进的方法，如减小相邻l o d 模 型的细节层次差别，或者在距离视点较远的地方进行两个l o d 模型的切换 等。由于存贮空间是有限的，生成的l o d 模型的数目必然会受到限制，因此 这类方法并非很适合大规模高度场的实时渲染。 上述早期的针对复杂地形模型的简化和多分辨率表示主要适用于复杂地 形模型的预处理，即生成地形模型在不同误差控制下的动态多分辨率模型， 但在不同l o d 层次间切换进行地形绘制时有明显的跳跃感，不适于实时交 互。后来出现了视点相关( v i e w d e p e n d e n t ) 的模型简化技术，它不再把模型 看成一个整体来简化，而是针对视点的位置，只选取与视点相关的模型区域， 6 哈尔滨工程大学硕士学位论文 对离视点近的区域以较高的细节度表示，而离视点远的地形则用较少的细节 度表示，实现视点相关连续l o d 绘制。9 0 年代中期出现的连续l o d 模型 4 ，5 。 一些文章上也将这种模型称为多分辨率模型( m u l t i r e s 0 1 u t i o n m o d e l s ) 。所 谓连续l o d 模型是指一种紧凑的模型表示方法，从这个表示中可以生成任意 多个不同分辨率的模型，从而实现模型的连续显示。从发表的文献和资料来 看，目前的研究主要集中在视点相关多分辨率模型。尽管存在着各种各样的 地形层次多分辨率表示方法，但从多分辨率模型表示的结果来看，主要可归 结为基于三角网格的多分辨率层次模型和基于树数据结构的多分辨率层次模 型。基于三角网格的多分辨率层次模型方面，d e f l o r i a n i 1 0 首先提出了用 层次结构来描述地形的方法，但其最大问题是建立层次三角形的不可避免地 出现细长的三角形，从而造成地形的拟合精度下降。若视点改变，如果实时 重新构建三角网格，将使简化速度受到影响，从目前已有的各种基于三角网 格的实时多分辨率模型建模方法来看，基本思想都是避开复杂的三角网格重 建过程，而采用了三角阚格预处理的方式，记录模型简化过程中的模型信息， 在实时简化中利用这些已知的信息进行边合并或分裂，实现基于视点相关的 三角网格实时多分辨率模型，如h o p p e 提出的累进网格( p m ) 方法、唐泽圣 等提出的有序递减网格实时动态绘制算法 3 0 ，3 5 。此外，还有使用形态上 变形的方法来实现不同分辨率地形三角网格间连续过渡的方法。基于树类数 据结构的多分辨率层次模型方面，l i n d s t o r m 2 9 较早提出了四叉树结构的实 时地形简化算法，王宏武 1 5 等提出了基于多分辨率地形模型的视点相关模 型。 1 3 论文所做工作 如前所述，最近提出的高度场及地形实时渲染方法，虽然大部分都利用 了视点相关和连续l o d 模型技术，但其层次模型的生成都是以原始模型的简 化为基础的。 与此相比，本文所提出的方法是基于一种对整个模型生成过程及其应用 特点的多方面考虑，并应用了表面细分理论，从而更加兼具理论及实践意义。 7 哈尔滨工程大学硕士学位论文 本文的主要工作在于： ( 1 ) 提出了一种从数据集x 自动重建平滑、具有自适应细分特性的的表 面s 的实时演染方法，这里x 通常是r2 域上以正交网格形式分布的高度场数 据集。 ( 2 ) 对高度数据并未作限制，可由算法，例如，不规则碎片地形算法产 生，根据特定应用的需要，这时可省去对x 的预处理。值得注意的是，这里 x 也可以是真实的遥感或扫描数据。 ( 3 ) 定义了快速视点相关递归划分的标准，标准考虑了视锥体、屏幕空 间投影大小等因素。 ( 4 ) 提出了一种以上述标准为基础的网格精化的高效算法。算法利用了 快速中心差分操作，支持帧率和建模策略的灵活调整，并通过支持表面细分 特性进一步提高了视觉质量。 ( 5 ) 方法实时地以动态方式产生l o d 模型，避免付出预先产生多分辨率 模型的较高计算代价。实现了表面几何结构的动态改变，从而实现了帧间不 同层次细节模型较为平滑的变化。 本文提出的方法将从几个方面描述，首先是中心差分镶嵌法，还有递归 镶嵌的条件，裂缝消除，多片元构成高度场( 地形) 等方面。对纹理和光照、 视锥体裁剪也有说明。 1 4 论文结构概述 本文涉及的相关技术在2 章介绍，所使用的具体中心差分形式在第3 章 描述，并在此章解决了单个面片镶嵌的问题。第4 章阐明了如何由单个面片 构造完整的高度场( 地形) 系统。给出的实时渲染的辅助技术，并提出一种配 合本渲染技术的预处理方法。在结论部分对研究工作进行了总结，并提出需 要进一步研究的问题。 哈尔滨工程大学硕士学位论文 第2 章相关技术 2 1 高度场的数据表达方式 d e m 和d t m 主要用于描述地面起伏状况，可以用于提取各种地形参数，如 坡度、坡向、粗糙度等，并进行通视分析、流域结构生成等应用分析。因此， d e m 在各个领域中被广泛使用。 2 1 1 数字地形模型 数字地形模型( d t m ，d i g i t a lt e r r a i nm o d e l ) 最初是为了高速公路的 自动设计提出来的( m i l l e r ，1 9 5 6 ) 。此后，它被用于各种线路选线( 铁路、 公路、输电线) 的设计以及各种工程的面积、体积、坡度计算，任意两点间 的通视判断及任意断面图绘制。在测绘中被用于绘制等高线、坡度坡向图、 立体透视图，制作正射影像图以及地图的修测。在遥感应用中可作为分类的 辅助数据。它还是地理信息系统的基础数据，可用于土地利用现状的分析、 合理规划及洪水险情预报等。在军事上可用于导航及导弹制导、作战电子沙 盘等。对d t m 的研究包括d t m 的精度问题、地形分类、数据采集、d t m 的粗差探 测、质量控制、数据压缩、d t m 应用以及不规则三角网d t m 的建立与应用等 8 。 数字地形模型是利用一个任意坐标场中大量选择的己知x ，y ，z 的坐标点 对连续地面的一个简单的统计表示，或者说，d t m 就是地形表面简单的数字表 示。数字地形模型更通用的定义是描述地球表面形态多种信息空间分布的有 序数值阵列，从数学的角度，可以用下述二维函数系列取值的有序集合来概 括地表示数字地形模型的丰富内容和多样形式。1 ： k p = 六 p ，v p ) ，k = 1 ，2 ，3 ，m ，p = 1 ，2 ，3 ，n ( 2 - 1 ) 哈尔滨工程大学硕士学位论文 式中 k 。一第p 号地面点上的第k 类地面特性信息的取值； 似，v ，) 一第p 号地面点的二维坐标： m 一地面特征信息类型的数目； h 一地面点的个数； 2 1 2 数字高程模型 从数学的角度，高程模型是高程z 关于平面坐标x ，y n 个自变量的连续函 数，数字高程模型( d e m ) 只是它的个有限的离散表示。高程模型最常见的 表达是相对于海平面的海拔高度，或某个参考平面的相对高度，所以高程模 型又叫地形模型。实际上地形模型不仅包含高程属性，还包含其它的地表形 态属性，如坡度、坡向等。 数字地形模型是地形表面形态属性信息的数字表达，是带有空间位置特 征和地形属性特征的数字描述。数字地形模型中地形属性为高程时称为数字 高程模型( d i g i z a le l e v a t i o n m o d e l ，简称d e m ) 。高程是地理空间中的第三 维坐标。由于传统的地理信息系统的数据结构都是二维的，数字高程模型的 建立是一个必要的补充。d e m 通常用地表规则网格单元构成的高程矩阵表示， 广义的d e m 还包括等高线、三角网等所有表达地面高程的数字表示。在地理信 息系统中，d e m 是建立d t m 的基础数据，其它的地形要素可由d e m 直接或间接导 出，称为“派生数据”，如坡度、坡向。 式( 2 1 ) 中，当t n = 1 且工为对地面高程的映射， ，v ，) 为矩阵的行列号 时，式( 2 1 ) 表达的数字地模型即所谓的数字高程模型。实际上，d e m 是d t m 中晟基本的部分，它是对地球表面地形地貌的一种离散的数字表达。 总之，数字高程模型d e m 是表示区域d 上的三维向量有限序列，用函数的 形式描述为： v = ( ，r ，z 。) ，i2 1 ，2 ，3 ，” 1 0 ( 2 2 ) 哈尔滨工程大学硕士学位论文 式中 。，r 一平面坐标： 互一( x ，z ) 对应的高程。 当该序列中各平面向量的平面位置呈规则网格排列时，其平面坐标可以 省略，此时d e m 就简化为一维向量序列 z ，i = 1 ，2 ，3 ，珂一。 2 2 可见性剔除技术 背面剔除和视锥体剔除是实现可见性剔除的常用技术。是提高实时绘制 效率具有效工具。可见性剔除算法通过在绘制前快速判断不可见的绘制元素， 得到可能的可见集，从而减少不必要的运算时间和存储空间。这里对其中的 主要技术作一概述，即背面剔除( b a c kf a c ec u l l i n g ) 和视锥体剔除( v i e w f r u s t u mc u l l i n g ) 。 背面剔除用来剔除背向视点的多边形。这些多边形因为背离视线方向而 显然不可见，因而应及时删去以提高取景变换的效率。决定一个多边形是否 背离视点只需作一简单的几何测试。先计算多边形的法向和视线向量，其中 视线向量为从多边形到视点的向量。分别记这两个向量为。和，然后计算 ，和的夹角。如果该角大于9 0 。即，n o ，则该多边形为背面( 如图 2 1 示) 。可从需作进一步取景变换的场景多边形集合中删除 1 0 。 哈尔滨工程大学硕士学位论文 图2 1 背面剔除 2 0 0 3 年，s h e n gl i 等提出了一种针对地形t i n 模型的背面剔除算法“。算 法的基本思想是，在预处理过程提取地形特征( 主要是山脊线) ，然后剔除掉 不可见的山脊线背面三角形。算法是基于这样的一个事实，在对于起伏剧烈 的地形表面( 如山区) ，在某一视点位置，位于山脊线背面的区域大部分不为 视点所见。 视锥体剔除算法通常采用的是绘制元素组的约束盒作为替代进行可见性 判断，如果约束盒位于视域四棱锥( v i e wf r u s t u m ) 之外，则其所包围的所有 绘制元素都不可见。 2 3 高度场网格模型的裂缝消除技术 多分辨率层次细节网格简化技术，依据地形的表面特征以及地形节点距 离视点的距离对地形的不同区域通过不同的分辨率层次细节进行简化。在运 用树数据结构对地形进行多分辨率表示时，不同层次细节的地形块之间，会出 现“网格裂缝”现象。 通过改变引起裂缝的顶点的高度值实现无缝拼接( 会导致t 型节) 。如图 1 2 哈尔滨工程大学硕士学位论文 2 2 所示，不过，允许t 型节出现的做法虽然简单，也会带来绘制时的光照的 一些不连续现象，对于有些显卡也可能导致一些空洞小点 i 2 。 图2 2 裂缝消除 一般对此问题解决方式有几种。例如对较低的细节层次进行割分，使它 能够达到使用裂缝点的较高层次细节；另一种就是在保证相邻节点的层次细 节差异不大于l 级的条件下，通过绘制较高细节层次节点时舍弃裂缝点。前者 没有相邻点细节层次差异级数的要求，能够在任意时刻处理任何裂缝点，但 是会增加场景的复杂度，也间接的描述了更详实的地形；后者在裂缝点的处 理上相对简单一些，但是为了满足相邻节点层次细节差异级数的要求也会在 节点分割过程中导致一些额外的开销，同时还需要在绘制过程中查询相邻节 点的状态以决定是否跳过裂缝点。此外，还有几种方式，例如采取将高分辨 率顶点拉向底边以达到闭合的方法，用在可能发生裂缝的地方进行三角剖分 的方法来填充裂缝等。 2 4 光照计算 2 。4 1 光照模型 光照模型即根据光学物理的有关定律，计算景物表面上任一点投向观察 者眼中的光亮度的大小和色彩组成的公式“。光照计算与光照模型密切相 关。 来自光源或周围环境的光照射到景物表面时，会出现以下3 种情形： ( 1 ) 经景物表面向外反射形成反射光。 ( 2 ) 若景物透明，则入射光会穿透该景物，从而产生透射光。 ( 3 ) 部分入射光将被景物吸收而转换成热。 物体表面的反射光和透射光的光谱分布决定了景物表面呈现的颜色。只 有反射光和透射光能够刺激人眼产生视觉效果。反射光和透射光的强弱则决 定了景物表面的明暗程度，显然，反射光和透射光决定于入射光的强弱、光 谱组成以及景物表面对入射光中不同波长光的吸收程度。 由以上论述。若已知入射光在每一波长上的强弱和物体表面在此波长上 对光的吸收率，即给出入射光的光普分布以及物体表面的反射率和透射率的 光谱分布就能根据环境的光源布置和景物表面的材料属性正确计算出景物 表面反射光和透射光的光强和颜色。但由于光谱采样和光谱至颜色的转换的 计算量相当大面在许多应用场合并不要求如此精确的模拟，因而有必要 给出一些简单的光亮度计算方法。认视觉效果来看，通常可假定入射光仅由 红、绿、蓝三种小同波长的光组成这样在光照模型中。就仅需考虑景物 表面对这三种不向波长光的反射和透射从而大大简化光亮度的计算。更近 一步，若假定光源发出的光为白光。景物为不透明体，则景物表面呈现的颜 色仅由其反射光决定。物体表面的反射光可分为漫反射光和镜面反射光，漫 反射光可以认为是光穿过物体表面层被部分吸收后。重新发射出来的光。因 此漫反射光均匀地散布在各个方向观察者不论站在哪一方位上。他所观 察到的漫射光的强度均相等。镜面反射光则是物体的外表面对入射光的直接 1 4 反射。镜面反射光亮度沿镜面反射主方间最强。在该主方向四周则逐渐衰 减形成一定的空间分布因而，观察音只有位于一定方向上，方可看到明 亮的镜面反射光。 在计算机图形学中，采用光照明模型来计算景物表面上任一点投向观察 者眼中的光亮度的大小和色彩组成。光照明模型分为局部光照明模型和全局 光照明模型。局部光照明模型仅考虑光源直接照射在景物表面所产生的光照 效果，景物表面通常被假定为不透明，且具有均匀的反射率。局部光照明模 型能表现由光源直接照射在漫射表面上形成的连续明暗色调、镜面上的高光 以及由于景物相互遮挡而形成的阴影等。考虑到目前实时绘制技术常采用局 部光照明模型，以下以较为简单的p h o n g 模型为例进行说明。 p h o n g 模型是由1 9 7 3 年p h o n g 提出的关于镜面反射光的经验模型与 l a m b e r t 漫反射模型结合产生的。它仅考虑了景物表面的漫反射和镜面反射光 的计算，因而可独立地分解为漫射分量和镜面反射分量： ，= 七。+ k d ( 三) + k s ，f ( y r ) 4 ( 2 3 ) 实际环境中，物体会接受到一些从周围环境投射来的光，称这部分光为 环境光或泛光。右边第一项即泛光项，第二项为漫反射项，第三项为镜面反 射项。k 为泛光系数，k 为漫反射率，k 。为镜面反射率，其取值范围均为0 至1 。，。为泛光强度，为光源的入射光亮度。为被照射点p 处的表面单 位法向量，为被照射点p 指向光源方向的单位向量，厅为关于的镜面反 射方向的单位向量，矿为被照射点p 指向视点方向的单位向量，如图2 3 所 示。镜面高光指数门控制着景物表面上高光范围的大小。 哈尔滨工程大学硕士学位论文 。： 钐 ，) 图2 3p h o n g 模型的几何说明 p h o n g 模型是一个纯几何模型，一旦光源颜色和景物表面反射率得以确 定，则从景物表面可见点p 处到达观察者的反射光亮度仅与入射角、视线与镜 面反射光的夹角有关，因此，仅需求出景物表面各点法向，结合必要的已知 项厶n 用，即可计算每一点的光亮度。因而计算相当简便。特别地，当镜 面反射率取为0 时，p h o n g 模型就退化为l a m b e r t 漫反射模型。在具体实现时， 也、k 、k ，、i o 和，分别由红、绿、蓝三分量组成，因而，式( 2 - 3 ) 需对红、 绿、蓝三分量分别计算得到最终的可见点光亮度。式( 2 3 ) 描述的是单光源照 射下的光亮度计算。若要对多光源的光照进行计算，只需对每个光源分别计 算累加即可。 2 4 2 增量光亮度插值 即使采用较为简单的光照模型，由于需计算每一被照射点处多个单位向 量，因而其计算量还是很大的。为此，图形学中常用增量方法来计算光亮度。 这就是著名的g o u r a u d n ) j 暗处理和p h o n g n ) j 暗处理。 景物表面的多边形逼近容易失去原有曲面的光滑性，这是由于每一平面 片上所有点的法向均相同。若采用p h o n g 模型来绘制画面，则同一平面片上光 亮度将保持一致，而相邻平面片间法向量的不连续性将导致物体表面光亮度 的不连续变化。为了解决由多个平面片近似表示的曲面物体的绘制问题提出 了各种不同的简便算法。增量光亮度计算最初是为解决多边形逼近曲面的光 1 6 哈尔滨工程大学硕士学位论文 滑绘制而设计的，由于其高效的硬件实现，目前己广泛应用于实时绘制系统 中。 g o u r a u d 明暗处理将曲面表面的光亮度取为近似表示该曲面的各多边形 的顶点光亮度的双线性插值“。假定一曲面物体由多面体表示，已知各多边 形的法向，则对每一顶点，可取共享该顶点的各多边形法向的平均值作为该 顶点处曲面的法向，然后把该法向代入光照明模型计算出顶点处曲面的光亮 度值。在图2 4 中，顶点a 处曲面的法向可取为共享该顶点的各多边形的法向 量v ，、，、，、。；的平均值 以= 三( i + 2 + ，+ 4 ) 图2 4 顶点a 的法向计算 ( 2 4 ) 当然，在代入光照明模型计算之前，需先对。进行单位化处理。若已知 生成该多面体的原始曲面，而多边形的各顶点即为原始曲面上的采样点，则 可取多边形各项点处原始曲面的真正法向，直接代入光照明模型进行光亮度 计算。在采用扫描线算法对上述多边形进行绘制时，先用多边形顶点的光亮 度线性插值出当前扫描平面与多边形边界交点处的光亮度，然后再用交点的 光亮度线性插值出多边形与扫描平面相交区段上每采样点的光亮度值。图 2 5 显示出一扫描平面与多边形相交，交线的端点是a 点和b 点，p 是投影于相 17 哈尔滨工程大学硕士学位论文 应扫描线上一象素中心的多边形采样点，多边形三个顶点的光亮度分别为，。、 ，：、，。取a 点的光亮度j 。为厶和，：的线性插值，b 点的光亮度j 。为，2 和，的 线性插值，则p 点的光亮度j ，为，。和1 。的线性插值。即 i = u 1 1 + ( 1 一u ) 1 2 ，“= a k ，8 = 订1 + ( 1 一v ) 1 3 ，v = b 圪k i p = 以+ ( 1 一f ) 日， r = p b a b 其中u ，v ，t 称为插值参数。 j j 图2 5 采用双线性捅值计算p 点的光亮度 ( 2 5 ) ( 2 - 6 ) ( 2 7 ) 采用g o u r a u d 暗处理不但可以克服由多边形近似表示的曲面光亮度的 不连续现象，而且计算量也很小。事实上，线性插值可使用增量法进行计算， 其计算量仅涉及一次加法计算。如在上例中，可沿扫描线，从左至右顺序计 算a 8 区段上所有象素的光亮度。设，。和i a 已经确定，只和最点是相邻两象 素的坐标，相邻象素的插值参数之差为a t ，那么，不难发现只点光亮度，。和 鼻点光亮度。之间有以下关系： ，b 。， + ( ，4 1 b ) ，= ，b + ， ( 2 8 ) 哈尔滨工程大学硕士学位论文 由于i 在同一条扫描线上为常数，因此计算一相邻象素的光亮度仅需一 次加法计算。这种增量方式的光亮度计算使得g o u r a u d h 蝈暗处理广泛用于速度 要求较高的应用领域，如飞行模拟、动画设计以及c a d 领域中的快速显示等。 尽管g o u r a u d 明暗处理简单易行，但有时也会产生错误的绘制效栗。如图 2 6 ( a ) 所示，。，m ，和，。是4 个顶点的法向量。由于 n p l = y 2 = 南= n 导致，r l = j r 2 = ，y ，= ，r 4 ，采用6 0 u r a u d 明暗处理技术将 使多边形面片尸内各点光亮度取为常数，这显然是不正确的。针对这种情况， 可将多边形分割成更细小的多边形如图2 6 ( b ) 。由于这些多边形起到了过渡 作用，因而避免了错误。g o u r a u d 明暗处理不能正确地模拟高光，这是因为采 用光亮度插值后将使多边形内的高光丢失。另外，6 0 u r a u d 明暗处理会诱导马 赫带效应。虽然光亮度双线性插值保证了由多边形近似表示的曲面上各处光 亮度的连续变化，但在相邻多边形的公共边界上光亮度的一阶导数并不连 续，由于人眼的光学错觉，光亮度变化一阶不连续的边界处会呈现亮带或黑 带，即马赫带效应。克服这些缺点的一种方法是采用p h o n g 明暗处理。 ( a ) 平面不连续所产生的错误( b ) 补救措施 图2 6g o u r a u d 明暗处理中的特殊情况 p h o n g 明暗处理，也叫法向量插值明暗处理，它以增加一定的丌销为代价 克服了g o u r a u d 明暗处理的缺点“”。p h o n g 明暗处理能正确地模拟商光并能大 大减轻马赫带效应。它的思想是对多边形顶点处法向量做双线性插值，在多 1 9 哈尔滨工程大学硕士学位论文 边形内构造一个连续变化的法向量函数，将依据这一函数计算的多边形内各 采样点的法向代入光亮度计算公式，即得到由多边形近似表示的曲面在各采 样点出的光亮度。法向量插值方法和光亮度插值类似，例如，可采用前述的 扫描线双线性插值方法。如在图2 5 0 ，a 点的法向量。为，和，的线性 插值，b 点的法向量。为，和，的线性插值，而p 的法向量则是。和。 的线性插值，即 n = u n l + ( 1 一u ) n 2 ，u = a v , 吃 n b = v n i + ( 1 一v ) 虬，v = b k k n p = t n + ( 1 一t ) n 口， f = p b a b ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 其中u ，v ，t 为插值参数。线性插值的计算仍可采用前述的增量法 n p 2 = n 日+ ( 虬一n 日) a t = n n + ( 2 1 2 ) p h o n g 明暗处理从求解由多边形近似表示的原曲面的法向量入手，画面真 实感较g o u r a u d 明暗处理的绘制结果有明显改进，如图2 6 所示。但是，由于 每一象素内表面采样点光亮度还需使用光照明模型进行计算，故计算量较大。 这影响了它在一些实时图形系统中的直接应用。为此人们采取了一些加速的 方法。加速方法可分为数值方法和几何方法。作为实践中采用的一种技巧， 可隔一个象素应用光照明模型，而中间象素的光亮度取为相邻象素光亮度的 平均。这种两步插值法在图像质量方面几乎没什么损失。这相当于将多边形 投影到只占三个象素的屏幕区域，然后进行o o u r a u d 明暗处理，而任这一级分 辨率下，o o u r a u d 明暗处理的缺陷消失。采用这种技巧，可使绘制时间减少百 分之三十。在数值优化方向，d u f f 把插值公式代入光照明模型中( 2 0 ) ，然 后用正向差分技术获得简化表达式。采用该项优化技术后，可使每个象素的 计算量减为三次加法、一次除法和一次开方运算。b i s h o p 采取的策略与d u f f 的类似，其主要思想是将法向量插值公式代人光照明模型中，取其泰勒展开 式的前三项作为光亮度计算的近似公式( 2 1 ) 。在几何优化方面h a r r i s o n 提出局部区域的高光叠加技术 2 1 ，即首先采用g o u r a u d 明暗处理方法快速绘 2 0 哈尔滨工程大学硕士学位论文 制整个物体。然后对每一多边形进行镜面高光检测。将镜面高光添加到那些 确实包含高光的多边形中。因为通常物体表面上只有一小块区域包含高光运 用该方法可显著地提高绘制效率，其代价是会带来一定程度的马赫带效应。 2 5 纹理映射技术 物体表面对光照的反射率通常是不同的，但为了说明光照明模型，当时 假设表面反射率为常数。景物表面的反射率变化在图形学中用纹理来描述 “。这里仅就最常用和通常意义上的二维纹理进行介绍。 二维纹理映射本质上是一个二维纹理平面到三维景物表面的一个映射。 一般来说，二维纹理定义在一平面区域上，它可以用数学函数解析地表达， 亦可以用各种数字化图像来离散定义。这样，该平面区域上的每一点处，均 定义有一灰度值或颜色值。称该平面区域为纹理空间。在图形绘制时，利用 纹理映射可方便地确定景物表面上任一可见点p 在纹理空间中的对应位置( u ， v ) ，( u ，v ) 处所定义的纹理值或颜色值描述了景物表面在p 点处的某种纹理 属性，如漫反射率和镜面反射率等。 纹理的映射方式直接影响最终生成图形的真实性。从数学的观点来看， 映射可用公式( 2 一1 3 ) 式来描述： 其中( u