等值線等值面的生成

會(huì)計(jì)學(xué)1等值線等值面的生成網(wǎng)格序列法

(1)將網(wǎng)格點(diǎn)分為“IN”和“OUT”兩種狀態(tài)，表示該點(diǎn)在等值線內(nèi)，或在等值線外。如果Fij≤Ft，則頂點(diǎn)(xi,yj)為“IN”，記為“－”；如果Fij﹥Ft，則頂點(diǎn)(xi,yj)為“OUT”，記為“＋”。(2)如果單元四個(gè)頂點(diǎn)全為“＋”，或全為“－”，則網(wǎng)格單元與值為Ft的等值線無交點(diǎn)，否則(3)對(duì)于兩個(gè)頂點(diǎn)分別為“＋”、“－”的單元邊，可用線性插值計(jì)算等值線在這條邊上的交點(diǎn)。如圖所示，(x0,y0)為“－”，(x0,y1)為“＋”，則交點(diǎn)為第1頁/共60頁網(wǎng)格序列法

在每一單元內(nèi)計(jì)算出等值線與該網(wǎng)格單元邊的交點(diǎn)后，利用這些交點(diǎn)，就能構(gòu)成在該單元內(nèi)的等值線段。為了正確地連接交點(diǎn)生成等值線段，必須規(guī)定等值線的方向。等值線的方向定義如下：沿等值線走，大于等值線值的點(diǎn)在等值線的左邊，小于等值線值的點(diǎn)在等值線的右邊。也就是“－”點(diǎn)在等值線的右邊，“＋”點(diǎn)在等值線的左邊。在規(guī)定了等值線的走向后，等值線的連接對(duì)于矩形單元可分如下四種情況進(jìn)行：(1)頂點(diǎn)全為“＋”，或全為“－”，無等值線段；(2)有一個(gè)頂點(diǎn)為“＋”或“－”，共可求出兩個(gè)交點(diǎn)，有一條等值線段，如圖3。第2頁/共60頁第3頁/共60頁網(wǎng)格序列法

(3)有兩個(gè)“＋”，兩個(gè)“－”頂點(diǎn)的情況，根據(jù)頂點(diǎn)的分布又可分成下面兩種情況：①有兩個(gè)交點(diǎn)，即兩個(gè)“＋”或兩個(gè)“－”的頂點(diǎn)位于同一條單元邊上，等值線段的連接如圖4a所示。②有4個(gè)交點(diǎn)，即“＋”、“－”頂點(diǎn)的分布相互交叉，這時(shí)的連接在規(guī)定了函數(shù)的走向后，可確定P，R為入點(diǎn)，S，Q為出點(diǎn)，連接情況如圖4b所示。在上述②的情況下，如果不規(guī)定等值線的走向，其實(shí)存在兩種連接方式，見圖5。在實(shí)際情況中，這兩種方式都是可能的，這種二義性的主要原因是在該單元內(nèi)存在一馬鞍點(diǎn)。第4頁/共60頁第5頁/共60頁第6頁/共60頁網(wǎng)格序列法

如何從中選擇一種正確的連接方式呢？這可從單元內(nèi)的雙線性插值函數(shù)分析入手。由于在單元邊上采用了線性插值，由此單元面上函數(shù)值的變化是雙線性的，即等值線在單元內(nèi)不是直線段而是雙曲線。二義性連接可通過求該雙曲線兩條漸近線交點(diǎn)處的函數(shù)值來判定，這是因?yàn)闈u近線的交點(diǎn)總是與其中一對(duì)頂點(diǎn)落入同一區(qū)域內(nèi)，如漸近線交點(diǎn)為“＋”，則取圖5a的連接方式；如為“－”，則取圖5b的連接方式。即在圖5a中，表示單元中部為“＋”，在圖5b中，表示單元中部為“－”。在實(shí)際計(jì)算中，為簡(jiǎn)化計(jì)算，往往采用單元對(duì)角線交點(diǎn)代替漸近線交點(diǎn)的計(jì)算。第7頁/共60頁單元剖分法

在網(wǎng)格序列法中，提出了解決矩形單元內(nèi)等值線的生成算法，其中馬鞍點(diǎn)二義性的解決是算法的一個(gè)主要復(fù)雜點(diǎn)，除此之外人們還提出了單元剖分法，該方法與矩形單元法相比，其主要特點(diǎn)是采用三角片簡(jiǎn)化單元內(nèi)等值線的抽取，無需再進(jìn)行馬鞍點(diǎn)的判定，但處理的單元數(shù)是原來的四倍。算法的基本思想是利用對(duì)角線將矩形單元分成四個(gè)三角形單元，見圖6，求出中心點(diǎn)的函數(shù)值，等值線的抽取直接在每個(gè)三角片中進(jìn)行。由于每一個(gè)三角片至多只包含一條等值線，因而在由三角片的三個(gè)點(diǎn)決定的平面內(nèi)，可直接用直線段連接等值線。

第8頁/共60頁單元剖分法

