一個三角形網(wǎng)格的變形(Deformation)算法應該滿足下面兩個基本條件

1. 能夠隱藏于交互界面之后
2. 效率足夠高以滿足交互需求

將曲面S變形為曲面S'的過程可以描述為：給定一個位移函數(shù)(Displacement Function)，該函數(shù)輸入曲面上的點p∈S，給出一個位移向量(Displacement Vector)——d(p)，并通過以下方式將曲面S映射為變形后的曲面S'

對于離散的三角形網(wǎng)格，位移函數(shù)d是分段線性(Piecewise Linear)的，即對于pi∈S

為了人為的控制變形的過程，我們常常會在網(wǎng)格上指定一些控制點pi∈H?S，然后固定網(wǎng)格的一部分F?S，對于這些點，其位移函數(shù)可以描述為

下圖中我們對一個正方形的曲面S進行變形，固定曲面S淺藍色的部分F，然后選取黃色部分H的頂點作為控制頂，將其向上拉動?？梢钥吹浇?jīng)過變形后，沒有被固定的部分(R，即深藍色部分)的頂點的位置發(fā)生了相應的變換。

一個主要的問題就是如何選取合適的位移函數(shù)di，使得變形的結果符合需求。這里將會討論兩大類變形的方法

1. 基于曲面的變形(Surface-Based Deformations)：位移函數(shù)d是從曲面S到三位空間的映射，即計算時在三角形網(wǎng)格上進行的。這類方法能夠有很高的控制度，能夠對每一個頂點都加以控制，但是其魯棒性不好，運行效率往往取決網(wǎng)格的的復雜度和質量。

2. 空間變形(Space Deformations)：位移函數(shù)d是從三維空間到三位空間的映射，即對曲面S的變形是隱式的。因為計算不依賴于三角形網(wǎng)格曲面S，所以其不受網(wǎng)格復雜度和質量的影響。

這里討論的大部分方法都是線性的方法，通常只需要解線性方程，即最小化二次能量能量(Quadratic Deformation Energy)。使用線性系統(tǒng)的優(yōu)點在于求解的效率高，缺點是有些時候得到的結果是不符合直觀的。非線性的方法通過最小化更為精確的變形能量，能夠達到更好的效果，但是求解效率確不高。

Transformation Propagation

一個常用且簡單的方法是將對控制點的變換傳播到整個變形區(qū)域上。在指定好控制點H和變形區(qū)域R后，控制點由用戶控制發(fā)生變換T，然后將變換T插值傳播至變形區(qū)域R上，使得從固定區(qū)域F至變換后控制點所在的區(qū)域H'的變化是平滑的。

兩者間的插值混合可以由一個標量場s進行控制

s=1代表頂點處于控制區(qū)域H(區(qū)域內的頂點被完全變換)，s=0代表頂點處于固定區(qū)域F(區(qū)域內的頂點不發(fā)生變換)，而位于變換區(qū)域R內的頂點的s值則由頂點到區(qū)域F和區(qū)域H的距離決定

距離既可以是測地線距離也可是歐氏距離，前者計算更復雜但是結果的效果更好。

另外標量場s也能夠是曲面S上的調和場(無源無旋)，即其滿足拉普拉斯方程

對于區(qū)域F和H我們加以狄利特雷限制(Dirichlet Constraint)，然后解下列線性拉普拉斯方程即可得到標量場s。

雖然此法性能遜于前者，但是能夠保證結果足夠光滑，而前者基于距離的方法只能保證C1連續(xù)。

標量場s還能夠進行進一步的調整以提供更多的控制和靈活度。

得到標量場后，對每一個頂點按以下方法進行插值運算，即可得到變形后頂點的位置。

不過此法存在一個問題，得到結果并不是幾何上最直觀的結果，還需要對控制區(qū)域H內的頂點的位移函數(shù)d進行平滑處理，或者使用最小化某些基于物理量的變形能量的方法。

原模型(左)；使用插值法計算結果（中）；理想的結果（右）

Shell-Based Deformation

為了得到更直觀準確的結果，位移函數(shù)d可以通過最小化基于物理的變形能量的方法得到。我們間曲面S看作是能夠拉伸(Stretching)或者彎折(Bending)的物理材質(皮膚、布料等)，然后使用能量函數(shù)來描述拉伸和彎折的程度。

