（计算机应用技术专业论文）虚拟现实中层次细节技术研究及应用.pdf

摘要 摘要 虚拟现实中对复杂三维场景的实时绘制提出了越来越高的要求。本文采用层 次细节技术来实现实时渲染，涉及了三个方面：网格模型层次细节技术、粒子系 统层次细节技术、动画和碰撞的层次细节技术。 在网格模型层次细节技术部分，结合g l o d 流程推广现有的网格层次细节算 法，讨论了更为一般化的网格层次细节算法框架以及建立层次细节模型的简化算 法，并研究了框架中可以扩展的一些算法，有效地提高了简化的质量。另外，本 文还针对地形数据实现了实时层次细节处理。 在粒子系统层次细节技术部分，借鉴网格层次细节技术，针对粒子系统实时 渲染的特点，本文提出了粒子系统层次细节系统框架，实现了对粒子系统的实时 渲染。 影响实时渲染的因素不仅包括具体模型，还包括动画和碰撞。因此，本文将 层次细节技术应用到动画和碰撞处理过程中，提高了对虚拟场景渲染的实时性。 基于以上的层次细节技术，本文构建了虚拟现实绘制系统。系统对三维场景 数据、动画数据、碰撞数据进行有效地设计和管理，使场景中的三维数据可以方 便地进行各种操作，如建立、复制、剪切、粘贴、移动、删除、复用、查找、交 互等。为了解决模型内存需求与实际内存不足之间的矛盾，本文引入了内联节点， 使系统具备了对大型场景进行管理和渲染的能力。同时本文还提出了一种用关系 数据库方式对虚拟现实中场景数据进行管理的方法，为可视化编辑、高效查询、 三维数据维护提供了一种新的手段。实验表明，各项技术的应用明显地提高了系 统的渲染效率，同时也有效地保持了场景渲染的真实感。 关键字：虚拟现实；层次细节：粒子系统；动画：碰撞；图形引擎 a b s t r a c t a b s t r a c t b r o a da p p l i c a t i o n so fv i r t u a lr e a l i t yh a v eb e e ns e t t i n gh i g h e ra n dh i g h e rt e c h n i c a l s p e c i f i c a t i o nf o rr e a l t i m er e n d e r i n go fc o m p l e xs c e n eo f t h r e e d i m e n s i o n a ls p a c e i n t h et h e s i s ，l e v e lo fd e t a i l ( l o d ) t e c h n o l o g yi sa p p l i e dt or e a c ht h er e q u i r e m e n t ，w h i c h i sc l a s s i f i e di n t ot h r e eb r a n c h e s ：l o do fm e s hm o d e l ，l o do fp a r t i c l es y s t e m ，l o d o fa n i m a t i o na n dc o l l i s i o n o nl o do fm e s hm o d e l ，i n t e g r a t e dw i t ht h ef l o wp r i n c i p l eo fg l o da n dt h e e x i s t e n ta l g o r i t h m so fm e s hl o d ，am o r eg e n e r a la l g o r i t h m i cf r a m e w o r ko fm e s h l o da n das i m p l i f i e da l g o r i t h mo f b u i l d i n gl o dm o d e la r ep r o d u c e d f u r t h e r m o r e ，a l o df r a m e w o r kf o rr e a l t i m er e n d e r i n go ft e r r a i nd a mi si m p l e m e n t e di nt h et h e s i s i nl e v e lo fd e t a i lt e c h n o l o g yo fp a r t i c l es y s t e m ，a c c o r d i n gt ot h ec h a r a c t e r i s t i co f r e a l - t i m er e n d e r i n go fp a r t i c l es y s t e m ，av i e w - d e p e n d e n tl e v e lo fd e t a i lf r a m e w o r k s y s t e mi se m p l o y e d t h e r e f o r e ，i te n a b l e sp a r t i c l es y s t e mt oh a v et h ea b i l i t yt o r e a l - t i m er e n d e r i n g o nl o do fp a r t i c l es y s t e m ，b a s e do nt h em e s hl o daf r a m e w o r ko fl o df o r r e a l - t i m er e n d e r i n go f p a r t i c l es y s t e mi si n c l u d e d t h ef a c t o r st oi n f l u e n c er e a l - t i m er e n d e r i n gi n c l u d en o to n l yt h em o d e l sb e i n g r e n d e r e db u ta l s oa n i m a t i o na n dc o l l i s i o n s oi ti sn e c e s s a r yt oa p p l yl o dt o a n i m a t i o na n dc o l l i s i o nt oi m p r o v et h er e a l t i m e r e n d e r i n g o fa n i m a t i o n a n d c o l l i s i o n b a s e do nt h ea c h i e v e m e n tr e l a t e dw i t l la b o v ew o r ka n dt h et e c h n o l o g yo f t h r e e - d i m e n s i o n a ld a t am a n a g e m e n tap r o t o t y p eo fe n g i n es y s t e mo fv i r t u a lr e a l i t yi s r e a l i z e d i nt h es y s t e mm o r ea t t e n t i o ni sp a i dt ot h em a n a g e m e n to fs c e n ed a t a ， a n i m a t i o nd a t aa n dc o l l i s i o nd a t as ot h a tt h ed a t ac a l lb eo p e r a t e dc o n v e n i e n t l y , s u c h a s ，c r e a t i o n ，r e p l i c a t i o n ，c u t , p a s t e ，r e m o v e ，d e l e t i o n ，r e u s e ，i n d e xa n do p e r a t i o n m u t u a l l ya n ds oo n i na d d i t i o n ，t os o l v et h ec o n t r a d i c t i o nb e t w e e ns u p p l ya n d d e m a n do fm e m o r y , t h ei n l i n en o d ei sc o m b i n e dw i t ll o da n da sar e s u l ta 1 1 1 1 1 北京工业大学工学硕士学位论文 e x e c u t a b l em e t h o di sp r o v i d e dt om a n a g ea n dr e n d e rl a r g e rs c a l ev i r t u a le n v i r o n m e n t s y n c h r o n o u s l y , am e c h a n i s mo fm o d e l i n ga b o u ts c e n ed a t ai nv i r t u a lr e a l i t yw i t h r e l a t i o nd a t a b a s ei sa d o p t e d ，w h i c hi m p o r t san e wm e a no fs u p p o r t i n gv i s u a le d i t o r , e f f i c i e n ti n q u i r i n gt h r e e d i m e n s i o n a ld a t aa n dm a i n t a i n i n gt h r e e d i m e n s i o n a l d a t a c o n v e n i e n t l y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e m e n to fr e n d e r i n go nb o t h t i m ea n d r e a l i t yc a r lb ea c h i e v e db yu s i n gt h e s et e c h n o l o g i e s k e yw o r d s ：v i r t u a lr e a l i t y ；l e v e lo fd e t a i l ；p a r t i c l es y s t e m ；a n i m a t i o n ；c o l l i s i o n ； g r a p h i ce n g i n e ； i v 目录 图表目录 图2 1 模型层次细节的流程图 图2 2 ：建立l o d 网格模型的流程图 图2 。3 ：视点相关顶点树的结构图 表2 1 ：网格简化规则分类表 图2 4 ：顶点聚类规则示意图 图2 5 ：顶点删除规则示意图 图2 - 6 ：边折叠规则示意图 图2 7 ：顶点聚类示意图 图2 8 ：模型简化的效果图 图2 - 9 ：动态管理l o d 模型的流程图 图2 1 0 ：视点相关顶点树的顶点分类图 图2 1l ：顶点折叠操作示意图 图2 1 2 ：顶点分裂操作示意图 图2 1 3 ：g l o d 的流程图一 图2 1 4 ：模型l o d 的效果图 图2 1 5 ：地形模型l o d 的流程图 图2 1 6 ：地形数据的格式示意图 图2 1 7 ：地型模型l o d 的效果图 图3 一l ：粒子系统l o d 的系统框架示意图 图3 2 ：粒子系统的l o d 规则示意图 图3 - 3 ：粒子系统l o d 的效果图 表3 1 ：粒子系统层次细节的测试数据表 图4 1 ：人群动画的效果图 表4 1 ：人群动画层次细节的测试数据表 图4 2 ：碰撞检测的效果图 表4 2 ：碰撞检测层次细节的测试数据表 图5 - 1 ：场景树结构示意图 图5 2 ：场景二叉树结构示意图 v i i 石 一 一 9 m m n h 坶 加 扒 扒 挖 抖 筋 拍 拍 如 弛 驺 弛 弛 铂 拍 钾 钾 如 钉 北京工业大学工学硕士学位论文 图5 3 ：建立内联节点的流程图 图5 - 4 ：场景中的内联节点结构图 图5 5 ：动画节点结构示意图 图5 - 6 ：动画节点文件结构示意图 图5 7 ：动画节点实验效果示意图 图5 - 8 ：碰撞节点结构示意图 图5 - 9 ：碰撞节点实验效果示意图 图5 1 0 ：碰撞节点文件结构示意图 图5 1 1 ：场景关系数据库的结构示意图 图5 1 2 ：场景关系数据库系统的界面 图5 - 1 3 ：将数据库存储方法应用在北工大漫游系统项目中的结果图 图5 1 4 ：虚拟现实绘制系统的系统框架示意图 图5 - 15 ：虚拟现实绘制系统的类图 图5 1 6 ：虚拟现实绘制系统的渲染效果图 v m 盟 鹑 舛 弱 卯 弘 四 乱 饥 斛 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 o j 、占、窖 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：鼢导师签名： 勉整望日期：堕：! 绪论 第一章绪论 虚拟现实( v i r t u a lr e a l i t y ，v r ) 是通过多种传感设备使用户“投入”到计算 机生成的一种模拟环境中并可使用户与该环境直接进行交互的技术。虚拟现实技 术在各个领域都有广泛应用，并对场景的组织管理和实时绘制提出了很高的要 求，一方面物体、场景越来越多样和复杂，超过了绘制引擎的实时绘制能力，另 一方面要求生成的物体、场景更加真实、具有良好的交互性，这就要求进一步研 究复杂场景的实时绘制技术。其中层次细节技术是众多实时绘制技术中最重要的 一种。 本章的内容是按照以下方式组织的：首先介绍本文的研究背景、现状，并简 要地阐述层次细节技术所涉及的内容及本文的创新之处，最后将介绍论文的内容 排列与组织结构。 1 1 研究背景 随着计算机图形学真实感绘制和三维获取方式的发展，模型越来越精细、逼 真，同时，动画与碰撞的数据也越来越多样和复杂。由此建立起的三维模型及动 画碰撞数据的复杂程度远远超过了当前计算机图形实时渲染能力。为了能够有效 地渲染虚拟现实中的三维场景，由此产生了对模型数据，动画数据和碰撞数据的 层次细节技术的研究【卜4 l 。 三维模型越来越复杂，这是因为三维激光扫描仪、医学图像系统、计算机视 觉系统的大量应用，同时这也是为了满足日益高涨的视觉需求。目前，多边形网 格表示方式是目前最常用的一种几何表示方式。为了表示出逼真的效果，模型的 多边形表示方式中常常包含着几百万个多边形网格。但是由于计算机绘制能力的 限制，对这些复杂的模型，在普通的机器上不能很好地实时绘制，另外很多大型 模型( 如地形模型) 所需内存量远大于计算机所能提供的内存量。为了适应这种 实时绘制、多分辨率模型的需求，需要对物体表面进行自动的简化，研究大型模 型的动态简化算法，同时研究大型模型绘制时视点、形状等因素对实时简化算法 的影响。 j ：奎三些盔兰三耋翟圭主竺兰銮 粒子系统5 罐1 是一种用来虚拟自然景物的有效方法，由于粒子系统需要大量的 运算，大量的粒子进行绘制也消耗了大量的c p u 时间，所以绘制的速度会很慢。 因此需要对粒子系统进行层次细节的处理，保持视觉效果的同时提高粒子系统的 绘制效率。动画和撞碰在虚拟现实中被广泛地应用，同时也成为影响渲染速度的 重要因素之一，对这两方面的优化处理成为提高渲染速度的有效手段。 在层次细节技术应用的同时，也产生了如何有效地对三维数据进行设计和管 理的问题。虚拟现实绘制系统是实现层次细节技术的平台和基础，如何有效地对 场景，动画，碰撞进行设计和管理，如何结合到层次细节技术中去成为了虚拟现 实中重要的研究内容之一。本文将分析和研究层次细节技术及相关技术，构建虚 拟现实绘制，达到实时绘制复杂场景的目的。 1 2 现状综述 目前大规模场景的实时图形绘制技术研究主要在场景简化、可见性裁剪、基 于图像的绘制和分布式并行计算等方面展开。目前普遍采用层次细节( l o d ) 模型技术t 9 - 5 6 来实现场景简化，该技术首先由c l a r k t l l l 于1 9 7 6 年提出，基本思想 是：用具有多层次结构的物体集合描述一个场景，即场景中的物体具有多个模型， 各模型具有不同的细节描述能力。在实时显示时，可根据物体重要程度的不同选 择具有相应细节描述能力的模型：而物体的重要程度可由物体在图像空间中所占 面积、与视点的距离等多种因素确定。在计算机图形学中，场景中的物体通常用 多边形网格描述，因此l o d 模型的自动生成就转化为三维多边形网格的简化问 题。传统l o d 模型由于需要同时存储多个物体的模型而使存储量非常大。而且 这种离散的( 静态的) l o d 模型无法支持模型间的平滑过渡。1 9 9 2 年s c h r o e d e r 5 0 1 提出了动态网格简化算法，利用网格的局部几何信息和拓扑信息去掉网格中的顶 点，简化物体模型。但这种方法在顶点被删除之后需要进行运算量较大的三角剖 分过程。1 9 9 2 年t u r k 提出了重新布点法，这种方法仅适用于光滑曲面，且简化 模型中引入了新点。1 9 9 6 年h o p p e b 7 1 提出了采用递进网格表示的简化算法，该 方法绘制效果好，但其迭代优化过程的执行效率很低。1 9 9 7 年g a r l a n d t 2 2 1 提出了 基于二次错误率判别的边收缩方式的实时网格简化算法。这种算法的优点是可实 时，简化质量可控，可同步进行纹理简化。2 0 0 0 年开始，由于计算机硬件的发 绪论 展，网格简化的研究转向大规模场景实时简化方面，l i n d s m 【3 8 1 2 0 0 0 年提出了 一种对大型模型批处理的算法。h o p p e 3 0 】和m a r t i n 4 6 】等人也提出了一种处理大型 模型的方法，主要思想是把大型模型分块直至可导入内存，然后对每个三维块进 行网格简化。2 0 0 3 年c i g n o n i l l 2 1 等人提出一个基于八又树的内存、外存交换模式 以解决内存频繁交换、不足的问题。 在虚拟现实中存在大量特殊的模型种类，如地形、粒子系统等，对于这些模 型的设计和实时绘制技术的研究对于虚拟现实应用有很重要的意义。地形是一个 在动态l o d 和o u t o f - c o r e 核外存储领域中最典型的应用之一。对地形数据进行 有效裁剪和视点相关的实时简化可以大量地减少绘制的数据量。地形漫游算法根 据其网格生成方法可以分为基于规整网格算法和基于不规则三角形网格( t i n ) 算 法两大类。1 9 9 6 年l i n d s t r o m 【3 6 1 首先提出一种基于规整网格连续层次细节的实时 高度场绘制算法。1 9 9 7 年，d u c h a i n e a u y i 2d 】在l i n d s t r o m 的基础上提出r o a m ( r e a l t i m e o p t i m a l a d a p t i v e m e s h e s ，实时优化适应性网格) 算法，这是目前应 用最广的一种算法。1 9 9 8 年，h o p p e t 3 0 l 将视点相关递进网格( v d p m ，v i e w d e p e n d e n tp r o g r e s s i v em e s h e s ) 应用到了地形中。粒子系统是用来模拟自然景物 的有效手段之。1 9 8 3 年，r e e v e s l 6 1 首次提出了粒子系统，利用简单体素来构造 复杂的模型，模拟自然现象如火焰、水、雨、雪、草木等造型。 1 3 本文工作 本文研究目的是将层次细节技术应用于虚拟现实的各个方面，包括有网格层 次细节技术、粒子系统层次细节技术、动画和碰撞层次细节技术：同时结合层次 细节技术设计了高效的场景管理和动画碰撞机制。具体地，( 1 ) 提出了一般化的 网格层次细节处理框架并研究了框架中可以改进的一些算法，扩展了网格l o d 技术在虚拟现实中的实际应用。( 2 ) 提出一种建立层次细节模型的简化算法，该 算法简化操作参数可控，同时可以很好地保持网格拓扑结构。( 3 ) 研究了地型和 粒子系统模型的层次细节技术，提出了与视点相关的层次细节算法，充分地提高 了绘制的实时性。( 4 ) 提出对动画和碰撞层次细节技术，从而将静态数据层次细 节处理扩展到动态数据上。( 5 ) 构建了虚拟现实绘制系统，提出包括层次细节层 在内的七层系统结构。同时，结合层次细节技术设计了有效的复杂场景管理结构 北京工业大学工学硕士学位论文 和一般性的动画碰撞实现机制。( 6 ) 本文还提出了一种用关系数据库方式对虚拟 现实中场景数据进行管理的方法。 1 4 内容结构 第一章是绪论，概述了本文内容，总结了现状，整理了本文的创新点。第二 章是网格模型的层次细节技术研究，深入地研究了网格模型层次细节技术，讨论 了更为一般化的网格层次细节算法框架以及框架中可以扩展的一些算法，并介绍 了一个层次细节模型的简化算法。第三章是粒子系统的层次细节技术研究。介绍 了粒子系统的绘制原理，同时将层次细节技术应用到粒子系统中，提出了粒子系 统的层次细节系统框架。第四章是动画和碰撞的层次细节技术研究，将层次细节 技术扩展到了动画及碰撞处理过程中。第五章是虚拟现实绘制系统，结合层次细 节技术设计了有效的复杂场景管理结构和一般性动画碰撞的实现机制。同时还提 出了一种用关系数据库方式对虚拟现实中场景数据进行管理的方法。 第二章网格模型的层次细节技术研究 第二章网格模型的层次细节技术研究 层次细节( l e v e lo f d e t a i l s ，l o d ) 技术是实时渲染技术中一项重要的技术，它 存在于场景绘制的各个过程。广泛意义的层次细节包括：模型层次细节技术，动 画层次细节技术，碰撞层次细节技术等等。 其中模型层次细节指的是采用适当算法减少模型的点、边、面数据，使模型 存在着由简到繁、由粗到精的多种表示形式。在一定视点标准下，在特定取值下 选择特定的模型，在与原模型逼近的前提下，尽量减少表示该模型的多边形数目。 另外，在两个相邻层次的模型间会有一定的视觉过渡( 即几何形状过渡) 。 如上总结，模型层次细节简化技术的研究主要集中在下面两个方面： ( 1 ) 建立不同层次细节的模型，对给定的多边形网格m ，建立一个序列的模型： ( m o ，m l ，m 。) ，其中m o = m ； ( 2 ) 建立相邻层次多边形网格m 。，m h ( 0 i = t h r e s h o l d )如果屏幕投影面积火于阈值t h r e s h o l d j f ( p n o d e 是活动节点) f o r ( p n o d e 子节点p n o d e c h i l d _ i ) a d j u s t n o d e t r e e ( p n o d e c h i l di ) e l s e e x p a n d n o d e ( p n o d e ) ； e l s e i f ( p n o d e 是活动节点) c o l l a p s e n o d e ( p n o d e ) ； ) ( 4 ) 其它规则 ，如果p n o d e 是边界节点 折叠节点p n o d e 如果屏幕投影面积小于闽值t h r e s h o l d 合并节点p n o d e 北京工业大学工学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ! i i i ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ! ! ! 竺 模型限定顶点数目规则为了将多边形模型的顶点数目限定在规定的阁值中， 减少渲染时的负载：模型外形保持规则为了保持多边形模型外型，简化模型非边 界部分，减少渲染时的负载。 2 4 层次细节的系统实现及实验结果 j o n a t h a nc o h e n ，d a v i dl u e b k e 4 4 1 等人提出了一个几何层次细节驱动层的接口 标准g l o d ( g e o m e t r i cl e v e lo fd e t a i l ) ，g l o d 为实现模型l o d 提供了一些 专门的应用程序接口，这些接口提供了一个有效的，可扩展的，容易实现的l o d 系统应用框架，支持有静态的、连接的、视点相关的l o d ，支持多种简化算法 和多种视点相关规则。另外，g l o d 较好地结合了o p e n g l 的标准，易于实现和 便于改进。本文的系统算法框架的实现基于c l o d 平台。 g l o d 中定义了三类数据：片、物体、组。片用o p e n g l 中的顶点数组列表 来表示，是网格的初始数据结构，渲染状态不可改变。物体是进行动态l o d 管 理的基本数据结构。另外，应用程序可以将一个或多个物体组合成组数据进行 l o d 处理。对于每一帧，g l o d 根据指定的调节模式和当前o p e n g l 状态来调 整每一组中所有的物体的所有片的层次细节。下图是g l o d 的数据流图( 引自 ) ： t h eg l o do b j e c ta n dd a t a f l o wm o d e l 图2 1 3 ：g l o d 的流程图 f i g u r e2 - 1 3 ：t h ef l o wi l l u s t r a t i o no f g l o d g l o d 的操作过程是：首先以片的形式体现初始网格。然后通过设置一系列 的“g l o d 生成参数p a t c h o b j e c t p a r a m s ”控制l o d 的层次细节操作。其中这些 参数可以用来指定简化规则、简化误差、层次细节类型( 例如：离散型、动态型、 视点相关型) 、重要的属性取值等。网格层次细节预处理后生成多分辨率网格模 型。模型可以被应用程序保存到磁盘中，也可以被用在后续的l o d 管理步骤中。 在动态l o d 管理时，g l o d 中设置了“g l o d 管理参数g r o u pp a r a r n s ”来指定视 2 4 第二章网格模型的层次细节技术研究 点相关实时简化的规则。g l o d 管理参数可以设定误差规则( 物体空间误差或屏 幕空间误差) ，实时简化视点规则( 误差规则或三角形数目限定规则) 和功d 甲b j 增 参数等。简化后的当前视点下的多分辨率网格可以被写到磁盘中，也可以通过 o p e n g l 对其进行渲染。本章中的l o d 平台采用了g l o d 的模式并在g l o d 的框架中加入算法2 ，1 ，实验结果如下： ( a ) ( c ) 图2 1 4 ：模型l o d 的效果图 f i g u r e2 - t 4 ：t h ee f f e c ti l t u s t r a t i o no f m o d e ll o d 苎奎苫些查兰三兰罂圭兰兰兰兰 2 5 地形网格的层次细节应用 地形网格是特殊的网格模型，所以一般网格的l o d 算法一样可以应用到地 形网格中。本文结合核外存储技术和简易裁剪算法，提出针到地形的l o d 算法 框架： 简化参数lod 控制参数 锱l o d 型酉 动态管理l o d 模型 视区裁剪 窿立模型l 匕二jl l o d 简化处理 卜分块处理l 匕裂缝和块拼接处理 i l o d 预处理l 帧间相关技术应用 图2 - 1 5 ：地形模型l o d 的沉程图 f i g u r e2 - 1 5 ：t h ef l o wi l l u s t r a t i o no f t e r r a i nm o d e ll o d 地形网格的l o d 算法描述如下：地形网格模型通过“建立l o d 模型”步骤 形成地形l o d 网格模型。首先，对地形进行分块处理( 核外存储的需要) ，之后， 对每块地形数据进行l o d 预处理，生成地形l o d 网格模型。在“动态管理l o d 模型”的步骤中，首先，对地形网格模型进行视区裁剪、l o d 简化处理、裂缝 和块拼接处理、帧间相关技术应用等程序处理，然后形成当前视点下的地形网格 模型，最后由o p e n g l 等方式来绘制。 2 5 1 地形模型 常用到的地形模型数据格式有三种：数字高程模型( d e m ：d i g i t a le l e v a t i o n m o d e l ) 、规则三角形地形网格模型、不规则三角形地形网格模型( t i n ) 圈闺圈 ( 1 ) d e m( 2 ) 规则三角形地形网格模型 ( 3 ) t i n 图2 - 1 6 ：地形数据的格式示意图 f i g u r e2 - 1 6 ：t h ef o r m a ti l l u s t r a t i o no f t e r r a i nd a t a 三种地形格式中，d e m 地形格式最为规则，也是地形的最基本的采样格式 第二章网格模型的层次细节技术研究 其具有简单的空间关系，高程数值可以用矩阵表示，所以容易使用、管理和压缩。 但其缺点是不能准确地表示地形结构，细节部分不能突出表达。t i n 是基于不规 则三角形的地形网格模型，它是将地形的特征点按一定的规则建立起覆盖整个地 形区域且不重叠的三角形网格地形。t i n 可以准确地描述出地形地貌的特征，从 而可以表示出复杂的地形地貌。但它的缺点是数据结构复杂，管理和使用因为其 不规则而增加了很大的复杂性。规则三角形地形网格模型介于上两种模型数据之 间，数据规则且易于表示地形特征。因而此种数据格式被大量应用在地形实时显 示系统中。 三类地形数据格式可以结合简化和精化的算法进行相互之间的转化。特别 地，由于基于规整三角形网格模型在实时简化渲染时易于裁剪和l o d 简化，且 效率最高，所以本文的l o d 算法采用了基于规整网格的地形数据。 2 5 2 地形模型实时l o d 算法 根据地形数据输入的类型，分实时l o d 算法为两种：基于规则网格和基于 不规则三角网格。1 9 9 6 年l i n d s t r o m 3 6 i 首先第一次提出基于规则网格地形的实时 l o d 算法，算法基于顶点选择使用三角形进行自顶向下的二叉分割细分方法。 1 9 9 7 年d u c h a i n e a u y l 2 0 】提出r o a m ( r e a l t i m eo p t i m a la d a p t i v em e s h e s ) 算法对 l i n d s t r o m 算法做了改进，算法是基于三角形合并分裂操作，该算法成为目前应 用最广的算法之一。另外基于规则网格地形数据的实时渲染算法还有：1 9 9 8 年 r 6 t t g e r l 4 8 1 算法( 基于顶点选择) ，2 0 0 0 年j o n a h a n d 2 对r o a m 改进算法f 基于顶点 选择) ，赵友兵【5 6 】的快速漫游算法等等。第二类算法是基于不规则地形网格数据 的实时l o d 算法。1 9 9 8 年h o p p e l 3 0 1 在地形l o d 应用中引入了v d p m ( v i e w - d e p e n d e n tp r o g r e s s i v em e s h e s ) 算法。此算法通过对地形网格分块处理和 利用递进网格的简化处理( 即对顶点对收缩简化操作) 生成l o d 地形结构，在演 染中利用了视点位最信息来实时简化地形数据。另外，对一般网格的实时l o d 算法都可以应用到地形网格数据中。 本文结合上述算法提出了一个地形实时l o d 算法，对算法中的关键步骤分 析如下： f 1 ) 分块处理 地形的数据量往往很大，所以首先对地形进行分块处理。分块处理大大方便 了核外存储和纹理处理。目前的地形算法在处理大型地形时大多都采用了分块的 方法。经典的l i n d s t r o m 算法对地形进行了分块，每一块根据采样间距分成多个 细节层次。h o p p e 的v d p m 算法首先也是对地形进行了分块，对每块地形数据 都用累进网格预处理。 本文算法采用了均匀地形分块方法，例如对“h o p p e4 0 9 7 2 0 4 9 大峡谷”地形 数据分块成了2 5 6 + 1 2 8 个1 7 + 1 7 大小的块。对于各块地型的管理和调度采用 5 2 节中的内联节点技术。 f 2 ) l o d 预处理 l o d 预处理类似于“建立l o d 模型”过程。按照地形简化操作的不同基本上 可以分为：基于顶点选择、基于边折叠、基于三角形合并分裂的。其中：l i n d s t r o m 算法是基于顶点选择的，通过对三角形的二叉分割，自上向上进行顶点删除( 即 三角形合并) ，最终形成多分辨率地形模型。r 6 t t g e r 算法也是基于顶点选择的， 不同与l i n d s t r o m 算法，算法是自上而下地对地形模型进行简化预处理生成地形 多分辨率模型的。h o p p e 的v d p m 算法是基于边折叠操作从而生成地形的递进 网格的。d u c h a i n e a u y 的r o a m 算法对l i n d s t r o m 算法做了改进，算法通过建立 三角形二叉树结构，对三角形进行分裂与合并操作从而生成地形的连续l o d 模 型。 本文地形简化算法结合了上述方法，采用和改进了文献 5 6 提出的自上向 下、基于顶点选择的三角形四叉分割方法。文献【5 6 在进行三角形四叉分割时， 利用每条边的中点采样误差来判断边中点是否是可简化点，但由于地形复杂多变 化，在分割时会很容易漏掉一些本应该细化的边。本文对文献 5 6 算法进行了改 进：在三角形四叉分割中，判断三角形各边的点是否是可简化结点时，采用多点 采样误差判定。首先对三角形上的各边进行多点采样，如果任一采样点误差大于 阈值，则采样点所在边的中点即为可简化点。加入改进误差的算法，使得生成的 多分辨率地形模型更加准确，同时更加体现了四叉分割的优点。虽然该误差判定 一定程度上影响了算法的速度，但是由于自上向下方式体现的是由粗到细的特 点，所以这样的误差判定是合理的。 ( 3 ) 视区裁剪 第二章网格模型的层次细节技术研究 视区裁剪处理在已有的地形算法中占用了很多的时间。显然，由于地形的 x z 平面特殊性，对于地形数据的视见体投影完全可以简化为投影到x z 平面上。 本文采用简化的x z 平面裁剪处理，较大地提高了实时简化的速度。 ( 4 ) l o d 简化处理 基于l o d 预处理生成的地形多分辨率模型，根据视点来实时简化处理。简 化处理也可分为自上向下和自下向上的方法。类似于一般网格的“管理l o d 模 型”算法内容。l i n d s t r o m 第一次提出了屏幕空间误差控制方法应用到了地形网格 数据中。本文使用的就是这样屏幕空间误差控制的方法。 ( 5 ) 裂缝和块拼接处理 地形中存在多个不同层次细节，裂缝是由于不同层次细节而产生的，同时如 果对地形进行了分块，则还需要考虑块与块之间的拼接问题。l i n d s t r o m 通过保 持顶点间依赖关系来消除不同细节层次间的裂缝。l i n d s t o m 的最新改进算法使用 了顶点单调误差规则，所以不会产生裂缝。r 6 t t g e r 算法使用控制边界细节的方 法使相邻节点间的层次差别不超过一层，从而消除了裂缝。赵友兵的快速漫游算 法放弃了惯用的重新部分三角形的方法，能过改变引起裂缝的顶点调度值，允许 “t 型节”存在，从而实现不同细节层次间的无缝拼接和块与块之间的拼接处理。 l i n d s t r o m 算法和v d p m 算法都是通过共享边界顶点来实现无缝拼接的，从而避 免了块与块之间的裂缝。本文算法使用文献 5 6 的裂缝消除方法。 ( 6 ) 帧间相关技术应用 利用上一帧的层次细节信息，避免重新操作多分辨率模型。本文增加了“细 分点集”辅助存储结构，用来保存前一帧的所有可见顶点，当进入下一帧时，对 这些“细分点集”进行判断操作( 或分裂或折叠) ，并修改“细分点集”结构。 综上所述，算法从六个方面到地形l o d 进行实现，同时改进了文献 5 6 算法 中是对三条边的中点误差值判定方法，使得生成的地形多分辨率模型更加准确、 逼真。该地形l o d 算法对“h o p p e 4 0 9 7 2 0 4 9 大峡谷”地形数据( 三角形数为5 7 8 0 ) 进行了实时渲染，结果如下： j ! 奎三兰查兰三兰登圭兰鳘兰兰一 2 6 小结 图2 - 1 7 ：地型模型l o d 的效果图 f i g u r e2 - 1 7 ：t h ee f f e c ti l l u s t r a t i o no f t e r r a i nm o d e ll o d 本章对网格模型层次细节技术做深入的研究和应用。借鉴g l o d 的流程和当 前已有的l o d 算法，本文提出了更为一般化的l o d 算法框架，同时基于该框 架，设计了一个采用点聚集网格简化规则和点到平面距离误差度量策略的简化算 法，很好地实现了网格的简化操作。本章的实现采用了d a v i dl u e b k e ，j o n a t h a n c o h e n 等人提出的几何层次细节驱动层的接口标准o l o d 并对它进行了扩展应 用。另外，本章还介绍了一个实现地形网格层次细节的改进算法。总之，网格模 型层次细节技术是实现复杂场景实时渲染的最重要技术之一，该技术也必将被应 用到图形的各个领域。 第三章粒子系统的层次细节技术研究 第三章粒子系统的层次细节技术研究 针到粒子系统，本文提出了一种实时渲染技术即粒子系统视点层次细节 ( l o d o f p a r t i c l es y s t e m ) 技术。具体地，系统根据当前视点的参数( 如位置、 方向等) 不断地调整渲染策略，从而使粒子系统形成多分辨率的体现，渲染时尽 可能达到真实性和实时性的平衡，同时减少相邻分辨率形式间的视觉过渡。通过 层次细节处理后的拥有大量粒子模型数据和动画数据的粒子系统可以被实时地 渲染在整个场景中，从而达到理想的渲染效果。粒子系统层次细节技术结合了静 态l o d 和动态l o d 两种方法，视点标准更加简易。 3 1 概述 粒子系统是一种过程模型，利用了各种计算过程生成模型和各个体素的各个 过程。一个粒子系统由大量的简单体素粒子构成。每一粒子有其自己的属性：位 置、大小、形状、颜色、纹理、速度、加速度、时间、生命期等等属性。大量的 粒子生成于某些粒子源，属性初值随机产生，之后由指定的物理或生理模型来控 制粒子的运动。粒子系统的工作原理如下：粒子系统随机生成大量简单粒子，同 时随时间的推移，对已有粒子不断更新，而且不断有新的粒子加入，为了模拟生 长过程，每个粒子被赋予自己的生命周期( 新生、成长、衰弱、死亡) ，这个过 程中为了描述景物的随机性，对粒子的每一个参数均将受到一个随机过程的控 制。粒子系统的每- n 都要进行如下步骤操作：( 1 ) 粒子源根据物理或生理模型 生成粒子；( 2 ) 更新粒子属性，同时删除生命周期结束的粒子；( 3 ) 绘制粒子系 统。 3 2 粒子系统层次细节技术 由粒子系统工作原理可以总结出来粒子系统的优点和缺点。优点是：( 1 ) 灵 活性：利用由大量简单构造的粒子构成的粒子系统可以生成复杂的自然景物，使 得复杂模型行为和简单体元素有机地结合在一来。( 2 ) 易实现：通过对粒子系统 的随机过程做出设置就以可定义出个粒子系统，同时简单的粒子易于图形显示 j ! 奎三= ：! ：查主三主罂圭兰箸兰吝 且效率较高。缺点是：( 1 ) 开销大：粒子进行动态属性更新时，计算开销很大。 ( 2 ) 造型简：粒子系统中粒子必尽使用的是简单的造型，所以构造的物体范围 有限。 本文将层次细节技术应用到了粒子系统中。粒子系统通过数据加载、数据优 化后进行粒子系统数据管理。主要思想是在粒子系统渲染前加入l o d 控制，从 而实现对粒子系统的层次细节控制。l o d 的控制方式分为静态方式和动态方式。 ( 1 ) 静态方式是预先建立粒子系统的多个层次细节，然后根据视点位置来选取 适当的细节。 ( 2 ) 动态方式是根据视点位置按照粒子l o d 规则动态地决定粒子系统的层次细 节。粒子系统l o d 规则采用类似于网格的视点相关规则( 距离规则、粒子数目 限定规则、形状规则、纹理规则等) ，不同与网格模型，粒子系统中粒子间没有 空间拓扑关系信息，所以需要修正层次细节技术应用后出现的异常情况。这里的 动态性体现在粒子系统l o d 规则不断更新上，在绘制过程时粒子系统会定时统 计层次细节的分布状态，然后动态更新l o d 规则。 本文提出的粒子系统实时绘制的系统框架如下图所示： 图3 - 1 ：粒子系统l o d 的系统框架示意图 f i g u r e3 - 1 ：t h es y s t e mf r a m e w o r