基于KD瞭ree剖分的三維動(dòng)態(tài)場景快速有效壓縮

馬志強(qiáng) 李海生

摘要：

為充分利用GPU并行計(jì)算特點(diǎn)，實(shí)現(xiàn)對(duì)三維動(dòng)態(tài)數(shù)據(jù)的快速有效壓縮，降低網(wǎng)絡(luò)帶寬的限制，提出一種基于KDtree剖分的快速有效壓縮方法。首先使用KDtree在第0幀對(duì)整個(gè)三維場景進(jìn)行劃分，并對(duì)每個(gè)葉子節(jié)點(diǎn)進(jìn)行剛體的并行構(gòu)造；建立能構(gòu)造剛體的葉子節(jié)點(diǎn)和均勻劃分的三維網(wǎng)格之間的映射關(guān)系，在三維空間使用并查集合并并行構(gòu)造的剛體；最后將壓縮后的動(dòng)態(tài)數(shù)據(jù)傳輸?shù)娇蛻舳瞬⒅貥?gòu)一定時(shí)間內(nèi)的三維動(dòng)態(tài)場景。算法可以極大提高服務(wù)器端數(shù)據(jù)的壓縮速度，有效減少需要傳輸?shù)臄?shù)據(jù)量。實(shí)驗(yàn)結(jié)果表明：該算法在保證壓縮質(zhì)量的同時(shí)，可以對(duì)原始三維動(dòng)態(tài)場景進(jìn)行快速有效壓縮，有效降低網(wǎng)絡(luò)帶寬對(duì)數(shù)據(jù)傳輸?shù)南拗啤?/p>

關(guān)鍵詞：

KDtree剖分；并查集；剛體合并；時(shí)變數(shù)據(jù)集；動(dòng)態(tài)數(shù)據(jù)壓縮

中圖分類號(hào)：

TP391.41

文獻(xiàn)標(biāo)志碼：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.

英文關(guān)鍵詞Key words：

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

0引言

隨著網(wǎng)絡(luò)時(shí)代的到來，以及移動(dòng)計(jì)算平臺(tái)計(jì)算能力的提升，三維虛擬場景遠(yuǎn)程可視化成為可視化技術(shù)發(fā)展的新趨勢，它可以使網(wǎng)絡(luò)上的數(shù)據(jù)資源得到更為合理有效的利用。但是觀測和模擬所獲取數(shù)據(jù)量的增長速度遠(yuǎn)大于網(wǎng)絡(luò)帶寬傳輸速度的增長，如何對(duì)這些數(shù)據(jù)進(jìn)行快速有效壓縮成為三維虛擬場景遠(yuǎn)程可視化面臨的重大挑戰(zhàn)。

基于三維動(dòng)態(tài)場景頂點(diǎn)運(yùn)動(dòng)軌跡壓縮的方法為解決上述問題提供了有效的解決途徑。基于小波變化的動(dòng)態(tài)數(shù)據(jù)壓縮算法[1-3]在進(jìn)行壓縮時(shí)，首先使用小波基獲取人體關(guān)節(jié)的旋轉(zhuǎn)角隨時(shí)間變化的數(shù)據(jù)集，然后刪除對(duì)繪制的人體動(dòng)態(tài)場景影響不大的小波系數(shù)，最終實(shí)現(xiàn)對(duì)一段時(shí)間間隔內(nèi)人體時(shí)變數(shù)據(jù)的有效壓縮。傅里葉動(dòng)態(tài)壓縮算法[4]通過頂點(diǎn)周圍點(diǎn)在上一幀和當(dāng)前幀的空間位置，預(yù)測頂點(diǎn)的新空間位置，從而實(shí)現(xiàn)對(duì)隨時(shí)間變化數(shù)據(jù)的壓縮。許多隨時(shí)間變化的動(dòng)態(tài)數(shù)據(jù)的運(yùn)動(dòng)軌跡[5-8]可由方程進(jìn)行表示，重構(gòu)動(dòng)態(tài)場景時(shí)通過方程計(jì)算頂點(diǎn)在運(yùn)動(dòng)中的空間位置。文獻(xiàn)[9-12]不使用方程表示，實(shí)現(xiàn)三維動(dòng)態(tài)場景中頂點(diǎn)運(yùn)動(dòng)軌跡的簡單壓縮。基于運(yùn)動(dòng)序列的壓縮方法[9]提出將運(yùn)動(dòng)序列均勻分割，獲得等長的單元運(yùn)動(dòng)序列，并使用Bezier曲線表示單元運(yùn)動(dòng)序列之間的時(shí)間聯(lián)系性，實(shí)現(xiàn)對(duì)頂點(diǎn)運(yùn)動(dòng)軌跡的有效壓縮。Lange等[10]和Vries等[11]等主要是將首尾的三維采樣點(diǎn)連接成一條線，然后通過判斷其他采樣點(diǎn)到此線的距離和用戶定義的閾值之間大小的比較，從而刪除一些采樣點(diǎn)。最后在重構(gòu)運(yùn)動(dòng)軌跡時(shí)，通過線性插值的方法來恢復(fù)刪除采樣點(diǎn)。以上算法壓縮速度都不快，且壓縮比有待提高。Rosen等[12]提出一種時(shí)變數(shù)據(jù)集聚類壓縮算法，采用暴力算法在所有的頂點(diǎn)中查找具有相似運(yùn)動(dòng)軌跡的頂點(diǎn)進(jìn)行聚類壓縮，能夠獲得較好的壓縮效果傳輸給客戶端，使得客戶端用戶可以從多角度對(duì)該場景進(jìn)行高質(zhì)量觀察，但其壓縮速度較慢。文獻(xiàn)[13-14]提出依據(jù)重要度，并引入信息熵對(duì)動(dòng)態(tài)體數(shù)據(jù)進(jìn)行有效壓縮，但壓縮效率仍較低。

