马志强 李海生

摘要：

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

关键词：

KDtree剖分；并查集；刚体合并；时变数据集；动态数据压缩

中图分类号：

TP391.41

文献标志码：A

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 KDtree was presented. Firstly， the dynamic scene was divided by KDtree 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：

KDtree division； disjoint set； rigid body merging； timevarying dataset； dynamic data compression

0引言

随着网络时代的到来，以及移动计算平台计算能力的提升，三维虚拟场景远程可视化成为可视化技术发展的新趋势，它可以使网络上的数据资源得到更为合理有效的利用。但是观测和模拟所获取数据量的增长速度远大于网络带宽传输速度的增长，如何对这些数据进行快速有效压缩成为三维虚拟场景远程可视化面临的重大挑战。

基于三维动态场景顶点运动轨迹压缩的方法为解决上述问题提供了有效的解决途径。基于小波变化的动态数据压缩算法[1-3]在进行压缩时，首先使用小波基获取人体关节的旋转角随时间变化的数据集，然后删除对绘制的人体动态场景影响不大的小波系数，最终实现对一段时间间隔内人体时变数据的有效压缩。……