（计算机应用技术专业论文）三维网格压缩(1).pdf

摘要 三维图形数据是继声音( 1 d ) 、图像( 2 d ) 、视频( 2 d + t ) 之后的第四种媒体。 随着计算机图形学中三维建模和三维扫描技术的进步，数字化的三维图形数据 开始大量涌现，并在许多领域得到了广泛的应用。 三维图形数据的数据量一般比较大，必须要进行有效地压缩，以减少它们 对存储空间和网络带宽的需求。相对于音频、图像以及视频压缩的大量研究工 作而言，三维图形数据的压缩还是一个较新的课题。 目前的三维网格压缩研究主要关注于如何提高压缩效率。本文不仅考虑了 压缩效率，而且围绕网格的i n t e m e t 应用环境对网格压缩提出的要求，还考虑 了如何使网格的压缩数据具有可扩展性，以适应i n t e r n e t 的带宽异构性、时 变性和各种终端图形处理能力的差异，以及如何使网格压缩能够支持交互浏览 的随机访问特性等。本文主要包括以下创新工作： 1 提出了一种同时具有质量可扩展性和分辨率可扩展性的网格压缩方法，以 便使压缩位流能够适应网络带宽和终端图形处理能力的异构。该方法的压 缩位流中包含了多个子集，每一个子集相应于特定质量和分辨率的重构网 格，根据当前的网络带宽和终端的图形处理能力，只需传输和解码相应的 位流子集即可。该方法的压缩位流大小只有p o c 方法的7 5 左右，压缩比 接近2 0 0 倍。 2 提出了一种支持随机访问的网格渐进压缩方法。该方法只传输在当前视点 和视线下可见区域的表面细节的压缩数据，从而节约了网络带宽和解码资 源。在该方法中，传输可见区域的数据只需总数据量的6 0 左右。 3 ， 提出了一种基于小波变换的非渐进压缩方法。它利用重新网格化来去除冗 余信息，并充分利用了小波变换优异的去相关性能，取得了2 0 0 倍左右的 压缩比，是e d g e b r e a k e r 方法的2 倍多。 4 提出了两种新的单一位率压缩方法：分块o c t 压缩方法和基于邻域预测的 几何信息压缩方法，取得了较高的压缩效率。传统的单一位率压缩方法只 去除了遍历路径上相邻顶点间的相关性，而分块d c t 方法将网格进行分块， 利用d c t 变换来去除每一块内顶点间的相关性；基于邻域预测的压缩方法 北京工业大学工学博士学位论文 则利用邻域预测，来去除各个顶点与其邻域内顶点间的相关性。 最后，作者介绍了今后的进一步研究方向，并对本文进行了总结。 关键词：网格，几何压缩，渐进压缩，小波变换，可扩展性 i i a b s t r a c t 3 dg r a p h i cd a t ai st h ef o u r t hg e n e r a t i o nm e d i at y p ef o l l o w i n gt h ea u d i o ( 1 d ) i m a g e ( 2 d ) ，a n dv i d e o ( 2 d + t i m e ) w i t ht h ep r o g r e s so fm o d e l i n ga n d3 ds c a n n i n g t e c h n i q u ei nc o m p u t e rg r a p h i c s ，m o r ea n dm o r e3 dg r a p h i cd a t aa r ee m e r g i n g ，a n d w i d e l yu s e di nm a n ya r e a so fs c i e n c ea n dt e c h n o l o g y 3 dg r a p h i cd a t au s u a l l yp o s s e s sh u g ea m o u n to fs i z e t h ec o m p r e s s i o no f3 d g r a p h i cd a t aw i l lr e d u c et h es t o r a g ea n dt r a n s m is s i o nc o s te f f i c i e n t l y a sc o m p a r e d w i t hm a n yw o r k sd e v o t e dt oa u d i o i m a g ea n d v i d e oc o m p r e s s i o n ，3 dg r a p h i cd a t a c o m p r e s s i o ni sr e l a t i v e l yan e wr e s e a r c ha r e a c u r r e n t l ym o s tw o r k so n3 d m e s hc o m p r e s s i o nf o c u so nh o wt oa c h i e v eh i g h c o m p r e s s i o ne f f i c i e n c y b e s i d e st h i sg o a l t h i sp a p e rw i l la ls op u te m p h a s i so n h o wt og e n e r a t es c a l a b l em e s hb i t s t r e a m sw h i c hc a nb ea d a p t e dt ot h eh e t e r o g e n e i t y o fi n t e r m e tb a n d w i d t ha n dt e r m i n a l s g r a p h i c sc a p a b i l i t i e s ，a n dh o wt oi n c o r p o r a t e u s e r s i n t e r a c t i o nb e h a v i o ri n t oc o m p r e s s i o ns c h e m e st h ef o l l o w i n gi n n o v a t i r e w o r k sh a v eb e e nc o m p l e t e d at r i a n g l em e s hc o m p r e s s i o ns c h e m eh a sb e e np r o p o s e dw h i c hs u p p o r t sb o t h q u a l i t ys c a l a b i l i t ya n dr e s o l u t i o ns c a l a b i l i t y t h eg e n e r a t e db i t s t r e a m sc a n b ea d a p t e dt ot h eh e t e r o g e n e i t yo fi n t e r n e tb a n d w i d t ha n dt e r m i n a l s g r a p h i c sc a p a b i l i t i e s ；a c c o r d i n gt ot h ea v a i l a b l eb a n d w i d t ha n dt e r m i n a l s g r a p h i c sc a p a b i l i t y ，o n l yas u b s e to f t h eb i t s t r e a mi st r a n s m i t t e da n d d e c o d e d ，t h eb i t s t r e a ms i z eo ft h i ss c h e m ei sa b o u t7 5 o ft h a to fp g c ：t h e c o m p r e s s i o nr a t i oi sn e a r l y2 0 0 ：1 2 at r i a n g l em e s hc o m p r e s s i o ns c h e m eh a sb e e np r o p o s e dw h i c hs u p p o r t sr a n d o m a c c e s s i b i l i t y ，o n l yd a t ao fv i s i b l er e g i o n sa r et r a n s m i t t e da n dd e c o d e dt o s a v en e t w o r kb a n d w i d t ha n dd e c o d i n gr e s o u r c e s o n l ya b o u t6 0 o ft o t a l b i t s t r e a mi sn e e d e dt or e c o n s t r u c tv i s i b l er e g i o n s an o n p r o g r e s s i v et r i a n g l em e s hc o m p r e s s i o ns c h e m eb a s e do nw a v e l e t t r a n s f o r mh a sb e e np r o p o s e d i tu s e sr e m e s h i n gt or e m o v et h er e d u n d a n c yo f t h eo r i g i n a lm e s h ，a n dt h e nu t i l i z e st h es t r o n gd e c o r r e l a t i o np o w e ro f i l l 北京工业大学工学博士学位论文 w a v e l e tt r a n s f o r mt h ea c h i e v e dc o m p r e s s i o nr a t i o ni sa b o u t2 0 0 ：l ，w h i c hi s m o r et h a n2ti m e so ft h a t o fe d g e b r e a k e r 4 t w on o v e ls i n g l e r a t em e s hc o m p r e s s i o nm e t h o d sh a v eb e e np r o p o s e d ：b l o c kd c t m e t h o da n da d j a c e n c yp r e d i c t i o nm e t h o dt r a d i t i o n a ls i n g l e r a t ec o m p r e s s i o n s c h e m e so n l yd e c o r r e l a t et h ev e r t i c e sn e i g h b o r i n ga l o n gt r a v e r s a lp a t h t h e b l o c kd c tm e t h o dp a r t i t i o n sam e s hi n t om a n yb l o c k s ，t h e nu s e sd c tt r a n s f o r m t od e c o r r e l a t ee a c hb l o c k t h ea d j a c e n c yp r e d i c t i o nm e t h o du s e sa l lv e r t i c e s i nav e r t e x en e i g h b o r h o o d ，n o to n l yt h ev e r t i c e sn e i g h b o r i n ga l o n g t r a v e r s a lp a t h t op r e d i c ti t sg e o m e t r yp o s i t i o n a tl a s t s o m ef u t u r er e s e a r c hd i r e c t i o n so f3 dm e s hc o d i n ga r ep r o p o s e d k e y w o r d s ：m e s h g e o m e t r yc o m p r e s s i o n ，p r o g r e s s i v ec o m p r e s s i o n ，w a v e l e tt r a n s f o r m ， s c a l a b i l i t y i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名 日期：之! 么2 至z 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：垡吐丝日期：坦型) 2 2 第1 章绪论 1 1 课题背景与意义 迄今为止，多媒体技术的发展已经历了声音( 1 d ) 、图像( 2 d ) 、视频( 2 d + t ) 等三种数据类型。随着计算机图形学中三维建模和三维扫摧技术的进步，数字 化的三维图形数据开始大量涌现，成为继声音、图像、视频之后的第四种媒体。 正如声音、图像、视频等媒体给社会带来了深刻的影响一样，三维图形正在而 且必将给人类带来巨大的价值，在商业、制造业、建筑业、教育、医学、娱乐、 艺术、军事等领域产生广泛的应用。 与图像、视频等媒体相比，三维图形有着较强的逼真性和交互性，能给用 户带来图像、视频等媒体所不具有的视觉感受。人们是生活在三维世界中的， 逼真的三维图形场景可使用户感觉就象是处于真实的世界中，并可以以多种方 式与场景进行交互，从而给用户带来沉浸式的体验。三维图形所表示的场景可 以是计算机合成出来的虚拟场景，从而极大地节约实物的使用。除了能产生与 图像、视频等媒体不同的视觉和交互体验外，三维图形数据通常还携带了图像 和视频所不具有的几何信息，而这些几何信息对于c a d 等应用是非常重要的。 随着i n t e m e t 的发展与普及，以及三维图形数据的大量涌现和图形加速卡 的绘制能力的不断增强，人们通过i n t e r n e t 来共享三维图形数据的需求越来越 强。然而，尽管目前人们已经可以在网上较方便地获取文本、声音、图像、视 频等媒体数据，网上的三维图形数据却还比较少。主要原因就是三维图形数据 的数据量般都比较大，在现有的网络带宽条件下需要较长的传输时间。因此， 要想使三维图形数据在i n t e m e t 上普及，除了要解决三维图形数据的获取、编 辑、处理、管理与检索、绘制以及交互等图形技术和所需的网络、分布式技术 之外，三维图形数据的压缩和在i n t e r n e t 上的传输将是需要解决的关键技术。 三维图形数据的压缩可以有效地减少存储空问需求和节约网络带宽。三维 图形数据压缩和传输技术的发展将把三维图形世界引入到i n t e r n e t 中，使未来 i n t e m e t 上的三维图形数据象文本、声音、图像、视频一样普遍，使结合三维 图形的真实性、自然性、交互性和i n t e r n e t 的广域性、普及性的分布式图形系 统成为可能，从而较大地改变入们的生活方式、交流方式、生产方式以及工作 方式，产生较大的社会、经济价值。一些具体的应用实例有：分布式虚拟现实、 北京t 业大学t 学博l 学位论文 数字博物馆、网上虚拟商城、网络视频游戏、虚拟空涮会议、自然人机接口、 分布式协同设计、地理信息系统、科学计算可视化等。 三维图形数据压缩和传输的研究是涉及计算机图形学、数据压缩技术等学 科的交叉性课题。相对于文本、声音、图像、视频等数据压缩和传输的大量研 究工作而言，三维图形数据压缩和传输的研究还是一个较新的课题。三维图形 数据与其它媒体数据有很大不同。比如与图像相比，三维网格一般存在几何和 拓扑性质，网格顶点是空间不规则采样的，顶点间还存在着一般并不规则的连 接关系。三维网格的这些特点，使得信号和图像的压缩方法不能简单移植到网 格上，从而给三维网格压缩和传输的研究带来了新的问题和挑战。自从1 9 9 5 年s u n 公司的d e e r i n g 发表第一篇几何压缩的论文以来，三维图形数据压缩 和传输的研究虽然取得了一定的进展，但其理论基础还不完善，离完全实用还 有一定的差距，还有许多的问题需要进步解决。 目前已经有两个国际标准涉及三维图形数据压缩，即v r m l ( 虚拟现实建 模语言，现已改为w e b 3 d ) e l 和m p e g 4s n h c ( 合成数据自然数据混合编码) 中的几何编码部分，但这两个标准所采用的压缩方法都是前几年的研究成果 ( t o p o l o g i c a ls u r g e r y ) 。与此同时，一些研究成果也纷纷进入各大公司的相 关产品中，如m i c r o s o f t 的d i r e c t 3 d 、s u n 的j a v a 3 d 、m m 的h o t m e d i a 、以 色列v i r t u e 公司的v i r t u e 3 d ，以及i n t e l 、i - i p 的一些产品等1 5 】。 目前三维图形数据压缩和传输的研究正方兴未艾，成为计算机图形学的一 个热点研究领域。研究成果比较显著的国外研究机构主要有：美国的加州理工 学院、佐治亚理工学院、南加州大学、微软研究院、i b m 研究中心、s u n 公司， 以及以色列的以色列理工学院等。据作者的了解，国内目前只有浙江大学 c a d & c g 国家重点实验室，以及北京大学视觉与听觉信息处理国家重点实验 室等少数单位从事相关的研究工作。 1 2 三维图形数据的表示 三维图形数据的表示与采用的绘制方法有关。根据建模与绘制方法的不 同，三维图形数据主要包括多边形网格、纹理映射时所用的纹理图像、基于图 像绘制( i m a g e b a s e dr e n d e r i n g ，i b r ) 数据等类型。 目前采用的多边形网格主要是三角形网格和四边形网格。其中三角形网格 是目前最常用的三维图形模型表示方式，得到了很多图形库( 如o p e n g l 郇， d i r e c t 3 d 7 1 ) 的支持，大量的图形处理芯片也是针对三角形网格设计的。由于 可以将每一个四边形或多边形剖分成几个三角形，从而将四边形网格或者其它 多边形网格转化为三角形网格，因此本文将主要集中于研究三角形网格的压缩 编码。图1 一l 显示了一个三角形网格。 图1 1 三角形网格 f i g 1 1 a t r i a n g l em e s h 一个三角形网格由许多三角形拼接而成，可以由一个顶点数组和一个三角 形数组来描述，如下所示： v ：( f l o a tx ，y ，z ) m 】 t ：( i n tv 0 ，v l ，v 2 ) 【n 其中，每个顶点有x ，y ，z 三个坐标分量，每个三角形由它的三个顶点确定， v o ，v l ，v 2 为这三个顶点在顶点数组v 中的索引。m ，n 分别为顶点数与三角形 数。 每个顶点除了坐标以外，还可以包含其它各种用于绘制的属性信息，如每 个顶点的法向、颜色、纹理坐标等。上述描述方法广泛应用于各种网格文件格 式中，如常用的p l y ，o b j ，w r l ，3 d s ，x ，o f f 等格式。 网格所包含的信息可分为连接信息和属性信息。连接信息描述顶点间的连 接关系，而属性信息描述顶点的各种属性，主要包括描述顶点坐标的几何信息， 以及法向、颜色、纹理坐标等其它属性信息等。法向、纹理坐标等属性可以用 与顶点坐标类似的方式进行压缩。本文后面将主要研究三角形网格的连接信息 和几何信息的压缩。 三维网格主要是通过三维建模软件进行创作或者通过三维扫描仪来获取 北京t 业大学1 ：学博l 学位论叟 的。如果用三维建模软件来制作复杂的网格模型则需要较熟练的技能以及细 致耐心的操作。随着三维扫描仪的出现与发展，复杂三维几何数据的获取已变 得较为容易。由于三维物体的自遮挡，在每一视点只能获取部分物体表面的深 度与纹理数据，所以三维扫描仪要在多个角度对物体进行获取，并要求相邻视 点获取的数据要有部分重叠，然后对这些数据进行对准c 8 。9 】，将这些在不同视点 下获取的数据变换到同一坐标系下，最后将重叠部分的冗余数据去除，进行集 成与网格化。目前市场上最流行的三维扫描仪是美国c y b e r w a r e 公司的产品【l 。 作者所在的实验室也在距离图像的对准及集成方面做过多年的工作田nj ，所研 制的三维扫描仪在精度上达到了l m m ，为三维物体的数字化提供了一种手段。 圈l 一2 显示了我们自己研制的三维扫描仪。 幽1 - 2 我们研制的三维扫描仪 f i g 1 2 3 ds c a n n e rd e s i g n e db yo u rl a b 用三维扫描仪获取的网格的分辨率一般比较高，数据量很大，给存储、传 输和绘制都带来了较大的困难。图l ，3 显示了学术界常用的几个用三维扫描仪 获取的网格数据，同时标出了它们的三角形数目与数据量大小，其中的数据量 是指a s c i i 格式的网格文件的大小。对于v e l l u s 网格，在5 6 k 的拨号连接上， 需要2 3 分钟才能下载完。因此，网格数据的压缩是一个十分必要和迫切的问 题。 目前，网格的绘制流水线主要有固定功能和可编程的两种。在通常的固定 功能的绘制流水线中，采用了p h o n g 局部光照模型，g o u r a u d 明暗处理以及 4 第1 章绪论 z - b u f f e r 消隐算法，通常的计算机图形学教科书中都有它们的详细描述1 2 - 1 s l 。 b u n n y 7 万 2 3 2 m r a b b i t 1 3 万 45 l m l a o r s e 97 万 3 2 3 m 1 1 万 3 7 9 m v e n u s 2 7 万 9 2 9 m 图1 - 3 常川的网格及它们的数据量 f i gl 一3 s o m em e s h e so b t a i n e db y3 d8 c a n r l e ra n dt h e i rs i z e 固定功能绘制流水线的缺点是缺乏灵活性，很多高真实感的绘制算法难以在执 行固定功能流水线的图形库或图形硬件上实现。与执行固定绘制流水线的图形 硬件不同，9 0 年代后期出现了具有可编程能力的图形处理器( g r a p h i c s d r o c e s s i n gu n i t ，g p u ) ” ，在绘制流水线的几何阶段和光栅阶段引入了可编 程住。 纹理映射是最常用的添加物体表面细节的方法。通常，纹理图案出一幅图 像来表示。因此，纹理图像的压缩可以采用通常的图像压缩方法，如j p e g ”， 或基于小波的图像压缩方法如s p i h t 1 、j p e g 2 0 0 0 t 2 0 a 等。 多边形网格的绘制以及纹理映射都是基于几何的绘制方法。而基于图像的 北京t 业大学丁学博l j 学位论史 绘制( i b r ) 技术【2 1 1 则是在环境中以若干视点和视角离散地采样一些图像，然 后通过处理与组织这些图像，绘制出在新的视点与视角下所看到的图像，从而 构造出一个支持用户自由漫游的虚拟现实系统。目前主要的i b r 技术有基于全 景图的q u i c k t i m ev r 2 ，l i g h tf i e l d 2 3 1 与l u m i g r a p h1 2 4 1 方法，以及同心圆拼图 方法( c o n c e n t r i cm o s a i c ) 1 等。i b r 技术获取了大量的图像，且这些图像之 间存在一定的相关性，因此需要研究这些图像的有效压缩。i b r 数据压缩的主 要工作有 2 6 2 8 。 其它的主要图形数据类型还有体数据( v o l u m ed a t a ) 等，它们的压缩也已 经有一些成果3 0 。 除多边形网格之外，本文后面不再对其它类型图形数据的压缩进行讨论。 1 3 本文的组织 本文主要研究三角形网格的压缩。除了要取得高的压缩效率之外，我们将 重点研究如何使压缩数据适合于在i n t e m e t 环境下进行传输、绘制和交互，比 如如何使压缩网格具有可扩展性( s c a l a b i l i t y ，或称可伸缩性) ，以及如何使网 格压缩能够支持交互浏览的随机访问特性等。最后，作者讨论了网格压缩的一 些进一步研究方向。 本文的组织如下： 第1 章绪论。主要介绍了三维图形数据压缩的意义，以及三维图形数据 的表示。 第2 章网格压缩综述。对当前三维网格单一位率压缩和渐进压缩的主要 成果进行了综述。阐述了网格压缩应该满足的一些要求。简要介绍了本文中用 到的网格压缩的一些基础技术，如算术编码和网格的小波变换。 第3 章三角形网格的可扩展编码。提出了一种基于小波变换的压缩方法， 用来生成具有可扩展住的位流，以便适应i n t e r n e t 带宽的异构、时变以及网 络终端图形处理能力的异构。该方法在实现可扩展性的同时，还取得了很高的 压缩效率。 第4 章支持随机访问的三角形网格压缩。本章在网格压缩方法中考虑了 支持随机访问的要求，使得只需要传输在当前视点下可见部分所对应的压缩数 第1 市绪论 据驯口j 。 第5 章基于小波变换的非渐进网格压缩。前面两章是基于小波变换来实 现可扩展编码和随机访问，本章则是采用小波变换的强去相关能力来实现非渐 进压缩。 第6 章三角形网格的分块d c t 压缩。借鉴j p e g 图像压缩中的分块d c t 思想，本章提出了三角形网格的分块d c t 压缩方法。 第7 章基于邻域预测的三角形网格几何信息压缩。通常顶点坐标是沿遍 历路径进行预测来压缩的，从而只利用了遍历路径上相邻顶点间的相关性。进 行邻域预测将可以利用邻域内顶点间的相关性，使几何信息的压缩摆脱遍历路 径的制约。 第8 章进一步研究方向。介绍了下一步将要从事的一些工作，包括连接 关系自动重构的网格压缩、网格的r o i 编码、网格的鲁棒性编码与可靠传输、 网格与纹理的同步压缩、利用g p u 实现网格的高效解码、以及数字几何处理 等。 结论部分对本文的主要工作和创新进行了总结a ! ! ! 一 ， j ：j ：! 兰：兰! 耋坚! 兰竖生兰 第2 章网格压缩综述 根据压缩目的的不同，当前网格压缩的研究3 1 弛1 可分为单一位率压缩 ( s i n g l e r a t ec o m p r e s s i o n ) 年 1 渐进压缩( p r o g r e s s i v ec o m p r e s s i o n ) 两大类。单一位率 压缩是指要等到接收了所有的压缩数据后，爿4 能进行解码的压缩方法。其目的 是要获得高的压缩比，减少存储空间需求和节约网络带宽。而渐进压缩是要将 一个三角形网格模型压缩成适于渐进传输的形式，即先传输并显示一个粗糙的 基网格( 与原模型形状相近，但缺乏细节，且数据量很少) ，然后再不断地传 输细节信息。渐进传输的主要目的是为了减少交互时用户的初始等待时间，在 基网格传输完毕并显示后，用户就可以开始与之交互。随着时间的增加，物体 上的细节越来越丰富，越来越趋近于完整的几何模型。系统可以根据各种条件， 如当前的可用带宽等，在压缩位流的任点停止传输，并能从已接收的位流中 重构出某一细节层次( 1 e v e lo fd e t a i l ) 的几何模型。这个几何模型的质量由位 流的率失真特性决定。这就是渐进压缩所得到的位流的嵌入式特性。 无论是单一位率压缩还是渐进压缩，都要研究如何压缩网格的连接信息和 几何信息。对单一位率压缩而言，其连接信息是指顶点间的连接关系，而几何 信息则是指顶点的坐标。对渐进压缩而言，其基网格是用单一位率压缩方法压 缩的；而细化操作中的连接信息用来指定在已重建的网格中哪个位置进行细化 操作( 比如新顶点的插入位置) ，细化操作中的几何信息用来指定细化操作的 具体值( 比如新插入顶点的坐标预测误差) 。 2 。l 单一位率压缩方法综述 单一位率压缩也称为非渐进压缩( n o n p r o g r e s s i v ec o m p r e s s i o n ) 。由于重构 网格的分辨率与原始网格是一样的，所以也称为单一分辨率压缩( s i n g l e r e s o l u t i o nc o m p r e s s i o n ) 。单一位率压缩的研究已经有很多工作。 2 1 1连接信息压缩 d e e r i n g 的工作开创了几何压缩的研究领域。他基于广义三角形条带 第2 葶网格压缩综述 ( g e n e r a l i z e dt r i a n g l es t r i p ) 来进行三角形网格压缩，主要采用硬件实现，以缓 解c p u 和图形卡之间的总线带宽瓶颈。在广义三角形条带中，新加入顶点可 以与某两个最近访问过的顶点组成新三角形，因此d e e r i n g 引入了一个顶点高 速缓存，用来保存最近用过的顶点，对这些顶点，只需用顶点高速缓存的索引 号来引用它们。所有的顶点按三角形条带的顺序组成一个顶点流，输入到图形 卡中，然后解码单元对顶点流和索引流进行解析( p a r s i n g ) ，组成一个个三角 形输入到后续的绘制流水线中，并把最近用到的顶点保存在顶点高速缓存中， 阻便进行重用。在顶点流中，每个顶点的坐标、颜色用前一个顶点的坐标、颜 色进行预测，并对预测误差进行h u f f m a n 编码。各个顶点的法向则被量化到事 先规定的一些空间方向上，并采用查找表的方法进行顶点法向的解码。d e e f i n g 方法的压缩比约为6 1 0 倍。d e e r i n g 在该文中提出的建立顶点高速缓存的思想 也在当代的g p u 设计中得到了广泛应用。 基于d e e f i n g 方法，c h o w 设计了一个有效的将三角形网格转化为三角形条 带的方法t 3 3 1 ，以便在形成新三角形时，大多数顶点能得到重用。此外，他还设 计了一种方法，对具有不同细节丰富程度的区域进行不同精度的量化。该方法 取得了3 0 一3 7 倍的压缩比。b a r - y e h u d a 和g o t s m a n 3 4 1 则从理论上证明了，对于 一个具有n 个顶点的网格，大小为1 2 7 2 n 的顶点栈就足以使高速缓存的访问 缺失率( c a c h em i s sr a f t o ) 最小，或者说顶点栈中的顶点得到了最大程度的重 用。 在以上几何压缩的早期工作中，顶点坐标采用了预测编码，但每个三角形 的三个顶点还是用索引来表示的。因为索引号很难压缩，从而使得压缩比不高。 事实上，一般应用并不需要在解码后严格地恢复出编码端顶点和三角形的原始 顺序，因此是可以不借助于索引号柬编码网格的。基于这个认识，许多基于遍 历的连接信息编码方法发展起来。这些方法的主要思想是先采用某种遍历方法 对网格进行遍历，以压缩连接信息，并沿遍历所得的顶点序列对顶点坐标进行 预测，然后再对预测误差进行熵编码。遍历时，一次征j 报( c o n q u e r i n g ) 个元素， 按照被征服的元素的不同，这些方法分为基于面、基于边和基于顶点的方法等 三类。基于面的方法主要有拓扑手术( t o p o l o g i c a ls u r g e r y ，t s ) 4 1 、 e d g e b i t e a k e l 一【3 5 蚓、c u t b o r d e r 3 7 1 等。基于边的方法主要有t r i a n g l ef i x e l 吲和f a c e 北京1 业大学丁学蹲i 学幢论丘 f i x e r l 1 。基于顶点的方法主要有t g1 4 0 、a l l i e z 和d e s b r u n 4 1 1 、网格坍缩压缩 ( m e s hc o l l a p s ec o m p r e s s i o n ) 【4 2 】、a n g l e a n a l y z i e r1 4 3 1 等。 t a u b i n 和r o s s i g n a c 的t s 方法是m p e g 4s n h c 中的几何编码标准以及 v r m l 数据压缩标准的基础，它沿顶点生成树将网格剖开，得到一个不包含内 部顶点的简单网格，即可以用三角形生成树来表示的三角形条带，然后用( 行 程，行进位( b r a n c h i n gb i t ) ，叶节点位( 1 e a f b i t ) ) 三元组来编码顶点生成树， 用( 行程，叶节点位) 二元组以及行进模式来编码三角形生成树，从而压缩了 原网格的连接信息；对每个顶点的坐标值，用顶点生成树上前几个顶点坐标值 的线性组合来进行预测，再对预测误差进行h u f f m a n 编码，从而压缩了网格的 几何信息。t s 方法的连接信息压缩位率平均小于4b v 。 r o s s i g n a c 的e d g e b r e a k e r 方法采用了三角形的宽度优先遍历，一次访问一 个三角形。每当从某条边进入到个未被访问过的三角形时，如果相对的那个 顶点没有被访问过，则输出符号c ( c e n t e r ) ，标记该顶点与三角形为已访问，并 且下一个操作为访问右边的相邻三角形：否则根据左、右两个相邻三角形被访 问情况的四种可能组合，分别输出l ( 1 e f t ) ，r ( r i g h t ) ，s ( s p l i t ) ，e ( e n d ) 等四个 符号中的某一个，标记该三角形为已访问，并采取相应的下一个操作：访问右 边的相邻三角形，访问左边的相邻三角形，分又或结束。这个过程不断进行， 直到所有的三角形都被访问过为止，最后再对所得的符号序列进行熵编码。图 2 一l 显示了基于面的连接关系编码的过程。 由于这五种符号概率分布很不均匀，其中c 的概率约为0 5 ，所以 e d g e b r e a k e r 方法可获得很高的连接信息压缩比，其压缩位率的上限为4b v ， 是第一个在理论上给出了压缩上限的方法。k i n g 和r o s s i g n a c 提出了一种新的 c l e r s 串的编码方法删，其压缩位率的上限为3 6 7b v 。原始的e d g e b r e a k e r 方法在解码时，按照编码端的遍历次序，不断地重构出三角形，解码复杂度最 差为0 ( n 2 ) 。r o s s i g n a c 和s z y m c z a k 提出了e d g e b r e a k e r 压缩方法的w r a p & z i p 解码方法45 1 ，采用与原始解码方法一样的顺序，解码复杂度改进到最差为 o ( n ) ，但对于有柄( h a n d l e ) 的网格，编、解码时仍需多次遍历。i s e n b u r g 和 s n o e y i n k 提出了e d g e b r e a k e r 压缩方法的s p i r a l er e v e r s i 解码方法h ，它按照与 编码端遍历相反的次序进行网格重构，解码复杂度为o ( 7 7 ) 。g o t s m a n 和 o 第2 辛网格压缩练述 k r o n r o d 将e d g e b r e a k e r 方法推广到任意的多边形网格，对四边形网格取得了 3 5b f v 的结果。k i n g 则将e d g e b r e a k e r 方法推广到四边形网格，证明了最差 可以取得2 7 5b v 的结果。s z y m c z a k 和k i n g 还将e d g e b r e a k e r 方法应用到较 规则网格上，取得了很高的压缩比，对于价为6 的顶点超过8 5 的三角形网格， 压缩比可达1 8 5b v 。 图2 1 基于面的连接关系编码示例 f i g 2 一le x a m p l eo ff a c e - b a s e dc o n n e c t i v i t yc o d i n g c u t b o r d e r 方法是由g u m h o l d 和s t r a s s e r 提出的，其思想与e d g e b r e a k e r 方 法非常类似。 i s e n b u r g 和s n o e y i n k 提出了基于边进行遍历的t r i a n g l ef i x e r 和f a c ef i x e r 方 法，后者可用于多边形网格，包括三角形与多边形混合的网格。其中最主要的 两种操作为：只将一个具有f 条边的多边形附加到当前边界上，而操作l 则将 当前活动边在边界上的前一条边作为活动边，随后的多边形则附加在这个新的 活动边上。解码是逆序进行的。t r i a n g l ef i x e r 的连接信息位率在l 一4b v 左右。 图2 2 显示了基于边的连接关系编码的过程。 t o u m a 和g o t s m a n 的t g 方法是目前连接信息压缩比最高的方法之一。它 从一个初始三角形的三个顶点出发，对与每个顶点相连的边和顶点进行遍历， 北京t 业大学1 学博l 。学位论文 然后又对与这些新的顶点相连的边和顶点进行遍历，这样不断地进行下去，并 按遍历顺序输出每个顶点的价( v a l e n c e ，相连的边数) ，最后对所得的顶点价 的序列进行熵编码；由于网格中每个顶点的价基本上都在6 左右分布，概率分 布很不均匀，所以t g 方法可以获得很高的连接信息压缩比。图2 ，3 显示了基 于顶点的连接关系编码的过程。当前已遍历区域的边界构成一活动列表( a c t i v e l i s t ) 。主要的操作为加入操作a ，它引八个价为j 的顶点。沿逆时针方向用a 操作依次输出当前枢轴( p i v o t ) 顶点的各个相连顶点的价，直到与当前枢轴顶 点相连的顶点都被访问过为止，然后选取在活动列表上的下一个顶点作为枢轴 顶点，继续进行遍历。当活动列表不断扩展到与自身相交时，如图2 3 ( i ) ，就 将活动列表分裂成两个( j ns p l i t 操作) ，然后依次分别进行遍历。对非常规则 的网格，t g 方法的连接信息压缩位率可达o 2b v ，对一般网格则为2 ，3b v 左 右。 蚓2 - 2 基丁边的连接关系编码示例 f i g2 - 2e x a m p l eo fe d g e b a s e dc o n n e c t i v i t yc o d i n g a l l i e z 和d e s b r u n 对t gt y p e 0 的遍历过程作了改进，他们采用启发式的 第2 章网格压缩综述 遍历，选取活动列表上具有最小自由边数目的顶点作为下一个枢轴顶点，目的 是尽可能减少s p l i t 操作的出现次数，以提高压缩性能。这种策略可以使s p u r 操作的数目减少7 0 。7 0 。与t g 方法相比，位率减少了1 5 左右。他们同时还证 明了基于价的连接关系压缩方法具有近最优性( n e a ro p t i m a l ) 口“，即接近于 t u t t e 口 ”通过枚举而得到的连接关系压缩下限。 与t g 方法一样，i s e n b u r g 和s n o e y i n k 的网格坍缩压缩方法也基于顶点价。 该方法不断执行边收缩( e d g ec o n t r a t i o n ) 操作，直到整个网格坍缩为一个顶点。 对每个边收缩操作，输出一个顶点的价。最后对价序列进行熵编码或行程编码， 压缩结果为1 - 4b v 。 幽2 - 3 基丁顶点的连接关系编码示例 f i g 2 - 3e x a m p t eo fv e r t e x - b a s e dc o n n e e t i v i t y eo d i n g l s e n b u 唱【5 萄和k h o d a k o v s k y t s 3 等人独立地将t g 方法推广到多边形网格。他 们将连接关系编码为一个顶点的度( d e g r e e ，即价) 的序列和一个面的度的序 列，并通过预测来利用相邻顶点的度和面的度之间的相关性。压缩位率比f a c e f i x e r 方法平均要高2 6 。 m a l l o n 5 4 1 等人提出了同心条带( c o n c e n t r i cs t r i p s ) 方法，围绕一个中心顶 北京i 业大学t 学博l 。学位论义 点，他们将网格分解为一个一个的条带，每个条带由同心且相邻的两个顶点串 确定。整个网格可以表示为三个列表：顶点列表、儿子列表、兄弟列表。该方 法取得了约3 0b v 的压缩位率，且易于用硬件实现。 i s e n b u r 9 1 5 5 1 在压缩三角形网格连接关系的同时，实现了三角形条带的编码。 三角形条带是常用的提高绘制效率的方法，通过设置顶点高速缓存，对每个三 角形重用其中的两个顶点，可以减少内存与图形卡之间的顶点数据传输量以及 需要计算变换和光照的顶点数量。计算最优的三角形条带是一个n p 难的问题， 所以常采用一些启发式搜索算法。由于构造三角形条带的复杂性，最好在确定 好三角形条带后，将它编码到位流中，而不是在解码端重新进行构造。基于 t r i a n g l ef i x e r 方法，i s e n b u r g 用己确定好的三角形条带来引导遍历过程，从而同 时压缩了连接关系和三角形条带。 2 1 2几何信息压缩 目前主要的网格几何