保細(xì)節(jié)的曲面編輯算法研究_中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文

1、中國科學(xué)技術(shù)大學(xué)University of Science and Technology of China本科畢業(yè)論文A Dissertation Submitted for the Bachelors Degree保細(xì)節(jié)的曲面編輯算法研究Surface Editing with Detail Preservation姓名李 勃B.S. CandidateBo Li導(dǎo)師劉利剛 教授SupervisorProf.Ligang Liu2013 年 5 月May, 2013中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文0 謝 感謝中國科學(xué)技術(shù)大學(xué)多年在學(xué)習(xí)生活中的幫助，使學(xué)生在思想境界，學(xué)術(shù)水平上都有了比較大的提高。

2、并感謝母校能給學(xué)生這樣一個(gè)機(jī)會(huì) 完成這篇論文。感謝中國科學(xué)技術(shù)大學(xué)劉利剛老師在本論文將近三個(gè)月的制作期間持續(xù)地耐心地解答學(xué)生的問題。劉老師不僅在論文中各種難點(diǎn)處給予學(xué)生自 然而深刻的指導(dǎo)，而且在學(xué)生學(xué)習(xí)生活方面處于十分迷茫的時(shí)期提供了友 善而有力的教誨，使學(xué)生能夠正視人生道路上的困難，在接下來的若干年 里學(xué)生也將跟隨劉老師從事相關(guān)研究工作，希望老師不吝教導(dǎo)。同時(shí)感謝中國科學(xué)技術(shù)大學(xué)單文同學(xué)、丁超同學(xué)與華中科學(xué)技術(shù)大學(xué)的王康同學(xué)等在這段時(shí)間內(nèi)提供的各種資源上和知識(shí)上的幫助。感謝孫琪 同學(xué)在論文相關(guān)資源相關(guān)的方方面面的協(xié)助，孫琪同學(xué)在共同學(xué)習(xí)的四年 中提供了學(xué)生各種各樣的幫助，其所充滿的專業(yè)精神與

3、助人精神，是我所 應(yīng)該學(xué)習(xí)的。能夠順利的完成學(xué)業(yè)并走向新的道路我十分高興，在此亦將十分感謝 同宿舍以及鄰舍的各位同學(xué)，給我創(chuàng)造了這樣一個(gè)充滿了善意與努力的環(huán) 境。尤其感謝我的父母在各方面的無私的大力支持與默默的奉獻(xiàn)，我以你 們?yōu)闃s。1中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文目 錄致謝1摘要3Abstract4第一章 緒論51.1引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.2相關(guān)工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6

4、第二章 Laplacian 編輯92.1Laplacian 坐標(biāo) . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.2Laplacian 編輯 . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3Laplacian 編輯的實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . .142.4 Laplacian 編輯的優(yōu)缺點(diǎn) . . . . . . . . . . . . . . . . . . . . . . . 15

5、第三章ARAP 編輯163.1ARAP 局部分析 . . . . . . . . . . . . . . . . . . . . . . . . . . .163.2ARAP 整體處理 . . . . . . . . . . . . . . . . . . . . . . . . . . .183.3 ARAP 編輯的實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 ARAP 編輯的特點(diǎn) . . . . . . . . . . . . . . . . . . . . . . . . . . 20 第四章 總結(jié)與延伸234

6、.1 總結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 延伸 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 參考文獻(xiàn)262中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文0 要 伴隨著計(jì)算機(jī)圖形學(xué)學(xué)科的深入發(fā)展與該學(xué)科應(yīng)用于實(shí)際工作中要求的廣泛加深，三維模型的形狀變形問題變得相當(dāng)基本而重要。本篇論文便主要介紹了三維模型形狀編輯過程中能夠有效保持模型表面細(xì)節(jié)的兩種算法。分別為基于 Laplacian 坐標(biāo)變換的 La

7、placian 編輯以及以此為基礎(chǔ)的進(jìn)一步地施加剛性修正的 ARAP 編輯。本論文著重于介紹兩種算法的原理、實(shí)現(xiàn)、應(yīng)用以及發(fā)展，大致分為三個(gè)部分。第一部分，也就是第二章我們主要介紹 Laplacian 編輯。這種 Lapla-cian 編輯是一種先對(duì)選定區(qū)域中各點(diǎn)建立局部拉普拉斯坐標(biāo)，然后通過引導(dǎo)其進(jìn)行平移、旋轉(zhuǎn)、放縮這幾種可以保持細(xì)節(jié)部分的變換來完成保持模型表面細(xì)節(jié)的形狀變形的一種算法。這種算法可以有效地完成保持模型表面細(xì)節(jié)形狀變形，并且具有形式簡(jiǎn)潔，運(yùn)算速度快等諸多優(yōu)點(diǎn)。而 第 二 部 分，我 們 則 介 紹 ARAP 編 輯，這 將 放 在 第 三 章 中 進(jìn) 行。ARAP 編輯，即極大

