三維引擎動(dòng)畫關(guān)鍵技術(shù)優(yōu)化設(shè)計(jì)研究

丁 磊

(安徽文達(dá)信息工程學(xué)院 計(jì)算機(jī)工程學(xué)院，安徽 合肥 231201)

隨著三維引擎動(dòng)畫諸多關(guān)鍵技術(shù)的發(fā)展與成熟，使用三維引擎動(dòng)畫作為展示和交互方式的現(xiàn)象日趨普遍，人們對(duì)三維動(dòng)畫的細(xì)節(jié)美感要求也越來越高，導(dǎo)致其數(shù)據(jù)量和模型復(fù)雜程度也水漲船高，對(duì)應(yīng)存儲(chǔ)與網(wǎng)絡(luò)傳輸所需消耗的計(jì)算機(jī)資源也逐漸增加[1].因此把重構(gòu)模型失真程度控制在滿足使用要求的前提下，大幅提高三維動(dòng)畫的壓縮比是一個(gè)有待解決的技術(shù)問題.針對(duì)這個(gè)問題，前人提出了多種解決方案，

羅國(guó)亮等[2]為了提高三維動(dòng)畫數(shù)據(jù)的壓縮比與壓縮時(shí)效性，提出了一種基于三維模型頂點(diǎn)序列調(diào)整的優(yōu)化壓縮算法，采用不同類型動(dòng)畫數(shù)據(jù)對(duì)其進(jìn)行測(cè)試，結(jié)果表明，該算法在壓縮比和壓縮速度上比傳統(tǒng)算法有所提升.王美麗等[3]針對(duì)三維模型浮雕在解壓模型過程中容易出現(xiàn)細(xì)節(jié)信息丟失的問題，提出了適用于三維復(fù)雜網(wǎng)絡(luò)模型生成數(shù)字浮雕的優(yōu)化方案，實(shí)驗(yàn)結(jié)果表明，該方案能有效降低構(gòu)建三維數(shù)字浮雕模型重構(gòu)過程中的信息損失.于兵科[4]針對(duì)傳統(tǒng)三維動(dòng)畫模型在解壓重構(gòu)后動(dòng)畫效果有所劣化的問題，采用動(dòng)力學(xué)方法，以物理引擎為基礎(chǔ)，設(shè)計(jì)出一套改進(jìn)的三維模型重構(gòu)算法，實(shí)驗(yàn)結(jié)果顯示，該算法重構(gòu)出的三維模型動(dòng)畫效果更接近未解壓前的狀態(tài)，動(dòng)畫信息損失更少.綜上所述，行業(yè)內(nèi)專家對(duì)模型壓縮優(yōu)化方法做了詳細(xì)研究，但是較少涉及流式傳輸，因此本文設(shè)計(jì)一種三維引擎動(dòng)畫的優(yōu)化壓縮算法，其對(duì)于降低計(jì)算機(jī)處理負(fù)擔(dān)、提高三維動(dòng)畫的網(wǎng)絡(luò)傳輸速度、實(shí)現(xiàn)動(dòng)畫數(shù)據(jù)的流式傳輸具有一定價(jià)值.

1 面向三維引擎動(dòng)畫的改進(jìn)壓縮算法

1.1 基于整數(shù)規(guī)劃的時(shí)域聚類算法

三維引擎動(dòng)畫的壓縮技術(shù)呈現(xiàn)出由單分辨率壓縮向多分辨率壓縮轉(zhuǎn)變的趨勢(shì)，因?yàn)槎喾直媛蕢嚎s又稱為漸進(jìn)式壓縮，支持對(duì)幾何模型的漸進(jìn)傳輸，其網(wǎng)絡(luò)利用效率更高[5-8].本研究提出一種漸進(jìn)式壓縮的優(yōu)化改進(jìn)算法，其算法的壓縮流程如圖1所示.

圖1 改進(jìn)的三維引擎動(dòng)畫壓縮算法流程