本文提出一種基于KDtree剖分的快速有效壓縮方法：使用KDtree在第0幀對(duì)整個(gè)三維場景進(jìn)行劃分，對(duì)KDtree的每個(gè)葉子節(jié)點(diǎn)進(jìn)行剛體的并行構(gòu)造，較大幅度提高了壓縮速度。建立能構(gòu)造剛體的葉子節(jié)點(diǎn)和均勻劃分的三維網(wǎng)格之間的映射關(guān)系，使用并查集方法合并構(gòu)造的剛體，實(shí)現(xiàn)三維動(dòng)態(tài)場景的有效壓縮，有效降低網(wǎng)絡(luò)帶寬的限制。

1算法整體流程

假定有在一段時(shí)間范圍內(nèi)（S幀）的三維動(dòng)態(tài)場景，此動(dòng)態(tài)場景包含w個(gè)頂點(diǎn)，還包含每個(gè)頂點(diǎn)在S幀內(nèi)的三維空間位置以及頂點(diǎn)之間的三角連接關(guān)系。本文主要通過對(duì)頂點(diǎn)運(yùn)動(dòng)軌跡（頂點(diǎn)在整個(gè)S幀內(nèi)的三維空間位置）進(jìn)行壓縮，從而達(dá)到壓縮的目的。具體壓縮思想為：將整個(gè)運(yùn)動(dòng)過程中具有相似運(yùn)動(dòng)軌跡的頂點(diǎn)聚為一類，稱之為剛體。計(jì)算剛體所包含的頂點(diǎn)從第1到S-1幀相對(duì)于第0幀空間位置的運(yùn)動(dòng)矩陣，通過存儲(chǔ)剛體運(yùn)動(dòng)矩陣來代替剛體所包含頂點(diǎn)在第1到S-1幀的空間位置，從而實(shí)現(xiàn)對(duì)頂點(diǎn)運(yùn)動(dòng)軌跡的壓縮。為了提高壓縮速度，本文提出使用KDtree在第0幀剖分三維動(dòng)態(tài)場景，對(duì)KDtree的每個(gè)葉子節(jié)點(diǎn)進(jìn)行剛體的并行構(gòu)造，并使用并查集方法將構(gòu)造后的剛體進(jìn)行合并，有效提高壓縮比，從而降低網(wǎng)絡(luò)帶寬的限制。

本文壓縮算法的具體步驟為：

1）基于KDtree剖分的剛體并行構(gòu)造：

①三維動(dòng)態(tài)場景的KDtree剖分；

②剛體的并行構(gòu)造。

2）基于并查集的剛體快速合并：

①映射關(guān)系的建立；

②基于并查集的剛體合并；

③剩余散點(diǎn)的壓縮。

圖1給出本文基于KDtree剖分的三維動(dòng)態(tài)場景快速壓縮算法的整體流程。以三維場景中所有模型頂點(diǎn)在S幀運(yùn)動(dòng)中的三維空間位置為輸入，首先在第0幀對(duì)整個(gè)三維動(dòng)態(tài)場景進(jìn)行KDtree剖分，并對(duì)剖分后包含大于三個(gè)頂點(diǎn)的葉子節(jié)點(diǎn)并行構(gòu)造剛體得到小剛體（Small Rigid Body， SRB）；然后建立包含剛體的葉子節(jié)點(diǎn)和均勻劃分的三維網(wǎng)格之間的映射關(guān)系，使用并查集將并行構(gòu)造的小剛體快速合并得到剛體（Rigid Body， RB），并將不能合并到剛體的頂點(diǎn)，即散點(diǎn)（Unassigned Vertex， UV）進(jìn)行壓縮，有效降低網(wǎng)絡(luò)帶寬的限制；最后將壓縮后的數(shù)據(jù)包傳輸?shù)娇蛻舳耍鈮翰⒅貥?gòu)三維動(dòng)態(tài)場景。

2基于KDtree剖分的剛體并行構(gòu)造

為了實(shí)現(xiàn)剛體的快速構(gòu)造，整體思路是在第0幀對(duì)三維場景進(jìn)行KDtree剖分，然后對(duì)包含三個(gè)頂點(diǎn)以上的葉子節(jié)點(diǎn)進(jìn)行剛體的并行構(gòu)造， 得到n個(gè)小剛體SRB。由于剖分后每個(gè)葉子節(jié)點(diǎn)所包含頂點(diǎn)數(shù)較少（用戶定義不超過30個(gè)），單個(gè)葉子節(jié)點(diǎn)構(gòu)造剛體的速度較快；同時(shí)整體是基于CUDA的并行剛體構(gòu)造，因此可實(shí)現(xiàn)整個(gè)三維動(dòng)態(tài)場景所包含頂點(diǎn)運(yùn)動(dòng)軌

