（計(jì)算機(jī)軟件與理論專業(yè)論文）空間三維物體的三角網(wǎng)劃分.pdf

摘要 摘要 由于空間三角網(wǎng)劃分技術(shù)的發(fā)展，加速了產(chǎn)品數(shù)字化的進(jìn)程，它可以方便，準(zhǔn)確， 快速，高效的進(jìn)行物體模型建模，所以廣泛的應(yīng)用于c a d ，c a m ，逆向工程，地球信息 系統(tǒng)，3 d 動(dòng)畫(huà)，虛擬現(xiàn)實(shí)( r v ) ，增強(qiáng)現(xiàn)實(shí)( a v ) 等諸多領(lǐng)域，對(duì)工業(yè)生產(chǎn)，社會(huì)娛樂(lè)， 經(jīng)濟(jì)發(fā)展，軍事現(xiàn)代化，醫(yī)學(xué)可視化等領(lǐng)域，起到了中流砥柱的作用，并取得了顯著的 成果。又由于空間三角網(wǎng)劃分技術(shù)存在著若干問(wèn)題，所以需要對(duì)空間三角網(wǎng)劃分技術(shù)進(jìn) 行改進(jìn)，具體通過(guò)以下五章來(lái)介紹。 第一章是緒論，主要介紹了課題的相關(guān)背景。我們對(duì)三角網(wǎng)劃分的方法進(jìn)行了合理 的分類；既介紹了早期三角網(wǎng)劃分的一些特征，又對(duì)最近十幾年來(lái)的l o d 三角網(wǎng)劃分 與散亂點(diǎn)的三角網(wǎng)劃分發(fā)展情況進(jìn)行了詳盡的介紹。并在最新研究成果的基礎(chǔ)上，提出 了本文的技術(shù)思路。 第二章詳細(xì)介紹了l o d 三角網(wǎng)劃分技術(shù)。我們針對(duì)網(wǎng)絡(luò)傳輸?shù)膶?shí)時(shí)性，交互性等 特點(diǎn)，進(jìn)行了l o d 三角網(wǎng)簡(jiǎn)化的研究，并基于真實(shí)感顯示的要求，根據(jù)重要度與視覺(jué) 辨析度之間的轉(zhuǎn)換，重點(diǎn)研究了動(dòng)態(tài)l o d 三角網(wǎng)劃分技術(shù)。 第三章在三維空間散亂點(diǎn)的基礎(chǔ)上，通過(guò)改進(jìn)三角網(wǎng)劃分技術(shù)，實(shí)現(xiàn)了空間曲面三 角網(wǎng)劃分算法，并對(duì)邊界環(huán)的分裂，融合，閉合進(jìn)行了重點(diǎn)研究。同時(shí)，對(duì)于高密度的 非空洞模型散亂點(diǎn)，詳細(xì)介紹了截面線三角網(wǎng)劃分技術(shù)，并通過(guò)實(shí)驗(yàn)證實(shí)了算法的有效 性，準(zhǔn)確性。 第四章對(duì)已劃分的三角網(wǎng)，由于其可能影響整體的均勻性與視覺(jué)效果，我們介紹了 三角網(wǎng)優(yōu)化技術(shù)，并對(duì)模型逼近細(xì)分優(yōu)化技術(shù)與綜合優(yōu)化技術(shù)進(jìn)行了重點(diǎn)研究。 第五章是對(duì)論文的整體內(nèi)容的總結(jié)，并提出了本文三角網(wǎng)劃分技術(shù)仍然存在的問(wèn) 題。同時(shí)也對(duì)今后需要進(jìn)一步努力和完善的工作進(jìn)行了介紹。 關(guān)鍵詞：三角網(wǎng)劃分空間散亂點(diǎn)l o d 技術(shù)三角網(wǎng)優(yōu)化曲面三角網(wǎng) a b s 仃a c t a b s t r a c t a st h et e c h n o l o g yd e v e l o p m e n to ft h es p a c et r i a n g u l a t i o nm e s h e sw h i c ha c c e l e r a t et h e p r o c e d u r e o ft h ed i g i t a lp r o d u c e s i tc a nw i d l ya p p l i c a t e di nv a r i o u so ff i e l d s ，s u c ha s c a d ，c a m ，r e v e r s e e n g i n e e r i n g ，g e o g r a p h y i n f o r m a t i o n s y s t e m ，t h r e e d i m e n s i o n a l a n i m a t i o n ，v i r s u a lr e a l i t y , a u g m e n t e dr e a l i t ya n ds oo n ，t h a tb e c a u s ei tc a r lb u i l du pt h e o b j e c t m o d u l e 、) ，i t l ls o m ec h a r a c t e r i s t i c s ，s u c ha st h ec o n v e n i e n t ，a c c u r a t e ，s w i f ta n d e f f i c i e n t t h e r e f o r e ，i tp l a yav i t a li m p o r t m e n tr o l ei ns u c hf i e l d sa si n d u s t r yp r o d u c e s ，s o c i a l e n t e r t a i n m e n t ，e c o n o m i cd e v e l o p m e n t ，m o d e mm i l i t a r ya n dv i s u a lm e d c i n e ，a n dg e tam a n i f e s t a c h i v e m e n t b e c a u s et h e r ea r es t i l le x i s ts e v e r a lp r o b l e m si nt h e s p l i t e dt r i a n g u n a t i o n m e s h ，w h i c hn e e ds o m ei m p r o v e m e n t ，a n di nt h en e x tf i v ec h p t e r st h ed e t a i lp r o c u d u r ew i l lb e i n t r o d u c e d i nc h a p t e r1 ，w em a i n l yi n t r o d u c e dt h eb a c k g r o u n do fo u rw o r k w ec l a s s i f i e dt h es p l i t t r i a n g u n a t i o nm e s h e sm e t h o d sr e a s o n a b l y ；e a r l i e rm o d e l so ft h et r i n a g u n a t i o nm e s ha n dt h e l a t e s td e v e l o p m e n t si nt h i sf i e l dw e r ed i s c u s s e dd e t a i l e d w eb r i n go u to u rt r a i no ft h o u g h t b a s e do nt h ea c c o m p l i s h m e n t so ft h e s ei s s u e so nr e c e n ty e a r s i n c h a p t e r 2i n t r o d u c e dt h ed e t a i lm e t h o da b o u tt h el o ds p l i tt r i a n g u n a t i o n m e s h e s ( s t m ) w er e s e a r c h e dt h el o dt r i a n g u n a t i o nm e s h e ss i m p l i f ym e t h o dw h i c hb a s e e d o nt h et i m e l ya n di n t e r a c t i v e l yf e a t u r e b a s eo nt h et h i r dd i m e n s i o nr e q u i r e m e n t ，w ep u to n w e i g h tt or e s e a r c ht h ed y n a m i cl o dt r i n a g u n a t i o nm e s h ，a c c o r d i n gt ot h ed i v e r s i o nb e t w e e n t h ei m p o r td e g r e ea n dt h ev i s u a la n a l y s i sd e g r e e i nc h a p t e r3 ，b a s eo nt h e3 ds c a t t e rs p a c ep o i n t ，w eg e tt h es p a c ec u r v ef a c ed i v i s i o n m e t h o dt h r o u g ht h ei m p r o v e m e n to ft h es t m ，a n dr e s e a r c h e dt h eb o u n d a r yc i r c l ei nf o r mo f t h es p l i t e d ，f u s ea n dc l o s e d t h ei n t e r f a c e - l i n em e t h o di n t r o d u c e du n d e rt h en o n - h o l em o d u l e d a t a , a n dv e r i f i e dt h ea l g o r i t h mi sa v a i l a b i l i t ya n dv e r a c i t y i nc h a p t e r4a st h ee v e n l yr e s u l ta n dt h ev i s u a le f f i c i e n t l yo ft h ei n t e g r i t yo b j e c t ，w e i n t r o d u c e dt h eo p t i m a t i o nm e t h o dt ot h es t mw h e ni tw a sb u i l e du p ，a n dp u to nw e i g h t r e s e a r c h e do nt h et h c h n o l o g yo ft h ew h o l eo p t i m a t i o na n dt h em o d u l es u b d i v i s i o no p t i m a t i o n i nc h a p t e r5i st h ec o n c l u s i o n so ft h ew h o l et h e s i s ，w eg i v e no u tt h es t i l le x i s tp r o b l e mi n s t m ，a n di n t r o d u c e dt h ew o r kn e e dt oi m p r o v ea n dh a r ds t u d yi nt h ef u t u r e k e yw o r d s ：s p l i t e dt r i a n g u l a t i o nm e s h e s ，s c a t t e rs p a c ep o i n t s ，l o dt e c h n o l o g y ， t r i a n g u l a t i o no p t i m i z a t i o n ，c u r v et r i a n g u l a t i o nm e s h i i 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取 得的研究成果盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文 中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含本人為獲得江南 大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料與我一同工作的同志 對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意 簽名： 期：j 趟4 卅 關(guān)于論文使用授權(quán)的說(shuō)明 本學(xué)位論文作者完全了解江南大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定： 江南大學(xué)有權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和磁盤(pán)，允 許論文被查閱和借閱，可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù) 進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文， 并且本人電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致 保密的學(xué)位論文在解密后也遵守此規(guī)定。 簽名： 一 導(dǎo)師簽名： e l 期： 第一章前言 第一章前言 1 1空間三角網(wǎng)劃分的背景 空間三角網(wǎng)的劃分，在c a d ，c a m ，逆向工程，地球信息系統(tǒng)，3 d 動(dòng)畫(huà)，虛擬現(xiàn)實(shí) ( r v ) ，增強(qiáng)現(xiàn)實(shí)( a v ) 等諸多領(lǐng)域，取得了顯著的成果。對(duì)工業(yè)生產(chǎn)，社會(huì)娛樂(lè)，經(jīng)濟(jì)發(fā) 展，軍事現(xiàn)代化，醫(yī)學(xué)可視化等領(lǐng)域，起到了中流砥柱的作用。 三角網(wǎng)因其構(gòu)造靈活、邊界適應(yīng)性好的特點(diǎn)，因此一直受到重視?？臻g三角網(wǎng)曲面 最初是由d ec a s e t li u a 于5 0 年代末提出的，但其成果直至1 9 7 5 年才被b o e m h 發(fā)現(xiàn)，此 后，國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了大量的研究。空間三角網(wǎng)曲面重構(gòu)的一般過(guò)程是，對(duì)給定的 散亂數(shù)據(jù)點(diǎn)進(jìn)行三角剖分，并作必要的修正，計(jì)算三角網(wǎng)格邊界條件，構(gòu)造初始三角網(wǎng) 曲面，來(lái)構(gòu)造整體。連續(xù)的散亂數(shù)據(jù)插值三角網(wǎng)曲面，是1 9 9 4 年，由x i nc h e n & f r a n c i s s c h m i t t 1 】在研究圖像數(shù)據(jù)的曲面重建時(shí)提出的，利用型值點(diǎn)估算出曲面的局部幾何性 質(zhì)，得到曲面的特征線，以這些特征為基礎(chǔ)建立初始的三角網(wǎng)格，在三角網(wǎng)劃分中，未 用到的點(diǎn)都當(dāng)作冗余數(shù)據(jù)，在必要的時(shí)候，可以作為參考點(diǎn)，來(lái)修正已經(jīng)劃分的三角網(wǎng)。 基于三角b e z i e r 曲面的構(gòu)造方法，得到一張光滑的三角網(wǎng)曲面，是1 9 9 5 年由h y u n g i u n p a k & k w a n q s o o k i n g t 2 1 提出的，一種自適應(yīng)的光滑曲面逼近大規(guī)模散亂點(diǎn)的方法，他們 用分段三次b e z i e r 三角代數(shù)曲面作為最終輸出結(jié)果，而使各三角曲面片之間達(dá)到跨邊界 c 1 連續(xù)。該方法從插值于產(chǎn)品的邊界曲線開(kāi)始，不斷插入最大誤差點(diǎn)來(lái)精化逼近曲面， 直到所有測(cè)點(diǎn)都在規(guī)定的誤差內(nèi)，若逼近的允許誤差為0 ，則曲面插值于所有數(shù)據(jù)點(diǎn)。 但是，這一方法采用非參數(shù)的形式，逼近結(jié)果受到坐標(biāo)系的影響，并且只能適應(yīng)單值曲 面。hh o p p e t 3 】通過(guò)研究大量散亂數(shù)據(jù)的曲面重構(gòu)問(wèn)題，他提出的方法概括起來(lái)分三個(gè) 步驟：首先，初始曲面估計(jì)：利用函數(shù)方法構(gòu)造一張插值于測(cè)量點(diǎn)的曲面1 4 - 5 1 ，估算測(cè)量點(diǎn) 到曲面的距離，采用輪廓線抽取算法來(lái)提取曲面。其次，網(wǎng)格優(yōu)化，該步驟主要目的在 于減少三角形數(shù)目，提高曲面的逼近精度。再次，分段光滑曲面片，通過(guò)一種分段細(xì)分 的方法來(lái)將曲面的尖角特征構(gòu)造出來(lái)，提高曲面的逼近精度。 19 9 6 年，bs a r k a r & c h m e n q 又提出另外一種稱為o r t h o g o n a lc r o s ss e c t i o n ( o c s ) p 】 的方法，首先對(duì)每塊測(cè)量數(shù)據(jù)進(jìn)行三角剖分，得到幾張插值于測(cè)量點(diǎn)的基于三角平面的 曲面模型，然后用三組正交的等間隔平行平面與上曲面求交，在各個(gè)截面線內(nèi)去除各曲 面內(nèi)的重疊部分，求出各交線的交點(diǎn)即得所謂o c s 模型，然后利用根據(jù)曲面網(wǎng)格建立 曲面的方法構(gòu)造曲面。e c k ，h o p p e o o , 1 1 】等人利用多分辨率分析的網(wǎng)格簡(jiǎn)化方法將整個(gè)網(wǎng) 格劃分成多個(gè)四邊形區(qū)域，然后利用調(diào)和映射對(duì)每一塊數(shù)據(jù)進(jìn)行參數(shù)化，并用b 樣條擬 合，最后實(shí)現(xiàn)區(qū)域間的c 1 連續(xù)拼接。在網(wǎng)格簡(jiǎn)化中，以往的網(wǎng)格元素的刪除方式( 頂點(diǎn) 刪除、邊刪除、三角形刪除等) ，引入計(jì)算幾何中的v o r o n o i 圖和d e l u n a y a 三角化的思想 實(shí)現(xiàn)網(wǎng)格簡(jiǎn)化，該方法簡(jiǎn)化率高，簡(jiǎn)化質(zhì)量好，簡(jiǎn)化后的三角形形狀均勻。這一曲面重 建的過(guò)程有兩個(gè)特點(diǎn)：利用網(wǎng)格簡(jiǎn)化的思想實(shí)現(xiàn)數(shù)據(jù)分區(qū)，實(shí)現(xiàn)分區(qū)自動(dòng)化；網(wǎng)格簡(jiǎn) 化方法新穎，接近按照實(shí)物特征劃分，向人性化靠近了一步。 江南大學(xué)碩士學(xué)位論文 但是上面的方法都不能滿足虛擬現(xiàn)實(shí)系統(tǒng)的漫游，實(shí)時(shí)交互場(chǎng)景顯示，g i s 地理信 息系統(tǒng)查詢等領(lǐng)域所要求的網(wǎng)絡(luò)實(shí)時(shí)性，可變性等特點(diǎn)，使得在空間三角網(wǎng)劃分當(dāng)中， 基于l o d 三角網(wǎng)層次模型的劃分與簡(jiǎn)化技術(shù)的研究，有著廣闊的情景與應(yīng)用領(lǐng)域。同 時(shí)，由于利用磁場(chǎng)，超聲波，激光測(cè)距，光波干涉等技術(shù)的空間三維物體模型體數(shù)據(jù)采 集設(shè)備的商品化，出現(xiàn)了大量接觸式與非接觸式的掃描設(shè)備，利用這些設(shè)備，可以很容 易獲得空間物體的三維數(shù)據(jù)?；谶@些廉價(jià)的，便捷的數(shù)據(jù)，可以用于重建物體模型與 反向工程( r e ) 等數(shù)字產(chǎn)品領(lǐng)域，使得基于空間海量散亂點(diǎn)的三角網(wǎng)劃分，有著極大的 商業(yè)價(jià)值。因此，我們介紹了基于l o d 三角網(wǎng)劃分與簡(jiǎn)化技術(shù)，以及重點(diǎn)研究了基于 空間散亂點(diǎn)的三角網(wǎng)劃分技術(shù)。 1 2空間三角網(wǎng)劃分技術(shù) 隨著可視技術(shù)的發(fā)展，三角網(wǎng)劃分從二維領(lǐng)域進(jìn)入到三維領(lǐng)域，這是空間三角網(wǎng)劃 分技術(shù)的一大進(jìn)步。而對(duì)于三維掃描設(shè)備測(cè)得的海量數(shù)據(jù)，在繪制過(guò)程中的時(shí)間與存儲(chǔ) 量，同獲取的數(shù)據(jù)量和三角形數(shù)目呈現(xiàn)正比，這嚴(yán)重的影響了網(wǎng)絡(luò)的實(shí)時(shí)性與交互性。 因此需要研究了基于l o d 的三角網(wǎng)劃分技術(shù)，通過(guò)其基于配準(zhǔn)點(diǎn)的具體情況，進(jìn)行適當(dāng) 的三角網(wǎng)簡(jiǎn)化，使其達(dá)到了網(wǎng)絡(luò)傳輸性與交互性的要求。同時(shí)，對(duì)于散亂點(diǎn)的三角網(wǎng)劃 分，其判斷邊界點(diǎn)與非邊界點(diǎn)的繁瑣與復(fù)雜性，需要通過(guò)對(duì)散亂的數(shù)據(jù)點(diǎn)進(jìn)行預(yù)處理， 并對(duì)構(gòu)網(wǎng)方法進(jìn)行改進(jìn)，以提高構(gòu)網(wǎng)的效率，可靠性，準(zhǔn)確性。 1 2 1 基于l o d 三角網(wǎng)劃分技術(shù) 在真實(shí)感模型的應(yīng)用當(dāng)中，對(duì)于虛擬現(xiàn)實(shí)系統(tǒng)中虛擬環(huán)境和虛擬物體的顯示，只需 要用三角網(wǎng)格模型來(lái)描述虛擬對(duì)象的外表就可以滿足要求。但由于三角網(wǎng)的繪制時(shí)間和 存儲(chǔ)量過(guò)大的原因，過(guò)于龐大精細(xì)的網(wǎng)格模型，在上述領(lǐng)域是不實(shí)用的，尤其是在虛擬 現(xiàn)實(shí)系統(tǒng)中，對(duì)時(shí)間性要求很高，這嚴(yán)重的影響了限時(shí)計(jì)算與限時(shí)圖形繪制的應(yīng)用。 在虛擬漫游類型的環(huán)境應(yīng)用中，計(jì)算必須在指定時(shí)間內(nèi)完成圖形計(jì)算與繪制，否則 頭盔中顯示的圖像將與實(shí)際環(huán)境不符。為了解決這一問(wèn)題，網(wǎng)格簡(jiǎn)化與多細(xì)節(jié)層次模型 ( l e v e lo fd e t a i l ，簡(jiǎn)稱l o d ) 方法相繼產(chǎn)生。人們首先直接利用簡(jiǎn)化后的近似網(wǎng)格代替 原始網(wǎng)格進(jìn)行顯示，而后又引入l o d 模型，先定義一組不同細(xì)節(jié)層次的網(wǎng)格模型，再根 據(jù)不同場(chǎng)景和視點(diǎn)分別進(jìn)行繪制，當(dāng)物體離觀察點(diǎn)較近時(shí)，采用較精細(xì)的網(wǎng)格模型進(jìn)行 繪制，而對(duì)于遠(yuǎn)處的物體，則通過(guò)簡(jiǎn)化，采用較粗糙的模型進(jìn)行繪制。 基于上面思想，在網(wǎng)格簡(jiǎn)化方面，國(guó)內(nèi)外都相繼開(kāi)展了一些卓有成效的網(wǎng)格簡(jiǎn)化研 究工作。但總的來(lái)說(shuō)，目前并沒(méi)有十分理想的，通用的網(wǎng)格簡(jiǎn)化方法。現(xiàn)實(shí)當(dāng)中，對(duì)于 任意拓?fù)湫螤畹木W(wǎng)格，既要保持網(wǎng)格空間形狀在一定誤差范圍內(nèi)，又要保證網(wǎng)格數(shù)目少 的要求是非常困難的。s c h r o e d e r t l 2 1 等人通過(guò)頂點(diǎn)刪除簡(jiǎn)化網(wǎng)格。他們通過(guò)在局部區(qū)域 中評(píng)估頂點(diǎn)到相關(guān)平均平面的距離來(lái)判斷該頂點(diǎn)是否應(yīng)該刪除。如果刪除，則重新進(jìn)行 周圍頂點(diǎn)的三角劃分過(guò)程。這個(gè)算法能夠大量刪減三角面片，但由于在迭代過(guò)程中誤差 不斷積累，不能確保與原始網(wǎng)格很好地匹配。t u r k 提出了一種基于粒子互斥模型的多層 次網(wǎng)格簡(jiǎn)化方法。算法將新的數(shù)據(jù)點(diǎn)分布到原始三角網(wǎng)格表面，利用互斥原理使它們保 2 第一章前言 持平衡并合理地分布，然后刪除原有頂點(diǎn)，對(duì)新頂點(diǎn)所組成的圖形重新三角網(wǎng)劃分。由 于算法采用了簡(jiǎn)單的模型，對(duì)于一些復(fù)雜網(wǎng)格的簡(jiǎn)化結(jié)果不是很理想。算法中根據(jù)排斥 力重新分布新頂點(diǎn)，這涉及平面旋轉(zhuǎn)和投影，計(jì)算量和誤差都會(huì)比較大。由此， h h o p p e l1 1 3 , 4 等人提出了一種整體的網(wǎng)格優(yōu)化過(guò)程，既包括網(wǎng)格匹配，又包括了網(wǎng)格簡(jiǎn) 化，算法需要兩組輸入數(shù)據(jù)，建立比較復(fù)雜的全局能量?jī)?yōu)化方程，但整個(gè)簡(jiǎn)化過(guò)程所需 計(jì)算量大，自動(dòng)化程度不高，不能滿足限時(shí)計(jì)算的要求。此后，h o p p e 2 9 1 又在原有算法 的基礎(chǔ)上，提出了基于邊折疊方法的遞進(jìn)網(wǎng)格簡(jiǎn)化方法。r o s s i g n a c 3 0 】等人提出了一種 基于頂點(diǎn)聚類的網(wǎng)格簡(jiǎn)化算法。c o h e n o s , 1 6 1 提出包絡(luò)網(wǎng)格的概念，用包絡(luò)網(wǎng)格來(lái)約束基 于頂點(diǎn)刪除的簡(jiǎn)化過(guò)程。浙江大學(xué)的潘志庚等人在己有研究的基礎(chǔ)上，對(duì)h o p p e 、c o h e n 、 t u r k 1 7 - 1 9 等人的網(wǎng)格簡(jiǎn)化算法進(jìn)行了改進(jìn)，使網(wǎng)格簡(jiǎn)化獲得了較好的應(yīng)用。 至于l o d 模型的顯示方法，可分為靜態(tài)生成方法與實(shí)時(shí)動(dòng)態(tài)生成方法兩大類。對(duì)于 靜態(tài)生成方法，國(guó)內(nèi)外已提出的方法是用一般的網(wǎng)格簡(jiǎn)化算法事先構(gòu)造出多個(gè)不同精細(xì) 程度的簡(jiǎn)化網(wǎng)格模型，并在實(shí)時(shí)繪制中，根據(jù)當(dāng)前幀的視點(diǎn)參數(shù) 2 0 - 2 2 1 ，選用相應(yīng)的網(wǎng)格 模型進(jìn)行顯示。這種算法的優(yōu)點(diǎn)是簡(jiǎn)單易用，多級(jí)分辨率模型的表現(xiàn)形式較容易統(tǒng)一。 于是，目前許多商業(yè)化系統(tǒng)大多采用這種方法。但靜態(tài)生成方法的缺點(diǎn)也是比較明顯的， 主要有：一，多級(jí)分辨率模型之間不連續(xù)，在不同模型的切換過(guò)程中可能會(huì)造成圖象的 不連續(xù)變化，產(chǎn)生明顯的走樣：二，大部分情況下，放置這些不同分辨率的逼近模型一 般需要人工干預(yù)，不能達(dá)到完全自動(dòng)：三，需要額外的內(nèi)存來(lái)存放不同分辨率的中間模 型。 對(duì)于上述問(wèn)題，h o p p e 提出了一種遞進(jìn)網(wǎng)格【2 3 1 表示方式，這種遞進(jìn)網(wǎng)格把任意網(wǎng)格 表示成一個(gè)簡(jiǎn)化的基網(wǎng)格，以及一組記錄了網(wǎng)格精化信息的序列。網(wǎng)格簡(jiǎn)化可以通過(guò)一 系列頂點(diǎn)分裂操作來(lái)實(shí)現(xiàn)，同時(shí)可以動(dòng)態(tài)實(shí)時(shí)地恢復(fù)成原始網(wǎng)格。這種方法不僅能夠提 供一組連續(xù)的多細(xì)節(jié)層次模型，還支持遞進(jìn)方式傳輸，而且還提供了一種有效的網(wǎng)格壓 縮方式。r o n f a r d 2 4 i 將三維網(wǎng)格模型中的每條邊按照它們被刪除后導(dǎo)致的幾何誤差大小 進(jìn)行排序，從小到大地進(jìn)行刪除就可以快速得到原模型的多分辨率表示。i s l e r t 2 5 】提出 了一種半實(shí)時(shí)的多分辨率表示方法。他首先用靜態(tài)簡(jiǎn)化方法產(chǎn)生幾個(gè)關(guān)鍵的簡(jiǎn)化模型， 并對(duì)其中的三角形按照他們的視覺(jué)重要度進(jìn)行排序，在繪制過(guò)程中，選擇一個(gè)三角形數(shù) 量最少，但又比所需分辨率高的簡(jiǎn)化模型，按重要度從小到大地刪除三角形直到剛好滿 足當(dāng)前的精度要求為止。e c k 2 6 , 2 7 1 提出的實(shí)時(shí)顯示方法，可以將任意三角網(wǎng)格轉(zhuǎn)化為具 有細(xì)分結(jié)構(gòu)的三角網(wǎng)格，然后再利用小波技術(shù)產(chǎn)生具有細(xì)分結(jié)構(gòu)的三角網(wǎng)格多分辨率顯 示，但這種方法還不能處理表面不連續(xù)的問(wèn)題，也不能進(jìn)行拓?fù)渖系暮?jiǎn)化，因此還有待 進(jìn)一步的完善。 上述介紹的l o d 模型生成方法中，大多都沒(méi)有對(duì)視點(diǎn)參數(shù)與模型所采用的分辨率大 小建立起直接的關(guān)系，也無(wú)法對(duì)最終生成的圖象質(zhì)量給出一個(gè)直觀的評(píng)價(jià)標(biāo)準(zhǔn)。清華大 學(xué)的李捷【2 3 1 等人提出一種l o d 模型生成算法，建立了視點(diǎn)參數(shù)與分辨率的直接關(guān)系， 使得被繪制網(wǎng)格模型隨物體與視點(diǎn)距離的改變而連續(xù)變化，并且給出了圖象質(zhì)量的評(píng)價(jià) 標(biāo)準(zhǔn)。對(duì)于網(wǎng)格簡(jiǎn)化和l o d 模型生成技術(shù)的研究，在復(fù)雜圖象實(shí)時(shí)顯示和虛擬環(huán)境限時(shí) 3 江南大學(xué)碩士學(xué)位論文 繪制中，對(duì)保證圖象逼真度、提高繪制速率、增強(qiáng)計(jì)算機(jī)實(shí)時(shí)交互反應(yīng)能力，有著重要 的推動(dòng)作用。 1 2 2 基于空間散亂點(diǎn)的三角網(wǎng)劃分技術(shù) 散亂數(shù)據(jù)點(diǎn)集三角劃分，是通過(guò)散亂數(shù)據(jù)點(diǎn)集，構(gòu)造出單元之間不相互重疊與點(diǎn)集 的占有空間相容，并能精確逼近點(diǎn)集所表示的物體表面，且形狀和密度分布合理，相鄰 邊界相容的三角網(wǎng)格。散亂數(shù)據(jù)點(diǎn)的曲面重建一直是函數(shù)逼近論的一個(gè)重要研究?jī)?nèi)容 近年來(lái)，隨著計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)的發(fā)展，基于散亂數(shù)據(jù)的曲面重建技術(shù)得到了廣 泛的研究和應(yīng)用，且該技術(shù)的發(fā)展有力地促進(jìn)了造型和可視化等技術(shù)的高速發(fā)展。在散 亂數(shù)據(jù)的三維重建當(dāng)中，其難點(diǎn)在于如何在數(shù)據(jù)點(diǎn)集中自動(dòng)地得到鄰近點(diǎn)間正確的拓?fù)?連接關(guān)系。而正確的拓?fù)溥B接關(guān)系，將有效地揭露散亂數(shù)據(jù)點(diǎn)集所蘊(yùn)涵的原始物體表面 形狀和拓?fù)浣Y(jié)構(gòu)。根據(jù)數(shù)據(jù)點(diǎn)集組織形式的不同，可以把散亂數(shù)據(jù)點(diǎn)集分成三類：第一 類，點(diǎn)與點(diǎn)之間毫無(wú)內(nèi)在聯(lián)系的數(shù)據(jù)點(diǎn)集，我們稱之為無(wú)組織數(shù)據(jù)點(diǎn)集，此類數(shù)據(jù)點(diǎn)一 般都蘊(yùn)涵著一個(gè)隱含的假設(shè)，即存在一個(gè)流形表面插值或擬合這些數(shù)據(jù)點(diǎn)。第二類主要 來(lái)自于醫(yī)學(xué)圖像，稱為輪廓線或體數(shù)據(jù)，數(shù)據(jù)點(diǎn)呈層狀分布，每一層代表物體的一個(gè)剖 面。第三類是深度散亂數(shù)據(jù)，主要由三維激光掃描測(cè)距技術(shù)所獲得，數(shù)據(jù)集往往由多幅深 度圖像所組成。事實(shí)上，這三種數(shù)據(jù)類型都可以相互轉(zhuǎn)化，如可把深度圖像數(shù)據(jù)轉(zhuǎn)化成體 數(shù)據(jù)。目前，對(duì)于無(wú)組織散亂數(shù)據(jù)的三維重建，主要有三種方法。一種方法是構(gòu)造點(diǎn)到 物體表面的有向距離場(chǎng)，該距離場(chǎng)的零等值面，即為重建曲面 3 q ，但這種算法涉及到復(fù) 雜的法向一致性檢查和等值面抽取，重建非常耗時(shí)，且重建表面需經(jīng)優(yōu)化處理【3 2 1 才能使 用。第二種方法是直接采用隱函數(shù)曲面，或參數(shù)曲面來(lái)逼近，或擬合數(shù)據(jù)點(diǎn)集。f o l e y 3 3 】 綜述了從散亂點(diǎn)重構(gòu)隱函數(shù)曲面和參數(shù)曲面的有關(guān)算法。而p r a t t 【3 4 】則直接采用簡(jiǎn)單形 狀如圓、球、直線、立方體來(lái)擬合數(shù)據(jù)點(diǎn)，但這種方法難以重建復(fù)雜拓?fù)涞那嫘螤睢?第三種方法，即應(yīng)用v o r o n o i 圖對(duì)散亂點(diǎn)集進(jìn)行d e l a u n a y 三角化。1 9 7 2 年，l a w s o n 3 5 1 提 出了三角化的最大角最小化原則，符合這一原則的三角化稱為局部均勻的。隨 后，s i b o n 3 6 1 證明了d e l a u n a y 三角化是符合這一原則的唯一形式。緊接著，g r e e na n d s i b o n1 3 7 實(shí)現(xiàn)了二維空間的v o r o n o i 圖的計(jì)算及d e l a u n a y 三角化。b o w y e r 【3 8 1 和 w a t s o n 3 9 1 把結(jié)果推廣到任意維。隨后出現(xiàn)了大量的文獻(xiàn)，其中介紹了用各種不同的方法 去實(shí)現(xiàn)v o r o n o i 圖和d e l a u n a y 三角化 4 0 - 4 2 。由于d e l a u n a y 三角剖分后的結(jié)果是一個(gè) 三角形或四面體的凸包，并不表示真正的原物體表面，其中包含許多冗余的三角形或四 面體。b o i s s o n n a t 【4 3 】對(duì)表面拓?fù)渫瑯?gòu)與球的物體介紹了一種算法，通過(guò)層層剝離冗余 四面體，使物體表面的所有散亂數(shù)據(jù)點(diǎn)可見(jiàn)。1 9 9 4 年，e d e l s b r u n n e r 【4 4 】提出了o f - s h a p e 的概念，o f s h a p e 方法通過(guò)刪除四面體凸包中，其包圍球或外接圓半徑大于o f 的四面 體、三角形和邊，使其得到重建表面。后來(lái)，b a j a jh 5 1 基口- s h a p e 生成了c 1 連續(xù)的散亂 數(shù)據(jù)點(diǎn)的插值曲面。對(duì)于均勻一致的數(shù)據(jù)點(diǎn)集，口- s h a p e 方法很有效，但由于數(shù)據(jù)點(diǎn)集的 不均勻性或表面的某種不連續(xù)性，有時(shí)很難自動(dòng)選擇合適的口值，來(lái)保留需要的三角化 元素，并刪除不需要的所有元素。 4 第一章前言 通過(guò)對(duì)上面已有的三角劃分方法的應(yīng)用和分析，發(fā)現(xiàn)散亂數(shù)據(jù)點(diǎn)集三角劃分仍存在 著以下問(wèn)題：三角劃分結(jié)果只能是一個(gè)三角形單元集合的凸包，對(duì)有復(fù)雜邊界，如帶有凹 邊界或內(nèi)孔的曲面數(shù)據(jù)，若不將原區(qū)域分解成若干凸區(qū)域，劃分結(jié)果中將有大量冗余三 角形。如d e l a u n a y 三角劃分4 7 1 、l a w s o n 、 4 6 , 4 8 1 b kc h o i 等算法都存在這一問(wèn)題?，F(xiàn)有 的三角劃分方法都只能解決三維測(cè)量數(shù)據(jù)點(diǎn)與二維投影點(diǎn)一一對(duì)應(yīng)的情況，對(duì)于單向投 影有重疊的數(shù)據(jù)點(diǎn)集，都是通過(guò)分片向合適的方向投影，分別處理后進(jìn)行拼接的方法來(lái) 實(shí)現(xiàn)。這種方式往往需要大量的人工干預(yù)，降低了三角劃分算法的效率【4 9 1 。盡管b kc h o i 算法采用在三維空間直接劃分，但因其實(shí)施條件的限制，仍然無(wú)法根本解決這一問(wèn)題。 由于在三維空間不易尋找數(shù)據(jù)點(diǎn)之間的鄰接關(guān)系，3 d 三角劃分算法的研究一直沒(méi)有取得 較大的突破性進(jìn)展。p a o l o 5 0 】等人雖然將d e l a u n a y 三角劃分?jǐn)U展到多維空間，但實(shí)質(zhì) 上仍是d & c ( d i v i d e c o n q u e r ) ，即分片拼接劃分方法從二維空間到三維空間的延伸，也 沒(méi)能解決分片所帶來(lái)的問(wèn)題。而我們介紹了解決上述問(wèn)題基于擴(kuò)展思想的曲面三角網(wǎng)劃 分算法，同時(shí)對(duì)于“非空洞的散亂點(diǎn)云，提出了基于截面線思想的三角網(wǎng)劃分，并 通過(guò)實(shí)驗(yàn)驗(yàn)證了改進(jìn)的算法。 1 3 論文研究的主要內(nèi)容 對(duì)于空間三維三角網(wǎng)劃分中依然存在的問(wèn)題，我們將從三個(gè)大的方面來(lái)介紹與研究。 其主要工作致力于真實(shí)感顯示的l o d 三角網(wǎng)劃分，以及簡(jiǎn)化，進(jìn)一步研究了基于散亂點(diǎn) 的三角網(wǎng)劃分改進(jìn)技術(shù)，并對(duì)劃分的三角網(wǎng)進(jìn)行了優(yōu)化與分析。從而提高真實(shí)感顯示當(dāng) 中所需要的網(wǎng)絡(luò)實(shí)時(shí)性與交互性，并利用先進(jìn)的掃描設(shè)備來(lái)獲取模型空間的散亂點(diǎn)，來(lái) 構(gòu)建三角網(wǎng)，從而達(dá)到降低產(chǎn)品設(shè)計(jì)與建模的代價(jià)，縮短產(chǎn)品的生產(chǎn)周期，提高產(chǎn)品的 質(zhì)量，使生成的模型的具有廉價(jià)性，精確性，以及高效性等特點(diǎn)。 1 3 1l o d 三角網(wǎng)劃分及簡(jiǎn)化 為滿足三角網(wǎng)在真實(shí)感模型顯示系統(tǒng)中的應(yīng)用，作者介紹了基于t i n 三角網(wǎng)的劃 分，以及l(fā) o d 模型的簡(jiǎn)化技術(shù)，并重點(diǎn)研究了重構(gòu)網(wǎng)格的實(shí)時(shí)動(dòng)態(tài)l o d 模型生成方法， 在h o p p e 提出的可逆遞進(jìn)網(wǎng)格的的基礎(chǔ)上，增加了邊界點(diǎn)的處理和邊界保形，并結(jié)合透 視變換的基本原理生成連續(xù)的l o d 模型。本節(jié)將詳細(xì)論述重構(gòu)網(wǎng)格的l o d 模型生成， 以及研究了重構(gòu)網(wǎng)格的實(shí)時(shí)動(dòng)態(tài)l o d 模型生成算法。通過(guò)在已有算法基礎(chǔ)上添加邊界 點(diǎn)的處理和邊界保形，并將模型視距與簡(jiǎn)化模型分辨率相關(guān)聯(lián)，來(lái)生成連續(xù)的l o d 模 型，同時(shí)對(duì)生成的l o d 模型進(jìn)行了誤差計(jì)算。 1 3 2 散亂點(diǎn)三角網(wǎng)劃分的技術(shù) 基于采集的空間物體模型的散亂數(shù)據(jù)點(diǎn)，我們介紹了散亂點(diǎn)三角網(wǎng)劃分思想，以及 在劃分當(dāng)中仍然面臨的問(wèn)題和所需要解決的問(wèn)題。對(duì)于封閉與非封閉的情況，我們介紹 了三角網(wǎng)的初始化方法，對(duì)各種曲面劃分進(jìn)行了分析，并重點(diǎn)介紹了擴(kuò)展三角網(wǎng)劃分過(guò) 程，以及對(duì)邊界環(huán)的處理，如邊界環(huán)的分裂，邊界環(huán)的融合，邊界環(huán)的封閉進(jìn)行了研究。 同時(shí)，對(duì)于模型“非空洞 的采集密度高的散亂點(diǎn)云數(shù)據(jù)，利用截面線的思想，提出了 通過(guò)引入等間距且平行的虛平面，將空間三維的數(shù)據(jù)劃分為n 個(gè)集合，對(duì)各個(gè)集合中的 江南大學(xué)碩士學(xué)位論文 數(shù)據(jù)近似在同一個(gè)空間虛平面上，且對(duì)各個(gè)近似同一空間虛平面上的集合，分別構(gòu)造截 面線，即邊界，并對(duì)每個(gè)截面線進(jìn)行特征點(diǎn)計(jì)算，對(duì)每?jī)蓚€(gè)平行截面線間進(jìn)行等比例或 非等比例劃分，從而得到模型的三角網(wǎng)。并通過(guò)實(shí)驗(yàn)驗(yàn)證了本文方法的可行性，有效性 與準(zhǔn)確性。 1 3 3 三角網(wǎng)劃分的優(yōu)化技術(shù) 本章對(duì)完成劃分后的三角網(wǎng)提出了優(yōu)化方法，其中對(duì)當(dāng)前三角網(wǎng)優(yōu)化過(guò)程中的頂點(diǎn) 優(yōu)化方法，空間網(wǎng)格的優(yōu)化方法進(jìn)行了介紹，由于這兩種方法都存在不能同時(shí)滿足：( 1 ) 網(wǎng)格中三角形形狀規(guī)整。( 2 ) 三角網(wǎng)格在誤差范圍內(nèi)逼近實(shí)物曲面。在上面這兩種情況 下，重點(diǎn)介紹了綜合優(yōu)化方法，其方法可以實(shí)現(xiàn)：若三角網(wǎng)格空間形狀與實(shí)際曲面的 誤差超過(guò)了規(guī)定范圍，能適當(dāng)?shù)靥砑泳W(wǎng)格頂點(diǎn)，即對(duì)網(wǎng)格進(jìn)行局部細(xì)化，使新網(wǎng)格m 與 實(shí)際曲面的誤差在規(guī)定的范圍之內(nèi)。當(dāng)網(wǎng)格空間形狀滿足要求，網(wǎng)格頂點(diǎn)數(shù)量確定時(shí)， 可以保證網(wǎng)格中的三角形形狀最優(yōu)。同時(shí)，就當(dāng)前模型的逼近細(xì)分優(yōu)化方法，做了重點(diǎn) 介紹，并給出了細(xì)分優(yōu)化的算法過(guò)程。通過(guò)上面優(yōu)化理論的介紹，可以很好的保證構(gòu)建 的三角網(wǎng)具有高的逼真度，和準(zhǔn)確度。 1 4 論文的結(jié)構(gòu) 各章節(jié)內(nèi)容分布如下： 第一章緒論，主要介紹了課題的相關(guān)背景。我們按空間三角網(wǎng)劃分的方法和思路 的不同，對(duì)三角網(wǎng)劃分的方法進(jìn)行了論述；既介紹了早期三角網(wǎng)劃分的一些特征，也重 點(diǎn)對(duì)最近十幾年來(lái)的最新發(fā)展情況進(jìn)行了詳盡的介紹。并重點(diǎn)介紹了基于l o d 三角網(wǎng) 劃分與空間散亂點(diǎn)的三角網(wǎng)劃分過(guò)程，并引入了本文所需要解決的問(wèn)題和采用的方法， 給出了本文的技術(shù)思路。 第二章為了能達(dá)到真實(shí)感顯示的目的，研究了動(dòng)態(tài)l o d 的三角網(wǎng)劃分的層次遞進(jìn) 方法，重點(diǎn)介紹了l o d 三角網(wǎng)的簡(jiǎn)化技術(shù)，視距與簡(jiǎn)化模型的分辨率，l o d 模型的誤 差計(jì)算，以及遞進(jìn)l o d 三角網(wǎng)具體實(shí)現(xiàn)的算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了動(dòng)態(tài)l o d 模型的生 成技術(shù)。 第三章對(duì)于空間三維的散亂點(diǎn)數(shù)據(jù)，我們介紹了各種劃分技術(shù)，并基于截面線的 思想，對(duì)于“非空洞”的三維模型，改進(jìn)了三角網(wǎng)劃分，并通過(guò)實(shí)驗(yàn)證實(shí)了該方法的有 效性，可靠性。 第四章介紹了三角網(wǎng)的優(yōu)化技術(shù)，并給出了頂點(diǎn)優(yōu)化技術(shù)，空格網(wǎng)格的優(yōu)化技術(shù)， 以兼有上兩種方法優(yōu)點(diǎn)的綜合優(yōu)化技術(shù)。并重點(diǎn)介紹了模型逼近細(xì)分優(yōu)化技術(shù)，以及上 面各種優(yōu)化技術(shù)的實(shí)現(xiàn)算法。 第五章對(duì)本篇論文進(jìn)行了總結(jié)，提出了論文還依然面臨的問(wèn)題，同時(shí)對(duì)今后需要 進(jìn)一步努力和完善的工作做了介紹。 6 第二章基于l o d 三角網(wǎng)劃分的研究 第二章基于l o d 三角網(wǎng)劃分的研究 基于l o d 三角網(wǎng)劃分技術(shù)，為了應(yīng)用于真實(shí)感顯示中，在保證網(wǎng)絡(luò)傳輸?shù)膶?shí)時(shí)性， 又不損失圖形的質(zhì)量，以及物體模型不失真的情況下，我們介紹了基于t i n 三角網(wǎng)劃分 的技術(shù)，研究了l o d 三角網(wǎng)的簡(jiǎn)化技術(shù)，并在基于h o p p e 提出的遞進(jìn)網(wǎng)格基礎(chǔ)上，結(jié)合 透視變換原理生成和顯示連續(xù)的l o d 模型的具體方法與算法，以及l(fā) o d 模型的屏幕誤差 的計(jì)算。 2 1 基于t i n 的三角網(wǎng)劃分 由于客觀世界是不規(guī)則的，致使三角網(wǎng)劃分技術(shù)分為兩類，一類是不規(guī)則的三角網(wǎng) 劃分，即t i n 三角網(wǎng)劃分，另一類是規(guī)則的三角網(wǎng)劃分，即t i n 6 - 8 】三角網(wǎng)劃分。由于 規(guī)則的三角網(wǎng)是不規(guī)則三角網(wǎng)的特例，且在基本上保證模型的表面特征的情況下，能應(yīng) 用于實(shí)時(shí)繪制與網(wǎng)絡(luò)的虛擬場(chǎng)景的交互，所以重點(diǎn)介紹三角網(wǎng)劃分的t i n 技術(shù)，即點(diǎn)擴(kuò) 張技術(shù)，徑向掃描技術(shù)，基于凸殼的快速生成技術(shù)。 2 1 1 點(diǎn)擴(kuò)張技術(shù) 點(diǎn)擴(kuò)張技術(shù)是借鑒“生長(zhǎng) 的思想，如2 1 ( b ) 圖所示，首先采集得到模型( a ) 的數(shù)據(jù) 點(diǎn)集s = 否 求出y 。頂點(diǎn)的s t a r ( k ) 及 v ，頂點(diǎn)的頂點(diǎn)環(huán)并按逆時(shí)針捧 序 上 計(jì)算頂點(diǎn)s t a r ( 形) 在平均乎蕊 上的投影坐撂及礦，的曲率盔 土 縣 名：瀛歪 土， 二，7 f 計(jì)算礦到邊界邊拉直線l i 段的距離dl 多 如果吐 n 堡 刪除v ，及s t a r ( 杉) ， 并補(bǔ)留下的空洞 r 。一 l j - 2 2 2 3 簡(jiǎn)化的準(zhǔn)則 圖2 - 7 簡(jiǎn)化的流程圖 f i g 2 - 7s i m p l i f i e df l o wc h a r t 江南大學(xué)碩士學(xué)位論文 在三角網(wǎng)的簡(jiǎn)化過(guò)程中，要得到一個(gè)優(yōu)良的簡(jiǎn)化模型，必須要有一個(gè)好的簡(jiǎn)化準(zhǔn)則。 好的簡(jiǎn)化準(zhǔn)則應(yīng)該能使原始模型的頂點(diǎn)刪減率高，計(jì)算量小，而且簡(jiǎn)化后的模型應(yīng)盡可 能的保留原始模型的拓?fù)浣Y(jié)構(gòu)性質(zhì)。 網(wǎng)格簡(jiǎn)化的常用準(zhǔn)則有點(diǎn)到平均平面的距離1 5 1 1 、頂點(diǎn)曲率【5 2 1 、特征角 5 3 1 、二次誤 差度量 5 4 - 5 6 1 等，通常將幾個(gè)準(zhǔn)則結(jié)合起來(lái)進(jìn)行判斷，如文獻(xiàn)【5 7 1 是根據(jù)點(diǎn)到星型鄰域平 均平面的距離和網(wǎng)格局部拓?fù)涮卣鞯淖R(shí)別來(lái)作為頂點(diǎn)取舍的判斷準(zhǔn)則，這有效的處理了 高斯曲率近于零，而平均曲率較大的網(wǎng)格，其簡(jiǎn)化效果好，但過(guò)程較復(fù)雜。所以我們把 頂點(diǎn)曲率與頂點(diǎn)到其星型鄰域平均平面的距離這兩個(gè)條件結(jié)合起來(lái)作為判斷準(zhǔn)則，具體 的判斷過(guò)程分兩種情況。第一種情況，如圖2 8 所示，若& 穢( k ) 為全星型鄰域，則選 擇位于物體表面曲率最小處的頂點(diǎn)予以刪除，一般是用戶給定一閥值e l ，當(dāng)曲率小于該 值時(shí)，就滿足刪除要求。刪除頂點(diǎn)后并將該點(diǎn)的星型鄰域的三角形也刪除，然后對(duì)網(wǎng)格 生成的空洞進(jìn)行約束三角剖分，提取星型領(lǐng)域邊界。對(duì)于邊界的提取，可按照對(duì)邊界邊 的定義來(lái)實(shí)現(xiàn)，即對(duì)只屬于一個(gè)三角形的邊進(jìn)行提取。 圓q 圖2 8 星型領(lǐng)域與邊界的提取 f i g 2 - 8 s t a ro ft h ee x t r a c t i o no ft h eb o r d e ra r e a s 對(duì)于頂點(diǎn)的曲率的計(jì)算，可以參考4 4 1 的方法，如圖2 - 9 所示，設(shè)簡(jiǎn)單頂點(diǎn)為q ，荔為q 點(diǎn) 的平均平面的法向量，互，最，最為q 點(diǎn)的星型鄰域中的頂點(diǎn)，置為從q 點(diǎn)到z 點(diǎn)的向量， 圖2 - 9 o 頂點(diǎn)的曲率計(jì)算 f i g 2 - 9 v e r t e xo ft h eqc u r v a t u r ec a l c u l a t i o n o = 1 ，2 ，七) ，包為磊與葛的夾角，則q 點(diǎn)的曲率計(jì)算如公式( 2 3 ) ： 一( q ) 2 南2 ( 2 3 ) 上述對(duì)離散點(diǎn)的曲率的估算方法其實(shí)是很粗糙的，若需要得到較精確的值，可以對(duì) 離散數(shù)據(jù)點(diǎn)，先作插值或擬合，再求曲率，但這樣會(huì)增加計(jì)算的復(fù)雜性，降低速度。鑒 于我們需要的只是曲率值的大小，所以上述對(duì)離散點(diǎn)曲率值的估算還是很有效的。 1 4 第二章基于l o d 三角網(wǎng)劃分的研究 第二種情況，若s t a r ( v i ) 為半星型鄰域，設(shè)其與k 點(diǎn)相鄰的兩條邊界線段為k s 和 匾，可對(duì)這兩線段進(jìn)行拉直操作，拉直后為虛線雨，如圖2 - 1 0 所示。滿足第一種 1 圖2 - 1 0 線段的拉直操作 f i g 2 1 0s e g m e n to f t h es t r a i g h t e n i n go p e r a t i o n 情況后，還必須滿足k 點(diǎn)到過(guò)點(diǎn)s ，島的直線距離小于用戶給定的某一誤差值吃，即滿 足式( 2 4 ) ： 令a = k 墨，b = k s 2 ，則 拈蹦乞 ( 2 4 ) 2 2 2 4l o d 三角網(wǎng)的簡(jiǎn)化算法 對(duì)于l o d 三角網(wǎng)的簡(jiǎn)化算法，其具體的描述如下： ( 1 ) 對(duì)于頂點(diǎn)集隱= 以，圪) 中每一點(diǎn)巧，求出s t a r ( v j ) ，然后執(zhí)行( 2 ) 到( 5 ) 。 ( 2 ) 提取& 甜眈) 三角形的邊界，通過(guò)邊界中是否包含巧點(diǎn)判斷& 心) 是完全星型 鄰還是半星型鄰域。即不包含說(shuō)明s t a r i v j ) 是全星型鄰域，否則是半星型鄰域。 ( 3 ) 計(jì)算每個(gè)點(diǎn)的曲率，s t a r ( v 1 ) 是半星型鄰域時(shí)還需計(jì)算該點(diǎn)到邊界的距離，如圖 2 1 0 所示，對(duì)于符合簡(jiǎn)化準(zhǔn)則的點(diǎn)，還要置該點(diǎn)移去標(biāo)志為真。否則，置該點(diǎn)移去標(biāo) 志為假。 ( 4 ) 對(duì)移去標(biāo)志為真的頂點(diǎn)，按其符合的準(zhǔn)則進(jìn)行空洞剖分區(qū)域內(nèi)的劃分，并分別 進(jìn)行約束三角剖分。 ( 5 ) 根據(jù)剖分結(jié)果修正相關(guān)數(shù)據(jù)結(jié)構(gòu)。 ( 6 ) 重復(fù)以上步驟，直到頂點(diǎn)集v e x = 以，砭，圪) 中，每個(gè)頂點(diǎn)均不滿足簡(jiǎn)化準(zhǔn)則 為i e 。 對(duì)于( 4 ) 中的約束三角剖分，其具體實(shí)現(xiàn)過(guò)程如下： ( 1 ) 計(jì)算s t a r ( v ，) 的平均平面p 的方程，并在該平面p 上建立一個(gè)局部坐標(biāo)系。求出 邊界多邊形中每一頂點(diǎn)在平面p 上的投影，并用單向循環(huán)鏈表保存頂點(diǎn)，順序連接投 影點(diǎn)得到一平面多邊形。具體過(guò)程如下：設(shè)平均平面p 的單位法矢為n ，中心坐標(biāo)為c ， x 為p 上一點(diǎn)，則平面p 的方程為( 2 5 ) ： 玎( x c ) = a x + b y + c z + d = 0 ( 2 5 ) 1 5 江南大學(xué)碩士學(xué)位論文 則邊界多邊形的每個(gè)頂點(diǎn)s ，= b f ，y y ，z f 只= l ，2 ，到平面p 的有向距離為： d ，= a x ，+ 8 y ，+ c z ，+ d ( 2 6 ) 由此得s ，在p 上的投影坐標(biāo)為s ? = s ，一d ，刀，令g = s ? 一c ，則取p 上的兩個(gè)正 交單位向量。 島= 矗，6 2 = n 島 ( 2 7 ) 蚓 于是可得多邊形上任意頂點(diǎn)s ，的投影點(diǎn)s ? 的局部坐標(biāo)為： “，吩) = 僻一c ) 6 l ，研一c ) b 2 ) ( 2 8 ) ( 2 ) 如果該多邊形是非自交的，轉(zhuǎn)到( 3 ) ，否則，表示該環(huán)不能三角化，那么產(chǎn)生該環(huán) 的候選頂點(diǎn)不能刪除，轉(zhuǎn)到( 6 ) 。 ( 3 ) 判斷多邊形頂點(diǎn)的凸凹性。在循環(huán)鏈表中順序取3 個(gè)節(jié)點(diǎn)p 、q 、r ，若q 點(diǎn)為凸 點(diǎn)，并且由p 、q 、r 構(gòu)成的三角形內(nèi)不包含其它頂點(diǎn)，則按式( 2 2 ) 計(jì)算a q p r 的品質(zhì)系 數(shù)，求出這樣的所有三角形，并從中選擇品質(zhì)系數(shù)值最大的三角形p q r ，保存該三角 形，并從鏈表中刪除q 頂點(diǎn)，否則轉(zhuǎn)( 4 ) 。 ( 4 ) 若鏈表中存在4 個(gè)以上的節(jié)點(diǎn)，保存該三角形p q r ，并從鏈表中刪除節(jié)點(diǎn)q ，轉(zhuǎn) 步驟( 2 ) ，否則，判斷p q r 與除q 點(diǎn)外的余下三點(diǎn)構(gòu)成的三角形是否構(gòu)成凸四邊形，如 能構(gòu)成凸四邊形，則按最小內(nèi)角最大準(zhǔn)則進(jìn)行優(yōu)化，并保存優(yōu)化后的2 個(gè)三角形，轉(zhuǎn)步 驟( 6 ) ，如果不能構(gòu)成凸四邊形，保存p q r ，轉(zhuǎn)步驟( 5 ) 。 ( 5 ) 由鏈表中最后3 個(gè)節(jié)點(diǎn)構(gòu)成1 個(gè)三角形。 ( 6 ) 結(jié)束。 2 3 基于可逆遞進(jìn)網(wǎng)格的動(dòng)態(tài)l o d 技術(shù) 在h o p p e 提出的可逆遞進(jìn)網(wǎng)格的的基礎(chǔ)上，我們研究了重構(gòu)網(wǎng)格實(shí)時(shí)動(dòng)態(tài)l o d 模型 生成方法，增加了邊界點(diǎn)的處理和邊界保形，并結(jié)合透視變換的基本原理生成連續(xù)的l o d 模型，本節(jié)將詳細(xì)論述重構(gòu)網(wǎng)格的l o d 模型生成和顯示的具體過(guò)程和算法。 2 3 1 遞進(jìn)網(wǎng)格的實(shí)現(xiàn)過(guò)程 為了支持真實(shí)感模型的多分辨率實(shí)時(shí)動(dòng)態(tài)顯示，必須要生成連續(xù)的l o d 模型，實(shí) 現(xiàn)多級(jí)分辨率模型間的平滑過(guò)渡?？赡孢f進(jìn)網(wǎng)格就是一種構(gòu)造連續(xù)l o d 模型的有效方 法。這種方法不僅能大大節(jié)省存儲(chǔ)空間，而且由算法對(duì)原始模型做一次處理就可生成， 避免了在實(shí)時(shí)顯示過(guò)程中進(jìn)行大量的計(jì)算和存儲(chǔ)。 可逆遞進(jìn)網(wǎng)格的構(gòu)造方法可采用邊折疊法、頂點(diǎn)刪除法或者三角形刪除法。這三 種方法的實(shí)現(xiàn)方法雖然不同，但得到的結(jié)果卻是一致的。一個(gè)邊折疊操作是將一條邊 的一個(gè)端點(diǎn)向另一個(gè)端點(diǎn)合并，其結(jié)果如圖2 1 1 ( b ) 所示。頂點(diǎn)刪除法的實(shí)現(xiàn)方法不同 于上面三角網(wǎng)星型領(lǐng)域簡(jiǎn)化方法，它是引入了頂點(diǎn)的重要度計(jì)算來(lái)刪除頂點(diǎn)，在刪除 頂點(diǎn)后所形成的多邊形空洞進(jìn)行重新三角劃分，其結(jié)果如圖2 1 2 ( b ) 所示。對(duì)比圖2 1 l 和圖2 1 2 中的頂點(diǎn)k 的變化，不難發(fā)現(xiàn)，雖然邊折疊方法是將k 向虼合并，而頂點(diǎn)刪 1 6 第二章基于l o d 三角網(wǎng)劃分的研究 除操作則是在刪除頂點(diǎn)圪后重新三角劃分，但多邊形kk 巧虼最終的三角形劃分情 況卻是相同的。同時(shí)，邊折疊和頂點(diǎn)刪除過(guò)程也是三角形刪除的過(guò)程。邊折疊法、頂 點(diǎn)刪除法和三角形刪除法雖然結(jié)果一致，對(duì)網(wǎng)格局部變化的記錄方法卻不相同，而最 簡(jiǎn)單、明確的數(shù)據(jù)記錄方法，是最能方便、迅速地生成可逆遞進(jìn)網(wǎng)格。 v i v j 蘑 幻 v j ( a ) 邊折疊前( b ) 邊折