Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (9): 2590-2596.DOI: 10.11772/j.issn.1001-9081.2016.09.2590

Previous Articles     Next Articles

Fast and effective compression for 3D dynamic scene based on KD-tree division

MA Zhiqiang, LI Haisheng   

  1. Academy of Electronic and Information Technology, China Electronics Technology Group Corporation, Beijing 100041, China
  • Received:2016-02-29 Revised:2016-04-03 Online:2016-09-10 Published:2016-09-08


马志强, 李海生   

  1. 中国电子科技集团公司 电子科学研究院, 北京 100041
  • 通讯作者: 马志强
  • 作者简介:马志强(1982-),男,山东临沂人,工程师,博士,CCF会员,主要研究方向:计算机图形学、远程可视化;李海生(1983-),男,内蒙古巴彦淖尔人,工程师,硕士,主要研究方向:计算机图形学、实时渲染。

Abstract: In order to take full advantage of GPU to realize fast and effective compression and reduce the limitation of network bandwidth, a fast and effective compression method based on KD-tree was presented. Firstly, the dynamic scene was divided by KD-tree at the first time step and small rigid bodies were constructed in each leaf in parallel. The mapping relations between rigid body leaves and the 3D divided grid were established to merge rigid bodies by using disjoint set. Finally, the compressed dynamic data were transmitted to the client to reconstruct the 3D dynamic scene within a certain period of time. The algorithm can greatly improve the speed of compression on the server, and effectively reduce the amount of data. The experimental results show that the proposed algorithm can not only guarantee the quality of the compression, but also compress dynamic datasets quickly and effectively which reduces the limitation of network bandwidth for the dynamic data.

Key words: KD-tree division, disjoint set, rigid body merging, time-varying dataset, dynamic data compression

摘要: 为充分利用GPU并行计算特点,实现对三维动态数据的快速有效压缩,降低网络带宽的限制,提出一种基于KD-tree剖分的快速有效压缩方法。首先使用KD-tree在第0帧对整个三维场景进行划分,并对每个叶子节点进行刚体的并行构造;建立能构造刚体的叶子节点和均匀划分的三维网格之间的映射关系,在三维空间使用并查集合并并行构造的刚体;最后将压缩后的动态数据传输到客户端并重构一定时间内的三维动态场景。算法可以极大提高服务器端数据的压缩速度,有效减少需要传输的数据量。实验结果表明:该算法在保证压缩质量的同时,可以对原始三维动态场景进行快速有效压缩,有效降低网络带宽对数据传输的限制。

关键词: KD-tree剖分, 并查集, 刚体合并, 时变数据集, 动态数据压缩

CLC Number: