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

馬志強(qiáng) 李海生

摘要：

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

關(guān)鍵詞：

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

中圖分類號：

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

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

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

1算法整體流程

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

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

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

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

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

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

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

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

③剩余散點的壓縮。

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

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

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

跡的快速有效壓縮。本文將剛體定義為一個三元組（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}是剛體在整個運(yùn)動過程中從第1到S-1幀相對于第0幀空間位置的運(yùn)動矩陣。

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

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

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

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

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

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

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

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

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

構(gòu)造初始剛體（i， j，k）后，求初始小剛體具體某一幀相對于第0幀的運(yùn)動矩陣。具體如圖4：假定初始小剛體（i， j，k）在運(yùn)動過程某一幀f時的空間位置為（a，b，c），首先將頂點i移動到第f幀對應(yīng)的空間位置a上，得到移動矩陣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幀相對于第0幀的運(yùn)動矩陣qf，即Q1、Q2和Q3的相乘，用式（1）表示為：

qf=Q3×Q2×Q1（1）

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

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

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

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

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

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

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

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

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

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

其中：Pf′v是頂點v在第f幀（0

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

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

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

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

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

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

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

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

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

3.2基于并查集的剛體合并

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

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

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

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

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

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

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

程序前

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

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

3.3剩余散點的壓縮

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

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

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

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

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

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

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

5實驗結(jié)果與分析

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

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

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

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

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

5.2壓縮效率

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

6結(jié)語

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