中心點(diǎn)函數(shù)值Fmid的計(jì)算可采用兩種方式：如有顯式函數(shù)F(x,y)，則Fmid=F(xmid,ymid)；如只有四個(gè)點(diǎn)的函數(shù)值，無法求顯式函數(shù)形式，則可用四點(diǎn)的平均值代替Fmid。圖7列出了幾種可能的情況，可以看出，通過利用矩形單元中點(diǎn)的函數(shù)值，等值線的精度提高了，其抽取過程也相對(duì)簡(jiǎn)單些。第9頁/共60頁第10頁/共60頁第11頁/共60頁第4章等值面的生成

所謂等值面是指空間中的一個(gè)曲面，在該曲面上函數(shù)F(x,y,z)的值等于某一給定值Ft，即等值面是由所有點(diǎn)SFt={(x,y,z)：F(x,y,z)=Ft}組成的一個(gè)曲面。等值面技術(shù)在可視化中應(yīng)用很廣，許多標(biāo)量場(chǎng)的可視化問題都可歸納為等值面的抽取和繪制，如各種等勢(shì)面、等位面、等壓面、等溫面等。等值面技術(shù)除生成等值面的幾何表示外，還包括顯示技術(shù)，如要考慮合適的光照模型、解決等值面的相互遮擋等。等值面的生成和顯示也是可視化研究中的一個(gè)重要領(lǐng)域。第12頁/共60頁一Cuberille方法(立方體方法)

Cuberrille等值面方法又稱OpaqueCube算法，最初由Herman等人提出，后來又多次改進(jìn)。算法主要分為兩個(gè)步驟。(1)確定邊界單元對(duì)于規(guī)則網(wǎng)格數(shù)據(jù)，其網(wǎng)格單元可看成是正六面體單元，整個(gè)三維數(shù)據(jù)就是由這種正六面體組成的，這種組成三維圖象的基本正六面體單元稱為體元。對(duì)于給定的閾值Ft，遍歷體數(shù)據(jù)中的各個(gè)單元，將組成體元8個(gè)頂點(diǎn)上的值與Ft進(jìn)行比較，找出頂點(diǎn)值跨越Ft的所有體元，即體元中有的頂點(diǎn)值大于閾值，有的頂點(diǎn)值小于閾值，因此體元內(nèi)包含等值面片，這就是邊界單元。(2)繪制各邊界單元的6個(gè)多邊形面，即將等值面看成是由各單元的六個(gè)外表面拼合而成。第13頁/共60頁Cuberille方法(立方體方法)

每個(gè)單元均為一正六面體，包括6個(gè)多邊形面。對(duì)組成所有邊界體元的多邊形面進(jìn)行繪制，即可產(chǎn)生最終的圖象結(jié)果。在繪制多邊形過程中應(yīng)采用合適的光照模型和消隱技術(shù)。如果在具有硬件深度緩存(Z-buffer)功能的計(jì)算機(jī)上運(yùn)行立方體方法，可以將這組多邊形不分次序地提交給硬件，由硬件完成消除隱藏面的任務(wù)。如果以軟件方式執(zhí)行立方體方法，在算法中必須考慮多邊形的遮擋問題。一個(gè)有效的方法是把遍歷體元集合與顯示兩個(gè)步驟合二為一，遍歷體元集合時(shí)采用從后至前的次序。發(fā)現(xiàn)一個(gè)邊界體元，就立刻顯示它的6個(gè)面。后顯示到屏幕上去的多邊形將覆蓋先顯示的多邊形，這樣就達(dá)到了消除隱藏面的目的，這就是畫家算法的思想。第14頁/共60頁Cuberille方法(立方體方法)

Cuberrille算法的主要優(yōu)點(diǎn)是簡(jiǎn)單易行，其主要缺點(diǎn)是出現(xiàn)嚴(yán)重的走樣，顯示的圖象給人一種“塊狀的感覺”，尤其在物體邊界處鋸齒形走樣特別明顯，而且畫面較粗糙，不能很好地顯示對(duì)象的細(xì)節(jié)。立方體法的另一個(gè)缺點(diǎn)是面的重疊冗余問題。兩個(gè)相鄰邊界體元的公共面重復(fù)出現(xiàn)，實(shí)際上它們都不會(huì)出現(xiàn)在顯示畫面上，因?yàn)闊o論從哪個(gè)角度進(jìn)行觀察，它們都會(huì)被這兩個(gè)體元的其它面遮擋。改進(jìn)的立方體法刪除了邊界體元之間的公共面，減少了顯示過程需要處理的多邊形的數(shù)量。第15頁/共60頁二MarchingCubes(MC)方法

