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

山東大學(xué)碩士學(xué)位論文 摘要 等值面技術(shù)在可視化中應(yīng)用廣泛，許多標(biāo)量場中的可視化問題都?xì)w納為等值 面的抽取和繪制，m 缸c l l i n gc i l b 囂方法是目前應(yīng)用最為廣泛的等值面抽取方法之 一。自1 9 8 7 年l o 枷s 等提出該算法以來，就因為其簡單高效取得了眾多研究 人員的關(guān)注，被廣泛的應(yīng)用于醫(yī)學(xué)圖像重構(gòu)，有限元分析，隱式曲面繪制等領(lǐng)域 的研究中，取得了許多重要的成果。但算法也存在一些不足之處。在目前為之， 已經(jīng)有大量的研究工作對m a r c h i n gc u b e s 算法本身進(jìn)行了有效的探討，來對該 算法進(jìn)行完善和提高它的運算效率。本文按照改進(jìn)算法對m a r c h i n gc u b 囂的具 體領(lǐng)域的改進(jìn)，提出歸類方法并進(jìn)行比較討論，為在具體的領(lǐng)域中應(yīng)用和進(jìn)一步 研究改進(jìn)算法，有著很好的借鑒意義。 本文首先介紹了算法的研究背景和意義，以及該領(lǐng)域相關(guān)的工作和研究現(xiàn) 狀，然后闡述了算法的基本原理，討論了其優(yōu)缺點和產(chǎn)生這些優(yōu)缺點的原因。算 法在構(gòu)造等值面的過程中，太依賴于直觀的構(gòu)造，構(gòu)建體元狀態(tài)模型時，對于對 稱，旋轉(zhuǎn)等情況的處理缺乏全面考慮，忽視了立方體內(nèi)部可能存在的環(huán)狀結(jié)構(gòu)和 存在的臨界點( 等值面發(fā)生變化的點) ，直接使用求得的邊界等值點，根據(jù)基本 的體元狀態(tài)模型，簡單連接成三角片構(gòu)成等值面，導(dǎo)致生成的等值面有在拓?fù)浣Y(jié) 構(gòu)，表示精度和效率方面，不能滿足實際應(yīng)用中的需求。 文章對算法構(gòu)造的等值面在拓?fù)浣Y(jié)構(gòu)方面存在的二義性分面上的二義性和 體上的二義性兩個方面進(jìn)行討論。首先分析了立方體面上存在二義性的原因，給 出了解決面上二義性的辦法；隨后，通過分析插值曲面在體元內(nèi)部可能存在的結(jié) 構(gòu)，引出體二義性，并且根據(jù)解決體二義性方法的不同原理，分四個類別對解決 方法進(jìn)行討論，根據(jù)三線性插值函數(shù)等值面的特性和不同體元模型的實驗結(jié)果， 指出了每一類算法存在的問題和優(yōu)勢所在。 由于m 盯c h i n gc u b 髂算法求逼近等值面的過程中，使用線性插值計算出等值 面與立方體邊的交點之后，采用簡單連接的方式，形成逼近等值面的邊界多邊形， 然后進(jìn)行三角化得到最終的逼近等值面片，所以當(dāng)算法針對采樣稀疏的數(shù)據(jù)場構(gòu) 造等值面時，會出現(xiàn)等值面精度不高的問題，無法保證所形成的等值面的表示精 度。增加采樣點無疑是提高表示精度的直接方法，但是隨著采樣點的加入，形成 山東大學(xué)碩士學(xué)位論文 三角片的增加，所需要的存儲空間和處理時間往往超出系統(tǒng)的負(fù)荷和實時應(yīng)用的 要求：另一種方法是漸進(jìn)式網(wǎng)格抽取算法，算法通過逐漸細(xì)化的方法，逐步提高 表示精度，直到達(dá)到應(yīng)用要求為止，這種方法可以在增加計算量不大的情況下提 高精度。 m a r c h i n gc u b e s 算法對每一個立方體單元進(jìn)行處理，耗費大量的時間，同時， 在采樣密度較高的數(shù)據(jù)場中，也往往生成過多三角面片，導(dǎo)致算法效率大大降低。 本文對這種情況進(jìn)行分析，總結(jié)了提高算法效率的主要方法。然后將這些方法分 成三類：第一類方法通過建立合適的數(shù)據(jù)結(jié)構(gòu)，跳過不存在等值面的體元，有效 的節(jié)省了生成等值面所需要的時間；第二類方法旨在討論節(jié)省存儲空間的幾種方 法，主要是在保證逼近精度的情況下，通過合并相鄰的三角面片進(jìn)行實現(xiàn)；文章 重點討論了第三類，即多分辨率方法，該方法兼顧算法時間和空間兩個方面的耗 費，有效地解決了交互顯示等實際應(yīng)用問題。 。 文章最后對m a r c h i n gc u b 豁改進(jìn)算法進(jìn)行總結(jié)，并展望了算法今后的發(fā)展方 向，對實踐中具體應(yīng)用算法和對其進(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)的說明 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨 立進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不 包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研 究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本聲明 的法律責(zé)任由本人承擔(dān)。 論文作者簽名：雌日期：2 羋 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解山東大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保 留或向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱；本人授權(quán)山東大學(xué)可以將本學(xué)位論文的全部或部分 內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或其他復(fù)制手 段保存論文和匯編本學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 啤一名：僻 山東大學(xué)碩士學(xué)位論文 1 1 研究背景和意義 第一章緒論 面繪制是科學(xué)計算可視化方法中常用的一種方法，它從原始的三維數(shù)據(jù)中重 建出中間的幾何圖元( 一般是以三角面片或者體元組成的曲面) ，然后使用真實感 圖形學(xué)技術(shù)對幾何圖元進(jìn)行光照計算和繪制【1 捌。面繪制技術(shù)的基本原理是，首 先對整個數(shù)據(jù)進(jìn)行等值表面分割和定義，用各種幾何元擬合表面，然后繪制出所 有的幾何元【3 】。在可視化中常用的幾何元有體元級大小的平面多邊形、多邊形網(wǎng) 格、三角片等。實際上，從數(shù)據(jù)場中構(gòu)造的表面就是提取的某一閾值的逼近等值 面。許多標(biāo)量場中的可視化問題都?xì)w納為等值面的抽取和繪制，如醫(yī)學(xué)圖像中的 三維重建；有限元計算中的標(biāo)量場分析，分子化學(xué)中的分子表面顯示；地質(zhì)中礦 藏分布的構(gòu)造等等。在散亂點的雎面重建h 5 】和關(guān)鍵幀動畫1 6 刀中，也常常提取零 等值面作為散亂點數(shù)據(jù)的重建曲面和中間幀。近年來，等值面逼近問題得到了極 為廣泛的關(guān)注，并取得了許多重要的成果。m a r c h i n gc u b e s 方法以其簡單和高效 的特點，成為應(yīng)用最廣泛的等值面逼近方法。 隨著成像設(shè)備的不斷更新及其性能的提高，斷層掃描序列圖像的層內(nèi)與層間 分辨率較以前有顯著提高，使得能夠在二維水平上更加清楚、直觀地看到物體結(jié) 構(gòu)的細(xì)微特征，從而獲得越來越詳實的信息。然而，這些二維影像數(shù)據(jù)只是表達(dá) 某一截面的信息，研究人員只能通過二維圖像進(jìn)行觀察，所得到的結(jié)果往往帶有 研究人員的主觀判斷和研究經(jīng)驗。地r c h i n gc u b e s 算法的不斷完善和發(fā)展，使 得提供直觀、逼真而且能夠包含原始信息中隱含的豐富內(nèi)容的三維信息成為可 能。通過圖形圖像技術(shù)，可以對影像進(jìn)行任意放大、縮小、旋轉(zhuǎn)、對比調(diào)整、三 維重建等處理，得到便于研究者從多角度、多層次進(jìn)行觀察的三維模型。這對分 析結(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 ( 以下將 其稱為m c ) 是基于體元的一種典型的面繪制方法。m c 算法作為一種構(gòu)造等值面的 山東大學(xué)碩士學(xué)位論文 方法，使用三角面片作為中間幾何圖元的基本表達(dá)元素，較好地解決了在任意不 規(guī)則、非線性數(shù)據(jù)場中進(jìn)行等值面重建的問題。 由于目前的顯卡都可以對三角面片進(jìn)行硬件加速的繪制，并且m c 方法本身原 理簡單，容易實現(xiàn)，因此得到了廣泛的應(yīng)用，被認(rèn)為是目前最流行的面繪制算法， 對面繪制的研究產(chǎn)生了深遠(yuǎn)的影響。一直到現(xiàn)在為止在可視化領(lǐng)域的著名雜志和 會議上還經(jīng)常有針對m c 方法的改進(jìn)算法。然而，m c 方法也存在一定的不足之處。 首先，m c 算法不能保證生成曲面滿足c o 連續(xù)，即產(chǎn)生的逼近等值面片的拓?fù)浣Y(jié)構(gòu) 與采樣數(shù)據(jù)場的拓?fù)浣Y(jié)構(gòu)不一致【1 】；其次，m c 方法直接連接邊上插值得到的等 值點組成逼近等值面的多邊形，然后三角化得到等值面，當(dāng)要求的逼近精度較高 時，很難達(dá)到逼近精度的要求，對于采樣比較稀疏的數(shù)據(jù)場更是如此協(xié)刪；最 后，m c 算法用大量的三角片來逼近等值面，對這些三角片的頂點和項點連通關(guān)系 進(jìn)行編碼，需要非常大的存儲空間和傳輸帶寬，同時，生成和處理大量的三角片 往往會耗費較多的執(zhí)行時間渺稍1 ，這限制了算法在交互應(yīng)用中的使用。 最初，眾多學(xué)者的注意力主要集中在面二義性問題上，目的是提取正確的邊 界多邊形。然而，邊界多邊形是等值面與體元邊界的交點，不同的三線性插值曲 面與體元相交可產(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é)者開始提出新的疑問：除了bk n a t a 啊孤算法提出的體二義性外，是否還 有其他體元內(nèi)部存在“管”狀曲面? 如果存在，又如何判定“管”狀曲面的存在 和提取逼近等值面呢? 由此引起了廣泛關(guān)注，提出了許多對于m c 方法的改進(jìn) 【2 9 q 1 1 ，其中很多方法根據(jù)不同的數(shù)據(jù)特征，從一個角度來判定體二義性的存在， 因而沒有有效的保證等值面的拓?fù)湔_性和體元模型查找表的完整性。 其次，利用m c 算法求逼近等值面的過程中，使用線性插值計算出等值面與 立方體邊的交點之后，采用簡單連接的方式，形成逼近等值面的邊界多邊形，然 后進(jìn)行三角化得到最終的逼近等值面片。當(dāng)對目標(biāo)數(shù)據(jù)場的采樣密度比較大，m c 算法中單位立方體大小相對顯示尺度來說很小時，這種簡單構(gòu)造三角片的方式已 經(jīng)足以滿足實際使用的精度要求。但如果要對局部數(shù)據(jù)放大觀察或者采樣數(shù)據(jù)本 身的分辨率很低，就需要對這種簡單構(gòu)造方式進(jìn)行改進(jìn)，來達(dá)到較高的逼近精度 要求。 2 山東大學(xué)碩士學(xué)位論文 此外，m c 算法在數(shù)據(jù)場密度較高的情況下具有較好的繪制效果，但這時往往 生成大量的三角面片，需要較大的存儲空間和傳輸帶寬，并且過多三角面片需要 較長的時間進(jìn)行處理，以至于無法進(jìn)行實時繪制。這些因素都使m c 算法的應(yīng)用 受到了限制。因此，需要改進(jìn)算法來減少對存儲空間的需要和對時間的耗費。 一些文獻(xiàn)曾綜合討論過部分改進(jìn)算法，如舢l 、，肌g e l d e 2 i ，2 1 1 等對等值面抽 取過程中產(chǎn)生的拓?fù)浣Y(jié)構(gòu)問題進(jìn)行研究，k b r o d h 【7 1 1 曾對體數(shù)據(jù)可視化的各種 方法進(jìn)行綜述，ph e c k b e n m l 對等值面逼近算法也進(jìn)行過討論，但這些文獻(xiàn)對于 改進(jìn)算法或者針對一個方面進(jìn)行研究，或者沒有很好的對各種改進(jìn)方法進(jìn)行分類 對比，致使沒有形成完整地理論體系，阻礙了m c 和其改進(jìn)算法在具體的領(lǐng)域中進(jìn) 行應(yīng)用。 1 3 論文主要貢獻(xiàn)和章節(jié)安排 本文主要對等值面逼近算法m c 進(jìn)行綜合分類研究，該方法是應(yīng)用最廣泛的面 繪制方法之一，其基本的實現(xiàn)方法是在等值面上提取有限個等值點并將其三角 化，以得到的三角片組合曲面作為逼近等值面，因而等值點的選擇和等值點的三 角化是該方法的關(guān)鍵環(huán)節(jié)，等值點的位置和三角化的方式?jīng)Q定著體元內(nèi)部逼近等 值面的拓?fù)浣Y(jié)構(gòu)和幾何形狀，逼近等值面片的表示精度以及生成面片的數(shù)量和處 理時間。雖然在m c 方法的不斷發(fā)展過程中，眾多學(xué)者對拓?fù)鋯栴}，精度問題和效 率優(yōu)化問題進(jìn)行了研究，但卻缺乏全面的綜述討論，目前為止，沒有形成一種公 認(rèn)的行之有效的方法。 本文總結(jié)現(xiàn)有的針對各個領(lǐng)域的改進(jìn)方法，從拓?fù)涠x性，等值面表示精度 和算法效率三個方面進(jìn)行綜合討論分析，提出新的分類方法。對每一個方面的改 進(jìn)方法按照其理論依據(jù)不同進(jìn)行分類，理論依據(jù)相同的分類按照發(fā)展歷程進(jìn)行討 論，對每類改進(jìn)算法，文章對其實驗結(jié)果進(jìn)行比較，然后分析對比，指出其優(yōu)點 和不足之處。對于拓?fù)涠x性的改進(jìn)方法，文章從面二義性和體二義性兩個角度 進(jìn)行分析，面二義性問題的解決方法相對簡單，使用漸近線方法可以很好的進(jìn)行 解決；體二義性問題的解決相對復(fù)雜，文章通過分析三線性插值曲面的性質(zhì)，按 照解決方法的研究歷程，將解決體二義性的方法從四個方面進(jìn)行分析，由簡單到 復(fù)雜，從最初提出的鞍點解決方法，到最終的臨界點和拓?fù)浣Y(jié)構(gòu)方法解決體二義 山東大學(xué)碩士學(xué)位論文 性，逐漸改進(jìn)了算法中存在的不足之處。關(guān)于如何提高逼近等值面表示精度，文 章分兩個類別進(jìn)行討論，增加采樣內(nèi)部點是很直觀的方法，但單純依賴于增加采 樣點的方法顯然是不合理的，等值點數(shù)目越多，計算量和數(shù)據(jù)量也就越大，導(dǎo)致 產(chǎn)生大量的冗余數(shù)據(jù)；漸進(jìn)式網(wǎng)格方法是較好的處理方法，該方法在處理等值面 的過程中，不斷細(xì)化，直到滿足具體應(yīng)用的需求，在保證表示精度的同時，能有 效防止冗余數(shù)據(jù)的產(chǎn)生。文章對算法效率從時間耗費和空間存儲效率兩個方面進(jìn) 行討論，具體分為三個方向：第一類方法通過建立合適的數(shù)據(jù)結(jié)構(gòu)，跳過不存在 等值面的體元，有效的節(jié)省了生成等值面所需要的時間；第二類方法旨在討論節(jié) 省存儲空間的幾種方法，主要是在保證逼近精度的情況下，通過合并相鄰的三角 面片進(jìn)行實現(xiàn)；文章重點討論了第三類，即多分辨率方法，該方法兼顧算法時間 和空間兩個方面的耗費，有效地解決了交互顯示等實際應(yīng)用問題。 全文共分六章，第一章緒論介紹了科學(xué)計算可視化中的等值面抽取算法m c 的研究背景、研究現(xiàn)狀和重要意義；第二章闡述了m c 算法的原理，應(yīng)用領(lǐng)域，并 對算法本身存在的問題進(jìn)行分析；第三章對m c 方法中存在的拓?fù)涠x性進(jìn)行研 究，首先介紹了算法中拓?fù)涠x性的存在，然后從面二義性和體二義性的解決兩 個方面，討論改進(jìn)算法的研究情況；第四章針對m c 算法在構(gòu)造等值面的過程中達(dá) 不到表示精度的問題，綜合分析了現(xiàn)有的提高表示精度的方法：第五章提出了提 高m c 算法得時間和空間效率的方法。有些數(shù)據(jù)場，由于采樣密度過大，在等值面 逼近的過程中，形成大量的三角面片，從而需要大量的存儲空間和處理時間，無 法達(dá)到交互式應(yīng)用的要求，本章對算法在時間空問效率以及其綜合應(yīng)用方面的改 進(jìn)進(jìn)行總結(jié)；第六章對全文工作進(jìn)行了回顧和總結(jié)，提出了m c 算法發(fā)展的趨勢， 并對未來發(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ù)場中的相鄰兩層上的各四個像素為頂點組成的立方體為最 小的等值面搜索單元( 也稱為體元) 。其基本思想是逐個處理數(shù)據(jù)場的體元，分 類出與等值面相交的體元，采用線性插值計算出與等值面相交的體元的棱邊上的 交點，根據(jù)體元8 個頂點與等值面的相對位置，將這些交點按一定方式連接成等 值面，作為等值面在體元內(nèi)的逼近表示，所有體元中的等值面構(gòu)成整個數(shù)據(jù)場的 等值面。等值面中各三角片頂點處的法向量的計算，一般先采用中心差分計算出 體元頂點處的梯度，再用線性插值計算等值點處的梯度值作為該點的法向量。 m c 的基本假設(shè)是沿著體元的棱邊數(shù)據(jù)場呈線性變化。也就是說，如果一條棱 邊的兩個頂點的數(shù)據(jù)場值分布大于和小于等值面的值，則該條邊上有且僅有一點 是等值面與該邊的交點。確定立方體體元內(nèi)部的等值面的分布是該算法的基礎(chǔ)。 算法可簡單地分為三個主要步驟：1 ) 用線性插值計算體元邊與等值面的交點， 以下將這些等值點稱為邊界等值點；2 ) 將交點按一定方式連接成等值面，通常 多采用三角片組合曲面來逼近等值面，這一過程稱為三角化；3 ) 計算等值面中 各三角片頂點處的法向量，為后續(xù)的繪制提供依據(jù)。 計算等值點的過程比較簡單，首先對體元的8 個頂點進(jìn)行分類，以判定該頂 點是位于等值面內(nèi)還是等值面外。再根據(jù)8 個頂點的狀態(tài)，確定等值面在體元內(nèi) 部的連接方式。 假定等值面的值為c 0 。則頂點分類規(guī)則為： ( 1 ) 如果體元頂點的數(shù)據(jù)場值c n ，則定義該頂點位于等值面之外，標(biāo)記 “+ ”號： 山東大學(xué)碩士學(xué)位論文 ( 2 ) 如果體元頂點的數(shù)據(jù)場值 c 0 ，則定義該頂點位于等值面之內(nèi)，標(biāo)記 “一”號。 圓 1 0l l 圈2 一l1 4 種基本體元狀態(tài)模型 每個體元有8 個頂點，每個頂點只有兩種狀態(tài)，顯然共有2 8 - 2 5 6 種組合狀 態(tài)。l o r e n s e n 最早利用頂點狀態(tài)反轉(zhuǎn)和旋轉(zhuǎn)對稱性將2 5 6 種組合狀態(tài)的所有可能 的情形總結(jié)為如圖2 1 所示的1 4 種基本模式。其中由邊界等值點構(gòu)成的多邊形 稱為邊界多邊形。 需要說明的是，在本文中我們對體元頂點和邊的標(biāo)注仍然沿用l o r e n s 鋤的表 示方式，如圖2 2 所示，v 1 v 8 分別表示體元的八個頂點，e 1 e 1 2 分別表示體元 的十二條邊。 v s e 7 v 7 v 圖2 2 體元頂點和邊的標(biāo)注 v 6 在實現(xiàn)時，可按照立方體項點狀態(tài)構(gòu)造等值面連接模式的索引表： 6 山東大學(xué)碩士學(xué)位論文 i i i d e x = 可直接由立方體各項點的狀態(tài)檢索出其中等值面的分布模式，確定該立方體 體元內(nèi)的等值面三角片連接方式。 為使重構(gòu)的曲面片之間具有拓?fù)湟恢滦裕此鼈兛梢詷?gòu)成連續(xù)的、無孔的、 無懸浮面的曲面( 數(shù)據(jù)場的邊界處除外) ，等值點的三角化過程應(yīng)遵循以下規(guī)則： ( 1 ) 體元內(nèi)曲面的各三角片之間滿足c o 連續(xù)；( 2 ) 體元內(nèi)曲面無自交現(xiàn)象；( 3 ) 不出現(xiàn)“邊界面三角片”( 屬于體元邊界面的一部分的三角片) ；( 4 ) 一條直線 段屬于且僅屬于兩個三角片( 邊界體元除外) 。 2 2m 矗r c h i n gc u b 囂算法的優(yōu)點和存在問題 m a r c h i n gc u b e s 方法的提出提供了一種精確的定義體元以及體元內(nèi)等值面 的生成方法，體元定義為由相鄰層之間八個網(wǎng)格點組成的數(shù)據(jù)單元，它提供了一 種更一般化的體元定義，從造型的觀點看，所有三維標(biāo)量場都可以由這種一般意 義下的體元或單元組成，因而標(biāo)量場中的等值面的生成均可以分別在這些組成標(biāo) 量場的體元內(nèi)完成，這為散亂數(shù)據(jù)場和曲面分布數(shù)據(jù)場中等值面的構(gòu)造提供了非 常簡單有效的方法。但算法在構(gòu)造等值面的過程中，太依賴于直觀的構(gòu)造，構(gòu)建 體元狀態(tài)模型的過程中，對于對稱，旋轉(zhuǎn)等情況的處理缺乏全面考慮，忽視了立 方體內(nèi)部可能存在的環(huán)狀結(jié)構(gòu)和存在的臨界點( 等值面發(fā)生變化的點) ，直接使 用求得的邊界等值點，根據(jù)簡單的體元狀態(tài)模型，簡單連接成三角片，因此，存 在許多缺點。算法白面世之日起就受到極大的關(guān)注，該領(lǐng)域研究人員在應(yīng)用中不 斷地發(fā)現(xiàn)其中的問題和不足之處并加以改進(jìn)。 最早d a r s t 例發(fā)現(xiàn)二義性的問題。如果在體元的一個邊界面上，標(biāo)號為+ 和 標(biāo)號為一的角點分別位于對角線的兩端，則該表面上存在四個等值點，那么就會 有兩種可能的等值線的連接方式，如圖2 3 中a ) 和b ) 所示。如果二義性問題不解 決，就會導(dǎo)致最后生成的等值面可能有“孔洞”存在，即不能保證曲面的封閉性， 從而將空間分為“內(nèi)”和“外”。為與下文的體二義性相區(qū)別，我們稱這種二義 山東大學(xué)碩士學(xué)位論文 性為面二義性。 我們來觀察圖2 3 中的體元狀態(tài)模型可知，3 、6 中有一個面存在二義性，l o 中有兩個面存在二義性7 、1 2 中有三個面存在二義性，而1 3 中的六個面都存在 二義性。 圖2 3 二義性面上四個交點的相對位置 隨著m c 方法的廣泛應(yīng)用和對其研究的逐步深入，人們又發(fā)現(xiàn)了新的問題， n a t a r a ja n 【1 川首先指出體二義性的存在。根據(jù)三維線性插值，即使體元的六個表 面都不存在二義性，體元內(nèi)部的等值面仍然不確定。如圖2 - 4 中的體元狀態(tài)模型 4 ，其內(nèi)部的等值面可能為兩片分離的面片，也可能為一“管”狀曲面，也就是 說，m c 算法的體元模型查找表不完整，不能保證逼近等值面的拓?fù)湔_性。 畫 圖2 4 體二義性和“管”狀曲面 m c 算法在求逼近等值面的過程中，使用線性插值計算出等值面與立方體邊 的交點( 等值點) 之后，采用簡單連接的方式，形成逼近等值面的邊界多邊形， 然后進(jìn)行三角化得到最終的逼近等值面片。當(dāng)對目標(biāo)數(shù)據(jù)場的采樣密度比較大， 立方體大小相對顯示尺度來說很小時，這種簡單構(gòu)造三角片的方式已經(jīng)足以滿足 實際使用的精度要求。但如果要對局部數(shù)據(jù)放大觀察或者采樣數(shù)據(jù)本身的分辨率 很低，這種簡單連接方式構(gòu)造的逼近等值面分辨率較低，遠(yuǎn)遠(yuǎn)不能達(dá)到實用的要 山東大學(xué)碩士學(xué)位論文 求。 此外，m c 算法在數(shù)據(jù)場密度較高的情況下具有較好的繪制效果，但這時往 往生成過多的三角面片，存儲這些三角片頂點位置和法向量，需要較大的存儲空 間和傳輸帶寬，同時，計算大量三角面片的頂點位置和法向量，需要較長的時間 進(jìn)行處理，以至于很難進(jìn)行實時繪制和交互式應(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 面二義性問題 第二章中提到，如果位于等值面內(nèi)和在等值面外的頂點分別分布在對角線的 兩端，就會有兩種連接方式，當(dāng)相鄰的兩個立方體在公共面上采取的連接方式不 相同時，就會出現(xiàn)面二義性，導(dǎo)致孔洞生成。隨著面二義性問題的提出，也隨之 出現(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 刀和四面體剖分法方法( 移動四面體法婦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ù)據(jù)場呈線性變化， 由于四面體的每個面是三角形，生成的等值面片的連接方式是唯一的，并且對于 每個四面體，等值面模式只有三種情況，如圖3 。如果頂點數(shù)據(jù)全大于或者全小 于等值面值，等值面與單元無交( 圖3 1 左) ，如果一個頂點大于另外三個頂點 小于等值面值，則四面體中的等值面是一個三角片( 圖3 一l 中) ，如果兩個頂點 大于兩個小于等值面值，則等值面是一個四邊形( 圖3 1 右) ，可以由兩個三角 形構(gòu)造。 圖3 1 四面體中的等值面 四面體剖分法將立方體剖分為5 個，6 個或2 4 個四面體。然而，5 個或6 個 四面體的剖分是一種不對稱的剖分，剖分后形成的四面體不全等，無疑增加了處 理的復(fù)雜性。雖然2 4 個四面體的剖分是一種全等四面體的剖分，四面體的插值 計算比較簡單，卻產(chǎn)生太多的三角片，并且在立方體內(nèi)的等值面沒有二義性時， 山東大學(xué)碩士學(xué)位論文 立方體也會被剖分處理，這都大大增加了算法的時間耗費。面對龐大的數(shù)據(jù)，為 達(dá)到實時交互的要求，減少計算和存儲顯得尤為必要，尤其是近年來隨著成像設(shè) 備物理分辨率的不斷提高，對可視化運算速度提出更高的要求。另外，對于一個 立方體來說，四面體剖分方法中等值面的構(gòu)造跟剖分方式有關(guān)，不同的四面體剖 分方式將導(dǎo)致不同的等值面例，如圖3 2 所示。這樣一來，整個數(shù)據(jù)場內(nèi)等值面 的構(gòu)造與最初一個體元的剖分方式有關(guān)，導(dǎo)致形成的逼近等值面可能和真實等值 面有不同的拓?fù)浣Y(jié)構(gòu)。因而，用四面體剖分法來解決二義性問題很難達(dá)到理想的 結(jié)果。 圖3 2 四面體不同剖分方式形成不同的等值面 3 1 2 基于漸近線方法解決面二義性 漸近線方法是應(yīng)用最為廣泛的判定面二義性的方法?；驹硎牵寒?dāng)出現(xiàn) 面二義性時，雙曲線的兩支將所在平面分成三個區(qū)域，雙曲線漸近線的交點總是 和其中一對交點落在同一區(qū)域，具體為如果漸近線交點的標(biāo)量值大于等值面的標(biāo) 量值，則標(biāo)量值大于等值面標(biāo)量值的對頂點跟交點落在同一區(qū)域，反之，另一 對頂點與漸近線交點落在同一區(qū)域，這是漸近線方法判定面二義性的基礎(chǔ)。 根據(jù)漸近線方法，位于體元某一表面的等值線是一對漸近線分別與體元邊相 平行的雙曲線，雙曲線與體元表面可能交于0 、1 、2 、3 、4 個交點，如圖3 - 3 所 示。其中( a ) 、( b ) 和( e ) 三種均為退化情形，為處理簡單，我們將( a ) 歸并為( c ) ， ( b ) ( e ) 歸并為( f ) 。只考慮雙曲線與體元表面存在o 、2 和4 個交點的情形，即 山東大學(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é)果 采用漸近線方法可正確解決二義性面的連接問題，并且不會產(chǎn)生太多的 三角片，因而是解決面二義性的一種較好的方法。 山東大學(xué)碩士學(xué)位論文 3 2 m a r c h i n gc u b 鸛體二義性問題 n i e l s o n 【”，1 6 1 刀等雖然對立方體面上存在的二義性進(jìn)行分析，但對三線性插 值函數(shù)在立方體內(nèi)部的形狀沒有給與足夠的重視。n a t a r a j a n 【1 9 】對等值面在立方 體內(nèi)部的具體形狀進(jìn)行詳細(xì)研究，進(jìn)一步發(fā)現(xiàn)即使體元中不存在二義性面，體元 內(nèi)部也可能存在不同拓?fù)浣Y(jié)構(gòu)的等值面，指出了體二義性存在的可能性，并提供 了最初的解決辦法。隨后，通過對三線性插值等值面拓?fù)浣Y(jié)構(gòu)的深入研究，許多 體內(nèi)拓?fù)涠x性的解決辦法也相繼被提出。如圖3 5 中的體元狀態(tài)模型4 ，其內(nèi) 部的等值面可能為兩片分離的面片，也可能為一“管”狀曲面。 畫 圖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é)者開始提出新的疑問：除了模式4 外，是否還有其他體元內(nèi)部存在“管” 狀瞳面? 如果存在，又如何判定“管”狀曲面的存在和提取逼近等值面呢? 由此 引起了眾多學(xué)者的關(guān)注，提出了許多對于m c 方法的改進(jìn)。 3 2 1 利用鞍點解決體二義性 t a r a j a n 為有效的利用m c 算法抽取拓?fù)浣Y(jié)構(gòu)正確的等值面，提出逼近等 值面片需要滿足的三個條件：一是所得逼近等值面片須是原來等值面的幾何逼 近，即在一定誤差范圍內(nèi)與原等值面相同；二是要達(dá)到拓?fù)湟恢滦裕簿褪窃隗w 元中的任意兩點，對于逼近的等值面片和等值面，具有相同的位置關(guān)系；三是構(gòu) 造逼近等值面片的復(fù)雜度不能太高。在文章中n a t a r a j a n 引入了面鞍點和體鞍點 的概念，并利用這兩類鞍點來解決滿足以上三個條件的可視化問題。其中面鞍點 為漸近線方法中漸近線的交點，體鞍點為在三維空間中面鞍點的擴(kuò)展。即根據(jù)數(shù) 據(jù)在體元面上是雙線性變化的，可以得到在該面上的雙線性函數(shù)，對其兩個分量 山東大學(xué)碩士學(xué)位論文 分別求偏導(dǎo)，可以得到面鞍點，同理，對均勻采樣的數(shù)據(jù)場進(jìn)行三線性插值得到 的三線性函數(shù)，通過求該函數(shù)在三個方向上的偏導(dǎo)數(shù)可以得到體鞍點。 得到面鞍點和體鞍點后，根據(jù)以下規(guī)則來解決二義性：如果面上的一對對角 線頂點與面鞍點有相同的符號( 同時大于或者同時小于等值面值) ，則這一對頂點 在同一個區(qū)域內(nèi)，否則另外一對定點在同一區(qū)域；如果體對角線的一對頂點與體 鞍點有相同的符號，則連通這一對頂點，構(gòu)成一個管狀曲面，否則不連通這對頂 點，形成兩個分離的三角片。 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)部的逼近多邊形的邊只能由兩個多邊形共享，體數(shù)據(jù)邊緣的邊只能出現(xiàn)在 一個逼近多邊形中。并進(jìn)一步指出，如果三角片位于立方體的面上，在該立方體 中就會有兩個三角形共享同一條邊，同時，在相鄰的立方體中也會有至少一個三 角形共享這條邊，這將導(dǎo)致生成的三角片逼近曲面不連續(xù)。雖然n a t a r a j a n 解決 了立方體中存在的拓?fù)涠x性，但由于算法中沒有解決三角片落在立方體面上的 問題，因而不能保證生成c 0 連續(xù)的三角曲面片，同時，n a t a r a j a n 也沒有明確提 出對曲面如何進(jìn)行三角化。c i g l l o n i 鯽以n a t a r a j a n 的研究為基礎(chǔ)，對m c 進(jìn)行了進(jìn) 一步的研究，基于面鞍點和體鞍點對m c 的基本體元狀態(tài)進(jìn)行進(jìn)一步分類，構(gòu)造了 擴(kuò)展查找表，對各種情況都給出了三角化方法，新建的擴(kuò)展查找表總共7 9 8 種情 況，進(jìn)行旋轉(zhuǎn)，映射等操作后，最終得到具有8 8 種情況且各不相同的分類查找 表。對于逼近等值面存在不連續(xù)性的問題，特別是當(dāng)有三角片在立方體面上存在 時，算法通過對立方體對角線頂點插值的方法，來加入一個體對角線上的點，有 效解決了不連續(xù)的問題。但由于數(shù)據(jù)場在體對角線上是三線性變化的，因此，引 入的內(nèi)部點可能不在原等值面上。此外，對于圖3 噸中的體元模型1 3 4 中存在 單個復(fù)雜曲面片的情況和1 3 5 1 中存在兩個體鞍點的情況，算法都沒有很好的 加以解決。 3 2 2 推廣漸近線方法解決體二義性 c h e n l y a e v 口5 1 利用漸近線方法解決面上的二義性，對拓?fù)涠x性，提出兩 種新方法來加以解決。第一種方法以下面的結(jié)論為基礎(chǔ)：在立方體上的一個三線 性插值函數(shù)在一條平行于邊的直線上是線性變化的。算法通過比較有拓?fù)涠x性 1 4 山東大學(xué)碩士學(xué)位論文 的立方體相對的平面上的漸近線來消除二義性。如圖3 5 ，如果兩個符號相同的 點在立方體內(nèi)部是連通的，那么其一個面上的漸近線投影到其相對的另一個面上 時，兩段漸近線必然相交，反之，如果兩段漸近線的投影不相交，那么這兩個頂 點是分離的。 圖3 6 體元模型4 的兩種情況 第二種方法基于在平行于立方體面的任意平面上，三線性函數(shù)都是雙線性變 化的。在立方體中如果有兩個頂點是在內(nèi)部連通，但在面上不是連通的，如圖 3 7 中的a 。，c 1 ，那么必然存在一個平行于立方體面的平面，平面與立方體的 交點形成的面是一個二義性面，在該二義性面中，符號與立方體中連通的頂點的 符號相同的兩個頂點連通( 圖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īng)的頂點a 。，c ，在立方體內(nèi)部是連通的，否則，a 。，c 。是不連通的， 山東大學(xué)碩士學(xué)位論文 從而有效地將拓?fù)涠x性去除。 畫畫 國畫圓圓 畫回國廚圓 圓靜畫固器 圓圓留 圓 回國 圖3 8 細(xì)分m c 體元狀態(tài)模型 c h e r n y a e v 對m c 算法的1 5 種基本情況，首先根據(jù)是否含有二義性面進(jìn)行細(xì) 分，對于細(xì)分的這些情況中存在內(nèi)部拓?fù)涠x性的情況，進(jìn)一步加以細(xì)分。最后 明確給出了有3 3 種情況的拓?fù)浞诸惽闆r如圖3 8 和對應(yīng)的三角化方法。對于立 方體內(nèi)部需要加入頂點的情況，算法選擇其他頂點的平均值作為新加入的點，這 種方法選擇的點不一定位于等值面上，同時，算法也沒有解決三角片位于立方體 面上從而導(dǎo)致生成逼近