跡的快速有效壓縮。本文將剛體定義為一個(gè)三元組（V， P0，Q）：

V={v1， v2，…，vx}是剛體所包含的x個(gè)頂點(diǎn)的索引，其中x≥3；

P0={（a1，b1，c1）0，（a2，b2，c2）0，…，（ax，bx，cx）0} 是剛體所包含的x個(gè)頂點(diǎn)在第0幀的三維空間位置；

Q={q1，q2，…，qS-1}是剛體在整個(gè)運(yùn)動(dòng)過程中從第1到S-1幀相對(duì)于第0幀空間位置的運(yùn)動(dòng)矩陣。

2.1三維動(dòng)態(tài)場景的KDtree剖分

基于KDtree劃分的剛體并行構(gòu)造，首先是對(duì)整個(gè)三維動(dòng)態(tài)場景在第0幀建立軸對(duì)齊包圍盒（Axis Aligned Bounding Box， AABB）進(jìn)行KDtree剖分，直到每個(gè)葉子節(jié)點(diǎn)所包含頂點(diǎn)數(shù)目小于等于用戶自定義閾值（一般是3至15的任一值）或達(dá)到劃分深度。在圖2中以二維為例，介紹KDtree剖分過程及結(jié)果。假定KDtree剖分后，每個(gè)葉子節(jié)點(diǎn)所包含頂點(diǎn)個(gè)數(shù)不能超過3個(gè)，即剖分過程中一旦葉子節(jié)點(diǎn)所包含頂點(diǎn)個(gè)數(shù)小于等于3，則停止剖分。圖2（a）小圓圈點(diǎn)表示場景所含的頂點(diǎn)，圖中數(shù)字表示第幾次剖分。第1次剖分是分為上下兩部分，由于上下所包含頂點(diǎn)個(gè)數(shù)大于3，因此進(jìn)行第2次剖分。第2次剖分后，上下兩部分的左側(cè)所包含頂點(diǎn)個(gè)數(shù)小于等于3，因此不再進(jìn)行剖分，而是對(duì)上下兩部分的右側(cè)進(jìn)行第3次剖分。直到第5次剖分，滿足每個(gè)葉子節(jié)點(diǎn)所包含頂點(diǎn)個(gè)數(shù)都小于等于3。圖2（b）是三維動(dòng)態(tài)場景在第0幀進(jìn)行KDtree剖分后的葉子節(jié)點(diǎn)示意圖。

2.2剛體的并行構(gòu)造

在第0幀對(duì)三維動(dòng)態(tài)場景進(jìn)行KDtree剖分以后，由于葉子節(jié)點(diǎn)中小剛體的構(gòu)造是相互不受影響的，因此可以對(duì)KDtree剖分后的葉子節(jié)點(diǎn)進(jìn)行基于通用并行計(jì)算架構(gòu)（Compute Unified Device Architecture， CUDA）的剛體并行構(gòu)

造。圖2（b）中，葉子節(jié)點(diǎn)L6所包含的頂點(diǎn)個(gè)數(shù)小于3，因而此葉子節(jié)點(diǎn)不能進(jìn)行剛體的構(gòu)造，將其所包含頂點(diǎn)定義為散點(diǎn)（不能構(gòu)造剛體也不能合并到剛體中的頂點(diǎn)）。

基于CUDA的剛體并行構(gòu)造，對(duì)每個(gè)葉子節(jié)點(diǎn)，首先是構(gòu)造包含三個(gè)頂點(diǎn)的初始剛體；如構(gòu)造成功，將葉子節(jié)點(diǎn)中剩余的頂點(diǎn)向構(gòu)造的初始剛體中合并，看是否能合并到初始剛體中；如初始剛體構(gòu)造不成功，則此葉子節(jié)點(diǎn)所包含頂點(diǎn)均為散點(diǎn)。下面詳細(xì)介紹單個(gè)葉子節(jié)點(diǎn)中小剛體的構(gòu)造過程。

1）初始小剛體的構(gòu)造。

如圖3所示，假定KDtree剖分后某個(gè)包含M（M≥3）個(gè)頂點(diǎn)的葉子節(jié)點(diǎn)，對(duì)于其包含的任意一頂點(diǎn)i，要找到滿足條件的其他兩個(gè)頂點(diǎn)j和k來構(gòu)造初始小剛體，并計(jì)算初始小剛體的運(yùn)動(dòng)矩陣Q。

對(duì)于頂點(diǎn)i， 算法首先找到另一個(gè)頂點(diǎn)j，保證i和j之間的距離在整個(gè)S幀內(nèi)相對(duì)于初始幀的變化量一直小于用戶設(shè)定的誤差閾值ε，即基于剛體運(yùn)動(dòng)過程中不發(fā)生形變的性質(zhì)，頂點(diǎn)i和j之間的距離在0幀到S-1幀幾乎是不發(fā)生變化的。一旦找到第二個(gè)采樣點(diǎn)j，算法尋找能最終構(gòu)成一個(gè)剛體的第三個(gè)采樣點(diǎn)k，保證i和k以及j和k之間的距離在S幀的變化量同樣要一直小于用戶設(shè)定的閾值ε，即保證k和i、 j之間的距離在第0幀到S-1幀幾乎是不發(fā)生變化的。

構(gòu)造初始剛體（i， j，k）后，求初始小剛體具體某一幀相對(duì)于第0幀的運(yùn)動(dòng)矩陣。具體如圖4：假定初始小剛體（i， j，k）在運(yùn)動(dòng)過程某一幀f時(shí)的空間位置為（a，b，c），首先將頂點(diǎn)i移動(dòng)到第f幀對(duì)應(yīng)的空間位置a上，得到移動(dòng)矩陣Q1；然后將三角形（i， j，k）的法線n1旋轉(zhuǎn)到第f幀三角形（a，b，c）的法線位置n0，得到旋轉(zhuǎn)矩陣Q2；最后將三角形（i， j，k）的邊（i， j）旋轉(zhuǎn)到（a，b），得到旋轉(zhuǎn)矩陣Q3。第f幀相對(duì)于第0幀的運(yùn)動(dòng)矩陣qf，即Q1、Q2和Q3的相乘，用式（1）表示為：

qf=Q3×Q2×Q1（1）

2）合并葉子節(jié)點(diǎn)剩余頂點(diǎn)到初始小剛體。

當(dāng)初始小剛體（i， j，k）構(gòu)造成功后，要判斷葉子節(jié)點(diǎn)中剩余頂點(diǎn)v是否能合并到此初始小剛體中。首先采用式（2）計(jì)算剩余頂點(diǎn)v在初始小剛體運(yùn)動(dòng)矩陣下的空間位置：

Pfv=（xv，yv，zv）0，f=0

qf×（xv，yv，zv）0，f>0（2）

其中：（xv，yv，zv）0是頂點(diǎn)v在第0幀的空間位置，qf是初始小剛體在第f幀（0

式（3）用于判斷葉子節(jié)點(diǎn)中剩余頂點(diǎn)v是否能合并到此初始小剛體srb中，如果不能合并，則為散點(diǎn)。

srb∪{v}=1，ErrMax（v，Q）≤ε

0，ErrMax（v，Q）>ε（3）

其中：ε是用戶定義的誤差閾值；Q是初始小剛體srb在整個(gè)運(yùn)動(dòng)過程S幀的運(yùn)動(dòng)矩陣；函數(shù)ErrMax（ ）返回頂點(diǎn)v在srb運(yùn)動(dòng)矩陣Q下的空間位置和相應(yīng)幀原有空間位置的最大絕對(duì)差值fabs（），由式（4）計(jì)算所得。

ErrMax（v，qf）=max（fabs（Pfv-Pf′v））（4）

其中：Pf′v是頂點(diǎn)v在第f幀（0

圖5給出了三維動(dòng)態(tài)場景在第0幀基于KDtree剖分后并行構(gòu)造剛體的效果圖：圖5（a）是原始三維場景，圖5（b）中每一個(gè)小剛體用一種隨機(jī)顏色來表示，不能構(gòu)造剛體以及不能合并到剛體中的頂點(diǎn)（散點(diǎn)）用白色表示。如兔子耳朵上的頂點(diǎn)，由于兔子在和小球碰撞過程中變化比較劇烈，無法構(gòu)造或合并到某個(gè)小剛體中，從而成為散點(diǎn)。

3基于并查集的剛體快速合并

基于并查集方法將剛體進(jìn)行快速合并的算法步驟為：由于KDtree剖分后的剛體在非均勻三維空間中，不能使用并查集進(jìn)行非均勻網(wǎng)格的剛體合并，因此首先建立非均勻網(wǎng)格的剛體葉子節(jié)點(diǎn)和在第0幀均勻劃分的三維網(wǎng)格之間的映射關(guān)系；然后在均勻剖分的三維網(wǎng)格使用并查集實(shí)現(xiàn)均勻網(wǎng)格所映射剛體的快速合并，提高壓縮比。剛體合并后，最后將剩余散點(diǎn)往已合并的剛體中合并，無法合并的散點(diǎn)進(jìn)行運(yùn)動(dòng)軌跡的壓縮，可以進(jìn)一步提高壓縮比。經(jīng)過并查集快速合并剛體，并行構(gòu)造的n個(gè)小剛體（SRB）可被合并成m個(gè)剛體（RB）。

3.1均勻剖分網(wǎng)格和并行構(gòu)造剛體映射關(guān)系建立

建立均勻剖分的三維網(wǎng)格和能構(gòu)造剛體的葉子節(jié)點(diǎn)之間的映射，其思路為：依次遍歷每個(gè)葉子節(jié)點(diǎn)，如果是能構(gòu)造剛體的葉子節(jié)點(diǎn)Li，則首先看其所含的第一個(gè)頂點(diǎn)所在三維網(wǎng)格Gi綁定的剛體葉子節(jié)點(diǎn)是否為空：