MarchingCubes（移動(dòng)立方體）方法是由W.E.Lorenson和H.E.Cline在1987年提出來的。由于這一方法原理簡(jiǎn)單，易于實(shí)現(xiàn)，目前已經(jīng)得到了較為廣泛的應(yīng)用，成為三維數(shù)據(jù)等值面生成的經(jīng)典算法，MarchingCubes算法又簡(jiǎn)稱為MC算法。1．MC方法的基本原理在MarchingCubes方法中，假定原始數(shù)據(jù)是離散的三維空間規(guī)則數(shù)據(jù)，一個(gè)體元定義為由相鄰層上的8個(gè)頂點(diǎn)組成的一個(gè)長(zhǎng)方體。為了在三維數(shù)據(jù)中構(gòu)造等值面，應(yīng)先給定所求等值面的值，該方法的基本原理是逐個(gè)處理所有的體元，將體元各頂點(diǎn)處的值與給定的閾值進(jìn)行比較，首先找出與等值面相交的體元，然后通過插值求等值面與體元棱邊的交點(diǎn)，并將各交點(diǎn)連成三角形來構(gòu)成等值面片，所有體元中的三角形集合就構(gòu)成了等值面。由于這一方法是逐個(gè)處理所有的體元，因此被稱為MarchingCubes方法。MC方法的主要步驟如下：第16頁/共60頁MarchingCubes(MC)方法

(1)確定包含等值面的體元及對(duì)應(yīng)的等值面片模式一個(gè)體元由8個(gè)數(shù)據(jù)點(diǎn)構(gòu)成，這8個(gè)數(shù)據(jù)點(diǎn)分別位于該體元的8個(gè)頂點(diǎn)上。首先對(duì)體元的8個(gè)頂點(diǎn)進(jìn)行分類，判定是位于等值面之外，還是位于等值面之內(nèi)。再根據(jù)8個(gè)頂點(diǎn)的狀態(tài)，確定等值面的模式。設(shè)等值面的值為Ft，頂點(diǎn)分類規(guī)則為：若某頂點(diǎn)的值≥Ft，則定義該頂點(diǎn)位于等值面之外，記為“0”。若某頂點(diǎn)的值＜Ft，則定義該頂點(diǎn)位于等值面之內(nèi)，記為“1”。如果某體元一條邊的一個(gè)頂點(diǎn)在等值面之內(nèi)，而另一個(gè)頂點(diǎn)在等值面之外，那么，該邊必然與等值面相交。根據(jù)這一原理就可以判斷所求等值面將與哪些體元相交，或者說將穿過哪些體元。第17頁/共60頁MarchingCubes(MC)方法

由于每個(gè)體元有8個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)又有0、1兩種狀態(tài)，因此每個(gè)體元按其8個(gè)頂點(diǎn)的0、1分布而言，共有28=256種不同的狀態(tài)。盡管判斷等值面將與哪些體元相交在原理上很容易理解，但是要根據(jù)這256種不同的情況求出每個(gè)體元中的等值面卻是很繁瑣的，而且也容易出錯(cuò)。可以利用兩種不同的對(duì)稱性將256種不同的情況簡(jiǎn)化為15種。①互補(bǔ)對(duì)稱性：如果將一個(gè)體元的頂點(diǎn)狀態(tài)顛倒，即“0”變成“1”，“1”變成“0”，則等值面與體元中8個(gè)頂點(diǎn)之間的拓?fù)潢P(guān)系將不會(huì)改變，該體元與等值面的相交情況與原來一致，即新生成的等值面與原等值面是相同的。也就是說，大于等值面的點(diǎn)與小于等值面的點(diǎn)是可以相互替換的，因此，只要考慮4個(gè)以下（含4個(gè)）的頂點(diǎn)值大于Ft就夠了。根據(jù)這種互補(bǔ)對(duì)稱性，可將體元的模式由256種減少為128種。

第18頁/共60頁MarchingCubes(MC)方法

②旋轉(zhuǎn)對(duì)稱性：如果某一模式的體元經(jīng)過旋轉(zhuǎn)后與另一模式的體元一致，即頂點(diǎn)位置及其狀態(tài)值相同，那么這兩種模式的體元可以合并為一種。根據(jù)這種旋轉(zhuǎn)對(duì)稱性，體元模式可以最終歸納為15種，見圖2。其中第0種情況表示所有8個(gè)頂點(diǎn)的值均大于（或小于）Ft，因而該體元與等值面不相交。第一種情況表示有一個(gè)頂點(diǎn)的函數(shù)值大于（或小于）Ft，其余7個(gè)頂點(diǎn)均與此相反，因而該體元內(nèi)的等值面將是一個(gè)三角面片。在考慮了上面兩種對(duì)稱性后，這一種情況實(shí)際上代表了16種情況。如此類推，圖2中的15種模式反映了一個(gè)體元中8個(gè)頂點(diǎn)可能存在的全部256種狀態(tài)。第19頁/共60頁第20頁/共60頁在實(shí)現(xiàn)時(shí)，對(duì)一個(gè)體元可按照它的8個(gè)頂點(diǎn)的狀態(tài)構(gòu)造一個(gè)一字節(jié)（8位）的狀態(tài)表，如圖3所示，其中的每一位表示該體元中一個(gè)頂點(diǎn)的0或1狀態(tài)，根據(jù)這個(gè)狀態(tài)表就可判斷出當(dāng)前體元屬于哪一種模式、等值面將與哪一條邊相交以及體元內(nèi)三角面片的連接方式。第21頁/共60頁MarchingCubes(MC)方法

