（计算机应用技术专业论文）基于移动终端的网格简化算法.pdf

针对移动终端的l 旬4 格简化算注摘要 论文题目：基于移动终端的网格简化算法 专业：计算机应用技术 硕士生：陈丽 指导教师：罗笑南教授 摘要 随着现代科技的发展和3 c 的融合，一场围绕“显示为中心”的无线大革命 拉开了序幕。这场无线大革命已经从9 0 年代的数据网络向2 1 世纪的视觉网络迈 进，同时数字家庭也从第一代向第二代开始了跨越。在各种应用中，三维几何模 型的数量规模和复杂程度在急剧地增长，人们对于实时操纵几何数据的要求逐日 增高；另一方面，移动设备迅猛发展，用相对较低的处理能力来处理三维图形成 为一个巨大的挑战。因此，针对手持设备的特点以及在此基础上进行图形简化和 显示的研究具有十分重要的意义。 本文围绕移动手持设备上三维图形的显示，针对移动手持设备的特点，对模 型的简化策略和保持模型的特征三角形进行了研究，提出一个在保持模型外观的 基础上对网格模型进行简化，并且简化后的模型可以适应在移动手持设备上进行 显示的完整算法。本文提出的基于三角形折叠的简化算法，利用三角形顶点的邻 接三角形折叠前后的单位法向量变化大小来判定三角形三个顶点中的关键顶点， 并将两个非关键顶点向关键顶点进行折叠以达到简化效果。此外，通过计算三角 形三个顶点的相邻三角形的单位法向量差的绝对值之和判断出三角形的起伏程 度，识别出模型的特征三角形，提出了保留特征三角形的简化策略；通过比较点 的邻接边和邻接三角形的数量，识别出边界三角形，提出保留边界三角形的完整 简化策略。文章最后给出了经过此算法处理后的模型在移动手持设备上的模拟应 用情况。完整的基于三角形折叠和特征保留的简化算法可以在保持模型外观的同 时有效的降低模型的规模，并且为在移动手持设备上几何模型的实时显示提供了 基础。随着移动计算技术的发展，移动三维图形的应用将会越来越多，本文的简 化算法可以得到广泛的应用。 关键词：移动终端，三维模型，三角形网格，网格简化，三角形折叠 壮十移动终端的网格掎化算法 a b s t r a c l t i t l e ：a d a p t i v es p e c t r a lc o m p r e s s i o n i nw i r e l e s sn e t w o r k 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 l t l e ：c h e nl i s u p e r v 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 w i t ht h ea d v a n c e m e n to ft h em o d e mt e c h n o l o g ya n dt h ec o n s o l i d a t i o no f3 cs t r a t e g y , t h ew i r e l e s sr e v o l u t i o nb a s e do nt h ed i s p l a yi sc o m m e n c e d t h er e v o l u t i o no ft h ed i g i t a l n e t w o r ki nt h e1 9 t hc e n t u r ys t r i d e st ot h ei m a g en e t w o r k ，w h i c hi su t i l i z e di nt h e2 1 t hc e n t u r y m e a n w h i l e ，t h ed i g i t a lf a m i l yi sa d v a n c e df o r mt h ef i r s tg e n e r a t i o nt ot h es e c o n dg e n e r a t i o n i nm a n ya p p l i c a t i o n s ，t h es i z ea n dc o m p l e x i t yo ft h e3 dm o d e l sa r er a p i d l yi n c r e a s i n g t h e t a s k st oc o n t r o lt h er e a l t i m eg e o m e t r ym o d e l sa r ec h a l l e n g i n g d u et ot 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 s ，i ti sn o tc o n v e n i e n tt ou t i l i z eal o w - e n dm a c h i n ei n3 dg r a p h i c s c o m p u t a t i o n t h e s es e r i e so fi s s u e ss h o w t h er e s e a r c h s i g n i f i c a n c eo fg e o m e t r ym e s h s i m p l i f i c a t i o n b a s e do nt h ef e a t u r e so ft h eh a n d h e l dd e v i c e sa n d3 dg r a p h i c sd i s p l a yo nh a n d h e l d d e v i c e s ，t h et h e s i sp r e s e n t st h es i m p l i f i c a t i o na l g o r i t h ma n dt h ek e yt r i a n g l e sw h i c hp r e s e r v e t h em o d e la p p e a r a n c e a l s oi tp r e s e n t sa ni n t e g r a t e dg e o m e t r ym e s hs i m p l i f i c a t i o na l g o r i t h m w h i c hc a np r e s e r v et h em o d e la p p e a r a n c ea n dc a nd i s p l a yt h e3 dw o r k e dm o d e l so nm o b i l e h a n d h e l dd e v i c e s t h es i m p l i f i c a t i o na l g o r i t h mi sb a s e do nt r i a n g l ec o l l a p s e f i r s t l y , o n e v e r t e xo fat r i a n g l ei sc h o s e na st h ek e yv e r t e x k e yv e r t e xi sf o u n dv i a t h ec h a n g e so f f o r e a n d a f tn o r m a lo fa l la d j a c e n tt r i a n g l e s ，w h i c ha r ec o n n e c t e da tt h e i rc o m m o nv e r t e x t h e no t h e rt w ov e r t e x e so f t h es a m et r i a n g l ea r ec o l l a p s e dt ot h ek e yv e r t e xf o rs i m p l i f i c a t i o n s e c o n d l y , t h e s i sp r e s e n t sak e yt r i a n g l ep r e s e r v a t i o nm e t h o d ，w h i c hi d e n t i f i e st h ek e yt r i a n g l e u s i n gc o m p u t i n gd i f f e r e n c e so ft h ea d j a c e n tt r i a n g l e s n o r m a lo ft h r e ev e r t i c e s a l s o i t p r e s e n t st h eb o u n d a r yt r i a n g l ep r e s e r v a t i o nm e t h o d ，w h i c hd e t e r m i n e st h eb o u n d a r yt r i a n g l e b yc o m p a r i n gt h en u m b e ro ft h ea d j a c e n tp o i n t sw i t ht h en u m b e ro ft h ea d j a c e n tt r i a n g l e s f i n a l l y , i tp r e s e n t st h er e s u l to 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 es i m p l i f i e d t h e w 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 f3 dm o d e lw 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 t 皋十移动终端的嘲格简化算法a b s t r a c i a l s ou s e df o rt h er e a l - t i m ed i s p l a yo nm o b i l eh a n d h e l dd e v i c e sd u et ot h ed e v e l o p m e n to f m 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 fm o b i l e3 dg r a p h i c st h e r e b yt h er e s u l t o f t h i st h e s i sw i l lb em o r ee 币c i e n t k e y w o r d s ：m o b i l et e r m i n a l ，3 dm o d e l ，t r i a n g l em e s h ，m e s hs i m p l i f i c a t i o n ， t r i a n g l ec o l l a p s e 摧十移动终端的恻格简化算法 n u 吾 刖吾 计算机图形学，从它的开始发展到现在，已经在许多地方扮演着重要的角色， 发挥着重要的作用。其应用领域涵盖着科学探索、工程设计、机械制造、模拟仿 真、医药卫生、城市规划、环境保护、文物修复、教育培训、艺术创造、以及游 戏娱乐等许多方面。计算机图形学应用的特点之一是广泛地使用三维几何数据。 随着计算机图形学及相关理论和技术的快速发展，使用的三维几何数据的数量规 模和复杂程度在不断地急剧增长着。 在日渐广泛的计算机图形学的应用之中，通常要求能够实时地观测和操纵这 些三维几何模型。同时，由于人们对几何数据的精度提出了更高的要求。这两方 面的事实不仅使人们要花费更多的代价去存储这些几何数据，而且它们对现有的 三维图形引擎的处理能力和速度提出了巨大的挑战。此外，随着现代科技的发展 和3 c 的融合，一场围绕“显示为中心”的无线大革命拉开了序幕。这场无线大 革命已经从9 0 年代的数据网络向2 1 世纪的视觉网络迈进，同时数字家庭也从第 一代向第二代开始了跨越。第一代数字家庭，以p c 为中心，靠有线数据网络传 输数据，只能满足普通数据传输的需求，无法获得高品质、流畅的视频图像；第 二代数字家庭则以显示为中心，靠无线视觉网络传输视频和音频，可以获得高品 质的视频图像。在数字家庭中广泛使用的移动手持设备得到迅猛发展，随之而来 的一系列移动计算方面的问题，逐渐引起了众多科研学者的注意，针对移动终端 上的三维图形处理和显示便是其中一个极富挑战性的课题。 由于移动设备相对的三维图形处理能力较低，且三维几何数据量和复杂度的 急剧增长，解决这些问题仅仅依靠提高三维图形引擎的处理速度，以及增加网络 带宽等硬件方面的措施是远远不够的。因此，三维模型的简化问题成为计算机图 形学和网络技术中令人感兴趣的重要课题。研究适合于计算机网络传输和移动设 备处理的三维几何数据的简化策略和表示方法有着十分重要的意义。 本文围绕在无线网络中的移动设备上进行三维图形的显示，根据移动手持设 坫十移础终端的删格简化算法刖吾 备存储器容量小、处理能力较低的特点，针对由三角形网格表示的几何模型，对 模型的简化策略和维持模型的重要特征方面进行研究，提出一个在保持模型外观 的基础上对几何模型进行有效的简化，并且在移动设备上进行显示的完整算法。 本文的章节结构如下 第1 章，介绍本课题的研究背景和网格简化算法，以及移动设备上图形应用 的相关方法； 第2 章，研究三角形折叠策略，提出一个选择关键顶点、其余两顶点向关键 顶点折叠的简化算法。给出简化后的效果图，分析简化后的模型数 据： 第3 章，研究模型的特征三角形和边界三角形，提出通过计算三角形每个顶 点邻接三角形的单位法相量差的绝对值之和来识别特征三角形的 算法，并提出通过比较点的邻接三角形和邻接点的数量来识别边界 三角形的策略； 第4 章， 对本文提出的算法进行验证，观察简化的效果，分析简化的模型数 据，模拟给出在移动手持设备上应用的情况； 第5 章，总结本文的工作，提出对未来的展望。 摹于移动终端的刚格简化算法笫l 章综述 第1 章综述 随着现代科技的发展和3 c 的融合，计算机图形学在各种应用中扮演着越来 越重要的角色，三维几何模型的数量规模和复杂程度在急剧地增长，模型简化方 法得到深入研究；与此同时，移动设备迅猛发展，用相对较低的处理能力来处理 三维图形成为一个巨大的挑战。针对手持设备的特点以及在此基础上进行图形简 化和显示的研究具有十分重要的意义。 1 1 研究背景 计算机图形学，从它的诞生发展到现在，已经在许多领域扮演着越来越重要 的角色，发挥着越来越重要的作用。从简单的增强视觉效果到利用其直观性进行 人机交互，三维模型在工业制造、产品设计、建筑设计、模拟仿真、地理信息系 统以及游戏娱乐等诸多领域中扮演着日益重要的角色。随着计算机技术的快速发 展和进步，人们对几何数据的精度和细节方面提出了更高的要求，各种高级造型 工具出现和模型获取技术的发展等各种因素，导致了这些在许多应用中使用的三 维几何数据的数量规模和复杂程度在急剧地增长着。模型变得越来越精细、越来 越复杂，数据的规模在不断地急剧增长着。由此建立三维模型所得的网格模型通 常是由几十万个、几百万个、甚至上亿个面片组成，在斯坦福大学的数字米开朗 基罗计划中注明的d a v i d 雕像的三角面片更是高达2 0 亿。在计算机图形学和 几何造型中，物体表面常用多边形网格，尤其是三角网格模型描述，本文的简化 模型也以三角网格模型为基础。 对于很多应用来讲，通常要求能够实时的观测和操纵这些三维几何数据，而 许多应用中使用的三维几何数据的数量规模和复杂程度还在急剧地增长着。这使 得人们不仅要花费更多的代价去存储这些几何数据，而且它们对现有的三维图形 引擎的处理能力和速度提出了巨大的挑战。再者，随着科学技术的发展，越来越 多地需要通过网络，特别是国际互联网，来存取那些存放在异地的三维几何数据。 这使得本已十分有限的网络宽带变得更加的紧张。 璀于移动终端的删格简化算法 第1 章综述 近些年来，现代科技的发展和3 c 的加速融合，一场围绕“显示为中心”的 无线大革命拉开了序幕。这场无线大革命已经从9 0 年代的数据网络向2 1 世纪的 视觉网络迈进，同时数字家庭也从第一代向第二代开始了跨越。第一代数字家庭， 以p c 为中心，靠有线数据网络传输数据，只能满足普通数据传输的需求，无法 获得高品质、流畅的视频图像；第二代数字家庭则以显示为中心，靠无线视觉网 络传输视频和音频，可以获得高品质的视频图像，画面的清晰度前所未见。数字 家庭中移动手持设备的迅猛发展，随之而来的一系列移动计算方面的问题，逐渐 引起了众多科研学者的注意，而移动终端上的三维图形显示便是其中一个具有挑 战性的课题。从市场上移动手持设备的发展趋势来看，已经初步具备了支持三维 图形绘制的硬件条件，但由于图形的精细度较大，设计人员仍需要花费一些诸如 存储器不足，以及处理器运算能力有限等问题。存储容量的不足是支持三维图形 显示的主要问题，它决定了用户能在手持式产品中存储的三维图形的规模，这时 就需要在图形数据量和图形精度方面进行折中。另一方面，目前许多便携式电脑 及移动电话的处理器缺少浮点运算、除法运算、方根运算以及三角函数运算，这 些都制约了移动手持设备像桌面型电脑处理器那样适用于三维应用。另外，三维 图形绘制所需要的一些高级效果，如转换、照明和裁剪等，要求高度精确的浮点 运算，而大部分嵌入式平台的图形处理能力仍未达到该水平。 庞大的图形数据量对处理器的处理能力、计算机的容量以及网络传输技术都 提出了很高的要求，成为实现移动设备图形处理、实时交互、网络三维动画、分 布式虚拟现实等应用的瓶颈。要解决这些由于三维几何数据数量和复杂度的急剧 增长以及手持设备相对较低的三维图形处理能力所带来的问题，仅仅依靠提高三 维图形引擎的处理速度和能力，以及增加网络带宽等硬件方面的措施是不够的。 而且在很多情况下，高分辨率的模型并不是必要的，模型的准确度以及需要处理 的时间也要有个折衷，因此，必须用一些相对简单的模型来代替原来模型，这就 要求对模型进行简化。化简对于几何模型的储存、传输、处理，特别是有利于进 行实时绘制。所以，研究新的占用空间小、绘制速度快，适合于计算机网络传输 和移动手持设各处理的三维几何数据表示方法有着十分重要的意义。 堆十移动终端的网格简化算法第1 章综述 1 2 网格模型简化概述 早在2 0 世纪7 0 年代，就有学者讨论网格模型的化简问题【2 】，然而直n 9 0 年代 以后，网格模型的化简才得到深入的研究，并有了很多成功的应用。由于现在网 格模型大部分由三角面片表示，而且即使原始模型不是三角面片，也可以对其进 行三角化，形成三角形网格模型。因此，网格模型简化的本质就是：在尽可能保 持原始模型特征的情况下，最大限度地减少原始模型的三角形和顶点的数目，因 此需要删除那些对模型影响不大的三角形，保留那些反映模型几何特征的三角 形。这样，它通常包括两个原则：( 1 ) 顶点最少原则，即在给定误差上界的情 况下，使得简化模型的顶点数最少。 ( 2 ) 误差最小原则，给定简化模型的顶点 个数，使得简化模型与原始模型之间的误差最d d 3 i 。 国内外对模型简化的研究已有了一系列的成果，如几何元素删除法，顶点聚 类方法，表面重新划分法等等。网格模型简化算法分类有多种，但是众多的分类 方法难以囊括所有的简化算法，本文将简化算法分为静态简化算法和动态简化算 法两大类3 6 l 。 1 2 1 网格的经典静态简化算法 早期的模型简化算法大多属于静态化简，它是根据一定的精简原则，由复杂 模型构造出简单模型用于绘制，它只考虑模型自身的信息，与视点无关。 ( 1 )几何元素删除法 几何元素删除方法是通过对几何元素的删除来实现模型的简化，即根据原模 型的几何拓扑信息，在保持一定的几何误差的前提下删除对模型几何特征影响相 对较小的几何元素：点、边、面。现在主要分为：点删除法、边折叠法、三角形 简化方法三种。 早在1 9 9 2 年，s c h r o e d e r 提出了顶点删除的网格简化方法【4 1 。在三角形网格 模型中，若顶点满足一定要求，那么就可将这一点删除，l 司时该顶点的所有邻接 面均被从原始模型中删除，因此模型的网格中会形成一个空洞( h o l e ) ，必须对 一5 一 摧十移动终端的例格简化算法第l 帝综述 空洞重新三角化，继续这种操作直到模型中无满足上述条件的顶点为止。如图 1 1 所示。 ( a ) 原始网格( b ) n 除一个顶点( c ) 对空洞三角化 图1 1点删除法 边折叠简化算法其实就是“点合并算法”，在折叠过程中，就是一条边的两 个点移到同一个位置，这样边的两个端点久合并成一个点( 如图1 2 所示) ，一 直这样循环下去，直到模型满足精度要求。h o p p e 在1 9 9 3 年采用能量优化的方 式来确定折叠次序和新顶点的位置【5 i 。g a r l a n d 和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 ) 的4 - 5 简算法【6 】。l i n d s t r o m 和t u r k 在1 9 9 8 年用化简前后体积和面积的变化作为误差测度，也得到了与q e m 类似的数学表达【”。在国内，李现民采用改进的蝶形细分算法来计算新顶点的位 置【引。实际上，边折叠一次性处理两个顶点，简化速度较快，通过边折叠来删除 顶点比重新三角化要好得多【。 ( a ) 原始网格( b ) 中问边折叠后 图1 2边折叠法 三角形折叠简化方法是边折叠方法的扩展，在简化时三角面作为被删除的基 本元素。它是边折叠算法的延续，一次三角形折叠可以删除4 个三角形、两个顶 点，而一次边折叠只能删除2 个三角形、一个顶点，如图1 3 所示。相比之下， 三角形折叠简化方法更快捷，但是与边折叠比较三角形折叠的计算方法要复杂一 挂十移动终端的网格简化算法第1 章综述 些。h a m a n n 提出的三角形折叠简化方法中他将三角形的权重定义为等角度与 曲率的乘积，然后对网格模型上的所有三角形按权重进行排序，并依次折叠，这 样细长且低曲率的面首先被删除【l0 ：i s l e r 等人则将边折叠与三角形折叠结合起 来构造了半实时多分辨率模型】；国内的研究有周昆等人将三角形折叠与q e m 算法结合起来，并给出了一种传递简化误差的方法【”1 ；另外，根据细分曲面的特 性，李桂清等人提出一种基于细分规则的三角形折叠方法f i ”，国内在这方面的 工作还有文献m ”1 等。 ( 2 ) 顶点聚类法 ( a ) 原始模型 ( b ) 中间三角形折叠后 图1 - 3三角形折叠法 顶点聚类法的主要思想是根据物体的复杂程度将原始模型划分为很多立方 体单元，然后将区域类的顶点合并成一个新顶点，再根据原始网格的拓扑关系对 这些新顶点进行三角化，就得到简化模型。r o s s i g n a ej 等人在1 9 9 3 年提出的顶 点聚类法最具代表性，k o k l i ml o w 和t i o w s e n g t a n 作了改进。国内的周 昆等人采用了八叉树对网格包围盒作自适应划分，同时采用二次误差测度来控制 新顶点的生成州。 ( 3 ) 表面重新划分法 表面重新划分法包括区域合并法和重新布点法。区域合并法的主要思想是选 择一个三角面为种子面，根据一定的准则将周围的面合并起来形成一个更大的面 ( 称为超面) ，再将超面边界拉直，并对其重新三角化，从而达到面片化简的目的。 k a l v i n 和t a y l o r 提出了一种比较典型的区域合并方法，这种算法无法避免带 洞超面的产生，影响了算法的运行效率。李捷、唐泽圣等人对此进行了改进， 桀十移动终端的删格简化算法第1 章综述 采用区域分割算法消除超面周界投影轮廓的自相交，而避免了带洞超面的产生 2 t 。h i n k e r 和h a n s e n 提出将近似平行的法向三角形形成一个面片组，用重新三 角化的方式进行区域合并的方法【2 2 】。后来，c i a r n p a l i n i1 2 3 j 、z h o u 等人作了改进【“1 。 t u r k 在1 9 9 2 年提出了重新布点法旺5 1 ，算法按照曲率在模型表面上取一组新 顶点，将新顶点与旧顶点连接成一个中间网格，然后去掉旧顶点，在对产生的空 洞( h o l e ) 进行三角化，以此达到简化的目的。t a o s o n gh e 等人则将模型转化为 体数据表示，采用移动立方体法抽取等值面，从而得到化简模型，它可以有效地 去除模型的高频细节。 ( 4 ) 小波分解 小波分解方法由l o u n s b e r y 和d e r o s e 在1 9 9 4 年提出【2 ”。它就是利用小波分 析的方法将一个三维模型分解成低分辨率部分和细节部分，低分辨率部分是原始 模型的一个子集，细节部分通常通过高通率波来得到，表现为高频信号。重建过 程就是通过选择适量的高频信号与低频信号以合成相应精度的三维模型，通过略 去其余的更高频分量来达到简化的效果。这种方法简单、高效，但是它只适用于 具有细分连通性的三角网格2 7 1 。随后，m a t t h i a s 等人作了改进，使得该算法可以 适应任意拓扑的网格渊f 3 4 1 。 1 2 2 网格的经典动态简化算法 动态简化的基本思想是在模型的化简过程中，可以实时地得到具有所需要的 分辨率的近似模型。动态化简是静态化简的延续，它的很多基本操作都是基于传 统的静态化简的方法。 ( 1 ) 层次表示法 层次表示法的思想是预先产生几个关键的简化模型，并对其中的三角面按视 觉重要度排序，在实时绘制中，选择一个比所需分辨率高的最简的逼近模型，并 对该逼近模型按重要度从d , n 大的顺序删除三角面，直到满足当前精度为止，这 样可以部分地解决计算量大的问题，i s l e r 等人提出了一种混合方法来实现半实时 是十移动终端的嘲格简化算法第】章综述 的层次细节表示j ，r o n f a r d 通过计算得到边简化时的偏差，依次队边删除进行 操作【2 。 ( 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 ) 算法【3 5 】。该方法所表示的l o d 模型序列具有很强的 连贯性，通过一系列的顶点分裂操作可以逐步地完全恢复原来的拓扑信息。如下 式所示，一个几何模型的渐进网格表示由一个基础网格和一系列顶点分裂操作构 成： 其中，m o 是基础网格，v s p l i t i 是顶点分裂操作，m u 是原始网格。 在实时绘制时，通过逆向跟踪简化信息序列，对每条简化信息执行点分裂逆 操作，可以逐步恢复所删除的模型细节，实时得到原始模型的连续精度的简化模 型，由此实现了l o d 模型的平滑过渡。陶志良针对p m 的二义性，改进了算法； 提出了支持快速恢复的可逆递进网格。 1 3 移动手持设备图形应用 计算机图形学的发展极大地促进了计算机可视化技术的发展。计算机可视化 技术的研究经历了一个很长的历程，形成了很多可视化工具，其中s g i 公司的 g l 三维图形库因为易于使用且功能完备而备受欢迎，利用其开发出来的三维应 用软件也颇受专业技术人员的喜爱。随着计算机技术的快速发展，g l 也进一步 发展成为o p e n g l ，o p e n g l 已被认为是高性能图形和交互式视景处理的标准， 目前包括i b m 、s u n 、h p 和m i c r o s o f t 的大公司都采用o p e n g l 图形标准。 伴随着移动通讯技术的快速发展，移动办公、移动电子政务、电子商务、移 动娱乐以及数字家庭等成为当前i t 产业的焦点之。p d a 、移动电话等手持式 设备( h a n d h e l d ) 在近几年迅猛发展，随之而来的一系列移动计算方而的问题， 9 皋十移动终端的| 叫格简化算法第1 章综述 逐渐引起了众多科研学者的注意。在图形应用标准方面，o p e n g l 形成了具有代 表性的适合嵌入式系统的图形标准一o p e n g le s ( o p e n g lf o re m b e d d e d s y s t e m s ) 。o r e n g le s 是一个从o p e n g l 提取出来的低阶、低容量的先进绘图用 a p i ，这个针对嵌入式系统所制定的绘图a p i ，能够使3 d 绘图与游戏，在不同 的行动装置或是嵌入式系统间，应用都非常便利。 o p e n g l e s 有如下六个特点：第一，o p e n g l e s 的产业标准开放和免权利金， 即任何人都可以生产制作并贩售兼容于o p e n g le s 的产品。在多数产业里， o p e n g le s 是一个真正开放、中立与跟平台的绘图标准：第二，o p e n g le s 小 容量与低耗电量。面对这些不同的平台，o p e n g l e s 仅需要非常小的储存容量、 最低的频宽且可同时适应整数与浮点运算，因此使用者可以轻易的将它放入系统 里：第三，o p e n g l e s 可在软硬件间连续绘图。所定义的绘图标准能够在不同平 台下使用，其中包含纯硬件的绘图芯片、运用c p u 功能的纯软件或是c p u 与硬 件之问混合平台；第四，o p e n g le s 易于扩展和整合。o p e n g le s 充许各种延 伸指令的使用。透过a p i 中的延伸指令集，你可以将硬件的特殊应用与o p e n g l e s 整合，或是在特殊平台上使用您特制的功能：第五，o p e n g le s 易使用。 o p e n g le s 具有直觉性运用与逻辑性命令的架构；第六，o p e n g le s 具有充份 的文件资料支持。因为o p e n g le s 是基于o p e n g l 所发展，所以有大量的资料 可供参考，这使得o p e n g l e s 可以很容易被使用。 在硬件设备方面，两大图形显示卡厂商n v i d i a 和a t i 已经开发出了一系列 可用于移动手持设备的处理芯片。大多数的产品都支持o p e n g le s 标准。随着 技术的进步，移动硬件设备的处理能力正在不断提高。 1 4 小结 总之，由于移动设备相对的三维图形处理能力较低，且三维几何数据量和复 杂度的急剧增长，解决这些问题仅仅依靠提高三维图形引擎的处理速度，以及增 加网络带宽等硬件方面的措施是远远不够的。因此，研究适合丁二计算机网络传输 和移动设备处理的三维几何数据的简化策略和表示方法有着十分重要的意义。 o 挂十移动终端的| 而9 格简化算法 第2 章撼于三如形折叠的网格简化算法 第2 章基于三角形折叠的网格简化算法 在移动手持设备上进行三维图形显示，由于其显示屏幕较小，对模型精度的 要求相对较低；另外，其处理能力相对较弱，要处理高细节度的模型十分吃力。 针对移动手持设备的这些特点，可选择一个虽然简化效果一般，但简化过程简单、 简化效率较高的网格简化算法。本章以三角形折叠的网格简化算法为基础，对折 叠的策略进行了研究，提出一个选择关键顶点的三角形折叠简化算法。 2 1 保持模型外观的折叠策略 为了下面叙述的方便和清楚起见，首先引入一些基本概念。 定义1 空间中一组三角形，其中一个是待折叠的三角形，那么与此三角形有 公共顶点的一组三角形定义为此三角形的邻接三角形集合n e i g h b o r t r i 。 定义2 对待折三角形t 的一个顶点p ，其余两个顶点都向此点折叠，则此点 称为三角形t 的关键顶点k e y ( t 1 。 定义3 对三角形中的一个顶点p ，那么包含此点的所有的边定义为点p 的邻 接边n e i g h b o r _ l i n e ( p 1 。 定义4 对三角形中的一个顶点p ，那么包含有此点的所有三角形定义为点p 的邻接三角形n e i g h b o r _ t r i a n g l e ( p ) 。 三角形折叠是一种简单的几何元素删除折叠方法。在三角形折叠操作中，通 过将三个点变为一个点的方式来删除其中的三角形，图2 1 所示为这种操作的一 个示意，其中左图是折叠前的模型，右图是点a 、b 、c 折叠到新点d ，删除了 第7 、8 、9 、1 0 这四个面，并将与a 点、b 点、c 点相联的点全部都改成与d 点相连的模型。对模型来说，原来的1 0 个面变成了6 个面，删除了4 个面和2 璀十移动终端的嘲格简化算法第2 章早十- - f 0 彤折叠的| 叫格简化算法 个顶点。因此，直接应用这种方法，通过n 次三角形折叠操作就可以将一个具有 4 n 个三角形的模型缩减到0 个面，可见简化效率比较高。 图2 - l 三角形折叠示例 在实际应用中，存在两种可能的简化系统使用的策略：一种是子集关键顶点 ( s u b s e tp l a c e m e n t ) 策略，另一种是最优关键顶点( o p t i m a lp l a c e m e n t ) 策略【3 0 l 。 子集关键顶点策略在三角形网格简化算法中是将三个顶点收缩到其中一个点的 位置，该方法实现简单，速度较快，并且可以对实际所做的选择进行编码，这也 正是渐进显示的基础，但此方法限制了选择点的可能性。最优关键顶点策略考察 更大的可能性范围，在三角形网格简化算法中，它不是将三个顶点折叠到其中一 个顶点的位置，而是将三个顶点折叠到三角形中的任何一个位置。最优关键顶点 策略较子集关键顶点策略相比，它可得到高质量的模型，但处理起来较为复杂， 不太适合渐进显示。子集关键顶点的解空间范围小，因此只能给出一个低质量的 近似结果。针对手持设备对精度要求不高的特点，本文采用子集关键顶点策略的 方法。 2 1 1 基于顶点相邻三角形法向量变化的折叠策略 在图2 - 1 中，选择a b c 三顶点a 、b 、c 中的任何一点作为关键顶点，将 其余两点折叠到关键顶点，这样有可能对原模型影响不大，但如果对关键顶点的 选择不当，更多的情况是使简化后的模型跟原模型的外观有很大差别。图2 2 所 示的是选择不同顶点作为关键顶点的示例。可以看到，当对关键顶点选择不当的 时候，模型外观将发生很大的变化。其中左上图是原模型，表示的是一个锥体； 右卜图是选择a 点为关键顶点将b 和c 两顶点折叠到关键顶点a 上的情况，可 见此时新模型相对原模型外观变化不大，甚至没有变化：左下图是选择b 点作 基于移动终端的叫 并简化算法第2 章基十二】= | = i 彤折叠的m 格简化算法 为关键顶点，可见模型已经有了较大的变化；右下图是选择c 点作为关键顶点 此时模型发生了非常大的变化，显然这是一个对关键顶点选择不当的情况。 幽2 - 2 选择不同关键顶点对模型的影响 由此可见，在子集关键顶点策略中，如何对折叠点，即关键顶点进行选择从 而尽量保持模型外观是非常关键的。在图2 2 的例子中，当选择顶点a 作为关键 顶点进行折叠时，与点b 、点c 相邻的三角形组n e i g h b o r _ t r i a n g l e ( b 1 和 n e i g h b o r _ t r i a n g l e ( c ) 所在三角面的朝向变化非常小，即两个三角形组 n e i g h b o r _ t r i a n g l e ( b ) 和n e i g h b o r _ t r i a n g l e ( c ) 的面的单位法向量变化很小，甚至 没有变化，模型的变化也非常小；当选择顶点b 作为关键顶点进行折叠时，与 顶点a 、顶点c 相邻的三角形n e i 曲b o r _ t r i a n g l e ( a ) 和n e i 曲b o r _ t r i a n g l e ( c ) 的单 位法向量则发生了较大的变化，模型发生了较大的变化：而当选择顶点c 作为 关键顶点进行折叠时，与顶点a 、顶点b 相邻的三角形n e i 【g h b o r _ t r i a n g l e ( a ) 和 n e i g h b o r _ t r i a n g l e ( b ) 的单位法向量则发生了非常大的变化，模型的结构的变化 特别大。由此可以看出，面片的单位法向量定义了面片的朝向，因此模型面片的 单位法向量对模型的形状结构、光照等外观属性起着至关重要的作用，同一三角 形单位法向量变化越大，对模型结构的影响则越大【3 0 】。根据以上的分析，这里提 出一种基于三角形折叠的简化策略，利用三角形顶点的邻接三角形折叠前后的单 1 1 一 拈十移动终端的嘲格简化算法 第2 章摧十二三角彤折叠的刚格弼化算法 位法向量变化程度，识别出三角形中的关键顶点，提出了其余两顶点向关键顶点 折叠的三角形简化策略，以此达到在三角形折叠过程中尽量使单位法向量变化较 小、尽量不改变原模型外观的目的。 图2 - 3 表示的是一组网格在折叠前的情形。假设选择a a b c 中的顶点a 为 关键顶点，那么折叠后，即将顶点b 和顶点c 折叠到顶点a 后，面7 、面8 、面 9 和面1 0 将被删除，因此其单位法向量的变化可以不作考虑。而与a a b c 相邻 的另外5 个三角形的单位法向量可能发生改变，即n e i g h b o r _ t r i a n g l e ( b ) 中有2 个面的法向量发生了变化，n e i g h b o rt r i a n g l e ( c ) 中有3 个面的法向量发生了变 化，如图2 - 4 ，其中虚线箭头所示为b 、c 两顶点折叠到顶点a 后，发生变化的 单位法向量。 图2 - 3 折叠前相邻面的单位法向量 图2 - 5 则是以顶点b 为关键顶点的情形，其中虚线箭头所示为顶点a 、c 折 叠到b 点后发生变化的4 个面的单位法向量；图2 - 6 以顶点c 为关键顶点，其 中虚线箭头所示为顶点a 、c 折叠到b 点后发生变化的3 个单位法向量。 幽2 _ 4 以a 为关键顶点，其余两点相邻三角形单位法向量的变化 牡十干多动终端的i 叫格简化算法第2 章批十三角彤折叠的嗍格简化算法 图2 - 5以b 为关键顶点，其余 图2 - 6以c 为关键顶点，其余两点相邻三角形单位法向量的变化 根据以上分析我们设定，在一个三角形a a b c 中，顶点的权值为除去此点 以外的其余两点的邻接三角形在折叠前后的单位法向量的变化量。依次可以算出 三顶点的权值，再依据三点的权值进行取舍，权值最大的顶点为关键顶点，权值 较小的两个顶点向关键顶点折叠，以此达到简化的目的。此顶点权值不但跟除关 键顶点以外的两顶点相邻三角形单位法向量的变化有关，同时也跟两顶点相邻的 三角形的数量有关。 三角形a a b c 的关键顶点的权值表示如下 k e y w e i g h t = | | n o r m a l _ n e w - n o r m a l _ o m | | ( 2 1 ) n e i g h b o r _ t r i a n g l e 在公式2 1 中，k e y w e i g h t 表示关键顶点的权值，n o r m a l n e w 和n o r m a l o l d 分别是指同一个三角形在折叠后和折叠前的单位法向量。而 | | n o r m a ln e w n o r m a lo l d i i 则表示在同个顶点的邻接三角形单位法向 n e l g h b o l t m n 9 1 e 量改变的总和， | | n o r m a ln e w n o r m a lo l d | 表示除关键顶点以外的其余 批十移动终端的| 尚9 格简化算法第2 章皋十二f f 】形折叠的m 格简化算法 两点相邻三角形单位法向量的变化总和。 公式2 1 的意义如下 关键顶点的权值= 点相邻三角形的单位法向量的变化量 在公式2 1 中，第一个的范围是同一个三角形中的非关键顶点，第二个 的范围是同一个点的所有相邻三角形，而相邻三角形中被删除的四个，即图2 3 中的面7 、面8 、面9 和面1 0 ，其单位法向量的变化量作为0 来计算。也就是说， 在图2 - 4 中，a 点的权值为5 条虚线箭头与原实线箭头变化量的总和；在图2 5 中，b 点的权值为4 条虚线箭头与原实线箭头变化量的总和：而在图2 - 6 中，c 点的权值为3 条虚线箭头与原实线箭头变化量的总和。 这样定义关键顶点的权值有两条依据【3 0 第一，如前所述，单位法向量变化量较小的对原模型外观的影响较小，当非 关键顶点的邻接三角形数量相同时，平均单位法向量变化量较小则总和较小，即 权值较小，而权值较小的被认为对模型外观影响较小。在对同一个三角形中的三 点进行选择时，权值较大的点作为关键顶点，权值较小的两顶点折叠到权值最大 的顶点，即关键顶点，这样做可以使得在折叠中尽量减少对模型外观的影响； 第二，若三点平均变化量相当，而其中一点的邻接三角形较多，则该顶点被 认为其影响范围较广，所得到的权值也偏大，同时也表示删除该点会对模型结构 造成较大的改变，因此在对三点进行选择时该顶点保持原位置。该依据与第一条 依据结合起来就成为公式2 1 。 2 1 2 对单位法向量的变化量进行量化 对单位法向量的变化量进行量化是为了使得在编程实现是，算法更为简单， 本文采用 3 0 1 给出的量化方法。由于单位法向量的模为1 ，因此这里所讨论的单 位法向量的变化就是指其向量方向的变化。如图2 7 所示，n o r m a l _ o l d ( x ，y z ) 表 示原三角形的单位法向量，n o r m a ln e w ( x ，y ，z ) 表示变化后三角形的单位法向量。 拱十移动终端的| 旬9 格简化算法第2 章桀于三】= f j 形折蒋的h 格简化算法 n o r m a l _ o l d ( x ，y ，z ) 和n o r m a l n e w ( x ，y ，z ) 的夹角0 的大小就可以用于表示单位法 向量的变化量，如图2 -