等值線等值面的生成ppt課件

第3章二維標量場等值線的生成 二維標量場可看成是定義于某一個面上的二維標量函數(shù)F F x y 所謂等值線是由所有點 xi yi 構(gòu)成 其中F xi yi Ft 為一給定值 將這些點按一定順序連接起來就組成了函數(shù)值為Ft的等值線 對于二維標量場 其數(shù)據(jù)往往是分布在規(guī)則網(wǎng)格點上的 常用的等值線抽取方法有網(wǎng)格序列法和單元剖分法 網(wǎng)格序列法 網(wǎng)格序列法 gridsequence 的基本思想是按網(wǎng)格單元的排列次序 逐個處理每一單元 尋找每一單元內(nèi)相應(yīng)的等值線段 在處理完所有單元后 就自然生成了該網(wǎng)格中的等值線分布 規(guī)則網(wǎng)格數(shù)據(jù)等值線的生成設(shè)一規(guī)則網(wǎng)格數(shù)據(jù)如圖所示 網(wǎng)格線是相互正交的 每一網(wǎng)格單元是一矩形 其中四個頂點分別為 x0 y0 x0 y1 x1 y0 x1 y1 對應(yīng)的值分別為F00 F01 F10 F11 要在該單元內(nèi)生成值為Ft的等值線 其主要計算步驟為 逐個計算每一網(wǎng)格單元與等值線的交點 連接該單元內(nèi)等值線的交點 生成在該單元中的等值線線段 由一系列單元內(nèi)的等值線線段構(gòu)成該網(wǎng)格中的等值線 網(wǎng)格單元與等值線的交點計算主要是求各單元的邊線與等值線的交點 假設(shè)函數(shù)在單元內(nèi)呈線性變化 可以采用頂點判定 邊上插值的方法計算交點 具體步驟為 網(wǎng)格序列法 1 將網(wǎng)格點分為 IN 和 OUT 兩種狀態(tài) 表示該點在等值線內(nèi) 或在等值線外 如果Fij Ft 則頂點 xi yj 為 IN 記為 如果Fij Ft 則頂點 xi yj 為 OUT 記為 2 如果單元四個頂點全為 或全為 則網(wǎng)格單元與值為Ft的等值線無交點 否則 3 對于兩個頂點分別為 的單元邊 可用線性插值計算等值線在這條邊上的交點 如圖所示 x0 y0 為 x0 y1 為 則交點為 網(wǎng)格序列法 在每一單元內(nèi)計算出等值線與該網(wǎng)格單元邊的交點后 利用這些交點 就能構(gòu)成在該單元內(nèi)的等值線段 為了正確地連接交點生成等值線段 必須規(guī)定等值線的方向 等值線的方向定義如下 沿等值線走 大于等值線值的點在等值線的左邊 小于等值線值的點在等值線的右邊 也就是 點在等值線的右邊 點在等值線的左邊 在規(guī)定了等值線的走向后 等值線的連接對于矩形單元可分如下四種情況進行 1 頂點全為 或全為 無等值線段 2 有一個頂點為 或 共可求出兩個交點 有一條等值線段 如圖3 網(wǎng)格序列法 3 有兩個 兩個 頂點的情況 根據(jù)頂點的分布又可分成下面兩種情況 有兩個交點 即兩個 或兩個 的頂點位于同一條單元邊上 等值線段的連接如圖4a所示 有4個交點 即 頂點的分布相互交叉 這時的連接在規(guī)定了函數(shù)的走向后 可確定P R為入點 S Q為出點 連接情況如圖4b所示 在上述 的情況下 如果不規(guī)定等值線的走向 其實存在兩種連接方式 見圖5 在實際情況中 這兩種方式都是可能的 這種二義性的主要原因是在該單元內(nèi)存在一馬鞍點 網(wǎng)格序列法 如何從中選擇一種正確的連接方式呢 這可從單元內(nèi)的雙線性插值函數(shù)分析入手 由于在單元邊上采用了線性插值 由此單元面上函數(shù)值的變化是雙線性的 即等值線在單元內(nèi)不是直線段而是雙曲線 二義性連接可通過求該雙曲線兩條漸近線交點處的函數(shù)值來判定 這是因為漸近線的交點總是與其中一對頂點落入同一區(qū)域內(nèi) 如漸近線交點為 則取圖5a的連接方式 如為 則取圖5b的連接方式 即在圖5a中 表示單元中部為 在圖5b中 表示單元中部為 在實際計算中 為簡化計算 往往采用單元對角線交點代替漸近線交點的計算 單元剖分法 在網(wǎng)格序列法中 提出了解決矩形單元內(nèi)等值線的生成算法 其中馬鞍點二義性的解決是算法的一個主要復(fù)雜點 除此之外人們還提出了單元剖分法 該方法與矩形單元法相比 其主要特點是采用三角片簡化單元內(nèi)等值線的抽取 無需再進行馬鞍點的判定 但處理的單元數(shù)是原來的四倍 算法的基本思想是利用對角線將矩形單元分成四個三角形單元 見圖6 求出中心點的函數(shù)值 等值線的抽取直接在每個三角片中進行 由于每一個三角片至多只包含一條等值線 因而在由三角片的三個點決定的平面內(nèi) 可直接用直線段連接等值線 單元剖分法 中心點函數(shù)值Fmid的計算可采用兩種方式 如有顯式函數(shù)F x y 則Fmid F xmid ymid 如只有四個點的函數(shù)值 無法求顯式函數(shù)形式 則可用四點的平均值代替Fmid 圖7列出了幾種可能的情況 可以看出 通過利用矩形單元中點的函數(shù)值 等值線的精度提高了 其抽取過程也相對簡單些 第4章等值面的生成 所謂等值面是指空間中的一個曲面 在該曲面上函數(shù)F x y z 的值等于某一給定值Ft 即等值面是由所有點SFt x y z F x y z Ft 組成的一個曲面 等值面技術(shù)在可視化中應(yīng)用很廣 許多標量場的可視化問題都可歸納為等值面的抽取和繪制 如各種等勢面 等位面 等壓面 等溫面等 等值面技術(shù)除生成等值面的幾何表示外 還包括顯示技術(shù) 如要考慮合適的光照模型 解決等值面的相互遮擋等 等值面的生成和顯示也是可視化研究中的一個重要領(lǐng)域 一Cuberille方法 立方體方法 Cuberrille等值面方法又稱OpaqueCube算法 最初由Herman等人提出 后來又多次改進 算法主要分為兩個步驟 1 確定邊界單元對于規(guī)則網(wǎng)格數(shù)據(jù) 其網(wǎng)格單元可看成是正六面體單元 整個三維數(shù)據(jù)就是由這種正六面體組成的 這種組成三維圖象的基本正六面體單元稱為體元 對于給定的閾值Ft 遍歷體數(shù)據(jù)中的各個單元 將組成體元8個頂點上的值與Ft進行比較 找出頂點值跨越Ft的所有體元 即體元中有的頂點值大于閾值 有的頂點值小于閾值 因此體元內(nèi)包含等值面片 這就是邊界單元 2 繪制各邊界單元的6個多邊形面 即將等值面看成是由各單元的六個外表面拼合而成 Cuberille方法 立方體方法 每個單元均為一正六面體 包括6個多邊形面 對組成所有邊界體元的多邊形面進行繪制 即可產(chǎn)生最終的圖象結(jié)果 在繪制多邊形過程中應(yīng)采用合適的光照模型和消隱技術(shù) 如果在具有硬件深度緩存 Z buffer 功能的計算機上運行立方體方法 可以將這組多邊形不分次序地提交給硬件 由硬件完成消除隱藏面的任務(wù) 如果以軟件方式執(zhí)行立方體方法 在算法中必須考慮多邊形的遮擋問題 一個有效的方法是把遍歷體元集合與顯示兩個步驟合二為一 遍歷體元集合時采用從后至前的次序 發(fā)現(xiàn)一個邊界體元 就立刻顯示它的6個面 后顯示到屏幕上去的多邊形將覆蓋先顯示的多邊形 這樣就達到了消除隱藏面的目的 這就是畫家算法的思想 Cuberille方法 立方體方法 Cuberrille算法的主要優(yōu)點是簡單易行 其主要缺點是出現(xiàn)嚴重的走樣 顯示的圖象給人一種 塊狀的感覺 尤其在物體邊界處鋸齒形走樣特別明顯 而且畫面較粗糙 不能很好地顯示對象的細節(jié) 立方體法的另一個缺點是面的重疊冗余問題 兩個相鄰邊界體元的公共面重復(fù)出現(xiàn) 實際上它們都不會出現(xiàn)在顯示畫面上 因為無論從哪個角度進行觀察 它們都會被這兩個體元的其它面遮擋 改進的立方體法刪除了邊界體元之間的公共面 減少了顯示過程需要處理的多邊形的數(shù)量 二MarchingCubes MC 方法 MarchingCubes 移動立方體 方法是由W E Lorenson和H E Cline在1987年提出來的 由于這一方法原理簡單 易于實現(xiàn) 目前已經(jīng)得到了較為廣泛的應(yīng)用 成為三維數(shù)據(jù)等值面生成的經(jīng)典算法 MarchingCubes算法又簡稱為MC算法 1 MC方法的基本原理在MarchingCubes方法中 假定原始數(shù)據(jù)是離散的三維空間規(guī)則數(shù)據(jù) 一個體元定義為由相鄰層上的8個頂點組成的一個長方體 為了在三維數(shù)據(jù)中構(gòu)造等值面 應(yīng)先給定所求等值面的值 該方法的基本原理是逐個處理所有的體元 將體元各頂點處的值與給定的閾值進行比較 首先找出與等值面相交的體元 然后通過插值求等值面與體元棱邊的交點 并將各交點連成三角形來構(gòu)成等值面片 所有體元中的三角形集合就構(gòu)成了等值面 由于這一方法是逐個處理所有的體元 因此被稱為MarchingCubes方法 MC方法的主要步驟如下 MarchingCubes MC 方法 1 確定包含等值面的體元及對應(yīng)的等值面片模式一個體元由8個數(shù)據(jù)點構(gòu)成 這8個數(shù)據(jù)點分別位于該體元的8個頂點上 首先對體元的8個頂點進行分類 判定是位于等值面之外 還是位于等值面之內(nèi) 再根據(jù)8個頂點的狀態(tài) 確定等值面的模式 設(shè)等值面的值為Ft 頂點分類規(guī)則為 若某頂點的值 Ft 則定義該頂點位于等值面之外 記為 0 若某頂點的值 Ft 則定義該頂點位于等值面之內(nèi) 記為 1 如果某體元一條邊的一個頂點在等值面之內(nèi) 而另一個頂點在等值面之外 那么 該邊必然與等值面相交 根據(jù)這一原理就可以判斷所求等值面將與哪些體元相交 或者說將穿過哪些體元 MarchingCubes MC 方法 由于每個體元有8個頂點 每個頂點又有0 1兩種狀態(tài) 因此每個體元按其8個頂點的0 1分布而言 共有28 256種不同的狀態(tài) 盡管判斷等值面將與哪些體元相交在原理上很容易理解 但是要根據(jù)這256種不同的情況求出每個體元中的等值面卻是很繁瑣的 而且也容易出錯 可以利用兩種不同的對稱性將256種不同的情況簡化為15種 互補對稱性 如果將一個體元的頂點狀態(tài)顛倒 即 0 變成 1 1 變成 0 則等值面與體元中8個頂點之間的拓撲關(guān)系將不會改變 該體元與等值面的相交情況與原來一致 即新生成的等值面與原等值面是相同的 也就是說 大于等值面的點與小于等值面的點是可以相互替換的 因此 只要考慮4個以下 含4個 的頂點值大于Ft就夠了 根據(jù)這種互補對稱性 可將體元的模式由256種減少為128種 MarchingCubes MC 方法 旋轉(zhuǎn)對稱性 如果某一模式的體元經(jīng)過旋轉(zhuǎn)后與另一模式的體元一致 即頂點位置及其狀態(tài)值相同 那么這兩種模式的體元可以合并為一種 根據(jù)這種旋轉(zhuǎn)對稱性 體元模式可以最終歸納為15種 見圖2 其中第0種情況表示所有8個頂點的值均大于 或小于 Ft 因而該體元與等值面不相交 第一種情況表示有一個頂點的函數(shù)值大于 或小于 Ft 其余7個頂點均與此相反 因而該體元內(nèi)的等值面將是一個三角面片 在考慮了上面兩種對稱性后 這一種情況實際上代表了16種情況 如此類推 圖2中的15種模式反映了一個體元中8個頂點可能存在的全部256種狀態(tài) 在實現(xiàn)時 對一個體元可按照它的8個頂點的狀態(tài)構(gòu)造一個一字節(jié) 8位 的狀態(tài)表 如圖3所示 其中的每一位表示該體元中一個頂點的0或1狀態(tài) 根據(jù)這個狀態(tài)表就可判斷出當(dāng)前體元屬于哪一種模式 等值面將與哪一條邊相交以及體元內(nèi)三角面片的連接方式 MarchingCubes MC 方法 2 計算等值面與體元邊界的交點 并連接成三角形當(dāng)三維離散數(shù)據(jù)的密度較高 即每個體元很小時 可以假定函數(shù)值沿體元邊界呈線性變化 因此 等值面與體元邊界的交點可以通過該邊兩端點函數(shù)值的線性插值求出 公式為 求出了等值面與體元邊界的交點以后 就可以按對應(yīng)的模式將這些交點連接成三角形 構(gòu)成該單元中的等值面片 MarchingCubes MC 方法 3 計算等值面的法向為了繪制等值面的真實感圖象 還必須給出構(gòu)成等值面的各三角面片的法向 對于等值面上的每一點 沿該面切線方向的梯度分量應(yīng)該是零 因此該點的梯度矢量的方向就代表了等值面的法向 MC方法就是利用這一原理來計算三角面片的法向 即對于三維規(guī)則網(wǎng)格數(shù)據(jù) 可以直接采用中心差分計算體元各頂點處的梯度 公式為 三角形頂點處的法向量可由體元邊界兩端點處的梯度再通過線性插值求得 在實際繪制等值面時 為了消除各三角面片之間明暗的不連續(xù)變化 只要給出三角面片各頂點處的法向并采用哥羅得 Gouraud 模型繪制各個三角面片即可 在計算機圖形學(xué)中 光滑的曲面常用多邊形來逼近 這是因為處理平面比處理曲面容易得多 例如 為了表示一個磨光的立方體的頂角 可使用7個平面片來近似 但是 若單純使用平面來繪制這種近似表面 生成的圖形將失去原有曲面的光滑性 而呈現(xiàn)多面體狀 這是由于平面上所有點的法向相同 不同平面塊之間存在不連續(xù)的法向量變化 從而引起不連續(xù)的光亮度跳躍 如何能以較少的計算量來解決上述問題呢 最簡單的方法就是Gouraud明暗處理技術(shù) Gouraud明暗處理的思想是對離散的光亮度作雙線性插值以獲得連續(xù)的光亮度函數(shù) 具體做法是 先計算出多邊形頂點處的光亮度值 把它們作為曲面光亮度的采樣點 然后根據(jù)多邊形頂點處的光亮度值進行插值求多邊形內(nèi)任一點的光亮度 若采用掃描線繪制算法 則可沿當(dāng)前掃描線進行雙線性插值 這是一種簡便易行的插值方法 即先用多邊形頂點的光亮度值由線性插值求出當(dāng)前掃描線與多邊形交點處的光亮度 然后根據(jù)交點的光亮度值再通過線性插值求出掃描線上位于多邊形內(nèi)每一象素點的光亮度值 圖4 a 顯示一掃描線與多邊形相交 交點為a點和b點 p是掃描線上位于多邊形內(nèi)的任一點 多邊形三個頂點的光亮度分別為I1 I2和I3 取a點的光亮度Ia為I1和I2的線性插值 b點的光亮度Ib為I1和I3的線性插值 p點的光亮度則為Ia和Ib的線性插值 即 其中u v t稱為插值參數(shù) 相當(dāng)于以端點為原點歸一化后的長度坐標 采用Gouraud明暗處理不但可以克服用多邊形表示曲面時光亮度的不連續(xù)現(xiàn)象 而且計算量也很小 事實上 由于線性插值可使用增量法進行計算 其運算量僅涉及一次加法運算 如在上例中 可沿掃描線從左至右的順序計算AB區(qū)段上所有象素的光亮度 設(shè)Ia和Ib已經(jīng)確定 p1和p2點是相鄰兩象素的坐標 a b兩點的插值參數(shù)之差為 t 那么 不難發(fā)現(xiàn)p2點光亮度Ip2和p1點光亮度Ip1之間有下列關(guān)系 由于 I在同一掃描線上為常數(shù) 因此計算一相鄰象素的光亮度僅需一次加法運算 這種增量方式的光亮度計算使Gouraud明暗處理廣泛用于實時圖形生成 在Gouraud明暗處理中 計算多邊形頂點的光亮度可采用Phong光照模型 MarchingCubes MC 方法 4 用MC方法求等值面的算法流程 將三維離散規(guī)則數(shù)據(jù)分層讀入內(nèi)存 掃描其中兩層數(shù)據(jù) 逐個構(gòu)造這兩層之間的體元 每個體元中的8個頂點取自相鄰的兩層 將體元各個頂點的值與給定的等值面值Ft進行比較 根據(jù)比較的結(jié)果進行分類 構(gòu)造該體元的狀態(tài)表 根據(jù)狀態(tài)表 查得與該狀態(tài)值對應(yīng)的等值面分布模式 確定將與等值面相交的體元邊界 通過線性插值 計算體元邊界與等值面的交點坐標 按對應(yīng)的模式將這些交點連接成三角形 構(gòu)成該單元中的等值面片 利用中心差分方法 求出體元各頂點處的梯度 再次通過線性插值方法 求出三角形各頂點處的法向 根據(jù)各三角面片各頂點的坐標值及法向量繪制等值面圖象 MarchingCubes MC 方法 2 MC方法的加速算法MarchingCube方法是逐個單元地檢測是否存在等值面 還要計算等值面與體元邊界的交點 再由標準的連接模式將各個交點連接成等值面片 事實上 據(jù)研究 真正與等值面相交的體元占總數(shù)據(jù)量很小的一部分 至多10 左右 計算過程中30 70 的時間用在了空體元的檢測上 從加快MarchingCube方法的角度出發(fā) 有必要研究一種快速有效的空間數(shù)據(jù)的遍歷方法和相應(yīng)的數(shù)據(jù)表達形式 以加速對空體元的檢測和排除 另一方面 對于一條與等值面相交的體元的邊 它同時被四個單元共用 這表明在這四個單元內(nèi)求等值面時都要用到這個交點 保存該交點的位置及法向量對于加速算法具有重要意義 對于規(guī)則網(wǎng)格數(shù)據(jù) 其體元是一個六面體單元 若采用空間八叉樹來表示這種體數(shù)據(jù) 則可以加快運算速度 MarchingCube方法的另一個重要問題是抽取的等值面三角片數(shù)量巨大 有時一個體元可以生成多達12個三角片 當(dāng)三維數(shù)據(jù)的數(shù)據(jù)量很大時 三角片的數(shù)量也非常大 這給等值面的繪制和交互操作帶來很大困難 Schroeder提出了在不影響圖形質(zhì)量的情況下 通過對原等值面三角片網(wǎng)重排結(jié)點 合并簡化 生成最優(yōu)化意義下的Delaunay三角化網(wǎng) 可以有效加快圖形的實時顯示 這對于MarchingCube方法的實用是非常有意義的 MarchingCubes MC 方法 3 MC方法存在的問題 1 MC方法構(gòu)造的三角面片是三維等值面的近似表示首先 在MC方法中 等值面與體元邊界的交點是基于函數(shù)值在體元邊界上呈線性變化這一假設(shè)而求出的 當(dāng)數(shù)據(jù)密度高 體元很小時 這一假設(shè)接近于實際情況 但是 在稀疏數(shù)據(jù)中 體元較大 如果仍然認為函數(shù)值在體元邊界上呈線性變化 將會產(chǎn)生較大誤差 這時 需要根據(jù)不同的具體情況對函數(shù)值沿體元邊界的變化作其它適當(dāng)?shù)募僭O(shè) 才能較準確地求出等值面 其次 即使函數(shù)值沿體元邊界作線性變化這一假設(shè)符合實際 那么通過線性插值求得的交點位置是準確的 但是 將體元中同一個面上兩條相鄰邊上的交點簡單地用直線連接起來也是一種近似 如下圖所示 為了說明這一問題 需要引入當(dāng)體元各邊界上函數(shù)值均為線性變化時的等值面模型 如圖3 5所示 P x y z 為小體元中的任意點 體元中的數(shù)據(jù)沿x y z三個方向均是線性變化的 如果點P1 P2為點P沿y軸在立方體兩個面上的投影 P11 P12 P21 P22分別為P1 P2點沿z軸在立方體平面上的投影 設(shè)V為y軸上的坐標分量 f為函數(shù)值 那么 通過三次線性插值 可得 1 其中P1 P2兩點的值可由P11 P12和P21 P22插值求得 而P11 P12 P21 P22四個點的值又可以由它們所在體元內(nèi)的一條邊上的兩個頂點插值得到 這樣 通過三次線性插值運算 就可以求得P x y z 點的函數(shù)值 1 式可具體展開為 其中系數(shù)ai i 0 7 取決于體元8個頂點處的函數(shù)值 如果給定的等值面的值為Ft 那么 等值面就被定義為滿足如下方程的點的集合 2 改變Ft的值 就可以得到不同等值面的表達式 由上述等值面方程可以方便地求出某等值面與體元邊界面的交線方程 不失一般性 設(shè)某邊界面所在平面的方程為z z0 代入方程式 2 可得 3 上式可進一步表示為 4 顯然 上述方程表示的是一條雙曲線 即等值面與體元中某一個面的交線是一條雙曲線或其中的一支 如果用一條直線來表示這條雙曲線 則會引起誤差 如圖所示 如果體元很小 這一誤差是可以忽略不記的 對于稀疏的三維數(shù)據(jù) 這種近似引起的誤差是難以接受的 可通過自適應(yīng)剖分算法將三角形按給定的逼近精度遞歸地分成子三角形 使這些子三角形的頂點滿足方程 3 且子三角形與等值面的最大距離小于給定的容差 MarchingCubes MC 方法 2 連接方式上的二義性MarchingCubes方法可以看成是二維等值線網(wǎng)格序列法在三維空間中的推廣 在網(wǎng)格序列法中 如果矩形網(wǎng)格單元4個頂點中有兩個頂點的值大于等值線的值 另兩個頂點的值小于等值線的值 且這兩個頂點交叉分布 那么等值線的連接就出現(xiàn)二義性 同理 在MarchingCubes方法中 如果正六面體單元的6個矩形表面中出現(xiàn)與此相同的情形 那么該正六面體單元中的等值面連接必然會出現(xiàn)二義性 這樣的面稱為二義性面 包含1個以上的二義性面的體元 即為具有二義性的體元 如下圖所示 事實上 在MarchingCubes方法的15種模式中 第3 6 7 10 12 13等6種情況是具有二義性的 MarchingCubes MC 方法 4 用雙曲線漸近線方法判別和消除二義性MC方法存在連接方式的二義性問題在該方法提出后不久 就由M J Durst提出來了 這一問題如果不解決 將造成等值面連接上的錯誤 如在兩個相鄰體元的公共面上 可能會出現(xiàn)兩種不同的連接方式 從而形成空洞 盡管人們已經(jīng)提出了幾種不同的判別和消除二義性的方法 但以G M Nielson等人提出的漸近線法 1991 最為常用 如前所述 在一般情況下 等值面與體元邊界面所在平面的交線是一條雙曲線或其中的一支 該雙曲線的兩支及其漸近線與體元的一個邊界面的相對位置關(guān)系可用下圖5來表示 在該圖所列的四種狀態(tài)中 當(dāng)雙曲線的兩支均與體元的某邊界面相交時 就會出現(xiàn)連接方式的二義性 在出現(xiàn)二義性的情況中 雙曲線的兩支將邊界面劃分為3個區(qū)域 顯然 雙曲線漸近線的交點總是和邊界面中呈對角分布的一對頂點落在同一區(qū)域內(nèi) 這一性質(zhì)就成為解決二義性問題的基礎(chǔ) 根據(jù) 4 式 漸近線方程可寫為 當(dāng)出現(xiàn)二義性時 需要計算f x y z0 的值 如果f x y z0 Ft 則漸近線的交點應(yīng)與數(shù)值大于Ft的一對頂點落在同一區(qū)域 如圖6 a 所示 可連接M1M2 M3M4 否則漸近線交點與數(shù)值小于Ft的一對頂點落在同一區(qū)域 如圖6 b 所示 可連接M1M3 M2M4 在圖6中 當(dāng)f x y z0 Ft時 對漸進線的交點標以正值 其對應(yīng)的二義面稱為正值二義面 記為PAF 當(dāng)f x y z0 Ft時 對漸進線的交點標以負值 其對應(yīng)的二義面稱為負值二義面 記為NAF 在所列的全部15種模式中 第0 1 2 4 5 8 9 11 14這9種模式下不存在二義性面 因而它們只存在1種連接方式 第3 6兩種模式 各存在一個二義性面 因此各有兩種連接方式 第10 12兩種模式 各存在兩個二義性面 因而各有4種連接方式 第7種模式有3個二義性面 因而有8種連接方式 第13種模式有6個二義性面 因而有64種連接方式 將以上各種情況加在一起 共有93種不同的連接方式 對于存在二義性的體元 按上述方法解決二義性問題 雖然增加了計算工作量 但是為了得出完全正確的結(jié)果卻是十分必要的 三MarchingTetrahedra MT 方法 MarchingTetrahedra方法簡稱為MT方法 亦稱四面體剖分法 它是在MC方法的基礎(chǔ)上發(fā)展起來的 該方法首先將立方體單元剖分為四面體 然后在其中構(gòu)造等值面 提出這種方法的原因很多 首先 由于四面體是最簡單的多面體 其它類型的多面體都能剖分為四面體 其次 將立方體剖分為四面體后 在四面體中構(gòu)造的等值面的精度要比在立方體中構(gòu)造的等值面要高 而最直接的原因是企圖通過在四面體內(nèi)構(gòu)造等值面來避免MC方法中存在的二義性問題 1 MT方法的基本原理及存在的問題可以將一個立方體剖分為5個 6個和24個四面體 5個或6個四面體的剖分是一種不對稱的剖分 剖分后的四面體不全等 24個四面體的剖分是一種全等四面體的剖分 常用的MT方法是將一個立方體剖分為5個四面體 與前述的方法一樣 假定待求的等值面的值為Ft 如果四面體頂點的值大于 或等于 Ft 則將該頂點賦以 號 如果小于Ft 則將該頂點賦以 號 假設(shè)在四面體的邊上數(shù)據(jù)呈線性變化 在考慮了 號反號造成的對稱情況后 對于每個四面體 等值面模式只有三種情況 如圖7所示 如果4個頂點全為 或全為 等值面與該四面體無交點 如一個頂點為 而另外3個頂點為 則該四面體中等值面是一個三角片 如有兩個頂點為 而另外2個頂點為 則該四面體中等值面是一個四邊形 可分解為兩個三角片 將各三角片拼接起來即可構(gòu)成等值面 這就是MT方法的基本原理 雖然在每一個四面體內(nèi) 等值面的生成是由頂點函數(shù)值的分布情況唯一確定的 但是 對于一個立方體來說 卻有兩種不同的四面體剖分方式 不同的剖分方式將生成不同的等值面 即等值面的結(jié)果依賴于剖分方式 另一方面 為了在相鄰體元的公共面上不出現(xiàn)裂縫 必須保證在這個面上的剖分一致性 也就是說 四面體的剖分方式在一系列體元中是交替變化的 這樣一來 三維數(shù)據(jù)內(nèi)等值面的構(gòu)造是與最初一個體元的剖分方式有關(guān)的 因此MT方法并不能消除等值面構(gòu)造中的二義性 這仍然是一個有待解決的問題 2 MT方法中二義性的判別和消除當(dāng)一個立方體剖分為5個四面體時 在每一個四面體的6條邊中 有些是原有立方體的棱 而另一些則是立方體6個面上的對角線 經(jīng)過仔細研究 在5個四面體的30條邊中 只有12條邊是原有立方體的棱 而其余18條則均為立方體面上的對角線 這就提出了一個問題 即當(dāng)立方體每條棱上的函數(shù)值呈線性變化時 立方體每個面中對角線上的函數(shù)值是否也呈線性變化呢 如果不是 那么當(dāng)該對角線兩端點均為 或 時 就認為在該線段上沒有交點 又是否能成立呢 前面論述過 當(dāng)體元每條棱上的函數(shù)值均呈線性變化時 體元內(nèi)等值面與體元邊界面的交線是由 3 式表示的一條雙曲線 設(shè)體元中一個面所在的平面為z z0 該面上某一對頂點的坐標為 xa ya z0 及 xb yb z0 則由該對頂點構(gòu)成的對角線方程為 5 將 5 式代入 3 式 經(jīng)過整理后可知 沿對角線的函數(shù)值分布為一個二次函數(shù) 并可寫成如下形式 6 其中A B C是由對角線端點坐標及體元的8個頂點的函數(shù)值決定的常數(shù) 既然沿對角線的函數(shù)值分布為二次函數(shù) 那么當(dāng)對角線兩端點均為 或 時 就不能簡單地認為在該對角線上無交點 而需要求解 6 式才能得出結(jié)果 于是 判斷對應(yīng)于閾值為Ft的等值面是否與該對角線相交 就需要判斷方程式 6 在區(qū)間 0 1 內(nèi)是否有解 若C 0 且 則方程 6 式將有兩個不同的解t1和t2 如果t1和t2都在區(qū)間 0 1 內(nèi) 那么等值面與對角線有兩個不同的交點 這是當(dāng)對角線兩端點的函數(shù)值為同號時的情況 是不能被忽略的 在這種情況下 等值面與體元對角線相交的多種可能性如圖8所示 圖8等值面與體元對角線相交的多種可能性 圖8 a 表明 只有一條雙曲線通過體元的面并與對角線有兩個交點 但此刻 該對角線兩端點的函數(shù)值均為 圖8 b 和 c 表示兩條雙曲線都通過該面 這是MC方法中的二義面 在圖8 b 中 兩條漸近線的交點與為 的對角線兩端點取異號 而在圖8 c 中 兩條漸近線的交點與為 的對角線兩端點取同號 在這兩種情況下 根據(jù)判別式計算結(jié)果 該等值線均與對角線有兩個交點 如果認為該對角線兩端點的函數(shù)值均為 而忽略這兩個交點 將導(dǎo)致等值線的錯誤連接 如圖8 d 所示 或等值線的連接不準確 如圖8 e 所示 而這正是傳統(tǒng)的MT方法所存在的問題 綜上所述 在MT方法中判斷四面體的一條邊與等值面是否有交點及計算交點的算法可描述如下 如果E1E2是原體元的一條邊 如果該邊兩端點所賦值異號 則通過線性插值計算交點 等值點 并輸出否則 沒有交點 否則 如果兩端點函數(shù)值同號而相應(yīng)的判別式非負則解一元二次方程式計算兩個交點 并輸出落在兩端點間的交點如果兩端點函數(shù)值異號計算兩交點 取落在兩端點間的點為交點 并輸出舍去另一點 3 連接等值點構(gòu)造多邊形在正確地計算出四面體各條邊上的交點 即等值點以后 下一步就應(yīng)該將一個四面體內(nèi)所有等值點連接成有效的多邊形 為此 需要首先考慮四面體中任一三角面片上等值點的連接 為了保證相鄰四面體在公共面上等值面的連接不出現(xiàn)裂縫 等值面被公共面所截得的交線應(yīng)該由公共面的性質(zhì)唯一決定 而不受它所在的四面體中其它頂點的影響 與此同時 三角形上等值點的連線不能與三角形的任何一條邊重合 且連線不能交叉 由于等值點的連線就是等值線 所以這樣的假設(shè)自然是合理的 對于一個三角形來說 根據(jù)頂點的函數(shù)值所賦予的符號及等值點的分布 可以分為6種狀態(tài) 具體可參見唐澤圣 三維數(shù)據(jù)場可視化 P101 P103 當(dāng)實現(xiàn)了四面體每一個三角形內(nèi)等值點的連接以后 不同三角形內(nèi)的連接線在三角形的公共邊上首尾相連即可形成多邊形 首先從一個三角形內(nèi)任取一條連線 在該線段末端點所在的另一個三角形內(nèi)找到以該點為起點的下一條邊 并對訪問過的線段做上標記 依次找下去 直到與最初的邊相遇 即構(gòu)成一封閉的多邊形 接著 判斷是否還有未訪問過的線段 如果有 從中取出一條重復(fù)上述的過程 直至所有的多邊形都輸出為止 由此可以看出 四面