8、剛性編輯，作為 Laplacian 編輯不能良好的控制形變模型細(xì)節(jié)剛性這一問題的解決方案，要在 Laplacian 編輯的基礎(chǔ)上建立晶格體系，通過奇異值分解提取之前坐標(biāo)變換對(duì)每一個(gè)晶格結(jié)構(gòu)變換的旋轉(zhuǎn)分量，對(duì)之前變換進(jìn)行晶格旋轉(zhuǎn)變換的近似來達(dá)到剛性修正的效果。這一方法可以比較好地保持形狀變形過程中的模型的剛性，從而達(dá)到Laplacian 編輯所不能達(dá)到的效果。在最后我們也較詳盡地比較了兩者在形狀變形過程中所達(dá)到的保持細(xì) 節(jié)形式的差異，提出了保細(xì)節(jié)形狀變形中的一些問題。這也是本論文的重 要內(nèi)容之一。關(guān)鍵字: 圖形變形，Laplacian 編輯，ARAP 編輯，稀疏矩陣3中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文

9、Abstract3D meshes editing is becoming more and more important with the rapid development of Computer Graphics and its application. This pa-per introduces two surface editing algorithms which can keep the surface details, the Laplacian editing based on the Laplacian coordinates and As-rigid-as-possib

10、le surface editing. The thesis focuses on the implementation, application and development of the two algorithms.The first one, laplacian editing, is based on the local Laplacian coordi-nates, by directing its simple coordinate transformation to keep the surface details. It has many advantage such as

11、 computing fast and achieving easily.The latter one ,ARAP editing, keeps the model as rigid as possible by setting up Cells. By using singular value decomposition to Laplacian surface editing, it can find a rotation approximation for keeping rigid. This approach can make it while Laplacian editing c

12、annot.The di erence of them is also the emphasis of this paper,which we will discuss at the end.Keywords: model editing , Laplacian editing , ARAP editing , Sparse Matrix4中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文0 1 章 緒論 1.1 引言 形狀變形是計(jì)算機(jī)圖形學(xué)中十分重要的一類問題。在處理三維圖形的實(shí)際 過程中，三角網(wǎng)格在記錄點(diǎn)、線、面的數(shù)據(jù)以及此三者之間關(guān)系的維護(hù)方面具 有十分顯著的優(yōu)勢(shì)，故三角形網(wǎng)格成為了此問題中比較常用的模型之一

13、。從而 形狀變形的相關(guān)問題經(jīng)常直接演變成處理三角網(wǎng)格坐標(biāo)變換的問題。在以往的三角網(wǎng)格坐標(biāo)變換的研究中，比較自然的想法是在世界坐標(biāo)系中 研究變換。然而，實(shí)際上對(duì)于處理形狀變形細(xì)節(jié)的保持這一問題，大部分情況 下我們并不需要對(duì)每個(gè)點(diǎn)的絕對(duì)位置進(jìn)行關(guān)注，而只需要考慮點(diǎn)的鄰域中的其 他點(diǎn)與其的相對(duì)位置關(guān)系即可。這就是說我們可以根據(jù)網(wǎng)格中每個(gè)點(diǎn)與其周圍 的少數(shù)點(diǎn)建立局部的坐標(biāo)架，通過這種局部標(biāo)架就可以有效的處理點(diǎn)的平移、 旋轉(zhuǎn)、放縮變換過程中的細(xì)節(jié)保持問題。并且如此建立標(biāo)架可以構(gòu)建出坐標(biāo)變 換的大規(guī)模稀疏矩陣的線性方程組，利用方程組的顯著的稀疏性就可以快速求 出變換后各點(diǎn)的坐標(biāo)。這就是目前的大部分形狀變形

14、相關(guān)的網(wǎng)格編輯的主要思 路。Laplacian 編輯就是這種思路所產(chǎn)生的一種圖形變形算法。而無論是在工業(yè)生產(chǎn)或是日常生活中，具有一定剛性的三維模型均是十 分平凡的。在處理這一類模型的形狀變形過程中，保持細(xì)節(jié)部分的相對(duì)水平 的穩(wěn)定也是十分重要的一類問題。而在接下來的討論中我們得出結(jié)論，僅靠Laplacian 編輯來完成形狀變形時(shí)會(huì)導(dǎo)致此類模型變換后細(xì)節(jié)的平衡上相對(duì)失真。對(duì)于這種情況，就可以通過 ARAP 編輯來進(jìn)行有效的修正。其基本思路是先進(jìn)行一次預(yù)測(cè)式的變換，這一步應(yīng)用 Laplacian 編輯即可，然后通過逐點(diǎn)建立 1- 鄰域的晶格結(jié)構(gòu)，將之前的坐標(biāo)變換視為對(duì)于每個(gè)晶格的基本變換。對(duì)此變換的

15、矩陣?yán)闷娈愔捣纸獾姆椒ǔ槿∑渲械男D(zhuǎn)變換，以此旋轉(zhuǎn)變換作為該晶格的基本變換的近似來操作整個(gè)圖形的變換，從而控制模型細(xì)節(jié)的剛性。5中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文1.2 相關(guān)工作 三維形狀變形的相關(guān)問題在計(jì)算機(jī)圖形學(xué)領(lǐng)域占有重要地位，因而在以 往已經(jīng)有相當(dāng)多的學(xué)者置身于這些研究之中了，而這篇文章就是主要基于Sorkine 等的關(guān)于 Laplacian 編輯的文章 1 與這一研究小組關(guān)于 ARAP 編輯 的文章 2 完成的。在此之前的相關(guān)研究中，比較古老的研究方向是將所編輯 圖形進(jìn)行合理拆分，將三維網(wǎng)格中的光滑部分和細(xì)節(jié)部分通過特定的算法提取 出來，并將兩者分別進(jìn)行編輯 34，這種方法雖然可以實(shí)現(xiàn)，

