三維引擎動畫關鍵技術優化設計研究

丁 磊

(安徽文達信息工程學院 計算機工程學院，安徽 合肥 231201)

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

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

1 面向三維引擎動畫的改進壓縮算法

1.1 基于整數規劃的時域聚類算法

三維引擎動畫的壓縮技術呈現出由單分辨率壓縮向多分辨率壓縮轉變的趨勢，因為多分辨率壓縮又稱為漸進式壓縮，支持對幾何模型的漸進傳輸，其網絡利用效率更高[5-8].本研究提出一種漸進式壓縮的優化改進算法，其算法的壓縮流程如圖1所示.

圖1 改進的三維引擎動畫壓縮算法流程

如圖1所示，算法的壓縮核心步驟為：①讀取三維引擎動畫文件，讀取各關鍵幀里的頂點坐標數據與拓撲數據;②通過計算待求指標的頂點在所有幀中坐標連成的空間曲線，然后用每幀的指標加權值得到每個頂點的曲率與繞度；③采用提出的時域聚類算法將要素相似的幀聚為一類;④對時域聚類結果的每一類關鍵幀進行空域分割，使頂點運動趨勢相似且拓撲連續的點聚為一類;⑤完成對時空兩者的聚類后，再對輸出數據進行圖傅里葉變換以進一步提高壓縮效果;⑥對經過圖傅里葉變換的系數值進行SPECK編碼，然后結合前面的連接數據與編碼后的數據輸出壓縮后的三維動畫文件.若要對模型解壓重構，按照壓縮流程逆向執行即可.

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

(1)

(2)

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

(3)

其中:k、τ代表曲率、繞度，α代表權重，一般情況下兩者重要性相同，α取0.5，特殊情況下應適當調整.如果模型幾乎是在單個平面上移動，則曲率指標重要性更高，α需要調大一些.

(4)

其中:t為i類所含幀數，為了控制算法運行過程中所消耗的存儲空間，定義一個權重系數β，表示誤差在目標函數中所占比重.另外，設空域分割一幀保存結果需要的存儲空間為t，則目標函數定義為：

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

(5)

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

(6)

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

1.2 基于動畫對象運動特性的分割算法

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

(7)

(8)

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

圖2 空域分割聚類流程圖

(9)

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

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

2 改進壓縮算法的壓縮效果分析

2.1 改進壓縮算法的壓縮對比實驗參數設置

針對設計好的算法，選用兩種常見的三維引擎動畫模型Human、Cat，它們的模型拓撲信息、幾何信息如表1所列.實驗使用的三維模型通過3 ds Max2017軟件構建，實驗在惠普251-050cn型臺式計算機平臺進行.對其使用該算法與常見的三維動畫壓縮算法Luo et al.2013、Vasa et al.2010進行對比壓縮實驗，以驗證該算法的壓縮效果，后兩種算法與本算法有相似之處，但它們僅對三維模型的幾何信息進行壓縮，不壓縮拓撲信息，且不考慮時域冗余.

如表1所列，模型的幾何信息遠大于拓撲信息.在確定算法的關鍵參數時，對于空域分割中的距離權重系數χ，考慮到算法需要較高的空間連續性以盡可能減少分割后每塊所含不連續頂點的數量，從而保證下一步圖傅里葉變換的準確性，該權重系數設置范圍為0.5～1，用以保證聚類后數據的空間連續性，具體取值通過Human、Cat模型的分割后χ權重系數與不連續點關系實驗確定，其實驗結果如圖3所示.

表1 用于測試的三維引擎動畫模型部分參數

圖3 分割后χ權重系數與不連續點占比的關系

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

2.2 三維引擎動畫模型壓縮對比試驗結果分析

選好算法系數后，采用常規的壓縮率-重構誤差率曲線來對比各算法效果，壓縮率由壓縮后的總數據大小除以模型頂點個數與動畫總幀數的乘積.各算法對Human三維引擎動畫壓縮效果如圖4所示.

圖4 各算法對Human三維引擎動畫模型壓縮效果

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

圖5 各算法對Cat三維引擎動畫模型壓縮效果

如圖5所示，對Cat三維引擎模型的壓縮、重構效果與對Human的大體一致，僅少數細節有所不同.因為Cat動畫模型較之Human更為復雜、運動變化更為激烈，所以在各算法下整體重構誤差率均較高，且在同樣重構誤差率下，壓縮效果整體都更差.算法間對比結果同樣顯示出，該研究提出的壓縮算法在壓縮效率、重構誤差方面具有顯著優勢.

3 結論

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