(2)計(jì)算等值面與體元邊界的交點(diǎn)，并連接成三角形當(dāng)三維離散數(shù)據(jù)的密度較高，即每個(gè)體元很小時(shí)，可以假定函數(shù)值沿體元邊界呈線性變化。因此，等值面與體元邊界的交點(diǎn)可以通過該邊兩端點(diǎn)函數(shù)值的線性插值求出，公式為：求出了等值面與體元邊界的交點(diǎn)以后，就可以按對(duì)應(yīng)的模式將這些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片。第22頁/共60頁MarchingCubes(MC)方法

(3)計(jì)算等值面的法向?yàn)榱死L制等值面的真實(shí)感圖象，還必須給出構(gòu)成等值面的各三角面片的法向。對(duì)于等值面上的每一點(diǎn)，沿該面切線方向的梯度分量應(yīng)該是零，因此該點(diǎn)的梯度矢量的方向就代表了等值面的法向。MC方法就是利用這一原理來計(jì)算三角面片的法向。即對(duì)于三維規(guī)則網(wǎng)格數(shù)據(jù)，可以直接采用中心差分計(jì)算體元各頂點(diǎn)處的梯度，公式為：第23頁/共60頁三角形頂點(diǎn)處的法向量可由體元邊界兩端點(diǎn)處的梯度再通過線性插值求得。在實(shí)際繪制等值面時(shí)，為了消除各三角面片之間明暗的不連續(xù)變化，只要給出三角面片各頂點(diǎn)處的法向并采用哥羅得(Gouraud)模型繪制各個(gè)三角面片即可。在計(jì)算機(jī)圖形學(xué)中，光滑的曲面常用多邊形來逼近，這是因?yàn)樘幚砥矫姹忍幚砬嫒菀椎枚?。例如，為了表示一個(gè)磨光的立方體的頂角，可使用7個(gè)平面片來近似。但是，若單純使用平面來繪制這種近似表面，生成的圖形將失去原有曲面的光滑性，而呈現(xiàn)多面體狀。這是由于平面上所有點(diǎn)的法向相同，不同平面塊之間存在不連續(xù)的法向量變化，從而引起不連續(xù)的光亮度跳躍。如何能以較少的計(jì)算量來解決上述問題呢?最簡(jiǎn)單的方法就是Gouraud明暗處理技術(shù)。Gouraud明暗處理的思想是對(duì)離散的光亮度作雙線性插值以獲得連續(xù)的光亮度函數(shù)。具體做法是：先計(jì)算出多邊形頂點(diǎn)處的光亮度值，把它們作為曲面光亮度的采樣點(diǎn)，然后根據(jù)多邊形頂點(diǎn)處的光亮度值進(jìn)行插值求多邊形內(nèi)任一點(diǎn)的光亮度。第24頁/共60頁若采用掃描線繪制算法，則可沿當(dāng)前掃描線進(jìn)行雙線性插值，這是一種簡(jiǎn)便易行的插值方法。即先用多邊形頂點(diǎn)的光亮度值由線性插值求出當(dāng)前掃描線與多邊形交點(diǎn)處的光亮度，然后根據(jù)交點(diǎn)的光亮度值再通過線性插值求出掃描線上位于多邊形內(nèi)每一象素點(diǎn)的光亮度值。圖4(a)顯示一掃描線與多邊形相交，交點(diǎn)為a點(diǎn)和b點(diǎn)，p是掃描線上位于多邊形內(nèi)的任一點(diǎn)，多邊形三個(gè)頂點(diǎn)的光亮度分別為I1，I2和I3。取a點(diǎn)的光亮度Ia為I1和I2的線性插值，b點(diǎn)的光亮度Ib為I1和I3的線性插值，p點(diǎn)的光亮度則為Ia和Ib的線性插值，即：其中u,v,t稱為插值參數(shù)(相當(dāng)于以端點(diǎn)為原點(diǎn)歸一化后的長(zhǎng)度坐標(biāo))。第25頁/共60頁采用Gouraud明暗處理不但可以克服用多邊形表示曲面時(shí)光亮度的不連續(xù)現(xiàn)象，而且計(jì)算量也很小。事實(shí)上，由于線性插值可使用增量法進(jìn)行計(jì)算，其運(yùn)算量?jī)H涉及一次加法運(yùn)算。如在上例中，可沿掃描線從左至右的順序計(jì)算AB區(qū)段上所有象素的光亮度。設(shè)Ia和Ib已經(jīng)確定，p1和p2點(diǎn)是相鄰兩象素的坐標(biāo)，a、b兩點(diǎn)的插值參數(shù)之差為t，那么，不難發(fā)現(xiàn)p2點(diǎn)光亮度Ip2和p1點(diǎn)光亮度Ip1之間有下列關(guān)系：由于I在同一掃描線上為常數(shù)，因此計(jì)算一相鄰象素的光亮度僅需一次加法運(yùn)算。這種增量方式的光亮度計(jì)算使Gouraud明暗處理廣泛用于實(shí)時(shí)圖形生成。在Gouraud明暗處理中，計(jì)算多邊形頂點(diǎn)的光亮度可采用Phong光照模型。第26頁/共60頁第27頁/共60頁MarchingCubes(MC)方法

