（计算机应用技术专业论文）基于特征点保护的三维几何网格简化研究与应用.pdf

基于特征点保护的三维几何| 唰格简化l i j f 究与应用摘要 论文题目：基于特征点保护的三维几何 网格简化研究与应用 专业：计算机应用技术 硕士生：周慧敏 指导教师：罗笑南教授 摘要 本论文的研究工作基于国家自然科学基金课题移动图形计算中的若干 关键问题研究与应用( 项目编号：4 1 0 3 0 2 0 ) 。该研究课题中的一个研究重点是基 于移动嵌入式手持设备平台的图形数据的表示和处理的问题，以支持动画、游戏 等相关软件在移动设备上的运行。本论文的研究以此为出发点，重点研究三维几 何模型的简化，以形成在移动手持设备上有效显示三维图形的可行方案，提出了 基于特征点保护的三维几何网格模型简化方法，并将方法应用于实际模型进行了 验证。 本文在研究总结经典三维网格模型简化方法的基础上，根据移动手持设备的 特点，首先给出了顶点对的特征函数的定义，并通过计算顶点对特征函数识别出 模型的关键点：更进一步，引入视觉特征的参考，识别出模型在给定视线下的轮 廓点：在此基础上提出一种基于特征函数衡量的对模型关键点、轮廓点这两种特 征点进行保护的边折叠几何模型简化方法。其次，本文在边折叠的简化方法的基 础上，又提出基于特征函数衡量的对模型关键点、轮廓点这两种特征点进行保护 的三角形折叠简化算法。最后，文章给出了上述两种方法在几何模型上的应用情 况，并与未加特征点保护的简化方法进行了对比分析，本文所述的方法可以有效 地保护模型外观特征，尤其在模型点面数量较少的情况下，模型造型更加完整可 信。随着移动计算技术的发展，移动三维图形的应用将会越来越多，本文所述的 模型简化方法为三维网格模型在移动平台上的显示、传输及其他处理提供了良好 的基础。 廓点 关键词：移动手持设备；几何简化：三维网格模型：特征函数；关键点；轮 基于特征点保护的三维几何网格简化研究与应用 t i t l e ：r e s e a r c ha n da p p l i c a t i o no f3 dm e s hs i m p l i f i c a t i o n b a s e do nc h a r a c t e r i s t i c sv e r t i c e sp r o t e c t i n g m a j o r ：c o m p u t e ra p p l i e dt e c h n o l o g y n a m e ：z h o uh u i m i n s u p e w i s o r ：p r o f e s s o rl u ox i a o n a n a b s t r a c t lh et h e s i sc o m e sf r o mt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o ni s s u e s t h ec a l c u l a t i o no fan u m b e ro fk e ym o b i l eg r a p h i c sr e s e a r c ha n da p p l i c a t i o n s ( i t e mn u m b e r ：4 10 3 0 2 0 ) o n eo ft h i sp r o j e c t sk e yt a s k sn e e d e dt ob ef u l f i l l e d i st od i s p l a ya n dp r o c e s sg r a p h i c sd a t ao na ne m b e d d e dm o b i l ep l a t f o r m ，i n s u p p o r to ft h eo p e r a t i o no fa n i m a t i o n ，g a m e sa n do t h e rr e l a t e ds o f t w a r e s r u n n i n go nm o b i l ee q u i p m e n t s w i t ht h i sb a c k g r o u n d ，t h et h e s i sf o c u s e so n s t u d y i n gt h em e t h o do fs i m p l i f y i n g3 dg e o m e t r i cm o d e l s a n df o r m a t t i n ga s c h e m et h a tc a nd i s p l a y3 dg r a p h i c so nm o b i l ed e v i c e se f f e c t i v e l y a tl a s t ， t h et h e s i s p r o p o s e s a s i m p l i f y i n g m e t h o db a s e do n p r o t e c t i n g t h e c h a r a c t e r i s t i c sv e r t i c e s ，a n da p p l i e st h em e t h o dt oa c t u a lm o d e l sf o rt e s t i n g a f t e rad e t a i l e ds t u d yo ft h ec l a s s i c a lm e t h o d so fs i m p l i f y i n g3 dm e s h m o d e l s ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h em o b i l ed e v i c e s ，t h et h e s i s m a k e sad e t a i l e dr e s e a r c ho nb o t ht h es i m p l i f i c a t i o ns t r a t e g ya n dt h em o d e l s c h a r a c t e r i s t i cv e r t i c e s ，a n dp r o p o s e st h ea l g o r i t h m st h a tw i l l s i m p l i f y t h e g e o m e t r i cm o d e la sw e l la sm a i n t a i n e dt h em o d e l sa p p e a r a n c e f i r s t ，t h e t h e s i sp r e s e n t st h ed e f i n i t i o n o ft h ep e a kf u n c t i o no fv e r t e xp a i r s ，a n dt h e m e t h o do fr e c o g n i z i n gt h ek e yv e r t i c e so ft h em o d e lt h r o u g ht h ep e a kf u n c t i o n f u r t h e r m o r e ，t h et h e s i si n t r o d u c e st h er e f e r e n c eo fv i e w p o i n t ，s oc o n t o u r s v e r t i c e sc a nb er e c o g n i z e d t h e na ne d g ec o l l a p s es i m p l i f i c a t i o nm e t h o d b a s e do nt h ep r o t e c t i o no fk e yv e r t i c e sa n dc o n t o u r sv e r t i c e sw a sp r o p o s e d t h em e t h o dc a nm a i n t a i nt h ea p p e a r a n c eo fm o d e l s e f f e c t i v e l y w h i l e s i m p l i f y i n gt h em o d e l ，s o i t p r o v i d e st h eb a s eo fd i s p l a y i n gg e o m e t r i cm o d e l s o nm o b i l ed e v i c e s s e c o n d ，t h i st h e s i sp r o p o s e st h et r i a n g l ec o l l a p s e ds i m p l i f y m e t h o db a s e do nt h ep r o t e c t i o no fk e yv e r t i c e sa n dc o n t o u r sv e r t i c e s ，w h i c h c o u l dm a i n t a i nt h ea p p e a r a n c eo ft h em o d e l sa sw e l la ss i m p l i f yt h em o d e la ta f a s ts p e e d a tl a s t ，t h et h e s i sd i s p l a y st h eo u t c o m e st h a ta p p l i e dt h em e t h o d s o n g e o m e t r i cm o d e l sa n dc o m p a r e st h e m w i t ht h eo n e st h a tw i t h o u t c h a r a c t e r i s t i cv e r c i c e sp r o t e c t i n g ，t h ea p p l i c a t i o ns h o w e dt h em e t h o d s p r o p o s e di n t h et h e s i sa r em o r ee f f i c i e n ta n df a s tt h a nt h eo r d i n a r yo n e s e s p e c i a l l yw h e nt h ea m o u n lo fv e d i c e sa n df a c e so ft h em o d e i i si i m i t e d t h e s h a p eo ft h em o d e lw b em o r et r u s t a b l ea n dv i v i d w i t ht h ed e v e l o p m e n to f m o b i l ec o m p u t i n g ，t h ea p p l i c a t i o n so f3 dm o b i l eg r a p h i c sw i l lb em o r e a n dt h e m e t h o dp r o p o s e di nt h et h e s i sw i l lp r o v i d eag o o df o u n d a t i o nf o rt h ed i s p l a y i n g t r a n s m i t t i n go ro t h e rp r o c e s s i n go ft h e3 d m e s hm o d e l so nm o b i l ed e v i c e s k e y w o r d s ：h a n d h e l dm o b i l ed e v i c e s ；g e o m e t r i cm e s hs i m p l i f i c a t i o n ；3 d m e s hm o d e l ；p e a kf u n c t i o n ；k e yv e r f e x ；c o n t o u r sv e k e x 基于特征点保护的三维几何网格简化研究与应前言 日! j青 本论文的研究基于国家自然科学基金课题移动图形计算中的若干关键 问题研究与应用( 项目编号：4 1 0 3 0 2 0 ) 。该研究课题中一个研究重点是基于移动 嵌入式手持设备平台的图形数据的表示和处理，以支持动画、游戏等相关软件在 移动设备上的运行。本文研究的开展以此为出发点，重点研究三维几何模型简化， 以形成在移动手持设备上有效显示三维图形的可行方案。本文围绕在移动手持设 备上进行三维图形的显示和处理这个中心，根据移动手持设备的特点，进行了基 于保护模型特征顶点的模型简化策略的研究。 对于当前很多应用来讲，通常要求能够实时观测和操纵三维几何数据以提高 人们的创造能力，或增强人们的满意程度。同时，由于人们对j l 何数据的精度和 细节方面提出了更高的要求，以及各种高级造型工具出现和模型获取技术发展等 各种因素，导致了在计算机图形学的许多应用中使用的三维几何数据的数量规模 和复杂程度还在急剧地增长着。这两方面的事实存在不仅使得人们要花费更多的 代价去存储这些几何数据，而且它们对现有的三维图形引擎的处理能力和速度提 出了巨大的挑战。再者，随着网络图形学的发展，越来越多地需要通过网络，特 别是国际互联网，来存取那些存放在异地的三维几何数据。这使得本已十分有限 的网络带宽变得更加的紧张。要解决这些由于三维几何数据量和复杂度的急剧增 长以及手持设备相对较低的三维图形处理能力所带来的问题，仅仅依靠提高三维 图形引擎的处理速度，以及增加网络带宽等硬件方面的措施是不够的。因此，三 维几何简化成为计算机图形学和网络技术中的重要课题，研究适合于计算机网络 传输和移动手持设备处理的三维几何数据表示方法有着十分重要的意义。 本论文的研究围绕在移动手持设备上进行三维图形的显示和处理这个中心 问题，根据移动手持设备存储器容量小、处理能力相对较低的特点，针对e h - - 角 形网格表示的几何模型，进行了基于保持模型外观的模型简化策略的研究，提出 了可以适应在移动手持设备上进行显示和处理的基于保护模型特征顶点的几何 模型简化方法。 基十特征点保护的二维几何网格简化研究与应用前苦 本文在充分研究总结经典三维网格模型简化方法的基础上，根据移动手持设 备的特点，首先给出了顶点刺的特征函数的定义，并通过计算顶点对特征函数识 别出模型的关键点；更进一步，引入视觉特征的参考，识别出模型在给定视线方 向下的轮廓点；在此基础上提出了一个基于特征函数衡量的对模型关键点、轮廓 点这两种特征点进行保护的保持模型外观的边折叠几何模型简化方法。经过具体 模型验证，这种方法可以在保持模型外观的同时有效的降低模型的规模，从而为 在移动手持设备上显示和处理几何模型提供了基础。其次，本文在边折叠的简化 方法的基础上，又提出了基于特征函数衡量的对模型关键点、轮廓点这两种特征 点进行保护的三角形折叠简化算法。经实例验证，这种基于特征点保护的三角形 折叠的几何简化方法在继承前述边折叠简化方法的优点的同时，又可以达到加快 简化速度的目的，并且保持模型外观。最后，文章给出了上述两种方法在几何模 型上的应用情况，并与未加特征点保护的简化方法进行了对比分析，本文所述的 方法可以有效地保护模型外观特征，尤其在模型点面数量较少的情况下，模型造 型更加完整可信。随着移动计算技术的发展，移动三维图形的应用将会越来越多， 本文所述的模型简化方法为三维网格模型在移动平台上的显示、传输及其他处理 提供了良好的基础。 本文的章节结构如下 第1 章，介绍本文的研究背景，几何简化方法，移动应用相关背景，阐明本 文的研究内容及研究重点； 第2 章， 基于三角形网格模型边折叠的简化策略，给出顶点对特征函数的概 念，给出轮廓点的定义，提出基于特征点保护的边折叠简化算法， 论述基于对特征点进行保护的边折叠简化的处理流程； 第3 章，研究三角形折叠策略，给出三角形特征函数的概念，引入视线参考 识别轮廓点，提出基于特征点保护的三角形折叠的简化算法，论述 基于对特征点进行保护的三角形折叠简化的处理流程； 第4 章，研究模型的特征点：通过特征函数来识别关键点，基于给定视点识 别轮廓点；基于以上两点识别关键点、轮廓点这两种特征点，并对 之进行保护；分别给出边折叠和三角形折叠简化中特征点的识别处 理流程： 箍于特征点保护的三维几何网格简化研究与应用 前言 第5 章，对本文提出的算法进行验证，观察简化的效果，分析简化的模型数 据，给出应用的情况； 第6 章总结本文的工作，提出对未来的展望。 _ 3 基于特征点保护的三维几何网格简化研究与应j = ：j第l 章综述 第1 章综述 计算机图形学是随着计算机及其外围设备而产生和发展起来的。它是近代计 算机科学与雷达，电视及图象处理技术的发展汇合而产生的硕果。在航空航天， 汽车轮船，电子机械，土建工程，影视广告，医药卫生，地理信息，轻纺化工等 领域广泛应用，推动了这门学科的不断发展，而不断解决应用中提住的各类新课 题，又进一步充实和丰富了这门学科的内容。 对于当前很多应用来讲，通常要求能够实时地观测和操纵这些三维几何模 型。同时，由于人们对几何数据的精度提出了更高的要求，以及各种高级造型工 具出现等各种因素，导致了这些三维几何数据的数量规模和复杂程度在急剧地增 长。这两方面的事实不仅使人们要花费更多的代价去存储这些几何数据，而且它 们对现有的三维图形引擎的处理能力和速度提出了巨大的挑战。另外，近年移动 手持式设备的迅猛发展，随之而来的一系列移动计算方面的问题，逐渐引起了众 多科研学者的注意，而移动终端上的三维图形处理便是其中一个具有挑战性的课 题。 1 1 研究背景 几何造型领域中，通常用多边形网格来描述三维形体。为了保证形体的真实 感和层次感，往往需要高度复杂、高度细节化的三维网格模型。随着三维数据获 取设备的普及，复杂网格数据的生成也变得越来越容易，具有几百万乃至于上亿 个三角形的复杂模型，在图形应用系统中并不鲜见。再者，随着网络图形学的发 展，越来越多地需要通过网络来存取存放在异地的三维几何数据，这使本已十分 有限的网络带宽变得更加的紧张。计算机存储、计算和处理网格模型的代价往往 与模型中三角形的数量成正比，庞大的网格数据对计算机的容量和处理能力等提 出较高要求，给模型的存储、传输、计算、绘制等带来困难。这些事实的存在使 得人们不得不花费更多的代价去存储这些几何数据，而且对现有的三维图形引擎 的处理能力和速度是一个巨大的挑战。正因如此，对三位模型进行有效的简化十 基于特征点保护的三维几何网格简化研究与应用 笫l 章综述 分必要。如图1 1 所示，s t a n f o r d 大- 学d i g i t a lm i c h e l a n g e l o 项目。借助三维扫描硬 件和三维重建软件完成了d a v i d 雕像数字化过程，单生成的三角面片就达2 0 亿 个。 b 照片 1 2 移动手持平台 a 三维扫描 图1 1d a v i d 雕像数字化模型o c 儿何模型 移动设备( m o b i l ed e v i c e ) 是当前应用最广泛的信息处理设备之一，这类设 备一般都具有独立的、可移动的数字运算、数据存储、多媒体播放、无线通讯等 信息处理能力，同时，这类设备可以通过接入无线网络与其他设备或者服务终端 进行数据交换。例如移动电话( m o b i l ep h o n e ) ，p d a ( p e r s o n a ld i g i t a l a s s i s t a n t ) ，h p c ( h a n d h e l dp r op c ) ，p o c k e tp c ，p a l m s i z ep c ，智能手 机( s m a r tp h o n e ) 等其他m i d ( 移动信息处理设备) 。它们满足了人们对移动通 信，互动互联，移动计算的需求，故其在当前数码消费市场上占有很大的份额， 同时市场需求也是多样并不断增长。 。2 0 0 6 年4 月7f i ，柬源于h t t p ：f l g r a p h i c ss t a n f o r de d u l d a t a l m i c h l 。t h ed i g i t a lm i c h e l a n g e l op r o j e c t ：3 ds c a n n i n go fl ar g es t a t u e s s i g g r a p h2 0 0 0 ，c o m p u t e rg r a p h i c s p r o c e e d i n g s ，2 0 0 0 ，1 3 1 1 4 4 基于特征点保护的三维几何网格简化研究与应用 第1 章综述 1 2 1 移动手持设备的局限 目前，移动设备上基本业务已经发展的比较全面了，其三维计算方面相应也 有很大的需求，例如：手机游戏等，进一步的需求如移动设备上的虚拟现实等。 但是目前其硬件条件还不能很好的满足这些需求。虽然当前的移动设备种类繁 多，它们还是具有如下的共同特点： 移动设备的处理器( c p u ) 能力非常有限；移动设备的图形处理器( g p u ) 能力低，数量少；移动设备的显示屏幕较小，色彩数目比起个人计算机来，还很 少；移动设备的存储能力距离三维计算的需求来说还有很大的距离；移动设备的 网络传输能力有限；移动平台上支持三维图形的软件工具包寥寥可数。许多处理 器都针对便携式电脑及移动电话作了相应改动，这些改动带来的缺陷包括缺少浮 点运算、除法运算、方根运算以及三角函数运算，它们都制约了手持式设备像桌 面型电脑处理器那样适用于三维应用。于是，移动图形的网格模型简化成为研究 热点。 移动通讯技术的快速发展，使移动办公、移动电子政务、电子商务、移动娱 乐等成为当前i t 产业的焦点之一。p d a 、移动电话等手持式设备( h a n d h e l d ) 在近几年迅猛发展，越来越多的生产厂家开始发展新一代的移动电话和掌上电脑 的一体化产品( s m a r tp h o n e ) ，随之而来的一系列移动计算方面的问题，逐渐 引起了众多科研学者的注意。无论从硬件设备还是应用标准来说，移动终端上的 三维图形计算都是一个具有挑战性的课题。 1 2 2 移动设备g p u 处理能力的进步 在硬件设备方面，两大图形显示卡厂商n v i d i a 和a t i 已经开发出了一系列 可用于移动手持设备的处理芯片。 2 0 0 6 年2 月1 3 日，n v i d i a 在2 0 0 6 年度3 g s m 世界大会。上强势发布许 多特性已经达到甚至超过了主流桌面g p u 的水平的最新移动版 。天极网2 月1 4 日消息_ 2 月1 3 同2 月1 6 日，2 0 0 6 年3 g s m 世界火会在西班牙巴塞罗那举行 _ 6 一 基于特征点保护的三维几何网格简化研究与应用第1 章综述 g p u g o f o r c e5 5 0 0 。图1 2 显示的是n v i d i ag o f o r c e5 5 0 03 d 引擎的画 面。 图1 2 n v i d i ag o f o r c e5 5 0 03 d 引擎的画面。 在3 g s m0 6 大会上还展示了专为g o f o r c e5 5 0 0 进行优化的两款游戏。有 史来首次由e l e c t r o n i c a r t s 公司在手机上演示基于o p e n g le s 标准的游戏 极品飞车：最高通缉( n e e d f o r s p e e dm o s t w a n t e d ) ，如图1 - 3 所示。 幽1 3极品飞丰：最高通缉。 得益于n v i d i ag o f o r c e5 5 0 0 ，这款惊险刺激的疾速赛车游戏呈现了更加 惊心动魄的视觉体验，实现了快速、流畅的帧速率，并且支持高分辨率v g a 显 示屏。此外，归功于钊对特定硬件的优化解决方案，这款游戏还展示了诸如动作 模糊和反射等特效，带给用户真正淋漓尽致的游戏体验。 n v i d i ag o f o r c e5 5 0 0 是业界第一款可流畅处理真正的流媒体数码电视、 高保真环绕音响、快速多张照片处理及大型游戏3 d 图形处理的移动g p u 。 n v i d i a 声称g o f o r c e5 5 0 0 在视频编码解码和3 d 加速方面取得了突破，是第 一款可支持以d v d 分辨率( 7 2 0 x 4 8 0 ) 回放h 2 6 4 、w m v 9 、m p e g 4 ( d i v x 、 x v i d ) 等内容的移动g p u ，可以为手机提供1 0 2 4 x 7 6 8 像素的超高屏幕分辨率， 。2 0 0 6 年4 月1 0 日，米源于日：联网，h t t p ：h c n n v i d i a c o m p a g e g o f o r c e _ 5 5 0 0h t m l 。2 0 0 6 年4 月1 0 日，来源十新华网，h t t p ：f l n e w sx i n h u a n e tc o m i t j 2 0 0 6 - 0 2 2 2 c o n t e n t _ 4 2 1 1 0 4 1 h t m l 一7 基于特征点保护的三维几何刑格简化研究与应用 第l 章综述 每秒最多可处理2 6 0 万个三角形，达到了前所未有的每秒2 0 0 百万像素处理能 力，并且功耗极低。用户可以随时随地更长时间参与游戏，获得游戏机级游戏体 验。 作为n v i d i a 的竞争对手，a t i 在1 月末也一下子向市场推出了i m a g e o n 2 3 8 0 和2 3 8 8 这两枚支持m p e g 4 、h 2 6 3 2 6 4 或r e a lv i d e 0 3 d 的移动图形芯 片o 。这些产品采用o p e n g le s1 1 + 扩展包，能为环境、光照和物体提供更 多真实细节，并同时保持高水准的互动性。a t l 的这两款产品提供最新的3 d 加 速功能，支持o p e n g le s1t 2 为游戏开发者提供更大的创作空间和更强的执行 性能。芯片为移动多媒体手机提供了音频、图像集成解决方案。 随着技术的进步，移动硬件设备的处理能力正在不断提高。 1 2 3 移动图形应用标准 在应用标准方面，具有代表性的标准是o p e n g le s 。o p e n g le s 是以跨 平台计算机绘图a p io p e n g l 子集合为基础，以应用于手持设备、家电或游戏 机等嵌入式系统为主要需求而制定的新一代3 d 绘图a p i 。当前，o p e n g le s 应用也日益广泛，除手持设备、娱乐设备上的应用之外，o p e n g le s s c 更是 扩展到了军用、航用及自动应用程序等这些安全性可靠性要求很高的应用方面， 如图1 4 所示，是一些应用的实例。 图1 - 4 o p e n g l e s 应用。 o p e n g le s 家族的标准详细描述如下表1 1 所示。 。2 0 0 6 年4 月1 01 3 ，来源于赛迪网，h t t p ：m e d i a c c i d n e tc o m l a r t 2 9 8 5 1 2 0 0 6 0 3 2 9 1 4 9 1 5 0 5 _ 1h t m 。2 0 0 6 年4 月1 01 3 ，来源于k h r o n o s 主页，h t t p ：w w w k h r o n o s o r g o p e n g l e s 一8 一 基于特征点保护的三维几何网格简化1 i f 究与应川第l 章综述 表1 1o p e n g le s 家族的标准 版本性能。 o p e n g le s10 o p e n g le s l1 一针对软件演化3 d 功能性、修改功能硬件 o p e n g le s1 x o p e n g le s1 1e x t e n s i o n一所有1 x 说明书与后面的兼容 p a c k 针对新一代的可编程硬件的3 d 功能性 o p e n g le s2 xo p e n g le s2 0一配有g l s le ss h a d i n g 语言 所有2 x 说明书与后面的兼容 一针对安全性主要应用程序的3 d 功能性 o p e n g le s s co p e n g le s - s c1 0 一军用航用和自动应用桴序 一本地平台w i n d o w 系统界面 一图像资源管理的丌j 携式图 e g le g l l 01 1a n d l 2 使得快速混合模式的2 d 3 d 渲染能使 用o p e n g l e s 和o p e n v g 无论是应用标准的发展，还是移动硬件设备处理能力的提高，都说明移动图 形应用的需求在增加，因此，移动终端上的三维图形计算的研究是十分必要且应 用前景广泛的。 1 3 几何简化概述 为了解决移动平台上遇到的上述这些问题，可以通过升级和提高处理器的性 能，增加系统的存储器容量，增加网络带宽等硬件方面的办法来解决。但是仅仅 这样是不够的，还需要软件算法方面的措施，如：在下载和绘制几何模型的时候， 选择性的处理那些潜在可见的部分；在适当的时候使用图像代替复杂的几何模 型；对远距离处的物体使用多分辨率的、简化的几何模型，当几何物体慢慢走近 的时候，渐进的细化物体的几何细节；使用几何简化方法，设计几何模型的紧致 表示，减少它的存储空间和传输时间，使得它适合于利用硬件进行快速绘制。 人们已经在上面的这些方向上作了许多的工作，如基于图像的建模和绘制方 法( i m a g eb a s e dm o d e l i n ga n dr e n d e r i n g ) 、层次细节方法( l e v e lo fd e t a i l ) 和几何简化( g e o m e t r yc o n t r a c t i o n ) 等等。 。2 0 0 6 年4 月10 日，来源于k h r o n o s 主页，h t t p ：w w w k hr o n o s o r g o p e n g l e s ! - 9 一 基于特征点保护的三维几何网格简化研究与应用 第l 章综述 1 3 _ 1 几何简化的研究对象 通常的几何模型包含两部分的内容：一部分是几何模型的形状( s h a p e ) 另一部分是几何模型的外观( a p p e a r a n c e ) 。 几何模型的形状描述了物体所占据的空间。在计算机图形学中，描述物体形 状的方法有很多，其中边界表示法( b o u n d a r yr e p r e s e n t a t i o n ) 是应用最为广 泛的一种方法。在边界表示法中，物体的形状信息是通过它的表面来描述的。而 物体的表面又可以有各种各样的表示方法，如参数曲面、代数曲面、隐函数曲面 以及多边形网格等等。所谓的多边形网格就是一个标有一些属性的多边形的集 合。在一个典型的由多边形网格表示的三维几何模型中，这些属性包括位置坐标、 颜色、法线向量以及纹理坐标等。 几何模型的外观则描述了物体上的入射光线和出射光线之间的相互作用关 系。本质上它是物体本身固有的一种物理性质。但是在计算机图形学中，人们常 用一些易于理解的光照明量来描述，如颜色( c o l o r ) 、光泽度( s h i n i n e s s ) 、以 及透明度( t r a n s p a r e n c y ) 等等。 从图形学发展的早期阶段开始，人们就使用多边形表示的几何模型。多边形 表示一般都支持任意的n 边多边形。早期的绘制硬件还接受这种n 边多边形， 但是出于速度考虑，今天几乎所有的绘制硬件都要求这些多边形在提交之前必须 分解为三角形。即使有些绘制硬件能够接受四边形，那也是隐含着这些四边形在 绘制之前可以由系统任意地分解为两个三角形。 基于上述理由，几何简化研究主要集中在对多边形网格模型，尤其是在三角 形的网格模型的简化上。本文的几何简化研究对象也是三角形网格模型 1 3 2 网格简化技术基本思想 所谓几何简化，是指对描述三维场景的模型数据进行简化。目的是加快图形 处理的速度、减少数字通信线路中传输模型所需要的时问以及存储该模型所需要 。何晖光，田捷等，网格模型简化综述，软件学报2 0 0 2 ，v 0 1 1 3 ，n o 1 2 2 2 1 5 - 2 2 2 4 10 基于特征点保护的三维几何网格简化刖f 究与应用第1 章综述 的空间。几何简化在移动手持设备显示三维图形、分布式虚拟现实、协同应用、 多用户视频游戏、模型数据在计算机内部的存储和传输等方面有着很重要的意 义。 网格简化的目的是：对于输入网格模型m 。，产生与其对应的、基本保持形 状的、较粗糙的简化逼近模型m 。输出的逼近模型m 。，应该满足某些预先给定 的条件。若m 。是三角网格，那么这些条件可以是预设的网格元素( 如三角形网格 顶点) 的数目，或是新旧模型间的几何误差阈限等。由于任意多边形网格都可以 转化为三角网格，故对三角网格的简化方法具有一般意义。 网格模型简化的本质是：在尽可能保持原始模型特征的情况下，最大限度地 减少原始模型的三角形和顶点的数目。它通常包括两个原则 ：顶点最少原则一 一即在给定误差上界的情况下，使得简化模型的顶点数最少：误差最小原则 给定简化模型的顶点个数，使得简化模型与原始模型之间的误差最小【1 4 】。 1 3 3 网格简化方法分类 网格模型化简算法分类有多种，如根据拓扑结构是否保持可以分为拓扑结构 保持形“和非拓扑结构保持形5 。；根据模型简化的过程可以分为逐步求精” 和几何化简“：根据误差可控性可分为误差受限“1 和误差不受限。3 ；根据视点相 关性可以分为视点无关的化简和视点相关的化简“2 ”1 。这些分类方法都难以 囊括所有的化简算法，同时有很多算法彼此交叉。 ( 1 ) 化简原则和误差测度 误差测度是用来量化输入模型和输出模型的差异，它引导模型化简，使得化 简后的误筹在用，j 允许误差范围之内。误差测度包括外观相似测度和几何误差测 度“。外观相似测度用来计算原始模型与简化模型投影到视平面的差异，它最符 合人们的视觉习惯，但由于它需要从各个视点进行采样，计算量大，因此在实际 应用中通常用几何相似测度来代替。一个经常用到的几何误差测度被定义为 n s i m p l i f i c a t i o ne n v e l o p e s ，p r o c e e d i n g so ft h es i g g r a p h 9 6 ，v o l3 0 ，n oa n n u a lc o n f e r e n c es e r i e s ， 1 9 9 61 1 9 1 2 8 1 1 捧于特征点保护的三维几何网格简化研究与应用 第i 章综述 e 一( m - ，m z ) = m a x ( ( m m a x d 。( m ：) ，( 翟黔d v ( m t ) ) ( 1 1 其中d v ( m ) 示一个顶点y 到一个模型m 的距离( d ，( m ) 2 卿i i v w l l ，是两个 向量的欧氏距离) ，这个误差用来测量两个模型之间的最大偏差，同样两个模型 之间的平均偏差可以定义为 e a v g ( m m ) = 去l 吐2 ( m ：) + 亡k 识圳 ( 1 2 ) 其中，w l 和m 分别是m i 和m j 的面积。 几何相似测度还有一些其他类型的表述：如s c h r o d e r 币u 用点到平面的平均距 离作为局部误差测度来控制顶点的删除一t u r k 采用的是曲率度量”q ，周晓云利 用特征角度作为误差测度【17 l 。 ( 2 )简化方法分类 早期的模型简化算法大多属于静态化简，这种化简方法只考虑模型自身信 息，与视点无关，也不可恢复原模型的信息。相对而言，动态化简则可以实时地 得到具有所需要的分辨率的近似模型。每个模型的化简程度由模型之外的因素决 定，例如视点。在本文中轮廓点的定义就是基于视点的。动态化简的很多基本操 作是静态化简的方法，动态化简是静态化简的延续。 静态化简方法主要包括以下几种方法：顶点聚类法、区域合并法、重新布点 法、逐步求精法、几何元素删除法、小波分解。 顶点聚类法【18 】首先用包围盒包围原始模型，然后将包围盒划分为若干区域， 同一区域内顶点合并为一个新顶点，再根据原始拓扑对这些新顶点三角化，就得 到简化模型。这种方法通用，不保持拓扑，速度较快：无法保持均分域内特征， 误差控制简单，模型质量不高。 区域合并方法【4 选择一个三角面为种子面，根据一定的准则将周围的面合并 起来形成一个更大的面( 超面) ，再将其边界拉直，重新三角化从而达到面片化 简的目的。这种算法可由用户控制简化误差，可以保持模型的拓扑，但无法避免 带洞超面，且重新三角剖分计算复杂，运行效率较低。 挂十特钲点保护的三维几何网格简化| ，i j f 究与麻用 第1 章综述 重新布点法1 6 1 先将用户指定数目的顶点根据各个三角面片的面积大小分布 在模型表面上，其次根据模型表面上顶点之间的斥力以使顶点在表面卜的分布更 均匀，然后将模型上的原始顶点与新加入的顶点混合在一起进行三角剖分，最后 将原始顶点一个个地删去，并及时地对删除顶点所造成的空洞进行三角化。 逐步求精方法首先给出一个原始网格的逼近网格，然后逐步增加细节，并重 新进行局部三角化，直到近似模型达到用户满意的精度为止【7 - 8 1 。它包括贪婪插 入法和层次细分法。 1 9 9 2 年，s c h r o e d e r 提出了顶点删除的网格简化方法9 ，此后，基于边折叠 【1 0 】、基于三角形删除【1 1 】等几何元素删除的方法被相继提出。这些方法的共同特 点是以几何元素的删除实现模型的简化，即根据原模型的儿何拓扑信息，在保持 一定的几何误差的前提下删除对模型几何特征影响相对较小的几何“图元”( 点、 边、面) 。以下将分别对这三种图元删除方法进行介绍： 如图1 5 一a 所示，存三角网格中，若一个顶点与它周围三角而片可被认为是 共面的( 这可以通过设定点到平面距离的阈值来判断) ，且删除该点不会改变拓 扑，则可删除该点，同时删除所有与该点相连的面，然后对其邻域重新三角化， 以填补空洞，重复这种操作直到三角网格中无满足上述条件的顶点为止”1 。如这 种算法计算快，也不需太多的内存；但这种算法只适用于流形，而且它在保持表 面的光滑性方面存在困难“。 边折叠简化算法，每次简化操作中以边作为被删除的基本几何元素。在进行 多次的选择性边折叠后，面片就可以被简化到我们想要的任何程度了。点分裂是 边折叠的逆变换，可以用来恢复被简化掉的信息。h o p p e 通过边折叠和点分裂构 建了渐进网格( p r o g r e s s i v em e s h ，简称p m ) 模型，实现了多分辨率 ( m u l t i r e s o l u t i e n ) 的层次细节模型( 1 e v e lo f d e t a i l ，简称l o d ) 的实时生成1 。边折 叠的关键是折叠的次序以及边折叠后新顶点的位置。h o p p e 在1 9 9 3 年采用能量 优化的方式来确定折叠次序和新顶点的位置【1 0 】，能量优化计算复杂，所需时问较 长，但是生成模型的效果却是在所有化简方法中最好的。g a r l a n d 干1 h e c k b e r t 在 1 9 9 7 年提出了一种基于二次误差测度( q u a d r i ce r r o rm e t r i c ，简称q e m ) i 筝j 化简算 。李敏君，纪庆革，二维几何数据压缩与简化，宇航学报，2 0 0 2 2 3 ( 3 ) ：8 5 8 8 1 3 基于特征点保护的三维几何网格简化研究与应j | 】帮l 章综述 法雎刀。q e m 算法误差测度是基于顶点到平面的距离平方和，该算法速度快，简 化生成的模型质量仅次于h o p p e 的能量优化方法，是一种非常有效的化简算法。 边折叠前边折叠后 a 边折叠操作示例 i “ 。 b 三角形折叠操作示例 图1 - 5 图元删除方法 三角形折叠简化方法简化时将三角面作为被删除的基本元素。它是边折叠算 法的延续，一次三角形折叠可以删除4 个三角形、两个顶点。周昆等人将三角形 r o n l 折叠与q e m 算法结合起来，并给出了一种传递简化误差的方法 小波分解方法为层次细节模型提供了一个完美的数学表达方式，它首先由 1 1 l o u n s b e r y 和d e r o s e 在1 9 9 4 年提出”。原理是。利用小波分析的方法将一个三维 模型分解成低分辨率部分和细节部分，低分辨率部分是原始模型的一个子集，它 的顶点为原始模型中对应顶点的邻域的加权平均，通常用低通滤波来实现，因此 表现为低频信号；细节部分通常包含抽象的小波系数，这些系数通过高通率波来 得到，表现为高频信号。重建过程通过选择适量的高频信号与低频信号以合成相 应精度的三维模型，通过略去其余的更高频分量来达到简化的效果。这种方法简 单、高效，但是它只适用于具有细分连通性的三角网格。 动态化简中最著名的算法当属h 0 p p e 芷s i g g r a p h ，9 6 上提出的p m 算法 。jm i c h a e ll o u n s b e r y , m u l t i r e s o l u t i o na n a l y s i sf o rs u r f a c e so f a r b i t r a r yt o p o l o g i c a lt y p e 。p h dt h e s i s d e p a r t m e n t o f c o m p u t e r s c i e n c ea n de n g