（计算机应用技术专业论文）基于特征保持的网格简化算法研究及其应用.pdf

茎主壁堑堡堡塑塑塑堡些墨鲨堡塞墨茎壁旦：塑至 + ， 论文题目：基于特征保持的网格简化算法研究及其应用 专业：计算机应用技术 硕士生：林煜斌 指导教师：罗笑南教授、周凡讲师 摘要 随着计算机图形学及其相关理论和技术的快速发展，并且伴随着医学、三维 扫描仪及后来c t 等三维数据获取设备的不断改进，生成的三维模型数据的数量 规模和复杂程度正在日益增长；同时，人们对于实时操纵几何数据的要求也越来 越高；另一方面，移动手持设备迅猛发展并得到在生活中的广泛应用，用相对较 低的处理能力来处理三维图形成为一个巨大的挑战。因此，针对手持设备的特点 以及在此基础上进网格简化和显示的研究具有十分重要的意义。 本文围绕在移动手持设备上进行三维图形的显示，针对移动手持设备的特 点，对模型的压缩策略和模型的特征点进行了研究，目标是提出一个在保持模型 外观的基础上对网格模型进行压缩、简化，并且简化后的模型可以适应在移动手 持设备上进行显示的完整算法。本文基于边折叠的网格简化算法，是在基于顶点 相邻三角形单位法向量变化的边折叠网格简化基础上，在边折叠中引入了三角形 的形状因子，从而避免了网格简化过程中产生畸形三角形面片；为了使网格模型 尽量保形，该算法还采用了局部寻优策略，使每一步边折叠操作都尽可能保证了 网格的外观；此外，通过分析顶点相邻三角形法向量方向，提出基于向量柬长度 的方法来识别出模型的特征点，同时根据顶点的邻接三角形数目和邻接顶点数目 的关系异识别出边界点，从而在边折叠操作时进行特征保留的策略；完整的保持 模型外观和特征保留的边折叠网格简化算法可以在保持模型外观的同时有效的 降低模型的规模，从而为在移动手持设备上显示几何模型提供了基础。文章最后 给出了在移动手持设备上的应用情况。随着移动计算技术的发展，移动三维图形 的应用将会越来越多，因此本文的成果具有较好的应用前景。 关键词：三维网格模型、网格简化、边折叠、向量束长度、网格特征点 基于特征保持的网格简化算法研究及其应用 a b s t r a c t t r i e ：r e s e a r c ha n da p p l i c a t i o no fm e s hs i m p l i f i c a t i o na l g o r i t h mb a s e d0 n c h a r a c t e r i s t i cp 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 c a t i o nt e c h n o l o g y n a m e ：l i n1 y u b i n s u p e r v i s o r ：p r o f e s s o rl u o x i a o n a n 、i n s t r u c t o rz h o uf a n a b s tt a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rg r a p h i c st h e o r ya n dt e c h n o l o g y , t h es i z ea n d c o m p l e x i t yo f3 dm o d e l sa r ei n c r e a s i n gr a p i d l y , b e s i d e s ，t h ec o n s t a n ti m p r o v e m e n ti n3 d c a p t u r i n gd a t ad e v i c e s ，s u c ha sm e d i c i n e so r3 ds c a n n e ra n dc t m e a n w h i l e , d e m a n d so f r e a l t i m ec o n t r o l l i n gg e o m e t r ym o d e l sa r eb e c o m i n gh e a v i e r w i t ht h ed e v e l o p m e n to f h a n d h e l dd e v i c e sa n di t sw i d e l ya p p l i c a t i o n s ，i ti sab i gc h a l l e n g et h a tu s i n gal o w e n d m a c h i n et oc o m p u t e3 dg r a p h i c s t h e s es e r i e so fi s s u e ss h o wt h a tr e s e a r c ho fg e o m e t r y c o m p r e s s i o ni nm e s hs i m p l i f i c a t i o na n dd i s p l a yi sv e r yi m p o r t a n t f o c u so nd i s p l a y i n g3 dg r a p h i c so r lh a n d h e l dd e v i c e s ，t h i st h e s i sd i s c u s s e sc o m p r e s s i o n m e t h o da n dc h a r a c t e r i s t i cv e r t e xb a s e do nt h ec h a r a c t e ro fh a n d h e l dd e v i c e s t h eg o a lo ft h i s t h e s i si st op r o p o s ea na p p e a r a n c ep r e s e r v a t i o ng e o m e t r yc o m p r e s s i o na r i t h m e t i c w h i c hc 柚 s u p p o r td i s p l a y i n g3 dm o d e l so uh a n d h e l dd e v i c e s t h i st h e s i sp r o p o s e da ne d g ec o l l a p s e a r i t h m e t i cb a s e do nt h ec h a n g eo ft r i a n g l en o r m a lw h i c hb o r d e ro nv e r t e x , a n dt h es h a p e f a c t o ri sc o n s i d e r e dt ot h i sa r i t h m e t i c t h a tt h ea b n o r m a lt r i a n g l ec a nb ev o i d e d i no r d e rt o p r o t e c tt h em e s hm o d e l ，t h el o c a lb e s tm e t h o di s i n t r o d u c el , w h i c hi su s e f u lf o rt h em e s h m o d e lf a c e t h i st h e s i sa l s op r o p o s e dac h a r a c t e rp r e s e r v a t i o nm e t h o db a s e do nt h el e n g t ho f v e c t o rs e ta n dt h eb o u n d a r yp o i n t t h ew h o l ea l g o r i t h mn o to n l yr e d u c e st h es i z eo f 3 dm o d e l w i t h o u tc h a n g i n gi t sa p p e a r a n c e , b u ta l s ou s e df o rt h er e a b t i m ed i s p l a yo nm o b i l eh a n d h e l d d e v i c e s f i n a l l y , i tp r e s e n t st h er e s u l t o nm o b i l eh a n d h e l dd e v i c e s ，a f t e rt h em o d e l sa r c s i m p l i f i e d d u et ot h ed e v e l o p m e n to fm o b i l et e c h n o l o g y , t h e r ew i l lb em o r ea p p l i c a t i o n so f m o b i l e3 dg r a p h i c s ；t h e r e b yt h er e s u l to f t h i st h e s i sw i l lh a v eas p r e a dp r o s p e c t k e y w o r d s ：3 dm e s hm o d e l , m e s hs i m p l i f i c a t i o n , e d g ec o l l a p s e , l e n g t ho fv e c t o r s e t , m e s hc h a r a c t e r i s t i cv e r t e x i i 基于特征保持的同格简化算法研究及其应用前言 l - l 刖罱 本论文主要针对移动嵌入式手持设备( 如手机平台) ，在这类平台上实现相 关的图形数据的表示和处理，以支持动画、游戏等相关软件在移动设备上的运行。 本研究课题以该项目为应用背景，重点是研究网格简化，并形成在移动手持设备 上有效显示三维图形的可行方案。 随着现代科技的发展和计算机图形学理论的研究深入，三维网格模型在各种 应用中扮演着越来越重要的角色，人们越来越大量地使用着三维网格数据，以实 现和完成各种不同的目标和效果。对于很多应用来讲，通常要求能够实时地观测 和操纵这些三维网格模型。同时，由于人们对几何数据的精度提出了更高的要求， 以及各种高级造型工具出现等各种因素，导致了这些三维网格数据的数量规模和 复杂程度在日益地增长。这两方面的事实不仅使人们要花费更多的代价去存储这 些几何数据，而且它们对现有的三维图形引擎的处理能力和速度提出了巨大的挑 战。另外，近年移动手持式设备的迅猛发展与应用，随之而来的一系列移动计算 方面的问题，逐渐引起了众多科研学者的注意，而移动终端上的三维图形处理便 是其中一个具有挑战性的课题。 要解决这些由于三维网格数据量和复杂度的急剧增长以及手持设备相对较 低的三维图形处理能力所带来的问题，仅仅依靠提高三维图形引擎的处理速度， 以及增加网络带宽等硬件方面的措施是不够的。因此，三维网格简化成为计算机 图形学和网络技术中令人感兴趣的重要课题。研究适合于计算机网络传输和移动 手持设备处理的三维几何数据表示方法有着十分重要的意义。 本研究课题围绕在移动手持设备上进行三维图形的显示，根据移动手持设备 存储器容量小和处理能力较低的特点，针对由三角形网格表示的几何模型，对模 型的压缩策略和模型的特征点进行研究，目标是提出一个在保持模型外观的基础 上对几何模型进行有效的压缩与简化，并且压缩后的模型可以适应在移动手持设 备上进行显示的完整算法。 基于特征保持的网格简化算法研究及其应用 前言 本文的章节结构如下： 第l 章， 介绍本课题的研究背景和网格简化算法，以及移动设备上图形应用 的相关方法，从而引出本文的研究重点： 第2 章， 研究边折叠策略，提出基于顶点相邻三角形单位法向量变化与避免 狭长尖角三角形的边折叠压缩与算法，并提出“局部寻优”策略； 第3 章， 研究模型的特征点，提出基于向量束长度的特征点识别方法；并提 出通过比较顶点的邻接顶点和邻接三角形的数量来识别边界顶点 的策略； 第4 章， 对本文提出的算法进行验证，观察压缩的效果，分析压缩的模型数 据，并给出在移动手持设备上应用的情况； 第5 章， 总结本文的工作，提出对未来的展望。 2 基于特征保持的网格简化算法研究及其应用 第1 章综述 第1 章综述 随着现代科技的发展和计算机图形学理论的研究深入，三维几何模型在各种 应用中扮演着越来越重要的角色，三维几何模型的数量规模和复杂程度在日益地 增长，模型简化方法得到深入研究；与此同时，移动设备迅猛发展与应用，用相 对较低的处理能力来处理三维图形成为一个巨大的挑战。针对手持设备的特点以 及在此基础上进行图形简化和显示的研究是一个具有挑战性和重大意义的课题。 1 1 研究背景 计算机图形学，从它的诞生发展到现在，已经在许多领域扮演着越来越重要 的角色，发挥着越来越重要的作用。从简单的增强视觉效果到利用其直观性进行 人机交互，三维模型在工业制造、电子机械、影视广告、产品设计、建筑设计、 模拟仿真以及游戏娱乐等诸多领域中扮演着日益重要的角色。在这些日渐广泛的 计算机图形学的应用之中，为了保证形体的真实感和层次感，往往需要高度复杂、 高度细节化的三维网格模型，以实现和完成各种不同的目标和效果。随着计算机 图形学及其相关理论和技术的快速发展，所使用的三维几何数据的规模和复杂程 度在不断地急剧增长着。 对于当前很多应用来讲，通常要求能够实时地观测和操纵这些三维几何模 型。以提高人们的创造能力，或增强人们的满意程度。同时，由于人们对几何数 据的精度和细节方面提出了更高的要求，以及各种高级造型工具出现和模型获取 技术的发展等各种因素，导致了这些在计算机图形学的许多应用中使用的三维几 何数据的数量规模和复杂程度还在急剧地增长着。这两方面的事实存在不仅使得 人们要花费更多的代价去存储这些几何数据，而且它们对现有的三维图形引擎的 处理能力和速度提出了巨大的挑战。图卜l 所示是一个斯坦福大学的数字米开朗 基罗计划中注明的d a v i d 雕像模型，该模型单生成的三角面片就达2 0 亿个i l j 。 再者，随着网络图形学的发展，越来越多地需要通过网络，特别是国际互联网， 来存取那些存放在异地的三维几何数据。这使得本已十分有限的网络带宽带变得 基于特征保持的网格简化算法研究及其应用 第1 章综述 更加的紧张。总之这些复杂的模型对计算机的存储容量、处理速度、绘制速度、 传输效率等都提出了很高的要求，给模型的存储、传输、计算、绘制等带来困难。 然而在很多情况下，高分辨率的模型并不总是必要的，模型的准确度以及需要处 理的时闻也要有一个折衷，因此必须用一些相对简单的模型来代替原始模型，这 就是对模型进行简化。 ( a ) 三维扫描( b ) 几何模型 图i - ld a v i d 雕像数字化模趔。 近年移动手持设备的迅猛发展，随之而来的一系列移动计算方面的问题，逐 渐引起了众多科研学者的注意，而移动终端上的三维图形计算便是其中一个具有 挑战性的课题。从市场上移动手持设备的发展趋势来看，已经初步具备了支持三 维图形绘制的硬件条件，但设计人员仍需要花费一些精力来处理其他问题，诸如 存储器不足，以及处理器运算能力有限等问题。存储容量的不足是支持三维图形 显示的主要问题，它决定了用户能在手持式产品中存储的三维图形的规模，这时 就需要在图形数据量和图形精度方面进行折中。另一方面，目前许多处理器都针 对便携式电脑及移动电话做出了相应改动，这些改动带来的缺陷包括缺少浮点运 算、除法运算、方根运算以及三角函数运算，它们都制约了移动手持设备像桌面 型电脑处理器那样适用予三维应用。另外，三维图形绘制所需要的一些高级效果， 如转换、照明和裁剪等，要求高度精确的浮点运算，而大部分嵌入式平台的图形 处理能力仍未达到该水平。 庞大的三维网格数据量对处理器的处理能力、计算机的容量以及网络传输技 术都提出了很高的要求，成为实现移动设备图形处理、实时交互、网络三维动画、 分布式虚拟现实等应用的瓶颈。要解决这些由于庞大的数据数量和急剧增长的复 。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 a r 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 4 基于特征保持的网格简化算法研究及其应用第1 章综述 杂度以及移动设备相对较低的三维图形处理能力所带来的问题，仅仅依靠提高三 维图形引擎的处理速度和能力，以及增加网络带宽等硬件方面的措施是不够的。 因此，三维网格简化成为计算机图形学和网络技术中令人感兴趣的重要课题。研 究新的占用空间小、绘制速度快，适合于计算机网络传输和移动设备处理的三维 网格数据表示方法有着十分重要的意义。 1 2 网格模型简化概述 网格模型简化是指在尽可能保持原模型几何形状不变的前提下，采用适当的 算法减少该模型的面片数、边数和顶点数。简化对于几何模型的存储、传输、处 理，特别是对实时绘制有着重要的意义。早在2 0 世纪7 0 年代，就有学者讨论网格 模型的简化问题1 2 ，然而直到9 0 年代以后，网格简化才得到深入的研究，并有了很 多成功的应用。 由于网格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也 可以对其进行三角化，因此网格模型简化的本质是：在尽可能保持原始模型特征 的情况下，最大限度地减少原始模型的三角形和顶点的数目。它通常包括两个原 则：顶点最少原则，即在给定误差上界的情况下，使得简化模型的顶点数最少；误 差最小原则，给定简化模型的顶点个数，使得简化模型与原始模型之间的误差最 小【3 1 。 国内外对模型简化的研究已有了一系列的成果。网格模型简化算法分类有多 种，例如根据模型简化的过程可以分为逐步求精h ，5 】和几何化简纠】；根据视点相 关性可以分为视点无关的化简6 ，1 1 1 和视点相关的化简院1 明等等。但是众多的分类 方法难以囊括所有的简化算法，本文将简化算法分为静态简化算法和动态简化算 法两大类i 啪。 1 2 1 经典的网格静态简化方法 早期的模型简化算法大多属于静态简化，它是根据一定的精简原则，由复杂 模型构造出简单模型用于绘制，它只考虑模型自身的信息，与视点无关，也不能 基于特征保持的网格简化算法研究及其应用第1 章综述 恢复原模型的信息。静态简化也可以构造多分辨率模型，但是它要事先存储多个 不同分辨率的近似模型，需要占用较多的内存，而且在不同分辨率的模型进行切 换的时候，由于相邻两层模型之间的面片数差别较大，因此会引起跳跃的感觉【1 2 1 。 ( 1 ) 顶点聚类法 顶点聚类方法 1 3 , 1 4 1 然后通过空间划分将原始模型分成若干个区域，这样，原 始模型的所有顶点就分别落在这些小区域内，将区域类的顶点合并成一个新顶 点，再根据原始网格的拓扑关系对这些新顶点进行三角化，就得到简化模型，其 过程如图1 所示。这是一种通用的不保持拓扑结构的简化算法，它可以处理任意 拓扑类型的网格模型，且速度较快。但该算法没有较好的误差控制，因此这种方 法生成模型的质量不高。k o k l i ml o w 和t i o w s e n gt a n 改进了顶点聚类简化方法 1 3 1 他们在保持原算法通用性的基础上，定义了一种更优的重要度。我国的周昆 等人采用了八叉树对网格包围盒作自适应划分，同时采用二次误差测度来控制新 顶点的生成【峙】。p e t e rl i n d s t r o m 拓展了顶点聚类方法，且将其应用于超大规模 网格模型化简【1 6 】。 4w 多 1 心 、 。i l 厶_ _ _ 一 1 l ， 一 l ( a ) 简化前 ( 2 ) 区域合并法 | 边 | 【l 一 ，一 i |，摹 l ，_ 一 一 i _l ， | 图1 2 顶点聚类方法简化 ( b ) 简化后 区域合并法的主要思想是选择一个三角面为种子面，根据一定的准则将周围 的面合并起来形成一个更大的面( 称为超面) ，再将超面边界拉直，并对其重新三 6 基于特征保持的网格简化算法研究及其应用 第1 章综述 角化，从而达到面片化简的目的。k a l v i n 和t a y l o r 提出了一种比较典型的区域合 并方法【1 7 1 ，这种算法无法避免带洞超面的产生，影响了算法的运行效率【1 8 】。李 捷、唐泽圣等人对此进行了改进，采用区域分割算法消除超面周界投影轮廓的自 相交，而避免了带洞超面的产生【1 9 】。h i n k e r 和h a n s e n 提出将近似平行的法向 三角形形成一个面片组，用重新三角化的方式进行区域合并的方法印l 。后来， c i a m p a l i n i1 2 1 1 、z h o u 等人作了改进f 2 2 1 。 ( 3 ) 重新布点法 g r e g t u r k 在1 9 9 2 年提出了重新布点法【2 3 l ，算法按照曲率在模型表面上取一 组新顶点，将新顶点与旧顶点连接成一个中间网格，然后去掉旧顶点，在对产生 的空洞( h o l e ) 进行三角化，以此达到简化的目的。t a o s o n gh e 等人则将模型转 化为体数据表示，采用移动立方体法抽取等值面，从而得到化简模型，它可以有 效地去除模型的高频细节【2 4 】。 ( 4 )几何元素删除法 所谓几何元素删除方法就是通过对几何元素的删除来实现模型的简化，即根 据原模型的几何拓扑信息，在保持一定的几何误差的前提下删除对模型几何特征 影响相对较小的几何元素：点、边、面。现在主要分为：点删除法、边折叠法( 顶 点对的删除1 、三角形简化方法三种。 s c h r o e d c r 在1 9 9 2 年就提出了顶点删除的网格简化方法【2 5 t 。在三角形网格模 型中，若一个顶点与它周围三角面片可被认为是共面的( 这可以通过设定点到平 面距离的阈值来判断) ，且删除该点不会改变拓扑，则可删除该点，同时该顶点 的所有邻接面均被从原始模型中删除，因此模型的网格中会形成一个空洞 ( h o l e ) ，必须对空洞重新三角化，继续这种操作直到模型中无满足上述条件的 顶点为止。这种算法计算较快，也不需要占用太多的内存。但是由于重新三角化 需要将局部表面投影到一个平面，这种算法只适用于流形，而且它在保持表面的光 滑性方面存在一定困难【3 0 】。 7 基于特征保持的网格简化算法研究及其应用第1 章综述 ( a ) 原始网格( b ) 删除一个顶点( c ) 对空洞三角化 图i - 3点删除法示意图 边折叠简化算法其实就是“点合并算法”，在折叠过程中，就是一条边的两 个点移到同一个位置，这样边的两个端点久合并成一个点( 如图1 - 2 所示) ，一 直这样循环下去，直到模型满足精度要求。h o p p e 在1 9 9 3 年采用能量优化的方 式来确定折叠次序和新顶点的位置 2 e l 。g a r l a n d 和h e c k b e r t 在1 9 9 7 年提出了一 种基于二次误差测度( q u a d f i ce r r o rm e t r i c ，简称q e m ) 的化简算法叨。l i n d s t r o m 和t u r k 在1 9 9 8 年用化简前后体积和面积的变化作为误差测度，也得到了与q e m 类似的数学表达旺8 1 。在国内，李现民采用改进的蝶形细分算法来计算新顶点的位 置【2 9 1 。实际上，边折叠一次性处理两个顶点，简化速度较快，通过边折叠来删除 顶点比重新三角化要好得多1 3 0 1 。 骂 ( a ) 边折叠前 图1 4边折叠法示意图 ( b ) 边折叠后 三角形折叠简化方法是边折叠方法的扩展，在简化时三角面作为被删除的基 本元素。它是边折叠算法的延续，一次三角形折叠可以删除4 个三角形、两个顶 点，而一次边折叠只能删除2 个三角形、一个顶点，如图1 3 所示。相比之下， 三角形折叠简化方法更快捷，但是与边折叠比较三角形折叠的计算方法要复杂一 些。h a m a n n 提出的三角形折叠简化方法中，他将三角形的权重定义为等角度与 曲率的乘积，然后对网格模型上的所有三角形按权重进行排序，并依次折叠，这 样细长且低曲率的面首先被删除【3 1 】；i s l e r 等人则将边折叠与三角形折叠结合起 来构造了半实时多分辨率模型1 3 2 】；我国周昆等人将三角形折叠与q e m 算法结合 基于特征保持的网格简化算法研究及其应用第1 章综述 起来，并给出了一种传递简化误差的方法【3 3 】；另外，根据细分曲面的特性，李桂 清等人提出一种基于细分规则的三角形折叠方法1 3 4 】，国内在这方面的工作还有 文献【3 6 】等。 娑 ( a ) 边折叠前 ( 5 ) 小波分解 图1 - 5三角形折叠法示意图 o ) 边折叠后 小波分解方法首先由l o u n s b e r y 和d e r o s e 在1 9 9 4 年提出【3 7 】，它为层次细节 模型提供了一个完美的数学表达方式。它的主要原理就是利用小波分析的方法将 一个三维模型分解成低分辨率部分和细节部分，低分辨率部分是原始模型的一个 子集，细节部分通常通过高通率波来得到，表现为高频信号。重建过程就是通过 选择适量的高频信号与低频信号以合成相应精度的三维模型，通过略去其余的更 高频分量来达到简化的效果。这种方法简单、高效，但是它只适用于具有细分连 通性的三角网格【3 7 1 。随后，m a t t h i a s 等人作了改进，使得该算法可以适应任意拓 扑的网格f 3 7 ，3 3 】。 1 2 2 经典的网格动态简化算法 动态简化的基本思想是；在模型的化简过程中，可以实时地得到具有所需要 的分辨率的近似模型。每个模型的化简程度由模型之外的因素决定，例如视点。 动态简化一般是通过一些简单的局部的几何变换来实现，从而生成具有连续的不 同分辨率的近似模型。动态简化是静态简化的延续，它的很多基本操作采用的是 静态化简的方法。 9 基于特征保持的网格简化算法研究及其应用 第1 章综述 ( i ) 层次表示法 i s l e t 等人提出了一种混合方法来实现半实时的层次细节表示 3 2 1 。层次表示法 的思想是预先产生几个关键的简化模型，并对其中的三角面按视觉重要度排序， 在实时绘制中，选择一个比所需分辨率高的最简的逼近模型，并对该逼近模型按 重要度从小到大的顺序删除三角面，直到满足当前精度为止，这样可以部分地解 决计算量大的问题。r r o n f a r d 首先对每条边定义由于它的删除所造成的简化网 格模型与原始网格模型之间的几何偏差，并将其按照从小到大进行排序，然后根 据用户对模型复杂程度的需要，依次进行边删除操作，这个算法可以生成原始网 格一系列连续的简化模型【3 9 j 。 ( 2 )渐进网格法 在动态化简中最著名的算法当属h o p p e 在s i g g r a p h 9 6 上提出的渐进网格 p m ( p r o g r e s s i v em e s h e s ) 算法1 。该方法所表示的l o d 模型序列具有很强的 连贯性，通过一系列的顶点分裂操作可以逐步地完全恢复原来的拓扑信息。如下 式所示，一个几何模型的渐进网格表示由一个基础网格和一系列顶点分裂操作构 成： m o 兰型盘肼1 兰翌丛，肘，一曼型! 嫱 m ” 其中， ，是基础网格，v s p l i t 是顶点分裂操作，材。是原始网格。 在实时绘制时，通过逆向跟踪简化信息序列，对每条简化信息执行点分裂逆 操作，可以逐步恢复所删除的模型细节，实时得到原始模型的连续精度的简化模 型，由此实现了l o d 模型的平滑过渡。陶志良针对p m 的二义性，改进了算法， 提出了支持快速恢复的可逆递进网格脚l 。费广正则利用递进网格进行多层次模型 编辑1 4 2 】。 ( 3 )基于视点的化简方法 1 9 9 6 1 z ，j u l i ec x i a 提出了一种实时的基于视点的三角网格模型简化算法嘲， 0 基于特征保持的网格简化算法研究及其应用第l 章综述 该算法可以实时地在同一模型的不同区域选择不同的精度层次；h o p p e 定义了一 个基于视锥模型表面法向和屏幕空间几何误差的细化标准，该标准包括视锥原 则、面的方向性原则和屏幕空间几何误差原则，并利用此准则进行选择性的边折 叠和点分裂，建立多分辨率的模型f 1 0 1 。 1 3 移动手持设备图形应用 移动通讯技术的快速发展，使移动办公、移动电子政务、电子商务、移动娱 乐等成为当前i t 产业的焦点之一。p d a 、移动电话等手持式设备( h a n d h e l d ) 在近几年迅猛发展，越来越多的生产厂家开始发展新一代的移动电话和掌上电脑 的一体化产品( s m a r tp h o n e ) ，随之而来的一系列移动计算方面的问题，逐渐引 起了众多科研学者的注意。无论从应用标准还是硬件设备来说，移动终端上的三 维图形计算都是一个具有挑战性的课题。 1 3 1 移动图形应用标准 在应用标准方面，具有代表性的标准是o r e n g le s 。o r ) 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 o le s s c 更是扩展到了军 用、航用及自动应用程序等这些安全性可靠性要求很高的应用方面，如图1 - 4 所 示，是一些应用的实例。 图i - 60 p e n g le s 应用实例 基于特征保持的阿格简化算法研究及其应用第1 章综述 o p e n g le s 家族的标准详细描述如下表1 1 所示： 版本性能 o p e n g le s1 0 ，针对软件演化3 d 功能性、修改功能硬件 o p e n g l e s1 xo p e n g l e s l 1 7 所有i x 说明书与后面的兼容 o p e n g l e s1 1e x t e n s i o n 针对新一代的可编程硬件的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 r l g le s - s co p c n g le s - s c1 0 一军用航用和自动应用程序 本地平台w i n d o w 系统界面 图像资源管理的可携式图 e g le g l l o 1 1a n d l 2 一使得快速混合模式的2 d 3 d 渲染能使用 o p e n g le s 雨lo p e n v g 1 3 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 的水平的最新移动版g p i 卜母o f o r c e 5 5 0 0 。图1 7 显示的是n v i d i ag o f o r c e5 5 0 03 d 引擎的画面。 图1 7n v i d i ag o f o r e e5 5 0 03 d 引擎的画面。 。来源于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 。来源于互联 【唾，h t t p ：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 0 h t m l 1 2 基于特征保持的网格简化算法研究及其应用第1 章综述 在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 o l e s 标准的游戏一极 品飞车：最高通缉( n e e df o rs p e e dm o s tw a n t e d ) ，如图1 8 所示。 图1 - 8 极品飞车：最高通缉9 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 、，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 7 6 8 像素的超高屏幕分辨率，每秒最多可 处理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 p e n g le s1 1 + 扩展包，能为环境、光照和物体提供更多真实细节， 并同时保持高水准的互动性。a t i 的这两款产品提供最新的3 d 加速功能，支持 o p e n g le s1 2 为游戏开发者提供更大的创作空间和更强的执行性能。芯片为移 动多媒体手机提供了音频、图像集成解决方案。 无论是应用标准的发展，还是移动硬件设备处理能力的提高，都说明移动图 形应用的需求在增加，因此，移动终端上的三维图形计算的研究是十分必要且应 用前景广泛的。 。来源于新华网，h i t p ：n e w s 】d n h u a n e l c o m 厅坦0 0 6 2 ，2 2 ，n t t4 2 1 1 0 4 1 h 咖i 1 3 基于特征保持的网格简化算法研究及其应用 第1 章综述 1 4 小结 本章首先介绍了本文的研究背景，其次对经典网格模型简化方法逐个进行介 绍分析，由此积累理论基础；并分析了移动平台的局限及当今移动设备硬件处理 能力的进步，介绍了移动图形应用标准方面最具有代表性的标准o p e i l g l e s 。总之，由于移动设备相对的三维图形处理能力较低，且三维网格模型数据 量和复杂度的急剧增长，解决这些问题仅仅依靠提高三维图形引擎的处理速度， 以及增加网络带宽等硬件方面的措施是远远不够的。因此，研究适合于计算机网 络传输和移动设备处理的网格简化策略和表示方法有着十分重要的意义。研究重 点包括：提出一个合理的网格简化算法，在减少模型顶点个数和三角形个数的同 时尽量保持原模型的外观，并对提出的算法进行实现与应用。 1 4 基于特征保持的网格简化算法研究及其应用第2 章基于边折叠的网格简化算法 第2 章基于边折叠的网格简化算法 在移动手持设备上进行三维图形显示，由于其显示屏幕较小，对模型精度的 要求相对较低；另外，其处理能力相对较弱，要处理并显示高细节度的模型十分 吃力。针对移动手持设备的这些特点，可选择一个虽然简化效果一般，但简化过 程简单、简化效率较高的网格简化方法。本章以边折叠网格简化算法作为基础， 对折叠的策略进行了研究，为了使网格模型尽量保形，还提出了局部寻优策略， 使每一步边折叠操作都尽可能保证了网格的外观 2 1 边折叠概述 边折叠( e d g ec o l l a p s e ) 是一种简单的网格简化方法。h h o p p e 用边折叠 的简化方法为一个任意的三角形网格构造它的渐进网格表示，而且可以做到最后 的基础网格很小很小【1 1 】，h t t o p p e 等人的累进网格算法得到了广泛的应用。这些 方法都是通过重复使用单位的边折叠操作来实现对复杂模型的简化的。 (a)简化前(b)简化后 图2 - i边折叠简化前及简化后图形 在边折叠操作中，通过将两个点变为一个点的方式来删除边，图2 1 所示为 这种操作的一个示意，选中边u v 的两个顶点u 和v ，将u “移去”或者“折叠” 到v 上，具体步骤如下： ( 1 ) 删除所有同时包含u 和v 顶点的三角形。也就是说，去除边u v 上的 所有三角形( 例如图2 - 1 中的面1 和面2 ) ； ( 2 ) 删除以u 作为顶点的三角形，用顶点v 来替代u ； 1 5 基于特征保持的阿格简化算法研究及其应用第2 章基于边折叠的网格简化算法 ( 3 ) 删除顶点u 。 重复以上步骤直到满足需要达到的顶点数目或是达到保持模型的外观下。通 常情况下，每一次边折叠操作。将会删除了一个顶点，2 个面和3 条边。因此， 直接应用这种方法，通过n 次边折叠操作就可以将一个具有2 n 个三角形的模型 缩减到0 个面，可见简化效率比较高。 边折叠过程是可逆的，通过顺序存储边折叠信息，就可以从简化模型开始重 构出复杂模型。这种特性在模型的网络传输方面非常有用，因为边折叠后的模型 可以有效的压缩格式进行传送，而且在接收数据的时候以渐进方式进行重构并显 示出来】。这种特性对于用手持设备进行三维图形显示也具有十分重要的意义。 实际操作中可以先把简化后的模型传送给手持设备，用户就可以先对该简化模型 进行观察，随后用户可以选择接收更多的模型细节以供显示，也可以选择不再接 受而直接使用简化的模型，毕竟更多的细节需要更强的处理器以及更大的存储器 进行处理。 2 2 保持模型外观的边折叠策略 在图2 - 1 中，u 折叠到v 的位置，当然v 也可以折叠到u 。仅局限于使用这 两种可能的简化系统使用的是子集定点( s u b s e tp l a c e m e n t ) 策略。而与之对应 的是最优定点( o g t i m a lp l a c e m e n t ) 策略，该策略考察更大的可能性范围，它 不是将一个点折叠到另外一个点，而是将两个顶点收缩到一个新的位置。子集定 点的优点是实现简单，速度很快；而限制了选择点的可能性，则可以对实际所做 的选择进行编码l ，这也正是渐进传输的基础；缺点是解空间范围小，因此只能 给出一个低质量的近似结果。最优定点策略优点是可给出更高质量的模型，但处 理起来更复杂。针对手持设备对精度要求不高的特点，而且为了可以方便实现渐 进传输，这里采用子集定点策略。 2 2 1 基于相邻三角形法向量变化因子 在图2 - 1 中，选择u 折叠到v 或者v 折叠到u ，有可能对原模型影响不大， 1 6 基于特征保持的网格简化算法研究及其应用第2 章基于边折叠的网格简化算法 但如果对折叠点的选择不当，更多的情况是使简化后的模型跟原模型的外观有很 大差别。图2 - 2 所示的是同一条边的可能收缩示例。可以看到，当对折叠点选择 不当的时候，模型外观将发生很大的变化。其中第一个图是原模型；第二个图是 u 折叠到v 的位置，可见此时新模型相对原模型外观变化不大，甚至没有变化； 最后一个图是v 折叠到u 的位置，可见模型已经有了很大的变化，显然这是一个 对折叠点选择不当的情况。 vv 图2 2不同折叠对模型的影响 由此可见，在子集定点策略中，如何对折叠点进行选择从而尽量使模型外观 的变化最小是十分关键的。在图2 - 2 的例子中，u 折叠到v 后，与点u 相邻的三 角形所在面的朝向变化很小，即三角形的单位法向量变化很小，甚至没变化；而 v 折叠到u 后，与点v 相邻的三角形的单位法向量则发生了很大的变化。面片的 单位法向量定义了面片的朝向，因此模型面片的单位法向量对模型的形状结构、 光照等外观属性起着至关重要的作用，同一三角形单位法向量变化越大，对模型 外观的影响则越大。根据以上的分析，顶点相邻三角形单位法向量变化大小影响 着边折叠后模型的外观，目标是在折叠时尽量使单位法向量变化较小，从而达到 尽量不改变原模型外观的目的。 图2 - 3 表示的是一组网格在折叠前的情形。由于面1 与面2 将被删除，因此 其单位法向量的变化不作考虑。可以看到点a 有5 个相邻三角形的单位法向量可 能发生改变，而点b 则有4 个相邻三角形的单位法向量可能发生改变 4 0 , 4 3 1 。 1 7 基于特征保持的网格简化算法研究及其应用第2 章基于边折叠的网格简化算法 图2 - 3折叠前点v 和点u 的单位法向量 图2 - 4 表示的是把u 折叠到v 的情形。其中虚线箭头所示为点u 的相邻三角 形折叠到v 之后的4 个单位法向量。图2 - 5 则是与之对应的v 折叠到u 的情形。 其中虚线箭头所示为点v 的相邻三角形折叠到u 之后的3 个单位法向量f 4 0 】。 图2 - 4u 折叠到v 时相邻三角形单位法向量的变化 v 向u 折叠 - - - - - 图2 5v 折叠到u 时相邻三角形单位法向量的变化 根据以上例子，这里把与边上两顶点相邻的三角形的单位法向量变化量作为 该边上两顶点如何折叠的依据，依据两点单位法向量变化量的大小进行取舍，较 小的点向法向量变化量较大的点折叠。此权值不但跟每个相邻三角形单位法向量 的变化有关，同时也跟与该点相邻的三角形的数量有关。因此，这里定义顶点的 8 基于特征保持的网格简化算法研究及其应用第2 章基于边折叠的网格简化算法 法向量变化因子，具体表示如下i 柏1 ： n o r m a l w e i g h t = 0 n o r m a l _ n e