(4)用MC方法求等值面的算法流程①將三維離散規(guī)則數(shù)據(jù)分層讀入內(nèi)存；②掃描其中兩層數(shù)據(jù)，逐個(gè)構(gòu)造這兩層之間的體元，每個(gè)體元中的8個(gè)頂點(diǎn)取自相鄰的兩層；③將體元各個(gè)頂點(diǎn)的值與給定的等值面值Ft進(jìn)行比較，根據(jù)比較的結(jié)果進(jìn)行分類，構(gòu)造該體元的狀態(tài)表；④根據(jù)狀態(tài)表，查得與該狀態(tài)值對(duì)應(yīng)的等值面分布模式，確定將與等值面相交的體元邊界；⑤通過線性插值，計(jì)算體元邊界與等值面的交點(diǎn)坐標(biāo)，按對(duì)應(yīng)的模式將這些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片；⑥利用中心差分方法，求出體元各頂點(diǎn)處的梯度，再次通過線性插值方法，求出三角形各頂點(diǎn)處的法向；⑦根據(jù)各三角面片各頂點(diǎn)的坐標(biāo)值及法向量繪制等值面圖象。第28頁/共60頁MarchingCubes(MC)方法

2．MC方法的加速算法MarchingCube方法是逐個(gè)單元地檢測(cè)是否存在等值面，還要計(jì)算等值面與體元邊界的交點(diǎn)，再由標(biāo)準(zhǔn)的連接模式將各個(gè)交點(diǎn)連接成等值面片。事實(shí)上，據(jù)研究，真正與等值面相交的體元占總數(shù)據(jù)量很小的一部分（至多10%左右），計(jì)算過程中30-70%的時(shí)間用在了空體元的檢測(cè)上，從加快MarchingCube方法的角度出發(fā)，有必要研究一種快速有效的空間數(shù)據(jù)的遍歷方法和相應(yīng)的數(shù)據(jù)表達(dá)形式，以加速對(duì)空體元的檢測(cè)和排除。另一方面，對(duì)于一條與等值面相交的體元的邊，它同時(shí)被四個(gè)單元共用，這表明在這四個(gè)單元內(nèi)求等值面時(shí)都要用到這個(gè)交點(diǎn)，保存該交點(diǎn)的位置及法向量對(duì)于加速算法具有重要意義。第29頁/共60頁對(duì)于規(guī)則網(wǎng)格數(shù)據(jù)，其體元是一個(gè)六面體單元，若采用空間八叉樹來表示這種體數(shù)據(jù)，則可以加快運(yùn)算速度。MarchingCube方法的另一個(gè)重要問題是抽取的等值面三角片數(shù)量巨大，有時(shí)一個(gè)體元可以生成多達(dá)12個(gè)三角片，當(dāng)三維數(shù)據(jù)的數(shù)據(jù)量很大時(shí)，三角片的數(shù)量也非常大。這給等值面的繪制和交互操作帶來很大困難。Schroeder提出了在不影響圖形質(zhì)量的情況下，通過對(duì)原等值面三角片網(wǎng)重排結(jié)點(diǎn)，合并簡(jiǎn)化，生成最優(yōu)化意義下的Delaunay三角化網(wǎng)，可以有效加快圖形的實(shí)時(shí)顯示，這對(duì)于MarchingCube方法的實(shí)用是非常有意義的。第30頁/共60頁MarchingCubes(MC)方法

3．MC方法存在的問題(1)MC方法構(gòu)造的三角面片是三維等值面的近似表示首先，在MC方法中，等值面與體元邊界的交點(diǎn)是基于函數(shù)值在體元邊界上呈線性變化這一假設(shè)而求出的。當(dāng)數(shù)據(jù)密度高、體元很小時(shí)，這一假設(shè)接近于實(shí)際情況。但是，在稀疏數(shù)據(jù)中，體元較大，如果仍然認(rèn)為函數(shù)值在體元邊界上呈線性變化，將會(huì)產(chǎn)生較大誤差。這時(shí)，需要根據(jù)不同的具體情況對(duì)函數(shù)值沿體元邊界的變化作其它適當(dāng)?shù)募僭O(shè)，才能較準(zhǔn)確地求出等值面。其次，即使函數(shù)值沿體元邊界作線性變化這一假設(shè)符合實(shí)際，那么通過線性插值求得的交點(diǎn)位置是準(zhǔn)確的，但是，將體元中同一個(gè)面上兩條相鄰邊上的交點(diǎn)簡(jiǎn)單地用直線連接起來也是一種近似(如下圖所示)。第31頁/共60頁第32頁/共60頁為了說明這一問題，需要引入當(dāng)體元各邊界上函數(shù)值均為線性變化時(shí)的等值面模型。如圖3.5所示，P(x,y,z)為小體元中的任意點(diǎn)，體元中的數(shù)據(jù)沿x,y,z三個(gè)方向均是線性變化的。如果點(diǎn)P1，P2為點(diǎn)P沿y軸在立方體兩個(gè)面上的投影，P11、P12、P21、P22分別為P1，P2點(diǎn)沿z軸在立方體平面上的投影。設(shè)V為y軸上的坐標(biāo)分量，f為函數(shù)值，那么，通過三次線性插值，可得：

