资源描述：
《增量几何压缩》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1139-1282/2000/11(09)1167-09©2000JournalofSoftware软件学报Vol.11,No.9+增量几何压缩刘新国鲍虎军彭群生浙江大学CAD&CG国家重点实验室，310027，杭州摘要本文提出了一个几何压缩算法节省三角网格模型存储和传输时间。它首先递归地以区域扩张方式将模型分解为一系列的层结构，利用层间的连贯性，以及对层结构的有效编码，实现了高效的拓扑压缩。同时，还设计了一个有效的非线性预测器来实现几何位置的压缩。与以前的算法相比，它具有线性复杂度，压缩比高，执行速度
2、快。实验结果表明，存储一个三角形的拓扑信息平均只需1.42比特。关键词几何压缩二维流形定向曲面三角形网格模型一、引言尽管自由曲面广泛应用于CAD和计算机动画系统中，但多边形模型，尤其三角形网格由于其简单性和灵活性，也被大量的图形硬、软件普遍支持。近年来，稠密的三角形网格模型逐渐在许多应用领域，如数字地形、可视化、虚拟现实及基于三维扫描的自动造型中得到了越来越广泛地应用。这使得对高度复杂、精细三角形网格的实时编辑、绘制和传送成为一个极具挑战性的课题。最初人们为了减少绘制时间，加快绘制速度研究几何压缩算法[
3、1,2,3,4,5]。几何压缩不同于传统的图象压缩机制。一个几何网格模型通常由其拓扑和几何信息二部分组成，其中拓扑信息是指网格顶点之间的相互连接关系，而几何信息则指网格顶点的位置信息及附着在各顶点的有关绘制信息，如颜色、法向和纹理坐标等。几何压缩的目标是减少复杂三角形网格在其拓扑和几何位置信息表达方面的冗余度。二、相关工作类似于VRML中的IndexFaceSet，一个简单的三角形网格模型可表示为一个顶点数组和一个三角形数组，分别存放顶点的几何位置和三角形顶点下标。对于N个顶点和M个面的三角形网格模型，
4、若用三个4个字节的浮点数来存贮每个顶点的空间坐标，4个字节的整数表示顶点的下标，其存储量为12N+12M字节。通常三角形个数是顶点个数的两倍左右，所以平均每个三角形的存储量是18字节。注意到这种表示方法中仍存在许多冗余信息，一种基于带状三角形结构（trianglestrip）的三角形网格表示方法得到了图形学界的高度重视。通过重用前两个被访问过顶点和加入一个新顶点的方式来定义新的三角形，这种带状三角形结构减少了对顶点的索引次数，从而大大减少数据存储。在这种表示法中，平均而言，每一顶点被索引二次左右，存储一
5、个三角形大约需14字节。尽管带状三角形结构可以减少对三角形网格模型的存储，但是采用一系列带状三角形结构完全覆盖一个具复杂拓扑的模型并非易[6,7,8,9,10]事。进一步研究发现，采用更复杂的编码方法，还能够大大地节省存储量。[2,5]Deering给出了一个一般化的带状三角形表示方法，通过增加索引缓冲的长度，在重[8]用已访问顶点方面得到了更多的控制，从而减少数据存储量。Taubin等在TopologySurgey算法中，通过构造一棵顶点树和一棵三角形树对连接关系进行编码。借助于这两棵树，表示一个三角
6、形只需要1个比特。加上记录顶点树所需的额外数据，存储一个三角形平均仅需[6]1.2至3.5比特(平均不超过2比特)。而Gumhold等则构造和维护一些顶点序列组成的分割边界，并引入七种不同的操作构造下一个三角形，根据构造三角形所使用的操作对这些分割边界进行动态维护。由于这些操作的使用频率各不相同，且相差很大，所以可采用Huffman编码进一步减少数据量，存储一个三角形平均需要1.5至4.23比特。[11,12,13,14,15,16,17]多分辨表示和LoD简化算法也可以看作是一类几何压缩算法，只是它改
7、变了原来模型中顶点集合和拓扑信息，而这在很多情况下是不被允许的。但是Hoppe的累进网[11,13]格方法（简称PM）不同，它所表示的LoD模型序列具有很强的连惯性，通过简单的顶点分裂操作可以逐步地完全恢复原来的拓扑信息。再对顶点分裂操作的有效编码，就能实现+本文收国家自然科学杰出青年基金（批准号：69925204），霍英东青年教师基金资助。—1168—JournalofSoftware软件学报2000,11(9)几何压缩。一个分裂操作包含一个分裂顶点和两条分裂边，如果当前层次模型的顶点数为N，存储分裂
8、顶点需要Log(N)个比特；如果顶点平均入度为6，存储两条分裂边平均需要大约5.3[14]比特。Taubin等扩展了PM方法，通过对一组相关的顶点分裂，称之为森林分裂(forestsplit)，进行编码，减少记录分裂操作的数据，从而获得更高的压缩比。拓扑信息压缩的关键在于充分地利用三角形顶点序列的连贯性。这需要我们以一种特殊地顺序和方式遍历网格中的三角形。通过以区域扩张的方法将原网格模型分解为一系列的层结构，在层与层之间保持极大的顶点连惯性
