应用哈密顿回路的三角网格拓扑压缩

Connectivity Compression of Triangle Meshes Based on Hamiltonian Cycle

为进一步优化三角网格的拓扑编码压缩率,提出一种高效的三角网格无损拓扑压缩算法.与已有的拓扑压缩算法对三角网的遍历顺序不同,该算法沿哈密顿回路对网格进行以面为单位的拓扑压缩,可以仅用HETS共4种操作符表示原始网格的拓扑信息,降低了操作符序列的熵;此外,利用序列中各操作符的相互关系对操作符成对进行组合熵编码,缩短了操作符序列的长度.实验结果表明,较当前各类拓扑压缩算法,文中算法处理各种三角网格模型获得的压缩率有很大降低.

We presented an efficient encoding algorithm for lossless compression of triangle mesh connectivity to optimize the compression ratio. Different from the traversal order of the former connectivity compression algorithms on the triangle mesh, this algorithm compresses the mesh face by face following the Hamiltonian cycle, and can adopt only four operators to represent the connectivity of the original mesh, which reduces the entropy of the operators. On the other hand, the length of the operator sequence can be shortened by encoding the operators in pairs. Experimental results show that the algorithm proposed in this paper can achieve much lower compression ratios on various triangle meshes than current connectivity compression algorithms.