(1)其中P1，P2兩點(diǎn)的值可由P11，P12和P21，P22插值求得，而P11、P12、P21、P22四個(gè)點(diǎn)的值又可以由它們所在體元內(nèi)的一條邊上的兩個(gè)頂點(diǎn)插值得到。這樣，通過三次線性插值運(yùn)算，就可以求得P(x,y,z)點(diǎn)的函數(shù)值，（1）式可具體展開為：第33頁/共60頁其中系數(shù)ai

(i=0,…7)取決于體元8個(gè)頂點(diǎn)處的函數(shù)值，如果給定的等值面的值為Ft，那么，等值面就被定義為滿足如下方程的點(diǎn)的集合

(2)

改變Ft的值，就可以得到不同等值面的表達(dá)式。由上述等值面方程可以方便地求出某等值面與體元邊界面的交線方程。不失一般性，設(shè)某邊界面所在平面的方程為z=z0，代入方程式(2)，可得

(3)上式可進(jìn)一步表示為：第34頁/共60頁

（4）顯然，上述方程表示的是一條雙曲線，即等值面與體元中某一個(gè)面的交線是一條雙曲線或其中的一支。如果用一條直線來表示這條雙曲線，則會(huì)引起誤差（如圖所示）。如果體元很小，這一誤差是可以忽略不記的。對(duì)于稀疏的三維數(shù)據(jù)，這種近似引起的誤差是難以接受的，可通過自適應(yīng)剖分算法將三角形按給定的逼近精度遞歸地分成子三角形，使這些子三角形的頂點(diǎn)滿足方程(3)，且子三角形與等值面的最大距離小于給定的容差。第35頁/共60頁MarchingCubes(MC)方法

(2)連接方式上的二義性MarchingCubes方法可以看成是二維等值線網(wǎng)格序列法在三維空間中的推廣。在網(wǎng)格序列法中，如果矩形網(wǎng)格單元4個(gè)頂點(diǎn)中有兩個(gè)頂點(diǎn)的值大于等值線的值，另兩個(gè)頂點(diǎn)的值小于等值線的值，且這兩個(gè)頂點(diǎn)交叉分布，那么等值線的連接就出現(xiàn)二義性。同理，在MarchingCubes方法中，如果正六面體單元的6個(gè)矩形表面中出現(xiàn)與此相同的情形，那么該正六面體單元中的等值面連接必然會(huì)出現(xiàn)二義性，這樣的面稱為二義性面，包含1個(gè)以上的二義性面的體元，即為具有二義性的體元，如下圖所示。事實(shí)上，在MarchingCubes方法的15種模式中，第3、6、7、10、12、13等6種情況是具有二義性的。第36頁/共60頁第37頁/共60頁MarchingCubes(MC)方法

4．用雙曲線漸近線方法判別和消除二義性MC方法存在連接方式的二義性問題在該方法提出后不久，就由M.J.Durst提出來了，這一問題如果不解決，將造成等值面連接上的錯(cuò)誤。如在兩個(gè)相鄰體元的公共面上，可能會(huì)出現(xiàn)兩種不同的連接方式，從而形成空洞。盡管人們已經(jīng)提出了幾種不同的判別和消除二義性的方法，但以G.M.Nielson等人提出的漸近線法(1991)最為常用。如前所述，在一般情況下，等值面與體元邊界面所在平面的交線是一條雙曲線或其中的一支。該雙曲線的兩支及其漸近線與體元的一個(gè)邊界面的相對(duì)位置關(guān)系可用下圖5來表示。在該圖所列的四種狀態(tài)中，當(dāng)雙曲線的兩支均與體元的某邊界面相交時(shí)，就會(huì)出現(xiàn)連接方式的二義性。在出現(xiàn)二義性的情況中，雙曲線的兩支將邊界面劃分為3個(gè)區(qū)域，顯然，雙曲線漸近線的交點(diǎn)總是和邊界面中呈對(duì)角分布的一對(duì)頂點(diǎn)落在同一區(qū)域內(nèi)，這一性質(zhì)就成為解決二義性問題的基礎(chǔ)。第38頁/共60頁第39頁/共60頁根據(jù)(4)式，漸近線方程可寫為：當(dāng)出現(xiàn)二義性時(shí)，需要計(jì)算f(x,y,z0)的值。如果f(x,y,z0)＞Ft，則漸近線的交點(diǎn)應(yīng)與數(shù)值大于Ft的一對(duì)頂點(diǎn)落在同一區(qū)域，如圖6(a)所示，可連接M1M2、M3M4，否則漸近線交點(diǎn)與數(shù)值小于Ft的一對(duì)頂點(diǎn)落在同一區(qū)域，如圖6(b)所示，可連接M1M3、M2M4。在圖6中，當(dāng)f(x,y,z0)＞Ft時(shí)，對(duì)漸進(jìn)線的交點(diǎn)標(biāo)以正值，其對(duì)應(yīng)的二義面稱為正值二義面(記為PAF)。當(dāng)f(x,y,z0)＜Ft時(shí)，對(duì)漸進(jìn)線的交點(diǎn)標(biāo)以負(fù)值，其對(duì)應(yīng)的二義面稱為負(fù)值二義面(記為NAF)。第40頁/共60頁第41頁/共60頁在所列的全部15種模式中，第0、1、2、4、5、8、9、11、14這9種模式下不存在二義性面，因而它們只存在1種連接方式。第3、6兩種模式，各存在一個(gè)二義性面，因此各有兩種連接方式。第10、12兩種模式，各存在兩個(gè)二義性面，因而各有4種連接方式。第7種模式有3個(gè)二義性面，因而有8種連接方式。第13種模式有6個(gè)二義性面，因而有64種連接方式。將以上各種情況加在一起，共有93種不同的連接方式。對(duì)于存在二義性的體元，按上述方法解決二義性問題，雖然增加了計(jì)算工作量，但是為了得出完全正確的結(jié)果卻是十分必要的。第42頁/共60頁三MarchingTetrahedra(MT)方法

