3D网格压缩技术详解

# 3D 网格压缩技术详解 ## 1 引言 在 3D 图形处理中，网格压缩是一个至关重要的环节，它能够有效减少数据传输量和存储空间，提高处理效率。本文将详细介绍几种常见的 3D 网格压缩方法，包括单速率连接压缩和渐进式连接压缩，并对它们的特点和性能进行分析。 ## 2 单速率连接压缩 ### 2.1 分层分解方法 分层分解方法可以独立编码不同的顶点和三角形层，从而将传输错误的影响局部化。基于此方法，有算法被提出用于编码大型 CAD 模型，该算法将分层分解方法扩展到压缩四边形和一般多边形模型，以及具有光滑非均匀有理 B 样条（NURBS）面片的 CAD 模型。 ### 2.2 价驱动连接编码方法 - **基本原理**：该方法首先选择一个种子三角形，其三条边形成初始边界线，将整个网格划分为已处理的内部部分和待处理的外部部分。然后边界线逐渐向外扩展，直到整个网格处理完毕，输出一系列顶点价，通过这些价可以重建原始连接性。 - **Touma 和 Gotsman 算法**：从任意三角形开始，将其三个顶点压入活动列表。每次从活动列表中弹出一个顶点，遍历所有未遍历的与该顶点相连的边，并将新顶点压入列表末尾。对于每个处理的顶点，输出其价。有时需要分割当前活动列表或与另一个活动列表合并，这些情况用特殊代码编码。在编码前，为每个边界环添加一个虚拟顶点并连接到该边界环的所有顶点，使拓扑封闭。由于典型网格中顶点价紧凑分布在 6 左右，可利用算术编码有效编码顶点价信息，平均编码网格连接性成本低于 1.5 bpv，但仅适用于可定向流形网格。 - **Alliez 和 Desbrun 改进算法**：为了进一步提高 Touma 和 Gotsman 算法的性能，该算法采取了以下优化措施： - **减少分割代码数量**：使用启发式方法选择自由边数量最少的顶点作为下一个焦点顶点，而不是选择活动列表中的下一个顶点。 - **减少分割偏移位数**：排除当前活动列表中焦点顶点的两个相邻且不适合分割的顶点，根据其余顶点到焦点顶点的欧几里得距离对其进行排序，分割偏移用排序列表中的索引表示，再加上 6 并以与正常价相同的方式编码。 - **减少虚拟顶点数量**：为输入网格的所有边界采用一个公共虚拟顶点。 - **编码输出符号**：使用范围编码器（一种有效的自适应算术编码器）对输出符号进行编码。该算法同样仅适用于可定向流形网格，在不规则网格上表现更优，若分割数量可忽略不计，其性能上限为 3.24 bpv。 ### 2.3 三角形征服连接编码方法 #### 2.3.1 切割边界机方法 - **基本原理**：与价驱动方法类似，从初始边界线开始，将整个网格划分为已征服和未征服部分，然后逐个插入三角形到已征服部分。不同之处在于，该方法输出新三角形的构建操作，而价驱动方法输出新顶点的价。 - **操作步骤**：在每一步，使用“新顶点”、“向前”、“向后”、“分割”和“关闭”五种构建操作之一将新三角形插入由切割边界封闭的已征服部分。构建操作序列用 Huffman 码编码。该方法适用于可定向或不可定向的流形网格，压缩成本在 3.22 - 8.94 bpv 之间，大多约为 4 bpv。其优点是解压缩速度快，解压缩方法易于用硬件实现，且压缩和解压缩操作可并行执行。 - **优化方法**：Gumhold 通过使用自适应算术编码器优化边界编码，进一步提高了压缩性能，实验压缩比在 0.3 - 2.7 bpv 之间，平均为 1.9 bpv。 #### 2.3.2 边破拆器算法 - **基本原理**：与切割边界机方法类似，但不编码与分割操作相关的偏移数据。三角形遍历由边环控制，每个边环界定一个已征服区域并包含一个门边缘。在每一步，聚焦于一个边环，其门边缘称为活动门，其他边环存储在栈中稍后处理。 - **操作步骤**： 1. 对于每个连接组件，定义一个边环。若组件没有物理边界，将对应一条边的两个半边设置为边环。 2. 每一步征服一个与活动门相邻的三角形，更新当前环，并将活动门移动到更新后环中的下一条边。 3. 对于每个征服的三角形，输出一个操作码。操作码有五种可能：C（环扩展）、L（左）、R（右）、E（结束）和 S（分割）。压缩过程本质上是对网格对偶图的深度优先遍历，遇到分割情况时，当前环分割为两个，其中一个压入栈中，另一个继续跟踪。该方法可以编码具有多个边界环或任意亏格的可定向流形网格的拓扑数据，简单网格的最坏情况编码成本为 4 bpv，但不适合流式应用，因为解压缩需要两步过程，解压缩时间为 $O(N_v^2)$。 - **改进算法**：不同学者对边破拆器算法进行了改进，如 King 和 Rossignac 保证简单网格的最坏情况编码成本为 3.67 bpv，Gumhold 进一步将上限提高到 3.522 bpv，Szymczak 等人针对高规则性网格优化了该方法，保证足够大的高规则性网格的最坏情况性能为 1.622 bpv。 #### 2