如圖1所示，算法的壓縮核心步驟為：①讀取三維引擎動(dòng)畫文件，讀取各關(guān)鍵幀里的頂點(diǎn)坐標(biāo)數(shù)據(jù)與拓?fù)鋽?shù)據(jù);②通過計(jì)算待求指標(biāo)的頂點(diǎn)在所有幀中坐標(biāo)連成的空間曲線，然后用每幀的指標(biāo)加權(quán)值得到每個(gè)頂點(diǎn)的曲率與繞度；③采用提出的時(shí)域聚類算法將要素相似的幀聚為一類;④對(duì)時(shí)域聚類結(jié)果的每一類關(guān)鍵幀進(jìn)行空域分割，使頂點(diǎn)運(yùn)動(dòng)趨勢(shì)相似且拓?fù)溥B續(xù)的點(diǎn)聚為一類;⑤完成對(duì)時(shí)空兩者的聚類后，再對(duì)輸出數(shù)據(jù)進(jìn)行圖傅里葉變換以進(jìn)一步提高壓縮效果;⑥對(duì)經(jīng)過圖傅里葉變換的系數(shù)值進(jìn)行SPECK編碼，然后結(jié)合前面的連接數(shù)據(jù)與編碼后的數(shù)據(jù)輸出壓縮后的三維動(dòng)畫文件.若要對(duì)模型解壓重構(gòu)，按照壓縮流程逆向執(zhí)行即可.

為了處理相鄰幀的冗余信息，提出一種基于整數(shù)規(guī)劃的時(shí)域聚類算法，通過它對(duì)動(dòng)畫幀進(jìn)行聚類，讓相似度高的網(wǎng)絡(luò)幀聚集為一類，以便下一步消除這些冗余數(shù)據(jù).考慮到時(shí)域聚類結(jié)果中每類所含幀數(shù)都為整數(shù)，因此普通的時(shí)域聚類并不適合此次研究[9-12].采用每幀頂點(diǎn)的曲率和繞度來代表其運(yùn)動(dòng)劇烈程度，這里的曲率、繞度是指由所有幀中待求曲率頂點(diǎn)組成的曲線，與每幀交點(diǎn)的曲率與繞度，其數(shù)值通過差分法求得，以減小擬合誤差，從而得到每幀的運(yùn)動(dòng)圖，以縱坐標(biāo)為頂點(diǎn)模型運(yùn)動(dòng)值，橫坐標(biāo)為頂點(diǎn)索引，則可以用相鄰幀的運(yùn)動(dòng)圖與坐標(biāo)軸所圍面積的差異大小來衡量運(yùn)動(dòng)劇烈程度.因此，該規(guī)劃問題的目標(biāo)函數(shù)就可以定義為每類偏離平均面積的平方和，約束條件為所有類含幀數(shù)之和等于總幀數(shù)，這樣，普通時(shí)域聚類問題被轉(zhuǎn)化成為非線性約束的整數(shù)規(guī)劃問題.具體的，第i個(gè)頂點(diǎn)在每幀中的曲率以及繞度的具體求解公式如下：

(1)

(2)

MO=αk+(1-α)τ，

(3)

其中:k、τ代表曲率、繞度，α代表權(quán)重，一般情況下兩者重要性相同，α取0.5，特殊情況下應(yīng)適當(dāng)調(diào)整.如果模型幾乎是在單個(gè)平面上移動(dòng)，則曲率指標(biāo)重要性更高，α需要調(diào)大一些.

(4)

其中:t為i類所含幀數(shù)，為了控制算法運(yùn)行過程中所消耗的存儲(chǔ)空間，定義一個(gè)權(quán)重系數(shù)β，表示誤差在目標(biāo)函數(shù)中所占比重.另外，設(shè)空域分割一幀保存結(jié)果需要的存儲(chǔ)空間為t，則目標(biāo)函數(shù)定義為：

min{βL(t1,…,tk)+(1-β)Kt}=

(5)

其中:K為聚類后的類別數(shù)量.最后幀數(shù)的約束條件如下：

(6)

其中:Nkey為關(guān)鍵幀的數(shù)量.至此，時(shí)域聚類問題便完整轉(zhuǎn)化為非線性約束下的整數(shù)規(guī)劃問題，然后采用蒙特卡羅方法求解.

1.2 基于動(dòng)畫對(duì)象運(yùn)動(dòng)特性的分割算法

對(duì)數(shù)據(jù)進(jìn)行時(shí)域聚類后，還需要對(duì)聚類結(jié)果中每一類的關(guān)鍵幀進(jìn)行空域分割，其目的是為了把模型中相似的各頂點(diǎn)劃分為同一塊[13-15].如果兩頂點(diǎn)的歐式距離與其時(shí)域聚類的簇內(nèi)運(yùn)動(dòng)期望之差的加權(quán)均值很小，算法就認(rèn)為兩頂點(diǎn)相似度高，應(yīng)聚為同一類，其中關(guān)鍵幀通過逐幀計(jì)算該類當(dāng)前幀與其他各幀的幀距總和，然后取該值最小的對(duì)應(yīng)幀為關(guān)鍵幀.設(shè)時(shí)域聚類第k類的關(guān)鍵幀f被空間分割為S塊，應(yīng)選擇合適的S值使分割結(jié)果中每塊內(nèi)含有頂點(diǎn)之間的運(yùn)動(dòng)量差別最小，其值由后續(xù)實(shí)驗(yàn)確定，則目標(biāo)函數(shù)可表示為：