設參數(shù)曲面S和S'，曲面由方程p:Ω→R3、p':Ω→R3給出，且位移函數(shù)被定義為d:Ω→R3。第一基本型和第二基本型能夠被用來衡量曲面的內在幾何量(如長度、面積和曲率等)。當曲面S被變形為S'時，其基本型由Ⅰ、Ⅱ變?yōu)榱?strong>Ⅰ'、Ⅱ'，它們的差可以用來描述拉伸和彎折(原文中稱這種能量為Elastic Thin Shell Energy)

剛度參數(shù)(Stiffness Parameters)ks和kb被用來控制曲面對拉伸和彎折變換的抵抗程度。在實際應用時只需要在變形的區(qū)域最小化上述能量即可。

但是上式由于是非線性的，計算量較大，無法應用的到交互式的程序中。所以通常將基本型簡化為位移函數(shù)d的偏導數(shù)(位置之差)，得到下樹的Thin Shell Energy

其中

這個函數(shù)和前面介紹平面平滑算法里Fairing方法中衡量曲面面積和曲率的能量的函數(shù)相類似。區(qū)別在于這里我們使用平移量d而不是位置p且最小化的是面積和曲率的變換程度，即我們最小化曲面的拉伸和彎折。

下圖中，我們固定灰色區(qū)域，抬升黃色區(qū)域，并且最小化Thin Shell Energy。該能量包含拉伸和彎折兩個部分，左圖展示了純拉伸的情況(ks = 1, kb = 0)，中圖展示了純彎折的情況(ks = 0, kb = 1)，右圖展示了兩者混合的情況(ks = 1, kb = 10)。

應用曲面平滑算法里Fairing方法中提到求最小化的方法，得到能量函數(shù)對應的歐拉拉格朗日方程

為了最小化能量，需要解上述的偏微分方程(PDE)，根據(jù)第三章中介紹的方法，將上式子寫成離散形式，其中

則上述偏微分方程(PDE)可以被離散為下面逐頂點形式

其中變換區(qū)域R內自由頂點的位移函數(shù)d1,...dn是未知的(方程左側x項)，區(qū)域H和區(qū)域F中位移函數(shù)是已知的(方程右側b項)。

L為拉普拉斯矩陣，x和b都是n行3列的矩陣。

最小化得到結果是C1連續(xù)的，在三角形網(wǎng)格中C1連續(xù)只由區(qū)域F和H中First-Two-Rings頂點定義，在最小化的時候不用考慮F和H區(qū)域上其它的頂點。

在交互的過程中會控制區(qū)域H內的頂點進行操作，使得矩陣方程的右側的b項不斷發(fā)生變換，這個情況有更加高效的算法。通過變換限制為仿射變換，也能夠將某些計算提前進行預計算以提高效率。

與Transformation Propagation方法相比，此法由于需要每一幀解一個線性方程，計算量相對較大，但是仍然是可交互的。由于此法基于物理法則，故其效果相對較好。

Multi-Scale Deformation

前文的Shell-Based Deformation方法并不能夠正確地處理小尺度的細節(jié)。由于對局部細節(jié)的旋轉變換并不是線性的，所以不能夠完全的使用線性的方法對其進行建模。一個更好的方法是使用后面即將介紹的多尺度變形的方法。

下圖中，我們抬升正方形曲面的右側，左二圖展示了使用前文中的線性方法得到的結果，發(fā)現(xiàn)其細節(jié)并沒有被正確的還原。使用Multi-Scale Deformation方法得到結果(左三圖)雖然仍然有變形，但是已經(jīng)和理想的情況(左四圖)非常接近了。

Multi-Scale Deformation的主要思想是使用在曲面平滑算法中提到的分解的方法將曲面分解為高頻和低頻兩個部分。低頻部分即是曲面大致的外形，而高頻部分則代表小尺度的細節(jié)。我們的目標是對低頻部分進行變形并保持高頻部分的細節(jié)。

這個過程在2維情況下如下圖所示，虛線部分表示了曲線的低頻部分，我們將這條虛線進行變形并添加上高頻細節(jié)，最終得到了理想的形變結果。

