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

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