（计算机软件与理论专业论文）细分曲面造型及几何压缩算法研究与设计.pdf

细分曲面造型及几何压缩算法研究与设计摘要 论文题目：细分曲面造型及几何压缩算法研究与设计 专业：计算机软件与理论 博士生：陈任 指导教师：罗笑南教授 摘要 近些年，细分方法成为了几何造型领域最活跃的研究热点之一。随着人们在 细分领域的不断开拓和研究，在细分的连续性理论、多分辨率表示、非正则规则 的构造技术等方面，人们已取得了许多进展，导致了许多具有不同特性的细分方 法的涌现。但是，就目前来说，细分方法要取代传统c a d c a g d 方法的地位仍 有许多未完成的工作。同时，随着计算机浮点运算能力和图形加速能力的飞速提 升，应用实践对三维模型的真实感和细腻度的要求越来越高，导致三维几何模型 的拓扑信息和几何信息量急剧增长，从而也为模型数据的传输和存储带来了严峻 的考验。 本文的研究内容包括两个方面，第一是研究一些行之有效的造型方法，以进 一步提高细分曲面的造型能力。细分模式大致可以分为插值细分和逼近细分两 种，插值细分更加容易控制生成网格的形状，并得到了广泛应用，本文也在前人 的基础上进一步研究了三角形网格上的插值细分模式。一般说来，细分的运算速 度与其新顶点生成掩膜的大小有着密切关系，本文通过研究如何减少掩膜中参考 顶点数，在第2 章里提出了一种快速的1 4 分裂插值细分方法，与现有b u t t e r f l y 细分兼容，且在不牺牲过多曲面质量的前提下，达到快速细分的目的。此外，观 察到现有b u t t e r f l y 方法在细分曲面质量上的不足，本文第3 章重新设计了 b u t t e r f l y 细分掩膜，以达到提高细分曲面效果的目的，提出了一种曲率有界且 c 1 连续的插值细分，最后通过傅立叶分析把正则掩膜推广到任意拓扑的网格上。 本文第二个研究方向是几何模型压缩和渐进传输算法，该算法有利于减少几 何模型数据信息的冗余，提高模型的传输速度，加速模型的显示。本文以四边形 面片为基本研究对象，根据几何模型拓扑信息和几何信息的不同特点，分别研究 拓扑信息的简化和几何信息的数据压缩两个方面内容，并结合这两方面的研究建 细分曲面造型及几何压缩算法研究与设计摘要 立一个完整的四边形面片压缩和渐进传输算法框架。在拓扑信息的简化上，本文 主要研究基于细分小波的面片简化。文章运用提升算法和k o b b e l t 提出的细分模 型建立四边形插值细分小波，再利用该细分小波对面片进行简化，达到拓扑信息 简化的目的。在面片简化的同时，部分几何信息会转化为小波系数，方便了后续 几何信息的压缩。 在几何信息的压缩上，本文主要研究小波系数的量化和零树构建两方面内 容。文章首先根据各简化层次面、边的对应关系，提出小波系数的组织方式，构 建出基于浮点数域的四叉树。接着，本文参照e z w 算法提出浮点形式的逐次逼 近量化，给出量化阈值的计算公式，从而结合熵编码技术对四叉树进行量化编码， 实现几何信息的数据压缩。最后，本文综合上述几何压缩、数据压缩的研究内容， 结合面片重构、熵编码等算法，给出一个面向四边形面片的压缩和渐进传输算法 框架，并对框架的部分算法实现进行阐述。通过对实际模型的试验，该算法有较 高的压缩比，同时支持渐进传输和显示，达到了预期的目的。 随着三维图形显示的推广，本文的成果将会有较好的应用前景，对于三维技 术的推广和应用具有十分重要的现实意义。 关键词：细分曲面、几何压缩、1 - 4 分裂、细分小波、提升算法、系数量化、零 树编码、e z w 算法 i l 细分曲面造型及几何压缩算法研究与设计 a b s t r a e t t i t l e ：r e s e a r c ha n dd e s i g no fs u b d i v i s i o ns u r f a c em o d e l i n ga n dg e o m e t r y c o m p r e s s i o na l g o r i t h m m a j o r ：c o m p u t e rs o l t w a r ea n dt h e o r y n a m e ：c h e nr e n 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 s u b d i v i s i o ns u r f a c ei sv a l u e di ng e o m e t r i cm o d e l i n gf o rt h e i rc o n v e n i e n c ea n d f l e x i b i l i t y i ta l l o w st h ea r b i t r a r yt o p o l o g i c a lo b j e c t st ob er e p r e s e n t a t e di na ne a s y d e s i g n ，r e n d e ra n dm a n i p u l a t ef o r m i nt h er e c e n td e c a d e ，al a r g en u m b e ro fo n g o i n g l i t e r a t u r e sa n dr e s e a r c h e so ns u b d i v i s i o nc a nb ef o u n d a l t h o u g hm u c hp r o g r e s sh a s b e e nm a d e ，s u b d i v i s i o ns c h e m e ss t i l lh a v es o m eu n r e s o l v e dp r o b l e m s ，m a k i n gi t d i f f i c u l tt ob ei n t e g r a t e di n t op r e s e n tc a d c a g ds y s t e m s w i t ht h ed r a m a t i cg r o w t h o ff l o a t i n g p o 缸o p e r a t i o na n dg r a p h i c sa c c e l e r a t i o n , h i g h l yr e a l i s t i ca n ds m o o t h3 d m o d e l sa l er e q u i r e db yv a r i o u sa p p l i c a t i o n s 1 1 1 ei n c r e a s i n gr e q u i r e m e n tl e a d st oh i g h d e m a n do fc o m p l e x i t yo ft o p o l o g i c a la n dg e o m e t r i ci n f o r m a t i o n , a n dc o n s e q u e n t l y p u tf o r w a r dg r e a tc h a l l e n g e s t ot h es t o r a g ea n dt r a n s m i s s i o no fm o d e ld a t a c o n t e n to ft h i st h e s i sc a nb ed i v i d e dt ot w op a r t s o n ei st h er e s e a r c ho nd e v e l o p i n g n e wm o d e l i n gm e t h o d s ，e s p e c i a l l yt h ei n t e r p o l a t o r ys u b d i v i s i o ns c h e m e so nt r i a n g u l a r m e s h , t om a k es u b d i v i s i o na d a p t i v et ov a r i o u sa p p l i c a t i o n s s u b d i v i s i o ns c h e m e sc a n g e n e r a l l yb ed i s t i n g u i s h e di n t oi n t e r p o l a t o r ys c h e m ea n da p p r o x i m a t o r ys c h e m e s i n c et h es h a p eo fr e f m e dm o d e l sc a nb ee a s i l yc o n t r o l l e db yi n t e r p o l a t o r ys c h e m e s ， t h i st y p eo fs c h e m e sd r a w sm u c ha t t e n t i o nf r o mc a d c a g dr e s e a r c h e r sa sw e l la s a n i m a t i o nd e s i g n e r s i ti sk n o w nt h a tt h e r ei sac l o s er e l a t i o nb e t w e e nt h ee f f i c i e n c y a n dt h e s i z eo ft h em a s ko ft h es u b d i v i s i o na l g o r i t h m t h ep r e s e n tw o r ks e e k st o r e d u c et h e s i z eo ft h em a s ka n dt h e ni n t r o d u c e saf a s ti - 4s p l i t t i n gs u b d i v i s i o n a l g o r i t h m m o r e o v e r , i nv i e wo ft h ed i s a d v a n t a g e so ft h eb u t t e r f l ys c h e m e ，w e r e d e s i g nt h eg e o m e t r i cr u l e sa n de x t e n dt h en e wr e g u l a rr u l e st oa r b i t r a r yt o p o l o g y w i t ht h eh e l po fo p e n g l ，e x p e r i m e n t a lr e s u l t sa r ep r e s e n t e dt oi l l u s t r a t et h ev i s u a l q u a l i t yo ft h e s en e w l yd e s i g n e da l g o r i t h m s i i i 细分曲面造型及几何压缩算法研究与设计 s e c o n d l y , w ed i s c u s st h eg e o m e t r yc o m p r e s s i o na n dm u l t i r e s o l u t i o ne x p r e s s i o nf o r q u a d r i l a t e r a lm e s h e s ，a n di tw i l lh e l pt or e d u c et h er e d u n d a n c yo fm o d e ld a t aa n dt o i m p r o v et h et r a n s m i s s i o ns p e e da n dr e n d e r i n gs p e e do ft h r e ed i m e n s i o n a lm o d e l s f o c u s i n go nq u a d r i l a t e r a lm e s h , t h el e f tp a r to ft h i st h e s i sd i s c u s s e sh o wt os i m p l i f y t h et o p o l o g i c a li n f o r m a t i o na n dt h ew a yt oc o m p r e s sg e o m e t r i ci n f o r m a t i o na c c o r d i n g t o t h ec h a r a c t e r i s t i c so ft o p o l o g i c a la n dg e o m e t r i ci n f o r m a t i o n t h i sp a r ta l s o c o m b i n e st h e s et w oa s p e c t st oe s t a b l i s ha n i n t e g r a t ef r a m e w o r kf o rg e o m e t r y c o m p r e s s i o na n dm u l t i r e s o l u t i o ne x p r e s s i o no fq u a d r i l a t e r a lm e s h e s i no r d e rt o s i m p l i f yt o p o l o g i c a li n f o r m a t i o n ，w ec o n s t r u c ta l li n t e r p o l a t e ds u b d i v i s i o nw a v e l e tf o r q u a d r i l a t e r a lp a t c h e sb a s e do nt h es u b d i v i s i o ns c h e m ea d v a n c e db yk o b b e l ta n d l i f t i n ga l g o r i t h m w i t ht h i ss u b d i v i s i o nw a v e l e t ，w ec a ne a s i l ys i m p l i f ya n yr e g u l a r q u a d r i l a t e r a lm e s ha n dc o n s e q u e n t l ya r c h i v eo u ra i ma tt o p o l o g i c a li n f o r m a t i o n r e d u c t i o n t h es i m p l i f y i n gp r o c e s sa l s ot u r n ss o m eo fg e o m e t r i ci n f o r m a t i o ni n t o w a v e l e tc o e f f i c i e n t sa n dt h i sw i l lf a c i l i t a t et h ef o l l o w - u pg e o m e t r i cc o m p r e s s i o n i ng e o m e t r i cc o m p r e s s i o n ，t h i sp a r tf o c u s e so nq u a n t i z a t i o no fw a v e l e tc o e f f i c i e n t s a n dc o n s t r u c t i o no fz e r o - t r e e t h et h e s i sf i r s td i s c u s s e st h es t a t i s t i c a lp r o p e r t i e so f w a v e l e tc o e f f i c i e n t so fd i f f e r e n ts i m p l i f i e dl e v e la n dt h ec o r r e l a t i o n sb e t w e e nt h e m t h e n , w ep r o p o s eas u c c e s s i v e - a p p r o x i m a t i o nq u a n t i z a t i o nb a s eo nf l o a t i n g - p o i n t d o m a i nt ot h ew a v e l e tc o e f f i c i e n t si nt h el i g h to fe z w , a n d p r e s e n tt h ec o m p u t a t i o n f o r m u l af o rt h r e s h o l d w i t hs u c c e s s i v e - a p p r o x i m a t i o nq u a n t i z a t i o na n de n t r o p y c o d i n g ，w ec a i le a s i l ya p p l yd a t ac o m p r e s s i o nt ot h ez e r o t r e et oa c h i e v et h eg o a lo f g e o m e t r i ci n f o r m a t i o nc o m p r e s s i o n a tl a s t ，w ep u tf o r w a r daf r a m e w o r kf o r g e o m e t r yc o m p r e s s i o na n dm u l t i r e s o l u t i o ne x p r e s s i o nf o rq u a d r i l a t e r a lm e s h e sb a s e d o nt h ea b o v ed i s c u s s i o n sa n dr e m e s h i n ga n dz e r o - t r e ec o m p r e s s i o na l g o r i t h m i m p l e m e n to f t h ek e ya l g o r i t h m sa l ea l s op r e s e n t e di nt h i sp a r t k e y w o r d s ：s u b d i v i s i o ns u r f a c e ，g e o m e t r yc o m p r e s s i o n ， 1 - 4 s p l i t t i n g , s u b d i v i s i o nw a v e l e t ，l i f t i n ga l g o r i t h m ，q u a n t i z a t i o n ，z e r o - t r e ec o d i n g ，e z w a l g o r i t h m i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： i k0 = l h 0 0 厶8 ( 1 2 ) 在一连续的基础上，若要使细分曲面拥有曲率有界的性质，那么其6 个模 最大的特征值应进一步满足如下结构，l o o p 把此结构称为b o u n d e dc u r v a t u r e s p e t r u m 2 9 1 ： 1 ，彳，允，五2 ，2 2 ，2 2 ( 1 3 ) 无论是r e i f 的理论还是l o o p 的进一步探讨，此套理论体系都只能数值地证 明细分曲面的连续性问题。若已知一个曲面中心是一个度数为n 的顶点，那么 r e i f 他们的理论能够验证此细分极限曲面一连续性以及曲率有界问题。但无法 一般地证明所有度数的情况都能满足一连续和曲率有界条件，只能分别地验证 单个度数的连续性。不过一般来说，验证度数1 0 0 以下的连续性已经能够满足工 业及计算机动画需求。 z o r i n 在1 9 9 8 年提出了能够分析任意网格的矿连续性理论【3 0 】。z o r i n 的突出 贡献在于成功地解决了分析奇异点的高次连续性问题。z o r i n 的分析理论主要基 于细分矩阵、特征基函数( e i g e nb a s i sf u n c t i o n ) 和参数映射( p a r a m e t r i cm a p ) 。 但是该方法的推导和应用都十分复杂繁琐，鲜见于用其作为细分模式的分析手段 的文献。 东京大学的k a w a h a r a d a 最近提出了一种新的连续性分析理论1 3 1 1 。细分曲面 特别是插值细分曲面，对曲面进行参数化分析是一件非常困难的工作。为了避免 直接分析细分曲面本身，k a w a h a r a d a 分析细分模式的面片法向量细分模式 ( n o r m a ls u b d i v i s i o ns c h e m e ) 来决定细分曲面的连续性。基于法向量细分模式， 细分曲面造型及几何压缩算法研究与设计第l 章细分曲面造型及几何压缩方法综述 他推导出了曲面c k 连续的充分必要条件。该方法在证明步骤上比z o r i n 的方法 简洁许多，应该会在将来的细分证明工作中扮演重要的角色。他推导的方法虽然 能够适用于任意拓扑的网格，但是也如r e i f 的方法一般，只能从数值上证明单 个度数的奇异点网格的连续性问题，无法证明整个方法的任意度数都满足某阶的 连续性，是为该方法的一个不足。 1 4 细分曲面模式构造方案 细分曲面模式的构造主要有两个部分组成：( 1 ) 正则规则的构造，使细分模 式能够适用正则网格，对正则网格进行细化：( 2 ) 非正则规则的构造，细分模式 比传统c a d 方法的主要优势就在于对于任意拓扑网格的处理能力，因而非正则 模式的构造对于整个细分有着非常重要的意义。 1 4 1 细分曲线到曲面的推广 表1 1主要细分模式及其来源 应用对象细分模式网格类型特性来源 b 样条曲线 逼近 b 样条 曲线四点法曲线插值 l a g r a n g e 插值 割角法曲线逼近b 样条 l o o p 三角形逼近b o x 样条 b u t t e r f l y 三角形插值 l a g r a n g e 插值 曲面c c四边形逼近b 样条 3 三角形逼近 l a g r a n g e 插值 2四边形逼近 l a g r a n g e 插值 对于插值细分曲面，正则规则构造的灵感通常来自于细分曲线的进步。d y n 于1 9 8 7 年提出了四点法曲线细分模式【8 j ，受到该方法的启发，d y n 于1 9 9 0 年又 提出了b u t t e r f l y 曲面细分模式【7 】。当一个正则三角形网格沿着三角形任意一条边 的方向压缩为一条曲线的时候，b u t t e r f l y 方法和四点法是等价的，因而可以把 b u t t e r f l y 方法看成是四点法在三角形网格上的推广。同样来源于四点法，k o b b e l t 也提出了基于四边形网格的细分模式【9 1 。插值3 细分【1 4 1 、插值2 细分【1 6 1 同理 也可以看成是四点法在相应类型网格的拓展。 细分曲面造型及几何压缩算法研究与设计第l 章细分曲面造型及几何压缩方法综述 下面以b u t t e r f l y 细分为例，介绍曲线到曲面的推广法则。这里提前涉及了细 分模式的细节，关于四点法的具体细分模式可以参考2 2 节，b u t t e r f l y 细分模式 可以参考3 2 节。 一 ( a ) 图1 - 3 b u t t e r f l y 细分与四点法细分之间的推广关系 从2 2 节中我们已知四点法的掩膜中四个顶点的系数分别为口d 、口卜口2 、幻， 那么图1 3 中描述的b u t t e r f l y 掩膜若要成为四点法在曲面上的推广，则b u t t e r l f y 掩膜中的系数应满足如下约束： 兰a ：o 三= 二y ：三：； ? 三：+ l 兰：三多+ 口+ 7 l 1 2 2 口 ( 1 4 ) 这样当正则网格沿着图1 3 ( a ) 中虚线方向压缩时，新顶点生成的位置和四 点法是一致的；当正则网格沿着图1 3 ( b ) 中虚线的方向压缩时，新顶点的生成 不影响曲线( 一个压缩成曲线的曲面) 原有的形状。 1 4 2 傅立叶分析在非正则规则构造中的应用 对于插值细分而言，由于非正则规则构造的困难，直到1 9 9 6 年才真正出现 了第一个能处理任意拓扑三角形网格的插值细分模式【1 2 1 ，此方法是b u t t e r f l y 方 法的一次重要改进。若一个细分模式要对c a d 产生真正的作用，无论对于正则 还是非正则网格而言，其生成的曲面至少应该是一连续，但是对于如何使奇异 点附近曲面达到一连续一直是一个难题。我们知道检验一个曲面是否为c 。连续 的一个非常重要的必要条件是其细分矩阵的特征值的结构【1 0 1 。因而研究如何保持 细分曲面造型及几何压缩算法研究与设计第l 章细分曲面造型及几何压缩方法综述 细分矩阵的特征值结构，使其满足公式( 1 1 ) 中的结构特征是设计非正则规则 的一个可行研究方向。 一般而言，我们的得到的细分矩阵都能转化为循环矩阵的形式。而傅立叶分 析在循环矩阵的一个重要的应用就是可以在保证循环矩阵特征值结构不变的情 况下，拓展矩阵的循环块数目。若一个正则的细分矩阵由6 个循环块所组成，那 么运用傅立叶分析到这个细分矩阵上，我们可以构造出一个新的循环矩阵，这个 新矩阵可以由任意n 个循环块所组成，这个新的矩阵和原矩阵有着同样的特征值 结构。因而新构造出的细分矩阵也能保证满足连续的必要条件。只要再验证 细分矩阵的特征映射是否满足单射和正则，则可知新构造的细分矩阵是否具有 一连续的属性。此方法已经被运用到了许多细分模式的构造上【1 2 ，1 6 ，1 8 , 1 9 】。 1 5 几何压缩概述 几何压缩在计算机图形学应用范围日益扩大，作用日益增加的同时，人们对 计算机图形合成质量也在不断地提出新的要求。但是要合成高质量的画面，往往 需要有足够精细的几何模型。因此在计算机图形学的许多应用中使用的三维几何 数据的数量和复杂不断地急剧增长着。新的造型工具和模型重建技术的出现也促 成了这一发展趋势。如何实时有效地处理这些日益增多和日渐复杂的三维几何数 据成为计算机图形学发展中的一个巨大挑战。再者，随着网络图形学的发展，越 来越多地需要通过网络，特别是国际互联网，来存取那些贮放在异地的三维几何 数据。这些日益增多和日渐复杂的三维几何数据也使得本以十分有限的网络带宽 带变得更加的紧张。 总之，计算机图形学应用的特点之一是广泛地使用三维几何数据。而且随着 计算机图形学及其相关理论和技术的快速发展，这些在数量规模和复杂程度还在 日益增长三维几何数据在不断满足需求的同时，也给我们带来了许多问题和巨大 挑战，概括的讲包括以下三个方面的内容： ( 1 ) 图形适配器因为没有足够的内存完全装栽巨大的模型，或者受限于数 据传输瓶颈而不充分地能够发挥其图形处理的性能。 细分曲面造型及几何压缩算法研究与设计第1 章细分曲面造型及几何压缩方法综述 ( 2 ) 在三维c a d 系统中的模型变得越来越复杂，大大地增加了处理这些模 型的所需的内存代价和辅助外存的代价。 ( 3 ) 如今的许多应用，如协同设计( c 0 1 1 a b o r a t i v ed e s i g n ) 、网络游戏、 快速成型、虚拟交互等等，都需要发布传输三维的几何模型。但是现有的网络带 宽严重限制和阻碍了这些发布传输。 为了解决上述的这些问题，我们可以通过升级和提高图形处理的性能，增加 网络带宽等硬件方面的办法来解决。但是仅仅这样是不够的，还需要软件算法方 面措施，如： ( 1 ) 在下载和绘制几何模型的时候，选择性的处理那些潜在可见的部分。 ( 2 ) 在适当的时候使用图像代替复杂的几何模型。 ( 3 ) 对远距离处的物体使用多分辨率的、简化的几何模型，当几何物体慢 慢的走进的时候，渐进式的细化地分辨率的几何细节。 ( 4 ) 使用几何压缩方法，设计几何模型的紧致表示，减少它的存储空间和 传输时间，使得它适合于利用硬件进行快速绘制。 人们已经在上面的这些方向上作了许多的工作，如基于图像的建模和绘制方 法( 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 m p r e s s i o n ) 等等。 应用的需求，为理论研究的发展提供了强大的推动力，人们开始研究如何对 模型进行简化和数据压缩，以适应实际应用的需求。1 9 9 5 年，s u n 公司的d e e r i n g 发表了g e o m e t r yc o m ”e s s i o n i 弛】一文，揭开了三维几何压缩的序幕。m d e e r i n g 几何压缩方法的目的是压缩几何数据，减少c p u 和图形卡之间的数据传输，从而 加快图形处理的速度。在该方法中引入了一个网格缓存器，用来存储1 6 个曾经 使用过的旧顶点。然后通过重用网格缓存中的旧顶点来减少需要传输的顶点数 据。同时对需要的传送的顶点几何数据进行量化和增量编码进行压缩。在这之后， 相关的压缩算法不断被提出，进行了各种改进和提高，各种工程化的技术也不断 细分曲面造型及几何压缩算法研究与设计第l 章细分曲面造型及几何压缩方法综述 地被提出【3 3 - 3 5 。 在研究中，通常把网格模型所包含的信息划分为三个部分：第一部分为拓扑 信息( t o p o l o g i c a li n f o r m a t i o n ) ，主要描述网格模型中顶点与面片之间的邻接关 系：第二部分为几何信息( g e o m e t r i ci n f o r m a t i o n ) ，用于描述网格模型的项点的 坐标位置，几何信息一般都以单精度的浮点数形式存放，因此所占用的空间相对 比较大；第三部分为属性信息，包括颜色、法线向量以及纹理坐标等信息【矧。 在p r o g r e s s i v eg e o m e t r yc o m p r e s s i o n t 3 7 一文中，k h o d a k o v s k y 等人对几何信 息做了进一步的分析，将参数信息( p a r a m e t e ri n f o r m a t i o n ) 从几何信息中剥离出 来，缩小了几何信息的内涵。从直观上理解，我们可以简单地将几何信息理解为 顶点坐标沿法向方向的分量，这个量对于面片的拟合程度有较大的影响；参数信 息则可以理解为顶点坐标沿切线方向的分量，该分量对面片拟合程度的影响较 小。在下文中，我们将不详细区分几何信息这个概念：在与参数信息一起使用的 时候，几何信息是狭义上的几何信息，其它情况下一般都指广义上的概念。 网格模型不同信息的划分，带来了不同的压缩途径。研究人员针对拓扑信息 和几何信息提出了多种不同的算法，促进了几何模型压缩的发展。 1 5 1 拓扑信息压缩技术 对于一个几何模型而言，它的项点通常采用一个浮点数组来表达，而边、面 则是用顶点的数组下标来表达。通常，几何模型边和面的数量都是相当庞大的。 所以，拓扑信息压缩的目的就是尽量减少模型中所需记录的顶点数目，或者是尽 量避免同一个顶点序号在拓扑信息中多次出现。目前的拓扑信息压缩技术分为以 下五种类型： ( 1 ) 基于三角形带的压缩 这类压缩算法的基本思想为建立带状的三角形结构来组织几何模型，使得同 分类方法参照了学术报告几何模型压缩( 作者：王文成，中国科学院软件研究所) h t t p ：w w w c a d z j - c d u c r g c h i n a g r a p h c h i n e s e h o t r e p o r t c g _ s y m p o s i u m 0 5 _ w a n g w e n g c h e n g _ g m c p a l 细分曲面造型及几何压缩算法研究与设计 第1 章细分曲面造型及几何压缩方法综述 一顶点在某个三角形带中最多只出现次，从而减少同一个顶点序号在不同三角 形拓扑信息中出现的次数【驯。这类算法的实质，是利用了相邻三角形具有一条共 边、两个共同顶点的特性，只记录一次共边上的顶点，从而达到减少拓扑信息的 目的。 v 3v 5 场v 2 图1 4 三角形带示例 如图卜4 所示，三角形& 与s 。之间存在着邻边k ，所以在记录、s 。时， 可以只记录一次k ，从而减少拓扑信息的记录；在绘制三角形带时，则通过设 置缓冲器暂存公共顶点，减少后续数据的传输量。比如说在绘制品、s 。时，可 以先绘制三角形岛，然后通过顶点缓冲器记录顶点k 和，绘制墨时就可以只 传送蚝。 根据三角形带形状的不同，常用的三角形带有星形三角形带( s t a rt r i a n g l e s t r i p ) 、锯齿三角形带( z i g z a gt r i a n g l es t r i p ) 、广义三角形带( g e n e r a l i z e dt r i a n g l e s t r i p ) 三种。 35 2 图1 5 简单三角形带( a ) 星形三角形带( b ) 锯齿形三角形带( c ) 独立四边形 细分曲面造型及几何压缩算法研究与设计第l 章细分曲面造型及几何压缩方法综述 星形三角形带如图1 - 5 ( a ) 所示，首先输入三角形带中的第一、第二个顶 点，并且把它们依次存入顶点缓存器中。此后每输入一个新的顶点都和缓存器中 两个顶点一起共同定义一个新的三角形，并且这个新输入的顶点也存放入顶点缓 存其中，覆盖缓存器中较晚存入的那个顶点。在这个过程中，显然最先输入的那 个顶点一直都在顶点缓存器中，所以它出现在所有三角形上。这些三角形构成一 个星形结构，因此称它们为星形三角形带。 锯齿三角形带这是目前使用最为广泛的一种简单三角形带。如图1 - 5 ( b ) 所示，首先输入第一和第二个顶点，并且把它们依次存入顶点缓存器中。此后的 每一个新的顶点都和缓存器中两个顶点一起共同定义一个新三角形，并且这个新 输入的顶点也存放入顶点缓存其中，覆盖缓存器中较早存入的那个顶点。由此可 见，实现这种三角形带和实现星形三角形带的唯一区别在于缓存器中的顶点覆盖 的策略不一样。在星形三角形带中，总是覆盖较晚缓存的那个顶点，而在锯齿三 角形带中总是覆盖较早缓存的那个顶点。 虽然通过重用，上述两种三角形带可以减少对同一个顶点的重复传输，二加 快对三角形网格模型的绘制速度。但是这种方法要求我们必须事先生成这些三角 形带，而生成一个高效的三角形带表示并不是一件容易的事情。因此在一些商业 软件中也经常采用一种更加简单的三角形带一独立四边形。如图1 - 5( c ) 所 示，一个独立四边形由4 个顶点构成，其中顶点1 、2 、3 和顶点1 、3 、4 分 别定义了两个三角形。 图l 石广义三角形带 广义三角形带广义三角形带是最复杂的一种三角形带。在广义的三角形带 中既可以像锯齿三角形带那样构造新的三角形，也可以像星形三角形带那样构造 新的三角形， 如图1 - 6 所示。另外，还可以构造不共享边或顶点的三角形，以 1 8 - 细分曲面造型及几何压缩算法研究与设计第1 章细分曲面造型及几何压缩方法综述 及改变三角形的顶点的排列顺序。广义三角形实现这些功能的代价是在每个顶点 的前面都要加上一个大小为2 个比特的控制字。为了便于理解这些控制字，假 设有一个顶点缓冲器，用于存储最近访问的2 个顶点。广义三角形的顶点控制 字一共有4 个，它们是： r e s e t ：重新开始一个新的三角形带。 r e s e tr e v e r s e ：改变三角形的顶点顺序。 r e p l a c eo l d e s t ：取代顶点缓存中第一个项点。 r e p l a c em i d d l e ：取代项点缓存中第二个顶点。 使用顶点控制字获得的好处是可以制成更长的三角形带。实验的经验表明： 锯齿三角形带的平均长度为4 - 8 个三角形，而广义的三角形带的平均长度可以达 到1 4 - 3 0 个三角形。上述的几种三角形带都可以用一个顶点数组来存储。这中存 储形式和传统的编程语言中的数据结构相容一致，使得它们都在计算机图形学中 得到广泛的使用。 ( 2 ) 基于度驱动的压缩 这类算法的基本思想是以一个三角形开始，根据每个点的度不同逐步处理各 个点；当点的度用完时，再对相关的点进行处理。简单一点来说，该类算法是利 用了图论中顶点度的概念，通过入度出度值对网格的拓扑信息进行编码。 这类算法的典型代表为t o u m a 在文献m 中提出的入度编码法。和c u t - b o r d e r m a c h i n e 类似，入度编码法在网格上任选一个初始三角形，用该三角形的三个顶 点构造一个循环项点链表( v e r t e xl i s t ) ，并且取其中一个顶点为焦点( f o c u s ) 。 如果编码的被编码的网格是有边界的，那么首先通过引入哑顶点( d u m yv e r t e x ) 的方法，把它转换成封闭的网格。在编码的过程中，按照逆时针次序处理焦点上 的所有的入边。每处理焦点一条入边，对应的顶点都将添加到链表中。当处理完 所有的入边之后，首先输出一个a d d 命令，然后从顶点链表中删除 该焦点，并且把顶点链表中的下一个顶点选作为焦点。在这个过程中，顶点链表 有可能发生自交，此时需要将它分裂为两个顶点链表，并且输出一个s p l i t 命令。此外，顶点链表有可能发生和别的顶点链表重叠，此时需要将 这两个顶点链表合并为一个大的顶点链表，并且输出一个m e r g e 命令。在接近规则网格的情况下，网格顶点的入度是一个均值为6 的 概率分布，越靠近6 的入度值出现的概率越大。因此，如果采用熵编码对顶点的 入度值进行压缩，该网格的顶点入度编码可以获得小于l b v 、甚至0 2 b v 的编 码结果。 ( 3 )基于区域扩张的压缩 该类算法的基本思路与基于度驱动的压缩的方法类似，它从一个种子三角形 开始，逐渐地扩张所处理的三角形，直到覆盖整个网格模型。但与后者不同的是， 这类算法输出的是拓扑变化，而不是点的度。 该类算法的典型方法为r o s s i g n a c 提出的e d g e b r e a k e r t 4 0 】算法。该编码方法是 目前最好的编码方法之一，具有编解码速度快、便于硬件实现的特点。它还有一 个最坏情况下的编码效率的估计值，该估值为4 b v 。 该算法的基本操作为：以一条边作为入口，以边对应的顶点环绕一周的边作 为一个顶点环，从入口开始按照相邻关系对网格上的三角形依次进行遍历。对每 个遍历三角形而言，会有两个顶点位于顶点环的入口，然后根据它的第三个顶点 的各种不同情况输出一个不同的操作码，最后所有操作码形成一个码串，称之为 操作码历史。 ( e s 图1 7 算法遍历过程的五种不同情况，下方字母为输出的操作码( 摘自文献【4 0 1 ) c u t - b o r d e rm a c h i n e 编码【4 1 ，4 2 1 是s g u m h o l d 等人提出的一种算法，用于 细分曲面造型及几何压缩算法研究与设计第1 章细分曲面造型及几何压缩方法综述 对网格拓扑信息进行快捷、有效地编码。该算法的特点其具有局部性，无需考虑 网格的整体特性，因此具有实时编码和解码速度。c u t - b o r d e rm a c h i n e 编码算 法和e d g e b r e a k e r 编码算法极为相似。它首先任取一个三角形，以它的三个项 点建立一条初始分割线( c u tb o r d e r ) ，分割线上的一条边被选为当前边，称为 入口( g a t e ) 。然后沿着分割线遍历网格和构造网格中的三角形，并且动态维护 该分割线。在编码的过程中按照广度优先的遍历规则选择下一个入口。 ( 4 ) 基于分割的压缩 该类算法的基本思想为沿着边，将模型剖分并展开成平面，然后再将边、展 开的多边形形成树状结构，再对这些树进行压缩编码。该类算法的目的同样是为 了减少顶点在拓扑信息中的冗余记录，再利用数据压缩中的压缩算法对数据做进 一步的压缩操作。 拓扑手术算法( t o p o l o g i c a ls u r g e r y ) 【4 3 ，删是该类算法的典型代表。拓扑 手术是t a u b i n 和r o s s i g n a c 提出的一个三角形网格编码方法，其目的是压缩 几何数据，减少几何模型的磁盘空间，从而也可以减少几何模型在网络上的传输 时间。该方法首先为三角形网格构造一棵顶点树，然后沿着顶点展开树的边将网 格剪开、变成一个没有内点的简单多边形( s i m p l ep o l y g o n ) ，使得它可以通过 三角形展开树( t r i a n g l es p a n n i n gt r e e ) 和一些二进制匹配码来完全表示。由 于采用了树状结构进行存储，可以利用数据压缩相应的算法做进一步的压缩，具 有一定的优越性；但是这类算法的压缩过程中，需要同时维护两棵树，一个是顶 点展开树，另一个是三角形展开树，同时它是基于全局处理的，所以解码过程中 需要较大的存储空间，带来了一定程度的不足。 所谓的三角形展开树是三角形网