一種基於控制網格的變形方法

2023-10-09 14:53:54 6

專利名稱：一種基於控制網格的變形方法
技術領域：
本發明涉及數字幾何處理技術領域，尤其涉及一種基於控制網格的變形方法。
背景技術：
如今隨著數字採集技術的不斷發展，高複雜度的三維網格模型越來越普及， 對複雜物體進行快速有效的編輯成為受到廣泛關注的熱點內容，而模型的形狀 編輯都會涉及到變形技術。對網格模型進行變形的方法一般是使用一個包圍模 型的控制網格，可以分為操作控制頂點和插值計算兩個階段。前一個階段根據
用戶對控制頂點的操作，使用各種方法對控制網格做出相應變形；後一個階段， 根據控制網格的變形插值計算嵌入的模型的變形結果。各種網格編輯和變形技 術都可以用於操作控制頂點的階段。
為了獲得光滑的插值結果，自由變形方法採用了樣條函數。而基於均值坐 標的方法使用一個稀疏的控制表面而不是控制網格以進行光滑的插值。為了獲 得高質量的變形結果，這些方法的求值過程都需要一個相對較大的領域內的信 息，甚至可能是整個控制網格，這並不適合用圖形顯示卡高速地實現。
在目前的很多圖形應用中，重心坐標插值可能是被廣泛採用的最簡單的插 值技術。在三維空間中的重心坐標插值只需要一個四面體的四個頂點，對應於 一個控制頂點的基函數只有在該頂點相鄰的四面體內才能取得非零的函數值。 雖然重心坐標插值的局部特性便於快速計算和局部控制，但是當控制頂點比較 稀疏時，由於插值函數一階不連續的性質，目標模型在控制網格邊界處會產生 明顯的不光滑瑕疵。增加控制頂點的數目和密度雖然能夠削弱這一效應，卻相 應地增加了操作控制網格的代價。

發明內容
本發明的目的在於針對現有技術的不足，提出一種基於控制網格的變形方 法。本方法在控制網格非常稀疏的情況下，仍然能夠有效的驅動任意高複雜度 的模型進行變形，使得操作控制網格所需要的CPU代價非常小，同時變形後的 目標的計算能夠使用現代圖形顯示卡有效的實現。本方法也同樣適用於變形二 維的圖像對象。
為實現這樣的目的，本發明採用的技術方案如下 一種基於控制網格的變 形方法，包括以下步驟1) 將目標對象嵌入到控制網格中，對控制網格進行變形；
2) 根據控制網格的變形，在傳統的重心坐標插值函數基礎上引入待定的 局部變換矩陣，建立改進的重心坐標插值函數；
3) 使用改進的重心坐標插值函數建立總能量函數，並根據需要調整其中 的加權係數；
4) 根據總能量函數求解最優的局部變換矩陣，據此使用改進的重心坐標 插值函數計算變形後的對象。
需要變形的目標對象可以是二維圖像或者三維網格模型，所建立的控制網 格，對於二維圖像是平面的三角網格，對於三維網格模型是四面體網格，控制 網格需要把整個對象嵌入其中，可以僅具有稀疏的控制頂點。
所述的改進的重心坐標插值函數為每個控制頂點引入了待定局部變換矩 陣，其定義形式如下
X(W) = S—/^(W)(《+M/(W-W,));
其中，",為n個控制頂點，x,是已知的變換後的控制頂點，A(")即為傳統重 心坐標插值的基函數，M,是待定的局部變換矩陣。
所述的總能量函數定義為插值函數的不連續能量和振動能量函數的加權
和。控制網格的相鄰兩個片元z;和7;的不連續能量定義為插值函數在它們邊界處
梯度差的模的平方和，其定義形式如下E, W-^Jvx(")I,力-Vjc(")I",^;
其中，/4/表示7;.上與"相鄰的邊界，_/~>/表示"上與7;相鄰的邊界。相 應地，全局不連續能量定義為控制網格中所有相鄰片元對的不連續能量的總和， 其形式如下
K工H Z ^00°
/or a// 。咖咖'owe 弓. 所述的振動能量的定義形式如下
其中，r表示控制網格的片元的集合，a卩為其中的片元，對於二維對象^是 平面三角片，對於三維對象f是四面體，相應地M即為/的面積或體積。ft表示
Frobenius範數。
最後求解得到的局部變換矩陣應使總能量函數值最小的。 本發明的有益效果是，本發明使用非常稀疏的控制網格也可以產生視覺上光滑的插值結果；可以重生成控制頂點的位置；可以局部求值，適合使用圖形
顯示卡實現高性能的計算。


