（應用數(shù)學專業(yè)論文）loop細分曲面的曲線插值與形狀控制.pdf

福建師范大學劉曉芬碩士學位論文 摘要 為了增強細分方法表達曲面的能力，滿足實際生產(chǎn)應用中對曲面形狀 控制的需求，本文主要對細分曲面造型方法及其應用進行研究，重點研究 細分曲面插值已知曲線和細分曲面的形狀控制問題。本文首先回顧了細分 曲面的產(chǎn)生背景、歷史和應用，特別是在細分曲面插值和形狀控制方面的 應用。然后介紹了細分曲面造型方法的特點、分類標準和幾種經(jīng)典的細分 方法的定義規(guī)則等。接著，針對三角網(wǎng)格本文提出了基于l o o p 細分方法 的曲線插值方法并證明了該方法的收斂性。該方法不需要修改細分規(guī)則， 只需在被插值曲線的控制多邊形兩側(cè)構造對稱三角網(wǎng)格帶，該對稱三角網(wǎng) 格帶將收斂于插值曲線。因此，包含有該三角網(wǎng)格帶的多面體網(wǎng)格的極限 曲面將經(jīng)過插值曲線。本文還給出了自動構造對稱三角網(wǎng)格帶的算法。若 要插值多條相交曲線只需在交點處構造全對稱三角網(wǎng)格。運用本方法可在 三角網(wǎng)格生成的細分曲面中插值多達六條的相交曲線。在此方法基礎上， 最后本文提出了通過插值曲線控制細分曲面形狀的幾種不同方法。主要基 于兩種思想：一、插值曲線的控制多邊形保持不變，修改對稱三角網(wǎng)格帶 的形狀：二、修改插值曲線的控制多邊形。具體實現(xiàn)方法為：1 、曲率控制： 2 、旋轉(zhuǎn)控制；3 、法向控制：4 、縮放控制：5 、自由變形。 關鍵詞：曲面造型、細分曲面、曲線插值、l o o p 細分、形狀控制 福建師范大學劉曉芬碩士學位論文 a b s t r a c t i no r d e rt oe n h a n c ee x p r e s s i n ga b i l i t yo fs u b d i v i s i o nm e t h o da n ds a t i s f y a c t u a ld e m a n do fs u r f a c e s h a p ec o n t r o l l i n g ，t h i s t h e s i s m a i n l ys t u d i e s m o d e l i n ga n da p p l i c a t i o no fs u b d i v i s i o ns u r f a c e s ，t h ed i s c u s s e dp o i n ti sh o w t o i n t e r p o l a t et h eg i v e nc u r v e si nt h es u b d i v i s i o ns u r f a c ea n dh o wt oc o n t r o l t h es h a p eo fs u b d i v i s i o ns u r f a c e s f i r s t l y ，w er e v i e wt h eb a c k g r o u n d ，h i s t o r y a n da p p l i c a t i o no fs u b d i v i s i o ns u r f a c em o d e l i n g s e c o n d l y ，f o rt r i a n g l em e s h ， w ep r e s e n tt h ec h a r a c t e r i s t i ca n dc l a s s i f i c a t i o no fs u b d i v i s i o nm e t h o d sa n dt h e d e f i n i t i o nr u l e so fs o m er e p r e s e n t a t i v es u b d i v i s i o nm e t h o d s t h i r d l y ，w e p r o p o s eam e t h o dt h a tn e e d n tm o d i f ys u b d i v i s i o nr u l e sf o ru s i n gs y m m e t r i c t r i a n g l es t r i p s h a p e dm e s ht og e n e r a t el o o ps u b d i v i s i o ns u r f a c e sw i t hc u r v e i n t e r p o l a t i o n c o n s t r a i n t s t h e s y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hi s c o n s t r u c t e db yd e s i g n i n gs y m m e t r i ct r i a n g l e sf o rb o t hs i d e so ft h ec o n t r o l p o l y g o no fi n t e r p o l a t e dc u r v e t h i sc o n t r o lp o l y g o ni sr e f e r r e da sc e n t r a l p o l y g o n w ec a np r o v et h a tt h es y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hc a n c o n v e r g et ot h ei n t e r p o l a t e dc u r v e s ot h el i m i t e ds u r f a c eo ft h eg i v e nm e s h w i t ht h es y m m e t r i ct r i a n g l es t r i p s h a p e dm e s hw i l lc o n t a i ni n t e r p o l a t e dc u r v e t h i sp a p e rp r o v i d e st h ea r i t h m e t i co ft h ea u t o m a t i cp r o d u c i n gt h es y m m e t r i c t r i a n g l es t r i p s h a p e dm e s h i ft h ei n t e r p o l a t e dc u r v e si n t e r s e c ta tp o i n tv ，w e c a nd e s i g naf u l ls y m m e t r i ct r i a n g l em e s ha tp o i n tv t h em e t h o dp r o p o s e di n t h i sp a p e rw i l li n t e r p o l a t ei n t e r s e c t i n gc u r v e si nt h eg i v e nm e s h t h en u m b e r s o fi n t e r s e c t i n gc u r v e sa r eu pt os i x o nt h eb a s i so ft h i sm e t h o d ，l a s t l y ，w e p r o p o s es o m em e t h o d st h a tc a nc o n t r o lt h es h a p eo fs u b d i v i s i o ns u r f a c e sw i t h t h ei n t e r p o l a t e dc u r v e t h e ym a i n l yb a s eo nt w oi d e a s o n e ，k e e p i n gt h es h a p e o ft h ec o n t r o lp o l y g o no f i n t e r p o l a t e dc u r v e ，w em o d i f yt h es h a p eo ft h e s y m m e t r i ct r i a n g l es t r i p s h a p e dm e s h t w o ，w em o d i f yt h es h a p eo ft h e c o n t r o lp o l y g o no fi n t e r p o l a t e dc u r v e t h em e t h o d si n c l u d i n g ：1 c u r v a t u r e i i 福建師范大學劉曉芬碩士學位論文 c o n t r o ! l i n g ；2 r e v o l u t i o nc o n t r o l l i n g ；3 n o r m a lc o n t r o l l i n g ；4 z o o m c o n t r o l l i n g ；5 f r e e d o mt r a n s f o r m k e y w o r d s ：s u r f a c em o d e l i n g ，s u b d i v i s i o ns u r f a c e ，c u r v ei n t e r p o l a t i o n ，l o o p s u b d i v i s i o n ，s h a p ec o n t r o l l i n g 福建師范大學劉曉芬碩士學位論文 中文文摘 近年來，細分曲面造型技術已經(jīng)成為計算機輔助幾何設計和計算機圖 形學領域內(nèi)的一個國際性研究熱點。細分曲面除了具有傳統(tǒng)的曲面表示一 一n u r b s 曲面所具有的許多優(yōu)點：簡單高效、局部性、連續(xù)性、仿射不變性 等外，還具有任意拓撲性、可伸縮性、表示一致性、數(shù)值穩(wěn)定性、實現(xiàn)的 簡單性等特點。這些特點使得細分曲面造型技術能夠克服以n u r b s 曲面為 代表的傳統(tǒng)的參數(shù)曲面表示的一些缺點，如在對人的頭、手、自然花卉等 復雜的任意拓撲結(jié)構的曲面進行表示時遇到的裁剪和拼接問題。當前，隨 著計算機圖形顯示對于真實性、實時性和交互性要求的提高和幾何設計對 象復雜度的提升，細分曲面造型技術的應用越來越廣泛，其應用領域包括 工業(yè)造型設計、計算機動畫、計算機游戲和醫(yī)學圖像處理等。 本文主要研究細分曲面造型方法及其應用，重點研究細分曲面插值已 知曲線和細分曲面的形狀控制問題。在實際生產(chǎn)中常常需要對細分曲面進 行曲線插值使得該細分曲面經(jīng)過一些特征曲線從而控制細分曲面的形狀， 甚至需要有一些靈活方便的方法對細分曲面的形狀進行進一步的控制以達 到理想的效果。為了滿足這些實際應用需求，同時，又由于在實踐中三角 形網(wǎng)格是常見的一種網(wǎng)格，所以也為了應用的普遍性，本文選擇研究基于 l o o p 細分方法的曲線插值和l o o p 細分曲面的形狀控制問題。本文提出了 一種基于l o o p 細分方法的曲線插值方法，并給出了幾種通過插值曲線來控 制l o o p 細分曲面的形狀的方法。這些曲線插值和形狀控制的方法不僅易于 實現(xiàn)，而且有效地增強了細分方法表達曲面的能力，更好地滿足了實際生 產(chǎn)應用中對曲面形狀控制的需求。本文共分五章： 第一章，緒論?；仡櫦毞址椒óa(chǎn)生的背景及其發(fā)展歷史，介紹細分方 法的應用，特別是在細分曲面的插值和形狀控制方面的應用，以及本文的 研究內(nèi)容。 第二章，細分方法綜述。綜合闡述了細分方法的特點及分類標準，集 中介紹了幾種經(jīng)典的細分方法，如d o o s a b i n 細分方法、c a t m u l l c l a r k v 福建師范大學劉曉芬碩士學位論文 細分方法、l o o p 細分方法、改進的b u t t e r f ly 細分方法以及3 細分方法 等。 細分規(guī)則通常由兩部分組成。一是拓撲分裂規(guī)則( t o p 0 1 0 9 ic a ls p l i t r u le ) ，描述網(wǎng)格經(jīng)過一次細分后得到的所有頂點之間的連接方式；另一 個是幾何規(guī)則( g e o m e t r i cr u le ) ，決定經(jīng)過一次細分后產(chǎn)生的新點的幾 何位置。根據(jù)細分方法分類標準，d o o s a b i n 細分方法是基于四邊形網(wǎng)格， 采用點分裂操作作為拓撲規(guī)則的細分方法，該細分方法生成的細分曲面是 雙二次均勻b 樣條曲面向任意拓撲結(jié)構網(wǎng)格的推廣，所以它生成的極限曲 面為c 連續(xù)：c a t m u l l c l a r k 細分方法與d o o s a b i n 細分方法一樣是基于 四邊形網(wǎng)格，但它采用l 一4 四邊形分裂法生成新網(wǎng)格的拓撲，利用該細分 方法生成的細分曲面是雙三次均勻b 樣條曲面向任意拓撲結(jié)構網(wǎng)格的推 廣，所以它生成的極限曲面為c2 連續(xù)：與c a t m u l l 一c l a r k 細分方法和 d o o s a b in 細分方法不同，l o o p 細分方法是一種基于三角網(wǎng)格的細分方法， 所生成的細分曲面是盒式樣條( b o xs p l in e ) 曲面的推廣，它采用卜4 三 角形分裂法生成新網(wǎng)格的拓撲，在規(guī)則的三角網(wǎng)格上能生成c2 連續(xù)的極限 曲面，對于非規(guī)則的三角網(wǎng)格，除奇異點處是c 。連續(xù)外，其余點都是c ! 連續(xù)：以上三神經(jīng)典的細分方法都屬于逼近型細分方法。 通過對各種經(jīng)典的細分方法的比較，本文選擇l o o p 細分方法作為研究 的對象，這是因為1 、前人在這方面研究的還不是很多，2 、l o o p 細分方法 是基于三角網(wǎng)格的，而三角網(wǎng)格是最常見一種拓撲結(jié)構。本文研究的主要 內(nèi)容是基于l o o p 細分方法的曲線插值和l o o p 細分曲面的形狀控制問題。 第三章，基于l o o p 細分方法的曲線插值。給出了一種新的利用l o o p 細分方法進行曲線插值的方法。該方法不需要修改細分規(guī)則，只要在被插 值曲線的控制多邊形兩側(cè)構造對稱三角網(wǎng)格帶即可。被插值曲線可以是一 條或多條不相交的曲線，也可以是多條相交的曲線。 曲線插值是指在構造曲面過程中通過一定的方法使最終生成的曲面經(jīng) 過預先指定的曲線。本文提出的基于l o o p 細分方法的曲線插值方法，關鍵 的思想是在被插值曲線的控制多邊形兩側(cè)構造對稱三角網(wǎng)格帶。所謂對稱 三角網(wǎng)格帶是由一系列對稱三角形構成，其中每對相鄰的對稱三角形都可 構成對稱三角網(wǎng)格。對稱三角網(wǎng)格的定義為以被插值曲線的控制多邊形的 v 福建師范大學劉曉芬碩士學位論文 任意兩條相鄰邊為公共邊，向其兩側(cè)構造三角形，每對有公共邊的三角形 的兩個相對點關于公共邊的中點對稱。本文證明了，一個對稱三角網(wǎng)格帶， 經(jīng)過k ( k - - o 。) 次l o o p 細分后得到的極限曲線是一條由對稱三角網(wǎng)格帶的中 心多邊形確定的三次均勻b 樣條曲線。因此，欲插值一條三次均勻b 樣條 曲線，只要對該曲線的控制多邊形構造對稱三角網(wǎng)格帶就能實現(xiàn)。本文給 出了自動構造對稱三角網(wǎng)格帶的算法。進一步，要插值相交曲線，需在插 值點處構造全對稱三角網(wǎng)格。全對稱三角網(wǎng)格是在對稱三角網(wǎng)格基礎上加 強條件，使得每對通過對稱三角網(wǎng)格中心點的線段共線且相等。本文證明 了，經(jīng)過k ( k _ 0 0 ) 次l o o p 細分后，極限曲線將經(jīng)過全對稱三角網(wǎng)格的中心 點，即多條曲線的相交點，從而使最終生成的細分曲面插值多條相交曲線。 第四章，基于插值曲線的l o o p 細分曲面形狀控制。在第三章介紹的曲 線插值方法的基礎上，給出了控制l o o p 細分曲面形狀的不同方法：這些方 法的核心思想是利用插值曲線及其對稱三角網(wǎng)格帶的仿射變換來調(diào)節(jié) l o o p 細分曲面形狀。 本文提出的控制細分曲面形狀的幾種不同方法主要是通過插值曲線的 變化來進行控制。主要基于兩種思想：一、插值曲線的控制多邊形保持不 變，修改對稱三角網(wǎng)格帶的形狀：二、修改插值曲線的控制多邊形。對于 第一種思想，具體實現(xiàn)方法有：1 、曲率控制；2 、旋轉(zhuǎn)控制：3 、法向控制。 對于第二種思想的具體實現(xiàn)方法為：l 、縮放控制；2 、自由變形。 曲率控制：對于對稱三角網(wǎng)格帶，改變其每條中心邊中點到對應的相 對點的長度，當，變大時，細分曲面的曲率變?。划攆 變小時，細分曲面 的曲率變大。 旋轉(zhuǎn)控制：對于對稱三角網(wǎng)格帶，設每對對稱三角形共面的面為m ， 將其對應的兩相對點在面m ，上繞著它們的公共邊的中點旋轉(zhuǎn) 只( 石 只 丌) 。 法向控制：對于對稱三角網(wǎng)格帶，將有公共邊的每對對稱三角形繞其 公共邊旋轉(zhuǎn)( 一萬 l 3 時成= 擊。 ( 2 ) 拓撲結(jié)構的建立 連接每個新頂點與其周圍的新邊點； 連接每個新邊點與其周圍的新邊點。 圖2 7 2 8 顯示了l o o p 細分方法的模板。圖2 9 顯示了對三角形網(wǎng)格 運用l o o p 細分方法一次后網(wǎng)格的聯(lián)接情況。 3 1 8 1 培 圖27e 一頂點模板圖 圖28v 一頂點模板圖 圖2 9l o o p 細分方法的拓撲規(guī)則 福建師范大學劉曉芬碩士學位論文 2 4 4 改進的b u t t e r f iy 細分方法 b u t t e r f l y 細分方法是d y n 、g r e g o r y 和l e v i n “”于1 9 9 0 年提出的一種適 用于三角形網(wǎng)格的細分新方法，由于其模板與蝴蝶相似而得名。這種細分 方法與l o o p 細分方法有相似之處，都是基于面分裂的細分方法，即每個三 角形一分為四。但是與l o o p 細分方法不同的是，它是屬于插值型細分方法， 每次細分時，原來網(wǎng)格的頂點位置不變，只是對每條邊生成一個新的頂點， 即新邊點( e - 頂點) 。最初的b u t t e r f l y 細分方法生成的極限曲面在規(guī)則點 處達到c 1 連續(xù)，但在奇異點處不能達到c 連續(xù)。后來z o r i l l s 1 提出了改進的 b u t t e r f l y 細分方法，它可以在任意的三角形網(wǎng)格上生成c 連續(xù)的曲面。 下面主要介紹改進的b u t t e r f l y 細分方法。對于三類不同情況的網(wǎng)格邊 產(chǎn)生三類新邊點( e - 頂點) ，第一類網(wǎng)格邊是內(nèi)部邊且該邊的兩個端點的 度數(shù)均為6 ，第二類網(wǎng)格邊是內(nèi)部邊且該邊至少有一個端點的度數(shù)不等于6 ， 第三類網(wǎng)格邊是內(nèi)部邊且該邊的兩個端點的度數(shù)均不為6 。 ( 1 ) 幾何規(guī)則 第一類新邊點( e 一頂點) ：對于網(wǎng)格中一內(nèi)部邊v v ，該邊兩個端點的 度數(shù)均為6 ，則產(chǎn)生該邊對應的新邊點( e - 頂點) 的細分模板見圖2 1 0 ， 其中d = 一，b = + 2 w ，c 1 6，d = 0 3 ，0 蔓甜- l ，一般取0 3 = 0 。邊v ，v 上的新邊點v 。的計算公式為 v f = a ( v j + v ) + b ( v 8 + v 4 ) + c ( v l + v 3 + v 5 + v 7 ) + d ( v 2 + v 6 ) 第二類新邊點( e - 頂點) ：對于網(wǎng)格中一內(nèi)部邊，該邊一個端點為規(guī)則 點( 度數(shù)為6 ) ，另一個端點為奇異點( 度數(shù)7 6 ) ，則產(chǎn)生該邊對應 的新邊點( e - 頂點) 的細分模板見圖2 1 1 ，點v 為奇異點。其中各鄰接 點的權值表示如下： 當盯5 時，- = i i i i + c o s 等! + 號c 0 5 專2 ) f = 0 ，n 一1 ； 當玎= 3 時，s o = 吉，s = 是= 一古： 當n = 4 時，s o = ，s t = 邑= 0 ，s 2 = 一 。 新邊點v 。的計算公式為： 第2 章細分方法綜述 v 。= v + s v l i - o 第三類新邊點( e - 頂點) ：對于網(wǎng)格中一內(nèi)部邊，該邊兩個端點的度數(shù) 均不為6 ，為了得到該邊的新邊點，先對該邊的兩端點分別應用第二類 新邊點的模板產(chǎn)生兩個新頂點，則該邊的新邊點就是這兩個新頂點的 平均值。 礴圓島 圖2 1 0e - 頂點模板圖 f i g2 10e v e r t e xm a s k 該邊為兩端點度數(shù)均為6 的內(nèi)部邊 圖2 1 1e - 頂點模板圖 f i g2 11 e - v e r t e xm a s k 該邊為一端點度數(shù)為6 的內(nèi)部邊 ( 2 ) 拓撲結(jié)構的建立 改進的b u t e r f ly 細分方法的拓撲結(jié)構的建立與l o o p - - 羊，即每個三角 形一分為四。 連接每個頂點與其周圍的新邊點： 連接每個新邊點與其周圍的新邊點。 2 4 5 , f i 細分方法 前面介紹的四種細分方法除d o o s a b i n 細分方法外都采用卜4 網(wǎng)格分 裂，因此每次細分都使多邊形面片數(shù)增加4 倍，面片增長速度太快，不利于 多分辨率處理。k o b b e l t 2 9 在2 0 0 0 年提出一種稱為3 細分方法的算法有效 地減緩了面片增長速度。該方法以三角網(wǎng)格為初始控制網(wǎng)格，采用一種新 的頂點插入和分裂方式。經(jīng)過一次細分，三角形面的個數(shù)增加3 倍，兩次細 分后，三角形面的個數(shù)增加9 倍，能達到一階光滑。 ( 1 ) 幾何規(guī)則 福建師范大學劉曉芬碩士學位論文 新面點( f - 頂點) ：設三角形的三個頂點為v 。，v 。，v ：，則該面的新面點 為三個頂點的平均，即 v f = ( v o + v l + v 2 ) 新頂點( v 一頂點) ：設頂點v 的n 個相鄰點為v 。，”l j 一，v 。，則頂點v 的新 頂點為該點本身和其所有相鄰頂點的加權和，即 v r = ( 一a ) v + 魯萎v ， 其中口= ( 4 2 c o s ( 2 叫n ) ) 9 。 ( 2 ) 拓撲結(jié)構的建立 每次細分時，先將每個三角形面的新面點與三角形的三個頂點相連， 然后去掉原三角形的內(nèi)部邊，最后將每個面的新面點與同該面相鄰的所有 面的新面點相連。 圖2 1 2 2 1 3 為3 細分方法的模板。圖2 1 4 顯示了3 細分方法細分 二次的過程。 圖2 1 2f - 頂點模板圖 f i g2 i2f - v e r t e xm a s k 圖2 1 3v - 頂點模板圖 f i g2 13v v e r t e xm a s k 第2 章細分方法綜述 2 5 小結(jié) 笪么么 ( a )( b )( c ) & 氐 ( d )( e ) 圖2 1 4 i 細分方法示意圖。 一 f i g2 1 44 3 s u b d i v i s i o ns k e t c hm a p ( a ) 初始網(wǎng)搭；( b ) 一( c ) 第一次細分；( d ) 一( e ) 第二次細分。 本章首先解釋了細分方法描述中的一些常用術語，接著介紹了細分方 法的主要特點及幾種分類方式，最后描述了幾種經(jīng)典的細分方法，如 d o o s a b i n 細分方法、c a t m u l l c l a r k 細分方法、l o o p 細分方法、改進的 b u t t e r f l y 細分方法、手細分方法等，并對每一種細分方法給出其模板及 拓撲結(jié)構的連接方式示意圖。 福建師范大學劉曉芬碩士學位論文 第3 章基于l o o p 細分方法的曲線插值 3 1 引言 所謂曲線插值是指在構造曲面過程中通過一定的方法使最終生成的曲 面經(jīng)過預先指定的曲線。這在實際應用中有很重要的意義。例如，在產(chǎn)品 外觀設計中，我們需要使最后成形的曲面經(jīng)過特定的些曲線，這些曲線 決定了產(chǎn)品的最后形狀特征。最早研究細分曲面中的曲線插值問題的是 n a s r p 2 。43 。川。他提出了基于d o o s a b i n 細分方法生成帶有曲線插值約束的 細分曲面“2 ”3 和基于c a t m u l l - c l a r k 細分方法生成帶有曲線插值約束的細 分曲面“。這些方法所插值的曲線都是均勻b 樣條曲線，為了能夠插值 n u r b s 曲線，張景嶠n ”等提出了基于非均勻c a t m u l l 一c l a r k 細分方法的曲 線插值方法。以上這些方法基于的初始網(wǎng)格都是四邊形網(wǎng)格，而在實踐中 三角形網(wǎng)格是常見的一種網(wǎng)格，若要應用上述方法需先將三角形網(wǎng)格轉(zhuǎn)換 成四邊形網(wǎng)格，這樣必然會增加計算量。若能直接在三角網(wǎng)格的基礎上實 現(xiàn)曲線插值，則會很大的提高計算效率?；谶@個思想本章給出了基于 l o o p 細分方法生成帶有曲線插值約束的細分曲面的方法。 本章給出的基于l o o p 細分方法的曲線插值方法不需要修改細分規(guī)則， 只需以插值曲線的控制多邊形為中心多邊形，向其兩側(cè)構造對稱三角網(wǎng)格 帶，該對稱三角網(wǎng)格帶將收斂于插值曲線。因此，包含有該三角網(wǎng)格帶的 多面體網(wǎng)格的極限曲面將經(jīng)過插值曲線。運用本章提出的方法可在三角網(wǎng) 格生成的細分曲面上插值多種情況的曲線：( 1 ) 單條閉合曲線或開曲線： ( 2 ) 多條不相交的閉合曲線或開曲線；( 3 ) 多條相交曲線，最多可達到六 條。 3 2l o o p 多邊形網(wǎng)格帶 為了實現(xiàn)生成帶有曲線插值約束的l o o p 細分曲面，本節(jié)首先定義一種 第3 章基于l o o p 細分方法的曲線插值 最終能生成一條滿足條件的插值曲線的三角網(wǎng)格帶。該三角網(wǎng)格帶可根據(jù) 預先給定的條件定義。 ? 考閥上汐仍景坎 定義1設有a 、b 、c 三點，若該三點基線且點b 為線段a c 的中點， 即la b | = j b cl ，則稱點a 、c 關于。直b 過稱。( 參見圖3 1 ) 定義2對于兩相鄰三角形( v 。，v ；，v ：) 和( v 。，v ，v ，) ，若點v ：、v ：， 關于公共邊vo v 的中點e 對稱，則稱avo v 。v 。與v o v v ：。為對稱三角形。公 共邊v o v 稱為中心邊，點v 。、v 。稱為關于中心邊v0 v i 的相對點。( 參見圖 3 2 ) 定義3設有兩組對稱三角形，兩條中心邊相交于公共點v ，則將兩 對相對點中位于兩中心邊同一側(cè)的兩點連接所構成的三角網(wǎng)格稱為對稱三 角網(wǎng)格，公共點v 稱為中心點。 圖3 3 所示三角網(wǎng)格為對稱三角網(wǎng)格，其中c a 。v 與c ，b v 為對稱 三角形，aca o 。v 與c ：b ：v 為對稱三角形，點v 為中心點。 幽3i 對稱圖32 對稱二角形 f i g3 1s y m m e t r y f i g3 2s y m m e t r yt r i a n g l e b 圖33 對稱二角網(wǎng)格 f i g3 3s y m m e t r yt r i a n g l e m e s h 定義4設s 為對稱三角網(wǎng)格，中心點為點v ，點a t 、b - 為關于中心邊 c ，v 的相對點，點a ：、b ：為關于中心邊v c ：的相對點，若點a 、v 、bz 三點 共線且la v i = iv b ：】，點c 、v 、c ：三點共線且lc - v l2 lv cz i ，點0 2 、v 、b t 三 點共線且la ：v l = v b i ，則稱s 為全對稱三角網(wǎng)格。( 參見圖3 4 ) 定義5 由一系列對稱三角形構成的三角網(wǎng)格帶稱為砬箍三魚旦堅 直，其中則! 塑墮銎簽三魚受疊旦生幽整三塹幽，由中心邊構成的 多邊形稱為中心多邊形。 福建師范大學劉曉芬碩士學位論文 圖3 5 所示為一對稱三角網(wǎng)格帶，其中以點c 。、c 、c ：、c 。、c t 、cs 為 頂點的多邊形為中心多邊形。 圖3 4 全對稱三角網(wǎng)格 f i g3 4f u l ls y m m e t r i c t r i a n g l em e s h 3 3 對稱三角網(wǎng)格帶的收斂 圖3 5 對稱三角網(wǎng)格帶 f i g3 5s y m m e t r i ct r i a n g l e s t r i p - s h a p e dm e s h 根據(jù)3 2 小節(jié)的定義，下面分析用l o o p 細分方法對對稱三角網(wǎng)格帶進 行細分的情況。 引理1對于給定的對稱三角網(wǎng)格帶g ，若對g 進行一次l o o p 細分( 不 考慮邊界情況) 所得到三角網(wǎng)格帶g7 仍為對稱三角網(wǎng)格帶。 證明：根據(jù)對稱三角網(wǎng)格帶的定義( 定義5 ) ，顯然要證對一個對稱三 角網(wǎng)格帶進行一次l o o p 細分后仍得到一個對稱三角網(wǎng)格帶，只要證明一個 對稱三角網(wǎng)格經(jīng)過一次l o o p 細分后仍得到一個對稱三角網(wǎng)格。對于任意一 個對稱三角網(wǎng)格( 如圖3 6 所示) ，其中，點v 為中心點，邊c 1 扎c ：v 為中 心邊，點a 、b l 為關于中心邊c i v 的相對點，點口2 、b 2 為關于中心邊c 2 v 的 相對點，點e 。為中心邊c l v 的中點，點e ：為中心邊c ：v 的中點。相應的點c f 、 c 2 、d ：、a ；、b 0 毯、v 為一次l o o p 細分后產(chǎn)生的新點。點e ：為邊c ；v 的 中點，點e ：為邊c ；v 的中點。 顯然要證一個對稱三角網(wǎng)格經(jīng)過一次l o o p 細分后仍得到一個對稱三 角網(wǎng)格，我們只要證明2 e ，- a f + b f 2 e c t ；+ b i 。 第3 章基于l o o p 細分方法的曲線插值 圖3 6 對稱三角網(wǎng)格 f i g3 6s y m m e t r yt r i a n g l em e s h 由定義1 有a i + b i = 2 e 】 a 2 + b 2 = 2 e 2 c 1 + v = 2 e 1 c 2 + v = 2 e2 根據(jù)l o o p 細分公式有 c ，_ ( c 1 + v ) + ( d + 島) a f = ( d l + v ) + ( c l + a 2 ) b i = ( 6 l + v ) + ( c l + b 2 ) v7 = 古( c l 十c 2 + d l + a 2 + b l + b 2 ) + 言v 將式( 3 1 ) 一( 3 - 4 ) 代入上述諸式得 c f _ ；- 2 p l + 2 e 1 = e 1 v = f f ( 2 e i + 2 e 2 + c l + c 2 ) + ；v = ( p l + e 2 ) + v d f + 6 ：= ( 2 v + 2 e i ) + ( 2 c i + 2 e 2 ) = 號p l + 8 2 + v 2 e f = c ：+ v = p i + p 2 + v 即證得2 e ：= a f + “，同理可證2 e ；= 日：+ 噬。 證畢。 ( 3 1 ) ( 3 - 2 ) ( 3 3 ) ( 3 - 4 ) ( 3 - 5 ) ( 3 - 6 ) 引理2給定一個對稱三角網(wǎng)格帶g ，把g 的中心多邊形看作一條三 次均勻b 樣條曲線的控制多邊形，把每個節(jié)點區(qū)間的中點作為新節(jié)點插入， 得到一條新的控制多邊形，它與g 經(jīng)過一次l o o p 細分后，所得的對稱三角 網(wǎng)格帶g7 的中心多邊形相同。 證明：e h 式( 3 - 5 ) ( 3 - 6 ) 有 福建師范大學劉曉芬碩士學位論文 = 鏟華 z c 2 = 半 ( 3 - 7 ) ( 3 - 8 ) v = 撕+ 8 ：) + v = ( 畢+ 竿) + v = ( c i 4 - c 2 ) + v ( 3 9 ) 式( 3 - 7 ) 一( 3 - 9 ) 即為將每個節(jié)點區(qū)間的中點作為新節(jié)點插入所得的 新的控制頂點“。 證畢。 根據(jù)引理卜2 可推出下面定理。 定理1設g 為一對稱三角網(wǎng)格帶，經(jīng)過( 女一( 3 0 ) 次l o o p 細分后得到 的極限曲線是一條由g 的中心多邊形確定的三次均勻b 樣條曲線。 證明：( 1 ) 根據(jù)l o o p 細分理論“，經(jīng)過k 次l o o p 細分，當k 哼0 0 時， 對稱三角網(wǎng)格帶將收斂于其中心多邊形；( 2 ) 根據(jù)b 樣條曲線理論”1 ，反 復插入各節(jié)點區(qū)間中點將使得控制多邊形收斂于相應的b 樣條曲線。于是 由( 1 ) 、( 2 ) 及引理2 知本定理成立。 證畢。 定理2 設g 為一對稱三角網(wǎng)格帶，c i c ：c 。是g 的中心多邊形，當點 c h 、c i 、c j + i ( 2 f n 一1 ) 三點共線且ic ) - i c ，i = 1c i c i 時，g 經(jīng)過( 斗) 次l o o p 細分后得到的極限曲線將插值于點c i 。 證明：當點c h 、c ，、c 三點共線且lc i _ l c 。i = 1c i c l 時，經(jīng)過一次l o o p 細分后，由式( 3 - 6 ) 可得c q 。又r - h 式( 3 - 5 ) 得c ：1 = 華：c 2 ，= ! l 等量； 所以點c ：。、c _ 三點共線且lc - c ；i = 1c ：c ：+ i ，由此知經(jīng)任意次l o o p 細分 后點c 總在中心多邊形上。于是由定理1 的證明知，g 經(jīng)過( 七一) 次l o o p 細分后得到的極限曲線將插值于點c ，。 證畢。 推論1設g ，f - 1 , 2 ，m 是共享同一個全對稱三角網(wǎng)格f 的m ( m 6 ) 個對稱三角網(wǎng)格帶，為g 的中心多邊形的終邊，f 的中心點為g 。的中心 多邊形的倒數(shù)第二個頂點，則經(jīng)過k ( k 斗) 次l o o p 細分后，m 個對稱三角 2 6 第3 章基于l o o p 細分方法的曲線插值 網(wǎng)格帶收斂于m 條相交于全對稱三角網(wǎng)格f 的中心點的三次均勻b 樣條曲 線只，i = 1 , 2 ，m 。若l ，與l ，共線，則g 與g ，對應的曲線只與0 在f 的中心 點處c 1 連續(xù)，反之，則c o 連續(xù)。 3 4 插值多條不相交曲線 根據(jù)定理l ，可以對給定的三角網(wǎng)格構造l o o p 細分曲面，使得該曲面 通過指定的一條或多條不相交的曲線。問題描述如下： 給定一個三角網(wǎng)格h ，在上指定m 個控制多邊形印，f _ l ，2 ，m ，由 印，確定的m 條三次均勻b 樣條曲線只不相交，要求構造插值m 條由c p ， f - 1 , 2 ，確定的三次均勻b 樣條曲線p 的l o o p 細分曲面。 為了能夠使得的l o o p 細分曲面插值m 條不相交的由叩，確定的三次 均勻b 樣條曲線p ，根據(jù)定理1 只要在上以印。為中心多邊形構造嵌入對 稱三角網(wǎng)格帶，對得到的三角網(wǎng)格運用l o o p 細分規(guī)則，生成的極限曲 面就能實現(xiàn)插值m 條不相交的曲線。 由于m 個對稱三角網(wǎng)格帶的構造方法類似，本文以一個對稱三角網(wǎng)格 帶的構造為例。對于某個控制多邊形印，設它的n 個控制頂點為c ， i = 1 , 2 ，n ，n l 條邊為l 。、l ? 、l 。，l j = c ，c ，j = l ，2 ，n l ，則構造 以印為中心多邊形的對稱三角網(wǎng)格帶的具體方法是：( 1 ) 在印，的每條邊 l 。，j 2 l ，2 ，n 一1 的兩側(cè)構造對稱三角形c j 。川口，】和c 0 + r 點a a ，2 為 關于中心邊l 。的相對點；( 2 ) 分別將位于c p ，同側(cè)的相對點連接起來。在構 造中應遵循的原則是：1 、基于數(shù)據(jù)量方面的考慮，選取點口、口，：時應盡 量選取在給定三角網(wǎng)格上的點，在一定范圍內(nèi)可適當調(diào)整原三角網(wǎng)格上的 點的位置，使得最終新生成的三角形盡量少：2 、若印，上的頂點的度大于 6 ，則刪除多余的邊，多余邊的另一個端點根據(jù)就近原則與相近的點連接； 3 、若印，上的頂點的度小于6 ，則添加邊，即對印，上以該頂點為端點的兩 條邊l ，、l 。重新選取各自的相對點使得該頂點的度為6 。 對稱三角網(wǎng)格帶可手動構造實現(xiàn)，也可自動構造實現(xiàn)。手動構造即手 動選取控制多邊形印上每條邊的相對點。而自動構造的實現(xiàn)方法見本文 3 5 節(jié)。 福建師范大學劉曉芬碩士學位論文 圖3 7 顯示了進行曲線插值的例子，其初始網(wǎng)格為位于立方體表面的 三角網(wǎng)格，最終的極限曲面通過以立方體四個面的中線為控制多邊形確定 的曲線。其中，上行從左到右為：初始網(wǎng)格、加入插值控制多邊形( 加粗) 的初始網(wǎng)格和嵌入對稱三角網(wǎng)格帶的修改后的網(wǎng)格：下行從左到右為：無 插值曲線的極限曲面、對嵌入對稱三角網(wǎng)格帶的修改后的網(wǎng)格進行一次 l o o p 細分和三次l o o p 細分后的效果( 黑粗線為插值曲線) 。圖3 8 給出了 一個對稱三角網(wǎng)格帶的例子。其中，黑實線為一個一般的對稱三角網(wǎng)格帶， 白實線為它的中心多邊形、虛線為第一次細分的效果和黑粗線為極限曲線。 圖3 9 顯示了一個插值兩條不相交曲線的例子。其中，左邊從上到下為： 初始網(wǎng)格和嵌入對稱三角網(wǎng)格帶的修改后的網(wǎng)格：右邊從上到下為：無插 值曲線的極限曲面和對嵌入對稱三角網(wǎng)格帶的修改后的網(wǎng)格進行三次 l o o p 細分后的效果( 黑粗線為插值曲線) 。 賂路 圖3 7 立方體曲面插值曲線 第3 章基于l o o p 細分方法的曲線插值 圖3 8 對稱三角網(wǎng)格帶 圖3 9 插值兩條不相交的曲線 3 5 自動構造對稱三角網(wǎng)格帶 設插值曲線的控制多邊形為c i c ：巳，在原始網(wǎng)格中以邊 c i c f + i ，i = l ，2 仃一1 為公共邊的兩三角形為q t + l6 i 和kc , c 6 f 2 ，邊q 氣l 的中 點為e 。，則實現(xiàn)自動構造以控制多邊形c j c ：0 為中心多邊形的對稱三角網(wǎng) 格帶的關鍵是確定關于中心邊c , c 。的相對點口。和口f 2 0 為了使對稱三角網(wǎng)格 福建師范大學劉曉芬碩士學位論文 帶實現(xiàn)自動構造，首先給定一個網(wǎng)格上的點可調(diào)整的移動范圍s ，當點包移 至點b , 位置或點b j ：移至點6 ；2 位置時，應滿足i 陽- b , 0 占或0 6 f 2 一b , 2 i i f 。在本 節(jié)提出的自動構造對稱三角網(wǎng)格帶的算法中主要分三種情況考慮。 情況一：移動點6 f ?；驆u：。當點島。在移動范圍占內(nèi)移動時，能夠使得點 成為關于中心邊c ，c 。的相對點，即口。= 且a 。：= b 則移動點b ”或者， 當點島：在移動范圍s 內(nèi)移動時，能夠使得點成為關于中心邊c l c o 的相對 點，即口。= b i 且q 2 = ，則移動點6 f ：。否則，考慮情況二。 情況二：添加點a ，l 或a 1 2 0 當情況一不可行時，若點日f l 向c i c 。6 i 方向 上的投影點落在公共邊為邊c 6 f 。、c j + l6 l 。的三角形面內(nèi)，取口，：= b 2 ，添加點口“ 或者，若點q ：向c i c i + 。6 f ：方向上的投影點落在公共邊為邊c ，6 f ：、c j + 。島：的三 角形面內(nèi)，取口。= b i 。，添加點口，否則，考慮情況三。 情況三：同時添加點a 口i 2 0 當情況二不可行時，為了使得原網(wǎng)格總 體形狀不作太大變化，則只有同時添加兩點a ?？?， 在本算法中，除了考慮關于中心邊e c 。的相對點a 。和q ：的確定以外， 還應考慮的是中心多邊形上的點的度數(shù)問題，應始終保持這些點的度數(shù)為 6 ，為此就須適當?shù)卦?、減邊數(shù)。具體算法如下： p o r1 = lt 0n l 求點6 f 關于中心邊q c j + 。的中點e ，的對稱點及點包：關于中心邊e t + 的中 點e ，的對稱點6 f l 。 i f 點、包2 的距離i b ；2 b , 2 i s t h e n 將點6 j 2 移至點的位置，即6 ：= ，使得口。= b a ，：= 包2 。 e l s ei f 點、b i l 的距離f b , b , i i 6 t h e n 刪除多余的邊，將點口川，i 與點口川相連接，點。_ 1 2 與點口膳相連 接，刪除的邊上除點c ，外的另一個端點按就近原則與鄰近它的 點相連接構成三角形面。 e n d ： e n d 福建師范大學劉曉芬碩士學位論文 3 6 插值多條相交曲線 根據(jù)本文3 3 小節(jié)的結(jié)論，還可生成插值多條相交曲線的l o o p 細分曲 面。 設給定一個三角網(wǎng)格日，在日上指定i n 個控制多邊形e p ，i = 1 , 2 ，m ， 由c p 。確定的三次均勻b 樣條曲線為只。為了使l o o p 細分曲面插值多條相 交曲線，不妨設m ( 1 m 6 ) 個插值曲線的控制多邊形印相交于點v ，且 這些控制多邊形c p 。滿足下面的條件。 條件1 ：交點v 為每個控制多邊形的倒數(shù)第二個頂點，且在點v 處可 構造共享全對稱三角網(wǎng)格。 根據(jù)定理l 和定理2 ，可構造插值m 條交于點v 的曲線只只，只的 l o o p 細分曲面。 實現(xiàn)方法包括三個步驟：( 1 ) 構造1 1 1 個對稱三角網(wǎng)格帶；( 2 ) 在中心 多邊形的交點處構造共享的全對稱三角網(wǎng)格；( 3 ) 應用l o o p 細分方法對修 改后的三角網(wǎng)格進行細分。 ( 1 ) 構造m 個對稱三角網(wǎng)格帶 構造方法可參見本文3 4 節(jié)、3 5 節(jié)。 ( 2 ) 構造共享全對稱三角網(wǎng)格 為簡便起見，首先考慮m = 2 的情況，即兩條益線相交的情況。根據(jù)條 件l ，可分兩種情況討論。情況一，兩個控制多邊形的相交于點v 的終邊 共線：情況二，兩個控制多邊形的相交于點v 的終邊不共線。對于情況一 可直接用步驟( 1 ) 中構造對稱三角網(wǎng)格的方法實現(xiàn)?，F(xiàn)在討論情況二。 設兩個控制多邊形c p ，、c p ，相交于點v ，如圖3 1 0 所示，邊c v 為c p 的終邊，邊d v 為c p 。的終邊，邊c v 、d v 不共線。構造共享全對稱三角網(wǎng) 格步驟如下： 步驟 步驟 步驟 步驟 聯(lián)接點a 和d 、點b 和c 。 過點v 作邊a d 、b c 的平行線e f ，使得| e vj = lv f l = la d | = lb c l 聯(lián)接點d 和f ，點e 和b ，點f 和c 以及點e 和a 。 將構造的共享全對稱三角網(wǎng)格嵌入原網(wǎng)格中。 第3 章基于l o o p 細分方法的曲線插值 圖3 1 0 共享全對稱三角網(wǎng)格 f i g3 10s h a r i n gr u t is y m m e t r y t r i a n 2 l em e s h 在進行步驟4 操作時，應遵循的原則是：1 、若點v 的度大于6 ，則刪 除多余的邊。多余邊的另一個端點根據(jù)就近原則與相近的點連接：2 、對于