1）如果為空，則建立映射關(guān)系。

2）如果不為空，即三維網(wǎng)格Gi已經(jīng)和某個(gè)剛體葉子節(jié)點(diǎn)Lj建立了映射關(guān)系，則將Li所包含剛體往Lj包含的剛體中合并；如能合并，則Lj剛體中增加Li剛體所包含的頂點(diǎn)；如果不能合并，則Lj所包含剛體頂點(diǎn)變?yōu)樯Ⅻc(diǎn)，以保證一個(gè)均勻網(wǎng)格只映射一個(gè)剛體。

圖6二維顯示基于KDtree剖分并行構(gòu)造的剛體與均勻剖分網(wǎng)格之間映射關(guān)系的建立：左側(cè)剛體葉子節(jié)點(diǎn)L1所包含的第一個(gè)頂點(diǎn)在中間均勻剖分的網(wǎng)格cell（1，1）中，因此均勻網(wǎng)格cell（1，1）所映射的剛體葉子節(jié)點(diǎn)為L1；同理，cell（1，4）、cell（2，3）、cell（3，3）和cell（4，3）分別映射剛體葉子節(jié)點(diǎn)L4、L5、L7和L8；剛體葉子節(jié)點(diǎn)L2和L3的第一頂點(diǎn)均在均勻網(wǎng)格cell（1，3）中，因此都可映射到均勻網(wǎng)格cell（1，3）。但一個(gè)均勻網(wǎng)格只允許映射一個(gè)剛體葉子節(jié)點(diǎn)，cell（1，3）和L2建立映射關(guān)系后，判斷L3所包含的剛體是否能合并到cell（1，3）所映射的葉子節(jié)點(diǎn)L2所包含的剛體中：如能合并，則L2剛體中增加L3剛體所包含的頂點(diǎn)；如不能合并，則L3剛體所包含的頂點(diǎn)變?yōu)樯Ⅻc(diǎn)。式（2）和（3）判斷一個(gè)頂點(diǎn)是否能合并到某一剛體中，如果判斷一個(gè)剛體能合并到另一剛體，則要保證剛體所包含的所有頂點(diǎn)都能合并到另一剛體中。

圖6建立基于KDtree剖分并行構(gòu)造的小剛體與均勻網(wǎng)格之間的映射關(guān)系基于KDtree剖分并行構(gòu)造的小剛體與均勻網(wǎng)格的映射

3.2基于并查集的剛體合并

建立均勻剖分的三維網(wǎng)格和包含剛體的葉子節(jié)點(diǎn)之間的映射關(guān)系后，即可進(jìn)行基于并查集[15]在均勻三維網(wǎng)格的剛體合并， 圖7顯示了二維剛體的并查集合并。

圖7（a）是3.1節(jié)所建立的均勻網(wǎng)格和剛體葉子節(jié)點(diǎn)之間的映射關(guān)系。為方便理解，假定每個(gè)均勻網(wǎng)格都映射了一個(gè)并行構(gòu)造后的剛體，即從剛體srb1到srb16。基于并查集在二維均勻網(wǎng)格合并剛體時(shí)，按照從左到右、從上到下的順序進(jìn)行遍歷；而對(duì)每一個(gè)映射了剛體srbi的均勻網(wǎng)格，是向右向下進(jìn)行查找，看其鄰居網(wǎng)格所映射的srbj是否能和srbi進(jìn)行合并。函數(shù)Merge（）用于兩個(gè)剛體之間的合并，式（2）到式（4）判斷一個(gè)頂點(diǎn)是否能合并到某一剛體中，如判斷能合并到另一剛體，則要保證剛體所包含的所有頂點(diǎn)都能合并到另一剛體，即如果判斷剛體srbj能被合并到剛體srbi，是因?yàn)閟rbj所包含的所有頂點(diǎn)都能被合并到剛體srbi；合并后，srbi包含srbj的所有頂點(diǎn)。

圖7（a）中，首先將所有能映射剛體的網(wǎng)格的父節(jié)點(diǎn)定義為本身，然后進(jìn)行基于并查集的剛體合并：從cell1開始遍歷，向右向下看cell2的srb2和cell5的srb5是否能合并到cell1的srb1。首先看srb2，如Merge（）返回true，則srb2合并到srb1，并依據(jù)并查集合并規(guī)則將cell1作為cell2的父節(jié)點(diǎn)（圖7（b）第1行左，父節(jié)點(diǎn)為圓圈1）；剛體srb5不能合并，則保留不動(dòng)。繼續(xù)遍歷cell2，向右向下看cell3的srb3和cell6的srb6是否能合并到cell2的srb2，依據(jù)并查集的合并規(guī)則，判斷是否能合并到cell2父節(jié)點(diǎn)中的剛體srb1。假定srb3合并到srb1，則將cell1作為cell3的父節(jié)點(diǎn)；srb6不能合并，繼續(xù)保留（圖7（b）第1行右）。遍歷到cell5，假定cell6的srb6和cell9的srb9能合并到srb5，則cell5成為cell6和cell9的父節(jié)點(diǎn)。遍歷完所有均勻網(wǎng)格后，圖7（b）中所顯示的樹形第一層圓圈剛體即是基于并查集合并后的剛體。