16、但是成本比較 大，運(yùn)算速度慢，占據(jù)資源多，此后就不太熱門了。而后則出現(xiàn)一些基于整體 編輯的形狀變形，如 Welch 等的簡(jiǎn)易形狀編輯 5，Taubin 等的光滑表面處理 算法 6，Veuvre 等的基于有限元建模的形狀變形 7 等等，這些算法產(chǎn)生于三 維網(wǎng)格整體編輯研究的初期，對(duì)于處理相對(duì)光滑三維網(wǎng)格形狀變形具有很好的 效果，但對(duì)于處理具有顯著細(xì)節(jié)需要保持的三維網(wǎng)格，這些方法的效果就不盡 人意了。再之后，F(xiàn)ORSEY 等人提出了保細(xì)節(jié)形狀變形在世界坐標(biāo)系中實(shí)現(xiàn)的 算法 8，可以比較有效的保持形狀變形中的細(xì)節(jié)部分，但是這種基于整體點(diǎn)的 研究思路，也導(dǎo)致了運(yùn)算上的規(guī)模過大的問題。后來在圖像處理領(lǐng)域

17、中 Perez等將偏微分方程引入其中提出了基于泊松方程的圖像拼接技術(shù) 9，效果十分顯 著，且其所用的求解大規(guī)模稀疏矩陣方程組的運(yùn)算技術(shù)發(fā)展十分迅速，運(yùn)算速 度非常之快。6中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文圖 1.1: 基于 Possion 方程的圖像拼接技術(shù) 9以此為鑒，Sorkine 等在不久之后提出了相似的工作，即相似地通過建 立數(shù)值微分方程來研究三維模型的形狀變形 10，進(jìn)而提出了之后要介紹的Laplacian 編輯 1，在這之后 Liu 等又發(fā)展出了雙重 Laplacian 編輯 11。圖 1.2: 基于 Laplacian 編輯的形狀變形 1另一方面，形狀變形中細(xì)節(jié)保持的研究并不止于此，L

18、aplacian 編輯的非 剛性結(jié)果并不令人滿意，而解決這一問題成了更進(jìn)一步的研究方向，隨著以模 型表面形狀能量函數(shù)理論 12 控制剛性保持的方法得到重視，相關(guān)研究變得更 多。但因?yàn)榇四芰亢瘮?shù)實(shí)際上不是線性的，所以應(yīng)用起來并不順利。Koobrlt7中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文等于是做了許多將其線性化的工作 131415。結(jié)合著另外一些基于特殊標(biāo)架的形狀變形算法 1617，Sorkine 等又進(jìn)一步提出了 ARAP 編輯 2。圖 1.3: 基于 ARAP 編輯的形狀變形 28中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文0 2 章 Laplacian 編輯 2.1 Laplacian 坐標(biāo) 對(duì)于一個(gè)已知的三角形網(wǎng)

19、格，對(duì)網(wǎng)格中所有點(diǎn)進(jìn)行編號(hào) f1; :; ng，并定義集合 V 表示網(wǎng)格中所有點(diǎn)的坐標(biāo)的集合，即:V = fv1; :; vng定義集合 K 表示網(wǎng)格中所有邊的集合，就是說，若 i 與 j 為一條邊的兩個(gè) 頂點(diǎn)，則 (i; j) 2 K。取點(diǎn) i 的 1-鄰域，即與點(diǎn) i 直接相連成邊的點(diǎn)的集合，定義為 Ni，即：Ni = fjj (i; j) 2 Kg定義 di 為點(diǎn) i 的度，表示點(diǎn) i 的 1-鄰域內(nèi)點(diǎn)的數(shù)量，即：di = jNij由此，用于代替世界坐標(biāo)系分析局部問題，我們確立點(diǎn) i 的局部 Laplacian坐標(biāo)。為了簡(jiǎn)潔起見我們只將“局部”限定在點(diǎn) i 的 1-鄰域內(nèi)，如此而言之后

20、構(gòu)建的線性方程組的稀疏性是最強(qiáng)的。定義：1vj(2-1)L (vi) = vi di jNi為點(diǎn) i 的 Laplacian 坐標(biāo)。其表示了點(diǎn) i 相對(duì)于其 1-鄰域內(nèi)的其他點(diǎn)的重心的 偏移量，如圖 2.1：9坐標(biāo)變換無意義化。如果改變定義中的權(quán) 1di中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文圖 2.1: Laplacian 坐標(biāo)，即鄰域中其他點(diǎn)到該點(diǎn)的向量定義 Laplacian 坐標(biāo)為點(diǎn) i 相對(duì)于其 1-鄰域內(nèi)的其他點(diǎn)的重心的偏移量可 以在下面的形狀變形過程中保持局部細(xì)節(jié)變化的均勻性，以不至于使 Laplacian為其他值會(huì)導(dǎo)致細(xì)節(jié)部分在平移、旋轉(zhuǎn)、放縮方面產(chǎn)生特異的變化，但只要不存在對(duì)于鄰域中每個(gè)

