（应用数学专业论文）三角网格压缩算法.pdf

浙江大学硕士论文 摘要 三角网格作为三维物体的一种有效表示形式，在计算机图形学领域有着广泛 的应用。三角网格的顶点序列及其连接关系构成网格曲面的几何与拓扑信息。由 于网格曲面通常数据量巨大，研究网格曲面的压缩算法对于网格存储和传输有着 重要意义。本文通过三角网格新的图表示和顶点坐标重排列技术，研究网格曲面 新的拓扑与几何压缩算法。 三角网格的拓扑连接关系可以由顶点之问的连接边确定，与网格曲面每一顶 点有一条边连接的顶点构成网格的邻域，网格顶点及其一邻域点集构成网格的邻 域图表示。依据网格顶点及其邻近点的距离构造得到网格顶点的邻域球，再根据 邻域球对网格的邻域图表示进行压缩和解压缩。由于一般三角网格顶点的邻域点 通常分布在邻域球附近，这种方法可对三角网格的拓扑信息进行有效压缩，尤其 对局部采样均匀的三角网格能达到高效的压缩效果。 在对网格顶点坐标进行压缩时，为充分利用数据的连贯性，将原顶点序列按 各坐标分量依单调性进行重排，由坐标重排后的点列连接得到单调坐标曲线。根 据坐标重排技术将原顶点坐标的三个浮点序列转化成两个重排整数列和单调坐 标曲线表示。由于单调坐标曲线通常具有很好的数据连贯性，可用简单多边形近 似表示，从而实现对原浮点数据的有效压缩表示。这种压缩算法效果良好，无需 对网格的顶点坐标列作预数量化处理，且压缩和解压算法都很快，可以很好的满 足实时性要求。 关键字：三角网格；拓扑压缩；几何压缩；邻域图表示；o b j 格式；单调 坐标曲线；近似曲线 浙江大学硕士论文 a b s t r a c t t r i a n g l em e s h e s a r cak i n do fe f f i c i e n tf o r mf o rs u r f a c er e p r e s e n t a t i o n ，t l l e yh a v eb e e nw i d e l y u s e di nc o m p u t e rg r a p h i c s at r i a n g l em e s hi sa l w a y sc o n s i s t i n go fal i s to fv e r t i c e sa n dt h e c o n n e c t i o ni n f o r m a t i o nb e t w c e r lt h e m ，w h i c ha l s oc o n s t i t u t eg e o m e t r i ca n dt o p o l o g i c a l i n f o r m a t i o no ft h es u r f a c em e s h b e c a u s et r i a n g l e sm e s h e sa l w a y sh a v el a r g ea m o u n to fv e r t i c e s a n dt r i a n g l e s d a t ac o m p r e s s i o nf o rt r i a n g l em e s h e sp l a y si m p o r t a n tr o l et ow i d ca p p l i c a t i o n ss u c h a sd a t as t o r a g ea n d o rt r a n s m i s s i o n t w oe f f i c i e n tn e wa l g o r i t h m sf o rt o p o l o g i c a la n dg e o m e t r i c c o m p r e s s i o na r ed e v e l o p e di n t h i sp a p e r , w h i c ha r eb a s e do nan e wk i n do fn e i g h b o r h o o dg r a p h r e p r e s e n t a t i o na n dc o o r d i n a t e so r d e r i n gt e c h n i q u e s a st h et o p o l o g yo fat r i a n g l em e s hi sd e t e r m i n e db yt h ec o n n e c t i n ge d g e sb e t w e e n n e i g h b o r i n gv e r t i c e s ，t h ev e r t e xl i s t 谢l l lo n ee d g el e n g t ht oa 触e dv e r t e xf o r m s1 - r i n g n e i g h b o r h o o do ft h ev e r t e x t or e p r e s e n tn e i g h b o r h o o dg r a p he f f i c i e n t l yf o rat r i a n g l em e s h ， n e i g h b o r h o o ds p h e r ei sc o m p u t e df o re v e r yv e r t e xf o rw h i c ht h ec e n t e ri st h ev e r t e xi t s e l fa n dt h e r a d i ii sc o m p u t e da st h es h o r t e s td i s t a n c eb e t w e e nt h ev e r t e xa n di t sn e i g h b o r s t h et o p o l o g i c a l d a t ac a nb ec o m p r e s s e de f f i c i e n t l yb a s e do nt h et e c h n i q u eo fn e i g h b o r h o o dg r a p ha n d n e i g h b o r h o o ds p h e r e t h i sm e t h o dw o r k sv e r yw e l lf o rm o s tt r i a n g l em e s h e s ，e s p e c i a l l yf o r m e s h e s 诵t l ll o c a lu n i f o r ms a m p l i n g t h ee f f i c i e n c yo fg e o m e t r i cc o m p r e s s i o nd e p e n d so nh o wt h ed a t ac o h e r e n c yo ft h eo r i g i n a l v e r t e xc o o r d i n a t e sh a sb e e nu t i l i z e d t oa c h i e v es u c hag o a l ，w ea r r a n g ec o o r d i n a t e sl i s t sa s m o n o t o n el i s t s t h en e wc o o r d i n a t e sl i s t sf o r mam o n o t o n ec o o r d i n a t e sc u r v ei ns p a c e ，f o rw h i c h t h ed a t ac a nb es i m p l i f i e da n dc o m p r e s s e dv e r ye f f i c i e n t l y a tl a s t ，w es h o u l do n l ys a v et w o i n t e g e rl i s t sa n das i m p l i f i e dm o n o t o n ep o l y g o n f o rm e s h e sc o m p o s e do ft e n so ft h o u s a n d so f v e r t i c e sw i t hf l o a t i n gc o o r d i n a t e s ，t h eo r i g i n a lg e o m e t r i cd a t ae a r lb er e d u c e de f f i c i e n t l yi nt h i s w a y m o r e o v e r , t h i sm e t h o da l s ob e n e f i t sf r o ms i m p l i c i t ya sw e l l a sh i 【g hs p e e df o rd a t a k e y w o r d s ：t r i a n g l em e s h ；c o n n e c t i v i t yc o d i n g ；g e o m e t r yc o d i n g ；n e i g h b o r h o o dg r a p h ；o b j f o r m a t ；m o n o t o n i cc o o r d i n a t ec u r v e ；a p p r o x i m a t eo u r v e i i 浙江大学硕士论文 1 1 研究问题 第一章绪论 图形数据在各方面得到越来越广泛的运用，包括视频游戏，机械设计，建筑 物展示，虚拟现实，电子商务，和科学可视化等领域。在各种各样的表示工具中， 三角网格是一种表示三维模型的有效方法。它用拓扑，几何和属性数据为特色来 表示三维多边形网格。拓扑数据描述顶点之间的连接关系：几何数据指定了网格 中顶点的位置；属性数据指定了法向量，材料反射率和纹理坐标等属性。由于几 何和属性数据在很多例子中是依附于顶点的，因此，几何和属性数据经常被称为 顶点信息，并且许多三维三角网格的压缩算法以相似的方法操纵几何和属性数 据。所以一般压缩算法都集中于研究拓扑和几何数据。 为了达到高度逼真效果，网格模型通常较为复杂。他们可以从很多来源得到， 如建模软件和三维扫描仪等。他们经常需要大量的存储空间和传输宽带，随着三 维网格的顶点数和复杂性的爆炸性增长，对存储空间，计算能力和网络宽带等资 源的要求越来越高。在这些资源中，网络宽带在那些需要实时交互的基于网络的 图形学应用中是最严重的瓶颈。因此，这本质上要求我们有效的压缩图形数据。 从二十世纪九十年代初期开始，这些研究领域受到很多学者的关注，并且在过去 的十多年中该方向取得了大量有意义的进展。 三维网格压缩的早期研究工作集中在单一性噪比( s i i l 酉e m t e ) 压缩技术上，来 解决c p u 和图卡之间的带宽问题。在单一性噪比压缩算法中，所有的拓扑数据 和几何数据同时被压缩和解压。计算机图卡要完整的收到所有的比特流数据后才 能描绘原始的网格。后来，随着因特网的流行，渐进式压缩和传输的研究得到了 加强。当渐进式压缩和传输时，一个三维网格可以一边由解码器从细节粗糙的等 级到精细的等级逐渐重建，一边接收比特流数据。更重要的是，当用户发现所下 载的网格不是他所想要的或者结果已经足够好，达到了他的预期目的时，他可以 浙江大学硕士论文 停止下载，所以渐进式压缩增强了交互的能力。 三维网格已经被一体化成几个国际化标准。v r m l 1 建立了一种通过互联网 传输的三维模型标准。最初，一个三维网格在v r m l 中用没有压缩的a s c i i 格 式表示，为了更有效的传输，t a u b i ne ta 1 用基于拓扑手术的算法为v r m l 发展 了压缩的二进制格式，这种算法非常容易的达到了5 0 ：l 的压缩比例，相比于 v r m l a s c i i 格式。m p e g - 4 是一种由移动图片专家组为数字电视，交互图形和 交互多媒体的应用而开发的i s o i e c 多媒体标准，它也包括三维网格的压缩算 法。这种三维网格压缩算法也是基于拓扑手术算法，其本质上是流型三角网格的 单一性噪比压缩算法。此外，m p e g - 4 三维网格压缩算法还结合了渐进式三维网 格压缩，非流型三维网格解码，误差弹性和质量可测性等可选择的模式。 1 2 拓扑表示与压缩 1 2 1 拓扑表示 拓扑数据描述顶点之间的连接关系，其表示方法有三角形表示法，边表示法 等，三角形表示法是记录三维网格曲面的所有三角形，每个三角形的顶点之间的 连接关系用顶点数列的三个下标表示。而边表示法是记录三维网格的所有边，每 条边的顶点之间的连接关系用顶点数列的两个下标表示。 1 2 2 拓扑压缩 一个典型的网格压缩算法对拓扑数据和几何数据的解压过程是相互独立的。 许多早期的工作集中在拓扑压缩上，然后几何数据的压缩顺序由拓扑压缩来决 ，j 叶 疋。 现在的拓扑压缩算法一般可分为六类：第一类为v r m l a s c i i 格式【1 】，对一 2 浙江大学硕士论文 个有1 ，个顶点的网格而言，每个顶点的下标用l 0 9 2 ，个比特表示，于是一个三角 形用3l 0 9 21 ，个l - t ；特，所以这种方法的拓扑数据压缩率为6 l 0 9 21 ，助1 ，( b i t sp e r v e r t e x ) 。第二类方法为三角形带法，其主要思想是把三维网格划分成长长的三角 形带，然后对这些三角形带进行编码。d e e r i n g 1 3 ，c h o w 1 4 都是这方面的工作。 第三类方法为生成树法，由于平面图的拓扑信息在用顶点生成树和三角形生成树 进行编码时，其结果为常数个助1 ，。t a u b i na n dr o s s i g n a c 3 采用拓扑手术的方 法对网格的拓扑信息进行编码，主要思想为将给定的网格沿着选定的边切割成平 面多边形，然后对切割边和多边形进行编码。第四类方法为多层分解法，b a j a je t a l 2 1 提出了一种利用顶点的多层结构对网格的拓扑信息进行编码的方法，他将 三角网格的顶点分解成同轴的数层，然后在相邻的顶点层之间构造三角形层，于 是网格的拓扑信息可以用顶点层的总数，每个顶点层的位置和每个三角形层中的 三角形位置来表示，网格的拓扑压缩转化为对这些信息进行编码。第五类方法为 以顶点的度为主导的方法，它选定一个种子三角形，将其三边构成一条初始边界 线，这条边界把整个网格分为两部分，内部为已经处理过的部分，外部为即将要 处理的部分，边界线逐渐向外延展，直到整个网格被处理过。于是可以得到顶点 度的输出流，而初始网格的拓扑信息可以由顶点度的输出流重构出来。t o u m aa n d g o t s m a n 2 3 ，a l l i e za n dd e s b r u n 2 4 都是这方面的工作。第六类方法为占领三角 形法，和第五类方法类似，占领三角形法也是从一个初始边界边开始，初始边界 边把网格的三角形分为占领的部分和未被占领的部分，然后向占领三角形的部分 一个一个的插入三角形。和第五类方法不同的是，该方法输出的是新三角形的构 建算子，而第五类方法的输出为新顶点的度。g m n h o l da n ds t r a b e r 2 7 】， r o s s i g n a c 5 ，k i n ga n dr o s s i g n a c 2 9 都是这方面的工作。 1 3 几何数据压缩 由于几何数据比拓扑数据占更多的存储空间，因此，现在的一些算法主要考 虑如何有效的压缩几何数据，而不关心拓扑数据。 3 浙江大学硕士论文 所有的单一性噪l 匕( s i n g l e r a t e ) 的拓扑压缩算法都是无损的，但是，几何数据 的编码一般都是有损的，许多单一性噪比的几何压缩算法都分为三个过程：顶点 位置的预数量化，预数量化后位置的预测和预测误差的熵编码。未被压缩的几何 数据的顶点坐标是3 2 比特的浮点型数据，其精度远远超出人眼的分辨率，在许 多应用中也不需要这样高的精度，因此，预数量化过程是将顶点坐标的精度降低， 在不影响视觉质量的前提下，用较少的比特表示顶点坐标，经典的几何压缩算法 都是将顶点坐标数量化为8 1 6 比特。在顶点坐标的预数量化后，对顶点的位置 进行预测性的编码，利用相邻顶点之间的相关性，可以大大的减少几何数据量。 一个好的预测方法产生的预测误差会更高，然后进行熵编码，如哈夫曼编码或算 术编码。因此几何压缩的关键是寻找一个好的预测方法，现在的几何数据预测方 法主要有四种，d e l t a 预测法，线性预测法，平行四边形预测法和二阶预测法， 所有的这些预测方法在选定特定的参数的情况下都可以看作是线性预测法的特 例。 d e l t a 预测法利用了相邻顶点之间的坐标相差很小，坐标之i 司的差距( d e l t a s ) 通常很小，然后我们对坐标之间的差距进行编码，d e e r i n g 1 3 和c h o w 1 4 是这 方面的工作。而t a u b i na n dr o s s i g n a c 3 矛j j 用了线性预测法，顶点的位置是由顶 点生成树的k 个顶点的线性组合来预测的，这k 个顶点是顶点生成树从根顶点 到当前顶点唯一选定的，第n 个顶点用公式表示为：= 乃只一；+ s ( ) ， 这里 ，五，以的取值为使误差的平方的期望最小 e 肚( ) 1 1 2 = e 1 1 只一善k 丑吃吓 。n 啪a a n ag 。t 锄觚幽，使用了平行四 边形预测法，这种方法基于三角形占领法，对占领区域内有活动边的三角形，以 活动边为对角线作一个平行四边形，然后用平行四边形生成的顶点作为预测点， 这样如果四个项点在一个近似平面上时，该方法可以达到很好的效果，如果没有， 就用邻近的折角作一个空间四边形，也能得到很好的效果。b a j a j 2 1 使用t - 阶 预测法，二阶预测法分为两个步骤，步骤一：计算相邻顶点之间的差距矢量，然 4 浙江大学硕士论文 后数量化之；步骤二：求出经数量化后的步骤一的差距矢量的差距矢量，然后编 码。在预数量化的结果为8 比特的前提下，现在最好的单一性噪比几何压缩算法 的比特率可达6 1 0 助1 ，。 1 4 本文工作 本文第二章简单介绍了o b j 格式，并提出了网格的一邻域图表示法。接着做 了一邻域图表示法向o b j 格式的转化，然后对一邻域表示法做拓扑压缩。和o b j 格式记录所有三角形三顶点的连接关系不同，所有顶点的一邻域点被记录下来， 并作为拓扑数据。而o b j 格式在记录网格的拓扑数据时，即三角形连接关系时， 顶点下标平均重复记录了6 次，这是由于网格的顶点的度的平均值为6 ，用一邻 域图表示网格时，拓扑数据同样是顶点数的6 倍。但许多网格的顶点分布是相对 均匀的，每个网格顶点的一邻域点通常分布在以当前顶点为球心的球面附近，球 的半径由到最近点距离乘以一常数得到。下一步找出球外的一邻域点和球内的非 一邻域点，将其定义为顶点的第一类奇异点和第二类奇异点。在记录网格的拓扑 数据时，和o b j 格式不同，本文记录顶点的第一类奇异点和第二类奇异点，若网 格顶点分布比较均匀，所需要记录的拓扑数据量将很小，这样便得到了网格的压 缩格式。接下来做了压缩格式的解压过程，根据顶点坐标和记录的两类拓扑信息， 便可恢复出原网格完整的拓扑信息。为进一步提高压缩效率，可对原网格先作优 化处理。本章对大量的网格例子作试验，对均匀网格的例子得到了很好的压缩结 果。 第三章为三角网格的几何压缩算法，和传统的基于预测的几何压缩方法不 同，我们对每个网格，先构造一条单调坐标曲线，单调坐标曲线上的所有点的x ， y ，z 坐标列为网格顶点的x ，y ，z 坐标列按从d , n 大的顺序重排列后得到的。 然后我们用一条顶点数少的多的近似曲线来近似初始单调坐标曲线，并记录近似 曲线上的顶点坐标，近似曲线上每段的单调坐标曲线的顶点数，和y ，z 坐标的 变换数列作为我们的压缩结果。在解压时，我们对近似曲线作均匀插点，并恢复 5 浙江大学硕士论文 出原网格，我们的压缩和解压算法都很快，复杂度为d ( ，z l 0 9 2 刀) ，当网格的顶 点数n 比较大时，压缩结果为2 l 0 9 2 刀b p l ，如当网格顶点数为6 2 3 5 3 ( 2 1 6 - 1 ) 时，压缩结果为3 2b p v 。 第四章对本文所做的研究工作进行了一下总结，然后展望一下在接下来的研 究工作中还要继续做的问题。 浙江大学硕士论文 第二章网格的邻域图表示法及其拓扑压缩 三角网格的数据可分为几何数据，拓扑数据和由法向量、材料反射率以及纹 理坐标构成的属性数据，其中拓扑数据描述了顶点之问的连接关系。许多早期的 工作都集中在拓扑压缩上。本章首先提出网格的一邻域图表示法，接着做了一邻 域图表示法向o b j 格式的转化，然后对一邻域表示法做拓扑压缩算法和解压算 法，最后为了进一步提高压缩效率，在对原网格优化后，做了大量的拓扑压缩实 验，并得到了很好的压缩效果。 2 1 网格的邻域图表示法 当用o b j 格式表示三角网格时，几何数据为网格的顶点坐标数列，拓扑数据 为网格曲面的所有三角形的连接关系。以平面网格为例，如图1 ，该网格的几何 数据为各顶点坐标数列 弓，昱，只，忍，只，另，忍) 拓扑数据为网格曲面的所有三角形的连接关系 三角形l ： 三角形2 ： 三角形3 ： 三角形4 ： 三角形5 ： 三角形6 ： 三角形7 ： 三角形8 ： 1 ，2 ，7 2 ，3 ，7 3 ，8 ， 7 3 ，4 ，8 4 ，5 ，8 5 ，6 ， 8 6 ，7 ， 8 6 ，1 ，7 7 浙江大学硕士论文 p 1 p 2 图1 在这里，我们也可以用一邻域图表示三角网格，其几何数据与o b j 格式表示 三角网格的几何数据一样，为所有网格顶点的坐标数列，拓扑数据和o b j 格式不 同，我们记录每个顶点的所有一邻域点，以图1 所示网格为例，该网格的几何数 据为 只，昱，b ，只，乞，b ，只 拓扑数据为 顶点1 的一邻域点：2 ，6 ，7 顶点2 的一邻域点：1 ，3 ，7 顶点3 的一邻域点：2 ，4 ，7 ，8 顶点4 的一邻域点：3 ，5 顶点5 的一邻域点：4 ，6 ，8 顶点6 的一邻域点： 1 ，5 ，7 ，8 顶点7 的一邻域点： 1 ，2 ，3 ，6 ，8 顶点8 的一邻域点：3 ，4 ，5 ，6 ，7 浙江大学硕士论文 2 2 邻域图表示法向o b j 格式的转化 为了使网格的邻域图表示格式有着广泛的应用，本节首先解决邻域图表示法 向o b j 格式的转化问题，由于邻域图表示法和o b j 格式的几何数据相同，因此， 转化问题的关键是已知所有顶点的一邻域点的情况下，如何恢复o b j 格式的拓扑 数据，也即网格曲面的所有三角形的连接关系。在这里我们首先假设网格中所有 边的两端点的公共邻域点的数目不大于2 ，通过对绝大多数网格例子试验发现， 当网格中的边为边界边时，其两端点的公共邻域点数为l ，当网格中的边为非边 界边时，其两端点的公共邻域点数为2 。有了以上的假设，转化算法如下： 算法输入：网格顶点序列及每个顶点的一邻域点 ( 1 ) 选取一点及其邻域点，求出这两点的公共邻域点，以这三点构造初始三角 形，将三边压入堆栈中。 ( 2 ) 判断堆栈是否为空，若空则停止算法，否则让最顶上的边出栈。 ( 3 ) 求出栈边的剩余公共邻域点，若没有公共邻域点，重复以上步骤，否则， 以该边两端点和求出的邻域点构成新的三角形，记录新三角形，并将另外 两边压栈，再重复以上步骤。 算法输出：网格的所有三角形。 2 3 拓扑压缩 由于复杂网格的应用越来越广泛，当网格点数目比较大时，如果用o b j 格式 表示网格，那么拓扑数据将用6 1 ，个整型数据表示，其中y 为网格的顶点数。如 果用邻域图直接表示网格，其拓扑数据和o b j 格式一样，也要用6 y 个整型数据 9 浙江大学硕士论文 表示。 幸运的是，本文通过观察大量的网格例子，发现网格的很多顶点分布一般是 比较均匀的，特别是每个顶点的一邻域点，它们与该顶点的距离之间的差异不大。 因此对每个顶点，以该顶点为球心，以，为半径作球，这里厂满足，d = c ， 其中，d 为网格的所有顶点到该顶点的最短距离，对一个确定的网格来说，c 为 常数，c 的大小因网格的不同而不同，可以说c 为一个网格的特征数量，其值的 确定将在后面的章节中提到。 p 图2 p 8 为了便于说明，我们以平面网格为例，如图2 ，该网格共1 4 个 页点 r ，暑，只，只，忍，忍，另，只，与，日o ，日。，暑2 ，日3 ) ，我们取顶点昂，其一邻 域点为 墨，b ，只，e ) ，非一邻域点为 只，与，最，b ，毋o ，暑，名2 ，暑。) ，我 们将一邻域点分为两类：一类为圆内的一邻域点 日，罡，忍，只) ，一类为圆外的 一邻域点 只) ，同时该圆也将异的非一邻域点分为两类：一类为圆内的非一邻 l n 浙江大学硕士论文 域点 眉2 ，曰3 ) ，一类为圆外的非一邻域点。则顶点p o 的邻域点可用 ( 昂) = d ( 昂) u 忍) 一 日2 ，曰3 ) 表示，这里d ( 昂) 表示球内的所有网格顶 点 只，p l ，罡，b ，只，日2 ，p 1 3 ) 。 我们现在定义如下： 定义1 - 在一个三角网格中，给定一个常数c ，对每一个顶点忍，找出该网格 中所有点到该顶点的最短距离d ，以该顶点为球心，以c x d 为半径作球，球外 的一邻域点为顶点r 的第一类奇异点，记为墨。 定义2 ：在一个三角网格中，给定一个常数c ，对每一个顶点昂，找出该网格中 所有点到该顶点的最短距离d ，以该顶点为球心，以c x d 为半径作球，球内的 非一邻域点为顶点r 的第二类奇异点，记为足。 图4 中，顶点p o 的第一类奇异点为 墨= 只) ， 第二类奇异点为 是= 置2 ，暑，) 。 有了以上定义，我们便可以对网格的一邻域图表示法的拓扑数据进行压缩， 如果三角网格有n 个项点，我们便可以将网格压缩成如下格式： 常数c 顶点1 的x 坐标，顶点l 的y 坐标，顶点1 的z 坐标 顶点l 的第一类奇异点下标 顶点1 的第二类奇异点下标 浙江大学硕士论文 顶点2 的x 坐标，顶点l 的y 坐标，顶点1 的z 坐标 顶点2 的第一类奇异点下标 顶点2 的第二类奇异点下标 顶点n 的x 坐标，顶点1 的y 坐标，顶点l 的z 坐标 顶点1 3 的第一类奇异点下标 顶点1 3 的第二类奇异点下标 1 。7 1 6 4 4 3 v - 0 6 7 1 5 6 4 - 0 0 2 8 8 2 9 - 0 7 0 0 1 4 0 f5 s3 6 v - 0 7 0 0 1 4 0 - 0 0 5 2 1 6 t - 0 ? 0 0 1 4 0 f2 v 一0 6 7 1 5 6 40 0 1 2 3 5 5 - 0 6 7 1 5 6 d fl1 0 2 s41 0 l v - 0 7 0 0 1 4 0 - 0 0 2 0 5 9 2 - 0 6 7 1 5 6 4 f1 0 0 s0 v - 0 6 4 2 9 8 4 - 0 0 0 4 1 1 8 - 0 7 0 0 1 4 0 82 图3 图3 是网格的一邻域表示法压缩后的结果，其中，第一行的浮点数为网格的 常数c 的值，第二行第一个字母v 表示该行表示的是顶点1 的坐标，后面是顶点 1 的x ，y 和z 坐标，第三行第一个字母f 表示该行表示顶点1 的第一类奇异点 下标，后面的5 表示顶点1 的第一类奇异点是顶点列的第五个点，也即图5 中第 十三行表示的顶点。第三行第一个字母s 表示该行表示顶点l 的第二类奇异点下 标，后面的3 和6 表示顶点1 的第二类奇异点是顶点列的第三个和第六个顶点。 图5 中若顶点的第一类奇异点下标行缺失，表示该顶点的第一类奇异点数为零， 如第十三行表示的顶点5 ；若第二类奇异点下标行缺失，表示该顶点的第二类奇 异点数为零，如第五行表示的顶点2 ；若顶点的第一类奇异点下标行和第二类奇 异点下标行都缺失，表示该顶点的第一类和第二类奇异点的数目都为零。 1 2 浙江大学硕士论文 在这里，我们得到的压缩格式有如下性质： 性质1 ：若我们记吩( c ) 为网格中所有顶点的第一类奇异点数之和，h 2 ( c ) 为网 格中所有顶点的第二类奇异点数之和，则_ ( c ) 为减函数，吃( c ) 为增函数。 性质2 ：若网格曲面足够光滑且顶点的分布足够均匀，那么存在一个c 值，使得 第一类奇异点数和第二类奇异点数之和为0 图4 图4 的网格中，我们可以选取适当的c 值，使得每个顶点的所有一邻域点都 圆内，所有的非一邻域点都在圆外，这里的圆是定义1 中的圆。 2 4 拓扑解压 拓扑解压的过程为由我们在上一节得到的压缩格式求出所有顶点的一邻域 点，对于网格m 的每个顶点p ，我们首先求出网格中所有点到该点的最短距离 浙江大学硕士论文 d m i n = m i n d ( p i ，尸) ，m ) ，这里d ( 霉，尸) 表示三维空间中顶点到顶 点p 的欧氏距离，令，= c x d ，以p 为球心，以r 为半径作球，求出球内的所 有网格顶点的集合 d ( 尸) = 只m ，d ( 只，p ) 厂) 若顶点尸的第一类奇异点集为s i ( p ) ，第二类奇异点集为是( 尸) ，若顶点p 的 一邻域点集为( p ) ，则 n ( p ) = d ( p ) u 墨( p ) - s 2 ( p ) 这样我们就得到了顶点p 的所有的一邻域点。 以图2 为例，首先求出所有的网格点到顶点昂的最短距离d ( b ，p o ) ，然后 以p o 为圆心，以c d 为半径作圆，这样我们得到圆内的所有网格顶点 d ( 昂) = 日，最，b ，只，只2 ，暑，) 由于顶点昂的第一类奇异点集为 墨( 昂) = e ) 第二类奇异点集为 是( 异) = 名2 ，墨3 ) 所以顶点r 的一邻域点集为 ( 昂) = d ( p o ) u 8 。( 昂) 一是( 昂) = 暑，忍，只，只) 2 5 网格优化与拓扑压缩 由2 3 节我们得到的网格压缩格式的性质1 ：若我们记，l l ( c ) 为网格中所有 顶点的第一类奇异点数之和，刀2 ( c ) 为网格中所有顶点的第二类奇异点数之和， 1 4 浙江大学硕士论文 则( c ) 为减函数，n 2 ( c ) 为增函数。于是，基于邻域图表示的拓扑压缩的主 要目标是求出合适的常数c ，减少啊( c ) + ，z 2 ( c ) 。常数c 可由实验得出。为了 减少刀l ( c ) + 以2 ( c ) ，通常需要对原网格曲面作进一步的优化。 这是由于2 3 节的性质2 ：若网格曲面足够光滑且顶点的分布足够均匀，那么存 在一个c 值，使得第一类奇异点数和第二类奇异点数之和为0 于是我们打算先 对网格进行优化，使网格趋向于均匀，以便我们得到更好的压缩结果。本章分为 三个部分，第一部分为网格的优化，第二部分为网格的常数c 值的确定，第三部 分为实验结果和改进。 2 5 1 网格优化 网格的优化是在保持网格的拓扑数据不变的情况下，对网格顶点的几何坐标 作适当的调整，以期待达到更好的应用效果。本节为了使网格的每个顶点的邻域 点之间的分布相对比较均匀，只做简单的网格优化处理，当然更复杂的方法也许 可以达到更好的效果，我们的网格优化做法如下： 对网格的每个顶点p 其法向量为j i i ，一邻域点为 l ，2 ，虬) ，这里朋 为顶点p 的一邻域点的个数，我们首先求出一邻域点的重心坐标 mj _ p 7 = ! 三! 网格优化以后尸变化到 声一+ ( 玉元弘 上述方法可迭代数次，以便达到更好的效果。图5 是平面曲线的优化方法，我们 的网格优化方法与其类似。 1 5 浙江大学硕士论文 j n 2 5 2 常数c 值的确定 图5 经过网格优化以后，我们现在来确定具有 个顶点的网格的常数c 的值，我 们对网格的每个顶点只，求出其邻域点到该点的最大距离d 上和网格的所有顶 点到该点的最小距离心n ，那么最大距离和最小距离的比率为 = d 二觚d 二；n 我们求出网格中所有顶点的比率的平均值 巧 = 将其作为常数c 的值，下一小节是实验结果。 2 5 3 实验结果和改进 我们对大量的网格例子进行实验，结果如表l ： 1 6 浙江大学硕士论文 三角形 顶点数常数c第一类第二类奇异点 数奇异点奇异点总数 数数 c u p 4 6 2 5 42 3 1 2 71 2 5 1 92 1 0 0 21 8 2 1 0 2 0 f a n d i s k1 2 9 4 66 4 7 51 5 5 0 44 0 5 47 6 3 81 1 6 9 2 v e n u s 5 0 1 3 4 3 4 2 6 7 1 7 32 3 2 0 9 5 1 8 5 6 1 9 2 4 0 42 4 4 2 6 0 d in o s a u r4 7 8 5 82 3 9 3 l1 7 5 5 91 6 3 8 22 0 5 8 03 6 9 6 2 s c r e w d riv e r5 4 3 0 02 7 1 5 21 8 7 0 21 5 4 0 93 6 2 1 55 1 6 2 4 r o c k e r a r m8 0 3 5 44 0 1 7 72 0 1 7 13 0 8 2 79 5 4 6 31 2 6 2 9 0 m o u n t a in4 8 0 22 5 0 01 7 1 6 41 4 3 23 7 7 75 2 0 9 b u n n y 6 9 6 7 43 4 8 3 91 8 6 0 81 9 4 4 24 2 6 1 56 2 0 5 7 f a c e3 4 3 0 81 7 3 5 71 5 4 9 29 1 2 62 5 7 6 13 4 8 8 7 c o s t as u b 52 2 5 2 81 1 2 6 61 9 0 0 21 6 3 8 52 0 3 2 73 6 7 1 2 d h e a d _ n o is y 1 9 9 9 2 41 0 0 0 5 62 4 6 4 78 0 2 2 86 2 2 3 5 27 0 2 5 8 0 d h e a d s m o o t h 1 9 9 9 2 41 0 0 0 5 61 5 8 9 37 5 7 9 62 3 9 8 99 9 7 8 5 e y e s m o o t h 5 4 5 6 62 8 0 0 91 6 8 8 01 7 1 2 82 1 5 7 03 8 6 9 8 m e c h p a r t 1 4 6 7 4 07 3 3 6 61 7 7 0 24 9 7 9 97 0 2 5 61 2 0 0 5 5 p l a n c k h e a d5 0 8 8 62 5 4 4 52 5 0 9 11 8 8 6 81 1 9 0 9 61 3 7 9 6 4 s m o o t h _ b u n n y 6 9 6 7 43 4 8 3 91 8 8 1 2 1 9 0 9 2 4 5 2 7 86 4 3 7 0 t e e t h2 3 3 2 0 41 1 6 6 0 42 0 5 0 08 2 8 4 93 1 5 5 3 83 9 8 3 8 7 表1 从表1 中我们可以看出，常数c 在1 5 至1 8 之间取值时，奇异点总数一般 都大约是网格的三角形的总数，由于在o b j 格式中，三角形的连接关系是用三个 整数表示的，因此，我们的压缩格式相比于o b j 格式，几乎是压缩了i 3 的数据 量。如例子中的f a n d i s k ，d i n o s a u r ，s c r e w d r i v e r ，m o u n t a i n ，b u n n y ，f a c e ， m e c h p a r t 。而c u p 和d h e a d _ s m o o t h 更是将拓扑数据压缩到o b j 格式表示时的拓 扑数据的1 6 ，我们也可以从d h e a d _ n o i s y 和d h e a ds m o o t h 的例子看出，在拓 扑数据相同的情况下，几何数据对我们的结果的影响很大，而经过优化的均匀的 1 7 浙江大学硕士论文 网格往往能产生更好的结果。 从上面的表格中，我们还能了解到常数c 对我们的结果影响很重要，而我们 令c = 乞v g 是远远不够的，我们必须对我们的方法作出改进，以期达到更好的结 果。 在这里，我们把区间 1 ，2 r ，莒 分成一百等份，找出使第一类奇异点数和第二 类奇异点数之和最小的值作为常数c 的值。我们得到的试验结果如表2 ： 三角形数顶点数 最小c 值 第一类奇第二类奇奇异点总 异点数异点数数 c u p 4 6 2 5 42 3 1 2 7 i 4 9 6 3 0 69 9 34 2 81 4 2 i b u n n y 6 9 6 7 43 4 8 3 91 7 3 4 8 7 63 8 4 6 9 2 1 4 0 15 9 8 7 0 f a n d i s k1 2 9 4 66 4 7 51 5 2 5 2 2 74 6 5 1 6 9 6 11 1 6 1 2 m o u n t a in4 8 0 22 5 0 01 7 2 9 8 6 61 3 5 9 3 8 4 25 2 0 1 c o s t s u b 5 2 2 5 2 81 1 2 6 61 7 0 0 1 0 02 2 3 9 6 9 4 8 73 1 7 8 3 f a c e3 4 3 0 81 7 3 5 71 5 0 3 6 1 61 2 9 7 5 2 1 9 2 23 4 8 9 7 p l a n c k h e a d5 0 8 8 62 5 4 4 51 7 6 3 4 5 85 5 3 1 01 7 2 7 37 2 5 8 3 e y e s m o o t h5 4 5 6 6 2 8 0 0 9i 6 1 7 7 6 02 2 4 5 81 3 6 2 93 6 0 8 7 表2 在表2 中，从c u p 的例子我们可以看出，当c 值为1 4 9 6 3 0 6 时，我们的第 一类奇异点数为9 9 3 ，第二类奇异点数为4 2 8 ，奇异点总数为1 4 2 1 ，如果用o b j 格式表示拓扑数据，那么我们将用三角形数量的三倍的整型数据来表示，及 1 3 8 7 6 2 个整型数据表示网格的拓扑数据，而我们的压缩格式只需1 4 2 1 个整型数 据便能表示由2 3 1 2 7 个顶点构成的网格的拓扑数据，如果用比特率表示压缩率， 用2 字节无符短整型数据表示，那么我们的压缩率为0 9 8 3 印v 。这主要是因为 例子c u p 的网格点分布比较均匀，而其他例子不够均匀，使得试验结果不及c u p 浙江大学硕士论文 好，但相比于o b j 格式，。其数据量也得到了极大的减少。如果我们的网格分布更 均匀，那么我们的结果应该更漂亮，由2 3 节的性质2 ，如果可以使网格足够均 匀和光滑，那么网格的奇异点总数将趋向于零。 三角形数顶点数第一类第二类奇异点 奇异点奇异点总数 数数 v e n u s 5 01 3 4 3 4 26 7 1 7 31 6 3 5 7 72 1 0 2 61 8 4 6 0 3 r o c k e r a r m8 0 3 5 44 0 1 7 76 3 8 3 22 3 7 8 88 7 6 2 0 c o s t s u b 5 2 2 5 2 81 1 2 6 62 2 4 0 09 4 8 33 1 8 8 3 d h e a d n o is y1 9 9 9 2 41 0 0 0 5 61 9 9 9 5 98 2 3 4 i2 8 2 3 0 0 p l a n c k h e a d5 0 8 8 62 5 4 4 56 0 0 9 71 3 0 3 07 3 1 2 7 t e e c h 2 3 3 2 0 41 1 6 6 0 41 7 7 7 7 47 5 1 4 52 5 2 9 1 9 表3 ：所有网格的常数c 取值为1 7 0 对于表l 中因常数c 的值较大，而使我们的网格表示方法的拓扑数据量较大 的例子，我们取常数c 为1 7 0 ，便得到了表3 所示的试验结果，从表3 中我们 可以看出，o b j 格式表示的拓扑数据量比一邻域图表示法的压缩格式的拓扑数据 量要大两三倍。所以我们的表示方法的优势还是明显的。 我们的做法简单易于实现，对采样均匀的网格可实现高倍压缩，对一般网格 而言，拓扑数据量只相当于o b j 表示的拓扑数据量的1 3 左右。 1 9 浙江大学硕士论文 第三章几何压缩 在三角网格中，几何数据所占的存储空间比拓扑数据所占的存储空间要多很 多，因此，研究几何数据的压缩越来越热点，本章提出的几何压缩算法运算速度 快，能很好的满足实时性要求，其结果为将顶点数为n 的三角网格的几何数据压 缩为2 n + 所一1 个整型数据和m 个顶点( 3m 个浮点型数据) ，这里朋是一个比 刀小得多的整数。本章分为三个部分，第一部分介绍几何压缩算法，第二部分介 绍压缩算法的解压过程，第三部分为压缩结果及其与其他方法的比较。 3 1 几何压缩 本节在进行压缩前，先将所有的顶点按x 坐标从4 , n 大作重排列，并将拓扑 数据中三角形的连接关系下标换成重排列后顶点的下标，以图6 为例。 图6 该网格为二维平面网格，其几何数据为： r 7 ，e ，乞，只，忍，乞) 浙江大学硕士论文 共六个三角形，它们的连接关系即拓扑数据为： o ，5 ，1 0 ，2 ， 3 0 ，4 ，