在三維的情況下，首先通過移除高頻部分計算出曲面S的低頻形式B(原模型的光滑簡化形式)，在B上模型的細節(jié)D被移除。將B形變得到B'，通過B'和D我們能夠重建出最終的變形后的曲面S'。

上圖中我們只對原模型進行了一次分解，同樣地也可以對B再一次進行分解，以達到多吃變形的目的。

可以看到Multi-Scale Deformation主要包含下面三個操作

1. 分解(Decomposition)
2. 變形(Deformation)
3. 重建(Reconstruction)

其中分解可以使用到第四章提到的網(wǎng)格光滑算法，變形可以使用前文提到的算法。沒有提到的就是如何提取細節(jié)D并進行相應的重建。

位移向量(Displacement Vectors)

最直接的表示方法就是使用一個向量函數(shù)h:B→R3，函數(shù)h(p)表示光滑曲面B上每一個頂點都對應著一個三維向量。由于S和B擁有相同的連接性，所以位移向量

其中bi∈B，pi∈S。

使用全局坐標系取表示位移向量得到結果如下圖左圖所示，正確的方法是使用局部的基向量去表示位移向量(下圖右圖)。

因此在存儲hi時，需要使用曲面B上每個頂點的局部標價下的坐標而不是全局坐標。我們一般取法向量ni和另外兩個向量t(i,1)和t(i,2)作為一組正交基

基向量在從B變形到B'的過程中會發(fā)生相應的旋轉，最終我們根據(jù)B'的基向量以及位移向量在B中局部坐標基下的坐標可以得到S'上每一個頂點的坐標

法向量ni在每一個頂點上都是有定義的，剩下的只需要按照統(tǒng)一的標準取另外兩個軸ti,1和ti,2即可。

法向量位移(Normal Displacements)

當位移向量過長的時候會導致結果不穩(wěn)定，特別是在進行彎折(Bending)變形的時候，因此位移向量應該越短越好。因此，我們想到不再去尋找B上pi的對應頂點bi，而是去尋找B上距離p最近的頂點。

這種思想就是所謂的法向量位移，即

因為在上一節(jié)中hi通常是不與法向量平行的，因此法向量位移方法需要對S和B上的頂點進行重新采樣，從bi∈B上發(fā)射一條與法向量平行的射線以找到其在S上對應的頂點pi，而重采樣則會導致Alias Artifacts(走樣/假頻)現(xiàn)象的出現(xiàn)。

為了改進上面的方法，我們換一個方向。對于點pi∈S，我們尋找一個點bi∈B，且pi-bi與bi的法向量平行，而bi是曲面B上的任意一點，該點處于B上某一個三角形(a, b, c)∈B之中，因此bi可以表示為下列重心坐標的形式

其法向量同樣可以由重心坐標插值得到

而尋找點b的過程，可以使用牛頓迭代法求解下面方程的根

整個過程大致為，首先尋找離pi最近的三角形，如果在進行牛頓迭代的過程中重心坐標出現(xiàn)了負值，則分別對其相鄰的三角形進行處理。

一旦得到了三角形(a, b, c)和重心坐標 (α, β, γ)，則可以通過變形后的曲面B'計算出S'上每一個頂點pi的坐標

這樣避免了對曲面進行重采樣，從而使得某些尖銳細小的特征(Sharp Features)得到保留。因為點bi是曲面B上的任意一點，因此對于曲面S和B來說，其連接性并不一定要求是已知的。我們可以利用這一點來對曲面B進行重采樣以獲得更高的數(shù)值魯棒性。

位移向量和法向量位移的長度的不同通常取決于曲面B和曲面S相差的程度，對于例子

位移向量的長度平均比法向量位移的長度要長9倍。除了長度更短法向量位移也不需要進行啟發(fā)式的計算(計算坐標基t的過程)。