(7)

(8)

下面以第t類的關(guān)鍵幀f為例闡述空域分割的過程，其計(jì)算流程如圖2所示.

圖2 空域分割聚類流程圖

(9)

完成時(shí)域、空域聚類后，再對(duì)所有處理后的數(shù)據(jù)進(jìn)行圖傅里葉變換，進(jìn)一步提高壓縮效果.設(shè)變換對(duì)象為第i類的第j塊Sij.先運(yùn)用聚類后的動(dòng)畫數(shù)據(jù)拓?fù)淝蟪鯯ij的拉普拉斯矩陣L，計(jì)算公式為L(zhǎng)=D-A.D是對(duì)角矩陣，對(duì)角上的元素為對(duì)應(yīng)頂點(diǎn)的度，A為鄰接矩陣，由數(shù)據(jù)的拓?fù)湫畔⑶蟮?，兩頂點(diǎn)有邊對(duì)應(yīng)位置記1，無邊記為0.另外，L、D、A均為‖Sij‖×‖Sij‖的矩陣，‖Sij‖代表第i類里第j塊的頂點(diǎn)數(shù)量.求出拉普拉斯矩陣L后，再求出對(duì)應(yīng)的特征向量V，同為‖Sij‖×‖Sij‖的矩陣.最后，把每幀里相應(yīng)頂點(diǎn)的三維坐標(biāo)分別取出，投影到對(duì)應(yīng)部分的基上，計(jì)算得到相應(yīng)系數(shù)，再根據(jù)輸出文件的質(zhì)量、網(wǎng)絡(luò)傳輸速度、模型所屬行業(yè)等要求，從中選出kn個(gè)基較為重要的系數(shù)，以備下一步編碼.

為了滿足當(dāng)下主流的漸進(jìn)傳輸要求，對(duì)經(jīng)過圖傅里葉變換后提取的系數(shù)采用嵌入式編碼算法編碼，而常見嵌入式算法中SPECK編碼在獨(dú)立編碼、編碼速度方面具有明顯優(yōu)勢(shì)，因此研究選擇SPECK算法對(duì)圖傅里葉變換輸出系數(shù)進(jìn)行編碼.

2 改進(jìn)壓縮算法的壓縮效果分析

2.1 改進(jìn)壓縮算法的壓縮對(duì)比實(shí)驗(yàn)參數(shù)設(shè)置

針對(duì)設(shè)計(jì)好的算法，選用兩種常見的三維引擎動(dòng)畫模型Human、Cat，它們的模型拓?fù)湫畔ⅰ缀涡畔⑷绫?所列.實(shí)驗(yàn)使用的三維模型通過3 ds Max2017軟件構(gòu)建，實(shí)驗(yàn)在惠普251-050cn型臺(tái)式計(jì)算機(jī)平臺(tái)進(jìn)行.對(duì)其使用該算法與常見的三維動(dòng)畫壓縮算法Luo et al.2013、Vasa et al.2010進(jìn)行對(duì)比壓縮實(shí)驗(yàn)，以驗(yàn)證該算法的壓縮效果，后兩種算法與本算法有相似之處，但它們僅對(duì)三維模型的幾何信息進(jìn)行壓縮，不壓縮拓?fù)湫畔?，且不考慮時(shí)域冗余.

如表1所列，模型的幾何信息遠(yuǎn)大于拓?fù)湫畔?在確定算法的關(guān)鍵參數(shù)時(shí)，對(duì)于空域分割中的距離權(quán)重系數(shù)χ，考慮到算法需要較高的空間連續(xù)性以盡可能減少分割后每塊所含不連續(xù)頂點(diǎn)的數(shù)量，從而保證下一步圖傅里葉變換的準(zhǔn)確性，該權(quán)重系數(shù)設(shè)置范圍為0.5～1，用以保證聚類后數(shù)據(jù)的空間連續(xù)性，具體取值通過Human、Cat模型的分割后χ權(quán)重系數(shù)與不連續(xù)點(diǎn)關(guān)系實(shí)驗(yàn)確定，其實(shí)驗(yàn)結(jié)果如圖3所示.

表1 用于測(cè)試的三維引擎動(dòng)畫模型部分參數(shù)

