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

doi:10.11772/j.issn.1001-9081.2016.09.2590

Abstract

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:

TP391.41

MA Zhiqiang, LI Haisheng. Fast and effective compression for 3D dynamic scene based on KD-tree division[J]. Journal of Computer Applications, 2016, 36(9): 2590-2596.

马志强, 李海生. 基于KD-tree剖分的三维动态场景快速有效压缩[J]. 计算机应用, 2016, 36(9): 2590-2596.

References

[1] GUSKOV I, KHODAKOVSKY A. Wavelet compression of parametrically coherent mesh sequences [C] // SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Aire-la-Ville, Switzerland: Eurographics Association, 2004: 183-192.
[2] PAYAN F, ANTONINI M. Wavelet-based compression of 3D mesh sequences [EB/OL]. [2016-01-02]. http://www.i3s.unice.fr/~fpayan/data/publications/Payan_ICMI_2005.pdf.
[3] BEAUDOIN P, POULIN P, VAN DE PANNE M. Adapting wavelet compression to human motion capture clips [C] // GI '07: Proceedings of the 2007 Graphics Interface. New York: ACM, 2007: 313-318.
[4] WOODRING J, SHEN H W. Multiscale time activity data exploration via temporal clustering visualization spreadsheet [J]. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(1): 123-137.
[5] MA K, SHEN H. Compression and accelerated rendering of time varying volume data [EB/OL] . [2015-11-26] . http://web.cse.ohio-state.edu/~hwshen/papers/Ma2000.pdf.
[6] LEDERGERBER C, GUENNEBAUD M, MEYER M, et al. Volume MLS ray casting [J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6): 1372-1379.
[7] VUÇINI E, MÖLLER T, GRÖLLER M E. On visualization and reconstruction from non-uniform point sets using B-splines [J]. Computer Graphics Forum, 2009, 28(3): 1007-1014.
[8] JANG Y, EBERT D S, GAITHER K. Time-varying data visualization using functional representations [J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(3): 421-433.
[9] ARIKAN O. Compression of motion capture databases [J]. ACM Transactions on Graphics, 2006, 25(3): 890-897.
[10] LANGE R, FARRELL T, DURR F, et al. Remote real-time trajectory simplification [C] // Proceedings of the 2009 IEEE International Conference on Pervasive Computing and Communications. Washington, DC: IEEE Computer Society, 2009:1-10.
[11] VRIES G D, SOMEREN M V. Clustering vessel trajectories with alignment kernels under trajectory compression [C] // Proceeding of European Conference on Machine Learning and Knowledge Discovery in Databases, LNCS 6321. Berlin: Springer, 2010: 296-311.
[12] ROSEN P, POPESCU V. Simplification of node position data for interactive visualization of dynamic datasets [J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(9): 1537-1548.
[13] 彭艺,陈莉,雍俊海.大规模、时变数据的体绘制与特征追踪[J].计算机辅助设计与图形学学报,2013,25(11):1614-1622.(PENG Y, CHEN L, YONG J H. Large-scale time-varying data volume rendering and feature tracking [J]. Journal of Computer-Aided Design and Computer Graphics, 2013, 25(11):1614-1622. )
[14] DAI Q, SONG Y, XIN Y. Random-accessible volume data compression with regression function [C] // Proceeding of the 2015 14th International Conference on Computer-Aided Design and Computer Graphics. Piscataway, NJ: IEEE, 2015: 137-142.
[15] Duke University. Union-find algorithm [EB/OL]. [2015-10-26]. http://www.cs.duk.edu./courses/cps100e/fall09/notes/UnionFind.pdf.