21、點(diǎn)過大過小的情況，則并不影響接下來所提出的 Laplacian 編輯本身的有效性。2.2 Laplacian 編輯 對(duì)于三維模型的形狀變形，我們探討一種比較常見的方式。首先給定一個(gè) 網(wǎng)格，在網(wǎng)格上選定某一部分作為選定區(qū)域，通過控制一部分點(diǎn)的變換來控制 整個(gè)選定區(qū)域進(jìn)行變換。如圖 1-2 所示，將章魚的一條觸須選定，通過拖拽觸須上的一部分點(diǎn)來控制整條觸須變形。這一形狀變形的過程，我們先要選定區(qū)域，然后在其上選擇一部分點(diǎn)作為參照點(diǎn)，對(duì)其進(jìn)行坐標(biāo)變換并固定。定義交互區(qū)域中所有點(diǎn)完成變換之后的坐標(biāo)的集合為：V = fv1; :; vng其中選為參照點(diǎn)，率先完成坐標(biāo)變換并被固定的點(diǎn)為：vi = ui;

22、i 2 fm; :; ng; m < n10中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文此類形狀變形實(shí)際要解決的問題就是求解交互區(qū)域中其他點(diǎn)在保持模型表面細(xì)節(jié)的前提下的新的坐標(biāo) vi比較自然的，Laplacian 坐標(biāo)可以作為這一變換中保持細(xì)節(jié)求解的工具，由此建立一個(gè)能量函數(shù)：nn(2-2)E (V ) =jjL (vi) L (vi) jj2 + jjvi uijj2=1i=mi這個(gè)能量函數(shù)第一項(xiàng)表示了三角形網(wǎng)格 Laplacian 坐標(biāo)在變換過程中所產(chǎn) 生的能量，第二項(xiàng)則表示了參照點(diǎn)在變換的過程中所產(chǎn)生的能量，變量為變換 點(diǎn)坐標(biāo) V 。之所以被固定的點(diǎn)沒有絕對(duì)固定而是帶入能量函數(shù)參與擬合，是因 為論

23、文 18 表明如此做在形狀變形領(lǐng)域可以達(dá)到更好的連續(xù)性效果?？梢灶A(yù)期當(dāng)此能量函數(shù)的值達(dá)到最小時(shí)，我們所求得的變換點(diǎn)坐標(biāo) V 是保持模型表面細(xì)節(jié)相對(duì)穩(wěn)定的一組解。對(duì)于以上能量函數(shù)，完全可以用最小二 乘法簡(jiǎn)單地求出其達(dá)到最小值時(shí)的解。雖然求解這個(gè)能量函數(shù)的最小值可以在一定程度上保持形狀變形中圖形表 面的細(xì)節(jié)，但是要注意保持細(xì)節(jié)并不是保持細(xì)節(jié)定向大小等因素不變。況且根 據(jù)定義 2-1 也明顯可知，Laplacian 坐標(biāo)對(duì)于點(diǎn) i 與其 1-鄰域中各點(diǎn)的線性變換 是敏感的。所以當(dāng)參照點(diǎn)進(jìn)行特定的線性變換時(shí)，如圖 2-2，細(xì)節(jié)部分就難以 通過 Laplacian 坐標(biāo)不變來得到恰當(dāng)?shù)谋３至恕D 2.2

24、: 局部線性變換因此，保持 Laplacian 坐標(biāo)不變不是維持模型表面細(xì)節(jié)的最有效手段。為 此我們對(duì)每一個(gè)點(diǎn) i 定義一個(gè)線性變換對(duì) Ti，用其來表示經(jīng)過形狀變形之后的11中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文點(diǎn) i 的 Laplacian 坐標(biāo)的變換情況。明顯的，這些變換是變換之后的圖像各點(diǎn)與其 1-鄰域中各點(diǎn)坐標(biāo)的一個(gè)映射。據(jù)此我們得到能量函數(shù) 2-2 的一個(gè)修正：nn(2-3)E (V ) =jjTi (V ) L (vi) L (vi) jj2 + jjvi uijj2=1i=mi在這個(gè)能量函數(shù)中 Ti 與 V 都是待求解的量，難以直接求解出兩者。但若 將 Ti 表示為 V 的線性函數(shù)的話，這

25、一能量函數(shù)就退化成了二次函數(shù)，就容易 的求解出 V 了。一種比較自然的想法就是，可以考慮導(dǎo)致點(diǎn) i 的 Laplacian 坐標(biāo)發(fā)生線性 變換的 Ti，實(shí)際上可以使點(diǎn) i 與其 1-鄰域中各點(diǎn)坐標(biāo)發(fā)生同樣的線性變換。于是建立如下的能量函數(shù)：E (Ti) = jjTivi vijj2 +jjTivj vjjj2(2-4)jNi如果對(duì) Ti 不加任何限制，這個(gè)能量函數(shù)是不可能有唯一解的。所以要對(duì) 其進(jìn)行限制，我們可以規(guī)定 Ti 這個(gè)變換只包括平移、旋轉(zhuǎn)、各向同性的放縮。這三種變換屬于線性變換，使用齊次坐標(biāo)來表示此過程更加簡(jiǎn)潔有效。于 是我們建立 Ti 變換在齊次坐標(biāo)系下的矩陣。首先，Ti 的旋轉(zhuǎn)與