定義每一個(gè)和剛體葉子節(jié)點(diǎn)建立映射關(guān)系的三維均勻網(wǎng)格cell（i， j，k）為一個(gè)四元組（srb， srbNodeNum， parentID， rank）。其中：srb是合并以后的剛體，其初始值為均勻網(wǎng)格所映射的剛體；srbNodeNum是一個(gè)常量，其值是均勻網(wǎng)格所映射剛體所包含的頂點(diǎn)個(gè)數(shù)；parentID是網(wǎng)格父節(jié)點(diǎn)的索引向量；rank是合并以后剛體srb所包含的頂點(diǎn)個(gè)數(shù)。

算法1用于三維動(dòng)態(tài)場景基于并查集的剛體合并，整體按照從外到里、從左到右、從上到下的順序進(jìn)行遍歷。首先初始化所有能映射剛體的三維網(wǎng)格的父節(jié)點(diǎn)parentID為其本身，并初始化網(wǎng)格所映射剛體srb的初始頂點(diǎn)個(gè)數(shù)rank為srbNodeNum。遍歷時(shí)對(duì)每一個(gè)能映射剛體的三維網(wǎng)格向右、向下、向里看是否有能映射剛體的鄰居進(jìn)行剛體的合并。Save（）函數(shù)將并查集合并后剛體存儲(chǔ)到RB序列中并輸出。

剛體的合并函數(shù)Union（）在算法2中進(jìn)行定義。對(duì)于給定的兩個(gè)映射剛體的均勻網(wǎng)格cell（i， j，k）和cell（x，y，z），Union（）首先判斷兩個(gè)均勻網(wǎng)格的父節(jié)點(diǎn)是否相同：如果相同，表明均勻網(wǎng)格映射的剛體已經(jīng)進(jìn)行了合并操作，不進(jìn)行處理；如果不相同，則進(jìn)行剛體的合并。剛體合并時(shí)，使用前面介紹的Merge（）函數(shù)將含頂點(diǎn)個(gè)數(shù)少的剛體minrank_root向含頂點(diǎn)個(gè)數(shù)多的剛體maxrank_root合并：如果合并返回true，則剛體maxrank_root頂點(diǎn)包含minrank_root的頂點(diǎn)rank，并將minrank_root的頂點(diǎn)清零，其父節(jié)點(diǎn)變?yōu)閙axrank_root的父節(jié)點(diǎn)。

算法2相鄰剛體的合并 Union（cell（i， j，k），cell（x，y，z））。

程序前

基于并查集的合并方法，將具有運(yùn)動(dòng)一致性的小剛體合并，提高了動(dòng)態(tài)數(shù)據(jù)壓縮比。而且并查集合并的復(fù)雜度為O（1），可實(shí)現(xiàn)并行構(gòu)造的小剛體的快速合并。

圖8給出了三維動(dòng)態(tài)場景基于并查集方法合并構(gòu)造后剛體的效果圖。與圖8（a）基于KDtree剖分而進(jìn)行剛體并行構(gòu)造的效果相比，圖8（b）基于并查集方法合并后的剛體數(shù)目明顯減少，則相應(yīng)需要存儲(chǔ)的運(yùn)動(dòng)矩陣數(shù)量變少，因此能夠較好地提高動(dòng)態(tài)數(shù)據(jù)的壓縮比。

3.3剩余散點(diǎn)的壓縮

完成剛體的構(gòu)造以及合并后，需要對(duì)剩余散點(diǎn)進(jìn)行壓縮，以進(jìn)一步提高壓縮比。散點(diǎn)壓縮是使用式（2）和（3）將剩余散點(diǎn)向并查集合并后的剛體中合并，圖9給出了散點(diǎn)合并到剛體后的效果圖。與圖9（a）未合并前相比，圖9（b）中兔子的耳朵和后背的一些散點(diǎn)（白色頂點(diǎn)）被合并到剛體中，提高了動(dòng)態(tài)數(shù)據(jù)的壓縮比。

4客戶端三維動(dòng)態(tài)場景的重構(gòu)

壓縮后的動(dòng)態(tài)數(shù)據(jù)傳輸?shù)娇蛻舳艘院螅蛻舳艘獙?duì)數(shù)據(jù)進(jìn)行解壓縮，重構(gòu)三維動(dòng)態(tài)場景。客戶端三維動(dòng)態(tài)頂點(diǎn)的解壓重構(gòu)步驟如下：

1）預(yù)計(jì)算所有三維動(dòng)態(tài)頂點(diǎn)在整個(gè)運(yùn)動(dòng)過程中的三維空間位置（運(yùn)動(dòng)軌跡）。