法向量位移的方法效率極高，但是其主要的問題在于相鄰的頂點的位移向量之間并沒任何聯(lián)系。當彎折(Bending)程度較大的時候，會導致細節(jié)部分出現(xiàn)非預期的結果。在極端情況曲面可能還能出現(xiàn)自相交的情況(當B'的曲率比位移長度hi要大的時候)。

下面的兩種算法正是為了改進上述情況而提出的

• Displacement Volumes：曲面S和曲面B對應的兩個三角形(pi, pj, pk)和(bi, bj, bk)組成了一個棱柱體，該棱柱體的體積被用來作為細節(jié)D，在變形的過程中保持不變。對于變形的曲面B'，重建的過程是找到一個曲面S'使得其每一個棱柱體的體積都和原來的相等。這樣會使得結果根據(jù)直觀合理且避免了自相交的情況，缺點是該方法在重建的過程中計算量較大。

• Deformation Transfer：原書中沒有詳細介紹該算法，可以參考這篇論文Deformation Transfer for Detail-Preserving Surface Editing。該算法在最終效果和運行效率上取了一個折中，只需要解一個疏松的泊松方程即可。

Differential Coordinates

盡管前面的Multi-Scale Deformation方法效率高，且能夠保存模型中的細節(jié)，但是如何生成一個合理的層級結構確是一個相當復雜的過程。為了避免Multi-Scale Deformation中分解的過程，另外一類方法采用了修改曲面的微分屬性而不是空間坐標的方法來重建變形后的曲面。

Gradient-Based Deformation

對于原始網(wǎng)格上每一個頂點上某個標量值，都可以找到對應的分段線性函數(shù)

其梯度是一個常向量(每一個三角形T對應一個常向量)

同樣地，考慮以下三維的情況

則對應每個三角形T，它的梯度是一個3*3的雅可比矩陣

參考第三章中介紹的方法，可以計算出矩陣中的各個位置上梯度函數(shù)的值。

接下來對每一個三角形的梯度JT進行變形，即乘以一個3*3的變換矩陣(旋轉、縮放/錯切) MT

MT是根據(jù)對控制點的變換得到，具體的方法會在后文中介紹。

剩下的步驟就是在盡量保持每一個三角形梯度不變得情況下，尋找每個頂點的新的位置。

如下圖所示，黃色區(qū)域為控制點所在區(qū)域，原模型為圓柱體表面(左圖)，我們對變換區(qū)域(藍色區(qū)域)上每一個三角形施以對控制點相同的變換，這將使得模型“裂開”(中圖)，然后改變每一個三角形的位置且盡量保持三角形的朝向不變，最終得到了變形后的模型(右圖)。

這個過程即是最小化下列的能量函數(shù)

f是待尋找的方程，g是目標梯度場。為了最小化上式子，應用變分法解下列歐拉拉格朗日方程

用目標的的x, y, z坐標代替f，并用離散拉普拉斯算子和離散散度算子對原方程離散化得到線性方程

為了使得方程有解(系統(tǒng)非奇異)，需要將固定一些點p'i，如示意圖中黃色的控制區(qū)域H內的頂點(這也就是上面的示意圖的中圖里黃色區(qū)域的控制點的位置被直接修改的原因)、示意圖中灰色的固定區(qū)域F內的頂點。

解上述方程只需要解一個輸送的泊松方程，比前面的Shell-Based Deformation效率略高。另外，泊松方程在邊界處只是C0連續(xù)的，但是Shell-Based Deformation是C1連續(xù)的。

Laplacian-Based Deformation

Laplacian-Based Deformation與Gradient-Based Deformation方法類似，不過其目標不再是逐三角形的梯度，而是逐頂點拉普拉斯坐標。

我們首先計算每個頂點的拉普拉斯坐標，然后乘以變換矩陣M，最后尋找新的頂點坐標去你和目標拉普拉斯坐標。

這個過程中最小化能量函數(shù)為

對應的歐拉拉格朗日方程為

上式離散化后得到下列方程

在解方程的時候同樣的需要固定一些頂點。需要注意的是，拉普拉斯算子的離散形式有Uniform和Cotangent兩種，對于不規(guī)則網(wǎng)格使用后者得到的結果效果會更好一些。

Laplacian-Based Deformation方法和Shell-Based Deformation方法之間是存在聯(lián)系的。忽略掉Laplacian-Based Deformation中對拉普拉斯坐標的變換，使用原始的拉普拉斯坐標來計算新的頂點的位置，在Shell-Based Deformation中固定相同的頂點且原始頂點相同，兩者都能得到相同的歐拉拉格朗日方程

則最終得到相同的結果。

如何得到變換矩陣M

那么前面兩種方法中都使用到了變換矩陣M，這一節(jié)將會討論如何根據(jù)對控制點的變換得到逐頂點和逐面(三角形)的變換矩陣

Propagation Of Deformation Gradients

第一種方法和之前提到的Transformation Propagation中插值的方法類似，這里我們對變換的梯度進行插值。通常我們是按照下面的方式對控制點進行仿射變換

T(x)的梯度是一個3*3的矩陣 M，該矩陣代表了對控制點的旋轉、縮放/錯切變換。

需要注意的是，旋轉變換的插值與縮放/錯切變換不同，需要對變換矩陣進行極分解(Polar Decomposition)。

首先對M進行奇異值分解，得到

然后就能得到M矩陣中旋轉的部分和縮放/錯切的部分

因為U和V是正交矩陣，所以有

然后我們對旋轉部分是slerp插值，對縮放/錯切的部分使用線性插值，得到逐頂點的變換矩陣Mi

對于逐面(三角形)，其插值的因子s是三角形T的三個頂點對應的值si, sj, sk的平均值。需要注意的是，平移變換t并不會改變梯度和拉普拉斯坐標的值，所以當變換中包含有距離較大的平移變換的時候會產生不符合預期的結果。

Implicit Optimization

通過最小化下面能量函數(shù)，Implicit Optimization同時對新的頂點坐標p'i以及旋轉矩陣Mi進行優(yōu)化

其中Ai是頂點的局部面積，Mi和新頂點的位置有關。注意這個過程中同樣需要固定區(qū)域H和區(qū)域F中的頂點。

為了避免非線性最優(yōu)化(Nonlinear Optimization)(這是剛體變換Mi中必須滿足的)，局部變換被限制為相似線性變換(Linearized Similarity Transformation)，Mi被寫成下面的斜對稱矩陣

參數(shù)si和hi(位移向量)是由下列限制條件決定

通過p'i的線性組合可以得到si和hi。

書中對該部分介紹省略了很多，詳細的內容可以參考這篇論文：Laplacian Surface Editing

需要注意的一點是，根據(jù)拉普拉斯坐標的性質，其對旋轉敏感，所以網(wǎng)格的局部信息會發(fā)生旋轉扭曲，且旋轉尺度較大是，扭曲會非常嚴重。

Freeform Deformation

前面討論的所有方法都是基于曲面的(Surface- Based)，它們通過最小化某個能量函數(shù)在原曲面S上進行光滑變形。其計算過程歸結起來是解一個線性系統(tǒng)對應的歐拉拉格朗日方程。

上述方法的一個明顯的缺點在于其計算量和數(shù)值魯棒性和網(wǎng)格分割的復雜度和質量相關。對于退化的三角形(Degenerate Triangle)其Cotangent形式的拉普拉斯算子是不符合定義的，這會導致線性系統(tǒng)奇異。同樣地，Gap和非流形的出現(xiàn)使得頂點地局部信息不再一致，也會導致一些問題。諸如模型修復或者網(wǎng)格重劃分算法能夠在一定程度上接近這些問題?？v使網(wǎng)格的質量足夠高，但是其復雜過大也會導致線性系統(tǒng)規(guī)模過大無法得到其解。

接近這些問題的辦法是使用空間變形(Space Deformations)，它通過對目標模型的周圍空間進行變形從而隱式的對目標模型進行變形。

與基于曲面的變形(Surface-Based Deformations)不同，空間變形(Space Deformations)的變形是一個從三維空間到另一個三維空間的過程。

且d不依賴于特定的曲面，能夠作用用各種顯式表示的曲面(三角形網(wǎng)格的所有頂點、點采樣模型的所有點)。

Lattice-Based Freeform Deformation

Freeform Deformation(FFD)中使用3元張量樣條函數(shù)(Trivariate Tensor-Product Spline Function)來表示空間變形

其中Ni是B樣條函數(shù)，δc是控制點c的位移量。

為了簡化上式，可以將位移項和樣條函數(shù)項記為

最終得到

原網(wǎng)格上的每一個頂點pi∈S都有一個對應的的參數(shù)坐標ui = (ui, vi, wi)，且

每一個頂點都會被施以變換

因為d(ui)中的N項是一個常數(shù)，可以預計算，所以其效率較高。

通過操縱樣條控制點(即指定控制點位移δc)就能夠控制模型的變形。和之前提到的方法類似，固定控制區(qū)域H(施加位移向量d之后的位置)和固定區(qū)域F內的頂點，然后根據(jù)給定的δc解下列線性方程

由于方程左邊的矩陣不是方陣，所以可以使用最小二乘法的思想，最小化

以及控制點的位移量

不過需要注意兩個問題，首先如果上述方程是過定的(Over-Determined )，所以限制條件不能被完美地滿足；另外如果是欠定的(Under-Determined)，剩余的自由度是由最小化控制點的位移量決定的，而不是通過光滑算法決定。

樣條函數(shù)N在規(guī)則網(wǎng)格(Regular Grid)上如何放置是另外一個問題。如果放置不當，會造成Alias Artifacts(走樣/假頻)。通過使用更為靈活的且能夠更好的表示目標變形的格子框架能夠在一定程度上解決這個問題，但是面對復雜的變形的時候，格子框架的選取非常困難。

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)格。相對于格子框架，其能夠更好的包裹目標物體。