圖3 分割后χ權(quán)重系數(shù)與不連續(xù)點(diǎn)占比的關(guān)系

分析圖3可知，當(dāng)χ權(quán)重系數(shù)小于0.8時(shí)，隨著系數(shù)的增大，兩模型中不連續(xù)點(diǎn)占比下降明顯，但下降速度有所減緩；而當(dāng)權(quán)重系數(shù)接近0.8以后，隨著系數(shù)的增大，不連續(xù)點(diǎn)占比變化已不明顯，即這時(shí)增加系數(shù)對(duì)減少不連續(xù)點(diǎn)的作用已極其有限，所以χ權(quán)重系數(shù)選擇0.8較為合理.按照同樣的思路，可以確定kn取值較為合理.

2.2 三維引擎動(dòng)畫模型壓縮對(duì)比試驗(yàn)結(jié)果分析

選好算法系數(shù)后，采用常規(guī)的壓縮率-重構(gòu)誤差率曲線來對(duì)比各算法效果，壓縮率由壓縮后的總數(shù)據(jù)大小除以模型頂點(diǎn)個(gè)數(shù)與動(dòng)畫總幀數(shù)的乘積.各算法對(duì)Human三維引擎動(dòng)畫壓縮效果如圖4所示.

圖4 各算法對(duì)Human三維引擎動(dòng)畫模型壓縮效果

圖4中的“Hybrid spatiotemporal clustering”即為本研究提出的混合時(shí)空聚類壓縮算法.分析圖4可知，在3種算法都存在數(shù)據(jù)的范圍內(nèi)，達(dá)到同一模型壓縮率時(shí)，此算法的模型重構(gòu)誤差率最小，即模型重構(gòu)時(shí)失真程度最小，而在達(dá)到同一模型重構(gòu)誤差率時(shí)，該算法的壓縮率又遠(yuǎn)遠(yuǎn)小于其他兩種算法，并且此算法在壓縮率大于0.3%時(shí)，減小壓縮率(即提高壓縮程度)帶來的模型重構(gòu)誤差增長(zhǎng)微小.綜上所述，該研究提出的新型壓縮算法對(duì)Human動(dòng)畫模型的壓縮效果、重構(gòu)效果明顯優(yōu)于傳統(tǒng)壓縮算法.為進(jìn)一步確認(rèn)算法效果，再對(duì)Cat三維動(dòng)畫模型進(jìn)行壓縮比對(duì)測(cè)試，結(jié)果如圖5所示.

圖5 各算法對(duì)Cat三維引擎動(dòng)畫模型壓縮效果

如圖5所示，對(duì)Cat三維引擎模型的壓縮、重構(gòu)效果與對(duì)Human的大體一致，僅少數(shù)細(xì)節(jié)有所不同.因?yàn)镃at動(dòng)畫模型較之Human更為復(fù)雜、運(yùn)動(dòng)變化更為激烈，所以在各算法下整體重構(gòu)誤差率均較高，且在同樣重構(gòu)誤差率下，壓縮效果整體都更差.算法間對(duì)比結(jié)果同樣顯示出，該研究提出的壓縮算法在壓縮效率、重構(gòu)誤差方面具有顯著優(yōu)勢(shì).

3 結(jié)論

本文針對(duì)三維引擎動(dòng)畫的關(guān)鍵技術(shù)之一的壓縮技術(shù)進(jìn)行了優(yōu)，在分析了前人解決方案的基礎(chǔ)上，提出了一種基于時(shí)域、空域雙重聚類的三維動(dòng)畫壓縮算法.該算法創(chuàng)新性地把目標(biāo)函數(shù)、曲率、繞度進(jìn)行了重新定義，從而把基于整數(shù)規(guī)劃的時(shí)域聚類問題轉(zhuǎn)換成為非線性約束的整數(shù)規(guī)劃問題.使用該算法與其他三維動(dòng)畫壓縮算法進(jìn)行壓縮與重構(gòu)實(shí)驗(yàn)，在相同模型壓縮率條件下，使用該算法進(jìn)行模型重構(gòu)時(shí)，重構(gòu)誤差率最小，而在同一模型重構(gòu)誤差率時(shí)，該算法的壓縮率又遠(yuǎn)遠(yuǎn)小于其他算法，在小壓縮率、中等壓縮率、大壓縮率條件下，該算法的重構(gòu)誤差率較對(duì)比算法分別降低了至少45%、20%和3%.結(jié)果說明該研究提出的新型壓縮算法對(duì)三維引擎動(dòng)畫的壓縮率、重構(gòu)誤差有一定的優(yōu)化效果.