基于拓扑手术的几何压缩

基于拓扑手术的几何压缩基于拓扑手术的几何压缩 GABRIEL TAUBIN JAREK ROSSIGNAC 摘要摘要 来源于主要工业部门的复杂的三维数据变得日益丰富而重要，办公和私人所使 用的交互式三维渲染随处可以得到，互联网上传送和共享的三维数据正以几何级数递增， 所有这些应用极大的刺激了对高效的三维几何压缩技术的需求。三维几何压缩技术在减 少三维模型通过数字传送通道的传输时间和减少磁盘空间存储量方面具有重要意义。因 为以前的三维模型是 通过多面体来表示的，多面体模型在渲染时通常会对表面模型进行三角面片化，所以本 篇文章介绍一种新的复杂三角面片模型的压缩表示方法简单而高效的压缩与解压缩 算法。 在这个方案中，顶点的位置坐标在给定的精度内进行量化，然后构造一颗顶点跨度树， 通过树中的 2，3 或者 4 个先前的顶点来预测当前顶点的位置坐标，然后对校正的顶点 坐标进行熵编码。法线，颜色，纹理坐标等属性信息也是使用相同的方法进行压缩。连 接信息的编码属于无损压缩，平均每个三角形小于两比特。顶点跨度树和少量的跳跃边 把模型分离成一个简单的多边形。一颗三角形跨度树和一系列匹配位用来对三角化的多 边形编码。我们的方法在 Michael Deering 的研究成果之上进行改进，充分利用在顶点 跨度树中若干祖先顶点的几何相近性，保持了连接信息的无损压缩，避免了顶点的重复， 连接信息仅使用了小于三倍的比特位。然而由于解压缩需要对所有顶点随机存储，此方 法硬件渲染时必须修改以适应有限的内存。最后，我们演示了一些达到两个数量级压缩 效果的 VRML 模型的实现结果。 1引言引言 尽管在机械 CAD 和动画方面模型系统正在扩展它们的几何领域向自由曲面方向发展， 多面体模型仍然是制造，建筑，地理信息系统，地球科学和娱乐行业所使用的主流三维表 示方法。多面体模型在硬件辅助渲染方面尤位有效，它对于视频游戏，虚拟现实，飞行模 拟和涉及复杂 CAD 模型的电子模型试验应用十分重要。 相对于图像和视频压缩而言，无论是研究机构还是三维数据交换标准委员会都很少关 注三维形状的压缩问题。这种形式很可能因下述原因而迅速改变。 （1）机械 CAD 模型复杂性的爆炸式增长大大增加了处理这些模型所需的内存和 辅助存储的成本。 （2）协同设计，游戏，快速成型，虚拟交互中，三维模型在网络中的传输被可得 到的有限带宽所限制。 （3）高性能硬件适配器的图形性能由于内存不足以存储整个模型或者由于传输瓶 颈问题而被大大制约。 由于任意的多边形面片可以简单高效的三角面片化，此篇文章只进行三角网格的解释。 一个三角形网格被它的顶点(位置)，三角形之间的连接关系（连接信息） ，颜色，法线及纹 理信息（属性） （属性信息不影响三维几何信息，但会对渲染方式产生影响）所定义。 本篇所介绍的压缩格式和压缩与解压缩算法是在 Deering 先前所作的工作基础之上展 开的，具体如下： （1）连接信息的无损编码和高压缩比（平均每个三角形小于两个比特） ；图 1 是一个 例子。 （2）更好的关于坐标压缩的顶点组织形式。 （3）对任意拓扑结构的多边形模型，为建立接近最优的压缩提供高效率的方法。 （4）压缩和解压缩技术产生很长的三角形条带，因此很适合当前的高端图形适配器。 2相关的工作相关的工作 近年来被广泛研究的三维压缩方法可以分为三类：多面体简化，位置和属性压缩，和 连接信息的编码。 2.1 多面体简化多面体简化 多面体简化技术通过改变模型的连接信息来减少网格中的顶点数目，同时尽可能的调 整其余顶点的位置以使由于简化而形成的网格误差为最小。这些技术集中于促使过采样网 格中图形或数据的减少来达到产生多细节层次（LOD）的目的。尽管这些技术被认为是有 损压缩，它们不适合应用于要求有精确连接信息的模型。实际上简化技术和这里描述的压 缩技术是交叉的，因为几何压缩可以应用于每一个细节层次（LOD） 。 2.2 位置和属性的压缩位置和属性的压缩 无损或有损压缩方法用来减少和顶点位置相关的几何数据存储量（必须） ，和可能的 法线，颜色，和纹理坐标信息。应用通常目的的数据压缩算法于几何数据流会产生非最佳 的解决方法。我们构建 Deering 的方法，标准化几何数据在一个单位立法体内，圆整顶点 坐标为固定长度的整数。圆整的效果决定了损失的信息量。我们把顶点空间组织成一颗跨 度树，使用几何预测法用小的校正差值来代替位置和属性坐标，校正差值可以用更少的位 数进行无损编码，然后使用标准的无损熵编码技术进一步压缩。由大量小三角形组成的网 格在量化过程中所形成的人工痕迹可以通过网格平滑方法来减少。 2.3 连接信息编码连接信息编码 在许多流行的多面体或三角形网格的 3D 表示中，连接信息编码通常是试图减少内在 的冗余，这是主要的焦点也是本篇主要的贡献。 考虑一个 V 个顶点，T 个三角形的三角形网格（对于一个简单拓扑结构的网格，三角 形的个数大约是顶点个数的两倍）假定顶点以一个适当的顺序排列，定义这些顶点所支持 的 T 个三角形最少需要多少个比特位呢？ 从一个极端考虑，如果顶点总是被组织成一个标准的 2 维网格，三角形网格可以完全 被网格的行和列数所定义。正规的网格可以适用于 GIS 中的梯田模型和用于渲染统一的镶 嵌的非裁减矩形参数补块，然而它们不适用于 CAD，娱乐和其它应用中更通用的 3D 形状。 从另一个极端考虑，一个三角形可以被三个顶点引用所表示（指针或者顶点位置数组 的索引） ，这种解决方案不会对网格施加任何拓扑限制，但是每个三角形需要存储三个地址 （大概每个顶点六个地址） ，即使限制模型小于 1024 个顶点，这种方案仅连接信息每个顶 点就将消耗 60 个比特位。 在图形 API 中使用的三角形条带，例如 OpenGL 提供了一个折中方案，一个新顶点和 先前的两个顶点组合隐式地在当前的条带中定义了一个新三角形。三角形条带仅仅当可以 建立长三角形条带时才可以取得预期的效果，而长三角形条带问题是一个具有挑战性的计 算几何问题。近一步讲，由于一个顶点属于相同三角形条带或者两个不同的条带，平均被 使用两次，OpenGL 所使用的三角形条带需要传送大多数顶点多次，交换操作的缺乏进一 步增加了这种冗余。 三角形条带作为一种压缩技术的应用（所有顶点的位置在解压缩过程中可以随机访问 得到） ，每个三角形仍然需要存储一个顶点引用，每个条带需要两个顶点引用，而且需要保 存条带的数量，长度信息和每个三角形的附加信息位，这个信息位用来标识先前三角形的 哪一个公共边用来作为下一个三角形的基边（这个标识位相当于 GL 中的交换操作） 。 Deering 提出使用一个栈缓冲存储先前使用的 16 个顶点取代对模型所有顶点的随 机访问，这对存贮器非常有限的适配器是一个很合适的解决方法。Deering 对如何使用下一 个顶点提供了更通用的控制，以及允许栈中当前顶点的短时间包括和栈缓冲中 16 个顶点任 一个的重新使用，这使三角形条带的语义通用化。这种连接信息的存储成本是：每顶点一 比特位，表明是否把该顶点推入栈缓冲中；每三角形两比特位，表明如何控制当前的条带； 每三角形一比特位，表明是读入一个新顶点，还是从栈缓冲中读入一个顶点；以及四个比 特位的地址，每次当旧顶点被使用时用来从栈缓冲中选择顶点。假定一个顶点仅仅被使用 一次，则连接信息编码的总代价是：14 比特/顶点加 2+1 比特/三角形。假定每顶点两个 三角形，则总的代价位大概为 11 比特/顶点（当然，其它通用目的的压缩方案可以被应用 于产生比特流，但是上述情况是对所有种类几何压缩的讨论，因此忽略了这种相对的分析） 。 就我们所知，使用 Deering 的通用三角形网格目前还不能系统的创建好的遍历通用网格的 算法。不成熟的遍历网格方法会产生许多孤立的三角形或者小的分支，这意味着顶点中的 重要部分将会被传送一次以上，因此增加了每个三角形的比特位数。 在以上假设的基础之上，所有的顶点坐标解压缩时可以随机访问得到，本篇所提供的 解决方案比 Deering 的方法多产生两到三倍的压缩比，并且为计算接近最优的连接信息编 码提供了实践性和有效的算法。做为副产品，解压缩算法建立了非常长的三角性条带，这 适合于与当前的 3D 渲染适配器进行最优化交流。 而且，我们的压缩算法保持了网格的原始连接，而 Deering 的方法经常做不到这一点， 我们还使用了相近性组织顶点，这可以进一步对位置和属性信息进行压缩。 3 综述综述 三角形网格中的三角形可以形成一个或多个连接的流形组件。在我们的压缩方案中， 每一个连接组件的连接信息首先通过在组件的顶点和边图中构造一个顶点跨度树，来进行 编码。 由于在顶点跨度树中的相近性经常意味着对应顶点的几何相近性，我们可以使用树中 的祖先来预测顶点的位置，因此仅仅需要对预测值和实际顶点位置值之间的差值进行编码。 当顶点坐标被量化（例如，在一个定点表示方案中被截断到一个最接近的数字） ，这些校正 的向量通常比绝对的位置有更小的广度，因此可以使用更少的比特位来编码。然后校正的 差值使用熵编码进行压缩，例如在 JPEG/MPEC 标准中使用的哈夫曼编码或算术编码。 为了对连接信息编码，网格首先沿着称做切割边的边子集进行切割，这个子集包括顶 点跨度树的所有边，也可以有少量的不属于顶点跨度树的切割边。例如，对一个简单网格 （球面同构体网格）如图二所示，我们证明除顶点跨度树的边以外，没有其它切割边。 顶点跨度树的分支节点和叶子节点被顶点行程（仅有一个孩子的若干相连顶点集）相 互连接。我们通过对每一个顶点行程编码来压缩顶点跨度树的表示，编码由长度加两比特 信息位组成，信息位可以正确的俘获顶点跨度树的拓扑结构。为了提高压缩率，我们尽力 构造具有最小行程数量的顶点跨度树。 这种表示仅能俘获顶点跨度树的结构，顶点跨度树的节点和顶点位置的对应关系通过 存储的每一个顶点位置的压缩编码（例如校正差值熵编码）来建立，而顶点位置的存储顺 序必须和顶点跨度树中相应节点的先序遍历（深度优先）顺序相一致。 当作为拓扑边界处理，切割边把网格组织成一系列被分支三角形相连的三角形行程。 每一个分支三角形连接三个行程（我们把相近的两个分支三角形作为长度为一的三角形行 程） 。在行程或限制的分支三角形内连接三角形的边称作匹配边，我们证明了简单网格的一 条边（球面同构体的网格）不是匹配边就是顶点跨度树的边。 图的顶点对应于三角形、图的边对应于匹配边，这样的一张图形成了网格三角形的一 颗二叉跨度树。它是沿顶点跨度树进行切割产生的网格对偶图，我们采用和顶点跨度树相 同的编码方式对三角形跨度树编码，然而由于三角形树是二叉树，我们仅需存储每一个三 角形的行程长度加一个比特信息位。 这两颗树和压缩的顶点位置联合起来可以恢复每一个三角形行程的长度和边界以及封 闭每一个三角形的顶点。解压缩的第一步是由复原程序建立一个顶点索引查询表，这个表 反映了顶点沿网格（由切割边产生的网格）的边界环出现的顺序。图三演示了这个边界的 形成，为了直观起见，人为的扩大了切割边产生的拓扑连接性并且使边界环所包围的三角 化的多边形在平面内显示。这个切割和在平面内显示的过程和剥柚子皮的过程类似，所有 皮会保持连接性。显而易见，不同的切割策略产生不同行程数目的三角形树，我们研究了 一种切割策略似乎可以有效的把三角形和顶点行程的数目减小到最少。 对应于三角形树从上到下的遍历顺序遍历一个三角形行程可以定义左右边界。因为每 一个三角形行程的左右边界形成了边界环的连接分支，如果我们知道两个起始顶点和沿行 程左右边界的顶点数目，就可以复原每个行程的边界。 在三角形行程中，每个当前的匹配边和它先前的匹配边共享一个顶点，这个共享的顶 点可能位于左边界或右边界上，每个匹配边使用一个比特位来对正确的边编码，这些比特 位按照解压缩算法中匹配边被访问的顺序串行化，这就形成了我们称作的左或右步骤中的 匹配模式。 三角形跨度树表示的一个入口表明了在一个行程中匹配边的数量 N，然后是三角形行 程左右两边界的总顶点数目。匹配模式中的 0 表明了左边界顶点的数目，相应的 1 表明了 右边界顶点的数目。 给出边界环查询表中的两个索引（一个是左边界的起始点，另一个是右边界的起始点） ， 我们的解压缩算法接下来使用匹配模式的 N-1 个比特位为这个行程建立一个三角形条带。 在行程的末端，我们可能遇到三角形跨度树的一个叶子或者是一个分支三角形。在后 面一种情况，行程的最后匹配边构成邻接分支三角形的基。分支三角形的第三个顶点称作 Y 顶点，在边界环中相应的索引不是按我们的压缩格式那样显式的存储，而是在解压缩预 处理步骤中，以相对于父亲三角形行程左边界最后一个顶点的相对位置的形式存储在查询 表中。 解压缩算法将以递归的方式访问分支三角形的两个边所连接的两个行程，直到三角形 跨度树遍历结束并且所有的三角形被复原。沿着先序遍历的连接路径联结遇到的三角形可 以建立长三角形条带，这些路径以根或者一个分支节点为始点，在相应分支的最左叶子处 结束。 法线、颜色、和材质映射坐标也可以和三角化的模型联系起来。这些被模型的顶点所 列出，主要是出于渲染的目的。但是在不同的三角形中每一个顶点的使用可能是不同的。 在第六部分我们将演示跨度树的压缩表示对可以用来压缩法线、颜色、和纹理映射坐标的 三角形顶点有一个隐式的顺序。 4 简单网格简单网格（略） 5 通用网格通用网格（略） 6 属性信息属性信息（略） 7 实现结果实现结果（略） 8 结束