（計算數(shù)學專業(yè)論文）平面多邊形變形算法研究.pdf

西- i l - e 業(yè)大學碩士學位論文 摘要 變形，是指從初始物體到目標物體的連續(xù)、光滑、自然的過渡( 這里的物體 可以是數(shù)字圖像、曲線、曲面、網(wǎng)格等) 。變形有著十分廣泛的應(yīng)用，如計算機 圖形學、動畫設(shè)計、工業(yè)造型、科學計算可視化、電影特技等。本文對同構(gòu)平面 三角網(wǎng)格的變形和平面多邊形的變形算法進行了研究，主要的研究結(jié)果如下： 1 ) 平面多邊形的相似同構(gòu)三角剖分。本文提出了基于初始多邊形和目標多 邊形之間相似性的同構(gòu)三角剖分算法。該方法將初始多邊形和目標多邊形的相似 性進行分析，在不添加額外頂點的情況下，首先進行初始和目標多邊形的相似部 分三角剖分，得到相應(yīng)的簡化初末多邊形，該過程能夠起到對初始和目標多邊形 簡化的作用，對此簡化初始和目標多邊形進行相應(yīng)的同構(gòu)三角剖分。這樣能夠減 少在原始的初始和目標多邊形之間的同構(gòu)三角剖分的計算，以達到好的的效果。 應(yīng)用該算法能夠減少進行同構(gòu)三角剖分需要增加的額外頂點的個數(shù)，從而能夠減 少多邊形變形的復雜度和計算量。 2 ) 基于小波的平面多邊形變形算法。該算法首先將初始和目標多邊形進行 適當?shù)男〔ǚ纸猓玫较鄳?yīng)的輪廓多邊形和細節(jié)部分，再分別對輪廓多邊形和細 節(jié)進行變形，最后通過重構(gòu)算法得到中間多邊形。該算法在保持多邊形輪廓不自 交上有顯著的改善，因為該算法能夠在很大程度上保證輪廓多邊形不自交，從而 能夠?qū)⒃撍惴ㄅc同構(gòu)三角網(wǎng)格變形算法相結(jié)合，結(jié)合兩者的優(yōu)點。通過實踐證明 了運用該算法能夠減輕同構(gòu)三角剖分的難度，以及減少進行變形的計算量，進而 達到實時的效果，而且變形取得令人滿意的效果。 3 ) 平面凸網(wǎng)格的保凸變形研究。本文提出了具有不同凸邊界的同構(gòu)平面三 角網(wǎng)格的保凸變形算法。本文提出了基于角度的的保凸變形算法變形網(wǎng)格的凸邊 界，并給出了該算法保凸的理論證明，且具有凸邊界內(nèi)角按同一速度變化的性質(zhì)。 對網(wǎng)格的內(nèi)部頂點采用凸組合方法。本文方法能夠保證網(wǎng)格邊界在變形過程中始 終保持凸性，且任意時刻的中間網(wǎng)格與初末網(wǎng)格同構(gòu)，即不產(chǎn)生自交現(xiàn)象。 關(guān)鍵詞：同構(gòu)三角網(wǎng)格，相似性剖分，簡化多邊形，小波變換，多分辨分析， 輪廓多邊形，細節(jié)信息，額外頂點，避免自交，保凸變形，凸組合 西北工業(yè)大學碩士學位論文 a b s t r a c t m o r p h i n g ，a l s ok n o w na sm e t a m o r p h o s i s ，i st h eg r a d u a l ，c o n s e c u t i v e ，s l i p p e r y a n dn a t u r a lt r a n s f o r m a t i o no f t h es o u r c eo b j e c ti n t ot h e t a r g e to b j e c t ( t h eo b j e c tm a y b e d i g i t a li m a g e ，c u r v es u r f a c e ，g r i d d i n ga n ds oo n ) m o r p h i n gh a sw i d ep r a c t i c a lu s ei n a r e a ss u c ha sc o m p u t e rg r a p h i c s ，a n i m m i o n d e s i g n ，i n d u s t r i a lm o d e l i n g ，s c i e n c e c o m p u t m i o nv i s u a l i z a t i o n ，f i l ms t u n ta n ds oo n t h i sp a p e rm a k e sr e s e a r c h e so nt h e m o r p h i n go fp l a n a rc o m p a t i b l et r i a n g u l a t i o n sa n dp l a n a rp o l y g o n s ，a n dt h em a i n r e s u l t sa r ea sf o l l o w s ： 1 ) t h es i m i l i t u d ec o m p a t i b l et r i a n g u l a t i o n so fp l a n a rp o l y g o n s t h i sp a p e r p r e s e n t sac o m p a t i b l et r i a n g u l a t i o n sa r i t h m e t i cw h i c hi sb a s e du p o nt h ec o m p a r a b i l i t y b e t w e e nt h es o u r c ep o l y g o na n dt h et a r g e tp o l y g o n t h i sa r i t h m e t i ct a k e st h e c o m p a r a b i l i t yi n t oa c c o u n t f i r s t l y , t r i a n g u l a t e st h es i m i l i t u d ep a r t sb e t w e e nt h e s o u r c ep o l y g o na n dt a r g e tp o l y g o n ，n e e d i n gn oe x t r av e r t e xi n t h i sp r o c e s s ，t h i sc a n s i m p l i f yt h et w op o l y g o n s ，c a l l e dt h et w or e s u l t e dp o l y g o n sa ss i m p l i f i e ds o u r c e p o l y g o na n ds i m p l i f i e dt a r g e tp o l y g o n u s i n gt h ea l r e a d ye x i s t i n ga r i t h m e t i c ，t h et w o s i m p l i f i e dp o l y g o n sc a nb et r i a n g u l a t e d t h e nt h ec o m p u t a t i o nc a nb ed e c r e a s e df o r t r i a n g u l a t i n gt h eo r i g i n a lp o l y g o n sa n dt h er e s u l t so ft r i a n g u l a t i o na r es a t i s f i e d t h e n u m b e ro fe x t r av e r t e x e sc a nb ed e c r e a s e d ，s ot h ec o m p l e x i t ya n dt h ec o m p u t a t i o na r e d e c r e a s e df o rm e t a m o r p h o s i z i n gt h e p o l y g o n s 2 ) t h em o r p ha r i t h m e t i co fp o l y g o n si sb a s e du p o nw a v e l e t e s f i r s t l y , t h es o u r c e p o l y g o na n dt h et a r g e tp o l y g o na r ed e c o m p o s e da tt h es a m el e v e l ，a sar e s u l t , t h e o v e r a l ls h a p e so f t h ep o l y g o n sa n dt h ed e t a i l so f t h ep o l y g o n sc a nb eg o t t e n s e c o n d l y , t h eo v e r a l ls h a p e sa n dt h ed e t a i l sa r em e t a m o r p h o s i z e ds e p a r a t e l y l a s t l y , t h em i d d l e p o l y g o nc a l lb er e c o n s t r u c t e dv i ar e c o n s t r u c t e da r i t h m e t i ca c c o r d i n gt ot h em i d d l e o v e r a l ls h a p e sa n dt h em i d d l ed e t a i l s t h ei n t e r s e c t i o n f r e eo ft h eo v e r a l ls h a p eo ft h e p o l y g o n si sl a r g e l yi m p r o v e d ，s ot h i s a r i t h m e t i cc a nb em e r g e dw i t ht h em o r p h a r i t h m e t i co f t h ec o m p a t i b l et r i a n g u l a t i o n , t oe x e gt h ev i r t u e so f t h et w oa r i t h m e t i c e s t h e r ea r es o m ee x a m p l e st os h o wt h a tt h i sa r i t h m e t i cc a r ld e c r e a s e dt h ec o m p l i c a t i o n o fc o m p a t i b l et r i a n g u l a t i o n ，b r i n g i n go nt h ed e c r e a s e dt h ec o m p u t a t i o no fm o r p ha n d 1 1 西北工業(yè)大學碩士學位論文 t h ep r o c e s si sr e a lt i m e t h em o t hr e s u l t e sa r es a t i s f i e d 3 1t h i sp a p e rg o e sa l o n gw i t ht h er e s e a r c ho nc o n v e x i t y p r e s e r v i n gw h e np l a n a r c o n v e xg r i d d i n g sm e t a m o r p h o s i z e w h e nt w op o l y g o n st h a th a v ed i f f e r e n tc o n v e x b o u n d a r i e sm e t a m o r p h o s i z e ，t h ea r i t h m e t i cp r e s e n t e di nt h i sp a p e rc a r l k e e pt h e b o u n d a r yc o n v e x i t y t h i sa r i t h m e t i c i sb a s eo nt h ea n g l ea n dt h a ti su s e dt o m e t a m o r p h o s i z et h eb o u n d a r i e so ft h eg r i d d i n g s t h ec h a r a c t e rt h a tt h i sa r i t h m e t i ci s c o n v e x i t y - p r e s e r v i n gi sp r o v e di nt h i sp a p e ra n d t h i sa r i t h m e t i ch a st h ec h a r a c t e rt h a t a l lt h ea n g l e si nt h ep o l y g o nh a v et h es a m et r a n s f o r m a t i o n a lr a t e t h ei n n e rv e r t e x e s c a d - b em e t a m o r p h o s i z e dv i ac o n v e xc o m b i n a t i o n t h ea r i t h m e t i ci nt h i sp a p e rc a n k e e pt h eb o u n d a r yp r o t r u d i n ga l lt h et i m ea n dt h em i d d l eg r i d d i n gi sc o m p a t i b l ew i t h s o u r c eg r i d d i n ga n dt a r g c tg r i d d i n g ，t h ep h e n o m e n ao fi n t e r s e c t i o nw i l ln o ta p p e a ri n t h ew h o l ep r o c e s so f m e t a r n o r p h o s i s e k e yw o r d ：c o m p a t i b l et r i a n g u l a t i o n s ，s i m i l i t u d ec o m p a t i b l et r i a n g u l a t i o n ，s i m p l i f i e d p o l y g o n s ，w a v e l e tt r a n s f o r m a t i o n ，m u l t i - r e s o l u t i o n a n a l y s i s ，o v e r a l ls h a p ep o l y g o n ， d e t a i l ，e x t r av e r t e x ，i n t e r s e c t i o n - f r e e ，c o n v e x i t y - p r e s e r v i n g ，c o n v e xc o m b i n a t i o n i i i 第一章緒論 第一章緒論 1 1 變形概述和研究背景 變形( m e t a m o r p h o s i s 或m o r p h i n g ) ，也稱為形狀調(diào)配或融合( s h a p eb l e n d i n g ) 、 形狀平均( s h a p ea v e r a g i n g ) 等，是指從初始物體到目標物體的連續(xù)、光滑、自然 的過渡( 這里的物體可以是數(shù)字圖像、多邊形、多面體等) 。變形技術(shù)在許多領(lǐng)域 有著十分廣泛的應(yīng)用，如計算機圖形學、動畫設(shè)計、工業(yè)造型設(shè)計、虛擬現(xiàn)實、 科學計算可視化、電影特技制作等領(lǐng)域。變形應(yīng)用于計算機動畫，可以減輕美工 師的手工勞動；在產(chǎn)品造型設(shè)計中，應(yīng)用變形可以把不同造型特征相互交融，產(chǎn) 生新的造型系列；變形應(yīng)用于電影制作，可以產(chǎn)生奇特的電影特技效果，給人以 美的視覺享受。隨著現(xiàn)代信息社會和變形技術(shù)的不斷發(fā)展，變形將會有更加廣泛 的應(yīng)用。變形問題已經(jīng)引起了廣泛的關(guān)注和研究，比如二維圖像變形研究【8 、2 1 、 2 5 、3 2 、3 8 、4 9 、5 0 、5 1 、5 2 、6 0 、6 8 】，多邊形變形及多邊形曲線變形研究 1 2 、 1 6 、1 7 、2 4 、3 4 、3 6 、4 2 、4 4 、5 7 、5 8 、6 0 、6 1 、6 4 、6 7 ，自由曲線變形 5 4 、5 6 】， 三維變形 2 7 、2 8 、5 3 、5 5 1 。 變形通常要解決兩個關(guān)鍵問題：第一是建立初末兩物體的元素( 如頂點，邊， 角度等) 之間的對應(yīng)關(guān)系，稱為對應(yīng)問題( c o r r e s p o n d e n c e p r o b l e m ) ；第二是通過 插值初束兩物體的對應(yīng)元素產(chǎn)生中間狀態(tài)，稱為插值問題( i n t e r p o l a t i o n p r o b l e m ) 。 目前國內(nèi)外已有許多有關(guān)變形的研究成果，給出了解決變形問題的比較有效的算 法，但遺憾的是，變形是一種視覺效果，與人的審美標準密切榻關(guān)，主觀因素很 大，因此對于變形的兩個問題什么是成功地解決方案，還沒有正式明確的定義， 但研究者普遍認為一個令人滿意的變形應(yīng)該滿足以下三個條件： 1 變形過程中產(chǎn)生的中間狀態(tài)的一些特征，如邊長、夾角、面積等應(yīng)保持單 調(diào)平滑的變換。 2 變形過程中產(chǎn)生的中間狀態(tài)沒有出現(xiàn)自交、收縮、內(nèi)部區(qū)域發(fā)生扭曲等不 自然現(xiàn)象。 3 中間狀態(tài)要保持初始狀態(tài)和目標狀態(tài)的視覺特征。 目前已經(jīng)有許多的變形算法，其類型及其復雜性在很大程度上取決于物體的表示 第一章緒論 方法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，因此不同的表示方法所采用的變形算法也不盡相同，大 致分為以下三類： 1 基于體元表示 物體的體元表示即一個三維物體表示成定義在整個3 d 空間上的函數(shù)的水平 集，假設(shè)物體表示為點集p ，使得廠( p ) = c ，則( p ) = c 即為該物體的體元表示。 2 基于正視圖( e l e v a t i o nm a p ) 表示 該表示方法在地貌造型和圖像變形中有著重要的應(yīng)用。例如2 d 圖像可以看作 是在像素格上由正視圖( e l e v a t i o nm a p ) 定義的顏色映射。 3 基于邊界表示 物體的邊界表示是指物體由多邊形( 多面體) 和參數(shù)曲線( 曲面) 如樣條曲 線( 曲面) 這兩個主要模型來構(gòu)成其邊界的表示方法，有相當多的物體是以其邊 界表示的。 1 2 國內(nèi)外研究綜述 目前國內(nèi)外研究者通常主要研究變形的某一個問題：或主要研究變形的對應(yīng) 問題，其插值問題則用簡單的頂點線性插值法來解決；或假設(shè)對應(yīng)關(guān)系已經(jīng)給定 的前提條件下對插值問題進行研究，也有一些研究者同時研究這兩個問飚。其中 對應(yīng)問題的研究相對比較少，更多研究成果則是插值問題方面的。 1 2 1 對應(yīng)問題 在變形對應(yīng)問題的研究中，每一種算法都各有其適用范圍。在文獻 5 8 1 中 t h o m a sw s e d e r b e r g 基于一種物理模型，把平面多邊形的邊看作為金屬絲，通過使 得初始多邊形經(jīng)過彎曲或者伸縮變?yōu)槟繕硕噙呅螘r所做的功最小來建立初末多邊 形頂點的對應(yīng)關(guān)系，該方法適用于兩個相似的平面多邊形；k a n a i 在其文獻【5 5 】中 利用h a r m o n i c 映照使得初始和目標多面體網(wǎng)格與相應(yīng)的平面網(wǎng)格相對應(yīng)，并將這 兩個平面網(wǎng)格重疊進而建立初末多面體的對應(yīng)關(guān)系，這種方法適用于兩個同胚于 3 d 球或2 d 圓盤的可以不相似的多面體；文獻 5 e eg r e g o r y 用特征點把多面體網(wǎng) 格對應(yīng)分片，通過對分片的對應(yīng)，建立兩多面體的對應(yīng)關(guān)系，該方法適用于兩個 第一章緒論 不相似的同胚的簡單( 或非簡單) 多面體；在文獻 1 5 中d e c a r l o 利用初末曲面上 的稀疏控制網(wǎng)格建立虧格不同的曲面之間的對應(yīng)關(guān)系，該方法適用于拓撲結(jié)構(gòu)不 同的曲面。關(guān)于對應(yīng)問題，將在第二章詳細的介紹。 1 2 2 插值問題 對變形插值問題的研究常常是在假設(shè)對應(yīng)關(guān)系已經(jīng)確定的前提條件下進行 的。在文獻 2 5 】中h e r m a n nb i r k h o l z 和 5 2 】中b e i e r 提出的圖像變形的方法，都是 基于一種影響場，通過在初末圖像中使用若干條對應(yīng)的輔助線來完成圖像的對應(yīng) 和插值，從而實現(xiàn)圖像變形。這是一種較成功的圖像變形方法，但在有些情況下 會出現(xiàn)病態(tài)，即某些時刻的中間圖像產(chǎn)生重疊、相交。在解決多邊形、多面體、 曲線和曲面的插值問題的方法中，一個最簡單的方法是頂點線性插值法，這種方 法生成速度快，但變形中可能引起邊界的非正常萎縮，產(chǎn)生自交，一些簡單的幾 何特征如長度、角度等不能一致的變化，原因是各個頂點在變形過程中缺乏聯(lián)系， 其路徑是相互獨立的。在文獻【1 中k a u l 和r i o s s i g n a c 同時研究變形的對應(yīng)問題和 插值問題，提出了基于m i n k o w s k is u m 的算法，使得這兩個問題同時得到解決， 但該方法很容易混淆物體的相似部分，使得變形效果不理想。1 9 9 3 年s e d e r b e r g 和 王國瑾等在 5 7 1 q b 提出了關(guān)于平面多邊形變形的內(nèi)在解算法，1 9 9 8 年建立了用于空 間多邊形或多面體變形的新算法m s i ( 見【1 】) 。該方法首先找出初末多邊形或多面 體的頂點在局部直角坐標中的極坐標或者球面坐標，即內(nèi)在解，通過線性插值其 內(nèi)在變量重構(gòu)出中間狀態(tài)。這種方法能夠體現(xiàn)多邊形或者多面體的內(nèi)在結(jié)構(gòu)特征， 且生成速度快，取得了較好的變形效果，但是由于邊界的各個部分之間缺乏聯(lián)系， 沒有明確地考慮到多邊形或多面體的內(nèi)部，所以許多情況下邊界容易自交，內(nèi)部 面積( 體積) 在變形中易產(chǎn)生扭曲。為了克服內(nèi)在解算法中出現(xiàn)的容易自交的問 題，s h a p i r a 和r a p p o p o r t 4 2 利用多邊形的星骨架表示方法提出了一種新的插值方 法，該方法首先構(gòu)造初末多邊形的同構(gòu)的星骨架，然后線性插值相應(yīng)的元素如邊 長、角度等得出中間多邊形。由于它即考慮到了多邊形的邊界，也考慮到了多邊 形的內(nèi)部，故減少了變形過程中產(chǎn)生自交的可能性。 a l e x a 3 6 將初末物體分解成同構(gòu)的單純復形，在兩個對應(yīng)單純形之間定義仿 射變換并將其表示成旋轉(zhuǎn)變換和伸縮變換的復合，將這兩種變換線性插值得到 第一章緒論 期望的仿射變換，然后通過使得中間物體在最小二乘的意義下逼近該期望的仿射 變換，從而達到扭曲最小的效果。該方法考慮了物體的內(nèi)部，且變形具有剛性， 因而變形過程比較自然，且不易產(chǎn)生自交，但是該方法計算量比較大。f 1 0 a t e r 和 g o t s m a n 1 9 基于平面三角網(wǎng)格的內(nèi)頂點的凸組合表示方法，提出了具有相同凸邊 界的同構(gòu)三角網(wǎng)格的變形方法，稱為凸組合變形，該方法能夠使得中間三角網(wǎng)格 始終與初末網(wǎng)格同構(gòu)，不產(chǎn)生自交，且變形過程連續(xù)光滑，這給以后可保證不自 交的變形算法的研究打下了基礎(chǔ)。受 1 9 方法的啟發(fā)，g o t s m a n 和s u r a z h s k y f 6 0 給出了可避免自交的平面簡單多邊形的變形方法，它將初末多邊形分別嵌入到兩 個具有相同凸邊界的同構(gòu)平面三角網(wǎng)格中，通過采用文獻【1 9 】中的方法對這兩個三 角網(wǎng)格進行變形，以此實現(xiàn)多邊形的變形。該方法首次徹底的解決了平面簡單多 邊形的變形中產(chǎn)生自交的問題，而且也是到目前為止唯一能夠保證變形的中間狀 態(tài)不自交的變形方法。并且應(yīng)用于圖像變形，也可以保證中間圖像不產(chǎn)生折疊。 f l o a t e r 和g o t s m a n 1 9 的凸組合變形方法能夠保證初末多邊形在變形過程中不 產(chǎn)生自交，且變形過程連續(xù)光滑。但是在進行變形前，先要對初術(shù)多邊形進行同 構(gòu)三角剖分，這是一項十分復雜和艱苦的工作。對于同構(gòu)三角網(wǎng)格的研究將在第 三章詳細介紹。對插值問題的研究將在第四章詳細介紹。 1 3 論文研究內(nèi)容及結(jié)果 在國內(nèi)外二維圖形變形的基礎(chǔ)上，本文將在假設(shè)初末物體的對應(yīng)關(guān)系已經(jīng)確 立的前提條件下對變形的插值問題進行研究，本文的若干研究結(jié)果，有的綜合了 已有算法的優(yōu)點，在原有算法的基礎(chǔ)上進行了改進，使得原有的算法更加完善。 有的結(jié)果則是針對現(xiàn)有算法的不足與缺陷，提出了更好的算法，解決了原有算法 的缺陷，得到了更加令人滿意的結(jié)果。本文的研究內(nèi)容及研究結(jié)果如下： 1 ) 平面多邊形的相似同構(gòu)三角剖分，提出了基于初始多邊形和目標多邊形的 相似性的同構(gòu)三角剖分。該方法將初始多邊形和目標多邊形的相似性考慮進來， 首先在不添加額外頂點的情況下三角剖分掉初始和目標多邊形的相似部分，能夠 達到對初始和目標多邊形簡化的效果，在此簡化的初始和目標多邊形基礎(chǔ)上進行 同構(gòu)三角剖分，能夠達到簡化原始的初始和目標多邊形之間的同構(gòu)三角剖分的效 果。應(yīng)用該方法能夠減少進行同構(gòu)三角剖分增加的額外頂點個數(shù)，從而減少了多 第一章緒論 邊形變形的復雜度。 2 ) 基于小波的多邊形變形算法，提出了平面簡單多邊形的簡單有效的變形算 法。該方法結(jié)合了小波算法和多邊形的同構(gòu)三角剖分變形算法，通過實踐證明了 運用該方法能夠減輕同構(gòu)三角剖分的難度，以及減少了進行變形的計算量，從而 達到實時的效果，而且變形也可以取得令人滿意的變形效果。 3 ) 平面凸網(wǎng)格的保凸變形研究，提出了具有不同凸邊界的同構(gòu)平面三角網(wǎng)格 的保凸變形方法。本文提出了基于角度的的保凸變形算法變形網(wǎng)格的凸邊界，并 給出了該算法保凸的理論證明，且具有凸邊界內(nèi)角按同速度變化的性質(zhì)，對網(wǎng) 格的內(nèi)部頂點采用凸組合方法。本文方法能夠保證網(wǎng)格邊界在變形過程中始終保 持凸性，且任意時刻的中間網(wǎng)格與初末網(wǎng)格同構(gòu)，即不產(chǎn)生自交現(xiàn)象。 第二章對應(yīng)問題 第二章對應(yīng)問題 初末物體的對應(yīng)問題是進行變形的基礎(chǔ)，也是影響變形質(zhì)量的一個關(guān)鍵環(huán)節(jié)。 初末物體的對應(yīng)問題已經(jīng)有著廣泛的研究4 、9 、1 6 、2 4 、3 0 、3 5 、4 8 、5 5 、5 8 ， 而且取得了較好的成果，但是每一種對應(yīng)方法都有其自身的應(yīng)用范圍。對應(yīng)問題 的研究還有更加光明的研究前景，通過對應(yīng)問題的研究及實現(xiàn)，可以減少應(yīng)用變 形時所需要的手工勞動。 本章的目的在于尋找圖形上對應(yīng)的頂點位置。給定兩個初末物體，如果僅僅 需要建立的對應(yīng)關(guān)系是物體的邊界點對應(yīng)關(guān)系，可以通過使得從初始物體變形到 目標物體時所做的功最小或者采用加權(quán)的形式等方法決定初末物體之間的頂點對 應(yīng)關(guān)系。如果同時需要建立內(nèi)部頂點的對應(yīng)關(guān)系，可以采用嵌入的方法確定兩者 的對應(yīng)關(guān)系，現(xiàn)在平圖的變形技術(shù)不但要求對初末物體的外部頂點，而且需要變 形圖形的內(nèi)部性質(zhì)( 比如邊長，面積，顏色等) ，所以對初末物體的內(nèi)部變形也是 至關(guān)重要的。則本章重點作網(wǎng)格頂點的對應(yīng)介紹。 給定兩個網(wǎng)格a 如和m ，這一過程的結(jié)果是一個重心坐標的集臺風，使得m 上這些重心坐標的幾何體九( 島) 是在m 。上的一個嵌入，反之亦然。想 法就是將一個網(wǎng)格的頂點映射到另一個網(wǎng)格上，以完成m ，和m 之間雙射的主要 部分，經(jīng)過這一步，僅有邊和面需要做相應(yīng)的調(diào)整。 這一步驟的典型做法是為曲面尋找一個公共的參數(shù)域d 。通過將每一個曲面 可逆的映射到參數(shù)域上，圖形間的映射就被建立起來了。在變形的情況下，網(wǎng)格 的典型參數(shù)域是球面s 2 ( 在網(wǎng)格是一拓撲球面的情況下) 或者是一個由分段線性 參數(shù)域描述的拓撲圓盤的集合。在圓盤情況下，網(wǎng)格必須分解成圓盤的同構(gòu)結(jié)構(gòu) ( 這要求原網(wǎng)格是同構(gòu)的) 。一個主要的約束的要考慮用戶指定或自動生成的特征 的對應(yīng)( 如點點對應(yīng)) 。依賴于所選的方法，決定是通過重新參數(shù)化還是按照特征 對應(yīng)分解網(wǎng)格來完成這一步驟。 在映射到球面的情況下，需要計算嵌入九，s = s o ，丑， ，s 。r 3 , = 1 。球面 上的嵌入由一個球面到球面的雙射，按照特征對應(yīng)對齊。 第二章對應(yīng)問題 i ) k 嶼嗷 氐山個耐 $ 。專黟 ， 這個方法里的主要問題是計算球面上的頂點坐標s o ，s 以及重新參數(shù)化映射 _ ，。 分解方法是更普遍也更困難的方法。除了要產(chǎn)生拓撲圓盤的嵌入外，還必須 在考慮可能的特征對應(yīng)的情況下，將網(wǎng)格按同構(gòu)方式分解。形式上，要用一個包 含k 和蜀子集的抽象單純復形來粗略的逼近兩個網(wǎng)格： 辦( 。) ( h ) “辦( 0 ) ( i , v 0 1 ) 且辦m ( h ) “辦( 1 ) ( 1 墨i ) 。典型的，上是k o 年f l k l 的予式，如它是網(wǎng)格的一個劃分 ( p a r t i t i o n ) 。甄和k 1 的頂點視為l 中的某一個面，并且所有屬于一個特殊面的頂 點嵌入到它的平面圖形中。這需要將網(wǎng)格的每一片嵌入到平面上。 f ) k 嶼噍慨) 或山個田 l 刊7 舊 下面就平面圖形的外頂點對應(yīng)方法以及將平面上一單連通的有界或無界網(wǎng)格 嵌入到球面上的技術(shù)作介紹。 2 1 圖形邊界頂點對應(yīng) 2 1 1 基于最小做功的頂點對應(yīng) s e d e r b e r g 等人在受到用力拉伸一根金屬絲，該力做功的啟發(fā)下，在文獻【5 8 】 中提出了基于物理模型的二維多邊形頂點對應(yīng)算法。物體的變形主要由伸縮變換、 旋轉(zhuǎn)變換和平移變換構(gòu)成，做相應(yīng)的變換都會有相應(yīng)的功。 對于伸縮變換有，對一根長度為三。的金屬絲施加大小為p 的個外力，則金 第二章對應(yīng)問題 屬絲會發(fā)生一定的形變，其拉伸長度為：艿= 二睪。其中a 為金屬絲的橫截面的面 f 積，e 為金屬絲的拉伸系數(shù)，這是一個和金屬材料有關(guān)的不變的常量( 例如：鐵 的參數(shù)e 為2 9 0 0 0 0 0 0 p s i ) 。在拉伸金屬絲的過程中，外力p 所作的功為： 形：i 8 2 _ a e ( 2 1 ) 1r 、7 對于根固定的金屬絲，因為a e 是一個不變的衡量，用一個用戶自定義的“固體 拉伸常量”七，替換式中的a e 。如果l 。是一根金屬絲的初始長度，l 。是該金屬絲 的最終長度，當金屬絲的初末狀態(tài)交換的話，公式( 2 1 ) 將得到不同的值( 在初 始狀態(tài)將i 8 2 厶a e ，而在最終狀態(tài)將得到莘e ) 。當多邊形的一條邊縮短成為 一個點時( 即：l o = o ) ，上面的公式將計算得到一個無窮值。對公式( 2 1 ) 改進 得到： s = k s 瓦面告 ( 2 z ) 其中占= 厶一l 。，c 。是用戶定義的一個常量，通過該常量，用戶可以處理當一條邊 縮短成一個點的情況。公式( 2 2 ) 中的指數(shù)2 只有在金屬絲為線性彈性的情況下 才能適用，即金屬絲的伸縮變換不是太劇烈的情況下。如果伸縮變換太劇烈，則 實際所用的功比通過公式計算所得到的結(jié)果要小。那是因為在這種情況下，金屬 絲已經(jīng)發(fā)生了彈性形變，用指數(shù)1 替代公式中的指數(shù)2 更能描述拉伸或者壓縮金 屬絲所作的功。因此，對計算拉伸或者壓縮金屬絲所作的功的公式( 2 2 ) 做最終 的改變?nèi)缦拢恍? k 。l 一c 。j m m l i l ， l - 。l j + 。l i i 茜瓦云j 萬，其中七。，。和氣是 用戶定義的常量。 在現(xiàn)實中的物理模型中，上面的公式只有在處理金屬絲被拉長的情況下( 即： 厶 厶的情況下) 才有意義，處理被壓縮( l ； 厶) 的情況下沒實際意義。但是， 為了變形的問題，必須處理拉伸和壓縮兩種情況。因此設(shè)l 。= 1 1 只- & oi ， 厶= 慨一p 0 定義睨( f 0 ，j o ， i l ， ) 如下： 第二章對應(yīng)問題 彬( 地1 ) = ( 1 - c , ) m 型i n ( l o 生, l 1 ) 監(jiān)+ c ，m a x ( l o , l , ) ( 2 3 ) 拉伸就相當于將氣一只映射到0 。一只，其中= i 。或者f = i 。+ 1 ， = j ?；蛘?j 【= j o + 1 。 對于旋轉(zhuǎn)變換，需要解決從初始多邊形的一個角度變換成目標多邊形相應(yīng)角 度問題。對于從角z ( e o ，p 。o ，磺) 變換到角么( p l 爿，p ，o ：) ，定義其功為： ( f 0 ， ， f l ，朋， f 2 ，五】) ： 吒( 目+ m b a o 。 ) 。如果v o ，1 】，目( f ) o( 2 4 ) l k e ( z x o + r n , a o + ) “+ p h 如果| f 0 【o ，l 】，o ( t o ) = o 、 其中曰和a 0 + 在文獻【5 8 的2 1 節(jié)與2 2 節(jié)給出了定義，占( f ) 是從初始角度變換到 目標角度的中間角度，k 。，m 。，e 。和既是用戶定義的常數(shù)變量，常量屯是表示 物體彎曲的難度系數(shù)，m 。是補償系數(shù)，適合于當角度變換不是單調(diào)變換，e 。是一 個和e s 扮演相同角色的指數(shù)，仇是處理當岔( f ) 經(jīng)過零的補償常量。 頂點之間的對應(yīng)關(guān)系通過上面的伸縮變換所做的功( 2 3 ) 和旋轉(zhuǎn)變換所做的 功( 2 4 ) 之和最小來決定的，當對公式中的常數(shù)變量設(shè)定不同的值時，所得到的 對應(yīng)關(guān)系很可能也不一樣。該方法適用于兩個相似的平面多邊形。 2 1 。2 基于最小成本的頂點對應(yīng) h e n r yj o h a n 等人在文獻 2 4 1 中提出了一種頂點對應(yīng)算法，該算法延伸了 s e d e r b e r g 等人在文獻 5 8 中提出的最小能量算法和s c o h e n 等人在文獻【4 8 中提出 的頂點對應(yīng)算法。 h e n r y 在s e d e r b e r g 的思想上提出了一種新的成本算法。在該算法里，首先定 一 d +d 義了在頂點處的切線方向f 2 霞 三 赫其中代表初始或者目標l 其中各變 量如圖2 - 1 所示，并且定義算子如下： 9 第二章對應(yīng)問題 l 瓤 蹲! 孥斛只+ 、霄 l j 圖2 1 ( a ) 頂點處豹切向量定義與( b ) 角度成本計算 s x ) = ：i o 。；：o z ( j ，薈) = 4 b a y b x i g n ( 0 0 s x ) = 1 1 ox z t 一繃= 4 d y 一 從而得到在頂點p 處的角度成本為： a n g l e ( p ，) = ：1a r c c o s ( p f ：l ，只：i ) s i g n ( z ( 只：j ，只：i ) ) 頂點只5 處的參數(shù)簡單的定義為二( 擰為初始多邊形的頂點個數(shù)) ，同理可定義處 的參數(shù)為上( 聊為目標多邊形的頂點個數(shù)) ，則通過角度成本和參數(shù)成本表示的初 始多邊形的第i 個頂點與目標多邊形的第，個頂點對應(yīng)的成本函數(shù)為： c 。s 砸，) = q i g 拓( f ) 一鯽咖( 哆) i + 叻島一丟1 其中與口，為相應(yīng)的權(quán)值系數(shù)，剛頂點之間的對應(yīng)關(guān)系可以通過使得 n c o s t ( i ， ，( i ) ) 最小來求得，即求解m m c o s t ( ，j ( f ) ) 。 2 1 3 模糊的頂點對應(yīng) x i a o y ij i a n g 等人在文獻 6 5 】中提出了新的變形算法，其具體內(nèi)容將在第四章 作詳細介紹。在該文中，作者先將初末圖形用向量串表示，然后采用【4 5 】中從初始 向量串變形到目標向量串所定義的編輯算子，并且采用該文中計算兩向量串距離 的算法計算用向量串表示的初末兩幅圖形的距離，在計算初末圖形距離的同時， 初末向量串中各元素之間的對應(yīng)關(guān)系也就確定了下來。 1 0 第二章對應(yīng)問題 2 1 4 結(jié)論與比較 平面圖形邊界頂點的對應(yīng)算法的最大不同點在于定義了不同的成本計算方法。 在定義了成本計算方法之后，通過計算頂點之間的最小成本來確定頂點之間的對 應(yīng)關(guān)系。該類頂點對應(yīng)方法在初末圖形是相似的情況下，效果比較明顯，一旦初 術(shù)圖形有較大的差異，則會導致變形過程出現(xiàn)自交等不良現(xiàn)象。 2 2 基于網(wǎng)格的頂點對應(yīng)方法 三維圖形邊界的單連通( s i m p l y c o n n e c t e d ) 部分同構(gòu)于一圓盤，因此稱為拓 撲圓盤。為了尋找這些單連通片的一個參數(shù)化，需要定義一個從有界單連通網(wǎng)格 到平面的一個雙射。 在實際的應(yīng)用中，需要尋找片與片之間的雙射。這里關(guān)注從任意有界單連通 網(wǎng)格到單位圓盤上的映射，使得網(wǎng)格邊界頂點位于單位圓上。這里僅局限于幾種 參數(shù)化方法，這些方法允許三角化曲面的邊界是非凸的或者沒有固定是優(yōu)先獲得 更光滑的還是更少扭曲的邊界映射【1 1 、2 1 、2 2 】。 第一步，將邊界頂點固定在單位圓上。首先，從基域三取三個點，按等角方式 固定在單位圓上，這是取保基域中相鄰的面在經(jīng)過基域邊是有一個連續(xù)的參數(shù)化 所必要的。剩余的邊界頂點按弧長與原邊長成比例的方式固定。剩余的內(nèi)部頂點 是自由的，它們的位置由其與相鄰點的關(guān)系確定。 大部分已發(fā)表的方法是令一個由該頂點相對于其鄰點的關(guān)系表示的二次誤差 函數(shù)最小來確定內(nèi)部頂點。這樣內(nèi)部頂點的確定可以簡化為一個線性方程組的求 解問題。非線性的方法或者是使一高次函數(shù)最小化或者利用算法本身的性質(zhì)( 如 g r e g r o 等 4 、5 ，用戶指定一對對應(yīng)頂點，通過最短路徑確定內(nèi)頂點的對應(yīng)關(guān)系) 。 更明確的說，令f - g 。 是要映射到圓盤上的頂點，其中自由的內(nèi)部頂點的下標為 0 蘭i ”，固定的邊界點下標為仃i n ，下面的目標是要尋找平面上點的位置， i i = 1 ，n 莖i 0 ( 2 5 ) 然而，如果將這個二次表達式作為保證有效的平面嵌入的準則，則是不方便 的，這也是為什么多數(shù)方法轉(zhuǎn)而更嚴格但卻更有效的線性條件的原因。 接下來，將討論三種定義線性系統(tǒng)的方法，這些線性系統(tǒng)的解將產(chǎn)生頂點的 位置，另外還將說明g r e g o r y 等 4 、5 】的d i v i d & c o n q u e r 方法。 2 2 1 重心映射 t u t t e 6 6 已經(jīng)證明了怎樣利用重心映射將平圖映射到平面上。在約束假設(shè)中， 思想很簡單，就是將每一個頂點置于它的相鄰點的中心： w i = l d j j e n ( o ， ( 2 6 ) 設(shè)人= ， ，= 1 i , ，j ) 仨e k 世 q ， 則( 2 6 ) 式可以寫成線性方程組的形式： ( 卜a ) 矩陣( ，一a ) 是滿秩的，這樣方程組( 2 8 ) 就有唯一解。1 e 【6 6 】已經(jīng)證明這 個解是網(wǎng)格的一個有效嵌入。 注意到，網(wǎng)格的形狀并不影響頂點在平面上的位置，嵌入中的所有信息均來 自于k ，顯然這樣的嵌入并不能反映網(wǎng)格的頂點位置y 所蘊涵的幾何性質(zhì)。下面 試著混合原圖形的這些信息。 1 2 一 k 孫 盛磁 盛 第二章對應(yīng)問題 2 2 2 保形參數(shù)化 在重心映射中，權(quán)系數(shù)兄僅包含拓撲信息。f l o a t e r 3 9 】定義了反映網(wǎng)格局部形 狀的權(quán)系數(shù)，更準確的說，就是權(quán)系數(shù) 的選擇考慮了某頂點周圍的角度以及邊的 長度。 為了計算某特定點h 的權(quán)值，這個點先被置于原點，與它相連的邊按原來的長 度置于平面上，相應(yīng)的角度則與原圖形的角度成比例，這被假定為網(wǎng)格關(guān)于v 最理 想的參數(shù)化。 權(quán)值按以下方式進行：即如果相鄰點一已固定，那么所求的權(quán)值將使w f 置于 原點，并且必須求解線性方程組。這樣有 = ( ，磊，釓嵋 皿， 且 ，= 1( 2 1 0 ) 如果v j 僅有三個相鄰點，則上式將唯一確定一組權(quán)值；如果v j 有三個以上的相 鄰點，那么正的權(quán)值就必須從可能的解空間里選擇。權(quán)值的正性導致了凸組合， 這是確保一個有效嵌入的必要條件。f l o a t e r 給出了一個計算正權(quán)值的方法：取循 環(huán)有序的相鄰點集合五( f ) ，k z “、，對每一個七，產(chǎn)生一組非負權(quán)值，平均這 些權(quán)值以產(chǎn)生最終的權(quán)值： 五，2 南乳 ) ( 2 - 1 1 ) 有關(guān)正權(quán)值的計算將在后面章節(jié)做詳細的說明。確定權(quán)值后，的位置由方程組 ( 2 8 ) 給出。晟后f l o a t e r 4 0 、4 l 】證明了t u t t e 定理的一個一般化的結(jié)論，其中表 明每一個頂點都表示為其相鄰點的凸組合是產(chǎn)生有效嵌入的充分條件。 2 2 3 離散調(diào)和映射 調(diào)和映射( h a r m o n i cm a p p i n g ) 是幾個應(yīng)用微分的數(shù)學領(lǐng)域中的個概念。調(diào) 第二章對應(yīng)問題 和映射經(jīng)常被描述為在所有映射到給定區(qū)域q 的函數(shù)中，使d i r e c h l e t 能量 ( w ) = 了1 l v j 2 ( 2 1 2 ) 最小的函數(shù)“。p i n k a l l 和p o l t h i e r 5 9 說明了如何在三角形上離散這個問題，使得 每一點的權(quán)值都可以導出，并且可以得出一個形如方程組( 2 8 ) 的線性方程組。 更詳細的推導可參看p o l t h i e r 3 3 】，在這篇文章里，離散的d i r e c h l e t 能量用下式表 示： 啪飛1l 戮c o t 口, , j + c o t 屆。) 1 1 ，廣。1 2 ( 2 1 3 ) 口。= z ( i ，j ) ，屈，= 么( f ，k ，) ， f ，t k 每一點的最小解為 這樣可求得權(quán)值 0 = i 1 ( c o t 口u + c o t p , ，j ) ( _ - - v j ) j ( j ) 枷j。n(監(jiān)o(cotai u j k i r k 五廣 ，+ c o t 屬，) 【0 f ， ek 這些權(quán)值代入式( 2 8 ) 中可求得一個嵌入。 2 2 4 保面積的d i v i d & c o n q u e r 映射 ( 2 1 4 ) ( 2 1 5 ) g r e g o r y 等 4 、5 描述了一個遞歸算法，其目的是在映射中保持三角形的面積。 基本思想就是促使映射遞歸的將片( p a t c h ) 分割兩部分，每一部分再獨立的映射。 這些分割的選擇使得原網(wǎng)格與嵌入中的面積比大致相同。 特別的，選擇直徑上的兩個頂點。最短路徑按d i j k s t r a 的算法計算。這條路徑 映射成連接兩頂點的線段。然后改變路徑使得在嵌入中與在三角曲面上的面積比 差異最小。這些線段將每一片網(wǎng)格分成兩半，每半再按同樣的方式進行，直