MarchingTetrahedra方法簡(jiǎn)稱為MT方法，亦稱四面體剖分法，它是在MC方法的基礎(chǔ)上發(fā)展起來的。該方法首先將立方體單元剖分為四面體，然后在其中構(gòu)造等值面。提出這種方法的原因很多。首先，由于四面體是最簡(jiǎn)單的多面體，其它類型的多面體都能剖分為四面體。其次，將立方體剖分為四面體后，在四面體中構(gòu)造的等值面的精度要比在立方體中構(gòu)造的等值面要高。而最直接的原因是企圖通過在四面體內(nèi)構(gòu)造等值面來避免MC方法中存在的二義性問題。第43頁/共60頁1．MT方法的基本原理及存在的問題可以將一個(gè)立方體剖分為5個(gè)、6個(gè)和24個(gè)四面體，5個(gè)或6個(gè)四面體的剖分是一種不對(duì)稱的剖分，剖分后的四面體不全等，24個(gè)四面體的剖分是一種全等四面體的剖分。常用的MT方法是將一個(gè)立方體剖分為5個(gè)四面體。與前述的方法一樣，假定待求的等值面的值為Ft，如果四面體頂點(diǎn)的值大于（或等于）Ft，則將該頂點(diǎn)賦以“+”號(hào)；如果小于Ft，則將該頂點(diǎn)賦以“－”號(hào)。假設(shè)在四面體的邊上數(shù)據(jù)呈線性變化，在考慮了“+”、“－”號(hào)反號(hào)造成的對(duì)稱情況后，對(duì)于每個(gè)四面體，等值面模式只有三種情況，如圖7所示。如果4個(gè)頂點(diǎn)全為“+”或全為“－”，等值面與該四面體無交點(diǎn)；如一個(gè)頂點(diǎn)為“+”，而另外3個(gè)頂點(diǎn)為“－”，則該四面體中等值面是一個(gè)三角片；如有兩個(gè)頂點(diǎn)為“+”，而另外2個(gè)頂點(diǎn)為“－”，則該四面體中等值面是一個(gè)四邊形，可分解為兩個(gè)三角片。將各三角片拼接起來即可構(gòu)成等值面，這就是MT方法的基本原理。第44頁/共60頁第45頁/共60頁第46頁/共60頁雖然在每一個(gè)四面體內(nèi)，等值面的生成是由頂點(diǎn)函數(shù)值的分布情況唯一確定的，但是，對(duì)于一個(gè)立方體來說，卻有兩種不同的四面體剖分方式。不同的剖分方式將生成不同的等值面，即等值面的結(jié)果依賴于剖分方式。另一方面，為了在相鄰體元的公共面上不出現(xiàn)裂縫，必須保證在這個(gè)面上的剖分一致性，也就是說，四面體的剖分方式在一系列體元中是交替變化的。這樣一來，三維數(shù)據(jù)內(nèi)等值面的構(gòu)造是與最初一個(gè)體元的剖分方式有關(guān)的。因此MT方法并不能消除等值面構(gòu)造中的二義性，這仍然是一個(gè)有待解決的問題。第47頁/共60頁2．MT方法中二義性的判別和消除

當(dāng)一個(gè)立方體剖分為5個(gè)四面體時(shí)，在每一個(gè)四面體的6條邊中，有些是原有立方體的棱，而另一些則是立方體6個(gè)面上的對(duì)角線。經(jīng)過仔細(xì)研究，在5個(gè)四面體的30條邊中，只有12條邊是原有立方體的棱，而其余18條則均為立方體面上的對(duì)角線。這就提出了一個(gè)問題，即當(dāng)立方體每條棱上的函數(shù)值呈線性變化時(shí)，立方體每個(gè)面中對(duì)角線上的函數(shù)值是否也呈線性變化呢？如果不是，那么當(dāng)該對(duì)角線兩端點(diǎn)均為“＋”（或“－”）時(shí)，就認(rèn)為在該線段上沒有交點(diǎn)，又是否能成立呢？前面論述過，當(dāng)體元每條棱上的函數(shù)值均呈線性變化時(shí)，體元內(nèi)等值面與體元邊界面的交線是由（3）式表示的一條雙曲線。設(shè)體元中一個(gè)面所在的平面為z=z0，該面上某一對(duì)頂點(diǎn)的坐標(biāo)為(xa,ya,z0)及(xb,yb,z0)，則由該對(duì)頂點(diǎn)構(gòu)成的對(duì)角線方程為第48頁/共60頁(5)將（5）式代入（3）式，經(jīng)過整理后可知，沿對(duì)角線的函數(shù)值分布為一個(gè)二次函數(shù)，并可寫成如下形式：