原始網(wǎng)格S上的頂點pi能夠表示為控制籠上頂點的線性組合

其中權重φ是廣義重心坐標(Generalized Barycentric Coordinates)，可以取之前方程中的N項。

頂點的權重φ可以被預計算，這樣通過操作控制籠上的頂點

并使用下面的方法計算逐頂點的位移向量即可

這樣就能比之前使用格子框架能夠更為靈活地進行控制。其缺點是由于解是最小范數(shù)解(Least Norm Solution)，所以結果并不一定是一個Fair Deformation(不知道怎么翻譯)。

Radial Basis Functions

在Surface-Based Deformations中，通過指定地位移進行插值，并且最小化能量函數(shù)得到了相當不錯的結果。借用同樣的思想，同樣地，我們可以對Space Deformation中的函數(shù)

進行插值，并且最小化特定的能量函數(shù)?？偟膩碚f，我們的目標是找到函數(shù)d，能夠在位置pi根據(jù)指定的位移向量進行插值運算，且滿足給定的限制條件。Radial Basis Functions(RBFs)正是非常適合這類問題的函數(shù)。其定義為徑向對稱核函數(shù)φ的疊加，其中心為cj，權重為wj

其中π(x)為保證精度用的多項式項。通常取cj = pj，wj的值為下列方程的解