26、同向放縮部分 可以表示為：T = s exp (H)(2-5)其中 H 為一個(gè)斜對(duì)稱矩陣，三維情況下斜對(duì)稱矩陣對(duì)一個(gè)向量的變換可以表 示成兩個(gè)向量的外積形式：Hx = h x于是等式 2-5 又可以展開為：T = s ( I + H + hT h)(2-6)由于大多數(shù)情況下，形狀變形中進(jìn)行的都是比較連續(xù)的小幅度變化，所以 我們進(jìn)一步限定旋轉(zhuǎn)變換為小角度旋轉(zhuǎn)變換。12中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文于是我們對(duì)于可以省略上式中的二次項(xiàng)，從而得到線性變換 Ti 的一種限定矩陣：sh3h2txTi =h3sh1tyh2h1s tz0010加入了這些限制的 Ti 可以將能量函數(shù) 2-4 簡(jiǎn)化為：E (Ti)

27、 = jjAi (si; hi; ti)T bijj2其中 Ai 為點(diǎn) i 與其 1-鄰域各點(diǎn)坐標(biāo)所形成的的矩陣，其結(jié)構(gòu)是：vkx0vkzvky 100Ai =vky vkz0vkx 010; k 2 fig Nivkzvkyvkx0 001.式中的 si; hi; hi 即是矩陣 2-7 中的幾個(gè)變量。(2-7)(2-8)(2-9)0 bi 則是變換后的點(diǎn) i 與其 1-鄰域各點(diǎn)坐標(biāo)所形成的的向量，其結(jié)構(gòu)是： vkxv kybi =v k.z. ; k 2 fig Ni(2-10)則用最小二乘法處理能量函數(shù) 2-8 則可得到：(si; hi; ti)T = (ATi Ai)1 ATi bi(

28、2-11)自此就可以將 Ti 表示成 V 的線性函數(shù)，帶入能量函數(shù) 2-3 即可得到線性 稀疏矩陣方程組，解這一方程組就可以求得 V ，從而完成整個(gè)保持細(xì)節(jié)的形狀變形。13中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文2.3 Laplacian 編輯的實(shí)現(xiàn) 如圖是 Laplacian 編輯實(shí)際效果演示，下圖為 3Dmax 生成的一個(gè)粗糙化了 的平面，我們將該平面右側(cè)的那條邊向上拉若干距離之后，就生成了右面的新 圖形：(a)(b)圖 2.3: (a) 原粗糙平面 (b) 將之前平面右面的邊上拉之后的生成的新圖形對(duì)比這組圖片，我們可以清晰地看出，Laplacian 編輯在這一曲面的形狀 變形過程中有效的保持了這張曲

29、面的細(xì)節(jié)部分，即是那些突起的部分。下面是一組其他的比較復(fù)雜的模型形變的效果：14中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文(a)(b)圖 2.4: (a) 經(jīng)典的兔子頭模型 (b) 通過下拉兔子耳朵上的一點(diǎn)，帶動(dòng)整個(gè)兔子 左耳進(jìn)行彎曲，可以看出變形保持了兔子耳朵的形狀2.4 Laplacian 編輯的優(yōu)缺點(diǎn)我們所介紹的 Laplacian 編輯應(yīng)用于保細(xì)節(jié)形狀變形中有諸多優(yōu)點(diǎn)：1.Laplacian 編輯可以完成比較好的保持三維模型或二維模型局部形狀以及表面細(xì)節(jié)的形狀變形，完成的效果十分直觀。2.Laplacian 編輯的理論部分簡(jiǎn)潔明了，便于應(yīng)用與移植。3.Lpalacian 編輯的主要計(jì)算內(nèi)容為解一個(gè)大

30、規(guī)模稀疏矩陣線性方程組，對(duì)此已經(jīng)有很成熟的相關(guān)技術(shù)可以快速完成，提高了這一算法的運(yùn)行速度。當(dāng)然我們?cè)谄淅碚撝胁浑y發(fā)現(xiàn)其對(duì)表面細(xì)節(jié)的變化程度控制是模糊的。并 且對(duì)比圖片 2.3 與圖片 2.4 可以發(fā)現(xiàn)在經(jīng)過拉伸之類的變換之后，細(xì)節(jié)部分有 發(fā)生增大的現(xiàn)象。所以 Laplacian 編輯雖然能一定“程度”上保持三角形網(wǎng)格 表面細(xì)節(jié)，但是這個(gè)“程度”卻是不確定的。這便是 Laplacian 編輯的不足之 處，由此也引出了下面的 ARAP 編輯。15中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文第 3 章 ARAP 編輯正如我們?cè)?Laplacian 編輯最后所提及的，對(duì)于很多應(yīng)用于實(shí)際的形狀變 形，能夠保持形狀的穩(wěn)定

