（计算机应用技术专业论文）虚拟现实中三维复杂模型简化技术研究.pdf

上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 摘要 模型简化是计算机图形学和虚拟现实的一个核心内容，主要研究在计算机图 形系统环境中对模型的表示、设计和显示。它在处理中需要进行复杂的计算，并 且消耗大量的计算机资源。而且，由于计算机图形显示对于真实性、实时性和交 互性要求日益增强，图形工业迈向一体化、集成化和网络化步伐也不断加快，寻 求快速的模型简化技术一直是研究的热点。 以几何元素删除实现模型的简化是多细节层次模型自动生成的常用方法。但 由于复杂模型庞大的数据量以及模型简化复杂的计算，使得以往的l o d 模型生 成方法只能预先产生多个离散的简化模型，从而引起实时绘制时图形画面的跳 跃。为解决这个问题，人们相继提出了渐进网格模型概念以及三维复杂模型的实 时连续的多分辨率绘制技术。这种模型简化方法在快速生成模型和实时显示方面 具有很大的优势。本文提出一种新颖的基于包络和三角形折叠的渐进网格生成方 法和表示形式。在模型简化的整体效果方面，算法使用包络来控制模型简化的全 局误差，保证了简化的整体特征。在生成包络时，本文提出了一种改进的方法来 代替通用的数值计算方法，以提高包络的生成效率。在模型简化的局部效果方面， 本文提出了三角形折叠和误差矩阵来共同控制模型简化的局部误差的方法，简化 的速度比通常的边折叠方法和顶点删除方法更快，对简化过程中产生的空洞的三 角化效果更好，使模型的局部特征得到很好的保持。在误差矩阵的设计中，算法 能方便地加入颜色、纹理等属性因子，能保证在简化过程中模型的颜色、纹理等 属性不失真。在简化过程中算法已录下整个模型简化过程中三角形删除的信息， 并利用三角形删除与模型面片个数的对应关系，建立起渐进网格的表示形式。利 用这种渐进网格表示形式我们实现了三维复杂模型的实时连续多分辨率绘制。该 算法既能用于生成离散的l o d 模型，又能用于生成连续的渐进网格。本算法的 一个重要特点是可以根据当前视点参数产生连续的多分辨率近似模型，使得被绘 制的三角网格模型的面片数目随视点的位黄改变而产生连续的变化。 本文对下一步的工作进行了分析并且考虑从性能的优化等方面作进一步的 改进。本文的成果对工业产品原型设计、计算机动画和虚拟现实技术中所需的形 体表示等图形学与可视化研究方面的问题有一定的理论和实用参考价值。 关键词：虚拟现实、计算机图形学、 多分辨率绘制、渐进网格、 细节层次模型、网格模型简化、实时连续 二次误差矩阵、包络、三角形折叠 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y a b s t r a c t m o d e ls i m p l i f i c a t i o ni sac o r er e s e a r c ha r e ai nc o m p u t e rg r a p h i c sa n d c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，w h i c hm a i n l yf o c u s e so nr e p r e s e n ti n g ， d e s i g n i n g ，r e n d e r i n gi nac o m p u t e r o r i e n t e di m a g es y s t e m l a r g ea m o u n t o fc o m p l i c a t e dc o m p u t a t i o ni sn e c e s s a r yd u r i n gt h ep r o c e s so fg e o m e t r i c m o d e l i n ga n dag r e a td e a lo fr e s o u r c eo fc o m p u t e rs y s t e mi s i ng r e a tn e e d ， t o o f u r t h e r m o r e ，d u et ot h e i n c r e a s i n g r e a lis t i c ，r e a l t i m ea n d i n t e r a c t i v ed e m a n di nr e n d e r i n gc o m p u t e rg r a p h sa n dt h eh i g hd e v e l o p m e n t o fg r a p h i c a li n d u s t r yt o w a r d si n t e g r a t i o na n dn e t w o r k o r i e n t a t i o n ，t h e s e a r c hf o raf a s tm o d e ls i m p l i f i c a t i o nm e t h o di sa l w a y sah o tp o i n t s i m p l i f i c a t i o no ft h eo r i g i n a lc o m p l e xm e s hb a s e do nd e l e t i n gb a s i c g e o m e t r i ce l e m e n t ，s u c ha sv e r t i c e sa n de d g e s ，i so n eo ft h em e t h o d st o c r e a t em o d e l sa tm u l t i p l el e v e lo fd e t a i l b e c a u s et h ee x t r e m ec o m p l e x i t y o fo r i g i n a lm o d e la n dt h ee x p e n s i v ec o m p u t a t i o no fs i m p li f y i n gp r o c e s s ， s o m ek e ym o d e l sa td i f f e r e n tl e v e lo fd e t a i la r eg e n e r a t e di na d v a n c ea n d s t o r e df o rr e n d e r i n g ，w h i c hr e s u l ti no b j e c t i o n a b l ev i s u a l “p o p p i n g ” e f f e c tw h e nc h a n g i n gb e t w e e nm o d e l sa td i f f e r e n tl e v e lo fd e t a i1 i n r e n d e r i n g ，i no r d e rt os o l v et h i sp r o b l e m ，t h ec o n c e p to fp r o g r e s s i v e m e s h ( p m ) a n dm e t h o do fr e a l t i m e ，m u l t i r e s o l u t i o nm o d e l i n ga n dr e n d e r i n g o f3 dc o m p l e xv i r t u a le n v i r o n m e n ta r ep r o p o s e d t h i sk i n do f s i m p li f i c a t i o nm e t h o dh a sm a n ya d v a n t a g e si nf a s tg e n e r a t i o no fm o d e la n d r e a l t 】m er e n d e r i n g h e r e ，w ep r e s e n tan o v e lp r o g r e s s i v em e s hg e n e r a t i o n m e t h o db a s e do ne n v e l o p e sa n dq u a d r i ce r r o rm e t r i c s t oe n s u r et h eg l o b e e f f e c to fs i m p li f i c a t i o n ，w eu s ee n v e l o p e st oc o n t r o lt h eg l o b ee r r o r f o rt h es a k eo fr a i s i n gt h es p e e do fe n v e l o p e s c o n s t r u c t i o n ，a ni m p r o v e d m e t h o di sp r o p o s e dt or e p l a c et h eh u m e r i cc o m p u t i n gm o t h o d t h i sm e t h o d ， w h i c hp r o v i d e st r i a n g l ec o l l a p s e sa n dq u a d r i ce r r o rm e t r i c st oc o n t r o l t h el o c a le r r o ro fs i m p l i f i c a t i o n ，i sf a s t e rt h a nt h em e t h o dd e l e t i n g v e r t i c e sa n de d g e s ，a n db e t t e ri nt h el o c a le r r o l i no r d e rt ok e e pt h e m o d e l sp r o p e r t i e s ( s u c ha sc o l o ra n dt e x t u r e ) ，t h ep a r a m e t e r sc a nb e c o n v e n i e n t l ya d d e di n t ot h em e t r i c s a st h ei n i t i a lm e s hi ss i m d l i f i e d i n t oac o a r s em e s hb ya p p l y i n gas e q u e n c eo fs u c c e s s i v et r i a n g l er e m o v a l 。 as e q h e n c eo fd e t a i lr e c o r d st h a ti n d i c a t eh o wt oi n c r e m e n t a l l yr e f i n e t h ec o a r s em e s he x a c t l yb a c k i n t ot h eo r i g i h a lm e s hi ss t o r e d u s jn gt h e 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y r e l a t i o n s h i pb e t w e e nt h en u m b e ro fm e s hf a c e sa n dt h e n u m b e ro ft r i a n g l e s r e m 。v e d ，t h en e w 洲r e p r e s e n t a t i o n i s g o t a n dan e wa l g o r i t h mf o r g e n e r a t i n gc o n t i n u o u sl e v e l so fd e t a i l o fag i v e nt r i a n g l eo b j e c t i n r e a l t i m ei sp r o p o s e d t h i sm e t h o dc a nb eu s e de i t h e ri nt h eg e n e r a t i o n o fm o d e l sa td i f f e r e n tl e v e l o fd e t a i l ，o ri nt h ec o n s t r u c t i o n o f c o n t i n u o u sp m o n eo ft h ei m p o r t a n tf e a t u r e s i st h a tt h ec e n t l n u o u s a p p r o x i m a t em u l t i r e s o l u t i o nm o d e l c a nb eg e n e r a t e da c c o r d i n gt ot h e c u t r e n tv i e wp o i n t ，t h u st h en u m b e ro ft r i a n g l em e s h sf a c eb e e np r e s e n t e d c a nb ec o u t i n o u sc h a n g e db yt h ec h a n g eo f t h ev i e wp o i n t sp o s i t i o n f i n a l l y ，t h ep a p e ra l s om a k e sat h o r o u g ha n a l y s i sf r o mt h ev i e wo f t h ep e r f o r m a n c eo p t i m i z a t i o n t h er e s u l to ft h i sp a p e ri s s o m eu s e f u li n b o t ht h e o r ya n dp r a c t i c ef o rt h ea p p l i c a t i o n ss u c ha si n d u s t r i a lp r o t o t y p e d e s i g n ，c o m p u t e r a n i m a t i o n ，v i r t u a lr e a l i t y ，v i s u a l i z a t i o n ，s h a p e r e p r e s e n t a t io n ，a n ds oo n k e yw o r d s ：v i r t u a l r e a l i t y ，c g ( c o m p u t e rg r a p h i c s ) ，l e v e l m o d e l ( c o d ) ，s i m p l i f i c a t i o n o fm e s hm o d e l o fd e t a i l r e a l t l m e c o n t i n u o u sm u l t i r e s o l u t i o nr e n d e r i n g ，p r o g r e s s i v em e s h ( p m ) q u a d r i ce r r o rm e t r i c s 、e n v e l o p e s ，t r i a n l g ec o l l a p e s i i - 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名：亟! ! 堡日期趔：理：缉 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容。 ( 保密的论文在解密后应遵守此规定) 签名：姐 导师签名：j 右高 日期：砧硝，口弓群 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 第1 章绪论 本章是全文的一个开始，主要是对虚拟现实中的模型简化这样一个在计算机 图形学中的一个分支的历史、发展状况和特点作了一个比较全面的概括性综述。 作为后续章节的起始部分，本章的最后一节对全文的各章节的安排和组织结构作 了介绍。 1 1 虚拟现实概况 虚拟现实( v i r t u a lr e a l i t y ，简称v r ) 是一种新的人一机界面，它为用户( 参与 者) 提供了一种具有临场感和多感觉通道的体验，试图寻求一种最佳的人一机通 讯方式。虚拟现实也被称为人工现实( a r t i f i c i a lr e a l i t y ) 、电脑空 自j ( c y b e r s p a c e ) 、 人工合成环境( s y n t h e t i ce n v i r o n m e n t ) 、虚拟环境( v i r t u a le n v i r o n m e n t ，简称v e ) 。 v r 技术是一种高度逼真地模拟人在自然环境中视、听、动等行为的人机界 面技术。这种模拟具有两种基本特征，即“沉浸”特征和“交互”特征。v r 的 “沉浸”特征要求计算机所创建的三维虚拟环境能使“参与者”得到全身心置于 该环境之中的体验。v r 的“交互”特性主要是指参与者通过使用专用设备实现 用人类自然技能对虚拟环境中的实体进行交互考察与操作。因此，v r 技术将从 根本上改变人与计算机系统的交互操作方式。 v r 技术并非最近几年才出现，它的起源要追溯到计算机图形学之父i v a n s u t h e r l a n d 于1 9 6 5 年在i f i p 会议所作的标题为“t h eu l t i m a t ed i s p l a y ”的报告。 在该报告中，i v a ns u t h e d a n d 提出了一项富有挑战性的计算机图形学研究课题。 他指出，人们可以把显示屏当作一个窗口来观察一个虚拟世界。其挑战性在于窗 口中的图像必须看起来真实，听起来真实，而且其中物体的行为也很真实。这一 思想奠定了v r 研究的基础。1 9 6 8 年，i v a ns u t h e r l a n d 发表了题为“a h e a d m o u n t e d3 dd i s p l a y ”的论文，对头盔式三维显示装置的设计要求、构造 原理进行了深入的讨论。s u t h e r l a n d 还给出了这种头盔式显示装嚣的设计原型， 成为三维立体显示技术的奠基性成果。 v r 研究的进展从六十年代到八十年代中期是十分缓慢的。直到八十年代后 期，v r 技术才得以加速发展。这是因为显示技术已能满足视觉耦合系统的性能 要求，液晶显示( l c d ) 技术的发展使得生产廉价的头盔式显示器成为可能。 v r 系统的最大特点就是参与者能与计算机生成的虚拟环境进行自然的交 互，能用人类自然的技能与感知能力与虚拟世界中的对象进行交互作用。设想这 样一个虚拟现实系统的情景：用户在戴上头盔显示器和数据手套后，不仅可以看 第1 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 到一个排球，而且还可以摸到它，并能得到触觉反馈。用户还可以拍动排球，拍 球的时候，不仅能感受到排球对手的反作用力，还能听到拍球时发出的“嘭嘭” 声，这将会令人产生多么真实的感受。与传统的人一机界面系统相比，虚拟现实 的沉浸式交互技术是一种全新的人机交互风范。在传统的人一机系统中，用户是 一个外部的观察者，只是通过显示屏这个范围很有限的小窗口，观察计算机内的 合成环境，而v r 系统则是要用户参与到这个合成环境中。传统的进行人一机交 互最常用的设备是键盘和二维鼠标，人们通过它们与合成环境中的物体进行通 讯，这与我们在自然世界中的通讯方式相距甚远。 为了使用户产生身临其境的感觉，v r 系统必须具备一些不同于传统人机 系统的交互技术。这些能使人身临其境的交互技术主要有：大视角的立体显示、 头部跟踪、人及姿势跟踪、三维声音、触觉反馈和力反馈等技术。目前，实现这 些交互技术的设备主要有：头盔显示器、数据手套、三维位置传感器和三维声音 产生器等。 v r 系统可分为三大类：桌面v r 系统、沉浸式v r 系统和分布式v r 系统。 桌面v r 由于采用标准的c r t 显示器和立体显示技术，其分辨率较高，价格较 便宜。在使用时，桌面v r 系统设定一个虚拟观察者的位置。桌面v r 系统通常 用于工程c a d 、建筑设计以及某些医疗应用。沉浸式v r 系统利用头盔显示器 把用户的视觉、听觉和其它感觉封闭起来，产生一种身在虚拟环境中的错觉。分 布式v r 系统则是在沉浸式v r 系统的基础上将不同的用户通过网络联结在一 起，共享同一个虚拟空间，使用户达到一个更高的境界。 很早以前，人们已- 丌始设想用种新设备来产生能替代真实环境体验的新机 器，但早期的v r 系统与计算机并无多大关系，只有到计算机技术比较成熟的今 天，才使虚拟现实成为现实。 v r 技术在各行各业的应用具有很大的潜力和十分广阔的前景。下面介绍v r 已有的一些应用成果。 f 1 ) 医疗和康复 近年来，计算机在医学界的广泛应用( 如病人数据库、手术模拟、远程咨询、 数字化x 射线照片、专家系统等) ，改变了人们医疗和康复的模式，特别是v r 技术在医疗和康复中的应用，将根本改变这一方式。 ( 2 ) 娱乐、艺术和教学 在v r 技术发展的早期，娱乐是v r 技术发展的主要和直接推动力，而现在 又成了v r 系统的主要市场之一。在公共场所获得成功的v r 游戏项目有：世界 上第一个大型v r 娱乐系统b a t t l et e c h 中心，娱乐中心于1 9 9 0 年在芝加哥开张， 可供数十人共同玩战争游戏。此外，还有h u g h e s 飞机公司和l u c a s a r t s 娱乐公司 等丌发的m i r a g ev r 模拟器。w i n d u s t r i e s 有限公司于1 9 9 1 年开发了世界上第一 第2 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 个采用头盔显示器的娱乐系统，称为v i r u a t i l ys y s t e m ，并获1 9 9 2 年v r 产品奖。 v r 技术在未来的艺术领域将扮演重要的角色。它作为一种新的媒体不仅能 变静态艺术为动态艺术，而且将成为联结艺术创作者与欣赏者的重要纽带。目前， 与艺术有关的应用系统有：v i d e o p l a c e 、m a n d a l e 、虚拟演员( v i r t u a la c t o r s ) 、虚 拟博物馆( t h ev i r t u a lm u s e u m ) 、虚拟音乐( v i r t u a lm u s i c ) 等。 v r 技术在教育领域特别是在中小学教育中的作用，目前尚处于研究证实阶 段，但其前景是十分诱人的。由l o f f i n 及其同事开发的虚拟物理实验室，是一个 用于演示牛顿力学及量子物理有关定律的虚拟实验教学系统。 f 3 ) 军事和航空航天 在军事和航空航天领域，模拟和训练特别重要。随着当今技术的高度复杂化， 硬件系统的开发周期不断缩短，迫切需要一种灵活的、可升级的、网络化的模拟 系统。v r 技术在上述各个方面均能很好地满足这一需要。因此，美国政府充分 认识到v r 技术在保持美国技术领先方面具有的战略意义，并制定了系列的实 施计划。其中应用于军事方面的v r 系统有： f 4 ) 商业应用 v r 技术在商业领域最早也是最成功的应用是产品广告宣传。v r 广告比传 统广告更易于制作和更改，也更具有感染力。由此，许多公司已认识到率先使用 v r 技术可使他们的产品领导潮流。 f 5 1 自动控制和制造业 v r 技术一旦全面应用于自动控制和制造业，必将产生巨大的经济效益。但 是由于该领域固有的技术复杂性，v r 技术在这一领域的应用仍处于早期的研究 和开发阶段， 在制造业领域，v r 技术可能将零星替代并超过目前广泛使用的c a d 系统。 它可将产品需求分析、时间成本分析和产品设计，甚至将相应的生产线设计集成 在一起，以进一步缩短新产品的研制开发周期，降低成本。特别是对于产品定制 和售后服务，v r 技术的应用具有更大的优势。 就目前计算机图形学水平而言，只要有足够的计算时间，就能生成准确的象 照片一样的计算机图像。但v r 系统要求的是实时图形生成，由于时间的限制， 使我们不得不降低虚拟环境的几何复杂度和图像质量，或采用其它技术( 如纹理 映射) 来提高虚拟环境的逼真程度。 所谓实时显示，是指当用户的视点变化时，图形显示速度必须跟上视点的改 变速度，否则就会产生迟滞现象，要消除迟滞现象，计算机每秒钟必须生成1 0 帧到2 0 帧图象，当场景很简单时，例如仅有几百个多边形，要实现实时显示并 不困难，但是，为了得到逼真的显示效果，场景中往往有上万个多边形，有时多 达几百万个多边形。此外，系统往往还要对场景进行光照明处理、反混淆处理及 第3 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 纹理处理等等，这就对实时显示提出了很高的要求。 就图形学发展而言，起关键作用的无疑是图形硬件加速器的发展。高性能的 图形工作站和高度并行的图形处理硬件与软件体系结构是实现图形实时生成的 一个重要途径。然而应用模型的复杂程度往往超过当前图形工作站的实时处理能 力，考虑到v r 对场景复杂度几乎无限制的要求，在v r 高质量图形的实时生成 要求下，如何从软件着手，减少图形画面的复杂度，已成为v r 中图形生成的主 要目标。 要提高图形显示速度，一个实践证明非常有效的方法是降低场景的复杂度， 即降低图形系统需处理的多边形数目。目前，比较常用的方法有下面几种： 预测计算：该方法根据各种运动的速率和加速度，如人体头部转动 速度，用预测、外推法在下一帧画面绘制之前估箅出头部跟踪系统 及其它输入设备的输入，从而减少由输入设备所带来的延迟。 脱机计算：由于v r 系统是一个多任务的模拟系统，所以有必要尽可 能地将一些可预先计算好的结果预先计算并存储在相应的结构中， 其中包括全局光照模型、动态模型的计算等。 场景分块：一个复杂的场景可被划分成多个子场景，各子场景之间 几乎不可见或完全不可见。例如把一个建筑物按房间划分成多个子 部分。此时，观察者在某个房间仅能看到房内的场景及与门口、窗 户等相连的其它房间，这样，系统就能有效地减少在任一时刻需显 示的多边形数目，从而有效地降低了场景复杂度。但是，这种方法 对封闭空间有效，对开放空间则很难使用这种方法。 可见消隐：与场景分块方法不同，这种方法与用户的视点关系密切， 而前者仅与用户所处场景位置有关。使用这种方法，系统仅显示用 户当前能“看见”的场景，当用户仅能看到场景的很少一部分时， 由于系统仅显示相应场景，从而大大减少了需显示的多边形的数目。 然而，当用户能“看见”的场景较复杂时，这种方法也不起作用。 细节层次模型：即使采用了场景分块技术及可见消隐技术，有时用 户能“看见”的场景仍很复杂，为此细节层次( l e v e lo fd e t a i l ，简称 l o d ) 模型方法应运而生。所谓l o d 模型方法，即为每个物体建立 多个相似的模型，不同模型对物体的细节描述不同，对物体细节的 描述越精确，模型也越复杂。根据物体在屏幕上所占区域大小及用 户视点等因素，为各物体选择不同的l o d 模型，从而减少需显示的 多边形数目。这是一种有前途的方法，然而，这种方法对场景模型 的描述及维护提出了较高的要求。 比较以上几种方法，前面几种方法仅适用于某些特殊的情况，而l o d 模型 第4 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 方法则具有普适性。l o d 算法最大的特征是利用人的视觉特征，以最小的图形 绘制开销取得最好的图形画面视觉效果，删除那些视觉分辨不出的图形细节。如 何利用人的视觉特点最大程度减化模型，减轻图形系统的负载仍是一个待解决的 问题。现在，l o d 模型的自动生成和绘制技术己成为一个很有前途的研究方向， 受到了全世界范围内相关研究人员的重视。 图1 1l o d 模型 1 2 模型简化方法在虚拟现实中的应用前景 模型简化算法是指将一个模型表示为由较少几何元素构成的原模型的近似 模型的方法。即在图形绘制中根据模型在屏幕上的覆盖象素的多少，选择相应的 细节层次，使得对近物体的绘制使用比较精细的模型，而远物体则选择比较粗糙 的模型。其目的在于保证对原模型良好的形状逼近的前提下尽量减少用于表示该 模型的三角形数目。我们可以将这一过程描述为：输入模型的原始三角网格数据 ( 可以包含模型的各项性质，如几何性质、表面性质、颜色、纹理、法向量等) ， 利用模型简化的方法自动产主多层次细节( l e v e lo f d e t a i l ) ，在进行绘制或其它 处理时根据需要对模型的不同部分用不同的细节精度加以描述，使最后的结果图 像与用最精细模型的绘制结果误差在一定范围内。在生成模型多分辨率表示时， 通常有两种约束条件，即多边形数目约束和简化误差约束，前者通常与保持固定 帧速率的需求有夫，而后者则用于保证满意的绘制质量。 模型简化的实质就是网格简化( m e s hs i m p l i f i c a t i o n ) ，网格简化是在保持显 示速度或计算精度最佳的前提下，相应地删去模型中平坦区域内的顶点或三角 第5 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 形，然后对删去顶点或三角形留下的空洞重新进行局部三角剖分。实际场景中模 型的复杂性往往超过计算机能进行处理的能力，为了在计算机中以较少的时倒及 较高的图像质量绘制出复杂的模型，我们经常要对某些给定的网格模型进行简化 以达到我们的要求。网格剖分一般会对最大化最小角原则或最小权( 总长度最小) 剖分原则产生影响，不合理的剖分可能会对计算结果精度和显示速度有影响，所 以有时要求对网格优化。 留留 图1 2 网格简化 在采用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 r 丌发 系统都开始支持l o d 模型表示。 1 3 本论文的工作以及论文的组织 虚拟现实这一研究课题，难度大，实用性强，要使v r 技术真征实用化，会 涉及到人工智能、人机接口技术、传感技术以及高度并行的实时计算技术，还耍 借助于视觉生理学和心理学的最新研究结果。图形的实时生成是v r 成为现实的 关键技术之一，而l o d 模型技术则是达到图形实时生成一种有前途的技术。 第6 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 本论文对l o d 模型的自动生成和绘制技术进行了深入的研究和探索，本文 在内容上的安排如下： 本文的第一章v r 的基本概念、重要特点以及v r 系统的分类和应用领域。 并简要介绍了模型简化技术在虚拟现实中的作用。给出了v r 中实现图形实时生 成的有关方法，指出了l o d 模型是一种有前途的关键技术。同时阐明了虚拟现 实中l o d 模型自动生成和绘制技术的研究内容和应用价值，最后给出论文的组 织方式。 本文的第二章对模型简化的基本原理进行了详细的阐述。根据模型简化方法 的特点对各种模型简化方法进行了详细的分类，然后详细的介绍了几种典型的简 化方法。 本文的第三章对l o d 模型简化方法展开研究，提出了一种结合包络和三角 形折叠的新颖的连续多分辨率渐进网格生成方法，并对它的原理进行了详细的讲 解。 本文的第四章对第三章给出的算法进行实现。给出了算法的数据结构的设 计，基于j a v a3 d 的编程实现和实验结果，并对实验结果进行分析和评估。 本文的第五章中，对工作做了总结，并对下一步的工作做了展望。 第7 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 第2 章国内外模型简化技术研究现况 虚拟现实中的图形要实时生成，以便能进行交互式的控制、观察和操纵。然 而，图形工作站能实时处理的多边形数日是有限的，实际的场景复杂性往往超过 图形工作站进行实时绘制的能力，于是采用各种各样的技术来解决这个矛盾。随 着人们对模型简化方法研究的深入，各种算法层出不穷，其中细节层次技术就是 一种很有效、也是一种很有前途的技术，可望解决虚拟现实中图形实时生成的问 题。为了对己有算法有一个比较全面的认识，在这里我们有必要对它们进行系统 的归纳和总结。在本章中我们首先给出模型简化算法通常需考虑的若干问题，接 着对当前存在的各种算法进行系统的分类并加以详细介绍。本章主要针对计算机 自动生成多分辨率模型的方法进行讨论，而不包括早期算法巾所用的人工建立多 分辨率模型的方法。 2 1 模型简化的基本原理 在计算机图形学和几何造型中，图形常常用三角形网格来表示。随着激光 扫描设各和系统的进展，表示物体( 或场景) 的三角形网格变得越来越复杂，通 常包含几万，十万、甚至上百万个三角形面片，这样庞大的网格在储存、传送及 绘制时都是很不经济的，也难于进行必要的编辑处理。特别是在虚拟现实中图形 必须以实叫的速度进行绘制( 最小为每秒1 2 帧) ，否则，用户就不会有真实的体 验。因此，如何有效地简化场景便应运而生。模型简化就是根据模型中的几何与 拓扑信息，在保持视觉效果最佳的前提下，相应地删去模型中平坦区域内的顶点 或三角形，然后对删去顶点或三角形留下的空洞进行周部三角剖分。而平坦区域 的判定可以通过相邻三角形的法向量，或根掘顶点到局部近似平均平面的距离来 判定，或根据三角形的曲率计算来判定。在模型简化过程中，简化模犁可以保持 原模型的拓扑结构，也可以改变原模型的拓扑结构。这可以根据实际需要来决定， 每种方法都有自己的优缺点，适应不同的应用场合与需要。 每种方法都有自己的优缺点，适应不同的应用场台与需要。 第8 负 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 2 2 几何元素重要度及折叠误差 简化算法在对三角形或者边进行折叠操作之前要确定模型中哪些三角形或 右边要被折叠，而哪些不折叠。这时就要对模型中每个三角形或者每条边的重要 性进行度量。之后有两种判断取舍的方式：一种是设定一个重要性闽值，把每一 个三角形或者边的重要性与之比较，保留达到重要性阈值的三角形或者边；另一 种是把三角形或边按照其重要程度排序，接着给定一个简化模型的三角形个数， 或者顶点数( 因为边折叠每一次都是减少一个顶点) ，然后将顺序排在该值之后 的三角形或者边折叠掉。值得注意的是这里所说的重要性一般情况下只具有相对 意义。就是说在不同的场合，某一三角形或者边的重要性是可以不同的( 比如有 时候注重曲率，有时候注重边长) 。 无论是三角形折叠还是边折叠，最终都相当于把一些顶点合并到同一个顶 点，从数学意义上看，都相当于把一些点的坐标用一个新的坐标代替，这个新的 坐标就是折叠点的坐标。在折叠过程中折叠点的坐标是由折叠误差所确定的，一 般总是通过使折叠误差最小来确定折叠点的坐标。 2 2 1 局部判断准则 局部判断准则是模型简化的依据，土要有以下的两种：曲率标准、平坦性标 准。曲率标准考虑的是顶点的向量与相邻边的夹角关系，平坦性标准考虑的是顶 点与相邻面片的关系。 ( i ) 曲率标准 在图形学中，曲率一般是对曲线而言。其公式为： 其中k 是曲率，是曲线弧度参数，x ，y ，z 以f 为参数构成曲线方程。 而在三角形面片模型中，并没有真正的曲线。模型中的顶点其实是处在由线 段组成的折线上。度量这些折线的总体弯曲效果有若干方式，这里采用近似和类 比的方法。先考察二维折线的情况，如下图： 第9 页 汁川 生扩 r l “1j坐扩 r 叫l 0 1 j 生扩 叫 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 显然。角在。一，。度范围内变化时，。越小，即i 增引越小，b 点弯曲程度 就越大：当，角在，。一，。度范围内变化时，。越小，即卜引越小，b 点弯曲 程度就越大。因此可以用f 增导l 来定义折线上顶点的曲率，i 培纠在这里起到曲率 半径的作用，忙詈f 越小，曲率越大。 p 1 p 2 忙罔2 罔1 第1 0 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y 这样对离散点的曲率的计算方法，其实是比较粗糙的，如果要精确计算的话， 以先对离散数据作插值或者拟合，反求曲线方程，然后再求曲率。不过，这样大 大增加了计算的复杂度。而在模型简化中一般只需要曲率值的相对大小，所以采 用以上的估算还是有效的。 ( 2 ) 平坦性标准 这里需要分两种情况，即顶点在网格内部与顶点在边界的情形。 ( 1 ) 对网格内部的顶点v ，设其相关的三角形板为p v ，则该点的平坦性由 以下距离来描述： d = i n ( v c 】 其中，n 为以下向量的单位向量： n ( 厂加 ，e 昂 爿 ，厅 而c 的取值为： 心( 厂n ，e 昂 c 2 v b 爿杪) “v ， ，e 厅 f 为p v 中的三角形面片，h ( f ) 为f 的法向量，a ( o 为f 的面积，c ( o 为f 的中心。 ( 2 ) 对边界顶点v ( 只存在于网格里的一个三角形当中) ，记为其相邻的边 界顶点为v 1 ，v 2 ，则该点的平坦性计算为顶点v 到v l 与v 2 之间连线的距离。 2 2 2 顶点重要程度计算 顶点的重要程度是指顶点对整个模型外观的影响力大小。通常情况下，处在 - ；q 平坦区域的顶点的重要程度较低，而处在尖锐突出的区域的顶点较为重要。 因此顶点重要程度可以用顶点的曲率或者顶点平坦性标准来计算。即： 一。= k 或者k 。= d k 和d 由上面介绍的公式计算。 有时候还要考虑与顶点相连的边的边长关系。因为假如顶点的相邻边都很 短，那么这个顶点的曲率再大，也不过是一个不起眼的细节。因此这里可以驭最 长边、最短边或者平均边长来度量。 第1 l 页 上海大学研究生论文 t h ep o s t g r a d u a t et h e s i so fs h a n g h a iu n i v e r s i t y l e n g t h ( s e ) ，= m a x ( s f ) 或者f ：m i n ( s f ) 或者k 型了一 其中，& 是与顶点相关的边集。 综合考虑两项因素，有多种组合方式，以下是比较简单的两种计算方法 。= k ，或者。= 口k + b ， 其中，a 和b 是常数，控制k 和，的比例。 2 2 3 边重要程度计算 模型中的边的属性有：位鼍、方向、长度。首先也是研究边所处的位置。不 过边是由顶点构成的，若只考虑与边相连的两个或一个三角形，显然是不够的。 所以要描述所处位置的凹凸状况，应该考虑其两个顶点的曲率： e = k 】+ k 2 或者e = k lx k 2 其中，k ，和也是与边关联的两个顶点的曲率。 更复杂一点，可以组合两个顶点的重要程度，固为顶点的重要程度包含了更 多的位嚣信息： e = 矿l 。p + 矿2 f 或者e = v 1 ，。p v 2 接下来要考虑的因素是边长，这是边的一个重要特