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

西- i l - e 業(yè)大學(xué)碩士學(xué)位論文 摘要 變形，是指從初始物體到目標(biāo)物體的連續(xù)、光滑、自然的過(guò)渡( 這里的物體 可以是數(shù)字圖像、曲線、曲面、網(wǎng)格等) 。變形有著十分廣泛的應(yīng)用，如計(jì)算機(jī) 圖形學(xué)、動(dòng)畫設(shè)計(jì)、工業(yè)造型、科學(xué)計(jì)算可視化、電影特技等。本文對(duì)同構(gòu)平面 三角網(wǎng)格的變形和平面多邊形的變形算法進(jìn)行了研究，主要的研究結(jié)果如下： 1 ) 平面多邊形的相似同構(gòu)三角剖分。本文提出了基于初始多邊形和目標(biāo)多 邊形之間相似性的同構(gòu)三角剖分算法。該方法將初始多邊形和目標(biāo)多邊形的相似 性進(jìn)行分析，在不添加額外頂點(diǎn)的情況下，首先進(jìn)行初始和目標(biāo)多邊形的相似部 分三角剖分，得到相應(yīng)的簡(jiǎn)化初末多邊形，該過(guò)程能夠起到對(duì)初始和目標(biāo)多邊形 簡(jiǎn)化的作用，對(duì)此簡(jiǎn)化初始和目標(biāo)多邊形進(jìn)行相應(yīng)的同構(gòu)三角剖分。這樣能夠減 少在原始的初始和目標(biāo)多邊形之間的同構(gòu)三角剖分的計(jì)算，以達(dá)到好的的效果。 應(yīng)用該算法能夠減少進(jìn)行同構(gòu)三角剖分需要增加的額外頂點(diǎn)的個(gè)數(shù)，從而能夠減 少多邊形變形的復(fù)雜度和計(jì)算量。 2 ) 基于小波的平面多邊形變形算法。該算法首先將初始和目標(biāo)多邊形進(jìn)行 適當(dāng)?shù)男〔ǚ纸?，得到相?yīng)的輪廓多邊形和細(xì)節(jié)部分，再分別對(duì)輪廓多邊形和細(xì) 節(jié)進(jìn)行變形，最后通過(guò)重構(gòu)算法得到中間多邊形。該算法在保持多邊形輪廓不自 交上有顯著的改善，因?yàn)樵撍惴軌蛟诤艽蟪潭壬媳ＷC輪廓多邊形不自交，從而 能夠?qū)⒃撍惴ㄅc同構(gòu)三角網(wǎng)格變形算法相結(jié)合，結(jié)合兩者的優(yōu)點(diǎn)。通過(guò)實(shí)踐證明 了運(yùn)用該算法能夠減輕同構(gòu)三角剖分的難度，以及減少進(jìn)行變形的計(jì)算量，進(jìn)而 達(dá)到實(shí)時(shí)的效果，而且變形取得令人滿意的效果。 3 ) 平面凸網(wǎng)格的保凸變形研究。本文提出了具有不同凸邊界的同構(gòu)平面三 角網(wǎng)格的保凸變形算法。本文提出了基于角度的的保凸變形算法變形網(wǎng)格的凸邊 界，并給出了該算法保凸的理論證明，且具有凸邊界內(nèi)角按同一速度變化的性質(zhì)。 對(duì)網(wǎng)格的內(nèi)部頂點(diǎn)采用凸組合方法。本文方法能夠保證網(wǎng)格邊界在變形過(guò)程中始 終保持凸性，且任意時(shí)刻的中間網(wǎng)格與初末網(wǎng)格同構(gòu)，即不產(chǎn)生自交現(xiàn)象。 關(guān)鍵詞：同構(gòu)三角網(wǎng)格，相似性剖分，簡(jiǎn)化多邊形，小波變換，多分辨分析， 輪廓多邊形，細(xì)節(jié)信息，額外頂點(diǎn)，避免自交，保凸變形，凸組合 西北工業(yè)大學(xué)碩士學(xué)位論文 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è)大學(xué)碩士學(xué)位論文 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 ) 等，是指從初始物體到目標(biāo)物體的連續(xù)、光滑、自然 的過(guò)渡( 這里的物體可以是數(shù)字圖像、多邊形、多面體等) 。變形技術(shù)在許多領(lǐng)域 有著十分廣泛的應(yīng)用，如計(jì)算機(jī)圖形學(xué)、動(dòng)畫設(shè)計(jì)、工業(yè)造型設(shè)計(jì)、虛擬現(xiàn)實(shí)、 科學(xué)計(jì)算可視化、電影特技制作等領(lǐng)域。變形應(yīng)用于計(jì)算機(jī)動(dòng)畫，可以減輕美工 師的手工勞動(dòng)；在產(chǎn)品造型設(shè)計(jì)中，應(yīng)用變形可以把不同造型特征相互交融，產(chǎn) 生新的造型系列；變形應(yīng)用于電影制作，可以產(chǎn)生奇特的電影特技效果，給人以 美的視覺(jué)享受。隨著現(xiàn)代信息社會(huì)和變形技術(shù)的不斷發(fā)展，變形將會(huì)有更加廣泛 的應(yīng)用。變形問(wèn)題已經(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 。 變形通常要解決兩個(gè)關(guān)鍵問(wèn)題：第一是建立初末兩物體的元素( 如頂點(diǎn)，邊， 角度等) 之間的對(duì)應(yīng)關(guān)系，稱為對(duì)應(yīng)問(wèn)題( c o r r e s p o n d e n c e p r o b l e m ) ；第二是通過(guò) 插值初束兩物體的對(duì)應(yīng)元素產(chǎn)生中間狀態(tài)，稱為插值問(wèn)題( i n t e r p o l a t i o n p r o b l e m ) 。 目前國(guó)內(nèi)外已有許多有關(guān)變形的研究成果，給出了解決變形問(wèn)題的比較有效的算 法，但遺憾的是，變形是一種視覺(jué)效果，與人的審美標(biāo)準(zhǔn)密切榻關(guān)，主觀因素很 大，因此對(duì)于變形的兩個(gè)問(wèn)題什么是成功地解決方案，還沒(méi)有正式明確的定義， 但研究者普遍認(rèn)為一個(gè)令人滿意的變形應(yīng)該滿足以下三個(gè)條件： 1 變形過(guò)程中產(chǎn)生的中間狀態(tài)的一些特征，如邊長(zhǎng)、夾角、面積等應(yīng)保持單 調(diào)平滑的變換。 2 變形過(guò)程中產(chǎn)生的中間狀態(tài)沒(méi)有出現(xiàn)自交、收縮、內(nèi)部區(qū)域發(fā)生扭曲等不 自然現(xiàn)象。 3 中間狀態(tài)要保持初始狀態(tài)和目標(biāo)狀態(tài)的視覺(jué)特征。 目前已經(jīng)有許多的變形算法，其類型及其復(fù)雜性在很大程度上取決于物體的表示 第一章緒論 方法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，因此不同的表示方法所采用的變形算法也不盡相同，大 致分為以下三類： 1 基于體元表示 物體的體元表示即一個(gè)三維物體表示成定義在整個(gè)3 d 空間上的函數(shù)的水平 集，假設(shè)物體表示為點(diǎn)集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è)主要模型來(lái)構(gòu)成其邊界的表示方法，有相當(dāng)多的物體是以其邊 界表示的。 1 2 國(guó)內(nèi)外研究綜述 目前國(guó)內(nèi)外研究者通常主要研究變形的某一個(gè)問(wèn)題：或主要研究變形的對(duì)應(yīng) 問(wèn)題，其插值問(wèn)題則用簡(jiǎn)單的頂點(diǎn)線性插值法來(lái)解決；或假設(shè)對(duì)應(yīng)關(guān)系已經(jīng)給定 的前提條件下對(duì)插值問(wèn)題進(jìn)行研究，也有一些研究者同時(shí)研究這兩個(gè)問(wèn)飚。其中 對(duì)應(yīng)問(wèn)題的研究相對(duì)比較少，更多研究成果則是插值問(wèn)題方面的。 1 2 1 對(duì)應(yīng)問(wèn)題 在變形對(duì)應(yīng)問(wèn)題的研究中，每一種算法都各有其適用范圍。在文獻(xiàn) 5 8 1 中 t h o m a sw s e d e r b e r g 基于一種物理模型，把平面多邊形的邊看作為金屬絲，通過(guò)使 得初始多邊形經(jīng)過(guò)彎曲或者伸縮變?yōu)槟繕?biāo)多邊形時(shí)所做的功最小來(lái)建立初末多邊 形頂點(diǎn)的對(duì)應(yīng)關(guān)系，該方法適用于兩個(gè)相似的平面多邊形；k a n a i 在其文獻(xiàn)【5 5 】中 利用h a r m o n i c 映照使得初始和目標(biāo)多面體網(wǎng)格與相應(yīng)的平面網(wǎng)格相對(duì)應(yīng)，并將這 兩個(gè)平面網(wǎng)格重疊進(jìn)而建立初末多面體的對(duì)應(yīng)關(guān)系，這種方法適用于兩個(gè)同胚于 3 d 球或2 d 圓盤的可以不相似的多面體；文獻(xiàn) 5 e eg r e g o r y 用特征點(diǎn)把多面體網(wǎng) 格對(duì)應(yīng)分片，通過(guò)對(duì)分片的對(duì)應(yīng)，建立兩多面體的對(duì)應(yīng)關(guān)系，該方法適用于兩個(gè) 第一章緒論 不相似的同胚的簡(jiǎn)單( 或非簡(jiǎn)單) 多面體；在文獻(xiàn) 1 5 中d e c a r l o 利用初末曲面上 的稀疏控制網(wǎng)格建立虧格不同的曲面之間的對(duì)應(yīng)關(guān)系，該方法適用于拓?fù)浣Y(jié)構(gòu)不 同的曲面。關(guān)于對(duì)應(yīng)問(wèn)題，將在第二章詳細(xì)的介紹。 1 2 2 插值問(wèn)題 對(duì)變形插值問(wèn)題的研究常常是在假設(shè)對(duì)應(yīng)關(guān)系已經(jīng)確定的前提條件下進(jìn)行 的。在文獻(xiàn) 2 5 】中h e r m a n nb i r k h o l z 和 5 2 】中b e i e r 提出的圖像變形的方法，都是 基于一種影響場(chǎng)，通過(guò)在初末圖像中使用若干條對(duì)應(yīng)的輔助線來(lái)完成圖像的對(duì)應(yīng) 和插值，從而實(shí)現(xiàn)圖像變形。這是一種較成功的圖像變形方法，但在有些情況下 會(huì)出現(xiàn)病態(tài)，即某些時(shí)刻的中間圖像產(chǎn)生重疊、相交。在解決多邊形、多面體、 曲線和曲面的插值問(wèn)題的方法中，一個(gè)最簡(jiǎn)單的方法是頂點(diǎn)線性插值法，這種方 法生成速度快，但變形中可能引起邊界的非正常萎縮，產(chǎn)生自交，一些簡(jiǎn)單的幾 何特征如長(zhǎng)度、角度等不能一致的變化，原因是各個(gè)頂點(diǎn)在變形過(guò)程中缺乏聯(lián)系， 其路徑是相互獨(dú)立的。在文獻(xiàn)【1 中k a u l 和r i o s s i g n a c 同時(shí)研究變形的對(duì)應(yīng)問(wèn)題和 插值問(wèn)題，提出了基于m i n k o w s k is u m 的算法，使得這兩個(gè)問(wèn)題同時(shí)得到解決， 但該方法很容易混淆物體的相似部分，使得變形效果不理想。1 9 9 3 年s e d e r b e r g 和 王國(guó)瑾等在 5 7 1 q b 提出了關(guān)于平面多邊形變形的內(nèi)在解算法，1 9 9 8 年建立了用于空 間多邊形或多面體變形的新算法m s i ( 見(jiàn)【1 】) 。該方法首先找出初末多邊形或多面 體的頂點(diǎn)在局部直角坐標(biāo)中的極坐標(biāo)或者球面坐標(biāo)，即內(nèi)在解，通過(guò)線性插值其 內(nèi)在變量重構(gòu)出中間狀態(tài)。這種方法能夠體現(xiàn)多邊形或者多面體的內(nèi)在結(jié)構(gòu)特征， 且生成速度快，取得了較好的變形效果，但是由于邊界的各個(gè)部分之間缺乏聯(lián)系， 沒(méi)有明確地考慮到多邊形或多面體的內(nèi)部，所以許多情況下邊界容易自交，內(nèi)部 面積( 體積) 在變形中易產(chǎn)生扭曲。為了克服內(nèi)在解算法中出現(xiàn)的容易自交的問(wè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)的元素如邊 長(zhǎng)、角度等得出中間多邊形。由于它即考慮到了多邊形的邊界，也考慮到了多邊 形的內(nèi)部，故減少了變形過(guò)程中產(chǎn)生自交的可能性。 a l e x a 3 6 將初末物體分解成同構(gòu)的單純復(fù)形，在兩個(gè)對(duì)應(yīng)單純形之間定義仿 射變換并將其表示成旋轉(zhuǎn)變換和伸縮變換的復(fù)合，將這兩種變換線性插值得到 第一章緒論 期望的仿射變換，然后通過(guò)使得中間物體在最小二乘的意義下逼近該期望的仿射 變換，從而達(dá)到扭曲最小的效果。該方法考慮了物體的內(nèi)部，且變形具有剛性， 因而變形過(guò)程比較自然，且不易產(chǎn)生自交，但是該方法計(jì)算量比較大。f 1 0 a t e r 和 g o t s m a n 1 9 基于平面三角網(wǎng)格的內(nèi)頂點(diǎn)的凸組合表示方法，提出了具有相同凸邊 界的同構(gòu)三角網(wǎng)格的變形方法，稱為凸組合變形，該方法能夠使得中間三角網(wǎng)格 始終與初末網(wǎng)格同構(gòu)，不產(chǎn)生自交，且變形過(guò)程連續(xù)光滑，這給以后可保證不自 交的變形算法的研究打下了基礎(chǔ)。受 1 9 方法的啟發(fā)，g o t s m a n 和s u r a z h s k y f 6 0 給出了可避免自交的平面簡(jiǎn)單多邊形的變形方法，它將初末多邊形分別嵌入到兩 個(gè)具有相同凸邊界的同構(gòu)平面三角網(wǎng)格中，通過(guò)采用文獻(xiàn)【1 9 】中的方法對(duì)這兩個(gè)三 角網(wǎng)格進(jìn)行變形，以此實(shí)現(xiàn)多邊形的變形。該方法首次徹底的解決了平面簡(jiǎn)單多 邊形的變形中產(chǎn)生自交的問(wèn)題，而且也是到目前為止唯一能夠保證變形的中間狀 態(tài)不自交的變形方法。并且應(yīng)用于圖像變形，也可以保證中間圖像不產(chǎn)生折疊。 f l o a t e r 和g o t s m a n 1 9 的凸組合變形方法能夠保證初末多邊形在變形過(guò)程中不 產(chǎn)生自交，且變形過(guò)程連續(xù)光滑。但是在進(jìn)行變形前，先要對(duì)初術(shù)多邊形進(jìn)行同 構(gòu)三角剖分，這是一項(xiàng)十分復(fù)雜和艱苦的工作。對(duì)于同構(gòu)三角網(wǎng)格的研究將在第 三章詳細(xì)介紹。對(duì)插值問(wèn)題的研究將在第四章詳細(xì)介紹。 1 3 論文研究?jī)?nèi)容及結(jié)果 在國(guó)內(nèi)外二維圖形變形的基礎(chǔ)上，本文將在假設(shè)初末物體的對(duì)應(yīng)關(guān)系已經(jīng)確 立的前提條件下對(duì)變形的插值問(wèn)題進(jìn)行研究，本文的若干研究結(jié)果，有的綜合了 已有算法的優(yōu)點(diǎn)，在原有算法的基礎(chǔ)上進(jìn)行了改進(jìn)，使得原有的算法更加完善。 有的結(jié)果則是針對(duì)現(xiàn)有算法的不足與缺陷，提出了更好的算法，解決了原有算法 的缺陷，得到了更加令人滿意的結(jié)果。本文的研究?jī)?nèi)容及研究結(jié)果如下： 1 ) 平面多邊形的相似同構(gòu)三角剖分，提出了基于初始多邊形和目標(biāo)多邊形的 相似性的同構(gòu)三角剖分。該方法將初始多邊形和目標(biāo)多邊形的相似性考慮進(jìn)來(lái)， 首先在不添加額外頂點(diǎn)的情況下三角剖分掉初始和目標(biāo)多邊形的相似部分，能夠 達(dá)到對(duì)初始和目標(biāo)多邊形簡(jiǎn)化的效果，在此簡(jiǎn)化的初始和目標(biāo)多邊形基礎(chǔ)上進(jìn)行 同構(gòu)三角剖分，能夠達(dá)到簡(jiǎn)化原始的初始和目標(biāo)多邊形之間的同構(gòu)三角剖分的效 果。應(yīng)用該方法能夠減少進(jìn)行同構(gòu)三角剖分增加的額外頂點(diǎn)個(gè)數(shù)，從而減少了多 第一章緒論 邊形變形的復(fù)雜度。 2 ) 基于小波的多邊形變形算法，提出了平面簡(jiǎn)單多邊形的簡(jiǎn)單有效的變形算 法。該方法結(jié)合了小波算法和多邊形的同構(gòu)三角剖分變形算法，通過(guò)實(shí)踐證明了 運(yùn)用該方法能夠減輕同構(gòu)三角剖分的難度，以及減少了進(jìn)行變形的計(jì)算量，從而 達(dá)到實(shí)時(shí)的效果，而且變形也可以取得令人滿意的變形效果。 3 ) 平面凸網(wǎng)格的保凸變形研究，提出了具有不同凸邊界的同構(gòu)平面三角網(wǎng)格 的保凸變形方法。本文提出了基于角度的的保凸變形算法變形網(wǎng)格的凸邊界，并 給出了該算法保凸的理論證明，且具有凸邊界內(nèi)角按同速度變化的性質(zhì)，對(duì)網(wǎng) 格的內(nèi)部頂點(diǎn)采用凸組合方法。本文方法能夠保證網(wǎng)格邊界在變形過(guò)程中始終保 持凸性，且任意時(shí)刻的中間網(wǎng)格與初末網(wǎng)格同構(gòu)，即不產(chǎn)生自交現(xiàn)象。 第二章對(duì)應(yīng)問(wèn)題 第二章對(duì)應(yīng)問(wèn)題 初末物體的對(duì)應(yīng)問(wèn)題是進(jìn)行變形的基礎(chǔ)，也是影響變形質(zhì)量的一個(gè)關(guān)鍵環(huán)節(jié)。 初末物體的對(duì)應(yīng)問(wèn)題已經(jīng)有著廣泛的研究4 、9 、1 6 、2 4 、3 0 、3 5 、4 8 、5 5 、5 8 ， 而且取得了較好的成果，但是每一種對(duì)應(yīng)方法都有其自身的應(yīng)用范圍。對(duì)應(yīng)問(wèn)題 的研究還有更加光明的研究前景，通過(guò)對(duì)應(yīng)問(wèn)題的研究及實(shí)現(xiàn)，可以減少應(yīng)用變 形時(shí)所需要的手工勞動(dòng)。 本章的目的在于尋找圖形上對(duì)應(yīng)的頂點(diǎn)位置。給定兩個(gè)初末物體，如果僅僅 需要建立的對(duì)應(yīng)關(guān)系是物體的邊界點(diǎn)對(duì)應(yīng)關(guān)系，可以通過(guò)使得從初始物體變形到 目標(biāo)物體時(shí)所做的功最小或者采用加權(quán)的形式等方法決定初末物體之間的頂點(diǎn)對(duì) 應(yīng)關(guān)系。如果同時(shí)需要建立內(nèi)部頂點(diǎn)的對(duì)應(yīng)關(guān)系，可以采用嵌入的方法確定兩者 的對(duì)應(yīng)關(guān)系，現(xiàn)在平圖的變形技術(shù)不但要求對(duì)初末物體的外部頂點(diǎn)，而且需要變 形圖形的內(nèi)部性質(zhì)( 比如邊長(zhǎng)，面積，顏色等) ，所以對(duì)初末物體的內(nèi)部變形也是 至關(guān)重要的。則本章重點(diǎn)作網(wǎng)格頂點(diǎn)的對(duì)應(yīng)介紹。 給定兩個(gè)網(wǎng)格a 如和m ，這一過(guò)程的結(jié)果是一個(gè)重心坐標(biāo)的集臺(tái)風(fēng)，使得m 上這些重心坐標(biāo)的幾何體九( 島) 是在m 。上的一個(gè)嵌入，反之亦然。想 法就是將一個(gè)網(wǎng)格的頂點(diǎn)映射到另一個(gè)網(wǎng)格上，以完成m ，和m 之間雙射的主要 部分，經(jīng)過(guò)這一步，僅有邊和面需要做相應(yīng)的調(diào)整。 這一步驟的典型做法是為曲面尋找一個(gè)公共的參數(shù)域d 。通過(guò)將每一個(gè)曲面 可逆的映射到參數(shù)域上，圖形間的映射就被建立起來(lái)了。在變形的情況下，網(wǎng)格 的典型參數(shù)域是球面s 2 ( 在網(wǎng)格是一拓?fù)淝蛎娴那闆r下) 或者是一個(gè)由分段線性 參數(shù)域描述的拓?fù)鋱A盤的集合。在圓盤情況下，網(wǎng)格必須分解成圓盤的同構(gòu)結(jié)構(gòu) ( 這要求原網(wǎng)格是同構(gòu)的) 。一個(gè)主要的約束的要考慮用戶指定或自動(dòng)生成的特征 的對(duì)應(yīng)( 如點(diǎn)點(diǎn)對(duì)應(yīng)) 。依賴于所選的方法，決定是通過(guò)重新參數(shù)化還是按照特征 對(duì)應(yīng)分解網(wǎng)格來(lái)完成這一步驟。 在映射到球面的情況下，需要計(jì)算嵌入九，s = s o ，丑， ，s 。r 3 , = 1 。球面 上的嵌入由一個(gè)球面到球面的雙射，按照特征對(duì)應(yīng)對(duì)齊。 第二章對(duì)應(yīng)問(wèn)題 i ) k 嶼嗷 氐山個(gè)耐 $ 。專黟 ， 這個(gè)方法里的主要問(wèn)題是計(jì)算球面上的頂點(diǎn)坐標(biāo)s o ，s 以及重新參數(shù)化映射 _ ，。 分解方法是更普遍也更困難的方法。除了要產(chǎn)生拓?fù)鋱A盤的嵌入外，還必須 在考慮可能的特征對(duì)應(yīng)的情況下，將網(wǎng)格按同構(gòu)方式分解。形式上，要用一個(gè)包 含k 和蜀子集的抽象單純復(fù)形來(lái)粗略的逼近兩個(gè)網(wǎng)格： 辦( 。) ( h ) “辦( 0 ) ( i , v 0 1 ) 且辦m ( h ) “辦( 1 ) ( 1 墨i ) 。典型的，上是k o 年f l k l 的予式，如它是網(wǎng)格的一個(gè)劃分 ( p a r t i t i o n ) 。甄和k 1 的頂點(diǎn)視為l 中的某一個(gè)面，并且所有屬于一個(gè)特殊面的頂 點(diǎn)嵌入到它的平面圖形中。這需要將網(wǎng)格的每一片嵌入到平面上。 f ) k 嶼噍慨) 或山個(gè)田 l 刊7 舊 下面就平面圖形的外頂點(diǎn)對(duì)應(yīng)方法以及將平面上一單連通的有界或無(wú)界網(wǎng)格 嵌入到球面上的技術(shù)作介紹。 2 1 圖形邊界頂點(diǎn)對(duì)應(yīng) 2 1 1 基于最小做功的頂點(diǎn)對(duì)應(yīng) s e d e r b e r g 等人在受到用力拉伸一根金屬絲，該力做功的啟發(fā)下，在文獻(xiàn)【5 8 】 中提出了基于物理模型的二維多邊形頂點(diǎn)對(duì)應(yīng)算法。物體的變形主要由伸縮變換、 旋轉(zhuǎn)變換和平移變換構(gòu)成，做相應(yīng)的變換都會(huì)有相應(yīng)的功。 對(duì)于伸縮變換有，對(duì)一根長(zhǎng)度為三。的金屬絲施加大小為p 的個(gè)外力，則金 第二章對(duì)應(yīng)問(wèn)題 屬絲會(huì)發(fā)生一定的形變，其拉伸長(zhǎng)度為：艿= 二睪。其中a 為金屬絲的橫截面的面 f 積，e 為金屬絲的拉伸系數(shù)，這是一個(gè)和金屬材料有關(guān)的不變的常量( 例如：鐵 的參數(shù)e 為2 9 0 0 0 0 0 0 p s i ) 。在拉伸金屬絲的過(guò)程中，外力p 所作的功為： 形：i 8 2 _ a e ( 2 1 ) 1r 、7 對(duì)于根固定的金屬絲，因?yàn)閍 e 是一個(gè)不變的衡量，用一個(gè)用戶自定義的“固體 拉伸常量”七，替換式中的a e 。如果l 。是一根金屬絲的初始長(zhǎng)度，l 。是該金屬絲 的最終長(zhǎng)度，當(dāng)金屬絲的初末狀態(tài)交換的話，公式( 2 1 ) 將得到不同的值( 在初 始狀態(tài)將i 8 2 厶a e ，而在最終狀態(tài)將得到莘e ) 。當(dāng)多邊形的一條邊縮短成為 一個(gè)點(diǎn)時(shí)( 即：l o = o ) ，上面的公式將計(jì)算得到一個(gè)無(wú)窮值。對(duì)公式( 2 1 ) 改進(jìn) 得到： s = k s 瓦面告 ( 2 z ) 其中占= 厶一l 。，c 。是用戶定義的一個(gè)常量，通過(guò)該常量，用戶可以處理當(dāng)一條邊 縮短成一個(gè)點(diǎn)的情況。公式( 2 2 ) 中的指數(shù)2 只有在金屬絲為線性彈性的情況下 才能適用，即金屬絲的伸縮變換不是太劇烈的情況下。如果伸縮變換太劇烈，則 實(shí)際所用的功比通過(guò)公式計(jì)算所得到的結(jié)果要小。那是因?yàn)樵谶@種情況下，金屬 絲已經(jīng)發(fā)生了彈性形變，用指數(shù)1 替代公式中的指數(shù)2 更能描述拉伸或者壓縮金 屬絲所作的功。因此，對(duì)計(jì)算拉伸或者壓縮金屬絲所作的功的公式( 2 2 ) 做最終 的改變?nèi)缦拢恍? k 。l 一c 。j m m l i l ， l - 。l j + 。l i i 茜瓦云j 萬(wàn)，其中七。，。和氣是 用戶定義的常量。 在現(xiàn)實(shí)中的物理模型中，上面的公式只有在處理金屬絲被拉長(zhǎng)的情況下( 即： 厶 厶的情況下) 才有意義，處理被壓縮( l ； 厶) 的情況下沒(méi)實(shí)際意義。但是， 為了變形的問(wèn)題，必須處理拉伸和壓縮兩種情況。因此設(shè)l 。= 1 1 只- & oi ， 厶= 慨一p 0 定義睨( f 0 ，j o ， i l ， ) 如下： 第二章對(duì)應(yīng)問(wèn)題 彬( 地1 ) = ( 1 - c , ) m 型i n ( l o 生, l 1 ) 監(jiān)+ c ，m a x ( l o , l , ) ( 2 3 ) 拉伸就相當(dāng)于將氣一只映射到0 。一只，其中= i 。或者f = i 。+ 1 ， = j 。或者 j 【= j o + 1 。 對(duì)于旋轉(zhuǎn)變換，需要解決從初始多邊形的一個(gè)角度變換成目標(biāo)多邊形相應(yīng)角 度問(wèn)題。對(duì)于從角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 + 在文獻(xiàn)【5 8 的2 1 節(jié)與2 2 節(jié)給出了定義，占( f ) 是從初始角度變換到 目標(biāo)角度的中間角度，k 。，m 。，e 。和既是用戶定義的常數(shù)變量，常量屯是表示 物體彎曲的難度系數(shù)，m 。是補(bǔ)償系數(shù)，適合于當(dāng)角度變換不是單調(diào)變換，e 。是一 個(gè)和e s 扮演相同角色的指數(shù)，仇是處理當(dāng)岔( f ) 經(jīng)過(guò)零的補(bǔ)償常量。 頂點(diǎn)之間的對(duì)應(yīng)關(guān)系通過(guò)上面的伸縮變換所做的功( 2 3 ) 和旋轉(zhuǎn)變換所做的 功( 2 4 ) 之和最小來(lái)決定的，當(dāng)對(duì)公式中的常數(shù)變量設(shè)定不同的值時(shí)，所得到的 對(duì)應(yīng)關(guān)系很可能也不一樣。該方法適用于兩個(gè)相似的平面多邊形。 2 1 。2 基于最小成本的頂點(diǎn)對(duì)應(yīng) h e n r yj o h a n 等人在文獻(xiàn) 2 4 1 中提出了一種頂點(diǎn)對(duì)應(yīng)算法，該算法延伸了 s e d e r b e r g 等人在文獻(xiàn) 5 8 中提出的最小能量算法和s c o h e n 等人在文獻(xiàn)【4 8 中提出 的頂點(diǎn)對(duì)應(yīng)算法。 h e n r y 在s e d e r b e r g 的思想上提出了一種新的成本算法。在該算法里，首先定 一 d +d 義了在頂點(diǎn)處的切線方向f 2 霞 三 赫其中代表初始或者目標(biāo)l 其中各變 量如圖2 - 1 所示，并且定義算子如下： 9 第二章對(duì)應(yīng)問(wèn)題 l 瓤 蹲! 孥斛只+ 、霄 l j 圖2 1 ( a ) 頂點(diǎn)處豹切向量定義與( b ) 角度成本計(jì)算 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 一 從而得到在頂點(diǎn)p 處的角度成本為： a n g l e ( p ，) = ：1a r c c o s ( p f ：l ，只：i ) s i g n ( z ( 只：j ，只：i ) ) 頂點(diǎn)只5 處的參數(shù)簡(jiǎn)單的定義為二( 擰為初始多邊形的頂點(diǎn)個(gè)數(shù)) ，同理可定義處 的參數(shù)為上( 聊為目標(biāo)多邊形的頂點(diǎn)個(gè)數(shù)) ，則通過(guò)角度成本和參數(shù)成本表示的初 始多邊形的第i 個(gè)頂點(diǎn)與目標(biāo)多邊形的第，個(gè)頂點(diǎn)對(duì)應(yīng)的成本函數(shù)為： c 。s 砸，) = q i g 拓( f ) 一鯽咖( 哆) i + 叻島一丟1 其中與口，為相應(yīng)的權(quán)值系數(shù)，剛頂點(diǎn)之間的對(duì)應(yīng)關(guān)系可以通過(guò)使得 n c o s t ( i ， ，( i ) ) 最小來(lái)求得，即求解m m c o s t ( ，j ( f ) ) 。 2 1 3 模糊的頂點(diǎn)對(duì)應(yīng) x i a o y ij i a n g 等人在文獻(xiàn) 6 5 】中提出了新的變形算法，其具體內(nèi)容將在第四章 作詳細(xì)介紹。在該文中，作者先將初末圖形用向量串表示，然后采用【4 5 】中從初始 向量串變形到目標(biāo)向量串所定義的編輯算子，并且采用該文中計(jì)算兩向量串距離 的算法計(jì)算用向量串表示的初末兩幅圖形的距離，在計(jì)算初末圖形距離的同時(shí)， 初末向量串中各元素之間的對(duì)應(yīng)關(guān)系也就確定了下來(lái)。 1 0 第二章對(duì)應(yīng)問(wèn)題 2 1 4 結(jié)論與比較 平面圖形邊界頂點(diǎn)的對(duì)應(yīng)算法的最大不同點(diǎn)在于定義了不同的成本計(jì)算方法。 在定義了成本計(jì)算方法之后，通過(guò)計(jì)算頂點(diǎn)之間的最小成本來(lái)確定頂點(diǎn)之間的對(duì) 應(yīng)關(guān)系。該類頂點(diǎn)對(duì)應(yīng)方法在初末圖形是相似的情況下，效果比較明顯，一旦初 術(shù)圖形有較大的差異，則會(huì)導(dǎo)致變形過(guò)程出現(xiàn)自交等不良現(xiàn)象。 2 2 基于網(wǎng)格的頂點(diǎn)對(duì)應(yīng)方法 三維圖形邊界的單連通( s i m p l y c o n n e c t e d ) 部分同構(gòu)于一圓盤，因此稱為拓 撲圓盤。為了尋找這些單連通片的一個(gè)參數(shù)化，需要定義一個(gè)從有界單連通網(wǎng)格 到平面的一個(gè)雙射。 在實(shí)際的應(yīng)用中，需要尋找片與片之間的雙射。這里關(guān)注從任意有界單連通 網(wǎng)格到單位圓盤上的映射，使得網(wǎng)格邊界頂點(diǎn)位于單位圓上。這里僅局限于幾種 參數(shù)化方法，這些方法允許三角化曲面的邊界是非凸的或者沒(méi)有固定是優(yōu)先獲得 更光滑的還是更少扭曲的邊界映射【1 1 、2 1 、2 2 】。 第一步，將邊界頂點(diǎn)固定在單位圓上。首先，從基域三取三個(gè)點(diǎn)，按等角方式 固定在單位圓上，這是取保基域中相鄰的面在經(jīng)過(guò)基域邊是有一個(gè)連續(xù)的參數(shù)化 所必要的。剩余的邊界頂點(diǎn)按弧長(zhǎng)與原邊長(zhǎng)成比例的方式固定。剩余的內(nèi)部頂點(diǎn) 是自由的，它們的位置由其與相鄰點(diǎn)的關(guān)系確定。 大部分已發(fā)表的方法是令一個(gè)由該頂點(diǎn)相對(duì)于其鄰點(diǎn)的關(guān)系表示的二次誤差 函數(shù)最小來(lái)確定內(nèi)部頂點(diǎn)。這樣內(nèi)部頂點(diǎn)的確定可以簡(jiǎn)化為一個(gè)線性方程組的求 解問(wèn)題。非線性的方法或者是使一高次函數(shù)最小化或者利用算法本身的性質(zhì)( 如 g r e g r o 等 4 、5 ，用戶指定一對(duì)對(duì)應(yīng)頂點(diǎn)，通過(guò)最短路徑確定內(nèi)頂點(diǎn)的對(duì)應(yīng)關(guān)系) 。 更明確的說(shuō)，令f - g 。 是要映射到圓盤上的頂點(diǎn)，其中自由的內(nèi)部頂點(diǎn)的下標(biāo)為 0 蘭i ”，固定的邊界點(diǎn)下標(biāo)為仃i n ，下面的目標(biāo)是要尋找平面上點(diǎn)的位置， i i = 1 ，n 莖i 0 ( 2 5 ) 然而，如果將這個(gè)二次表達(dá)式作為保證有效的平面嵌入的準(zhǔn)則，則是不方便 的，這也是為什么多數(shù)方法轉(zhuǎn)而更嚴(yán)格但卻更有效的線性條件的原因。 接下來(lái)，將討論三種定義線性系統(tǒng)的方法，這些線性系統(tǒng)的解將產(chǎn)生頂點(diǎn)的 位置，另外還將說(shuō)明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è)中， 思想很簡(jiǎn)單，就是將每一個(gè)頂點(diǎn)置于它的相鄰點(diǎn)的中心： 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)證明這 個(gè)解是網(wǎng)格的一個(gè)有效嵌入。 注意到，網(wǎng)格的形狀并不影響頂點(diǎn)在平面上的位置，嵌入中的所有信息均來(lái) 自于k ，顯然這樣的嵌入并不能反映網(wǎng)格的頂點(diǎn)位置y 所蘊(yùn)涵的幾何性質(zhì)。下面 試著混合原圖形的這些信息。 1 2 一 k 孫 盛磁 盛 第二章對(duì)應(yīng)問(wèn)題 2 2 2 保形參數(shù)化 在重心映射中，權(quán)系數(shù)兄僅包含拓?fù)湫畔?。f l o a t e r 3 9 】定義了反映網(wǎng)格局部形 狀的權(quán)系數(shù)，更準(zhǔn)確的說(shuō)，就是權(quán)系數(shù) 的選擇考慮了某頂點(diǎn)周圍的角度以及邊的 長(zhǎng)度。 為了計(jì)算某特定點(diǎn)h 的權(quán)值，這個(gè)點(diǎn)先被置于原點(diǎn)，與它相連的邊按原來(lái)的長(zhǎng) 度置于平面上，相應(yīng)的角度則與原圖形的角度成比例，這被假定為網(wǎng)格關(guān)于v 最理 想的參數(shù)化。 權(quán)值按以下方式進(jìn)行：即如果相鄰點(diǎn)一已固定，那么所求的權(quán)值將使w f 置于 原點(diǎn)，并且必須求解線性方程組。這樣有 = ( ，磊，釓嵋 皿， 且 ，= 1( 2 1 0 ) 如果v j 僅有三個(gè)相鄰點(diǎn)，則上式將唯一確定一組權(quán)值；如果v j 有三個(gè)以上的相 鄰點(diǎn)，那么正的權(quán)值就必須從可能的解空間里選擇。權(quán)值的正性導(dǎo)致了凸組合， 這是確保一個(gè)有效嵌入的必要條件。f l o a t e r 給出了一個(gè)計(jì)算正權(quán)值的方法：取循 環(huán)有序的相鄰點(diǎn)集合五( f ) ，k z “、，對(duì)每一個(gè)七，產(chǎn)生一組非負(fù)權(quán)值，平均這 些權(quán)值以產(chǎn)生最終的權(quán)值： 五，2 南乳 ) ( 2 - 1 1 ) 有關(guān)正權(quán)值的計(jì)算將在后面章節(jié)做詳細(xì)的說(shuō)明。確定權(quán)值后，的位置由方程組 ( 2 8 ) 給出。晟后f l o a t e r 4 0 、4 l 】證明了t u t t e 定理的一個(gè)一般化的結(jié)論，其中表 明每一個(gè)頂點(diǎn)都表示為其相鄰點(diǎn)的凸組合是產(chǎn)生有效嵌入的充分條件。 2 2 3 離散調(diào)和映射 調(diào)和映射( h a r m o n i cm a p p i n g ) 是幾個(gè)應(yīng)用微分的數(shù)學(xué)領(lǐng)域中的個(gè)概念。調(diào) 第二章對(duì)應(yīng)問(wèn)題 和映射經(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 說(shuō)明了如何在三角形上離散這個(gè)問(wèn)題，使得 每一點(diǎn)的權(quán)值都可以導(dǎo)出，并且可以得出一個(gè)形如方程組( 2 8 ) 的線性方程組。 更詳細(xì)的推導(dǎo)可參看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 每一點(diǎn)的最小解為 這樣可求得權(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 ) 中可求得一個(gè)嵌入。 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 描述了一個(gè)遞歸算法，其目的是在映射中保持三角形的面積。 基本思想就是促使映射遞歸的將片( p a t c h ) 分割兩部分，每一部分再獨(dú)立的映射。 這些分割的選擇使得原網(wǎng)格與嵌入中的面積比大致相同。 特別的，選擇直徑上的兩個(gè)頂點(diǎn)。最短路徑按d i j k s t r a 的算法計(jì)算。這條路徑 映射成連接兩頂點(diǎn)的線段。然后改變路徑使得在嵌入中與在三角曲面上的面積比 差異最小。這些線段將每一片網(wǎng)格分成兩半，每半再按同樣的方式進(jìn)行，直