31、是十分重要的。提及形狀，對(duì)模型施加剛性屬性在形 狀變形中效果尤其明顯，為了使物體的剛性能夠有效保持，我們就要求變換 本身對(duì)于需要保持的部分只進(jìn)行平移與旋轉(zhuǎn)兩種變換方可。由此，則提出了ARAP 編輯，即 As-Rigid-As-Possible Surface Modeling。3.1 ARAP 局部分析 對(duì)一個(gè)已知的三角形網(wǎng)格 S，設(shè)其上的點(diǎn)的數(shù)量為 n，其上的三角形數(shù)量 為 m。仍取點(diǎn) i 的 1-鄰域，即與點(diǎn) i 直接相連成邊的點(diǎn)的集合，定義為 Ni。點(diǎn) i 的坐標(biāo)設(shè)為 vi。對(duì)網(wǎng)格上每一個(gè)點(diǎn) i，定義該點(diǎn)與其 1-鄰域上各點(diǎn)及他們所組成的邊與三角形所組成的圖形結(jié)構(gòu)為一個(gè)屬于該點(diǎn)的晶格，記

32、作 Ci?？梢詳嘌裕@樣的 晶格結(jié)構(gòu)在一個(gè)三角網(wǎng)格中至少包含一個(gè)三角形結(jié)構(gòu)?；谖覀兌x的晶格結(jié) 構(gòu)，我們先來介紹 ARAP 編輯的局部過程。給定點(diǎn) i 確定的晶格 Ci，對(duì)于整 體的形狀變形其當(dāng)然導(dǎo)致在此晶格的基礎(chǔ)上生成一個(gè)新的晶格 Ci。對(duì)于一個(gè)可 以保持剛性的三角形網(wǎng)格，經(jīng)過形狀變形的過程后兩個(gè)晶格的形狀應(yīng)該是保持 的。就是說變換對(duì)每一個(gè)晶格而言是一個(gè)旋轉(zhuǎn)矩陣 Ri，使得晶格中的邊發(fā)生 等角度的旋轉(zhuǎn)，即：vi vj = Ri (vi vj) ; 8j 2 Ni(3-1)由此建立能量函數(shù)：E (Ci; Ci) =wijjj vi vjRi (vi vj) jj2(3-2)jNi()wij

33、為晶格過中心的邊的權(quán)重，其大小依論文 1920 可以取為wij =1(cot ij + cot ij)(3-3)216中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文ij ; ij 為該邊所在的兩個(gè)三角形對(duì)角的角度，當(dāng)然對(duì)于邊界上的邊，這樣的角 只有一個(gè)。所以這種權(quán)重表示了在晶格中比較短的邊具有比較高的權(quán)重，這對(duì)于穩(wěn)定三角形的形狀是有利的。求解上述能量函數(shù)，我們?cè)O(shè) eij = vi vj，則 我們可以將能量函數(shù)改寫為：E (Ci; Ci) =wij eijRieijT eij RieijjNi() ()= jNi wij (eijT eij 2eijT Rieij + eijTRiT Rieij)(3-4)由于變

34、換限制為旋轉(zhuǎn)變換，當(dāng)然對(duì)于剛性我們不限制晶格結(jié)構(gòu)的平移變換，也可以看到對(duì)于單晶格而言整體同程度平移變換對(duì)此能量函數(shù)的大小沒有任何影響。所以第一項(xiàng)與第三項(xiàng)實(shí)際上是相等并且在能量函數(shù)中處于不變的狀態(tài)，只需考慮第二項(xiàng)達(dá)到最小即可使能量函數(shù)達(dá)到最小，于是如下：argmin2wij eijT Rieij = argmaxwijeijT RieijjNijNi= argmax Tr (wijRieij eijT )jNi= argmax Tr (Riwijeij eijT )(3-5)jNi定義:Si = wij eijeijT = PiDiP iT(3-6)jNi矩陣，P 是以 e其中 D是 wij形成

35、的對(duì)角陣，P是以 eij為列的 3jNijiiiij為列的 3 jNij 矩陣。這樣求 3-5 就變成了求 Tr (RiSi) 的問題，當(dāng) RiSi 為對(duì) 稱半正定矩陣時(shí)上式取得最大值。因此對(duì) Si 進(jìn)行奇異值分解，即：Si = Ui iV T(3-7)i于是可得：Ri = ViUiT(3-8)17中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文從而，我們求出了變換對(duì)于點(diǎn) i 決定的晶格結(jié)構(gòu)的旋轉(zhuǎn)近似矩陣。這也就是局部分析的目的。3.2 ARAP 整體處理 經(jīng)過之前逐點(diǎn)建立晶格并分析之后，可以進(jìn)行整體結(jié)構(gòu)的處理了。由于目的是對(duì)整體的保剛性變換，所以比較自然的想到如下表面形狀能量函數(shù)：nnwij jj vi vjR