(6)其中A，B，C是由對(duì)角線端點(diǎn)坐標(biāo)及體元的8個(gè)頂點(diǎn)的函數(shù)值決定的常數(shù)。既然沿對(duì)角線的函數(shù)值分布為二次函數(shù)，那么當(dāng)對(duì)角線兩端點(diǎn)均為“＋”（或“－”）時(shí)，就不能簡(jiǎn)單地認(rèn)為在該對(duì)角線上無交點(diǎn)，而需要求解（6）式才能得出結(jié)果。于是，判斷對(duì)應(yīng)于閾值為Ft的等值面是否與該對(duì)角線相交，就需要判斷方程式（6）在區(qū)間[0，1]內(nèi)是否有解。第49頁/共60頁若C≠0，且，則方程(6)式將有兩個(gè)不同的解t1和t2。如果t1和t2都在區(qū)間[0，1]內(nèi)，那么等值面與對(duì)角線有兩個(gè)不同的交點(diǎn)，這是當(dāng)對(duì)角線兩端點(diǎn)的函數(shù)值為同號(hào)時(shí)的情況，是不能被忽略的。在這種情況下，等值面與體元對(duì)角線相交的多種可能性如圖8所示。

圖8等值面與體元對(duì)角線相交的多種可能性第50頁/共60頁圖8（a）表明，只有一條雙曲線通過體元的面并與對(duì)角線有兩個(gè)交點(diǎn)，但此刻，該對(duì)角線兩端點(diǎn)的函數(shù)值均為“+”。圖8(b)和(c)表示兩條雙曲線都通過該面，這是MC方法中的二義面。在圖8(b)中，兩條漸近線的交點(diǎn)與為“+”的對(duì)角線兩端點(diǎn)取異號(hào)，而在圖8(c)中，兩條漸近線的交點(diǎn)與為“+”的對(duì)角線兩端點(diǎn)取同號(hào)。在這兩種情況下，根據(jù)判別式計(jì)算結(jié)果，該等值線均與對(duì)角線有兩個(gè)交點(diǎn)。如果認(rèn)為該對(duì)角線兩端點(diǎn)的函數(shù)值均為“+”而忽略這兩個(gè)交點(diǎn)，將導(dǎo)致等值線的錯(cuò)誤連接（如圖8(d)所示）或等值線的連接不準(zhǔn)確（如圖8(e)所示），而這正是傳統(tǒng)的MT方法所存在的問題。第51頁/共60頁第52頁/共60頁綜上所述，在MT方法中判斷四面體的一條邊與等值面是否有交點(diǎn)及計(jì)算交點(diǎn)的算法可描述如下：如果E1E2是原體元的一條邊

{

如果該邊兩端點(diǎn)所賦值異號(hào)， 則通過線性插值計(jì)算交點(diǎn)（等值點(diǎn)）并輸出 否則， 沒有交點(diǎn)

}

否則

{

如果兩端點(diǎn)函數(shù)值同號(hào)而相應(yīng)的判別式非負(fù) 則解一元二次方程式計(jì)算兩個(gè)交點(diǎn)，并輸出落在兩端點(diǎn)間的交點(diǎn) 如果兩端點(diǎn)函數(shù)值異號(hào) 計(jì)算兩交點(diǎn)，取落在兩端點(diǎn)間的點(diǎn)為交點(diǎn)，并輸出 舍去另一點(diǎn)

}第53頁/共60頁3．連接等值點(diǎn)構(gòu)造多邊形在正確地計(jì)算出四面體各條邊上的交點(diǎn)，即等值點(diǎn)以后，下一步就應(yīng)該將一個(gè)四面體內(nèi)所有等值點(diǎn)連接成有效的多邊形。為此，需要首先考慮四面體中任一三角面片上等值點(diǎn)的連接。為了保證相鄰四面體在公共面上等值面的連接不出現(xiàn)裂縫，等值面被公共面所截得的交線應(yīng)該由公共面的性質(zhì)唯一決定，而不受它所在的四面體中其它頂點(diǎn)的影響。與此同時(shí)，三角形上等值點(diǎn)的連線不能與三角形的任何一條邊重合，且連線不能交叉。由于等值點(diǎn)的連線就是等值線，所以這樣的假設(shè)自然是合理的。對(duì)于一個(gè)三角形來說，根據(jù)頂點(diǎn)的函數(shù)值所賦予的符號(hào)及等值點(diǎn)的分布，可以分為6種狀態(tài)。具體可參見唐澤圣《三維數(shù)據(jù)場(chǎng)可視化》P101-P103。第54頁/共60頁當(dāng)實(shí)現(xiàn)了四面體每一個(gè)三角形內(nèi)等值點(diǎn)的連接以后，不同三角形內(nèi)的連接線在三角形的公共邊上首尾相連即可形成多邊形。首先從一個(gè)三角形內(nèi)任取一條連線，