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

Connectivity Compression of Triangle Meshes Based on Hamiltonian Cycle

作　　者：张洁[1,2] 吴佳泽[1] 郑昌文[1] 胡晓惠[1] 

机构地区：[1]中国科学院软件研究所综合信息系统技术国家级重点实验室,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机辅助设计与图形学学报》2013年第5期697-707,共11页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2009AA01Z303)

摘　　要：为进一步优化三角网格的拓扑编码压缩率,提出一种高效的三角网格无损拓扑压缩算法.与已有的拓扑压缩算法对三角网的遍历顺序不同,该算法沿哈密顿回路对网格进行以面为单位的拓扑压缩,可以仅用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.

关 键 词：拓扑压缩 哈密顿回路 三角网格 算术编码 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]