36、i (vi vj) jj2 (3-9)E (S) = wiE (Ci; Ci) =wii=1i=1jNi)(這一能量函數(shù)達(dá)到最小時(shí)，整個(gè)三角形網(wǎng)格的全部晶格得到最大限度的剛性保持。式中的權(quán)值 wi 依照前面權(quán)值的選法可以定義為：wi =1(3-10)Ni這樣可以加大邊數(shù)較少的晶格的權(quán)值。也可以選 1 作為權(quán)值，因?yàn)榫W(wǎng)格內(nèi)部的 晶格邊數(shù)類似而邊界上的晶格的剛性對(duì)整體而言影響不十分明顯。然后對(duì)整個(gè)圖形的保持剛性的變換就轉(zhuǎn)化成了求以上能量函數(shù)的最小值得 問題，則：E (S)(=wij jj vi vjRi (vi vj) jj2vivijNi()+wjijj vj viRj (vj vi) jj2)

37、jNi()=jNi2wijvi vj Ri (vi vj )()+2wjivj viRj (vj vi)jNi()= j4wij (vi vj)1(Ri + Rj ) (vi vj)(3-11)Ni218中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文這組等式的左邊為我們求解的變形之后的點(diǎn)的坐標(biāo)的線性組合，右邊為已知量。再加上參照點(diǎn)的限制條件：vi = ui; i 2 fm; :; ng; m < n則構(gòu)成了一組大規(guī)模稀疏矩陣線性方程組，求解此方程組即可完成對(duì)剛性變換 的求解。從之前的局部分析中我們發(fā)現(xiàn)，在那一步驟中 V 是作為已知量出現(xiàn)的， 這就是說這種 ARAP 編輯本身需要另一種編輯作為提前演算部分，

38、通?？梢?選擇之前已經(jīng)研究過的 Laplacian 編輯作為這一演算步驟。如此則 ARAP 可視 為一種形狀變形之后的剛性修正，我們甚至可以通過多次迭代這種修正來達(dá)到 更好的保持剛性的效果。這也就是為什么我們說這種 ARAP 編輯要以之前的Laplacian 編輯做基礎(chǔ)了。3.3 ARAP 編輯的實(shí)現(xiàn) 如圖是之前展示的粗糙化了的平面，我們通過本章所介紹的 ARAP 編輯將此圖形以之前 Laplacian 編輯時(shí)同樣的方式進(jìn)行形狀變形：(a)(b)圖 3.1: (a) 原粗糙平面 (b) 將之前平面右面的邊上拉之后的生成的新圖形19中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文同樣地，用對(duì)稍復(fù)雜的兔子頭模型的效果

39、：(a)(b)圖 3.2: (a) 兔子頭模型 (b) 通過下拉兔子耳朵上的一點(diǎn)，帶動(dòng)整個(gè)兔子左耳進(jìn) 行彎曲可見 ARAP 編輯也可以完成有效的保持圖形的細(xì)節(jié)的變換。至于 Lapla-cian 編輯與 ARAP 編輯的差異之處，將在下一部分中討論。3.4 ARAP 編輯的特點(diǎn) 首先，ARAP 編輯是可以有效的完成保持網(wǎng)格剛性的變換。然后，對(duì)比 Laplacian 編輯與 ARAP 編輯的實(shí)現(xiàn)結(jié)果圖 2.5(b) 與 3.3(b)，后者在細(xì)節(jié)方面的剛性程度保持上的要強(qiáng)一些。下面提供一組更加直觀的結(jié)果。下圖展示了之前的粗糙平面的網(wǎng)格結(jié)構(gòu)，分別以 Laplacian 編輯和 ARAP編輯完成形狀變形

40、的效果：20中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文(a)(b)(c)(d)(e)圖 3.3: (a) 原粗糙曲面的網(wǎng)格結(jié)構(gòu) (b)(c) 網(wǎng)格進(jìn)行 Laplacian 編輯之后的網(wǎng)格 結(jié)構(gòu)圖 (d)(e) 網(wǎng)格進(jìn)行 ARAP 編輯之后的網(wǎng)格結(jié)構(gòu)圖可 以 看 出 Laplacian 編 輯 完 成 形 變 后 網(wǎng) 格 內(nèi) 部 的 三 角 形 結(jié) 構(gòu) 明 顯 不 均 勻，邊緣的三角形得到相當(dāng)?shù)呐蛎?，而向?nèi)則受到擠壓。其中的原因一是Laplacianb 編輯是不限制放縮的形變算法，而 ARAP 則只允許平移旋轉(zhuǎn)兩種 變換；二是有邊界的網(wǎng)格邊緣與內(nèi)部的點(diǎn)的 Laplacian 坐標(biāo)所保存的信息量有21中國科學(xué)技

41、術(shù)大學(xué)本科畢業(yè)論文差距，邊緣的點(diǎn)的權(quán)值小于中間的點(diǎn)。所以對(duì)邊緣會(huì)造成更大程度的扭曲。ARAP 編輯是要基于其他編輯協(xié)同工作的，所以其第一個(gè)特點(diǎn)就是依賴于 先前演算所選用編輯的效果，如果之前的編輯效果很差，則即使再進(jìn)行 ARAP編輯修正也不能得到很好的效果；而如果之前的編輯效果十分顯著，細(xì)節(jié)部分 的結(jié)構(gòu)十分好的保持下來的話，則至少通過多次進(jìn)行 ARAP 部分的修正之后，也會(huì)得到效果細(xì)節(jié)部分保持良好的剛性效果強(qiáng)的模型。如下面這組例子可以十分明顯的驗(yàn)證此問題：(a)(b)(c)圖 3.4: (a) 原兔子頭模型 (b) 兔子頭模型以未經(jīng)過 T 修正的 Laplacian 編輯作 為基礎(chǔ)的 ARAP

