等值線等值面的生成

會計學1等值線等值面的生成網格序列法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

{

如果該邊兩端點所賦值異號， 則通過線性插值計算交點（等值點）并輸出 否則， 沒有交點

}

否則

{

如果兩端點函數值同號而相應的判別式非負 則解一元二次方程式計算兩個交點，并輸出落在兩端點間的交點 如果兩端點函數值異號 計算兩交點，取落在兩端點間的點為交點，并輸出 舍去另一點

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