對(duì)于壓縮后的每一類復(fù)合剛體，由于存儲(chǔ)其所包含頂點(diǎn)在第0幀的空間位置，以及生命周期內(nèi)每一幀相對(duì)于第0幀空間位置的運(yùn)動(dòng)矩陣，兩者相乘即可計(jì)算出復(fù)合剛體所包含頂點(diǎn)在其生命周期內(nèi)的運(yùn)動(dòng)軌跡。重復(fù)以上步驟，計(jì)算所有復(fù)合剛體包含的頂點(diǎn)在相應(yīng)生命周期內(nèi)的運(yùn)動(dòng)軌跡，并與散的頂點(diǎn)的運(yùn)動(dòng)軌跡相結(jié)合，即可計(jì)算出所有動(dòng)態(tài)頂點(diǎn)在整個(gè)運(yùn)動(dòng)過程中的三維空間位置。

2）通過第一步計(jì)算出所有頂點(diǎn)的運(yùn)動(dòng)軌跡后，依據(jù)一同傳輸?shù)娇蛻舳说捻旤c(diǎn)的顏色和連接關(guān)系，繪制三角面片即可重構(gòu)三維動(dòng)態(tài)場景。對(duì)于無連接關(guān)系的三維動(dòng)態(tài)場景，通過計(jì)算出的頂點(diǎn)運(yùn)動(dòng)軌跡結(jié)合頂點(diǎn)的顏色即可重構(gòu)三維動(dòng)態(tài)場景。

本節(jié)在客戶端解壓并重構(gòu)一段時(shí)間范圍內(nèi)的三維動(dòng)態(tài)場景，由于重構(gòu)的是三維動(dòng)態(tài)場景包含的所有頂點(diǎn)在整個(gè)運(yùn)動(dòng)過程中的三維空間位置，與視點(diǎn)無關(guān)，因此無論客戶端視點(diǎn)如何發(fā)生變化，重構(gòu)三維動(dòng)態(tài)場景時(shí)，服務(wù)器都不需要重新傳輸數(shù)據(jù)，從而減少了網(wǎng)絡(luò)延遲的限制。

5實(shí)驗(yàn)結(jié)果與分析

本文算法的實(shí)驗(yàn)環(huán)境為Inter Core 2 3.0GHz CPU、4GB內(nèi)存、NVIDIA GeForce GTX 260 1GB顯示卡、運(yùn)行Windows XP操作系統(tǒng)的PC。實(shí)驗(yàn)程序基于OpenGL 3.0 API，Shader程序使用Shader Model 3.0方式編譯。所用數(shù)據(jù)如表1所示，其中場景大小是指在第0幀時(shí)三維場景軸對(duì)齊包圍盒（Axis Aligned Bounding Box， AABB）的大小。

本文使用一段時(shí)間范圍內(nèi)三種不同類型的三維動(dòng)態(tài)數(shù)據(jù)來驗(yàn)證壓縮算法的有效性：小球碰撞柔性固體兔子的運(yùn)動(dòng)數(shù)據(jù)、流體犰狳下落的運(yùn)動(dòng)數(shù)據(jù)以及流體水碰撞柔性固體碗的運(yùn)動(dòng)數(shù)據(jù)。三種動(dòng)態(tài)場景的數(shù)據(jù)均由基于物理的方法計(jì)算所得，其中，柔性固體兔子和碗的動(dòng)態(tài)數(shù)據(jù)由有限元方法計(jì)算所得，流體犰狳和水的動(dòng)態(tài)模擬數(shù)據(jù)由平滑粒子動(dòng)力學(xué)方法計(jì)算獲取。

5.1重構(gòu)質(zhì)量

圖10、圖11、圖12分別給出了服務(wù)器端壓縮后的動(dòng)態(tài)數(shù)據(jù)傳輸?shù)娇蛻舳私鈮褐貥?gòu)的三維動(dòng)態(tài)場景效果。圖10（a）、11（a）、12（a）為原始三維動(dòng)態(tài)場景繪制效果，圖10（b）、11（b）、12（b）為能獲得較好壓縮結(jié)果的Rosen算法的重構(gòu)效果，圖10（c）、11（c）、12（c）為本文算法的重構(gòu)效果。小球碰撞動(dòng)態(tài)柔性兔子、流體犰狳下落以及水碰撞柔性碗的動(dòng)態(tài)場景在第0幀的包圍盒AABB大小分別為10.0m×9.8m×14.3m、9.9m×8.3m×7.5m和6.7m×6.4m×10.5m，最大頂點(diǎn)誤差閾值ε為10mm。從圖10～12可以看出，本文壓縮算法和Rosen算法可以重構(gòu)出與原始三維動(dòng)態(tài)場景誤差不大的效果，均可達(dá)到較好的重構(gòu)效果。但相比Rosen 算法，本文算法的整體誤差要小，表2給出了量化分析。

