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

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