（計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)論文）marching+cubes算法研究現(xiàn)狀.pdf

山東大學(xué)碩士學(xué)位論文 摘要 等值面技術(shù)在可視化中應(yīng)用廣泛，許多標(biāo)量場(chǎng)中的可視化問(wèn)題都?xì)w納為等值 面的抽取和繪制，m 缸c l l i n gc i l b 囂方法是目前應(yīng)用最為廣泛的等值面抽取方法之 一。自1 9 8 7 年l o 枷s 等提出該算法以來(lái)，就因?yàn)槠浜?jiǎn)單高效取得了眾多研究 人員的關(guān)注，被廣泛的應(yīng)用于醫(yī)學(xué)圖像重構(gòu)，有限元分析，隱式曲面繪制等領(lǐng)域 的研究中，取得了許多重要的成果。但算法也存在一些不足之處。在目前為之， 已經(jīng)有大量的研究工作對(duì)m a r c h i n gc u b e s 算法本身進(jìn)行了有效的探討，來(lái)對(duì)該 算法進(jìn)行完善和提高它的運(yùn)算效率。本文按照改進(jìn)算法對(duì)m a r c h i n gc u b 囂的具 體領(lǐng)域的改進(jìn)，提出歸類(lèi)方法并進(jìn)行比較討論，為在具體的領(lǐng)域中應(yīng)用和進(jìn)一步 研究改進(jìn)算法，有著很好的借鑒意義。 本文首先介紹了算法的研究背景和意義，以及該領(lǐng)域相關(guān)的工作和研究現(xiàn) 狀，然后闡述了算法的基本原理，討論了其優(yōu)缺點(diǎn)和產(chǎn)生這些優(yōu)缺點(diǎn)的原因。算 法在構(gòu)造等值面的過(guò)程中，太依賴于直觀的構(gòu)造，構(gòu)建體元狀態(tài)模型時(shí)，對(duì)于對(duì) 稱(chēng)，旋轉(zhuǎn)等情況的處理缺乏全面考慮，忽視了立方體內(nèi)部可能存在的環(huán)狀結(jié)構(gòu)和 存在的臨界點(diǎn)( 等值面發(fā)生變化的點(diǎn)) ，直接使用求得的邊界等值點(diǎn)，根據(jù)基本 的體元狀態(tài)模型，簡(jiǎn)單連接成三角片構(gòu)成等值面，導(dǎo)致生成的等值面有在拓?fù)浣Y(jié) 構(gòu)，表示精度和效率方面，不能滿足實(shí)際應(yīng)用中的需求。 文章對(duì)算法構(gòu)造的等值面在拓?fù)浣Y(jié)構(gòu)方面存在的二義性分面上的二義性和 體上的二義性兩個(gè)方面進(jìn)行討論。首先分析了立方體面上存在二義性的原因，給 出了解決面上二義性的辦法；隨后，通過(guò)分析插值曲面在體元內(nèi)部可能存在的結(jié) 構(gòu)，引出體二義性，并且根據(jù)解決體二義性方法的不同原理，分四個(gè)類(lèi)別對(duì)解決 方法進(jìn)行討論，根據(jù)三線性插值函數(shù)等值面的特性和不同體元模型的實(shí)驗(yàn)結(jié)果， 指出了每一類(lèi)算法存在的問(wèn)題和優(yōu)勢(shì)所在。 由于m 盯c h i n gc u b 髂算法求逼近等值面的過(guò)程中，使用線性插值計(jì)算出等值 面與立方體邊的交點(diǎn)之后，采用簡(jiǎn)單連接的方式，形成逼近等值面的邊界多邊形， 然后進(jìn)行三角化得到最終的逼近等值面片，所以當(dāng)算法針對(duì)采樣稀疏的數(shù)據(jù)場(chǎng)構(gòu) 造等值面時(shí)，會(huì)出現(xiàn)等值面精度不高的問(wèn)題，無(wú)法保證所形成的等值面的表示精 度。增加采樣點(diǎn)無(wú)疑是提高表示精度的直接方法，但是隨著采樣點(diǎn)的加入，形成 山東大學(xué)碩士學(xué)位論文 三角片的增加，所需要的存儲(chǔ)空間和處理時(shí)間往往超出系統(tǒng)的負(fù)荷和實(shí)時(shí)應(yīng)用的 要求：另一種方法是漸進(jìn)式網(wǎng)格抽取算法，算法通過(guò)逐漸細(xì)化的方法，逐步提高 表示精度，直到達(dá)到應(yīng)用要求為止，這種方法可以在增加計(jì)算量不大的情況下提 高精度。 m a r c h i n gc u b e s 算法對(duì)每一個(gè)立方體單元進(jìn)行處理，耗費(fèi)大量的時(shí)間，同時(shí)， 在采樣密度較高的數(shù)據(jù)場(chǎng)中，也往往生成過(guò)多三角面片，導(dǎo)致算法效率大大降低。 本文對(duì)這種情況進(jìn)行分析，總結(jié)了提高算法效率的主要方法。然后將這些方法分 成三類(lèi)：第一類(lèi)方法通過(guò)建立合適的數(shù)據(jù)結(jié)構(gòu)，跳過(guò)不存在等值面的體元，有效 的節(jié)省了生成等值面所需要的時(shí)間；第二類(lèi)方法旨在討論節(jié)省存儲(chǔ)空間的幾種方 法，主要是在保證逼近精度的情況下，通過(guò)合并相鄰的三角面片進(jìn)行實(shí)現(xiàn)；文章 重點(diǎn)討論了第三類(lèi)，即多分辨率方法，該方法兼顧算法時(shí)間和空間兩個(gè)方面的耗 費(fèi)，有效地解決了交互顯示等實(shí)際應(yīng)用問(wèn)題。 。 文章最后對(duì)m a r c h i n gc u b 豁改進(jìn)算法進(jìn)行總結(jié)，并展望了算法今后的發(fā)展方 向，對(duì)實(shí)踐中具體應(yīng)用算法和對(duì)其進(jìn)一步進(jìn)行研究，都有很重要的借鑒意義。 關(guān)鍵詞：可視化；等值面抽??；拓?fù)涠x性；精度；效率 i i 山東大學(xué)碩士學(xué)位論文 a b s t r a c t i s o s i i k et e c i l l l o l o 韶i s 謝d e i y 璐e di i lv i s u a l i z a 6 0 n 鋤dm a n ys c a l 缸f i e l d 、，i s l l a l i z 撕珊d b l 鋤sc 鋤b e l v e db yi s o s u r f 赫n g 鋤dr d e 血呂m a r 凼n gc u b e s a l g o r i t i l i ni s t l l en d s t 麗d e l yu di s l l 一沁em e 山o dm l wf r o m1 9 8 7w h 吼 l o r e n 湖b r o 心h tf o r w a r dt h i sm e m o d m a n yr 髂e 缸c h e r sh a db e i m e r 囂t e d i l li tf o f “ss i m p l i d 夠鋤de m c i 鋤盯i ti s 晰d e l yu d mm a n ya r e 嬲，s u c h 鵲m e d i c a li m a g e r e c 吼s 蟣l c t i o i l ，觚t ee l 咖e n t 姐a l y s i s ，i n l p l i c i ts u r f 缸er d e r i n ge t c ，t h e f eh a v eb 咖 n u m e r o 璐r e a r c h e so nm a r c h i n gc u b 鼯畦l ln o w t oi n l p f o v e1 h e 桶c i c y 鋤dm a l 【e i tw o r kb e t t 既h lt l l i sp a p 也ei m p r o v 鋤e n ta l g o r i t l l 】【i l sa r e 、，i e 刪鋤dc l 舾s i f i e d a c c o 岫n g t o t 量l ea s p e c 協(xié)t l l e yh a v e i m p r o v e d t l l ea l 鰣血i nt l l i s w o r k 、】l i i uh a v e a d e 印i m p a c to nt l l ef h r t i l e rr e s e a r c h 趾da p p l i c a l i o n i l lt l l es p e c i 丘ca r e 弱 1 k sp a p e rf i r s ti i l 仃0 d u c 郫t h eb k g r o l | l i d 肌di n l p o r 啪c eo ft l l es t i l 衄s o m e e 菇s t i n gw o r k 孤dm e i i l o d sa b o u tt l l ea l g o r i t l l ma r ei m r o d u c e dt h 百v 囂o u tm e d e f i n i 6 0 n ，t 1 1 ed i s a d v 鋤t a g 鶴鋤da d v 鋤t a g e so f t i l ea 1 9 0 f i t l l l 砸鋤de x p l a i 鄴h o wa r e 1 1 1 e p r o b l e m sa r eb r o u g h ta b o l i t h lt 1 1 ep r o c 囂so fi s i | r f 如i n 呂t h ea l g o r i t h ml k s c o n s i d e r a t i o no f t l l ei n t e r i o rs 咖c t i l i o f t h ev o x e l 鋤dt a l 【e1 l l e 伍鋤百器i nt h es 協(xié)t e 1 1 1 0 d u l e 鶴i s o s u r f 缸e sf o r1 1 1 e r em a yb es o m ec r i 石c a lp o i n 協(xié)鋤dl o o p sw h e r et h e i s o s u m i c e sm a yc h 鋤g ei t ss h 印e ，t 量l ei s o s l | r f 缸豁p r o d u c e di i l 也i sw 鑼m 幫h a v e m 鋤yp r o b l e m si nt o p o l o g 蜘p r e c i s i o n 鋤de m c i c y 鋤dc 鋤ts a t i s 分m a n y a p p l i c a 吐o l l s t h e r ea r ef 缸e 鋤b i 鰣鑼鋤db o d y 鋤b i g i l i t yp r o b l 鋤sa b o l i tt 量l ea l g o m h i i lh i t l l i sp a p e r ，t 1 1 en 圯t l l o d st 0s o l v et l l ef 缸e 觚l b i g l l i t ya r ep l l tf o 刑a r d e df i r 甌齜dl 量l e n d i s c l l s s e s1 l l es o i 砸o n so fb o d ya l l l b i g i l i 鑼p r o b l e 腳f 如mf o l | ra s p e c t s t h r o u g h a 1 1 由豳gt h ep d o p e n i e so ft l l e 伍l i i l e a ri i l 僦p o l 撕o nf 血c t i o n 鋤dt l l ee 沖耐m 鋤t a l r e s l l l t s ，t h ed i f l e r c 鯔鋤m n gt i i ec l 船s m c a t i o n sa 旭p u tf 0 確d e d h it 1 1 i sp a p e lt l l ep r o b l e m so fl o wa c c u r a c yi s o s l l r f 缸鶴i ns p a r s e 紕f i e l da r e d i s c 璐s e d1 1 1 em a r c h i n gc u b e sa l g o m mf i r s t l yc o m p u t e st l l ei n t e r s e c t i o np o i n 怊 b e t w e e nt l l ei s o s u r f h e s 鋤dv o x e l s ，t l l e nl l s e st h ep o i n t st of o n n 證鋤羽鶴w h i c h 黜 山東大學(xué)碩士學(xué)位論文 忸k e r i 翹l l l ef _ m a la p p r o ) d m a t ei s o s l l r f a c e s h lt h i s 唧，血ea l g o r i t l l mc 猢o tg 哪i i t e e t h e c l l r a c yo ft h ei s o s u r f a c e ad i r e c tn 蚓 h o dt os o l v e1 l l i sp r o b l e mi st oi n c r e a s 鋤1 p l i n gp o i n 招，b m 塒1 l lm ei i i c 佗m to ft 量l ep o i n 協(xié)，t l l e r em 妙b et o om u c hs p a c e 舭dt i m en e e d e dt 0p r o c e s si i l 鋤i n t e r a c 6 v ew a ya n o m e rm e 山o dt oi m p r o v em e 孔c u r a c yi s 1 l l ea d a p 矗v e 鰣dm e l l l o dw i l i c ha b s t r a c st l l e 仃i 鋤百eg r a d u a l l yt i l l1 l l e a c c i l r a c yi ss 撕s 丘e da n dm i sm e m o dc a ni m p r o v em ea c c u m c y 、】v i t l l o l i ti l l c r e 舔i n g t 0 0m u c hc o m p u t 撕o n t i l i sp 印盯a l s o 鋤a l y z 器1 l i ec i r c m n s t a l l c et l l a tt h ea l g o 疵l i i i lm a yo f t l mp r o d u c e t o om 舡】ym 鋤甜囂i nd d a t af i e l da n dm e np u tf o r 啪r d1 i l em a i l lm e m o d st o i m p f o v et l l e 喊c i 印c y t h e r e 盯et h r e et y p e so fm e m o d s 協(xié)l v e1 l l ep r o b l 唧o n e w 幫i s 協(xié)a v o i ds w e 印i n gm ev o x e l sw h i c hd o nn o th a v ea n yi s l l 一沁鶴t os a v e 矗m e ； a 1 1 0 t h e rm e t i l o da i m s 協(xié)s a v e1 l l es p e s ，鋤dt i l e 刪i i l l 、唧i s 協(xié)c o m b i n es e v e r a l m a n g l e si n t o0 n e ；t h em l | 1 6 - r e l i n i o nm 劬o d i st i l ew i d e l y 懈e do n e 協(xié)i m p f o v em e e m c i e n 吼1 1 l i sm e m o d 啪s i d e 培t i 埠幻瑙i i lb o t l ls p a c e 鋤d6 m ea n dc 觚s a l i s 匆 1 量1 ep m c t i c a la p p l i c a t i o ns u d h 鵲i m 僦t i v ed i s p l a y a t l a s t ，“sp 印e rs u n 蚰a r i z 髂t l l em e m o d sa n d 百v 銘1 l l ef u t u r er e s e 砌仃鋤d s o fm 刪n gc u b 韶i n l p r o v 鯽e n tm e t h o d s a i l dt l l i si i l i 曲t h a v ei n 啪n 鋤ti m p a c t t l l e 如曲e rr e s e 砌w o f l 【鋤dp r a 甜c a la p p l i c 撕o n k e yw o r d s ：s u a l i z a t i 蚰，i s o s u r f a c i n 舀t o p o i o 貿(mào)a m b i g u i 鋤a c c u r a 鐋 e m c i 蛐c y 原創(chuàng)性聲明和關(guān)于論文使用授權(quán)的說(shuō)明 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú) 立進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不 包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的科研成果。對(duì)本文的研 究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本聲明 的法律責(zé)任由本人承擔(dān)。 論文作者簽名：雌日期：2 羋 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解山東大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保 留或向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱；本人授權(quán)山東大學(xué)可以將本學(xué)位論文的全部或部分 內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或其他復(fù)制手 段保存論文和匯編本學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 啤一名：僻 山東大學(xué)碩士學(xué)位論文 1 1 研究背景和意義 第一章緒論 面繪制是科學(xué)計(jì)算可視化方法中常用的一種方法，它從原始的三維數(shù)據(jù)中重 建出中間的幾何圖元( 一般是以三角面片或者體元組成的曲面) ，然后使用真實(shí)感 圖形學(xué)技術(shù)對(duì)幾何圖元進(jìn)行光照計(jì)算和繪制【1 捌。面繪制技術(shù)的基本原理是，首 先對(duì)整個(gè)數(shù)據(jù)進(jìn)行等值表面分割和定義，用各種幾何元擬合表面，然后繪制出所 有的幾何元【3 】。在可視化中常用的幾何元有體元級(jí)大小的平面多邊形、多邊形網(wǎng) 格、三角片等。實(shí)際上，從數(shù)據(jù)場(chǎng)中構(gòu)造的表面就是提取的某一閾值的逼近等值 面。許多標(biāo)量場(chǎng)中的可視化問(wèn)題都?xì)w納為等值面的抽取和繪制，如醫(yī)學(xué)圖像中的 三維重建；有限元計(jì)算中的標(biāo)量場(chǎng)分析，分子化學(xué)中的分子表面顯示；地質(zhì)中礦 藏分布的構(gòu)造等等。在散亂點(diǎn)的雎面重建h 5 】和關(guān)鍵幀動(dòng)畫(huà)1 6 刀中，也常常提取零 等值面作為散亂點(diǎn)數(shù)據(jù)的重建曲面和中間幀。近年來(lái)，等值面逼近問(wèn)題得到了極 為廣泛的關(guān)注，并取得了許多重要的成果。m a r c h i n gc u b e s 方法以其簡(jiǎn)單和高效 的特點(diǎn)，成為應(yīng)用最廣泛的等值面逼近方法。 隨著成像設(shè)備的不斷更新及其性能的提高，斷層掃描序列圖像的層內(nèi)與層間 分辨率較以前有顯著提高，使得能夠在二維水平上更加清楚、直觀地看到物體結(jié) 構(gòu)的細(xì)微特征，從而獲得越來(lái)越詳實(shí)的信息。然而，這些二維影像數(shù)據(jù)只是表達(dá) 某一截面的信息，研究人員只能通過(guò)二維圖像進(jìn)行觀察，所得到的結(jié)果往往帶有 研究人員的主觀判斷和研究經(jīng)驗(yàn)。地r c h i n gc u b e s 算法的不斷完善和發(fā)展，使 得提供直觀、逼真而且能夠包含原始信息中隱含的豐富內(nèi)容的三維信息成為可 能。通過(guò)圖形圖像技術(shù)，可以對(duì)影像進(jìn)行任意放大、縮小、旋轉(zhuǎn)、對(duì)比調(diào)整、三 維重建等處理，得到便于研究者從多角度、多層次進(jìn)行觀察的三維模型。這對(duì)分 析結(jié)果的準(zhǔn)確性和正確性有深遠(yuǎn)的意義，并促進(jìn)了應(yīng)用領(lǐng)域的飛速發(fā)展。 1 2 相關(guān)工作和研究現(xiàn)狀 在1 9 8 7 年，由w e l o r e n s o n 和h e c l i n e 嘲提出的m a r c h i n gc u b e s ( 以下將 其稱(chēng)為m c ) 是基于體元的一種典型的面繪制方法。m c 算法作為一種構(gòu)造等值面的 山東大學(xué)碩士學(xué)位論文 方法，使用三角面片作為中間幾何圖元的基本表達(dá)元素，較好地解決了在任意不 規(guī)則、非線性數(shù)據(jù)場(chǎng)中進(jìn)行等值面重建的問(wèn)題。 由于目前的顯卡都可以對(duì)三角面片進(jìn)行硬件加速的繪制，并且m c 方法本身原 理簡(jiǎn)單，容易實(shí)現(xiàn)，因此得到了廣泛的應(yīng)用，被認(rèn)為是目前最流行的面繪制算法， 對(duì)面繪制的研究產(chǎn)生了深遠(yuǎn)的影響。一直到現(xiàn)在為止在可視化領(lǐng)域的著名雜志和 會(huì)議上還經(jīng)常有針對(duì)m c 方法的改進(jìn)算法。然而，m c 方法也存在一定的不足之處。 首先，m c 算法不能保證生成曲面滿足c o 連續(xù)，即產(chǎn)生的逼近等值面片的拓?fù)浣Y(jié)構(gòu) 與采樣數(shù)據(jù)場(chǎng)的拓?fù)浣Y(jié)構(gòu)不一致【1 】；其次，m c 方法直接連接邊上插值得到的等 值點(diǎn)組成逼近等值面的多邊形，然后三角化得到等值面，當(dāng)要求的逼近精度較高 時(shí)，很難達(dá)到逼近精度的要求，對(duì)于采樣比較稀疏的數(shù)據(jù)場(chǎng)更是如此協(xié)刪；最 后，m c 算法用大量的三角片來(lái)逼近等值面，對(duì)這些三角片的頂點(diǎn)和項(xiàng)點(diǎn)連通關(guān)系 進(jìn)行編碼，需要非常大的存儲(chǔ)空間和傳輸帶寬，同時(shí)，生成和處理大量的三角片 往往會(huì)耗費(fèi)較多的執(zhí)行時(shí)間渺稍1 ，這限制了算法在交互應(yīng)用中的使用。 最初，眾多學(xué)者的注意力主要集中在面二義性問(wèn)題上，目的是提取正確的邊 界多邊形。然而，邊界多邊形是等值面與體元邊界的交點(diǎn)，不同的三線性插值曲 面與體元相交可產(chǎn)生相同或相似的邊界多邊形，從而導(dǎo)致體二義性的存在。1 9 9 4 年，bkn a t a r 面“1 9 】發(fā)現(xiàn)體二義性的存在，極大的促進(jìn)了m c 方法的研究和改進(jìn)， 許多學(xué)者開(kāi)始提出新的疑問(wèn)：除了bk n a t a 啊孤算法提出的體二義性外，是否還 有其他體元內(nèi)部存在“管”狀曲面? 如果存在，又如何判定“管”狀曲面的存在 和提取逼近等值面呢? 由此引起了廣泛關(guān)注，提出了許多對(duì)于m c 方法的改進(jìn) 【2 9 q 1 1 ，其中很多方法根據(jù)不同的數(shù)據(jù)特征，從一個(gè)角度來(lái)判定體二義性的存在， 因而沒(méi)有有效的保證等值面的拓?fù)湔_性和體元模型查找表的完整性。 其次，利用m c 算法求逼近等值面的過(guò)程中，使用線性插值計(jì)算出等值面與 立方體邊的交點(diǎn)之后，采用簡(jiǎn)單連接的方式，形成逼近等值面的邊界多邊形，然 后進(jìn)行三角化得到最終的逼近等值面片。當(dāng)對(duì)目標(biāo)數(shù)據(jù)場(chǎng)的采樣密度比較大，m c 算法中單位立方體大小相對(duì)顯示尺度來(lái)說(shuō)很小時(shí)，這種簡(jiǎn)單構(gòu)造三角片的方式已 經(jīng)足以滿足實(shí)際使用的精度要求。但如果要對(duì)局部數(shù)據(jù)放大觀察或者采樣數(shù)據(jù)本 身的分辨率很低，就需要對(duì)這種簡(jiǎn)單構(gòu)造方式進(jìn)行改進(jìn)，來(lái)達(dá)到較高的逼近精度 要求。 2 山東大學(xué)碩士學(xué)位論文 此外，m c 算法在數(shù)據(jù)場(chǎng)密度較高的情況下具有較好的繪制效果，但這時(shí)往往 生成大量的三角面片，需要較大的存儲(chǔ)空間和傳輸帶寬，并且過(guò)多三角面片需要 較長(zhǎng)的時(shí)間進(jìn)行處理，以至于無(wú)法進(jìn)行實(shí)時(shí)繪制。這些因素都使m c 算法的應(yīng)用 受到了限制。因此，需要改進(jìn)算法來(lái)減少對(duì)存儲(chǔ)空間的需要和對(duì)時(shí)間的耗費(fèi)。 一些文獻(xiàn)曾綜合討論過(guò)部分改進(jìn)算法，如舢l 、，肌g e l d e 2 i ，2 1 1 等對(duì)等值面抽 取過(guò)程中產(chǎn)生的拓?fù)浣Y(jié)構(gòu)問(wèn)題進(jìn)行研究，k b r o d h 【7 1 1 曾對(duì)體數(shù)據(jù)可視化的各種 方法進(jìn)行綜述，ph e c k b e n m l 對(duì)等值面逼近算法也進(jìn)行過(guò)討論，但這些文獻(xiàn)對(duì)于 改進(jìn)算法或者針對(duì)一個(gè)方面進(jìn)行研究，或者沒(méi)有很好的對(duì)各種改進(jìn)方法進(jìn)行分類(lèi) 對(duì)比，致使沒(méi)有形成完整地理論體系，阻礙了m c 和其改進(jìn)算法在具體的領(lǐng)域中進(jìn) 行應(yīng)用。 1 3 論文主要貢獻(xiàn)和章節(jié)安排 本文主要對(duì)等值面逼近算法m c 進(jìn)行綜合分類(lèi)研究，該方法是應(yīng)用最廣泛的面 繪制方法之一，其基本的實(shí)現(xiàn)方法是在等值面上提取有限個(gè)等值點(diǎn)并將其三角 化，以得到的三角片組合曲面作為逼近等值面，因而等值點(diǎn)的選擇和等值點(diǎn)的三 角化是該方法的關(guān)鍵環(huán)節(jié)，等值點(diǎn)的位置和三角化的方式?jīng)Q定著體元內(nèi)部逼近等 值面的拓?fù)浣Y(jié)構(gòu)和幾何形狀，逼近等值面片的表示精度以及生成面片的數(shù)量和處 理時(shí)間。雖然在m c 方法的不斷發(fā)展過(guò)程中，眾多學(xué)者對(duì)拓?fù)鋯?wèn)題，精度問(wèn)題和效 率優(yōu)化問(wèn)題進(jìn)行了研究，但卻缺乏全面的綜述討論，目前為止，沒(méi)有形成一種公 認(rèn)的行之有效的方法。 本文總結(jié)現(xiàn)有的針對(duì)各個(gè)領(lǐng)域的改進(jìn)方法，從拓?fù)涠x性，等值面表示精度 和算法效率三個(gè)方面進(jìn)行綜合討論分析，提出新的分類(lèi)方法。對(duì)每一個(gè)方面的改 進(jìn)方法按照其理論依據(jù)不同進(jìn)行分類(lèi)，理論依據(jù)相同的分類(lèi)按照發(fā)展歷程進(jìn)行討 論，對(duì)每類(lèi)改進(jìn)算法，文章對(duì)其實(shí)驗(yàn)結(jié)果進(jìn)行比較，然后分析對(duì)比，指出其優(yōu)點(diǎn) 和不足之處。對(duì)于拓?fù)涠x性的改進(jìn)方法，文章從面二義性和體二義性兩個(gè)角度 進(jìn)行分析，面二義性問(wèn)題的解決方法相對(duì)簡(jiǎn)單，使用漸近線方法可以很好的進(jìn)行 解決；體二義性問(wèn)題的解決相對(duì)復(fù)雜，文章通過(guò)分析三線性插值曲面的性質(zhì)，按 照解決方法的研究歷程，將解決體二義性的方法從四個(gè)方面進(jìn)行分析，由簡(jiǎn)單到 復(fù)雜，從最初提出的鞍點(diǎn)解決方法，到最終的臨界點(diǎn)和拓?fù)浣Y(jié)構(gòu)方法解決體二義 山東大學(xué)碩士學(xué)位論文 性，逐漸改進(jìn)了算法中存在的不足之處。關(guān)于如何提高逼近等值面表示精度，文 章分兩個(gè)類(lèi)別進(jìn)行討論，增加采樣內(nèi)部點(diǎn)是很直觀的方法，但單純依賴于增加采 樣點(diǎn)的方法顯然是不合理的，等值點(diǎn)數(shù)目越多，計(jì)算量和數(shù)據(jù)量也就越大，導(dǎo)致 產(chǎn)生大量的冗余數(shù)據(jù)；漸進(jìn)式網(wǎng)格方法是較好的處理方法，該方法在處理等值面 的過(guò)程中，不斷細(xì)化，直到滿足具體應(yīng)用的需求，在保證表示精度的同時(shí)，能有 效防止冗余數(shù)據(jù)的產(chǎn)生。文章對(duì)算法效率從時(shí)間耗費(fèi)和空間存儲(chǔ)效率兩個(gè)方面進(jìn) 行討論，具體分為三個(gè)方向：第一類(lèi)方法通過(guò)建立合適的數(shù)據(jù)結(jié)構(gòu)，跳過(guò)不存在 等值面的體元，有效的節(jié)省了生成等值面所需要的時(shí)間；第二類(lèi)方法旨在討論節(jié) 省存儲(chǔ)空間的幾種方法，主要是在保證逼近精度的情況下，通過(guò)合并相鄰的三角 面片進(jìn)行實(shí)現(xiàn)；文章重點(diǎn)討論了第三類(lèi)，即多分辨率方法，該方法兼顧算法時(shí)間 和空間兩個(gè)方面的耗費(fèi)，有效地解決了交互顯示等實(shí)際應(yīng)用問(wèn)題。 全文共分六章，第一章緒論介紹了科學(xué)計(jì)算可視化中的等值面抽取算法m c 的研究背景、研究現(xiàn)狀和重要意義；第二章闡述了m c 算法的原理，應(yīng)用領(lǐng)域，并 對(duì)算法本身存在的問(wèn)題進(jìn)行分析；第三章對(duì)m c 方法中存在的拓?fù)涠x性進(jìn)行研 究，首先介紹了算法中拓?fù)涠x性的存在，然后從面二義性和體二義性的解決兩 個(gè)方面，討論改進(jìn)算法的研究情況；第四章針對(duì)m c 算法在構(gòu)造等值面的過(guò)程中達(dá) 不到表示精度的問(wèn)題，綜合分析了現(xiàn)有的提高表示精度的方法：第五章提出了提 高m c 算法得時(shí)間和空間效率的方法。有些數(shù)據(jù)場(chǎng)，由于采樣密度過(guò)大，在等值面 逼近的過(guò)程中，形成大量的三角面片，從而需要大量的存儲(chǔ)空間和處理時(shí)間，無(wú) 法達(dá)到交互式應(yīng)用的要求，本章對(duì)算法在時(shí)間空問(wèn)效率以及其綜合應(yīng)用方面的改 進(jìn)進(jìn)行總結(jié)；第六章對(duì)全文工作進(jìn)行了回顧和總結(jié)，提出了m c 算法發(fā)展的趨勢(shì)， 并對(duì)未來(lái)發(fā)展進(jìn)行了展望。 4 山東大學(xué)碩士學(xué)位論文 第二章m a r c h i n gc u b 鶴算法概述 2 1m a r c h i n gc u b 鶴算法基本原理 m c 嘲方法以數(shù)據(jù)場(chǎng)中的相鄰兩層上的各四個(gè)像素為頂點(diǎn)組成的立方體為最 小的等值面搜索單元( 也稱(chēng)為體元) 。其基本思想是逐個(gè)處理數(shù)據(jù)場(chǎng)的體元，分 類(lèi)出與等值面相交的體元，采用線性插值計(jì)算出與等值面相交的體元的棱邊上的 交點(diǎn)，根據(jù)體元8 個(gè)頂點(diǎn)與等值面的相對(duì)位置，將這些交點(diǎn)按一定方式連接成等 值面，作為等值面在體元內(nèi)的逼近表示，所有體元中的等值面構(gòu)成整個(gè)數(shù)據(jù)場(chǎng)的 等值面。等值面中各三角片頂點(diǎn)處的法向量的計(jì)算，一般先采用中心差分計(jì)算出 體元頂點(diǎn)處的梯度，再用線性插值計(jì)算等值點(diǎn)處的梯度值作為該點(diǎn)的法向量。 m c 的基本假設(shè)是沿著體元的棱邊數(shù)據(jù)場(chǎng)呈線性變化。也就是說(shuō)，如果一條棱 邊的兩個(gè)頂點(diǎn)的數(shù)據(jù)場(chǎng)值分布大于和小于等值面的值，則該條邊上有且僅有一點(diǎn) 是等值面與該邊的交點(diǎn)。確定立方體體元內(nèi)部的等值面的分布是該算法的基礎(chǔ)。 算法可簡(jiǎn)單地分為三個(gè)主要步驟：1 ) 用線性插值計(jì)算體元邊與等值面的交點(diǎn)， 以下將這些等值點(diǎn)稱(chēng)為邊界等值點(diǎn)；2 ) 將交點(diǎn)按一定方式連接成等值面，通常 多采用三角片組合曲面來(lái)逼近等值面，這一過(guò)程稱(chēng)為三角化；3 ) 計(jì)算等值面中 各三角片頂點(diǎn)處的法向量，為后續(xù)的繪制提供依據(jù)。 計(jì)算等值點(diǎn)的過(guò)程比較簡(jiǎn)單，首先對(duì)體元的8 個(gè)頂點(diǎn)進(jìn)行分類(lèi)，以判定該頂 點(diǎn)是位于等值面內(nèi)還是等值面外。再根據(jù)8 個(gè)頂點(diǎn)的狀態(tài)，確定等值面在體元內(nèi) 部的連接方式。 假定等值面的值為c 0 。則頂點(diǎn)分類(lèi)規(guī)則為： ( 1 ) 如果體元頂點(diǎn)的數(shù)據(jù)場(chǎng)值c n ，則定義該頂點(diǎn)位于等值面之外，標(biāo)記 “+ ”號(hào)： 山東大學(xué)碩士學(xué)位論文 ( 2 ) 如果體元頂點(diǎn)的數(shù)據(jù)場(chǎng)值 c 0 ，則定義該頂點(diǎn)位于等值面之內(nèi)，標(biāo)記 “一”號(hào)。 圓 1 0l l 圈2 一l1 4 種基本體元狀態(tài)模型 每個(gè)體元有8 個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)只有兩種狀態(tài)，顯然共有2 8 - 2 5 6 種組合狀 態(tài)。l o r e n s e n 最早利用頂點(diǎn)狀態(tài)反轉(zhuǎn)和旋轉(zhuǎn)對(duì)稱(chēng)性將2 5 6 種組合狀態(tài)的所有可能 的情形總結(jié)為如圖2 1 所示的1 4 種基本模式。其中由邊界等值點(diǎn)構(gòu)成的多邊形 稱(chēng)為邊界多邊形。 需要說(shuō)明的是，在本文中我們對(duì)體元頂點(diǎn)和邊的標(biāo)注仍然沿用l o r e n s 鋤的表 示方式，如圖2 2 所示，v 1 v 8 分別表示體元的八個(gè)頂點(diǎn)，e 1 e 1 2 分別表示體元 的十二條邊。 v s e 7 v 7 v 圖2 2 體元頂點(diǎn)和邊的標(biāo)注 v 6 在實(shí)現(xiàn)時(shí)，可按照立方體項(xiàng)點(diǎn)狀態(tài)構(gòu)造等值面連接模式的索引表： 6 山東大學(xué)碩士學(xué)位論文 i i i d e x = 可直接由立方體各項(xiàng)點(diǎn)的狀態(tài)檢索出其中等值面的分布模式，確定該立方體 體元內(nèi)的等值面三角片連接方式。 為使重構(gòu)的曲面片之間具有拓?fù)湟恢滦裕此鼈兛梢詷?gòu)成連續(xù)的、無(wú)孔的、 無(wú)懸浮面的曲面( 數(shù)據(jù)場(chǎng)的邊界處除外) ，等值點(diǎn)的三角化過(guò)程應(yīng)遵循以下規(guī)則： ( 1 ) 體元內(nèi)曲面的各三角片之間滿足c o 連續(xù)；( 2 ) 體元內(nèi)曲面無(wú)自交現(xiàn)象；( 3 ) 不出現(xiàn)“邊界面三角片”( 屬于體元邊界面的一部分的三角片) ；( 4 ) 一條直線 段屬于且僅屬于兩個(gè)三角片( 邊界體元除外) 。 2 2m 矗r c h i n gc u b 囂算法的優(yōu)點(diǎn)和存在問(wèn)題 m a r c h i n gc u b e s 方法的提出提供了一種精確的定義體元以及體元內(nèi)等值面 的生成方法，體元定義為由相鄰層之間八個(gè)網(wǎng)格點(diǎn)組成的數(shù)據(jù)單元，它提供了一 種更一般化的體元定義，從造型的觀點(diǎn)看，所有三維標(biāo)量場(chǎng)都可以由這種一般意 義下的體元或單元組成，因而標(biāo)量場(chǎng)中的等值面的生成均可以分別在這些組成標(biāo) 量場(chǎng)的體元內(nèi)完成，這為散亂數(shù)據(jù)場(chǎng)和曲面分布數(shù)據(jù)場(chǎng)中等值面的構(gòu)造提供了非 常簡(jiǎn)單有效的方法。但算法在構(gòu)造等值面的過(guò)程中，太依賴于直觀的構(gòu)造，構(gòu)建 體元狀態(tài)模型的過(guò)程中，對(duì)于對(duì)稱(chēng)，旋轉(zhuǎn)等情況的處理缺乏全面考慮，忽視了立 方體內(nèi)部可能存在的環(huán)狀結(jié)構(gòu)和存在的臨界點(diǎn)( 等值面發(fā)生變化的點(diǎn)) ，直接使 用求得的邊界等值點(diǎn)，根據(jù)簡(jiǎn)單的體元狀態(tài)模型，簡(jiǎn)單連接成三角片，因此，存 在許多缺點(diǎn)。算法白面世之日起就受到極大的關(guān)注，該領(lǐng)域研究人員在應(yīng)用中不 斷地發(fā)現(xiàn)其中的問(wèn)題和不足之處并加以改進(jìn)。 最早d a r s t 例發(fā)現(xiàn)二義性的問(wèn)題。如果在體元的一個(gè)邊界面上，標(biāo)號(hào)為+ 和 標(biāo)號(hào)為一的角點(diǎn)分別位于對(duì)角線的兩端，則該表面上存在四個(gè)等值點(diǎn)，那么就會(huì) 有兩種可能的等值線的連接方式，如圖2 3 中a ) 和b ) 所示。如果二義性問(wèn)題不解 決，就會(huì)導(dǎo)致最后生成的等值面可能有“孔洞”存在，即不能保證曲面的封閉性， 從而將空間分為“內(nèi)”和“外”。為與下文的體二義性相區(qū)別，我們稱(chēng)這種二義 山東大學(xué)碩士學(xué)位論文 性為面二義性。 我們來(lái)觀察圖2 3 中的體元狀態(tài)模型可知，3 、6 中有一個(gè)面存在二義性，l o 中有兩個(gè)面存在二義性7 、1 2 中有三個(gè)面存在二義性，而1 3 中的六個(gè)面都存在 二義性。 圖2 3 二義性面上四個(gè)交點(diǎn)的相對(duì)位置 隨著m c 方法的廣泛應(yīng)用和對(duì)其研究的逐步深入，人們又發(fā)現(xiàn)了新的問(wèn)題， n a t a r a ja n 【1 川首先指出體二義性的存在。根據(jù)三維線性插值，即使體元的六個(gè)表 面都不存在二義性，體元內(nèi)部的等值面仍然不確定。如圖2 - 4 中的體元狀態(tài)模型 4 ，其內(nèi)部的等值面可能為兩片分離的面片，也可能為一“管”狀曲面，也就是 說(shuō)，m c 算法的體元模型查找表不完整，不能保證逼近等值面的拓?fù)湔_性。 畫(huà) 圖2 4 體二義性和“管”狀曲面 m c 算法在求逼近等值面的過(guò)程中，使用線性插值計(jì)算出等值面與立方體邊 的交點(diǎn)( 等值點(diǎn)) 之后，采用簡(jiǎn)單連接的方式，形成逼近等值面的邊界多邊形， 然后進(jìn)行三角化得到最終的逼近等值面片。當(dāng)對(duì)目標(biāo)數(shù)據(jù)場(chǎng)的采樣密度比較大， 立方體大小相對(duì)顯示尺度來(lái)說(shuō)很小時(shí)，這種簡(jiǎn)單構(gòu)造三角片的方式已經(jīng)足以滿足 實(shí)際使用的精度要求。但如果要對(duì)局部數(shù)據(jù)放大觀察或者采樣數(shù)據(jù)本身的分辨率 很低，這種簡(jiǎn)單連接方式構(gòu)造的逼近等值面分辨率較低，遠(yuǎn)遠(yuǎn)不能達(dá)到實(shí)用的要 山東大學(xué)碩士學(xué)位論文 求。 此外，m c 算法在數(shù)據(jù)場(chǎng)密度較高的情況下具有較好的繪制效果，但這時(shí)往 往生成過(guò)多的三角面片，存儲(chǔ)這些三角片頂點(diǎn)位置和法向量，需要較大的存儲(chǔ)空 間和傳輸帶寬，同時(shí)，計(jì)算大量三角面片的頂點(diǎn)位置和法向量，需要較長(zhǎng)的時(shí)間 進(jìn)行處理，以至于很難進(jìn)行實(shí)時(shí)繪制和交互式應(yīng)用，這些因素都使m c 算法的應(yīng) 用受到了限制。 9 山東大學(xué)碩士學(xué)位論文 第三章m a r c h i n gc u b 鶴拓?fù)涠x性解決辦法 3 1m a 佗h i n gc u b e s 面二義性問(wèn)題 第二章中提到，如果位于等值面內(nèi)和在等值面外的頂點(diǎn)分別分布在對(duì)角線的 兩端，就會(huì)有兩種連接方式，當(dāng)相鄰的兩個(gè)立方體在公共面上采取的連接方式不 相同時(shí)，就會(huì)出現(xiàn)面二義性，導(dǎo)致孔洞生成。隨著面二義性問(wèn)題的提出，也隨之 出現(xiàn)了眾多的解決方法”】，其中比較經(jīng)典的方法是n i e l s o n 提出的漸近線方 法( a s y m p t o t i cd e c i d e r ) 【1 刀和四面體剖分法方法( 移動(dòng)四面體法婦r c h i n g t e t r a l l e d r a ) 【1 0 ，l 。 3 1 1 基于四面體剖分解決面二義性 使用四面體方法解決二義性時(shí)，假設(shè)在四面體的邊上，數(shù)據(jù)場(chǎng)呈線性變化， 由于四面體的每個(gè)面是三角形，生成的等值面片的連接方式是唯一的，并且對(duì)于 每個(gè)四面體，等值面模式只有三種情況，如圖3 。如果頂點(diǎn)數(shù)據(jù)全大于或者全小 于等值面值，等值面與單元無(wú)交( 圖3 1 左) ，如果一個(gè)頂點(diǎn)大于另外三個(gè)頂點(diǎn) 小于等值面值，則四面體中的等值面是一個(gè)三角片( 圖3 一l 中) ，如果兩個(gè)頂點(diǎn) 大于兩個(gè)小于等值面值，則等值面是一個(gè)四邊形( 圖3 1 右) ，可以由兩個(gè)三角 形構(gòu)造。 圖3 1 四面體中的等值面 四面體剖分法將立方體剖分為5 個(gè)，6 個(gè)或2 4 個(gè)四面體。然而，5 個(gè)或6 個(gè) 四面體的剖分是一種不對(duì)稱(chēng)的剖分，剖分后形成的四面體不全等，無(wú)疑增加了處 理的復(fù)雜性。雖然2 4 個(gè)四面體的剖分是一種全等四面體的剖分，四面體的插值 計(jì)算比較簡(jiǎn)單，卻產(chǎn)生太多的三角片，并且在立方體內(nèi)的等值面沒(méi)有二義性時(shí)， 山東大學(xué)碩士學(xué)位論文 立方體也會(huì)被剖分處理，這都大大增加了算法的時(shí)間耗費(fèi)。面對(duì)龐大的數(shù)據(jù)，為 達(dá)到實(shí)時(shí)交互的要求，減少計(jì)算和存儲(chǔ)顯得尤為必要，尤其是近年來(lái)隨著成像設(shè) 備物理分辨率的不斷提高，對(duì)可視化運(yùn)算速度提出更高的要求。另外，對(duì)于一個(gè) 立方體來(lái)說(shuō)，四面體剖分方法中等值面的構(gòu)造跟剖分方式有關(guān)，不同的四面體剖 分方式將導(dǎo)致不同的等值面例，如圖3 2 所示。這樣一來(lái)，整個(gè)數(shù)據(jù)場(chǎng)內(nèi)等值面 的構(gòu)造與最初一個(gè)體元的剖分方式有關(guān)，導(dǎo)致形成的逼近等值面可能和真實(shí)等值 面有不同的拓?fù)浣Y(jié)構(gòu)。因而，用四面體剖分法來(lái)解決二義性問(wèn)題很難達(dá)到理想的 結(jié)果。 圖3 2 四面體不同剖分方式形成不同的等值面 3 1 2 基于漸近線方法解決面二義性 漸近線方法是應(yīng)用最為廣泛的判定面二義性的方法?；驹硎牵寒?dāng)出現(xiàn) 面二義性時(shí)，雙曲線的兩支將所在平面分成三個(gè)區(qū)域，雙曲線漸近線的交點(diǎn)總是 和其中一對(duì)交點(diǎn)落在同一區(qū)域，具體為如果漸近線交點(diǎn)的標(biāo)量值大于等值面的標(biāo) 量值，則標(biāo)量值大于等值面標(biāo)量值的對(duì)頂點(diǎn)跟交點(diǎn)落在同一區(qū)域，反之，另一 對(duì)頂點(diǎn)與漸近線交點(diǎn)落在同一區(qū)域，這是漸近線方法判定面二義性的基礎(chǔ)。 根據(jù)漸近線方法，位于體元某一表面的等值線是一對(duì)漸近線分別與體元邊相 平行的雙曲線，雙曲線與體元表面可能交于0 、1 、2 、3 、4 個(gè)交點(diǎn)，如圖3 - 3 所 示。其中( a ) 、( b ) 和( e ) 三種均為退化情形，為處理簡(jiǎn)單，我們將( a ) 歸并為( c ) ， ( b ) ( e ) 歸并為( f ) 。只考慮雙曲線與體元表面存在o 、2 和4 個(gè)交點(diǎn)的情形，即 山東大學(xué)碩士學(xué)位論文 圖中( c ) 、( d ) 和( f ) 所示的情形。 廠人 _ j 、 ( a ) h i l l 劃 ( d ) 廠天 弋 j ( b ) 廠太 弋 j ( e ) 廠 、一 _ j ( c ) 7 ( 1 圖3 3 等值面與體元某一表面的相交情況示意圖 模式0 ，1 ，2 ，4 ，5 ，8 ，9 和1 1 的等值面是確定的，而根據(jù)方法其它體元 內(nèi)部等值面則為如圖3 4 所示。 圖3 4 漸近線方法判定面二義性的結(jié)果 采用漸近線方法可正確解決二義性面的連接問(wèn)題，并且不會(huì)產(chǎn)生太多的 三角片，因而是解決面二義性的一種較好的方法。 山東大學(xué)碩士學(xué)位論文 3 2 m a r c h i n gc u b 鸛體二義性問(wèn)題 n i e l s o n 【”，1 6 1 刀等雖然對(duì)立方體面上存在的二義性進(jìn)行分析，但對(duì)三線性插 值函數(shù)在立方體內(nèi)部的形狀沒(méi)有給與足夠的重視。n a t a r a j a n 【1 9 】對(duì)等值面在立方 體內(nèi)部的具體形狀進(jìn)行詳細(xì)研究，進(jìn)一步發(fā)現(xiàn)即使體元中不存在二義性面，體元 內(nèi)部也可能存在不同拓?fù)浣Y(jié)構(gòu)的等值面，指出了體二義性存在的可能性，并提供 了最初的解決辦法。隨后，通過(guò)對(duì)三線性插值等值面拓?fù)浣Y(jié)構(gòu)的深入研究，許多 體內(nèi)拓?fù)涠x性的解決辦法也相繼被提出。如圖3 5 中的體元狀態(tài)模型4 ，其內(nèi) 部的等值面可能為兩片分離的面片，也可能為一“管”狀曲面。 畫(huà) 圖3 5 體二義性和“管”狀曲面 bkn a t a r a j a n 的發(fā)現(xiàn)，極大的促進(jìn)了m a r c h i n gc u b e 方法的研究和改進(jìn)， 許多學(xué)者開(kāi)始提出新的疑問(wèn)：除了模式4 外，是否還有其他體元內(nèi)部存在“管” 狀瞳面? 如果存在，又如何判定“管”狀曲面的存在和提取逼近等值面呢? 由此 引起了眾多學(xué)者的關(guān)注，提出了許多對(duì)于m c 方法的改進(jìn)。 3 2 1 利用鞍點(diǎn)解決體二義性 t a r a j a n 為有效的利用m c 算法抽取拓?fù)浣Y(jié)構(gòu)正確的等值面，提出逼近等 值面片需要滿足的三個(gè)條件：一是所得逼近等值面片須是原來(lái)等值面的幾何逼 近，即在一定誤差范圍內(nèi)與原等值面相同；二是要達(dá)到拓?fù)湟恢滦?，也就是在體 元中的任意兩點(diǎn)，對(duì)于逼近的等值面片和等值面，具有相同的位置關(guān)系；三是構(gòu) 造逼近等值面片的復(fù)雜度不能太高。在文章中n a t a r a j a n 引入了面鞍點(diǎn)和體鞍點(diǎn) 的概念，并利用這兩類(lèi)鞍點(diǎn)來(lái)解決滿足以上三個(gè)條件的可視化問(wèn)題。其中面鞍點(diǎn) 為漸近線方法中漸近線的交點(diǎn)，體鞍點(diǎn)為在三維空間中面鞍點(diǎn)的擴(kuò)展。即根據(jù)數(shù) 據(jù)在體元面上是雙線性變化的，可以得到在該面上的雙線性函數(shù)，對(duì)其兩個(gè)分量 山東大學(xué)碩士學(xué)位論文 分別求偏導(dǎo)，可以得到面鞍點(diǎn)，同理，對(duì)均勻采樣的數(shù)據(jù)場(chǎng)進(jìn)行三線性插值得到 的三線性函數(shù)，通過(guò)求該函數(shù)在三個(gè)方向上的偏導(dǎo)數(shù)可以得到體鞍點(diǎn)。 得到面鞍點(diǎn)和體鞍點(diǎn)后，根據(jù)以下規(guī)則來(lái)解決二義性：如果面上的一對(duì)對(duì)角 線頂點(diǎn)與面鞍點(diǎn)有相同的符號(hào)( 同時(shí)大于或者同時(shí)小于等值面值) ，則這一對(duì)頂點(diǎn) 在同一個(gè)區(qū)域內(nèi)，否則另外一對(duì)定點(diǎn)在同一區(qū)域；如果體對(duì)角線的一對(duì)頂點(diǎn)與體 鞍點(diǎn)有相同的符號(hào)，則連通這一對(duì)頂點(diǎn)，構(gòu)成一個(gè)管狀曲面，否則不連通這對(duì)頂 點(diǎn)，形成兩個(gè)分離的三角片。 v a ng e l d e r 和w i l h e l m s 2 1 1 研究發(fā)現(xiàn)，為保證多邊形逼近等值面c 0 連續(xù)，體 數(shù)據(jù)內(nèi)部的逼近多邊形的邊只能由兩個(gè)多邊形共享，體數(shù)據(jù)邊緣的邊只能出現(xiàn)在 一個(gè)逼近多邊形中。并進(jìn)一步指出，如果三角片位于立方體的面上，在該立方體 中就會(huì)有兩個(gè)三角形共享同一條邊，同時(shí)，在相鄰的立方體中也會(huì)有至少一個(gè)三 角形共享這條邊，這將導(dǎo)致生成的三角片逼近曲面不連續(xù)。雖然n a t a r a j a n 解決 了立方體中存在的拓?fù)涠x性，但由于算法中沒(méi)有解決三角片落在立方體面上的 問(wèn)題，因而不能保證生成c 0 連續(xù)的三角曲面片，同時(shí)，n a t a r a j a n 也沒(méi)有明確提 出對(duì)曲面如何進(jìn)行三角化。c i g l l o n i 鯽以n a t a r a j a n 的研究為基礎(chǔ)，對(duì)m c 進(jìn)行了進(jìn) 一步的研究，基于面鞍點(diǎn)和體鞍點(diǎn)對(duì)m c 的基本體元狀態(tài)進(jìn)行進(jìn)一步分類(lèi)，構(gòu)造了 擴(kuò)展查找表，對(duì)各種情況都給出了三角化方法，新建的擴(kuò)展查找表總共7 9 8 種情 況，進(jìn)行旋轉(zhuǎn)，映射等操作后，最終得到具有8 8 種情況且各不相同的分類(lèi)查找 表。對(duì)于逼近等值面存在不連續(xù)性的問(wèn)題，特別是當(dāng)有三角片在立方體面上存在 時(shí)，算法通過(guò)對(duì)立方體對(duì)角線頂點(diǎn)插值的方法，來(lái)加入一個(gè)體對(duì)角線上的點(diǎn)，有 效解決了不連續(xù)的問(wèn)題。但由于數(shù)據(jù)場(chǎng)在體對(duì)角線上是三線性變化的，因此，引 入的內(nèi)部點(diǎn)可能不在原等值面上。此外，對(duì)于圖3 噸中的體元模型1 3 4 中存在 單個(gè)復(fù)雜曲面片的情況和1 3 5 1 中存在兩個(gè)體鞍點(diǎn)的情況，算法都沒(méi)有很好的 加以解決。 3 2 2 推廣漸近線方法解決體二義性 c h e n l y a e v 口5 1 利用漸近線方法解決面上的二義性，對(duì)拓?fù)涠x性，提出兩 種新方法來(lái)加以解決。第一種方法以下面的結(jié)論為基礎(chǔ)：在立方體上的一個(gè)三線 性插值函數(shù)在一條平行于邊的直線上是線性變化的。算法通過(guò)比較有拓?fù)涠x性 1 4 山東大學(xué)碩士學(xué)位論文 的立方體相對(duì)的平面上的漸近線來(lái)消除二義性。如圖3 5 ，如果兩個(gè)符號(hào)相同的 點(diǎn)在立方體內(nèi)部是連通的，那么其一個(gè)面上的漸近線投影到其相對(duì)的另一個(gè)面上 時(shí)，兩段漸近線必然相交，反之，如果兩段漸近線的投影不相交，那么這兩個(gè)頂 點(diǎn)是分離的。 圖3 6 體元模型4 的兩種情況 第二種方法基于在平行于立方體面的任意平面上，三線性函數(shù)都是雙線性變 化的。在立方體中如果有兩個(gè)頂點(diǎn)是在內(nèi)部連通，但在面上不是連通的，如圖 3 7 中的a 。，c 1 ，那么必然存在一個(gè)平行于立方體面的平面，平面與立方體的 交點(diǎn)形成的面是一個(gè)二義性面，在該二義性面中，符號(hào)與立方體中連通的頂點(diǎn)的 符號(hào)相同的兩個(gè)頂點(diǎn)連通( 圖3 7a t ，c t ) 。 c l c t c o l a t c t - b j ) t 怠。j ? ，t 。r 圖3 7 拋物線方法解決體內(nèi)二義性 如果a t ，c t 是連通的，根據(jù)漸近線條件，可得，a l c t b t d p o 。由于數(shù) 據(jù)在立方體的邊上呈線性變化，可以用a 。，馬，c ，d 。和，b o ，c 。，d o 的 線性組合表示a t ，b t ，c t ，d t ，然后代入并驗(yàn)證不等式是否滿足，如果滿足， 則對(duì)應(yīng)的頂點(diǎn)a 。，c ，在立方體內(nèi)部是連通的，否則，a 。，c 。是不連通的， 山東大學(xué)碩士學(xué)位論文 從而有效地將拓?fù)涠x性去除。 畫(huà)畫(huà) 國(guó)畫(huà)圓圓 畫(huà)回國(guó)廚圓 圓靜畫(huà)固器 圓圓留 圓 回國(guó) 圖3 8 細(xì)分m c 體元狀態(tài)模型 c h e r n y a e v 對(duì)m c 算法的1 5 種基本情況，首先根據(jù)是否含有二義性面進(jìn)行細(xì) 分，對(duì)于細(xì)分的這些情況中存在內(nèi)部拓?fù)涠x性的情況，進(jìn)一步加以細(xì)分。最后 明確給出了有3 3 種情況的拓?fù)浞诸?lèi)情況如圖3 8 和對(duì)應(yīng)的三角化方法。對(duì)于立 方體內(nèi)部需要加入頂點(diǎn)的情況，算法選擇其他頂點(diǎn)的平均值作為新加入的點(diǎn)，這 種方法選擇的點(diǎn)不一定位于等值面上，同時(shí)，算法也沒(méi)有解決三角片位于立方體 面上從而導(dǎo)致生成逼近