圖l是本發明的方法流程圖2是本發明的實現效果與傳統方法的對比示例圖3是二維空間中局部變換矩陣在插值時的效果示例圖4是總能量函數中不同加權係數的效果示例圖。
具體實施例方式
下面根據附圖詳細描述本發明，本發明的目的和效果將變得更加明顯。
令i3為W空間的目標對象，"可以為2或3， 0-(f/，r)為i3的一確定的控制 網格，這裡"=(^...," )即為控制頂點集合，7 =",...人)表示網格的片元集合。 對於二維空間，^ = 2， ^為平面三角網格。對於三維空間，^ = 3， (P為四面體 網格。x("):0 —W為控制網格的變換函數，且已知x(",h、,W,ef/，則傳統的 重心坐標插值函數的形式如下
其中a (")為線性分段的重心坐標基函數，滿足z:=1《(")=i和^)=& 。 在修正曲線和曲面設計的相關文獻中， 一種簡單有效的衡量振動的方法是
使用薄板能量，可參考[Moretonl992] Moreton H. P. and S6quin C. H., "Functional optimization for fair surface design", 57GGi^屍//, 167—176， 1992和[Welch1992] Welch W. and Witkin A., "Variational surface modeling",肌GTMiW, 157—166, 1992。 一個參數曲面S(",力的薄板能量被定義為
這裡《+2《+《其實是5(",力的Hessian矩陣的Frobenius範數的平方。 本發明提出一種基於控制網格的變形方法，流程如圖1所示，包括建立和 變形控制網格、建立改進的重心坐標插值函數、建立總能量函數並調整加權系 數、求解最優局部變換矩陣並計算變形後的對象等四個步驟，對加權係數的調 整可以以最終的變形結果為依據。圖2展示了本方法實現的結果與傳統重心坐 標插值方法實現結果的對比，左邊為原始模型，中間是使用本方法的變形結果， 右邊是使用傳統重心坐標插值方法的結果，可以看到本方法克服了傳統方法的 缺陷，得到了光滑的變形結果。現具體介紹本方法的四個步驟-1)建立和變形控制網格
根據需要變形的對象是二維圖像或者三維網格模型，所建立的控制網格相應地為平面的三角網格或四面體網格，控制網格需要把整個對象嵌入其中，可 以僅具有稀疏的控制頂點。本方法對於三維模型採用了四面體網格而不是六面 體，是因為四面體網格可以更好的描述任意的拓撲結構。控制網格的建立和進 行變換可以採用各種已有的技術和方法，或者手動地指定，例如可以使用開源
的自動網格生成器netgen生成四面體網格，並在生成網格時將模型的表面向外 擴展以使生成的四面體網格能夠包含整個目標模型，可以使用基於物理的模擬 方法來變形控制網格，可參考[Miiller2004] Mtiller M. and Gross M., "Interactive virtual materials", iVoceefi /"gs q/^ 20<94 co一rewce Gra/ /n'd /"^/^ce， 239—246, 2004和[Huang2006] Huang J" Liu X.， Bao H., Guo B. and Shum H,Y" "An efficient large deformation method using domain decomposition", Co附pwfera <& Oop/z/", 30(6): 927—935， 2006。
2)建立改進的重心坐標插值函數
為了達到高性能的求值，本方法基於傳統的重心坐標插值，中心思想是在 每個控制頂點處引入待定的局部變換矩陣建立二次的插值函數，通過優化這些 局部變換矩陣來最小化插值函數的一階不連續，同時也最小化插值函數的二階
導數，避免引入不期望的振動。改進的重心坐標插值函數定義形式如下
其中A(w)為重心坐標基函數，M,是在頂點",領域內的待定局部變換矩陣。 傳統的重心坐標插值是該函數在所有的M,-O時的特例，且該函數對於任意的矩 陣集合(M」仍然滿足己知的控制頂點的變換。例如 = EjKXA +M,(& -m,》=a, s "。
這是一個該函數能夠用於變形的重要性質。並且在所有的M,上加上同一個
矩陣T後x(w)不會改變，艮P:xT(w) = 2二^0)(;c,+(M,+T)(w-w,)) = ;c(w)。
圖3給出了局部變換矩陣如何影響插值結果的一個示例。圖3a為原始圖像 和控制網格，圖3b顯示了對控制網格進行操作後使用傳統重心坐標插值的結果， 可以看到插值結果在控制網格邊界處存在不連續的現象。為了清楚的顯示局部 變換矩陣的效果，現僅在圖3a中的中心控制頂點處加入了局部變化矩陣 M"Re-l2x2，其中R0表示一個旋轉^角度的變換矩陣，圖3c、圖3d和圖3e顯 示了之後使用改進的重心坐標插值函數計算得到的插值結果，圖3c中取^ = 1和 6 = 60。，圖3d中取5 = 0.8和0 = 26。，圖3e中取^^0,5禾l^-0。。視覺上較好的效 果是圖3c。為了方便起見改進的重心坐標插值函數可以寫成向量的形式，艮P: x(w) = A(i/)m + B(w)x ;
其中111 = (]^1,.."]\1 )， x二(X".";O。
A(w)的元素是由m,.、伊,如)和m組成的二 次多項式，B(")的元素是由p,(")組成的"的一次多項式，二階導數^2形成一
個四階常數張量，而一階導數，形成三階常數張量，其二階導數^^
3)建立總能量函數並調整加權係數
為了求得最優矩陣，本方法定義了不連續能量和振動能量兩個能量函數， 把這兩個函數的加權和作為總能量函數。不連續能量用來衡量一階的梯度不連 續程度，振動能量用來衡量函數二階導數對應的振動程度。
由於A(")是分段線性的基函數"(w)的梯度可能在控制網格的兩個不同片元 的邊界處不連續。假設片元7^和7;.公有一個邊界/ey，使用插值函數在它們邊 界處梯度差的模的平方和來衡量不連續的程度，其定義形式如下
五一 w=￡J|vx(")|,—廣w")U4化。
其中/ —乂表示 :上與7;相鄰的邊界，—/表示7;上與7;相鄰的邊界。相應 地全局不連續能量即定義為控制網格中所有相鄰片元對的不連續能量的總和， 其形式如下&。w= S L,w。
/or o〃 cr咖咖f;朋tf r乂
與薄板能量類似，我們使用Hessian矩陣^^衡量插值函數x(")的振動能
其中r表示控制網格的片元的集合，f即為其中的片元，對於二維對象r是平 面三角片，對於三維對象,是四面體，相應地lrl即為r的面積或體積。||《表示 Frobenius範數。利用之前所述的x(")的性質可知在片元內部Hessian矩陣總為 常數。這樣就可以得到如下的總能量函數
￡她/ 0) = 0) + "五血0)。
其中"和p是加權係數，如圖4所示，可以調整不連續能量和振動能量的比 重得到不同的結果。在交互式的應用中可以默認的設置《 = 1並自動選擇一個匹 配的"值，例如使得五^Oc)和五^W中的Hessian矩陣具有相同的Frobenius範 數，然後用戶可以手動調整"的值以調整最終結果的連續性和光順性。圖4a給 出了一個原始對象，圖4b、圖4c、圖4d中分別取"=100、 "-0.25禾|] = 0.01。 可以看到隨著a的增加插值結果越來越光滑，但是振動也在增加。根據實驗發現 "=0.2和《 = 0.1分別對二維圖像和三維模型產生最好的效果。
4)求解最優局部變換矩陣並計算變形後的對象
求解改進的重心坐標插值函數中的最優局部變換矩陣，使得總能量《^(x) 最小，即
(M,，…,M ) = arg min￡,oto/ (x)。
m
如之前所述的，在所有的M,上加上任意的同一個矩陣後;c(")不會改變，因 此可以令第一個控制頂點的局部變換矩陣為零矩陣，這樣可以在求解這個能量 最小化問題時避免奇異性。= A(M)m + B(w)x在(X)和(x)中都會消去"， 而對m和x而言^。,W則是二次函數，有常數的Hessian矩陣，所以在求最優解 的時候只需要解一個稀疏的線性系統，並且為了實現高效的求解，可以預先計 算該線性系統矩陣的一個Cholesky分解。
本發明在傳統的重心坐標插值函數中的每個控制頂點處引入待定的局部變 換矩陣建立一個二次的插值函數；通過求解這些局部變換矩陣的最優解計算優
化的插值結果。傳統的重心坐標插值方法雖然實現簡單，具有很好的局部控制 和快速計算的特點，但是由於它在控制網格片元邊界處的一階不連續性，變形 結果會在邊界處產生明顯的不光滑效果。本方法很好了消除了這個缺陷，即使 使用非常稀疏的控制網格也能得到光滑的結果，同時本方法也最小化了插值函 數的二階導數，避免了插值結果中出現不期望的振動現象，並且本方法保持了 局部控制和快速計算的特點，可以使用圖形顯示卡高效地實現。
9
權利要求
1.一種基於控制網格的變形方法，其特徵在於，包括以下四個步驟1)將目標對象嵌入到控制網格中，對控制網格進行變形。2)根據控制網格的變形，在傳統的重心坐標插值函數基礎上引入待定的局部變換矩陣，建立改進的重心坐標插值函數。3)使用改進的重心坐標插值函數建立總能量函數，並根據需要調整其中的加權係數。4)根據總能量函數求解最優的局部變換矩陣，據此使用改進的重心坐標插值函數計算變形後的對象。
2. 根據權利要求1所述的基於控制網格的變形方法，其特徵在於，需要變 形的目標對象可以是二維圖像或者三維網格模型，所建立的控制網格，對於二 維圖像是平面的三角網格，對於三維網格模型是四面體網格，控制網格需要把 整個對象嵌入其中，可以僅具有稀疏的控制頂點。
3. 根據權利要求1所述的基於控制網格的變形方法，其特徵在於，改進的 重心坐標插值函數為每個控制頂點引入了待定局部變換矩陣，其定義形式如下formula see original document page 2其中，",為"個控制頂點，x,.是己知的變換後的控制頂點，p,(")為傳統重心 坐標插值的基函數，M,是待定的局部變換矩陣。
4. 根據權利要求1所述的基於控制網格的變形方法，其特徵在於，總能量 函數定義為插值函數的不連續能量和振動能量函數的加權和。
5. 根據權利要求3和權利要求4所述的一種基於控制網格的變形方法，其 特徵在於，控制網格的相鄰兩個片元7;和7;.的不連續能量定義為插值函數在它們 邊界處梯度差的模的平方和，其定義形式如下= LJ卜(")I'力—Vx(")U't化。其中，/ — y表示7;上與7;相鄰的邊界，/"W表示z;.上與7:相鄰的邊界。相 應地，全局不連續能量定義為控制網格中所有相鄰片元對的不連續能量的總和， 其形式如下-2] K小
6. 根據權利要求3和權利要求4所述的一種基於控制網格的變形方法，其 特徵在於，振動能量的定義形式如下其中，r表示控制網格的片元的集合，/即為其中的片元，對於二維對象/是 平面三角片，對於三維對象^是四面體，相應地M即為f的面積或體積。l卜L表示Frobenius範數。
7.根據權利要求1所述的基於控制網格的變形方法，其特徵在於，求解得 到的局部變換矩陣應使總能量函數值最小。
全文摘要
本發明公開了一種基於控制網格的變形方法，該方法根據控制網格的變形，使用改進的重心坐標插值技術計算目標對象相應的變形結果；本發明使用非常稀疏的控制網格也可以產生視覺上光滑的插值結果；可以重生成控制頂點的位置；可以局部求值，適合使用圖形顯示卡實現高性能的計算。
文檔編號G06T11/00GK101587595SQ200910099459
公開日2009年11月25日 申請日期2009年6月8日 優先權日2009年6月8日
發明者劉新國, 祿 陳, 鮑虎軍, 勁 黃 申請人:浙江大學