這樣RBF函數(shù)就能夠被應用到頂點上了

而核函數(shù)φ的選擇會影響到計算的復雜度和結果的質量。緊支撐徑向基函數(shù)(Compactly
Supported Radial Basis Functions)會產生稀疏的線性方程，因此其能夠被用來對加以很多限制條件的目標進行插值。其缺點在于效果不如全局支持徑向基函數(shù)(Global Support Radial Basis Functions)。

全局支持徑向基函數(shù)

會產生一個三次(??不確定是不是這么翻譯的)調和函數(shù)(Tri-Harmonic
Function)d

通過變分法可知，需要最小化的能量函數(shù)為

線性方法的局限性

原始模型

使用非線性方法得到的結果(從左往右分別是純平移變形、彎折變形、扭曲變形)

• Shell-Based Deformation結合Multi-Scale Deformation能在純平移變形時得到較高質量的結果，且能夠保留相當?shù)募毠?jié)。但是由于Shell Energy是線性的，當對物體施以大尺度旋轉變形的時候，結果會非常不理想。

Shell-Based Deformation得到的結果

• Gradient-Based Deformation使用對控制點變換的梯度更新每一個面的梯度，因此在對物體施以旋轉變形的時候結果會非常理想。但是由于局部旋轉的顯式傳播(Propagation)是對平移敏感的，會導致結果曲面不夠光滑，并且會丟失細節(jié)特征。

Gradient-Based Deformation得到的結果

• Laplacian-Based Deformation隱式地優(yōu)化了局部旋轉，因此相對來說對旋轉和平移變形更為友好。但是由于需要對旋轉部分線性化，因此在大尺度變形時會導致扭曲。

Laplacian-Based Deformation