LI Haisheng, born in 1983, M. S., engineer. His research interests include computer graphics, real-time rendering
随着网络时代的到来，以及移动计算平台计算能力的提升，三维虚拟场景远程可视化成为可视化技术发展的新趋势，它可以使网络上的数据资源得到更为合理有效的利用。但是观测和模拟所获取数据量的增长速度远大于网络带宽传输速度的增长，如何对这些数据进行快速有效压缩成为三维虚拟场景远程可视化面临的重大挑战。
基于三维动态场景顶点运动轨迹压缩的方法为解决上述问题提供了有效的解决途径。基于小波变化的动态数据压缩算法[1-3]在进行压缩时，首先使用小波基获取人体关节的旋转角随时间变化的数据集，然后删除对绘制的人体动态场景影响不大的小波系数，最终实现对一段时间间隔内人体时变数据的有效压缩。傅里叶动态压缩算法[4]通过顶点周围点在上一帧和当前帧的空间位置，预测顶点的新空间位置，从而实现对随时间变化数据的压缩。许多随时间变化的动态数据的运动轨迹[5-8]可由方程进行表示，重构动态场景时通过方程计算顶点在运动中的空间位置。文献[9-12]不使用方程表示，实现三维动态场景中顶点运动轨迹的简单压缩。基于运动序列的压缩方法[9]提出将运动序列均匀分割，获得等长的单元运动序列，并使用Bezier曲线表示单元运动序列之间的时间联系性，实现对顶点运动轨迹的有效压缩。Lange等[10]和Vries等[11]等主要是将首尾的三维采样点连接成一条线，然后通过判断其他采样点到此线的距离和用户定义的阈值之间大小的比较，从而删除一些采样点。最后在重构运动轨迹时，通过线性插值的方法来恢复删除采样点。以上算法压缩速度都不快，且压缩比有待提高。Rosen等[12]提出一种时变数据集聚类压缩算法，采用暴力算法在所有的顶点中查找具有相似运动轨迹的顶点进行聚类压缩，能够获得较好的压缩效果传输给客户端，使得客户端用户可以从多角度对该场景进行高质量观察，但其压缩速度较慢。文献[13-14]提出依据重要度，并引入信息熵对动态体数据进行有效压缩，但压缩效率仍较低。
本文提出一种基于KD-tree剖分的快速有效压缩方法：使用KD-tree在第0帧对整个三维场景进行划分，对KD-tree的每个叶子节点进行刚体的并行构造，较大幅度提高了压缩速度。建立能构造刚体的叶子节点和均匀划分的三维网格之间的映射关系，使用并查集方法合并构造的刚体，实现三维动态场景的有效压缩，有效降低网络带宽的限制。
1 算法整体流程假定有在一段时间范围内(S帧)的三维动态场景，此动态场景包含w个顶点，还包含每个顶点在S帧内的三维空间位置以及顶点之间的三角连接关系。本文主要通过对顶点运动轨迹(顶点在整个S帧内的三维空间位置)进行压缩，从而达到压缩的目的。具体压缩思想为：将整个运动过程中具有相似运动轨迹的顶点聚为一类，称之为刚体。计算刚体所包含的顶点从第1到S-1帧相对于第0帧空间位置的运动矩阵，通过存储刚体运动矩阵来代替刚体所包含顶点在第1到S-1帧的空间位置，从而实现对顶点运动轨迹的压缩。为了提高压缩速度，本文提出使用KD-tree在第0帧剖分三维动态场景，对KD-tree的每个叶子节点进行刚体的并行构造，并使用并查集方法将构造后的刚体进行合并，有效提高压缩比，从而降低网络带宽的限制。
本文压缩算法的具体步骤为：
1) 基于KD-tree剖分的刚体并行构造：
①三维动态场景的KD-tree剖分；
②刚体的并行构造。
2) 基于并查集的刚体快速合并：
①映射关系的建立；
②基于并查集的刚体合并；
③剩余散点的压缩。
图 1给出本文基于KD-tree剖分的三维动态场景快速压缩算法的整体流程。以三维场景中所有模型顶点在S帧运动中的三维空间位置为输入，首先在第0帧对整个三维动态场景进行KD-tree剖分，并对剖分后包含大于三个顶点的叶子节点并行构造刚体得到小刚体(Small Rigid Body, SRB)；然后建立包含刚体的叶子节点和均匀划分的三维网格之间的映射关系，使用并查集将并行构造的小刚体快速合并得到刚体(Rigid Body, RB)，并将不能合并到刚体的顶点，即散点(Unassigned Vertex, UV)进行压缩，有效降低网络带宽的限制；最后将压缩后的数据包传输到客户端，解压并重构三维动态场景。
|
图 1 基于KD-tree剖分的三维动态场景压缩流程 |
为了实现刚体的快速构造，整体思路是在第0帧对三维场景进行KD-tree剖分，然后对包含三个顶点以上的叶子节点进行刚体的并行构造, 得到n个小刚体SRB。由于剖分后每个叶子节点所包含顶点数较少(用户定义不超过30个)，单个叶子节点构造刚体的速度较快；同时整体是基于CUDA的并行刚体构造，因此可实现整个三维动态场景所包含顶点运动轨迹的快速有效压缩。本文将刚体定义为一个三元组(V, P0，Q)：
V={v1, v2，…，vx}是刚体所包含的x个顶点的索引，其中x≥3；
P0={(a1, b1, c1)0，(a2, b2, c2)0，…，(ax, bx, cx)0}是刚体所包含的x个顶点在第0帧的三维空间位置；
Q={q1，q2，…，qS-1}是刚体在整个运动过程中从第1到S-1帧相对于第0帧空间位置的运动矩阵。
2.1 三维动态场景的KD-tree剖分基于KD-tree划分的刚体并行构造，首先是对整个三维动态场景在第0帧建立轴对齐包围盒(Axis Aligned Bounding Box, AABB)进行KD-tree剖分，直到每个叶子节点所包含顶点数目小于等于用户自定义阈值(一般是3至15的任一值)或达到划分深度。在图 2中以二维为例，介绍KD-tree剖分过程及结果。假定KD-tree剖分后，每个叶子节点所包含顶点个数不能超过3个，即剖分过程中一旦叶子节点所包含顶点个数小于等于3，则停止剖分。图 2(a)小圆圈点表示场景所含的顶点，图中数字表示第几次剖分。第1次剖分是分为上下两部分，由于上下所包含顶点个数大于3，因此进行第2次剖分。第2次剖分后，上下两部分的左侧所包含顶点个数小于等于3，因此不再进行剖分，而是对上下两部分的右侧进行第3次剖分。直到第5次剖分，满足每个叶子节点所包含顶点个数都小于等于3。图 2(b)是三维动态场景在第0帧进行KD-tree剖分后的叶子节点示意图。
|
图 2 三维动态场景第0帧的KD-tree剖分示意图 |
在第0帧对三维动态场景进行KD-tree剖分以后，由于叶子节点中小刚体的构造是相互不受影响的，因此可以对KD-tree剖分后的叶子节点进行基于通用并行计算架构(Compute Unified Device Architecture, CUDA)的刚体并行构造。图 2(b)中，叶子节点L6所包含的顶点个数小于3，因而此叶子节点不能进行刚体的构造，将其所包含顶点定义为散点(不能构造刚体也不能合并到刚体中的顶点)。
基于CUDA的刚体并行构造，对每个叶子节点，首先是构造包含三个顶点的初始刚体；如构造成功，将叶子节点中剩余的顶点向构造的初始刚体中合并，看是否能合并到初始刚体中；如初始刚体构造不成功，则此叶子节点所包含顶点均为散点。下面详细介绍单个叶子节点中小刚体的构造过程。
1) 初始小刚体的构造。
如图 3所示，假定KD-tree剖分后某个包含M(M≥3)个顶点的叶子节点，对于其包含的任意一顶点i，要找到满足条件的其他两个顶点j和k来构造初始小刚体，并计算初始小刚体的运动矩阵Q。
|
图 3 初始刚体构造示意图 |
对于顶点i, 算法首先找到另一个顶点j，保证i和j之间的距离在整个S帧内相对于初始帧的变化量一直小于用户设定的误差阈值ε，即基于刚体运动过程中不发生形变的性质，顶点i和j之间的距离在0帧到S-1帧几乎是不发生变化的。一旦找到第二个采样点j，算法寻找能最终构成一个刚体的第三个采样点k，保证i和k以及j和k之间的距离在S帧的变化量同样要一直小于用户设定的阈值ε，即保证k和i、 j之间的距离在第0帧到S-1帧几乎是不发生变化的。
构造初始刚体(i, j, k)后，求初始小刚体具体某一帧相对于第0帧的运动矩阵。具体如图 4：假定初始小刚体(i, j, k)在运动过程某一帧f时的空间位置为(a, b, c)，首先将顶点i移动到第f帧对应的空间位置a上，得到移动矩阵Q1；然后将三角形(i, j, k)的法线n1旋转到第f帧三角形(a, b, c)的法线位置n0，得到旋转矩阵Q2；最后将三角形(i, j, k)的边(i, j)旋转到(a, b)，得到旋转矩阵Q3。第f帧相对于第0帧的运动矩阵q f，即Q1、Q2和Q3的相乘，用式(1)表示为：
| ${\boldsymbol{q}^f} = {\boldsymbol{Q}_3} \times {\boldsymbol{Q}_2} \times {\boldsymbol{Q}_1}$ | (1) |
|
图 4 求解刚体运动矩阵步骤示意图 |
2) 合并叶子节点剩余顶点到初始小刚体。
当初始小刚体(i, j, k)构造成功后，要判断叶子节点中剩余顶点v是否能合并到此初始小刚体中。首先采用式(2)计算剩余顶点v在初始小刚体运动矩阵下的空间位置：
| $P_v^f = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {{{\left( {{x_v},{y_v},{z_v}} \right)}_0}}&{}&{\;\;f = 0} \end{array}\\ \begin{array}{*{20}{c}} {{\boldsymbol{q}^f} \times {{\left( {{x_v},{y_v}{z_v}} \right)}_0},}&{f > 0} \end{array} \end{array} \right.$ | (2) |
其中：(xv, yv, zv)0是顶点v在第0帧的空间位置，q f是初始小刚体在第f帧(0 < f < S)相对于第0帧的运动矩阵。
式(3)用于判断叶子节点中剩余顶点v是否能合并到此初始小刚体srb中，如果不能合并，则为散点。
| $srb \cup \left\{ v \right\} = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{ErrMax\left( {v,\boldsymbol{Q}} \right) \le \varepsilon } \end{array}\\ \begin{array}{*{20}{c}} {0,}&{ErrMax\left( {v,\boldsymbol{Q}} \right)} \end{array} > \varepsilon \end{array} \right.$ | (3) |
其中：ε是用户定义的误差阈值；Q是初始小刚体srb在整个运动过程S帧的运动矩阵；函数ErrMax()返回顶点v在srb运动矩阵Q下的空间位置和相应帧原有空间位置的最大绝对差值fabs()，由式(4)计算所得。
| $ErrMax\left( {v,{q^f}} \right) = \max \left( {{\rm{fabs}}\left( {P_v^f - P_v^{f'}} \right)} \right)$ | (4) |
其中：Pv f ′是顶点v在第f帧(0 < f < S－1)的原始空间位置。
图 5给出了三维动态场景在第0帧基于KD-tree剖分后并行构造刚体的效果图：图 5(a)是原始三维场景，图 5(b)中每一个小刚体用一种随机颜色来表示，不能构造刚体以及不能合并到刚体中的顶点(散点)用白色表示。如兔子耳朵上的顶点，由于兔子在和小球碰撞过程中变化比较剧烈，无法构造或合并到某个小刚体中，从而成为散点。
|
图 5 基于KD-tree剖分的刚体并行构造效果图 |
基于并查集方法将刚体进行快速合并的算法步骤为：由于KD-tree剖分后的刚体在非均匀三维空间中，不能使用并查集进行非均匀网格的刚体合并，因此首先建立非均匀网格的刚体叶子节点和在第0帧均匀划分的三维网格之间的映射关系；然后在均匀剖分的三维网格使用并查集实现均匀网格所映射刚体的快速合并，提高压缩比。刚体合并后，最后将剩余散点往已合并的刚体中合并，无法合并的散点进行运动轨迹的压缩，可以进一步提高压缩比。经过并查集快速合并刚体，并行构造的n个小刚体(SRB)可被合并成m个刚体(RB)。
3.1 均匀剖分网格和并行构造刚体映射关系建立建立均匀剖分的三维网格和能构造刚体的叶子节点之间的映射，其思路为：依次遍历每个叶子节点，如果是能构造刚体的叶子节点Li，则首先看其所含的第一个顶点所在三维网格Gi绑定的刚体叶子节点是否为空：
1) 如果为空，则建立映射关系。
2) 如果不为空，即三维网格Gi已经和某个刚体叶子节点Lj建立了映射关系，则将Li所包含刚体往Lj包含的刚体中合并；如能合并，则Lj刚体中增加Li刚体所包含的顶点；如果不能合并，则Lj所包含刚体顶点变为散点，以保证一个均匀网格只映射一个刚体。
图 6二维显示基于KD-tree剖分并行构造的刚体与均匀剖分网格之间映射关系的建立：左侧刚体叶子节点L1所包含的第一个顶点在中间均匀剖分的网格cell(1, 1)中，因此均匀网格cell(1, 1)所映射的刚体叶子节点为L1；同理，cell(1, 4)、cell(2, 3)、cell(3, 3)和cell(4, 3)分别映射刚体叶子节点L4、L5、L7和L8；刚体叶子节点L2和L3的第一顶点均在均匀网格cell(1, 3)中，因此都可映射到均匀网格cell(1, 3)。但一个均匀网格只允许映射一个刚体叶子节点，cell(1, 3)和L2建立映射关系后，判断L3所包含的刚体是否能合并到cell(1, 3)所映射的叶子节点L2所包含的刚体中：如能合并，则L2刚体中增加L3刚体所包含的顶点；如不能合并，则L3刚体所包含的顶点变为散点。式(2)和(3)判断一个顶点是否能合并到某一刚体中，如果判断一个刚体能合并到另一刚体，则要保证刚体所包含的所有顶点都能合并到另一刚体中。
|
图 6 基于KD-tree剖分并行构造的小刚体与均匀网格的映射 |
建立均匀剖分的三维网格和包含刚体的叶子节点之间的映射关系后，即可进行基于并查集[15]在均匀三维网格的刚体合并, 图 7显示了二维刚体的并查集合并。
|
图 7 基于并查集合并刚体示意图 |
图 7(a)是3.1节所建立的均匀网格和刚体叶子节点之间的映射关系。为方便理解，假定每个均匀网格都映射了一个并行构造后的刚体，即从刚体srb1到srb16。基于并查集在二维均匀网格合并刚体时，按照从左到右、从上到下的顺序进行遍历；而对每一个映射了刚体srbi的均匀网格，是向右向下进行查找，看其邻居网格所映射的srbj是否能和srbi进行合并。函数Merge()用于两个刚体之间的合并，式(2)到式(4)判断一个顶点是否能合并到某一刚体中，如判断能合并到另一刚体，则要保证刚体所包含的所有顶点都能合并到另一刚体，即如果判断刚体srbj能被合并到刚体srbi，是因为srbj所包含的所有顶点都能被合并到刚体srbi；合并后，srbi包含srbj的所有顶点。
图 7(a)中，首先将所有能映射刚体的网格的父节点定义为本身，然后进行基于并查集的刚体合并：从cell1开始遍历，向右向下看cell2的srb2和cell5的srb5是否能合并到cell1的srb1。首先看srb2，如Merge()返回true，则srb2合并到srb1，并依据并查集合并规则将cell1作为cell2的父节点(图 7(b)第1行左，父节点为圆圈1)；刚体srb5不能合并，则保留不动。继续遍历cell2，向右向下看cell3的srb3和cell6的srb6是否能合并到cell2的srb2，依据并查集的合并规则，判断是否能合并到cell2父节点中的刚体srb1。假定srb3合并到srb1，则将cell1作为cell3的父节点；srb6不能合并，继续保留(图 7(b)第1行右)。遍历到cell5，假定cell6的srb6和cell9的srb9能合并到srb5，则cell5成为cell6和cell9的父节点。遍历完所有均匀网格后，图 7(b)中所显示的树形第一层圆圈刚体即是基于并查集合并后的刚体。
定义每一个和刚体叶子节点建立映射关系的三维均匀网格cell(i, j, k)为一个四元组(srb, srbNodeNum, parentID, rank)。其中：srb是合并以后的刚体，其初始值为均匀网格所映射的刚体；srbNodeNum是一个常量，其值是均匀网格所映射刚体所包含的顶点个数；parentID是网格父节点的索引向量；rank是合并以后刚体srb所包含的顶点个数。
算法1用于三维动态场景基于并查集的刚体合并，整体按照从外到里、从左到右、从上到下的顺序进行遍历。首先初始化所有能映射刚体的三维网格的父节点parentID为其本身，并初始化网格所映射刚体srb的初始顶点个数rank为srbNodeNum。遍历时对每一个能映射刚体的三维网格向右、向下、向里看是否有能映射刚体的邻居进行刚体的合并。Save()函数将并查集合并后刚体存储到RB序列中并输出。
算法1 基于并查集的刚体合并。
输入：均匀划分的参数(I, J, K)，均匀网格cell(i, j, k)。
输出：合并后刚体RB。
//并查集搜索顺序
for each i in I do
for each j in J do
for each k in K do
Cell+={cell(i, j, k)}
end
end
end
//基于并查集的小刚体合并
for each cell(i, j, k) in Cell do
if cell(i, j, k).srb!=null then
cell(i, j, k).parentID=(i, j, k);
cell(i, j, k).rank=cell(i, j, k).srbNodeNum;
end
end
for each cell(i, j, k) in Cell do
if cell(i, j, k).srb!=null then
Union(cell(i, j, k), cell(i+1, j, k));
Union(cell(i, j, k), cell(i, j+1, k));
Union(cell(i, j, k), cell(i, j, k+1));
end
end
return Save(RBs, cell.srb)
刚体的合并函数Union()在算法2中进行定义。对于给定的两个映射刚体的均匀网格cell(i, j, k)和cell(x, y, z)，Union()首先判断两个均匀网格的父节点是否相同：如果相同，表明均匀网格映射的刚体已经进行了合并操作，不进行处理；如果不相同，则进行刚体的合并。刚体合并时，使用前面介绍的Merge()函数将含顶点个数少的刚体minrank_root向含顶点个数多的刚体maxrank_root合并：如果合并返回true，则刚体maxrank_root顶点包含minrank_root的顶点rank，并将minrank_root的顶点清零，其父节点变为maxrank_root的父节点。
算法2 相邻刚体的合并Union(cell(i, j, k), cell(x, y, z))。
输入：cell(i, j, k), cell(x, y, z)
输出：maxrank_root
(a1, b1, c1)=cell(i, j, k).parentID;
(a2, b2, c2)=cell(x, y, z).parentID;
root1=cell(a1, b1, c1);
root2=cell(a2, b2, c2);
if root1==root2 then
return
end
if cell(x, y, z).srb!=null then
minrank_root=minRank(root1, root2);
maxrank_root=maxRank(root1, root2);
if (maxrank_root.srb).Merge(minrank_root.srb) then
maxrank_root.rank=maxrank_root.rank+
minrank_root.rank;
minrank_root.rank=0;
minrank_root.parentID=maxrank_root.parentID;
end
end
return maxrank_root
基于并查集的合并方法，将具有运动一致性的小刚体合并，提高了动态数据压缩比。而且并查集合并的复杂度为O(1)，可实现并行构造的小刚体的快速合并。
图 8给出了三维动态场景基于并查集方法合并构造后刚体的效果图。与图 8(a)基于KD-tree剖分而进行刚体并行构造的效果相比，图 8(b)基于并查集方法合并后的刚体数目明显减少，则相应需要存储的运动矩阵数量变少，因此能够较好地提高动态数据的压缩比。
|
图 8 基于并查集合并刚体效果图 |
完成刚体的构造以及合并后，需要对剩余散点进行压缩，以进一步提高压缩比。散点压缩是使用式(2)和(3)将剩余散点向并查集合并后的刚体中合并，图 9给出了散点合并到刚体后的效果图。与图 9(a)未合并前相比，图 9(b)中兔子的耳朵和后背的一些散点(白色顶点)被合并到刚体中，提高了动态数据的压缩比。
|
图 9 合并散点到刚体的效果图 |
压缩后的动态数据传输到客户端以后，客户端要对数据进行解压缩，重构三维动态场景。客户端三维动态顶点的解压重构步骤如下：
1) 预计算所有三维动态顶点在整个运动过程中的三维空间位置(运动轨迹)。
对于压缩后的每一类复合刚体，由于存储其所包含顶点在第0帧的空间位置，以及生命周期内每一帧相对于第0帧空间位置的运动矩阵，两者相乘即可计算出复合刚体所包含顶点在其生命周期内的运动轨迹。重复以上步骤，计算所有复合刚体包含的顶点在相应生命周期内的运动轨迹，并与散的顶点的运动轨迹相结合，即可计算出所有动态顶点在整个运动过程中的三维空间位置。
2) 通过第一步计算出所有顶点的运动轨迹后，依据一同传输到客户端的顶点的颜色和连接关系，绘制三角面片即可重构三维动态场景。对于无连接关系的三维动态场景，通过计算出的顶点运动轨迹结合顶点的颜色即可重构三维动态场景。
本节在客户端解压并重构一段时间范围内的三维动态场景，由于重构的是三维动态场景包含的所有顶点在整个运动过程中的三维空间位置，与视点无关，因此无论客户端视点如何发生变化，重构三维动态场景时，服务器都不需要重新传输数据，从而减少了网络延迟的限制。
5 实验结果与分析本文算法的实验环境为Inter Core 2 3.0 GHz CPU、4 GB内存、NVIDIA GeForce GTX 260 1 GB显示卡、运行Windows XP操作系统的PC。实验程序基于OpenGL 3.0 API，Shader程序使用Shader Model 3.0方式编译。所用数据如表 1所示，其中场景大小是指在第0帧时三维场景轴对齐包围盒(Axis Aligned Bounding Box, AABB)的大小。
|
表 1 实验所用模型数据 |
本文使用一段时间范围内三种不同类型的三维动态数据来验证压缩算法的有效性：小球碰撞柔性固体兔子的运动数据、流体犰狳下落的运动数据以及流体水碰撞柔性固体碗的运动数据。三种动态场景的数据均由基于物理的方法计算所得，其中，柔性固体兔子和碗的动态数据由有限元方法计算所得，流体犰狳和水的动态模拟数据由平滑粒子动力学方法计算获取。
5.1 重构质量图 10、图 11、图 12分别给出了服务器端压缩后的动态数据传输到客户端解压重构的三维动态场景效果。图 10(a)、11(a)、12(a)为原始三维动态场景绘制效果，图 10(b)、11(b)、12(b)为能获得较好压缩结果的Rosen算法的重构效果，图 10(c)、11(c)、12(c)为本文算法的重构效果。小球碰撞动态柔性兔子、流体犰狳下落以及水碰撞柔性碗的动态场景在第0帧的包围盒AABB大小分别为10.0 m×9.8 m×14.3 m、9.9 m×8.3 m×7.5 m和6.7 m×6.4 m×10.5 m，最大顶点误差阈值ε为10 mm。从图 10~12可以看出，本文压缩算法和Rosen算法可以重构出与原始三维动态场景误差不大的效果，均可达到较好的重构效果。但相比Rosen算法，本文算法的整体误差要小，表 2给出了量化分析。
|
图 10 球碰兔子重构的动态场景同原动态场景对比 |
|
图 11 犰狳下落重构的动态场景同原动态场景对比 |
|
图 12 水流碰碗重构的动态场景同原动态场景对比 |
|
|
表 2 本文算法同Rosen算法顶点平均误差比较 |
表 2给出了不同误差阈值时本文算法同Rosen算法顶点平均误差的比较。场景误差中的相对误差是用户定义的误差阈值和相应场景AABB中最大数值的比值；平均误差是所有顶点在整个运动过程中的原始空间位置和重构空间位置之差的平均值；误差比值是本文算法同Rosen算法的平均误差比值。从表中可看出，本文算法的平均误差比Rosen的小，主要原因是由于对散的顶点的压缩。Rosen通过获取顶点在关键帧的空间位置，然后通过线性插值的方式重构顶点的运动轨迹。而本文算法通过存储散点的原始空间位置或使用其所在刚体的运动矩阵得到运动轨迹，从而减小了顶点三维空间位置的重构误差。但因此最后的压缩比，相比Rosen算法会稍微有点降低(表 3中压缩结果)。
|
|
表 3 本文算法同Rosen算法压缩性能比较 |
表 3给出了本文压缩算法和Rosen压缩算法在不同误差阈值时压缩比和压缩时间的比较。从表 3中可看出，针对同一场景，本文压缩算法相比Rosen算法在压缩比近似的情况下，可达到较快的压缩速度。压缩比会比Rosen算法稍微有所降低，是因为散点压缩，在针对表 2的平均误差中有解释。表 3中压缩时间的对比可以看出：针对同一场景，本文压缩算法达到较好压缩比的同时具有较快的压缩速度，最快是Rosen算法的74.2倍。压缩时间同顶点的邻接一致性有关，邻接一致性较好的动态变形模型顶点会导致小刚体SRB构造的几率提升，从而使得散点数量减少，有效提升压缩时间。
表 4给出了不同误差阈值时，本文压缩算法各步骤的压缩时间。从表中可看出：KD-tree剖分后基于CUDA的初始刚体的并行构造(SRB构造)、基于并查集的刚体快速合并(SRB合并)所用时间都较少，有效地提高了压缩速度。大量压缩时间都用在散点压缩上，由于兔子场景顶点邻接一致性较高，初始刚体构造数量多且合并也较好，从而使得最终场景散点数量少，压缩速度相比其他两个场景较快。
|
|
表 4 本文压缩算法的各步骤压缩时间 |
本文提出了一种基于KD-tree剖分的快速有效的压缩方法，通过刚体并行构造和基于并查集的刚体快速合并方法加速动态数据的压缩过程，避免刚体分解过程中的暴力搜索、比较以及合并，在保证客户端重构质量的同时，可以实现对三维动态场景的快速高效压缩，有效降低了网络带宽的限制。在客户端重构一定时间间隔内的三维动态场景，用户在任意角度观察三维动态场景时，不需要服务器端重新压缩并传输数据，从而有效减少了网络延迟的限制。但在压缩时未考虑顶点运动过程中的阶段一致性，动态数据的压缩比还有待提高，下一步将考虑刚体与刚体之间在某一帧或某几帧可以合并的阶段一致性，以进一步提高动态场景数据的压缩比。
| [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.
( 0)
|
| [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.
(0)
|
| [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.
(0)
|
| [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.
doi: 10.1109/TVCG.2008.69 (0)
|
| [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.
(0)
|
| [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.
doi: 10.1109/TVCG.2008.186 (0)
|
| [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.
doi: 10.1111/cgf.2009.28.issue-3 (0)
|
| [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.
doi: 10.1109/TVCG.2011.54 (0)
|
| [9] |
ARIKAN O. Compression of motion capture databases[J].
ACM Transactions on Graphics, 2006, 25 (3) : 890-897.
doi: 10.1145/1141911 (0)
|
| [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.
(0)
|
| [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.
(0)
|
| [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.
doi: 10.1109/TVCG.2011.268 (0)
|
| [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.
) (0)
|
| [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.
(0)
|
| [15] |
Duke University. Union-find algorithm [EB/OL]. [2015-10-26]. http://www.cs.duk.edu./courses/cps100e/fall09/notes/UnionFind.pdf.
(0)
|