一個(gè)三角形網(wǎng)格的變形(Deformation)算法應(yīng)該滿足下面兩個(gè)基本條件
- 能夠隱藏于交互界面之后
- 效率足夠高以滿足交互需求
將曲面S變形為曲面S'的過程可以描述為：給定一個(gè)位移函數(shù)(Displacement Function)，該函數(shù)輸入曲面上的點(diǎn)p∈S，給出一個(gè)位移向量(Displacement Vector)——d(p)，并通過以下方式將曲面S映射為變形后的曲面S'
對(duì)于離散的三角形網(wǎng)格，位移函數(shù)d是分段線性(Piecewise Linear)的，即對(duì)于pi∈S
為了人為的控制變形的過程，我們常常會(huì)在網(wǎng)格上指定一些控制點(diǎn)pi∈H?S，然后固定網(wǎng)格的一部分F?S，對(duì)于這些點(diǎn)，其位移函數(shù)可以描述為
下圖中我們對(duì)一個(gè)正方形的曲面S進(jìn)行變形，固定曲面S淺藍(lán)色的部分F，然后選取黃色部分H的頂點(diǎn)作為控制頂，將其向上拉動(dòng)。可以看到經(jīng)過變形后，沒有被固定的部分(R，即深藍(lán)色部分)的頂點(diǎn)的位置發(fā)生了相應(yīng)的變換。
一個(gè)主要的問題就是如何選取合適的位移函數(shù)di，使得變形的結(jié)果符合需求。這里將會(huì)討論兩大類變形的方法
基于曲面的變形(Surface-Based Deformations)：位移函數(shù)d是從曲面S到三位空間的映射，即計(jì)算時(shí)在三角形網(wǎng)格上進(jìn)行的。這類方法能夠有很高的控制度，能夠?qū)γ恳粋€(gè)頂點(diǎn)都加以控制，但是其魯棒性不好，運(yùn)行效率往往取決網(wǎng)格的的復(fù)雜度和質(zhì)量。
空間變形(Space Deformations)：位移函數(shù)d是從三維空間到三位空間的映射，即對(duì)曲面S的變形是隱式的。因?yàn)橛?jì)算不依賴于三角形網(wǎng)格曲面S，所以其不受網(wǎng)格復(fù)雜度和質(zhì)量的影響。
這里討論的大部分方法都是線性的方法，通常只需要解線性方程，即最小化二次能量能量(Quadratic Deformation Energy)。使用線性系統(tǒng)的優(yōu)點(diǎn)在于求解的效率高，缺點(diǎn)是有些時(shí)候得到的結(jié)果是不符合直觀的。非線性的方法通過最小化更為精確的變形能量，能夠達(dá)到更好的效果，但是求解效率確不高。
Transformation Propagation
一個(gè)常用且簡(jiǎn)單的方法是將對(duì)控制點(diǎn)的變換傳播到整個(gè)變形區(qū)域上。在指定好控制點(diǎn)H和變形區(qū)域R后，控制點(diǎn)由用戶控制發(fā)生變換T，然后將變換T插值傳播至變形區(qū)域R上，使得從固定區(qū)域F至變換后控制點(diǎn)所在的區(qū)域H'的變化是平滑的。
兩者間的插值混合可以由一個(gè)標(biāo)量場(chǎng)s進(jìn)行控制
s=1代表頂點(diǎn)處于控制區(qū)域H(區(qū)域內(nèi)的頂點(diǎn)被完全變換)，s=0代表頂點(diǎn)處于固定區(qū)域F(區(qū)域內(nèi)的頂點(diǎn)不發(fā)生變換)，而位于變換區(qū)域R內(nèi)的頂點(diǎn)的s值則由頂點(diǎn)到區(qū)域F和區(qū)域H的距離決定
距離既可以是測(cè)地線距離也可是歐氏距離，前者計(jì)算更復(fù)雜但是結(jié)果的效果更好。
另外標(biāo)量場(chǎng)s也能夠是曲面S上的調(diào)和場(chǎng)(無(wú)源無(wú)旋)，即其滿足拉普拉斯方程
對(duì)于區(qū)域F和H我們加以狄利特雷限制(Dirichlet Constraint)，然后解下列線性拉普拉斯方程即可得到標(biāo)量場(chǎng)s。
雖然此法性能遜于前者，但是能夠保證結(jié)果足夠光滑，而前者基于距離的方法只能保證C1連續(xù)。
標(biāo)量場(chǎng)s還能夠進(jìn)行進(jìn)一步的調(diào)整以提供更多的控制和靈活度。
得到標(biāo)量場(chǎng)后，對(duì)每一個(gè)頂點(diǎn)按以下方法進(jìn)行插值運(yùn)算，即可得到變形后頂點(diǎn)的位置。
不過此法存在一個(gè)問題，得到結(jié)果并不是幾何上最直觀的結(jié)果，還需要對(duì)控制區(qū)域H內(nèi)的頂點(diǎn)的位移函數(shù)d進(jìn)行平滑處理，或者使用最小化某些基于物理量的變形能量的方法。
Shell-Based Deformation
為了得到更直觀準(zhǔn)確的結(jié)果，位移函數(shù)d可以通過最小化基于物理的變形能量的方法得到。我們間曲面S看作是能夠拉伸(Stretching)或者彎折(Bending)的物理材質(zhì)(皮膚、布料等)，然后使用能量函數(shù)來描述拉伸和彎折的程度。
設(shè)參數(shù)曲面S和S'，曲面由方程p:Ω→R3、p':Ω→R3給出，且位移函數(shù)被定義為d:Ω→R3。第一基本型和第二基本型能夠被用來衡量曲面的內(nèi)在幾何量(如長(zhǎng)度、面積和曲率等)。當(dāng)曲面S被變形為S'時(shí)，其基本型由Ⅰ、Ⅱ變?yōu)榱?strong>Ⅰ'、Ⅱ'，它們的差可以用來描述拉伸和彎折(原文中稱這種能量為Elastic Thin Shell Energy)
剛度參數(shù)(Stiffness Parameters)ks和kb被用來控制曲面對(duì)拉伸和彎折變換的抵抗程度。在實(shí)際應(yīng)用時(shí)只需要在變形的區(qū)域最小化上述能量即可。
但是上式由于是非線性的，計(jì)算量較大，無(wú)法應(yīng)用的到交互式的程序中。所以通常將基本型簡(jiǎn)化為位移函數(shù)d的偏導(dǎo)數(shù)(位置之差)，得到下樹的Thin Shell Energy
其中
這個(gè)函數(shù)和前面介紹平面平滑算法里Fairing方法中衡量曲面面積和曲率的能量的函數(shù)相類似。區(qū)別在于這里我們使用平移量d而不是位置p且最小化的是面積和曲率的變換程度，即我們最小化曲面的拉伸和彎折。
下圖中，我們固定灰色區(qū)域，抬升黃色區(qū)域，并且最小化Thin Shell Energy。該能量包含拉伸和彎折兩個(gè)部分，左圖展示了純拉伸的情況(ks = 1, kb = 0)，中圖展示了純彎折的情況(ks = 0, kb = 1)，右圖展示了兩者混合的情況(ks = 1, kb = 10)。
應(yīng)用曲面平滑算法里Fairing方法中提到求最小化的方法，得到能量函數(shù)對(duì)應(yīng)的歐拉拉格朗日方程
為了最小化能量，需要解上述的偏微分方程(PDE)，根據(jù)第三章中介紹的方法，將上式子寫成離散形式，其中
則上述偏微分方程(PDE)可以被離散為下面逐頂點(diǎn)形式
其中變換區(qū)域R內(nèi)自由頂點(diǎn)的位移函數(shù)d1,...dn是未知的(方程左側(cè)x項(xiàng))，區(qū)域H和區(qū)域F中位移函數(shù)是已知的(方程右側(cè)b項(xiàng))。
L為拉普拉斯矩陣，x和b都是n行3列的矩陣。
最小化得到結(jié)果是C1連續(xù)的，在三角形網(wǎng)格中C1連續(xù)只由區(qū)域F和H中First-Two-Rings頂點(diǎn)定義，在最小化的時(shí)候不用考慮F和H區(qū)域上其它的頂點(diǎn)。
在交互的過程中會(huì)控制區(qū)域H內(nèi)的頂點(diǎn)進(jìn)行操作，使得矩陣方程的右側(cè)的b項(xiàng)不斷發(fā)生變換，這個(gè)情況有更加高效的算法。通過變換限制為仿射變換，也能夠?qū)⒛承┯?jì)算提前進(jìn)行預(yù)計(jì)算以提高效率。
與Transformation Propagation方法相比，此法由于需要每一幀解一個(gè)線性方程，計(jì)算量相對(duì)較大，但是仍然是可交互的。由于此法基于物理法則，故其效果相對(duì)較好。
Multi-Scale Deformation
前文的Shell-Based Deformation方法并不能夠正確地處理小尺度的細(xì)節(jié)。由于對(duì)局部細(xì)節(jié)的旋轉(zhuǎn)變換并不是線性的，所以不能夠完全的使用線性的方法對(duì)其進(jìn)行建模。一個(gè)更好的方法是使用后面即將介紹的多尺度變形的方法。
下圖中，我們抬升正方形曲面的右側(cè)，左二圖展示了使用前文中的線性方法得到的結(jié)果，發(fā)現(xiàn)其細(xì)節(jié)并沒有被正確的還原。使用Multi-Scale Deformation方法得到結(jié)果(左三圖)雖然仍然有變形，但是已經(jīng)和理想的情況(左四圖)非常接近了。
Multi-Scale Deformation的主要思想是使用在曲面平滑算法中提到的分解的方法將曲面分解為高頻和低頻兩個(gè)部分。低頻部分即是曲面大致的外形，而高頻部分則代表小尺度的細(xì)節(jié)。我們的目標(biāo)是對(duì)低頻部分進(jìn)行變形并保持高頻部分的細(xì)節(jié)。
這個(gè)過程在2維情況下如下圖所示，虛線部分表示了曲線的低頻部分，我們將這條虛線進(jìn)行變形并添加上高頻細(xì)節(jié)，最終得到了理想的形變結(jié)果。
在三維的情況下，首先通過移除高頻部分計(jì)算出曲面S的低頻形式B(原模型的光滑簡(jiǎn)化形式)，在B上模型的細(xì)節(jié)D被移除。將B形變得到B'，通過B'和D我們能夠重建出最終的變形后的曲面S'。
上圖中我們只對(duì)原模型進(jìn)行了一次分解，同樣地也可以對(duì)B再一次進(jìn)行分解，以達(dá)到多吃變形的目的。
可以看到Multi-Scale Deformation主要包含下面三個(gè)操作
- 分解(Decomposition)
- 變形(Deformation)
- 重建(Reconstruction)
其中分解可以使用到第四章提到的網(wǎng)格光滑算法，變形可以使用前文提到的算法。沒有提到的就是如何提取細(xì)節(jié)D并進(jìn)行相應(yīng)的重建。
位移向量(Displacement Vectors)
最直接的表示方法就是使用一個(gè)向量函數(shù)h:B→R3，函數(shù)h(p)表示光滑曲面B上每一個(gè)頂點(diǎn)都對(duì)應(yīng)著一個(gè)三維向量。由于S和B擁有相同的連接性，所以位移向量
其中bi∈B，pi∈S。
使用全局坐標(biāo)系取表示位移向量得到結(jié)果如下圖左圖所示，正確的方法是使用局部的基向量去表示位移向量(下圖右圖)。
因此在存儲(chǔ)hi時(shí)，需要使用曲面B上每個(gè)頂點(diǎn)的局部標(biāo)價(jià)下的坐標(biāo)而不是全局坐標(biāo)。我們一般取法向量ni和另外兩個(gè)向量t(i,1)和t(i,2)作為一組正交基
基向量在從B變形到B'的過程中會(huì)發(fā)生相應(yīng)的旋轉(zhuǎn)，最終我們根據(jù)B'的基向量以及位移向量在B中局部坐標(biāo)基下的坐標(biāo)可以得到S'上每一個(gè)頂點(diǎn)的坐標(biāo)
法向量ni在每一個(gè)頂點(diǎn)上都是有定義的，剩下的只需要按照統(tǒng)一的標(biāo)準(zhǔn)取另外兩個(gè)軸ti,1和ti,2即可。
法向量位移(Normal Displacements)
當(dāng)位移向量過長(zhǎng)的時(shí)候會(huì)導(dǎo)致結(jié)果不穩(wěn)定，特別是在進(jìn)行彎折(Bending)變形的時(shí)候，因此位移向量應(yīng)該越短越好。因此，我們想到不再去尋找B上pi的對(duì)應(yīng)頂點(diǎn)bi，而是去尋找B上距離p最近的頂點(diǎn)。
這種思想就是所謂的法向量位移，即
因?yàn)樵谏弦还?jié)中hi通常是不與法向量平行的，因此法向量位移方法需要對(duì)S和B上的頂點(diǎn)進(jìn)行重新采樣，從bi∈B上發(fā)射一條與法向量平行的射線以找到其在S上對(duì)應(yīng)的頂點(diǎn)pi，而重采樣則會(huì)導(dǎo)致Alias Artifacts(走樣/假頻)現(xiàn)象的出現(xiàn)。
為了改進(jìn)上面的方法，我們換一個(gè)方向。對(duì)于點(diǎn)pi∈S，我們尋找一個(gè)點(diǎn)bi∈B，且pi-bi與bi的法向量平行，而bi是曲面B上的任意一點(diǎn)，該點(diǎn)處于B上某一個(gè)三角形(a, b, c)∈B之中，因此bi可以表示為下列重心坐標(biāo)的形式
其法向量同樣可以由重心坐標(biāo)插值得到
而尋找點(diǎn)b的過程，可以使用牛頓迭代法求解下面方程的根
整個(gè)過程大致為，首先尋找離pi最近的三角形，如果在進(jìn)行牛頓迭代的過程中重心坐標(biāo)出現(xiàn)了負(fù)值，則分別對(duì)其相鄰的三角形進(jìn)行處理。
一旦得到了三角形(a, b, c)和重心坐標(biāo) (α, β, γ)，則可以通過變形后的曲面B'計(jì)算出S'上每一個(gè)頂點(diǎn)pi的坐標(biāo)
這樣避免了對(duì)曲面進(jìn)行重采樣，從而使得某些尖銳細(xì)小的特征(Sharp Features)得到保留。因?yàn)辄c(diǎn)bi是曲面B上的任意一點(diǎn)，因此對(duì)于曲面S和B來說，其連接性并不一定要求是已知的。我們可以利用這一點(diǎn)來對(duì)曲面B進(jìn)行重采樣以獲得更高的數(shù)值魯棒性。
位移向量和法向量位移的長(zhǎng)度的不同通常取決于曲面B和曲面S相差的程度，對(duì)于例子
位移向量的長(zhǎng)度平均比法向量位移的長(zhǎng)度要長(zhǎng)9倍。除了長(zhǎng)度更短法向量位移也不需要進(jìn)行啟發(fā)式的計(jì)算(計(jì)算坐標(biāo)基t的過程)。
法向量位移的方法效率極高，但是其主要的問題在于相鄰的頂點(diǎn)的位移向量之間并沒任何聯(lián)系。當(dāng)彎折(Bending)程度較大的時(shí)候，會(huì)導(dǎo)致細(xì)節(jié)部分出現(xiàn)非預(yù)期的結(jié)果。在極端情況曲面可能還能出現(xiàn)自相交的情況(當(dāng)B'的曲率比位移長(zhǎng)度hi要大的時(shí)候)。
下面的兩種算法正是為了改進(jìn)上述情況而提出的
Displacement Volumes：曲面S和曲面B對(duì)應(yīng)的兩個(gè)三角形(pi, pj, pk)和(bi, bj, bk)組成了一個(gè)棱柱體，該棱柱體的體積被用來作為細(xì)節(jié)D，在變形的過程中保持不變。對(duì)于變形的曲面B'，重建的過程是找到一個(gè)曲面S'使得其每一個(gè)棱柱體的體積都和原來的相等。這樣會(huì)使得結(jié)果根據(jù)直觀合理且避免了自相交的情況，缺點(diǎn)是該方法在重建的過程中計(jì)算量較大。
Deformation Transfer：原書中沒有詳細(xì)介紹該算法，可以參考這篇論文Deformation Transfer for Detail-Preserving Surface Editing。該算法在最終效果和運(yùn)行效率上取了一個(gè)折中，只需要解一個(gè)疏松的泊松方程即可。
Differential Coordinates
盡管前面的Multi-Scale Deformation方法效率高，且能夠保存模型中的細(xì)節(jié)，但是如何生成一個(gè)合理的層級(jí)結(jié)構(gòu)確是一個(gè)相當(dāng)復(fù)雜的過程。為了避免Multi-Scale Deformation中分解的過程，另外一類方法采用了修改曲面的微分屬性而不是空間坐標(biāo)的方法來重建變形后的曲面。
Gradient-Based Deformation
對(duì)于原始網(wǎng)格上每一個(gè)頂點(diǎn)上某個(gè)標(biāo)量值，都可以找到對(duì)應(yīng)的分段線性函數(shù)
其梯度是一個(gè)常向量(每一個(gè)三角形T對(duì)應(yīng)一個(gè)常向量)
同樣地，考慮以下三維的情況
則對(duì)應(yīng)每個(gè)三角形T，它的梯度是一個(gè)3*3的雅可比矩陣
參考第三章中介紹的方法，可以計(jì)算出矩陣中的各個(gè)位置上梯度函數(shù)的值。
接下來對(duì)每一個(gè)三角形的梯度JT進(jìn)行變形，即乘以一個(gè)3*3的變換矩陣(旋轉(zhuǎn)、縮放/錯(cuò)切) MT
MT是根據(jù)對(duì)控制點(diǎn)的變換得到，具體的方法會(huì)在后文中介紹。
剩下的步驟就是在盡量保持每一個(gè)三角形梯度不變得情況下，尋找每個(gè)頂點(diǎn)的新的位置。
如下圖所示，黃色區(qū)域?yàn)榭刂泣c(diǎn)所在區(qū)域，原模型為圓柱體表面(左圖)，我們對(duì)變換區(qū)域(藍(lán)色區(qū)域)上每一個(gè)三角形施以對(duì)控制點(diǎn)相同的變換，這將使得模型“裂開”(中圖)，然后改變每一個(gè)三角形的位置且盡量保持三角形的朝向不變，最終得到了變形后的模型(右圖)。
這個(gè)過程即是最小化下列的能量函數(shù)
f是待尋找的方程，g是目標(biāo)梯度場(chǎng)。為了最小化上式子，應(yīng)用變分法解下列歐拉拉格朗日方程
用目標(biāo)的的x, y, z坐標(biāo)代替f，并用離散拉普拉斯算子和離散散度算子對(duì)原方程離散化得到線性方程
為了使得方程有解(系統(tǒng)非奇異)，需要將固定一些點(diǎn)p'i，如示意圖中黃色的控制區(qū)域H內(nèi)的頂點(diǎn)(這也就是上面的示意圖的中圖里黃色區(qū)域的控制點(diǎn)的位置被直接修改的原因)、示意圖中灰色的固定區(qū)域F內(nèi)的頂點(diǎn)。
解上述方程只需要解一個(gè)輸送的泊松方程，比前面的Shell-Based Deformation效率略高。另外，泊松方程在邊界處只是C0連續(xù)的，但是Shell-Based Deformation是C1連續(xù)的。
Laplacian-Based Deformation
Laplacian-Based Deformation與Gradient-Based Deformation方法類似，不過其目標(biāo)不再是逐三角形的梯度，而是逐頂點(diǎn)拉普拉斯坐標(biāo)。
我們首先計(jì)算每個(gè)頂點(diǎn)的拉普拉斯坐標(biāo)，然后乘以變換矩陣M，最后尋找新的頂點(diǎn)坐標(biāo)去你和目標(biāo)拉普拉斯坐標(biāo)。
這個(gè)過程中最小化能量函數(shù)為
對(duì)應(yīng)的歐拉拉格朗日方程為
上式離散化后得到下列方程
在解方程的時(shí)候同樣的需要固定一些頂點(diǎn)。需要注意的是，拉普拉斯算子的離散形式有Uniform和Cotangent兩種，對(duì)于不規(guī)則網(wǎng)格使用后者得到的結(jié)果效果會(huì)更好一些。
Laplacian-Based Deformation方法和Shell-Based Deformation方法之間是存在聯(lián)系的。忽略掉Laplacian-Based Deformation中對(duì)拉普拉斯坐標(biāo)的變換，使用原始的拉普拉斯坐標(biāo)來計(jì)算新的頂點(diǎn)的位置，在Shell-Based Deformation中固定相同的頂點(diǎn)且原始頂點(diǎn)相同，兩者都能得到相同的歐拉拉格朗日方程
則最終得到相同的結(jié)果。
如何得到變換矩陣M
那么前面兩種方法中都使用到了變換矩陣M，這一節(jié)將會(huì)討論如何根據(jù)對(duì)控制點(diǎn)的變換得到逐頂點(diǎn)和逐面(三角形)的變換矩陣
Propagation Of Deformation Gradients
第一種方法和之前提到的Transformation Propagation中插值的方法類似，這里我們對(duì)變換的梯度進(jìn)行插值。通常我們是按照下面的方式對(duì)控制點(diǎn)進(jìn)行仿射變換
T(x)的梯度是一個(gè)3*3的矩陣 M，該矩陣代表了對(duì)控制點(diǎn)的旋轉(zhuǎn)、縮放/錯(cuò)切變換。
需要注意的是，旋轉(zhuǎn)變換的插值與縮放/錯(cuò)切變換不同，需要對(duì)變換矩陣進(jìn)行極分解(Polar Decomposition)。
首先對(duì)M進(jìn)行奇異值分解，得到
然后就能得到M矩陣中旋轉(zhuǎn)的部分和縮放/錯(cuò)切的部分
因?yàn)?strong>U和V是正交矩陣，所以有
然后我們對(duì)旋轉(zhuǎn)部分是slerp插值，對(duì)縮放/錯(cuò)切的部分使用線性插值，得到逐頂點(diǎn)的變換矩陣Mi
對(duì)于逐面(三角形)，其插值的因子s是三角形T的三個(gè)頂點(diǎn)對(duì)應(yīng)的值si, sj, sk的平均值。需要注意的是，平移變換t并不會(huì)改變梯度和拉普拉斯坐標(biāo)的值，所以當(dāng)變換中包含有距離較大的平移變換的時(shí)候會(huì)產(chǎn)生不符合預(yù)期的結(jié)果。
Implicit Optimization
通過最小化下面能量函數(shù)，Implicit Optimization同時(shí)對(duì)新的頂點(diǎn)坐標(biāo)p'i以及旋轉(zhuǎn)矩陣Mi進(jìn)行優(yōu)化
其中Ai是頂點(diǎn)的局部面積，Mi和新頂點(diǎn)的位置有關(guān)。注意這個(gè)過程中同樣需要固定區(qū)域H和區(qū)域F中的頂點(diǎn)。
為了避免非線性最優(yōu)化(Nonlinear Optimization)(這是剛體變換Mi中必須滿足的)，局部變換被限制為相似線性變換(Linearized Similarity Transformation)，Mi被寫成下面的斜對(duì)稱矩陣
參數(shù)si和hi(位移向量)是由下列限制條件決定
通過p'i的線性組合可以得到si和hi。
書中對(duì)該部分介紹省略了很多，詳細(xì)的內(nèi)容可以參考這篇論文：Laplacian Surface Editing
需要注意的一點(diǎn)是，根據(jù)拉普拉斯坐標(biāo)的性質(zhì)，其對(duì)旋轉(zhuǎn)敏感，所以網(wǎng)格的局部信息會(huì)發(fā)生旋轉(zhuǎn)扭曲，且旋轉(zhuǎn)尺度較大是，扭曲會(huì)非常嚴(yán)重。
Freeform Deformation
前面討論的所有方法都是基于曲面的(Surface- Based)，它們通過最小化某個(gè)能量函數(shù)在原曲面S上進(jìn)行光滑變形。其計(jì)算過程歸結(jié)起來是解一個(gè)線性系統(tǒng)對(duì)應(yīng)的歐拉拉格朗日方程。
上述方法的一個(gè)明顯的缺點(diǎn)在于其計(jì)算量和數(shù)值魯棒性和網(wǎng)格分割的復(fù)雜度和質(zhì)量相關(guān)。對(duì)于退化的三角形(Degenerate Triangle)其Cotangent形式的拉普拉斯算子是不符合定義的，這會(huì)導(dǎo)致線性系統(tǒng)奇異。同樣地，Gap和非流形的出現(xiàn)使得頂點(diǎn)地局部信息不再一致，也會(huì)導(dǎo)致一些問題。諸如模型修復(fù)或者網(wǎng)格重劃分算法能夠在一定程度上接近這些問題?？v使網(wǎng)格的質(zhì)量足夠高，但是其復(fù)雜過大也會(huì)導(dǎo)致線性系統(tǒng)規(guī)模過大無(wú)法得到其解。
接近這些問題的辦法是使用空間變形(Space Deformations)，它通過對(duì)目標(biāo)模型的周圍空間進(jìn)行變形從而隱式的對(duì)目標(biāo)模型進(jìn)行變形。
與基于曲面的變形(Surface-Based Deformations)不同，空間變形(Space Deformations)的變形是一個(gè)從三維空間到另一個(gè)三維空間的過程。
且d不依賴于特定的曲面，能夠作用用各種顯式表示的曲面(三角形網(wǎng)格的所有頂點(diǎn)、點(diǎn)采樣模型的所有點(diǎn))。
Lattice-Based Freeform Deformation
Freeform Deformation(FFD)中使用3元張量樣條函數(shù)(Trivariate Tensor-Product Spline Function)來表示空間變形
其中Ni是B樣條函數(shù)，δc是控制點(diǎn)c的位移量。
為了簡(jiǎn)化上式，可以將位移項(xiàng)和樣條函數(shù)項(xiàng)記為
最終得到
原網(wǎng)格上的每一個(gè)頂點(diǎn)pi∈S都有一個(gè)對(duì)應(yīng)的的參數(shù)坐標(biāo)ui = (ui, vi, wi)，且
每一個(gè)頂點(diǎn)都會(huì)被施以變換
因?yàn)?strong>d(ui)中的N項(xiàng)是一個(gè)常數(shù)，可以預(yù)計(jì)算，所以其效率較高。
通過操縱樣條控制點(diǎn)(即指定控制點(diǎn)位移δc)就能夠控制模型的變形。和之前提到的方法類似，固定控制區(qū)域H(施加位移向量d之后的位置)和固定區(qū)域F內(nèi)的頂點(diǎn)，然后根據(jù)給定的δc解下列線性方程
由于方程左邊的矩陣不是方陣，所以可以使用最小二乘法的思想，最小化
以及控制點(diǎn)的位移量
不過需要注意兩個(gè)問題，首先如果上述方程是過定的(Over-Determined )，所以限制條件不能被完美地滿足；另外如果是欠定的(Under-Determined)，剩余的自由度是由最小化控制點(diǎn)的位移量決定的，而不是通過光滑算法決定。
樣條函數(shù)N在規(guī)則網(wǎng)格(Regular Grid)上如何放置是另外一個(gè)問題。如果放置不當(dāng)，會(huì)造成Alias Artifacts(走樣/假頻)。通過使用更為靈活的且能夠更好的表示目標(biāo)變形的格子框架能夠在一定程度上解決這個(gè)問題，但是面對(duì)復(fù)雜的變形的時(shí)候，格子框架的選取非常困難。
Cage-Based Freeform Deformation
Cage-Based Freeform Deformation可以被看作是Lattice-Based Freeform Deformation的一般化情況。Cage-Based Freeform Deformation使用控制籠(Control Cage)而不是Lattice-Based Freeform Deformation中使用的規(guī)則的格子框架。這種控制籠通常是包圍著待修改物體的任意三角形網(wǎng)格。相對(duì)于格子框架，其能夠更好的包裹目標(biāo)物體。
原始網(wǎng)格S上的頂點(diǎn)pi能夠表示為控制籠上頂點(diǎn)的線性組合
其中權(quán)重φ是廣義重心坐標(biāo)(Generalized Barycentric Coordinates)，可以取之前方程中的N項(xiàng)。
頂點(diǎn)的權(quán)重φ可以被預(yù)計(jì)算，這樣通過操作控制籠上的頂點(diǎn)
并使用下面的方法計(jì)算逐頂點(diǎn)的位移向量即可
這樣就能比之前使用格子框架能夠更為靈活地進(jìn)行控制。其缺點(diǎn)是由于解是最小范數(shù)解(Least Norm Solution)，所以結(jié)果并不一定是一個(gè)Fair Deformation(不知道怎么翻譯)。
Radial Basis Functions
在Surface-Based Deformations中，通過指定地位移進(jìn)行插值，并且最小化能量函數(shù)得到了相當(dāng)不錯(cuò)的結(jié)果。借用同樣的思想，同樣地，我們可以對(duì)Space Deformation中的函數(shù)
進(jìn)行插值，并且最小化特定的能量函數(shù)?？偟膩碚f，我們的目標(biāo)是找到函數(shù)d，能夠在位置pi根據(jù)指定的位移向量進(jìn)行插值運(yùn)算，且滿足給定的限制條件。Radial Basis Functions(RBFs)正是非常適合這類問題的函數(shù)。其定義為徑向?qū)ΨQ核函數(shù)φ的疊加，其中心為cj，權(quán)重為wj
其中π(x)為保證精度用的多項(xiàng)式項(xiàng)。通常取cj = pj，wj的值為下列方程的解
這樣RBF函數(shù)就能夠被應(yīng)用到頂點(diǎn)上了
而核函數(shù)φ的選擇會(huì)影響到計(jì)算的復(fù)雜度和結(jié)果的質(zhì)量。緊支撐徑向基函數(shù)(Compactly
Supported Radial Basis Functions)會(huì)產(chǎn)生稀疏的線性方程，因此其能夠被用來對(duì)加以很多限制條件的目標(biāo)進(jìn)行插值。其缺點(diǎn)在于效果不如全局支持徑向基函數(shù)(Global Support Radial Basis Functions)。
全局支持徑向基函數(shù)
會(huì)產(chǎn)生一個(gè)三次(??不確定是不是這么翻譯的)調(diào)和函數(shù)(Tri-Harmonic
Function)d
通過變分法可知，需要最小化的能量函數(shù)為
線性方法的局限性
- Shell-Based Deformation結(jié)合Multi-Scale Deformation能在純平移變形時(shí)得到較高質(zhì)量的結(jié)果，且能夠保留相當(dāng)?shù)募?xì)節(jié)。但是由于Shell Energy是線性的，當(dāng)對(duì)物體施以大尺度旋轉(zhuǎn)變形的時(shí)候，結(jié)果會(huì)非常不理想。
- Gradient-Based Deformation使用對(duì)控制點(diǎn)變換的梯度更新每一個(gè)面的梯度，因此在對(duì)物體施以旋轉(zhuǎn)變形的時(shí)候結(jié)果會(huì)非常理想。但是由于局部旋轉(zhuǎn)的顯式傳播(Propagation)是對(duì)平移敏感的，會(huì)導(dǎo)致結(jié)果曲面不夠光滑，并且會(huì)丟失細(xì)節(jié)特征。
- Laplacian-Based Deformation隱式地優(yōu)化了局部旋轉(zhuǎn)，因此相對(duì)來說對(duì)旋轉(zhuǎn)和平移變形更為友好。但是由于需要對(duì)旋轉(zhuǎn)部分線性化，因此在大尺度變形時(shí)會(huì)導(dǎo)致扭曲。