42、編輯進(jìn)行變形 (c) 兔子頭模型以完整的 Laplacian 編輯作為基 礎(chǔ)的 ARAP 編輯進(jìn)行變形顯而易見的，分別提供兩種初始編輯并用 ARAP 修正的等同于前文的操 作產(chǎn)生了明顯不同的效果，后者兔子耳朵的結(jié)構(gòu)保持得十分出色，前者則發(fā)生 了較大的變化。另外，由于第二次解方程組的系數(shù)矩陣需要實(shí)時(shí)構(gòu)建，所以運(yùn)行速度上會(huì) 有些不足，對(duì)于特別大的網(wǎng)格會(huì)較難實(shí)現(xiàn)。22中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文第 4 章 總結(jié)與延伸4.1 總結(jié) 綜上所述，我們研究了兩種十分有效的網(wǎng)格保細(xì)節(jié)形狀變形的算法:Lapla-cian 編輯與 ARAP 編輯。在第二章開始，我們?cè)敿?xì)的探討了 Laplacian 編輯的全過程。

43、這里我們首先建立了關(guān)于區(qū)域內(nèi)各點(diǎn)的 Laplacian 坐標(biāo)，即是鄰域重心到點(diǎn)的向量。然后建立了保持 Laplacian 坐標(biāo)均勻變化的能量函數(shù) 2-3?；诖四芰亢瘮?shù)，我們進(jìn)一步討論了如何求解以達(dá)到導(dǎo)出形變后個(gè)點(diǎn)坐標(biāo)的方法。然后我們給出了求解的結(jié)果以及實(shí)際中應(yīng)用 Laplacian 編輯的效果。最后我們分析了 Laplacian 的特點(diǎn)，從而引出了 ARAP 編輯。對(duì)于 ARAP 編輯，我們?cè)诘谌轮羞M(jìn)行解釋。首先，建立晶格這一種平凡的結(jié)構(gòu)體。然后，將 Laplacian 變換的結(jié)果用晶格的平移與旋轉(zhuǎn)變換進(jìn)行近似。然后建立整體剛性能量函數(shù)，求解來達(dá)到剛性修正的目的。最后我們對(duì)比了 Lapla

44、cian 編輯與 ARAP 編輯的不同之處，指出了兩者的優(yōu)勢(shì)與不足。我們?cè)谥拔恼轮幸呀?jīng)表明，Laplacian 編輯與 ARAP 編輯在完成形狀變形的同時(shí)都具有相當(dāng)?shù)谋＜?xì)節(jié)水平。對(duì)于 Laplacian 編輯，其具有運(yùn)算速度快，結(jié)果較直觀，移植較簡(jiǎn)單等諸多優(yōu)點(diǎn)，但是在完成形變后保持的細(xì)節(jié)部分不具有可控制性。而 ARAP 編輯，雖然其完成的變換可以盡可能的保持網(wǎng)格細(xì)節(jié)部分的剛性，但是運(yùn)算速度卻跟不上日益巨大的網(wǎng)格容量。4.2 延伸 之前所提到的剛性保持與否更多意義上應(yīng)該是實(shí)際模型的材質(zhì)決定的。我們可以這樣看待這兩種編輯算法：Laplacian 編輯可以看成是對(duì)中空的氣球進(jìn)行操作的變換，而 AR

45、AP 編輯則可以視為對(duì)保持實(shí)心的橡皮泥進(jìn)行操作的變換。這樣而言兩者則是分別達(dá)到了兩種不同的實(shí)際效果。23中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文所以，形狀變形中保持細(xì)節(jié)的相關(guān)問題的另一個(gè)重要課題可以是材質(zhì)的定量建模，類似于光照與反射材料模型、液體流動(dòng)速度與液體屬性模型等等。所以未來的發(fā)展方向可以是設(shè)計(jì)一種可靈活調(diào)節(jié)細(xì)節(jié)部分變化方向及變化大小的編輯形式，以達(dá)到在形狀變形這一問題中更加確切的控制細(xì)節(jié)變化程度的目的。24中國科學(xué)技術(shù)大學(xué)本科畢業(yè)論文參考文獻(xiàn)1 Sorkine O.，Cohen-Or D.，Lipman Y.，Alexa M.，Rossl C.，Seidel H.-P. Laplacian Sur

46、face Editing. Technical report. 2004. 2 Sorkine O.，Alexa M. As-Rigid as Possible Surface Modeling. Technical report. 2007. 3 Zorin D.，Scgroder P.，Sweldend W. Interactive multiresolution mesh edit-ing. In Proceedings of ACM SIGGRAPH. 1997. 4 Guskov I.，Sweldens W.，Schroder P. Multiresolution signal processing for meshes. In Proceedings of ACM SIGGRAPH. 1999. 5 Welch W.，Witkin A. Free-Form shape design using triangulated surfaces. In Proceedings of SIGGRAPH. 2000. 6 Taubin G. A