（计算机应用技术专业论文）基于球面参数化的三维几何压缩.pdf

丝釜竺垒兰些! ! 丝耋： 。：，：，。，。，：，。；。，：! 尘 基于球面参数化的三维几何压缩 摘要 随着三维几何模型在汁算机图形学应用中的范围日益扩大、作用日益增加，人 们对计算机图形的合成质量也在不断地提出新要求。但是要合成高质量的画面，往 往需要有足够精细的几何模型，这必然导致三维几何数据量和复杂程度的急剧增 长，新的三维扫描技术和大型c a d 软件的出现也促成了这一发展趋势。这些数量规 模和复杂程度日益增长的三维儿何数据在爿i 断满足需求的同时，也给我们带来了许 多问题和巨大挑战：( 1 ) 当前的图形适配器难以直接处理规模巨大的三维模型；( 2 ) c a d 系统中的模型变得越来越复杂，极大地增加了处理所需的时间和空间：( 3 ) 许 多新的应用，如协同设计、网络游戏、快速成型、虚拟现实等等，都需要发布和传 偷三维几何模型，但是目前的网络带宽无法实现复杂模型的实时传输和显示。 解决这些问题的途径除了不断提高和升级硬件的处理性能之外，更需要提出有 设的三维几何压缩算法。虽然国内外学者对几何压缩进行了十几年的研究，提出了 系列行之有效的编码葬法但是面对复杂程度日益增长的几何数据，传统的方法 仍然存在许多改进和提高的地方。本文的研究目的就是要提出一个新的三维几何压 缩框架来进一步提高三维网格的压缩比( 在重构误差保持不变的条件下) 。 本文提出了一平一于球面参数化的二维几何压缩框架，并在此框架下对球面参 数化、球面腻警“”重帮网格化、球面点定位以及小波压缩理论进行了全面的分 i 和深入的研究。主要贯如下： 提出了一个基于球域混合变形测度的球面参数化方法。通过结合混合变形测度 和累进网格技术，该方法不仅能够快速、高效地生成参数化网格，而且能够有 地减小参数化过程中的角度变形和面积变形。 键出了一个两阶段球面网格松弛方法。为了进一步减小球面参数化网格的变形， 本文提出一个两阶段松弛方法来调整顶点的球面位置。第一阶段是一个保面积 松弛算法，它能够有效地降低球面网格的面积变形，第一二阶段是一个基于s c d m 的松弛算法，它能够在面积变形和角度变形之间找到一个较好的平衡点。 提出了一个自适应的重新网格化方法。该方法以参数化球面网格为桥梁，构造 具有了分拓扑关系的空间三维网格。为了将更多的采样点分配给细节较多的区 第l 页 止j l 亘凡m i 学他砣史 i t i 垭 域，找们采用种白适应的松弛方法来渊整顶点的球面分布情况。 提出r 个适用于球面网格的启发式点定位算法。首先通过构造规则子分网格 将整个球面区域划分成若t 具有子分层次关系的查询小块；然后在进行查询之 d h ，根据查询点的位置找到它所位于的小块作为搜索区域，从而极大地缩小了 鹰询范围；最后在查询过程中，利用查询点相对于当前搜索三角形的重心坐标 值来选择下一搜索三角形，从而找到一条从初始搜索三角形到目标三角形的最 姬彘询路径。 构造了一种基于小波变换和零树编码的三维网格压缩方案。首先利用小波变换 将新构造的子分网格分解成一个基网格和若干层次的小波系数，然后分别利用 t g 算法和零树编码方法对基网格和小波系数进行压缩。在小波分解过程中，利 用重构的低分辨率网格上的顶点几何信息来预测高分辨率网格上的顶点信息， 有效地减小了小波系数：通过构造3 4 叉树，传统的零树编码方法能够快速地 推广到有边界网格。与经典的压缩算法相比，在相同的比特率条件下，本文的 方法最多能够将信噪比p s n r 提高2 - 5 d b 。 4 tj i 绍了三维几何压缩的一些背景知识和研究现状后，第一章的最后- 节给出 了基于球面参数化的三维几何压缩框架；第二章详细讨论了基于球域混合变形测度 的鬃进球面参数化方法；第三章介绍了一种松弛算法来进一步减小球面网格的参数 化变形：第四、五两章分别讨论了重新网格化方法和球面点定位算法：第六章对子 分网格的压缩过程进行了深入的研究；结论和展望在第七章给出。 关键词：三维几何压缩，球面参数化，重新网格化，球面点定位，小波变换，零树 编码， 1 、h r e ed i m e n s i o n a lg e o m e t r yc o m p r e s s l 0 n b a s e do ns p h e r l c a lp a r a m e t r l z a t i o n a b s t r a c t w i t ht h ei n c r e a s i n gu s eo f3 dg e o m e t r y , n e wr e q u i r e m e n t so nv i s u a lq u a l i t ya r e p r e s e n t e do n eb yo n e i no r d e rt oi m p r o v et h ev i s u a la p p e a r a n c eo f o b j e c t s ，m a n yd e t a i l s h a v et ob ep r e s e r v e d ，w h i c hw i l lc o n s e q u e n t i a l l yr e s u l ti n t o3 dg e o m e t r yr e p r e s e n t e db y al o to fd a t a d e v e l o p m e n to f3 ds c a n n i n gt e c h n o l o g ya n dl a r g ec a ds o f t w a r es y s t e m s a l s oa c c e l e r a t et h eu s eo f c o m p l i c a t e d3 dg e o m e t r y a l t h o u g ht h e s ec o m p l i c a t e dm o d e l s c a i j s a t i s f ym a n yr e q u i r e m e n t so fp e o p l e ，t h e yc a u s ef o l l o w i n gp r o b l e m s ：( 1 ) t h e g r a p h i c sa d a p t e rh a sn oe n o u g hm e m o r yt ol o a dt h e s el a r g em o d e l s ，w h i c hw i l ld e c r e a s e t h ep e r f o r m a n c eo fg r a p h i c s p r o c e s s i n gs e r i o u s l y ( 2 ) f o r3 dc a ds o f t w a r es y s t e m s ， l a r g ea n dc o m p l i c a t e dm o d e l sw i l li n c r e a s et h et i m ea n ds p a c eo f d a t ap r o c e s s i n g ( 3 ) i n m a n ya p p l i c a t i o n ss u c ha sc o l l a b o r a t i v ed e s i g n ，n e t w o r kg a m e ，r a p i dm o l d i n g ，v i r t u a l r e a l i t ya n de t c ，i ti sr e q u i r e dt ot r a n s f o r m3 dm o d e l sb yn e t w o r k b u tc u r r e n tb a n d w i d t h i ss ol i m i t e dt h a tm a n yl a r g em o d e l sc a n tb et r a n s f o r m e da n ds h o w ni nt i m e b e s i d e si m p r o v i n gt h ep e r f o r m a n c eo fg r a p h i c sh a r d w a r ec o n t i n u a l l y , d e v e l o p i n g e f f e c t i v ec o m p r e s s i o na l g o r i t h m si sa n o t h e rg o o dk e yt oa b o v ep r o b l e m s a l t h o u g h3 d g e o m e t r yc o m p r e s s i o nh a sb e e ns t u d i e df o ro v e rt e ny e a r sa n dm a n yv a l i da l g o r i t h m s h a v eb e e np r o p o s e d ，i ti ss t i l ld i f f i c u l tt op r o c e s st h ei n c r e a s i n gg e o m e t r yd a t a s ot h e a i mo ft h i sd i s s e r t a t i o ni st op r e s e n tan e ws c h e m eo f g e o m e t r yc o m p r e s s i o nt or e p r e s e n t t h el a r g ea n dc o m p l i c a t e dm o d e l sm o r ee f f e c t i v e l y w es t a r tf r o m c o n s t r u c t i n gn e wc o m p r e s s i o nf r a m e w o r ko f3 dg e o m e t r yt o i n t r o d u c ea c o m p r e s s i o ns c h e m eb a s e do ns p h e r i c a lp a r a m e t r i z a t i o n w i t h i nt h i s f r a m e w o r k ，w ed os o m er e s e a r c ho ns p h e r i c a lp a r a m e t r i z a t i o n ，r e l a x a t i o no fs p h e r i c a l m e s h ，r e m e s h i n g ，s p h e r i c a lp o i n tl o c a t i o na n dw a v e l e tb a s e dc o m p r e s s i o n s p e c i a l l y , w em a k et h ef o l l o w i n gc o n t r i b u t i o n s ： w e p r o v i d e a s p h e r i c a l p a r a m e t r i z a t i o na l g o r i t h m b a s e do ns c d m ( s p h e r i c a l _ d o m a i nc o m p o s i t i v ed i s t o r t i o nm e t r i c ) b yi n c o r p o r a t i n gs c d mi n t ot h e p r o g r e s s i v em e s hr e p r e s e n t a t i o n ，w ec a nn o to n l yg e n e r a t et h ep a r a m e t r i z a t i o nm e s h 竺兰塑垡型尘：! 耋： 一：! 型：竺三 r o b u s t l ya n dl a s t ，b u ta l s or e d u c et h ed i s t o r t i o no fp a r a m e t r i z a t i o ng r e a t l y w ep r e s e n tat w o s t a g er e l a x a t i o nm e t h o dt of u r t h e rr e d u c et h e d i s t o r t i o no f s p h e r i c a lp a r a m e t r i z a t i o nm e s h e s t h ef i r s ts t a g ei sa na u t h a l i cr e l a x a t i o na l g o r i t h m ， w h i c hc a nr e d u c et h ea r e ad i s t o r t i o no fs w o l l e nt r i a n g l e s t h es e c o n ds t a g ei s a r e l a x a t i o na l g o r i t h mb a s e do ns c d m ，w h i c hc a nr e d u c et h ea r e aa n da n g l ed i s t o r t i o n a tt h es a m et i m e w ep r e s e n tas e l f - a d a p t i v ea p p r o a c hf o rc o n v e r t i n gt r i a n g l em e s h e si n t om e s h e sw i t h s u b d i v i s i o nc o n n e c t i v i t y s i n c eah i g hs a m p l i n gd e n s i t yi so f t e nr e q u i r e di nr e g i o n s w i t hm o r ed e t a i l s ，w eu s es e l f - a d a p t i v ev e r t e xr e l o c a t i o na l g o r i t h mt oa l l o c a t em o r e v e r t i c e st ot h e s er e g i o n s w ep r e s e n tah e u r i s t i cs t r a t e g yt os o l v et h ep o i n tl o c a t i o np r o b l e mi ns p h e r i c a l t r i a n g u l a t i o nm e s h f i r s t l y , as p h e r i c a lm e s hw i t hr e g u l a rs u b d i v i s i o nc o n n e c t i v i t yi s c o n s t r u c t e dt op a r t i t i o nt h es p h e r i c a ld o m a i ni n t os o m es m a l lr e g i o n s t h e nt h e r e g i o n ，w h i c hc o n t a i n st h eq u e r yp o i n t ，i sf o u n da c c o r d i n gt ot h ep o s i t i o no ft h e p o i n ta n ds e l e c t e da st h es e a r c ha r e af o rl o c a t i n gi t d u r i n gt h ep o i n tl o c a t i o n ，t h e b a r y c e n t r i cc o o r d i n a t e sa r eu s e dt oe x t r a c tl o c a lh e u r i s t i ci n f o r m a t i o na b o u tt h e l o c a t i o no ft h eq u e r yp o i n ts oa st of i n dt h es h o r t e s tp a t hf r o mt h es t a r tt r i a n g l et ot h e t a r g e to n e ， w ec o m p r e s st h em e s hw i t hs u b d i v i s i o nc o n n e c t i v i t yb yw a v e l e tt r a n s f o r ma n d z e r o t r e ec o d i n g f i r s t l y , w a v e l e tt r a n s f o r mi su s e dt od e c o m p o s et h es u b d i v i s i o n m e s hi n t oab a s em e s ht o g e t h e rw i t hac o l l e c t i o no fw a v e l e tc o e f f i c i e n t s ，n e c e s s a r y t or e c o v e rt h eo r i g i n a lm o d e l t h e nt gc o d e ra n dz e r o t r e ec o d e ra r eu s e dt oc o d et h e b a s em e s ha n dw a v e l e tc o e f f i c i e n t s ，r e s p e c t i v e l y i no r d e rt or e d u c et h ee r r o r b e t w e e nt h ed e c o d e dm e s ht h eo r i g i n a lm e s h ，w e i m p r o v eo n t h ew a v e l e t d e c o m p o s i t i o np r o c e s s a sf o l l o w s ：t h ec o a r s e r - l e v e lw a v e l e tc o e f f i c i e n t sa r e c o m p u t e db e f o r et h ef i n e r - l e v e lo n e s w ea l s og e n e r a l i z et h ez e r ot r e ec o d e rt ot h e m e s hw i t hb o u n d a r i e sb yi n t r o d u c i n gt h e3 4t r e e i nc o m p a r i s i o nw i t ho t h e r s ，o u r a l g i r o t h mc a no b t a i na l li m p r o v e m e n to f 2 5 d bd e p e n d i n go nt h em o d e l a f t e ri n t r o d u c i n gs o r t i eb a c k g r o u n d sa n dt h es t a t eo f3 dg e o m e t r yc o m p r e s s i o n ，w e s u m m a r i z et h ec o m p r e s s i o ns c h e m eb a s e do ns p h e r i c a lp a r a m e t r i z a t i o ni nc h a p t e r1 c h a p t e r2d e s c r i b e st h ep r o g r e s s i v es p h e r i c a lp a r a m e t r i z a t i o nb a s e do ns c d mi nd e t a i l c h a p t e r 3i n t r o d u c e sar e l a x a t i o n a l g o r i t h m t of u r t h e rr e d u c et h ed i s t o r t i o no f i 街受通火车m 卜学位论殳 a b n ir a 【i p a r a m e t r i z a t i o nm e s h r e m e s h i n ga n ds p h e r i c a lp o i n tl o c a t i o na l g o r i t h m sa r ed i s c u s s e d i nc h a p t e r5a n dc h a p t e r6 ，r e s p e c t i v e l y c h a p t e r6s h o w st h ec o m p r e s s i o na l g o r i t h m b a s e do nw a v e l e tt r a n s f o r m f i n a l l y ，w ec o n c l u d et h i sd i s s e r t a t i o na n dd i s c u s ss o m e d i r e c t i o n sf o rf u t u r ew o r ki nc h a p t e r7 k e yw o r d s ：3 dg e o m e t r yc o m p r e s s i o n ，s p h e r i c a l p a r a m e t r i z a t i o n ，r e m e s h i n g ， s p h e r i c a lp o i n tl o c a t i o n ，w a v e l e tt r a n s f o r m ，z e r o t r e ec o d i n g 上海交通大擎学镶论文答辩决议书 申请者是勇i 所在学科 计算机应用技术 l ( 专业) 论文题昌缝于球面参数亿的兰维几何压缩 答辩日期 2 0 0 5 9 2 2 地点交大新建楼2 0 0 4 ，f 答辩委员会成员 姓名单位 职称签名 彭澄廉复旦长学教授、博导 朝乩乞 李启炎 同济次学 教授、博导 幸蝇 耿兆丰东华次学 教授、博导 让u 尤普元 上海燹通大学教授、博导 磷咚 金烨上海交通大学教授、博导 争秽 张申生 上海交通大学教授、赙导 捌 何援军上海交嗵大学教授、博导 稀缸絮 评语和决议： ? 一，县勇局举的博士论文基于球面参数化的三维几何压缩 对三维网格模型的压缩进行了深入的研究。该课题既有较 强的理论意义，又有重要的实用价值。论文作者的研究工 掌取得了如下刨新性成果： ( i ) 构建了基于球面参数化和小渡变换的三维几何压缩框架； ( 2 )提出了一种新的基于球域混合变形测度( s c d m ) 的累进球面参数化方法。通过结合混台变彤测度和累进网格 技术该方法不仅能够快速、高效地生成参数化网格，且能够有效地槭小参数化过程中的角度变形和蔼积变形j ( 3 ) 提出了一种豫酚段松弛算法。进一步减小了球面参散化嬲格的变形； ( 4 )提出了一种自适应的重新同格化方法与传统的方法相比，该算法能够更加有效地保持原始网格的细节： ( 5 )构造了一种基于小波变换和零树编码的同橹压缩方案与典型压缩算法相比该方案能够获得更好的压缩效果。 论文在三维凡何压缩框架、球面参数化、球面两格松弛、重新网格化班及三缝舟格编码等方面都作了创造性豹工作， 表明吴勇同学其有坚实宽广的基础理论、系统深入的专门知识、独立科研工作的能力强， 论文条理清晰，文笔流畅分析细致，论证严密 答辩中叔述清楚，回答问题正确，经答辩委员叁无记名投粤s 表决一致同意通过吴勇同学鹊博士学位论文答辩，建 议授予工学博士学位。 表决结粟： ： 一一一 。磊答辩委员会无记名投票表决，一致同意通过吴舅同学的博士学位论文答辩r 建议授予工学博士学位一 答辩委员会籀。签名， 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“”) 学位论文作者签名： 关勇 指导教师签名 日期： 渺尸 月立j 日t z t 期：年唔历丫k 嚼聂 铲月 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。 剥本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承手旦。 学位论文作者签名： 萎勇 日期：i 如，年，月) 日 第一章绪论 ，卜个世纪7 0 年代以来，多媒体数据已经经历了声音、图像、视频和三维几何 模型等几次重大革新。目前三维几何被，。泛应用于图形处理、动画仿真、虚拟现实、 媒体娱乐以及几何造型中柬模拟现实世界中的三维实体，图1 1 给出了这种数据表 j l j _ ) 1 ，法的实际应用效果。 嘲ll 三维几何模型的应用。( a ) 虚拟现实场案：( b ) 三维游戏；( c ) 三维动画电影；( d ) 三维产 品设计 f i g 1 ia p p l i c a t i o nf i e l d so f 3 dg e o m e t r y ( a ) s c e n eo f v i r t u a lr e a l i t y ；( b ) 3 dg a m e ；( c ) 3 dm o v i e ；( d ) d e s i g no f 3 do b j e c t 随着三维几何模型在计算机图形学应用中的范嗣日益扩大、作用目益增加，人 们对计算机图形的合成质量也在不断地提出新要求。但是要合成高质量的画面，往 往需要有足够精细的几何模型，这必然导致三维几何数据量和复杂程度的急剧增 长，新的三维扫描技术和大型c a d 软件的出现也促成了这一发展趋势。这些规模和 复杂程度日益增长的三维几何数据在不断满足需求的同时也给我们带来了许多问 题和巨大挑战，概括的讲包括如下几个方面： 图形适配器因为没有足够的内存完全装载巨大的模型，或者受限于数据传输 瓶颈而不能够充分地发挥其图形处理的性能。 第1 页 ! 坠竺些坠丝篁塞坚型：坠坠型型! 篁 二维c a d 系统巾的模型变得越来越复杂，极大地增加了处理所需的时i h j lj 空 川。 妞令的许多应用，如协同设计( c o l1 a b o r a t i r ed e s i g n ) 、网络游戏、快速 成型、虚拟交互等等，都需要发布和传输三维几何模型，但是目前的网络带 宽无法有效地满足这些需求。 在一些虚拟场景中，需要实时传输三维动画，如何通过网络有效传输那些以 关键帧表示的三维时序网格模型是当前三维动画处理中的一个难题。 为了解决上述问题，我们可以通过升级和提高图形处理的性能，增加刚络带宽等 硬错方面的办法来解决。但是仅仅这样是不够的，还需要采用算法方面的措施，如： 在下载和绘制几何模型的时候，选择性地处理那些潜在的可见部分。 在适当的时候使用图像代替复杂的几何模型。 对远距离处的物体使用多分辨率的、简化的几何模型。 使用几何压缩方法，减少它的存储空问和传输时间。 本文主要论述几何数据的压缩算法，用于减少模型的存储空闻和传输时闻。 1 1 国内外研究现状 几何压缩是计算机图形学中一个新兴的研究方向。最早的关于几何压缩方面的 工作可以追溯到1 9 9 5 年m d e e r i n g 发表的题为：g e o m e t r yc o m p r e s s i o n 的研究论 文“，稿b e e s i n g 几何压缩方法的目的是压缩几何数据，减少c p u 和图形卡之间的 数据传输，从而加快图形处理的速度。该方法引入一一个网格缓存器来存储1 6 个曾 经使用过的旧顶点，然后通过重用网格缓存中的旧顶点来减少需要传输的顶点数 据，同时对需要传送的顶点几何数据进行量化和增量编码。在此之厉人们开始关注 ，l 何压缩问题，并且做了大量的杰出工作。我们依据压缩结果是否保持了原始模型 的拓扑结构将现有的方法分为不规则网格的几何压缩和重新网格化压缩两类：前者 直接对原始网格进行压缩而不对模型的复杂性、规则性和均匀性做出任何假设；后 者则在压缩之前先对几何模型进行重新网格化。下面我们将对近年来国内外学者在 几何压缩方面的研究成果进行系统的回顾和总结。 1 1 不规则网格的压缩方法 直接对三维几何网格模型进行压缩的方法有许多种，按照网格类型可以分为三 危面片和多边彤面片两类，按照解压缩发生在传输过程中还是在传输结束之后可以 第2 页 ! 垒兰堡垒茎塑! ! 茎塞尘兰 薹：! 耋塑里 分挪分辨率压缩和多分辨率压缩两种，按照压缩内容n j 以分为：拓扑关系压缩、顶 点位置信息压缩以及其它属性压缩三类。 网格模型由顶点数据和 ：f i 扑关系表示，其中顶点数据包括所有顶点的位置坐 扔、法向量以及纹理信息，拓扑关系则町以简单地认为是网格面片与顶点之间的连 接方式。拓扑关系一般可以用一个而片一顶点列表来表示，每个而片记录所包含 的三个顶点序号，然而这种拓扑表示方式存在很大的数据冗余，每个顶点与多少个 丽h 相邻就会在拓扑关系中重复这个顶点序号多少次，显然为了减少存储量，应该 剥这种拓扑冗余进行压缩。与拓扑关系相比，顶点数据虽然不会被重复记录多次， 呵足我们知道拓扑相邻的两个顶点的数据信息一般比较接近，通常可以通过前一点 的信息预测后一点的信息。基于上面的分析，国内外学者提出了许多有效的压缩算 法。 1111 拓扑信息压缩 拓扑手术法“。是t a u b i n 和r o s s i g n a c 提出的一种三角形网格编码力法。该方法首 先为三角形网格构造棵顶点树，然后沿着顶点展开树的边将网格剪开、变成一个没 有内点的简单多边形( s i m p l e p o l y g o n ) ，最后利用三角形展开树( t r i a n g l e s p a n n i n g t t l e e ) 和一些二进制匹配码来完全表示该多边形。 所谓的三角形展开树是三角形网格连接图的对偶图中的一棵展开树，它也可以看 作是一棵由三角形组成的二叉树，树上的每一条边对应于网格中一条内部边。对这棵 i 角形展开树的深度优先遍历相当于从网格上的一个根三角形( r o o ty r i a n g l e ) 出 发，递归地遍历那些还没有遍历过的相邻三角形。三角形展开树可以用2 外比特来编 码，其中f 为网格中三角形的个数。对于每一条边，在刚格的遍历过程中都用一个比 特来表示三角形在这条边处是否有后续的三角形( 即是否有三角形和该三角形在展开 树上构成父子关系) 。 圆圆 圈l 一2 两个不同的羁格具有相同的边界和三角彤展开树 f i g l - 2 t w om e s h e sw i t hi d e n t i c a lb o u n d a r i e sa n dt r i a n g l e - s p a n n i n gt r e e s 3 第页 ! ! 窒耋塑查兰塑! ! 兰竺篁兰 竺：至塑茎塞! ! 些! 尘! 坠! 兰丝 从图1 2u j 知，仅仅从三角形眨开树小能得到完整的网格拓扑信息。i 纠此在拓扑 手术编码方法t j 使用了两棵展开树：一个是顶点展开树，另一个是三角形展开树。 t a u b i n 等人对顶点展开树和三角形展开树采用行程( r u n l e n g t h ) 方法进行编础，具 体如f ：树_ | 二的一串连续的、j 有个子节点( c h i l d ) 的节点组织在一起称为个 行程( r u n ) ，然后用它的长度作为它的编码，每一个长度编码最多需要l o g ( t ) 个比 特，同时在每一个分叉节点处都用蕊个比特来记录展开树的拓扑结构。对于复杂的网 格来说，编码这两棵树的代价都会小于1 ( 比特三角形) 。 e d g e b r e a k e r 是一种拓扑信息编码方法”1 ，用于处理三角形网格表示的三维几何 模型。e d g e b r e a k e r 是目前最好的编码方法之一，该方法不但有很好的理论分析，而 且对最坏情况的编码效率给出了一个很好的下限估计。最初的e d g e b r e a k e r 方法的下 限值是4 ( 比特顶点) ，但是通过对e d g e b r e a k e r 操作代码的分布和组合特征进行分 析，上述结果还可以改进，具体见9 。9 1 等文。 斟卜3 遍历网格三角彤可能遇到的6 种不同情况，x 表示当前的访问三角彤，它由入口迫( g a t e e d g e ) 和顶点v 组成 f i gi - 3s i xk i n d so fo p e r a t i o nt y p e sd e t e r m i n e db yt h el o c a t i o no fvw i t hr e s p e c tt ot h eb o u n d a r yb ： t r i a n g l ex i sc u r r e n tv i s i t e dt r i a n g l ec o m p o s e db yt h eg a t ee d g ea n dv 在编码的时候，e d g e b r e a k e r 沿着顶点环( l o o p ) ，按照相邻关系对网格上的三 角形依次进行遍历。顶点环上有一条边，称为入口边( g a t ee d g e ) 。遍历中的每一一 个三角形有两个顶点位于顶点环的入1 3 边上，e d g e b r e a k e r 根据该三角形的第三个顶 点的各种不同情况输出一个不同的操作码。e d g e b r e a k e r 的最后编码结果是一串操作 码，每一个三角形对应于一个操作码。 如图l 一3 所示，设当前正在访问的三角形是m 而且该三角形的第三个顶点为n 在e d g e b r e a k e r 中总共有6 种不同的操作码：巨瓜、s 和肛它们的意义分别 如下： 如果v 是一个没有编码过的顶点，如图1 3 ( a ) 所示，那么输出操作码 如果腥入1 3 在顶点环上的前面的一个顶点，如图卜3 ( b ) 所示，那么输出操 作码。 第4 页 p 、it - ”1 人学研i 位电堑 弛 程绪论 如果项点环上只有= = 三个顶点，而且是访问r f l 的三角形的三个顶点，如图卜3 ( c ) 所示，那么输出操作码 知- 粜提入口在顶点环上的后面的一个顼点 作码鼠 如果慢顶点环上其它位置l ! = 的某一个顶点 作码 封i 图卜3 ( d ) 所示，那么输出操 如罔l 一3 ( e ) 所示，那么输出搡 立u 果被编码的模型是一个有孔的、或者只有柄的复杂网格，如图1 3 ( f ) 所 示，那么顶点i 可能出现在其它的顶点环上。此时输出操作码肮 实验表明，e d g e b r e a k e r 编码方法能够将一个简单的三维网格压缩至1 3 到 2 b i t t r i a n g l e ，通过增加一些额外的字节，该方法还能够用来压缩带孔( h o l e ) 和 年丙( h a n d l e ) 的网格。因为e d g e b r e a k e r 不依赖于熵编码就可以获得比较好的编码效 并- ，凶此非常适合于处理小型的几何模型。对于包含大量顶点和三角形的复杂几何模 “通过结合熵编码，e d g e b r e a k e r 方法可以获得平均小于1 5 ( 比特三角形) 的更 l 岛编码效率。 虽然几何压缩的概念直到1 9 9 5 年才由m d e e r i n g 正式提出来，但是人们在 姒i 的刚候就已经注意到几何压缩这个问题。如在p h i g sp l u s ，p e x ，x g l 以及扩 展的o p e n g l 等现代图形语言中广泛采用的三角形带就是一个显著的例子。这些三 角形带可以用一个包含顶点数据的数组进行描述，而且这个数组可以直接输送到图 形管道进行绘制。绘制三角形模型的一个最简单方法是对每一个三角形输入它的三 个顶点。然而，这些三角形并不是彼此孤立的，相互之间苻许多公共的顶点。因此， 采用这种最简单的绘制方法需要重复输入许多项点，增加了陶形管道的负载，真接 影响了图形硬件的处理效率。为了减少应用程序和图形管道之间的数据传输，人们 将物体的三角形组织成三角形带的结构进行绘制。在绘制三角形带的过程中，前后 相继绘制的两个三角形具有一些公共的顶点。通过在图形处理器中设置一个顶点缓 冲器，这些公共的顶点数据在第一次使用的时候会被暂时存储在顶点缓冲区中，在 第二次使用的时候可以不用再重复传送，而只需要熏用顶点缓冲器中的数据即可。 通常顶点缓存器大小为2 ，即可以暂时存储两个顶点的数据。在利用二三角形带对三 维几何网格进行压缩方面，国内浙江大学的刘新国博士提出了一种有效方法“o3 ，如 图1 4 所示，l - s t r i n g 与0 一s t r i n g 是两种基本的三角形带，该方法借助区域增长 方法将原始网格模型分解成若干基本的l - s t r i n g 和o - s t r i n g ，然后对其进行相应 酌结构编码。实验结果表明，利用该方法对拓扑连接关系进行压缩的效率总是低于 17 0b i t t r i a n g l e ，平均压缩率是1 ，4 2b i t t r i a n g l e 。 第s 页 i h 刈山，、? ，触l 学位论殳 j t l 一球向磬数化的维儿f 扯缩 铀o ( a ) 三斯和( ”o 岱e r i p 图卜4 基本层结构 f i g l 4b a s i cs t r i n gs t r u c t u r e sg u m h o l d 等人提出了一种c u t b o r d e rm a c h i h e 编码算法1 ，用于对网格拓 扑信息进行快捷、有效的编码。该算法无需考虑网格的整体特性，因此具有实时编 码和解码速度。c u t - b o r d e rm a c h i n e 拓扑编码的特点是实现简单，编码的时候， 每构造+ 个三角形，边界边都输出一个操作码。因为编码过程的本身就是构造性的。 因此解码过程很容易实现，只需要依次解释编码时产生的每一个构造命令，构造相 应的一i 角形即町。所以c u t b o r d e rm a c h i n e 拓扑编码和解码的速度都非常的快。 ：i ，p e n t i u m3 0 0 m h z 的机器上，平均可以达到每秒钟7 5 0 ，0 0 0 个三角形的编码速度 和每秒钟1 ，5 0 0 ，0 0 0 个三角形的解码速度。对于输出的构造操作码再使用h u f f m a n 编码，c u t b o r d e rm a c h i t i e 拓扑编码算法的效率可以达到1 6 ( 比特三角形) 。 与三角形网格比较，以任意多边形面片表示的网格的拓扑压缩研究相对较少。 然而在那些精细设计的场合，非三角形网格得到了广泛应用。另外，利用当前造型 软件系统的镶嵌方法也很少产生三角形网格模型，而是产生大量的五边形、六边或 者更高边数的面片。一些早期的任意多边彤网格拓扑结构压缩方法能够达弱 9 b v ，这些方法通过建立顶点和面之间的连锁扫描树来实现压缩。c h u a n g 等人 “4 i 后来利用规范排序和多重插入项实现了一个更加紧凑的编码方法，他们报告说任 何简单的3 通平面图能够达到每条边不超过2 4 b i t s 的拓扑编码率。l i 和k u o o ”利 用“对偶”方法遍历对偶网格的边并输出一系列长度不同的特征，最后的序列通过 。个基于前后关系的墒编码器进行编码。i s e n b u r g 和s n o e y i n k 利用一个叫做“面 固定器”的方法对多边形网格的拓扑关系进行编码“1 ，这个算法基于入口而实现， 入口指定了被访面片的一个有向边，整个网格的遍历结果通过沿着边界环的连续入 口标签来组织。正如。“中说述，编码器和解码器都需要一个堆栈来记录活动的边 界环。遍历当前活动入口时，需要7 个不同的标签，r s ，e h 。以及m 。来描述到固 定面和孔的路径。k i n g “，k r o n r o da n dg o t s m a n “6 1 以及l e e “”等人将普通的压缩方 法推广到任意多边形网格模型，然而没有一个多边形网格编码方法能够达到最好三 第6 页 f f jj 眵阳格模型址缩方法的压缩率。 1i2 几何信息压缩 几何信息是构成几何模型的另一个重要组成部分。具体来讲，一个几何模型的几 何信息值包括模型上顶点的位置坐标、法向量、颜色以及纹理坐标等属性。因此几何 乐缔的另一个重要的内容是几何信息编码”1 “”2 “。 顶点坐标是一个几何模型中必不可少的几何属性，网格模型中的顶点坐标通常表 1 i 为三个浮点数，每个浮点数由四个字节表示。这