表2給出了不同誤差閾值時(shí)本文算法同Rosen算法頂點(diǎn)平均誤差的比較。場景誤差中的相對(duì)誤差是用戶定義的誤差閾值和相應(yīng)場景AABB中最大數(shù)值的比值；平均誤差是所有頂點(diǎn)在整個(gè)運(yùn)動(dòng)過程中的原始空間位置和重構(gòu)空間位置之差的平均值；誤差比值是本文算法同Rosen算法的平均誤差比值。從表中可看出，本文算法的平均誤差比Rosen的小，主要原因是由于對(duì)散的頂點(diǎn)的壓縮。Rosen通過獲取頂點(diǎn)在關(guān)鍵幀的空間位置，然后通過線性插值的方式重構(gòu)頂點(diǎn)的運(yùn)動(dòng)軌跡。而本文算法通過存儲(chǔ)散點(diǎn)的原始空間位置或使用其所在剛體的運(yùn)動(dòng)矩陣得到運(yùn)動(dòng)軌跡，從而減小了頂點(diǎn)三維空間位置的重構(gòu)誤差。但因此最后的壓縮比，相比Rosen算法會(huì)稍微有點(diǎn)降低（表3中壓縮結(jié)果）。

5.2壓縮效率

表3給出了本文壓縮算法和Rosen壓縮算法在不同誤差閾值時(shí)壓縮比和壓縮時(shí)間的比較。從表3中可看出，針對(duì)同一場景，本文壓縮算法相比Rosen算法在壓縮比近似的情況下，可達(dá)到較快的壓縮速度。壓縮比會(huì)比Rosen算法稍微有所降低，是因?yàn)樯Ⅻc(diǎn)壓縮，在針對(duì)表2的平均誤差中有解釋。表3中壓縮時(shí)間的對(duì)比可以看出：針對(duì)同一場景，本文壓縮算法達(dá)到較好壓縮比的同時(shí)具有較快的壓縮速度，最快是Rosen算法的74.2倍。壓縮時(shí)間同頂點(diǎn)的鄰接一致性有關(guān)，鄰接一致性較好的動(dòng)態(tài)變形模型頂點(diǎn)會(huì)導(dǎo)致小剛體SRB構(gòu)造的幾率提升，從而使得散點(diǎn)數(shù)量減少，有效提升壓縮時(shí)間。

6結(jié)語

本文提出了一種基于KDtree剖分的快速有效的壓縮方法，通過剛體并行構(gòu)造和基于并查集的剛體快速合并方法加速動(dòng)態(tài)數(shù)據(jù)的壓縮過程，避免剛體分解過程中的暴力搜索、比較以及合并，在保證客戶端重構(gòu)質(zhì)量的同時(shí)，可以實(shí)現(xiàn)對(duì)三維動(dòng)態(tài)場景的快速高效壓縮，有效降低了網(wǎng)絡(luò)帶寬的限制。在客戶端重構(gòu)一定時(shí)間間隔內(nèi)的三維動(dòng)態(tài)場景，用戶在任意角度觀察三維動(dòng)態(tài)場景時(shí)，不需要服務(wù)器端重新壓縮并傳輸數(shù)據(jù)，從而有效減少了網(wǎng)絡(luò)延遲的限制。但在壓縮時(shí)未考慮頂點(diǎn)運(yùn)動(dòng)過程中的階段一致性，動(dòng)態(tài)數(shù)據(jù)的壓縮比還有待提高，下一步將考慮剛體與剛體之間在某一幀或某幾幀可以合并的階段一致性，以進(jìn)一步提高動(dòng)態(tài)場景數(shù)據(jù)的壓縮比。

參考文獻(xiàn)：

[1]

GUSKOV I， KHODAKOVSKY A. Wavelet compression of parametrically coherent mesh sequences [C] // Proceedings of the Second International Conference on Machine Intelligence. Washington， DC： IEEE Computer Society， 2005：211-219.

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. AirelaVille， Switzerland： Eurographics Association， 2004： 183-192.

[2]

PAYAN F， ANTONINI M. Wavelet-based compression of 3d mesh sequences [C] //Proceedings of the Second International Conference on Machine Intelligence. Washington， DC： IEEE Computer Society， 2005：211-219.

PAYAN F， ANTONINI M. Waveletbased compression of 3D mesh sequences [EB/OL]. [20160102]. 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 W. Compression and accelerated rendering of time varying volume data [C] // Proceedings of the Workshop on Computer Graphics and Virtual Reality. New York： ACM Press， 2000：86-92.

MA K， SHEN H. Compression and accelerated rendering of time varying volume data [EB/OL] . [20151126] . http：//web.cse.ohiostate.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]

VUINI E， MLLER T， GRLLER M E. On visualization and reconstruction from nonuniform point sets using Bsplines [J]. Computer Graphics Forum， 2009， 28（3）： 1007-1014.

[8]

JANG Y， EBERT D S， GAITHER K. Timevarying 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 realtime 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]

彭藝，陳莉，雍俊海.大規(guī)模、時(shí)變數(shù)據(jù)的體繪制與特征追蹤[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013，25（11）：1614-1622.（PENG Y， CHEN L， YONG J H. Largescale timevarying data volume rendering and feature tracking [J]. Journal of ComputerAided Design and Computer Graphics， 2013， 25（11）：1614-1622. ）

[14]

DAI Q， SONG Y， XIN Y. Randomaccessible volume data compression with regression function [C] // Proceeding of the 2015 14th International Conference on ComputerAided Design and Computer Graphics. Piscataway， NJ： IEEE， 2015： 137-142.

[15]

Duke University. Unionfind algorithm [EB/OL]. [20151026].