（计算机软件与理论专业论文）面向移动终端的三维几何简化与传输方法的研究.pdf

面向移动终端的二维几何简化与传输方法的研究摘要 摘要 近些年来，随着无线宽带通信技术的发展，第三代移动通信系统( 3 g ) 正朝着 以c d m a 为基础，宽带化通信为特征的方向迈进。各式的移动终端设备如移动电 话、p d a 等，己逐渐成为人们不可缺少的随身物品。移动终端与无线网络上的各 种应用需求也日益增加，尤其是在移动网络上三维图形数据的传输及在移动显示 屏上显示高质量三维图形的需求日益迫切。移动图形处理是近年来计算机图形学 领域的一个研究热点。此外，随着3 c 融合进程加速，数字家庭相关技术同样得 到了迅速发展，通过数字电视终端实现与数字媒体广播端间的三维几何数据传输 及交互等，也是当前数字家庭领域的一个重要研究内容。通常在图形应用中，为 了获得具备一定真实感的显示效果，三维模型往往都由大量复杂的三角形网格构 成，在模型数据存取，传输及显示上都将耗费大量的资源。然而，移动终端及数 字电视终端与p c 机的特点有着显著的区别，整体渲染资源受限是其固有特点， 因此，在移动设备及数字机顶盒上进行三维图形应用受到很大的限制。 “普适计算研究手语无障碍信息服务的普适计算”( 国家自然科学基金 重点项目：6 0 5 3 3 0 3 0 ) 是面向2 0 0 8 年北京奥运会及残奥会的重要研究课题，利 用三维手语通过普适终端( 包括移动终端及数字电视) 进行无障碍信息交流是该 课题中一个重要研究内容。针对课题中及其他一些移动图形应用中存在的三维图 形应用问题，本文展开了面向移动终端的三维几何简化与传输方法的研究。本文 的贡献主要体现在以下方面： 从传统的基于几何元素删除的图形简化算法着手研究，在分析总结顶点删 除、边折叠、三角形折叠等传统的算法特性的基础上，提出在三角网格中利用多 个三角形组合构成及检索f i 边形的规则，并提出基于n 边形折叠的网格简化算法， 算法以n 边形折叠为基本简化操作，以二次误差作为误差度量。算法包含了 g a r l a n d 的q s l i m 算法( n = 2 ) 及p a n 的三角形( n = 3 ) 折叠的情况，简化速度和 简化模型品质受n 的具体取值影响，n 取较小的值适用于对简化品质要求较高的 图形简化；n 值取较大的值则适合于简化速度要求较高的图形应用。 面向移动终端的三维几何简化j 传输方法的研究 摘要 针对移动终端屏幕在不同投影下的轮廓几何误差在实际显示中相差较小的特 点，提出一种面向小型屏幕移动终端的轮廓保持的网格简化算法，算法对网格中 位于该视线方向上的轮廓相关的三角形进行判定，并分别定义为：轮廓顶点、轮 廓边及轮廓角三角形三种类型，分析了三种三角形对轮廓特征的重要程度并分别 加入加权保护系数以及定义其折叠规则。通过新折叠规则及加权因子的使用，新 算法比p a n 等均匀简化的算法在轮廓区域表现得更为出色，即使剩下面片数较 少，简化模型的轮廓依然能相对地接近原始模型。 针对用户感知度与移动终端屏幕分辨率相关的特性，提出一种基于感知度量 的网格简化算法，算法定义了模型在目标屏幕上的基准显示状态，并通过移动终 端分辨率及物体的视距参数计算得到目标屏幕的感知阈值e 及模型的感知度量， 通过加权q s l i m 算法动念地删除不符合显示精度要求的冗余数据。另外，算法还 加入了基于感知的尖特征保护，从而能够获得尖特征及整体简化效果与目标用户 感知度相匹配的简化模型。算法易于实现，适用于手机、p d a 等仅具备低分辨率 屏幕的移动终端上的图形应用。 最后，本文还基于移动网络的特性，结合以上提到的简化算法提出相关的移 动图形应用系统及传输方法，对弱交互性( 仅要求实时交互控制) 的移动图形应 用，提出基于脚本驱动的远程交互系统，通过在网络上传输脚本数据控制图形的 活动来代替频繁的图形传输，从而以减少数据传输量：对于强交互性移动图形应 用( 要求实时图形数据交互) ，提出采用基于用户感知简化的流式数据传输系统， 并对其网络架构、网络传输协议数据包封包等问题结合移动网络特性进行了相关 的讨论。 关键词：三角形网格模型，移动图形， 数字家庭，网格简化， n 边形折叠， 视相关简化，屏幕相关简化，手语交互，普适计算，流式传输 r e s e a r c ho l is c h e m e so f 3 0g e o m e t r ys i m p l i f i c a t i o na n dt r a n s m i s s i o nf o rm o b i l ed e v i c e s a b s t r a c t a b s tr a c t r e c e n t l y , d u et ot h ee v o l u t i o no fb r o a d b a n d w i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y , t h et h i r dg e n e r a t i o nm o b i l es y s t e mi sd e v e l o p i n go nc d m aa n df e a t u r e sb r o a d b a n d c o m m u n i c a t i o n t h em o b i l ed e v i c e s s u c ha sm o b i l ep h o n e sa n dp d a s b e c o m et h e n e c e s s a r i l yv a d em e c u m a p p l i c a t i o n so nm o b i l ed e v i c e sa n dw i r e l e s s n e t w o r k b e c o m ew i d e ra n dd e e p e r s p e c i a l l y , t h ed e m a n df o r3 dm o d e l s t r a n s m i s s i o nv i a m o b i l en e t w o r ka n dd i s p l a yo nm o b i l ed e v i c e sb e c o m e sm o r eu r g e n t t om e e tt h e r e q u i r e m e n t s ，m o b i l eg r a p h i c sp r o c e s s i n gb e c o m e sas i g n i f i c a n tt o p i co fc o m p u t e r g r a p h i c s f u r t h e r m o r e ，w i t ht h ep r o c e s so f3 ca m a l g a m a t i o n ，t e c h n o l o g y so fd i g i t a l h o m ea r ed e v e l o pr a p i d l y h o wt ot r a n s m i t3 dm o d e l sa n di n t e r a c t i v ei n f o r m a t i o n s v i a t h ed i g i t a lt vs y s t e mi sa n o t h e ri m p o r t a n tt o p i ci nt h ea r e a h o w e v e r , t om a i n t a i n ac o n v i n c i n gl e v e lo fr e a l i s mf o rc o m p u t e rg r a p h i c sa p p l i c a t i o n s ，m o d e l sa r eo f t e n c r e a t e da tah i g hr e s o l u t i o na n dr e p r e s e n t e da sc o m p l e xt r i a n g l e s t h ec o s to fs t o r i n g a n dt r a n s m i t t i n gt h e s ed a t a si sv e r ye x p e n s i v e f u r t h e r m o r e ，m o b i l ed e v i c e sa n dt h e d i g i t a lt vs y s t e ma r ed r a s t i c a l l yd i f f e r e n tf r o mp cs y s t e m s t h e yh a v ev e r ys m a l l a m o u n t so fr e s o u r c e sf o rr e n d e r i n g 。t h e r e f o r e3 dg r a p h i ca p p l i c a t i o n so nt h em o b i l e d e v i c e sa n dt h ed i g i t a lt vs y s t e ma r eb o t hm e e tw i t hg r e a tc h a l l e n g e s t a s k so ft h ek e ya r o j e c t ( g r a n tn o 6 0 5 3 3 0 3 0 ) o ft h en s f ci n c l u d es o m e a p p l i c a t i o n so fh a n dl a n g u a g ei n f o r m a t i o ns e r v i c ew h i c h w i l lb eo f f e r e di nt h eb e i j i n g 2 0 0 8o l y m p i cg a m e sa n dt h ep a r a l y m p i cg a m e s 3 de x p r e s s i o n so fh a n dl a n g u a g e o nt h em o b i l ed e v i c e so ro nt h ed i g i t a lt vi so n eo ft h ek e yr e s e a r c h e si nt h ep r o j e c t a i m i n ga tt h ep r o b l e m sa b o u t3 dg r a p h i c si nt h ep r o j e c ta n do t h e rm o b i l eg r a p h i c s a p p l i c a t i o n s ，t h i sp a p e rd e s c r i b e ss o m er e s e a r c h e so n3 dm e s h e ss i m p l i f i c a t i o na n d t r a n s m i s s i o no v e rm o b i l en e t w o r k s e v e r a lm a i n l yc o n t r i b u t i o n so ft h i sp a p e ra r e ： w ep r e s e n tt w or u l e st od e f i n ea n ds e a r c ht h en - e d g e sm e s hi nt r i a n g l em e s h e s a n dp u t sf o r w a r dan e wm 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 do nn - e d g e sm e s h c o l l a p s e t h ea l g o r i t h mu t i l i z e si t e r a t i v ec o l l a p s eo fn e d g e sm e s ht os i m p l i f ym e s h e s a n ds u r f a c ee r r o ra p p r o x i m a t i o n sa r em a i n t a i n e du s i n gq u a d r i cm e t r i c s o u ra l g o r i t h m c o n t a i n sg a r l a n d s ( w h e nn = 2 ) a n dp a n s ( w h e nn = 3 ) c a s e s b ya s s i g n e dap r o p e r v a l u ef o r n o ft h en - e d g em e s h ，t h ep r o p o s e da l g o r i t h mc a nb ec h o o s ee f f i c i e n t l yb y f u s e r st os i m p l i f ym e s h e sr a p i d l yo rt op r o d u c eah i g h q u a l i t ya p p r o x i m a t i o n a i ma tt h es p e c i a l t yt h a tg e o m e t r ye r r o r so ft h es i l h o u e t t e su n d e rd i f f e r e n t p r o j e c t i o nb e c o m el i m i t e di nt h es m a l l s c r e e nd i s p l a y , w ep u tf o r w a r dan e wm e s h s i m p l i f i c a t i o na l g o r i t h mb a s e do ns i l h o u e t t e sp r e s e r v ef o rt h e s ed e v i c e s t r i a n g l e so n t h es i l h o u e t t e sa r ec a t e g o r i z e di n t o3k i n d s ：t h ev e r t e xs i l h o u e t t et r i a n g l e ，t h ee d g e s i l h o u e t t et r i a n g l ea n dt h ea n g l es i l h o u e t t et r i a n g l e s i g n i f i c a n c e so ft h e s et r i a n g l e s a r ea n a l y z e d t h e r e f o r e ，w ea p p l i e sn e wr u l e so fc o l l a p s ea n da s s i g n saw e i g h tt ot h e c o s to ft h ep r o c e s s t h en e wa l g o r i t h mp e r f o r m sb e t t e rt h a np a n sa l g o r i t h m e s p e c i a l l yo nt h es i l h o u e t t e s e v e nw h e ni tl e a v e so n l yf e wt r i a n g l e s ，t h es i l h o u e t t e s a r ec l o s e rt ot h eo r i g i n a lm o d e lr e l a t i v e l y a i ma tt h ef e a t u r e st h a tu s e r sp e r c e p t i o na r ec o n s i d e r a b l yr e l a t i v et ot h e r e s o l u t i o no ft h em o b i l es c r e e n ，w ep u tf o r w a r dam 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 d o np e r c e p t u a lm e t r i c sf o rm o b i l ed i s p l a y t h en e wa l g o r i t h md e f i n et h eb e n c h m a r ko f v i e ww h e nt h em o d e li sd i s p l a y e do nt h et a r g e ts c r e e n s ot h ep e r c e p t u a lt h r e s h o l d e c a nb ed e t e r m i n e db yt h er e s o l u t i o no ft h et a r g e ts c r e e na n dt h e nt h en e w p e r c e p t u a lm e t i r i c sc a nb eo b t a i n e db yw e i g h t e dt h eq u a d r i ce r r o rm e t r i c sw i t h p e r c e p t u a lt h r e s h o l d t h a ti sr e d u n d a n c yo ft h em o d e lw h i c ha r en o tm a t c ht h e r e s o l u t i o no ft h et a r g e ts c r e e nw i l lb er e m o v e df i r s t l y f u r t h e r m o r e ，t h en e w p e r c e p t u a lm e t i r i c sc a nb ea l s ow e i g h t e db yas h a r pf e a t u r e sp e r c e p t u a lf a c t o r , s oa n a p p r o x i m a t i o nw i t hs h a r pf e a t u r e sp r e s e r v i e dc a nb eg o t ，a n di t i sf i t sf o rt h et a r g e t u s e r s p e r c e p t i o na t t h es a m et i m e t h ep r o p o s e da l g o r i t h mi ss u i t a b l ef o rt h e a p p l i c a t i o n so fg r a p h i c sf o rt h em o b i l e d e v i c e s a tl a s t ，w ef o c u so nt h et r a n s m i s s i o nm e t h o df o r3 dg e o m e t r ya p p l i c a t i o n s f o r t h ew e a k l yi n t e r a c t i v ea p p l i c a t i o n s ，a l li n t e r a c t i v es c r i p t b a s e ds y s t e mw h i c hi s d e s i g n e dw i t hs t r e a m i n gt r a n s m i s s i o nm e t h o di sp r e s e n t e dt or e d u c et h ed a t as t r e a m t r a n s m i t e do nt h ew i r e l e s sn e t w o r k w h i l ef o rt h es t r o n g l yi n t e r a c t i v ea p p l i c a t i o n s ，a p r o g r e s s i v em e s ht r a n s m i s s i o ns y s t e mb a s e do nu s e r sp e r c e p t i o ni sp u tf o r w a r d f u r t h e r m o r e ，s o m ep r o b l e m sr e l a t i v et ot h es y s t e ma r ed i s c u s s e d k e yw o r d s ：t r i a n g u l a rm e s hm o d e l ，m o b i l eg r a p h i c s ，d i g i t a lh o m e ，m e s h s i m p l i f i c a t i o n n e d g e m e s h c o l l a p s e ，v i e w d e p e n d e n t s i m p l i f i c a t i o n ， s c r e e n d e p e n d e n ts i m p l i f i c a t i o n ，s i g n l a n g u a g ec o m m u n i c a t i o n ，u b i q u i t o u s c o m p u t i n g ，s t r e a m i n gt r a n s m i s s i o n i v 面向移动终端的三维几何简化弓传输方法的研究论文原刨性声明 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 哿鸟 日期：2 0 0 7 年1 2 月3 e t 面向移动终端的三维几何简化与传输方法的研究学位论文使用授权声明 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资科室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。保密的学位论文在解密后使用本规定。 躲哔聊虢罗确 日期：2 0 0 7 年1 2 月3 日日期：2 0 0 7 年1 2 月1 7 同 面向移动终端的三维几何简化与传输方法的研究 第1 章绪论 第1 章绪论 随着无线网络技术及移动终端设备性能的不断提高，各类的移动图形应用正 日益增多，移动图形处理，特别是基于3 g 网络上的图形研究，逐渐成为近年计算 机图形学领域的一个研究热点。本章首先从传统的三维几何简化研究背景入手， 概述了图形简化的基本要求、发展趋势等内容，同时从静态简化及动态简化两个 方面分类总结了国内外已有的技术基础，然后对移动图形应用涉及的网络、软硬 件环境及终端特性等进行介绍及分析，并详细介绍了基于c s 架构的移动图形应 用模式及相关研究，最后扼要的阐述了本论文的主要研究内容及成果。 图卜12 0 亿面片的大卫( d a y i d ) 雕像”1 面向移动终端的三维几何简化与传输方法的研究第1 章绪论 1 1 研究背景 在计算机图形学和几何造型中，物体表面常用多边形网格模型尤其是三角网 格模型描述，网格模型己成为图形学中三维实体的重要表示方法。近几十年来， 随着计算机视觉三维数据获取设备、医学图像获取设备等的功能与测量精度的不 断提高，测量所得的数据量也以惊人的速度增加，由此建立三维模型所得的三角 网格动辄就是由几十万、几百万、甚至上亿个三角面片组成。 比如，由三维数字化仪得到的数据重建的三角网格模型的三角形数目的数量 级约为1 0 5 到1 0 6 ；在科学计算可视化中抽取的等值面的数量级约为1 0 6 ；在地理 信息系统中嘲，由高度数据场得到的三角网格模型的数量级约为1 0 5 到1 0 7 ；在 医学图像中，为某些器官抽取的等值面的数量级约为1 07 ；在文物保护中，所获 得的某些雕像模型面片的数量级高达1 0 1 0 ，斯坦福大学的数字米开朗基罗计划 ( d i g i t a lm i c h e l a n g e l op r o j e c t ) 中著名的大卫( d a v i d ) 雕像( 如图l 一1 示) 的三角面 片更是高达2 0 亿。 在现有的硬件环境下，即使在具备高性能图形加速卡的台式计算机上直接绘 制这些复杂的三维模型难以达到实时。使用大量的三角面片除了导致绘制速度大 大降低以外，还将导致系统资源( 如内存) 的极大浪费，并给模型分析( 如碰撞检测、 变形动画、表面分析等) 带来更大困难，同时也加大了网络传输的压力。比如， 在3 d 漫游这一类虚拟现实应用中，图象绘制必须在指定的时间内完成，否则视 觉图象将会失真，从而影响沉浸感；在虚拟手术等虚拟现实应用中，大规模数据 的处理与要求绘制、分析等的实时响应在有限的硬件条件下是难以同时满足的。 然而在很多情况下，精细的模型并不总是必要的，例如在3 d 漫游时，对远 处的物体只要生成一个较粗糙的模型就可以满足视觉效果了；在虚拟手术中，在 确定手术位置时可以选择较粗糙的模型来确定大概位置，而在实施手术时，则可 选择待手术组织的精确模型。因此模型的精确度与应用需求间需要一个折衷，网 格简化是降低模型复杂度使其满足应用需求的一种重要途径，其基本思路是在尽 量保持原有几何形状或其他属性的前提下，通过计算生成一个具有更少网格面片 或顶点数的较粗糙网格来代替复杂的原始模型，从而提高绘制效率。在台式p c 面向移动终端的三维几何简化与传输方法的研究第1 章绪论 平台上，网格简化已经在虚拟现实、计算机视觉、c a d 等方面得到重要应用。 另一方面，移动通讯技术经过近二十多年来的迅猛发展，移动终端硬件及无 线网络的性能的不断提高，继欧美，日韩等地区之后，第三代移动通讯( 3 r d g e n e r a t i o n , 3 g ) 将很快进入我国商用市场。相对于2 g 的g s m 移动通讯系统， 2 5 g ( 如g p r s ) 和3 g ( 如c d m a ) 移动通信网络的数据传输速度有了质的飞 跃，提高了数十倍乃至数百倍，这使得高质量图像、音视频和三维图形等多媒体 数据在移动网络上传输成为可能。随着手机、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 s ， 个人商务助理) 等移动设备的日益普及，高质量多媒体数据在这些便携设备上的 应用需求变得越来越迫切，根据市场调研机构i d c 预测( 见图l 一2 ) ，到2 0 1 0 年 全球数字媒体产业市场规模将达到4 1 1 6 亿美元，年复合增长率平均为2 3 ，当 中包括移动图形在内的移动媒体内容领域的复合增长率更将高达4 7 ，因此， 移动图形等相关研究越来越受到重视。 5 0 0 0 4 0 0 0 3 0 0 0 2 0 0 0 1 0 0 0 0 亿美元 2 0 0 2 2 0 0 72 0 1 0 年度 领域复合增k 率 移动媒体内容 4 7 电子出品 4 3 游戏 2 0 动漫 1 2 数字学习 2 6 图1 2 至2 0 1 0 年全球数字媒体产业市场规模预测。 平均：2 3 在台式p c 平台上，人们存储了大量宝贵的三维模型资源，尤其是三维数据 采集设备获得的复杂三维模型数据，然而由于移动平台具有显示屏幕小、处理能 力低、内存带宽小及功耗受限等特点，使这些资源难以在移动应用中直接使用。 三维几何图形简化技术是处理受限移动资源和应用需求间问题的最直接有 效的途径，然而，移动平台受限的硬件资源环境给移动图形简化及其他的移动图 形处理研究带来许多新的挑战，如何在小型屏幕以及资源受限的移动平台上提供 相对高的显示质量是近年来移动图形研究的热点。2 0 0 3 年8 月，在美国s a nd i e g o 举行的s i g g r a p h 2 0 0 3 大会上，爱立信系统研发小组研究人员t o m a s 。数据来源：市场咨询和顾问机构i d c 公司f 国际数据公司1 3 面向移动终端的三维几何简化0 传输方法的研究第1 章绪论 a k e n i n e m o i l e r 教授宣读了一篇有关蜂窝电话图形( c e l lp h o n eg r a p h i c s ) 的论文 【3 1 。大会主席c o l o r a d os c h o o lo f m i n e s 大学的a l y nr o c k w o o d 教授说：“向移动 图形的迁移是今年s i g g r a p h 大会的中心，人们将看到，对高质量的蜂窝电话 图形的需求会越来越强( t h em i g r a t i o nt om o b i l eg r a p h i c sw i l lb ea no v e r a r c h i n g t r e n da tt h i sy e a r ss i g g r a p hc o n f e r e n c e ，y o ua r es t a r t i n gt os e em o r ed e m a n df o r g o o dg r a p h i c s o nc e l lp h o n e s l ”这是数字几何处理领域中的一个新的研究问题 移动图形计算( m o b i l eg r a p h i c sc o m p u t i n g ) 开始的标志。 1 2 图形简化技术概述 三维几何模型简化是指保持其几何形状不变的前提下，采用适当的算法减少 该模型的顶点，面片等几何元素。早在2 0 世纪7 0 年代，就有学者讨论网格模型 简化的问题 4 | ，然而直到9 0 年代以后，网格简化才得到深入研究，进入2 l 世纪， 网格简化正逐渐延伸至与移动计算、心理视觉等领域相结合。本节，我们在图形 简化的研究内容、基本要求及应用现状与趋势等方面进行简单概述。 1 2 1 图形简化算法的研究内容 三维几何模型的简化目的是降低模型的数据量，从几何学角度出发，在保证 模型外观基本不变前提下，降低模型的表面的分割精度，尽量减少其分割的多边 形数目。从内容上讲，三维几何模型简化技术的研究内容主要集中以下几个方面： ( 1 ) 模型的简化方法： 研究通过什么样的方法或者操作才能减少模型表面的多边形数目。 ( 2 ) 模型简化时误差的控制方法： 研究采用什么样的手段才能保证简化后的模型与原始模型在外形上相似。 ( 3 ) 多分辨率系列模型的构造方法： 研究怎样构造出系列的近似模型，细节程度逐渐降低，其中原始模型细节程 面向移动终端的三维几何简化与传输方法的研究 第l 章绪论 度最高，最精细，而最后一个近似模型的细节程度最低，是最粗糙的简化模型。 模型的简化方法和误差控制方法是模型简化技术中的基本内容，结合这两个 方面的算法就能生成原始模型的近似模型，这称为单分辨率简化模型，其构造方 法是多分辨率简化模型构造的基础。本文中的内容将涵盖这三个方面的研究。 1 2 2 图形简化算法的基本要求 模型简化算法是指将一个模型表示为由较少几何元素构成的原始模型的近 似模型的方法。即在图形绘制时，根据模型在屏幕覆盖象素的多少，选择相应的 简化模型，对近物体绘制采用较精确的模型，而对远物体则选择较粗糙的模型。 在保证对原始模型较好逼近的前提下尽量减少用于表示该模型的三角形数目。 一个好的模型简化算法既能满足不同应用的需要，又能适应计算机的处理能 力，因此对模型简化算法的性能要求常常表现在以下几个方面： ( 1 ) 具有局部特征。对模型的局部变化不影响模型的整体复杂性。 ( 2 ) 连续性好。视觉参数小变动仅导致模型复杂性小变动，不发生画面抖动现象。 ( 3 ) 预处理时间尽量少，占用内存尽可能小，这对于在交互过程中可能会动态改 变的三维模型尤为重要。如果不能较好地满足这一要求，就会失去交互的意义。 ( 4 ) 适应性强。根据不同的应用满足相应的需求，如要求简化模型保持原始模型 的拓扑结构或流形特征等。 ( 5 ) 具有实时性。对模型在几何上的变动或状态上的改变能作出实时反映，并能 对几何信息随时进行访问。 1 2 3 图形简化算法的应用现状及趋势 模型简化算法已经在计算机图形学的许多领域，如虚拟现实化、计算机视觉、 网络传输等方面获得了重要的应用，具体而言主要包括： ( 1 ) 加速绘制，采用模型简化方法后，可以实时地除掉那些对视觉影响不重要的 面向移动终端的二维几何简化i 传输方法的研究第l 章绪论 细节，加快不同细节层次图形的绘制速度。 ( 2 ) 几何压缩，模型简化方法有助于采用更加紧凑的数据形式来表达复杂三维模 型，从而减少模型的存储量及其在网络上的传输时间【5 ，6 1 。 ( 3 ) 递进传输，在i n t e r n e t 环境下，如果网络速度有限，可以利用模型简化方法， 先传输较为粗糙的模型进行绘制，再逐步传输更多细节进行精细绘制( 7 1 。 ( 4 ) 加速计算，模型简化方法可以对诸如辐射度计算、碰撞检测计算以及动画中 的变形处理等进行加速。 ( 5 ) 方便造型，模型简化方法可为曲面造型提供重要的辅助手段。 1 3 国内外已有的网格简化研究基础 早在2 0 世纪7 0 年代，就有学者开始对模型的简化技术进行了初步探讨，随 着人们对模型简化技术研究的不断深入，从上世纪九十年代以来，各种新算法层 出不穷，许多经典的算法大大提高了简化的效率，在图形学的许多领域得到了广 泛应用。本节，我们结合文献1 8 l 的分析总结，对国内外己有的三维几何网格简化 研究划分为静态简化方法和动念简化方法两种类别进行介绍。 1 3 1 静态简化技术 静态简化技术是根据一定的精简原则，对复杂模型进行简化，它只考虑模型 自身的信息，与视点无关，也不能恢复原模型的信息。早期的简化算法大多属于 静态化简化，目前主要的静念简化方法有： 1 3 1 1 顶点聚类 顶点聚类方法9 1 1 的原理是：先用一个包围盒将原始模型包围起来，然后通 过空间划分将包围盒分成若干个区域，这样，原始模型的所有顶点就分别落在这 些小区域内，将区域类的顶点合并成一个新顶点，再根据原始网格的拓扑关系对 这些新顶点进行三角化，就得到简化模型。其优点是简化过程不需保持拓扑结构， 面向移动终端的三维几何简化与传输方法的研究 第1 章绪论 可处理任意拓扑的网格模型，且速度较快。由于这个方法是将模型的包围盒均匀 分割，所以无法保持那些大于分割频率的特征。同时新顶点生成只采取简单加权 平均，没有较好控制误差，因此生成模型的质量不高。这方面相关研究还有1 1 2 1 。 1 3 1 2 区域合并法 k a l v i n 等提出在网格中选择一个三角面作为种子面，据一定的准则将周围的 面合并形成一个更大的面( 称为超面) ，再将超面边界拉直，并对其重新三角化， 从而简化网格的算法。该算法称为区域合并法【1 4 l ，由于无法避免带洞超面的产 生，且重新三角剖分计算复杂，影响算法的运行效率，后来的改进算法有 1 5 - 1 9 1 。 l 3 1 3 重新布点法 g r e gt u r k 在1 9 9 2 年提出y 驯( r e t i l i n g ) 2 0 1 ，算法先将由用户指定数 目的顶点根据各个三角面片的面积大小分布在模型表面上，其次根据模型表面上 顶点之间的斥力以使顶点在表面上的分布更均匀，然后将模型上的原始顶点与新 加入的顶点混合在一起进行三角剖分，最后将原始顶点一个个地删去，并及时地 对删除顶点所造成的空洞进行三角化。这方面相关研究还有【2 1 ，2 2 1 。 1 3 1 4 逐步求精法 逐步求精方法首先给出一个原始网格的逼近网格，然后逐步增加细节，并重 新进行局部三角化，直到近似模型达到用户满意的精度为止四l ，它包括贪婪插 入法和层次细分法。 贪婪插入法在每一次遍历过程中选择误差最大的位置作为插入新顶点的位 置。这方面的研究有1 2 4 - 2 6 l 。层次细分法是一种离散的几何模型构造方法，它的基 本思想是：对给定的离散几何数据，递归地调用细分规则，从而逐步加密几何数 据使其收敛于一个极限的几何模型。比较著名的细分模式( 表1 1 列举了几种细 分的相关介绍) 包括c a t m u l l c l a r k 模式【2 7 】，l o o p 模式f 2 8 1 ，d o o s a b i n 模式【2 9 l 以 及b u t t e r y 模式( 3 0 l 等。其他相关的研究由于细分方法不受控制网格拓扑的限制， 可以对任意拓扑网格进行曲面造型，而且其递归结构与小波和多分辨率分析有着 面向移动终端的三维几何简化j 传输方法的研究 第1 帝绪论 密切联系3 1 1 ，近年来还有学者提出了了模式3 2 1 和4 - 8 模式例等。 表1 - 1 几种典型的静态细分曲面分类 细分模式网格类型分裂类硝顶点戈系连续性 c a t m u l l c l a r k四边形面分裂 逼近 c 。 l o o p 二角形面分裂逼近 c 。 m o d i f i e db u r e r y 三角形面分裂插值 c 。 d o o s a b i n四边形 点分裂逼近 c 以 三角形面分裂逼近( 插值) 1 3 1 5 几何元素删除法 1 9 9 2 年，s c h r o e d e r 提出了顶点删除的网格简化方澍3 4 1 ，此后，基于边折叠 3 5 1 、基于三角形删除【3 6 i 等几何元素删除的方法被相继提出。这些方法的共同特 点是以几何元素的删除实现模型的简化，即根据原模型的几何拓扑信息，在保持 一定的几何误差的前提下删除对模型几何特征影响相对较小的几何“图元( 点， 边、面) ”。下面将分别介绍几种典型的几何元素删除法： ( 1 ) 顶点删除法v e r t e xd e c i m a t i o np r o c e s s ( v d p ) 图1 - 3 顶点删除法 基本操作是一个顶点及其相邻的三角面片被删除，并且对产生的空洞进行重 新三角化( 如图卜3 所示) 。s c h r o e d e r 。“1 提出一个关于顶点删除的算法，该算法 的基本思路是指定一个最小的距离阈值，如果模型中某顶点到该顶点定义的平均 平面的距离小于该阂值，则认为陔顶点与周围三角面片共面，同时删除该顶点， 并采用递归循环分割法对删除顶点后遗留的空洞进行三角剖分，陔算法具有简单 并且执行效率高的特点。 这种算法计算较快，也不需要占用太多的内存，但是由于重新三角化需要将 局部表面投影到一个平面，这种算法只适用于流形，而且它在保持表面的光滑性 面向移动终端的三维几何简化与传输方法的研究 第1 章绪论 方面存在一定困难3 7 1 。随后又有算法对其改进9 ，3 & 3 引。实际上，顶点删除与边 折叠算法极为相似，通过边折叠来删除顶点比重新三角化要鲁棒得多【3 7 1 。 ( 2 ) 边折叠法e d g ec o ll a p s ep r o c e s s ( e c p ) 在每一次简化操作中以边作为被删除的基本几何元素，同时边相邻的两个三 角形被删除( 如图卜4 所示) 。进行多次的选择性边折叠后，面片就可被简化到 我们想要的任何程度了。点分裂是边折叠的逆变换，可用来恢复被简化掉的信息。 图卜4 边折叠 边折叠的关键是折叠的次序以及边折叠后新顶点的位置。h o p p e 在1 9 9 3 年 采用能量优化的方式来确定折叠次序和新顶点的位置“。，能量优化计算复杂， 所需时间较长，但是生成模型的效果却是在所有化简方法中最好的m 1 。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 ) 的化简算法q s l i m 4 ，4 2 1 。q s l i m 算法误差测度是基于顶点到平面的距离平方 和，该算法速度快，简化生成的模型质量仅次于h o p p e 的能量优化方法，是一 种非常有效的化简算法。h o p p e 将法向量、颜色以及纹理等信息加入到q s l i m 算 法中，然后采用叫作翼边( w e d g e ) 的数据结构来加以实现，也得到了较好的效果 4 3 1 。l i n d s t r o m 和t u r k 在1 9 9 8 年用化简前后体积和面积的变化作为误差测度， 也得到了与q e m 类似的数学表达【删，这种方法在计算边折叠队列和新顶点的位 置时只需要网格模型面的连接信息和顶点的位置，所以此算法占用内存量小，运 算速度快。国内外相关的研究还有【4 5 1 4 6 1 4 7 l 。 ( 3 ) 三角形折叠简化方法t r i a n g l ec o l l a p s ep r o c e s s ( t c p ) 三角形折叠简化方法是指，网格中某个三角形折叠成一个新顶点，同时删除 这个旧三角形共边的相邻三角形，如图1 5 所示，一次三角形折叠可以删除4 个 三角形、两个顶点。 面向移动终端的二维几何简化0 传输方法的研究第1 章绪论 图卜5 三角形折叠 h a m a