等值線等值面的生成課件

1、等值線等值面的生成課件第第3 3章章 二維標(biāo)量場等值線的生成二維標(biāo)量場等值線的生成 二維標(biāo)量場可看成是定義于某一個(gè)面上的二維標(biāo)量函二維標(biāo)量場可看成是定義于某一個(gè)面上的二維標(biāo)量函數(shù)數(shù)F=F(x, y)，所謂等值線是由所有點(diǎn)，所謂等值線是由所有點(diǎn)(xi, yi)構(gòu)成，其中構(gòu)成，其中F(xi, yi) =Ft（為一給定值），將這些點(diǎn)按一定順序連接起（為一給定值），將這些點(diǎn)按一定順序連接起來就組成了函數(shù)值為來就組成了函數(shù)值為Ft的等值線。對于二維標(biāo)量場，其數(shù)的等值線。對于二維標(biāo)量場，其數(shù)據(jù)往往是分布在規(guī)則網(wǎng)格點(diǎn)上的，常用的等值線抽取方法據(jù)往往是分布在規(guī)則網(wǎng)格點(diǎn)上的，常用的等值線抽取方法有網(wǎng)格序列法和單

2、元剖分法。有網(wǎng)格序列法和單元剖分法。等值線等值面的生成課件網(wǎng)格序列法網(wǎng)格序列法 網(wǎng)格序列法網(wǎng)格序列法(grid sequence)的基本思想是按網(wǎng)格單元的排列次序，的基本思想是按網(wǎng)格單元的排列次序，逐個(gè)處理每一單元，尋找每一單元內(nèi)相應(yīng)的等值線段，在處理完逐個(gè)處理每一單元，尋找每一單元內(nèi)相應(yīng)的等值線段，在處理完所有單元后，就自然生成了該網(wǎng)格中的等值線分布。所有單元后，就自然生成了該網(wǎng)格中的等值線分布。 規(guī)則網(wǎng)格數(shù)據(jù)等值線的生成規(guī)則網(wǎng)格數(shù)據(jù)等值線的生成 設(shè)一規(guī)則網(wǎng)格數(shù)據(jù)如圖所示，網(wǎng)格線是相互正交的，每一網(wǎng)格單設(shè)一規(guī)則網(wǎng)格數(shù)據(jù)如圖所示，網(wǎng)格線是相互正交的，每一網(wǎng)格單元是一矩形，其中四個(gè)頂點(diǎn)分別為元是

3、一矩形，其中四個(gè)頂點(diǎn)分別為(x0, y0)、(x0, y1)、(x1, y0)、(x1, y1)，對應(yīng)的值分別為，對應(yīng)的值分別為F00、F01、F10、F11。要在該單元內(nèi)生成值。要在該單元內(nèi)生成值為為Ft的等值線，其主要計(jì)算步驟為：的等值線，其主要計(jì)算步驟為： 逐個(gè)計(jì)算每一網(wǎng)格單元與等值線的交點(diǎn)；逐個(gè)計(jì)算每一網(wǎng)格單元與等值線的交點(diǎn)； 連接該單元內(nèi)等值線的交點(diǎn)，生成在該單元中的等值線線段；連接該單元內(nèi)等值線的交點(diǎn)，生成在該單元中的等值線線段； 由一系列單元內(nèi)的等值線線段構(gòu)成該網(wǎng)格中的等值線。由一系列單元內(nèi)的等值線線段構(gòu)成該網(wǎng)格中的等值線。 網(wǎng)格單元與等值線的交點(diǎn)計(jì)算主要是求各單元的邊線與等值線

4、的網(wǎng)格單元與等值線的交點(diǎn)計(jì)算主要是求各單元的邊線與等值線的交點(diǎn)。假設(shè)函數(shù)在單元內(nèi)呈線性變化，可以采用頂點(diǎn)判定，邊上交點(diǎn)。假設(shè)函數(shù)在單元內(nèi)呈線性變化，可以采用頂點(diǎn)判定，邊上插值的方法計(jì)算交點(diǎn)，具體步驟為：插值的方法計(jì)算交點(diǎn)，具體步驟為：等值線等值面的生成課件網(wǎng)格序列法網(wǎng)格序列法 (1) 將網(wǎng)格點(diǎn)分為將網(wǎng)格點(diǎn)分為“IN”和和“OUT”兩種狀態(tài)，表示該點(diǎn)在等值線兩種狀態(tài)，表示該點(diǎn)在等值線內(nèi)，或在等值線外。如果內(nèi)，或在等值線外。如果FijFt，則頂點(diǎn)，則頂點(diǎn)(xi, yj)為為“IN”，記為，記為“”；如果；如果FijFt，則頂點(diǎn)，則頂點(diǎn)(xi, yj)為為“OUT”，記為，記為“”。 (2) 如果單

5、元四個(gè)頂點(diǎn)全為如果單元四個(gè)頂點(diǎn)全為“”，或全為，或全為“”，則網(wǎng)格單元，則網(wǎng)格單元與值為與值為Ft的等值線無交點(diǎn)，否則的等值線無交點(diǎn)，否則 (3) 對于兩個(gè)頂點(diǎn)分別為對于兩個(gè)頂點(diǎn)分別為“”、“”的單元邊，可用線性插的單元邊，可用線性插值計(jì)算等值線在這條邊上的交點(diǎn)。值計(jì)算等值線在這條邊上的交點(diǎn)。 如圖所示，如圖所示，(x0, y0) 為為“”，(x0, y1) 為為“”，則交點(diǎn)為，則交點(diǎn)為00010010100100010000)()()(FFFFyFFyyyFFFFyyxxttttt等值線等值面的生成課件網(wǎng)格序列法網(wǎng)格序列法 在每一單元內(nèi)計(jì)算出等值線與該網(wǎng)格單元邊的交點(diǎn)后，利用這些在每一單元內(nèi)

6、計(jì)算出等值線與該網(wǎng)格單元邊的交點(diǎn)后，利用這些交點(diǎn)，就能構(gòu)成在該單元內(nèi)的等值線段。為了正確地連接交點(diǎn)生交點(diǎn)，就能構(gòu)成在該單元內(nèi)的等值線段。為了正確地連接交點(diǎn)生成等值線段，必須規(guī)定等值線的方向。等值線的方向定義如下：成等值線段，必須規(guī)定等值線的方向。等值線的方向定義如下： 沿等值線走，大于等值線值的點(diǎn)在等值線的左邊，小于等值線值沿等值線走，大于等值線值的點(diǎn)在等值線的左邊，小于等值線值的點(diǎn)在等值線的右邊。也就是的點(diǎn)在等值線的右邊。也就是“”點(diǎn)在等值線的右邊，點(diǎn)在等值線的右邊，“”點(diǎn)在等值線的左邊。在規(guī)定了等值線的走向后，等值線的連接對點(diǎn)在等值線的左邊。在規(guī)定了等值線的走向后，等值線的連接對于矩形單元

7、可分如下四種情況進(jìn)行：于矩形單元可分如下四種情況進(jìn)行： (1) 頂點(diǎn)全為頂點(diǎn)全為“”，或全為，或全為“”，無等值線段；，無等值線段； (2) 有一個(gè)頂點(diǎn)為有一個(gè)頂點(diǎn)為“”或或“”，共可求出兩個(gè)交點(diǎn)，有一條，共可求出兩個(gè)交點(diǎn)，有一條等值線段，如圖等值線段，如圖3。等值線等值面的生成課件等值線等值面的生成課件網(wǎng)格序列法網(wǎng)格序列法 (3) 有兩個(gè)有兩個(gè)“”，兩個(gè)，兩個(gè)“”頂點(diǎn)的情況，根據(jù)頂點(diǎn)的分布又頂點(diǎn)的情況，根據(jù)頂點(diǎn)的分布又可分成下面兩種情況：可分成下面兩種情況： 有兩個(gè)交點(diǎn)，即兩個(gè)有兩個(gè)交點(diǎn)，即兩個(gè)“”或兩個(gè)或兩個(gè)“”的頂點(diǎn)位于同一條的頂點(diǎn)位于同一條單元邊上，等值線段的連接如圖單元邊上，等值線段

8、的連接如圖4a所示。所示。 有有4個(gè)交點(diǎn)，即個(gè)交點(diǎn)，即“”、“”頂點(diǎn)的分布相互交叉，這時(shí)的頂點(diǎn)的分布相互交叉，這時(shí)的連接在規(guī)定了函數(shù)的走向后，可確定連接在規(guī)定了函數(shù)的走向后，可確定P，R為入點(diǎn)，為入點(diǎn)，S，Q為出點(diǎn)，為出點(diǎn)，連接情況如圖連接情況如圖4b所示。所示。 在上述在上述的情況下，如果不規(guī)定等值線的走向，其實(shí)存在兩種連的情況下，如果不規(guī)定等值線的走向，其實(shí)存在兩種連接方式，見圖接方式，見圖5。在實(shí)際情況中，這兩種方式都是可能的，這種。在實(shí)際情況中，這兩種方式都是可能的，這種二義性的主要原因是在該單元內(nèi)存在一馬鞍點(diǎn)。二義性的主要原因是在該單元內(nèi)存在一馬鞍點(diǎn)。等值線等值面的生成課件等值線等值

9、面的生成課件等值線等值面的生成課件網(wǎng)格序列法網(wǎng)格序列法 如何從中選擇一種正確的連接方式呢？這可從單元內(nèi)的雙線性插如何從中選擇一種正確的連接方式呢？這可從單元內(nèi)的雙線性插值函數(shù)分析入手。由于在單元邊上采用了線性插值，由此單元面值函數(shù)分析入手。由于在單元邊上采用了線性插值，由此單元面上函數(shù)值的變化是雙線性的，上函數(shù)值的變化是雙線性的， 即等值線在單元內(nèi)不是直線段而是雙曲線。二義性連接可通過求即等值線在單元內(nèi)不是直線段而是雙曲線。二義性連接可通過求該雙曲線兩條漸近線交點(diǎn)處的函數(shù)值來判定，這是因?yàn)闈u近線的該雙曲線兩條漸近線交點(diǎn)處的函數(shù)值來判定，這是因?yàn)闈u近線的交點(diǎn)總是與其中一對頂點(diǎn)落入同一區(qū)域內(nèi)，如漸

10、近線交點(diǎn)為交點(diǎn)總是與其中一對頂點(diǎn)落入同一區(qū)域內(nèi)，如漸近線交點(diǎn)為“”，則取圖，則取圖5a的連接方式；如為的連接方式；如為“”，則取圖，則取圖5b的連接方的連接方式。即在圖式。即在圖5a中，表示單元中部為中，表示單元中部為“”，在圖，在圖5b中，表示單元中，表示單元中部為中部為“”。在實(shí)際計(jì)算中，為簡化計(jì)算，往往采用單元對角。在實(shí)際計(jì)算中，為簡化計(jì)算，往往采用單元對角線交點(diǎn)代替漸近線交點(diǎn)的計(jì)算。線交點(diǎn)代替漸近線交點(diǎn)的計(jì)算。xyayaxaayxF3210),(等值線等值面的生成課件單元剖分法單元剖分法 在網(wǎng)格序列法中，提出了解決矩形單元內(nèi)等值線的生成在網(wǎng)格序列法中，提出了解決矩形單元內(nèi)等值線的生成算

11、法，其中馬鞍點(diǎn)二義性的解決是算法的一個(gè)主要復(fù)雜算法，其中馬鞍點(diǎn)二義性的解決是算法的一個(gè)主要復(fù)雜點(diǎn)，除此之外人們還提出了單元剖分法，該方法與矩形點(diǎn)，除此之外人們還提出了單元剖分法，該方法與矩形單元法相比，其主要特點(diǎn)是采用三角片簡化單元內(nèi)等值單元法相比，其主要特點(diǎn)是采用三角片簡化單元內(nèi)等值線的抽取，無需再進(jìn)行馬鞍點(diǎn)的判定，但處理的單元數(shù)線的抽取，無需再進(jìn)行馬鞍點(diǎn)的判定，但處理的單元數(shù)是原來的四倍。是原來的四倍。 算法的基本思想是利用對角線將矩形單元分成四個(gè)三角算法的基本思想是利用對角線將矩形單元分成四個(gè)三角形單元，見圖形單元，見圖6，求出中心點(diǎn)的函數(shù)值，等值線的抽取，求出中心點(diǎn)的函數(shù)值，等值線的抽

12、取直接在每個(gè)三角片中進(jìn)行。由于每一個(gè)三角片至多只包直接在每個(gè)三角片中進(jìn)行。由于每一個(gè)三角片至多只包含一條等值線，因而在由三角片的三個(gè)點(diǎn)決定的平面內(nèi)，含一條等值線，因而在由三角片的三個(gè)點(diǎn)決定的平面內(nèi)，可直接用直線段連接等值線?？芍苯佑弥本€段連接等值線。 等值線等值面的生成課件單元剖分法單元剖分法 中心點(diǎn)函數(shù)值中心點(diǎn)函數(shù)值Fmid的計(jì)算可采用兩種方式：的計(jì)算可采用兩種方式： 如有顯式函數(shù)如有顯式函數(shù)F(x, y)，則，則Fmid = F(xmid, ymid)； 如只有四個(gè)點(diǎn)的函數(shù)值，無法求顯式函數(shù)形式，則可用如只有四個(gè)點(diǎn)的函數(shù)值，無法求顯式函數(shù)形式，則可用四點(diǎn)的平均值代替四點(diǎn)的平均值代替Fmid

13、。 圖圖7列出了幾種可能的情況，可以看出，通過利用矩形列出了幾種可能的情況，可以看出，通過利用矩形單元中點(diǎn)的函數(shù)值，等值線的精度提高了，其抽取過程單元中點(diǎn)的函數(shù)值，等值線的精度提高了，其抽取過程也相對簡單些。也相對簡單些。等值線等值面的生成課件等值線等值面的生成課件等值線等值面的生成課件第第4 4章章 等值面的生成等值面的生成 所謂等值面是指空間中的一個(gè)曲面，在該曲面上函數(shù)所謂等值面是指空間中的一個(gè)曲面，在該曲面上函數(shù)F(x, y, z)的值等于某一給定值的值等于某一給定值Ft，即等值面是由所有點(diǎn)，即等值面是由所有點(diǎn) SFt = (x, y, z)：F(x, y, z) = Ft組成的一個(gè)曲面

14、。組成的一個(gè)曲面。 等值面技術(shù)在可視化中應(yīng)用很廣，許多標(biāo)量場的可視等值面技術(shù)在可視化中應(yīng)用很廣，許多標(biāo)量場的可視化問題都可歸納為等值面的抽取和繪制，如各種等勢面、化問題都可歸納為等值面的抽取和繪制，如各種等勢面、等位面、等壓面、等溫面等。等值面技術(shù)除生成等值面的等位面、等壓面、等溫面等。等值面技術(shù)除生成等值面的幾何表示外，還包括顯示技術(shù)，如要考慮合適的光照模型、幾何表示外，還包括顯示技術(shù)，如要考慮合適的光照模型、解決等值面的相互遮擋等。等值面的生成和顯示也是可視解決等值面的相互遮擋等。等值面的生成和顯示也是可視化研究中的一個(gè)重要領(lǐng)域?；芯恐械囊粋€(gè)重要領(lǐng)域。等值線等值面的生成課件一一 Cube

15、rille方法方法( (立方體方法立方體方法) ) Cuberrille等值面方法又稱等值面方法又稱Opaque Cube算法，最初由算法，最初由Herman等等人提出，后來又多次改進(jìn)。算法主要分為兩個(gè)步驟。人提出，后來又多次改進(jìn)。算法主要分為兩個(gè)步驟。 (1) 確定邊界單元確定邊界單元 對于規(guī)則網(wǎng)格數(shù)據(jù)，其網(wǎng)格單元可看成是正六面體單元，整個(gè)三對于規(guī)則網(wǎng)格數(shù)據(jù)，其網(wǎng)格單元可看成是正六面體單元，整個(gè)三維數(shù)據(jù)就是由這種正六面體組成的，這種組成三維圖象的基本正維數(shù)據(jù)就是由這種正六面體組成的，這種組成三維圖象的基本正六面體單元稱為體元。對于給定的閾值六面體單元稱為體元。對于給定的閾值Ft，遍歷體數(shù)據(jù)中

16、的各個(gè)，遍歷體數(shù)據(jù)中的各個(gè)單元，將組成體元單元，將組成體元8個(gè)頂點(diǎn)上的值與個(gè)頂點(diǎn)上的值與Ft進(jìn)行比較，找出頂點(diǎn)值跨進(jìn)行比較，找出頂點(diǎn)值跨越越Ft的所有體元，即體元中有的頂點(diǎn)值大于閾值，有的頂點(diǎn)值小的所有體元，即體元中有的頂點(diǎn)值大于閾值，有的頂點(diǎn)值小于閾值，因此體元內(nèi)包含等值面片，這就是邊界單元。于閾值，因此體元內(nèi)包含等值面片，這就是邊界單元。 (2) 繪制各邊界單元的繪制各邊界單元的6個(gè)多邊形面，即將等值面看成是由各單元個(gè)多邊形面，即將等值面看成是由各單元的六個(gè)外表面拼合而成。的六個(gè)外表面拼合而成。等值線等值面的生成課件Cuberille方法方法( (立方體方法立方體方法) ) 每個(gè)單元均為一

17、正六面體，包括每個(gè)單元均為一正六面體，包括6個(gè)多邊形面。對組成所有邊界個(gè)多邊形面。對組成所有邊界體元的多邊形面進(jìn)行繪制，即可產(chǎn)生最終的圖象結(jié)果。在繪制多體元的多邊形面進(jìn)行繪制，即可產(chǎn)生最終的圖象結(jié)果。在繪制多邊形過程中應(yīng)采用合適的光照模型和消隱技術(shù)。邊形過程中應(yīng)采用合適的光照模型和消隱技術(shù)。 如果在具有硬件深度緩存如果在具有硬件深度緩存(Z-buffer)功能的計(jì)算機(jī)上運(yùn)行立方體功能的計(jì)算機(jī)上運(yùn)行立方體方法，可以將這組多邊形不分次序地提交給硬件，由硬件完成消方法，可以將這組多邊形不分次序地提交給硬件，由硬件完成消除隱藏面的任務(wù)。如果以軟件方式執(zhí)行立方體方法，在算法中必除隱藏面的任務(wù)。如果以軟件

18、方式執(zhí)行立方體方法，在算法中必須考慮多邊形的遮擋問題。一個(gè)有效的方法是把遍歷體元集合與須考慮多邊形的遮擋問題。一個(gè)有效的方法是把遍歷體元集合與顯示兩個(gè)步驟合二為一，遍歷體元集合時(shí)采用從后至前的次序。顯示兩個(gè)步驟合二為一，遍歷體元集合時(shí)采用從后至前的次序。發(fā)現(xiàn)一個(gè)邊界體元，就立刻顯示它的發(fā)現(xiàn)一個(gè)邊界體元，就立刻顯示它的6個(gè)面。后顯示到屏幕上去個(gè)面。后顯示到屏幕上去的多邊形將覆蓋先顯示的多邊形，這樣就達(dá)到了消除隱藏面的目的多邊形將覆蓋先顯示的多邊形，這樣就達(dá)到了消除隱藏面的目的，這就是畫家算法的思想。的，這就是畫家算法的思想。等值線等值面的生成課件Cuberille方法方法( (立方體方法立方體方

19、法) ) Cuberrille算法的主要優(yōu)點(diǎn)是簡單易行，其主要缺點(diǎn)是算法的主要優(yōu)點(diǎn)是簡單易行，其主要缺點(diǎn)是出現(xiàn)嚴(yán)重的走樣，顯示的圖象給人一種出現(xiàn)嚴(yán)重的走樣，顯示的圖象給人一種“塊狀的感覺塊狀的感覺”，尤其在物體邊界處鋸齒形走樣特別明顯，而且畫面較粗尤其在物體邊界處鋸齒形走樣特別明顯，而且畫面較粗糙，不能很好地顯示對象的細(xì)節(jié)。糙，不能很好地顯示對象的細(xì)節(jié)。 立方體法的另一個(gè)缺點(diǎn)是面的重疊冗余問題。兩個(gè)相鄰立方體法的另一個(gè)缺點(diǎn)是面的重疊冗余問題。兩個(gè)相鄰邊界體元的公共面重復(fù)出現(xiàn)，實(shí)際上它們都不會出現(xiàn)在邊界體元的公共面重復(fù)出現(xiàn)，實(shí)際上它們都不會出現(xiàn)在顯示畫面上，因?yàn)闊o論從哪個(gè)角度進(jìn)行觀察，它們都會顯

20、示畫面上，因?yàn)闊o論從哪個(gè)角度進(jìn)行觀察，它們都會被這兩個(gè)體元的其它面遮擋。改進(jìn)的立方體法刪除了邊被這兩個(gè)體元的其它面遮擋。改進(jìn)的立方體法刪除了邊界體元之間的公共面，減少了顯示過程需要處理的多邊界體元之間的公共面，減少了顯示過程需要處理的多邊形的數(shù)量。形的數(shù)量。等值線等值面的生成課件二二 Marching Cubes(MC)方法方法 Marching Cubes（移動立方體）方法是由（移動立方體）方法是由W.E.Lorenson和和H.E.Cline在在1987年提出來的。由于這一方法原理簡單，易于實(shí)年提出來的。由于這一方法原理簡單，易于實(shí)現(xiàn)，目前已經(jīng)得到了較為廣泛的應(yīng)用，成為三維數(shù)據(jù)等值面生成現(xiàn)

21、，目前已經(jīng)得到了較為廣泛的應(yīng)用，成為三維數(shù)據(jù)等值面生成的經(jīng)典算法，的經(jīng)典算法，Marching Cubes算法又簡稱為算法又簡稱為MC算法。算法。 1MC方法的基本原理方法的基本原理 在在Marching Cubes方法中，假定原始數(shù)據(jù)是離散的三維空間規(guī)則方法中，假定原始數(shù)據(jù)是離散的三維空間規(guī)則數(shù)據(jù)，一個(gè)體元定義為由相鄰層上的數(shù)據(jù)，一個(gè)體元定義為由相鄰層上的8個(gè)頂點(diǎn)組成的一個(gè)長方體。個(gè)頂點(diǎn)組成的一個(gè)長方體。為了在三維數(shù)據(jù)中構(gòu)造等值面，應(yīng)先給定所求等值面的值，該方為了在三維數(shù)據(jù)中構(gòu)造等值面，應(yīng)先給定所求等值面的值，該方法的基本原理是逐個(gè)處理所有的體元，將體元各頂點(diǎn)處的值與給法的基本原理是逐個(gè)處理

22、所有的體元，將體元各頂點(diǎn)處的值與給定的閾值進(jìn)行比較，首先找出與等值面相交的體元，然后通過插定的閾值進(jìn)行比較，首先找出與等值面相交的體元，然后通過插值求等值面與體元棱邊的交點(diǎn)，并將各交點(diǎn)連成三角形來構(gòu)成等值求等值面與體元棱邊的交點(diǎn)，并將各交點(diǎn)連成三角形來構(gòu)成等值面片，所有體元中的三角形集合就構(gòu)成了等值面。由于這一方值面片，所有體元中的三角形集合就構(gòu)成了等值面。由于這一方法是逐個(gè)處理所有的體元，因此被稱為法是逐個(gè)處理所有的體元，因此被稱為Marching Cubes方法。方法。MC方法的主要步驟如下：方法的主要步驟如下：等值線等值面的生成課件Marching Cubes(MC)方法方法 (1) 確

23、定包含等值面的體元及對應(yīng)的等值面片模式確定包含等值面的體元及對應(yīng)的等值面片模式 一個(gè)體元由一個(gè)體元由8個(gè)數(shù)據(jù)點(diǎn)構(gòu)成，這個(gè)數(shù)據(jù)點(diǎn)構(gòu)成，這8個(gè)數(shù)據(jù)點(diǎn)分別位于該體元的個(gè)數(shù)據(jù)點(diǎn)分別位于該體元的8個(gè)個(gè)頂點(diǎn)上。頂點(diǎn)上。 首先對體元的首先對體元的8個(gè)頂點(diǎn)進(jìn)行分類，判定是位于等值面之外，還是個(gè)頂點(diǎn)進(jìn)行分類，判定是位于等值面之外，還是位于等值面之內(nèi)。再根據(jù)位于等值面之內(nèi)。再根據(jù)8個(gè)頂點(diǎn)的狀態(tài)，確定等值面的模式。個(gè)頂點(diǎn)的狀態(tài)，確定等值面的模式。 設(shè)等值面的值為設(shè)等值面的值為Ft，頂點(diǎn)分類規(guī)則為：，頂點(diǎn)分類規(guī)則為： 若某頂點(diǎn)的值若某頂點(diǎn)的值Ft，則定義該頂點(diǎn)位于等值面之外，記為，則定義該頂點(diǎn)位于等值面之外，記為“0

24、”。 若某頂點(diǎn)的值若某頂點(diǎn)的值Ft，則定義該頂點(diǎn)位于等值面之內(nèi)，記為，則定義該頂點(diǎn)位于等值面之內(nèi)，記為“1”。 如果某體元一條邊的一個(gè)頂點(diǎn)在等值面之內(nèi)，而另一個(gè)頂點(diǎn)在等如果某體元一條邊的一個(gè)頂點(diǎn)在等值面之內(nèi)，而另一個(gè)頂點(diǎn)在等值面之外，那么，該邊必然與等值面相交。根據(jù)這一原理就可以值面之外，那么，該邊必然與等值面相交。根據(jù)這一原理就可以判斷所求等值面將與哪些體元相交，或者說將穿過哪些體元。判斷所求等值面將與哪些體元相交，或者說將穿過哪些體元。等值線等值面的生成課件Marching Cubes(MC)方法方法 由于每個(gè)體元有由于每個(gè)體元有8個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)又有個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)又有0、1兩種狀態(tài)，因

25、此每兩種狀態(tài)，因此每個(gè)體元按其個(gè)體元按其8個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的0、1分布而言，共有分布而言，共有28=256種不同的狀態(tài)。種不同的狀態(tài)。盡管判斷等值面將與哪些體元相交在原理上很容易理解，但是要盡管判斷等值面將與哪些體元相交在原理上很容易理解，但是要根據(jù)這根據(jù)這256種不同的情況求出每個(gè)體元中的等值面卻是很繁瑣的，種不同的情況求出每個(gè)體元中的等值面卻是很繁瑣的，而且也容易出錯(cuò)。而且也容易出錯(cuò)。 可以利用兩種不同的對稱性將可以利用兩種不同的對稱性將256種不同的情況簡化為種不同的情況簡化為15種。種。 互補(bǔ)對稱性互補(bǔ)對稱性：如果將一個(gè)體元的頂點(diǎn)狀態(tài)顛倒，即：如果將一個(gè)體元的頂點(diǎn)狀態(tài)顛倒，即“0”變成變

26、成“1”，“1”變成變成“0”，則等值面與體元中，則等值面與體元中8個(gè)頂點(diǎn)之間的拓?fù)潢P(guān)個(gè)頂點(diǎn)之間的拓?fù)潢P(guān)系將不會改變，該體元與等值面的相交情況與原來一致，即新生系將不會改變，該體元與等值面的相交情況與原來一致，即新生成的等值面與原等值面是相同的。也就是說，大于等值面的點(diǎn)與成的等值面與原等值面是相同的。也就是說，大于等值面的點(diǎn)與小于等值面的點(diǎn)是可以相互替換的，因此，只要考慮小于等值面的點(diǎn)是可以相互替換的，因此，只要考慮4個(gè)以下個(gè)以下（含（含4個(gè)）的頂點(diǎn)值大于個(gè)）的頂點(diǎn)值大于Ft就夠了。根據(jù)這種互補(bǔ)對稱性，可將就夠了。根據(jù)這種互補(bǔ)對稱性，可將體元的模式由體元的模式由256種減少為種減少為128種。

27、種。 等值線等值面的生成課件Marching Cubes(MC)方法方法 旋轉(zhuǎn)對稱性旋轉(zhuǎn)對稱性：如果某一模式的體元經(jīng)過旋轉(zhuǎn)后與另一模式的：如果某一模式的體元經(jīng)過旋轉(zhuǎn)后與另一模式的體元一致，即頂點(diǎn)位置及其狀態(tài)值相同，那么這兩種模式的體元體元一致，即頂點(diǎn)位置及其狀態(tài)值相同，那么這兩種模式的體元可以合并為一種。根據(jù)這種旋轉(zhuǎn)對稱性，體元模式可以最終歸納可以合并為一種。根據(jù)這種旋轉(zhuǎn)對稱性，體元模式可以最終歸納為為15種，見圖種，見圖2。其中第。其中第0種情況表示所有種情況表示所有8個(gè)頂點(diǎn)的值均大于個(gè)頂點(diǎn)的值均大于（或小于）（或小于）Ft，因而該體元與等值面不相交。第一種情況表示有，因而該體元與等值面不相

28、交。第一種情況表示有一個(gè)頂點(diǎn)的函數(shù)值大于（或小于）一個(gè)頂點(diǎn)的函數(shù)值大于（或小于）Ft，其余，其余7個(gè)頂點(diǎn)均與此相反，個(gè)頂點(diǎn)均與此相反，因而該體元內(nèi)的等值面將是一個(gè)三角面片。在考慮了上面兩種對因而該體元內(nèi)的等值面將是一個(gè)三角面片。在考慮了上面兩種對稱性后，這一種情況實(shí)際上代表了稱性后，這一種情況實(shí)際上代表了16種情況。如此類推，圖種情況。如此類推，圖2中中的的15種模式反映了一個(gè)體元中種模式反映了一個(gè)體元中8個(gè)頂點(diǎn)可能存在的全部個(gè)頂點(diǎn)可能存在的全部256種狀態(tài)。種狀態(tài)。等值線等值面的生成課件等值線等值面的生成課件 在實(shí)現(xiàn)時(shí)，對一個(gè)體元可按照它的在實(shí)現(xiàn)時(shí)，對一個(gè)體元可按照它的8個(gè)頂點(diǎn)的狀態(tài)構(gòu)造一個(gè)

29、一字個(gè)頂點(diǎn)的狀態(tài)構(gòu)造一個(gè)一字節(jié)（節(jié)（8位）的狀態(tài)表，如圖位）的狀態(tài)表，如圖3所示，其中的每一位表示該體元中一所示，其中的每一位表示該體元中一個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的0或或1狀態(tài)，根據(jù)這個(gè)狀態(tài)表就可判斷出當(dāng)前體元屬于哪狀態(tài)，根據(jù)這個(gè)狀態(tài)表就可判斷出當(dāng)前體元屬于哪一種模式、等值面將與哪一條邊相交以及體元內(nèi)三角面片的連接一種模式、等值面將與哪一條邊相交以及體元內(nèi)三角面片的連接方式。方式。等值線等值面的生成課件Marching Cubes(MC)方法方法 (2) 計(jì)算等值面與體元邊界的交點(diǎn)，并連接成三角形計(jì)算等值面與體元邊界的交點(diǎn)，并連接成三角形 當(dāng)三維離散數(shù)據(jù)的密度較高，即每個(gè)體元很小時(shí)，可以假定函數(shù)當(dāng)三維

30、離散數(shù)據(jù)的密度較高，即每個(gè)體元很小時(shí)，可以假定函數(shù)值沿體元邊界呈線性變化。因此，等值面與體元邊界的交點(diǎn)可以值沿體元邊界呈線性變化。因此，等值面與體元邊界的交點(diǎn)可以通過該邊兩端點(diǎn)函數(shù)值的線性插值求出，公式為：通過該邊兩端點(diǎn)函數(shù)值的線性插值求出，公式為： 求出了等值面與體元邊界的交點(diǎn)以后，就可以按對應(yīng)的模式將這求出了等值面與體元邊界的交點(diǎn)以后，就可以按對應(yīng)的模式將這些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片。些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片。)/()(, 1,kjikjikjitFFFFiX等值線等值面的生成課件Marching Cubes(MC)方法方法 (3) 計(jì)算等值面的法向計(jì)算等

31、值面的法向 為了繪制等值面的真實(shí)感圖象，還必須給出構(gòu)成等值面的各三角為了繪制等值面的真實(shí)感圖象，還必須給出構(gòu)成等值面的各三角面片的法向。對于等值面上的每一點(diǎn)，沿該面切線方向的梯度分面片的法向。對于等值面上的每一點(diǎn)，沿該面切線方向的梯度分量應(yīng)該是零，因此該點(diǎn)的梯度矢量的方向就代表了等值面的法向。量應(yīng)該是零，因此該點(diǎn)的梯度矢量的方向就代表了等值面的法向。MC方法就是利用這一原理來計(jì)算三角面片的法向。即方法就是利用這一原理來計(jì)算三角面片的法向。即 對于三維規(guī)則網(wǎng)格數(shù)據(jù)，可以直接采用中心差分計(jì)算體元各頂點(diǎn)對于三維規(guī)則網(wǎng)格數(shù)據(jù)，可以直接采用中心差分計(jì)算體元各頂點(diǎn)處的梯度，公式為：處的梯度，公式為：),(

32、),(zyxfzyxgzzyxfzyxfgyzyxfzyxfgxzyxfzyxfgkjikjizkjikjiykjikjix2/),(),(2/),(),(2/),(),(111111等值線等值面的生成課件 三角形頂點(diǎn)處的法向量可由體元邊界兩端點(diǎn)處的梯度再通過線性三角形頂點(diǎn)處的法向量可由體元邊界兩端點(diǎn)處的梯度再通過線性插值求得。在實(shí)際繪制等值面時(shí)，為了消除各三角面片之間明暗插值求得。在實(shí)際繪制等值面時(shí)，為了消除各三角面片之間明暗的不連續(xù)變化，只要給出三角面片各頂點(diǎn)處的法向并采用哥羅得的不連續(xù)變化，只要給出三角面片各頂點(diǎn)處的法向并采用哥羅得(Gouraud)模型繪制各個(gè)三角面片即可。模型繪制各個(gè)

33、三角面片即可。 在計(jì)算機(jī)圖形學(xué)中，光滑的曲面常用多邊形來逼近，這是因?yàn)樘幵谟?jì)算機(jī)圖形學(xué)中，光滑的曲面常用多邊形來逼近，這是因?yàn)樘幚砥矫姹忍幚砬嫒菀椎枚?。例如，為了表示一個(gè)磨光的立方體理平面比處理曲面容易得多。例如，為了表示一個(gè)磨光的立方體的頂角，可使用的頂角，可使用7個(gè)平面片來近似。但是，若單純使用平面來繪個(gè)平面片來近似。但是，若單純使用平面來繪制這種近似表面，生成的圖形將失去原有曲面的光滑性，而呈現(xiàn)制這種近似表面，生成的圖形將失去原有曲面的光滑性，而呈現(xiàn)多面體狀。這是由于平面上所有點(diǎn)的法向相同，不同平面塊之間多面體狀。這是由于平面上所有點(diǎn)的法向相同，不同平面塊之間存在不連續(xù)的法向量變化，從

34、而引起不連續(xù)的光亮度跳躍。存在不連續(xù)的法向量變化，從而引起不連續(xù)的光亮度跳躍。 如何能以較少的計(jì)算量來解決上述問題呢如何能以較少的計(jì)算量來解決上述問題呢?最簡單的方法就是最簡單的方法就是Gouraud明暗處理技術(shù)。明暗處理技術(shù)。Gouraud明暗處理的思想是對離散的光明暗處理的思想是對離散的光亮度作雙線性插值以獲得連續(xù)的光亮度函數(shù)。具體做法是：先計(jì)亮度作雙線性插值以獲得連續(xù)的光亮度函數(shù)。具體做法是：先計(jì)算出多邊形頂點(diǎn)處的光亮度值，把它們作為曲面光亮度的采樣點(diǎn)，算出多邊形頂點(diǎn)處的光亮度值，把它們作為曲面光亮度的采樣點(diǎn)，然后根據(jù)多邊形頂點(diǎn)處的光亮度值進(jìn)行插值求多邊形內(nèi)任一點(diǎn)的然后根據(jù)多邊形頂點(diǎn)處的

35、光亮度值進(jìn)行插值求多邊形內(nèi)任一點(diǎn)的光亮度。光亮度。等值線等值面的生成課件 若采用掃描線繪制算法，則可沿當(dāng)前掃描線進(jìn)行雙線性插值，這若采用掃描線繪制算法，則可沿當(dāng)前掃描線進(jìn)行雙線性插值，這是一種簡便易行的插值方法。即先用多邊形頂點(diǎn)的光亮度值由線是一種簡便易行的插值方法。即先用多邊形頂點(diǎn)的光亮度值由線性插值求出當(dāng)前掃描線與多邊形交點(diǎn)處的光亮度，然后根據(jù)交點(diǎn)性插值求出當(dāng)前掃描線與多邊形交點(diǎn)處的光亮度，然后根據(jù)交點(diǎn)的光亮度值再通過線性插值求出掃描線上位于多邊形內(nèi)每一象素的光亮度值再通過線性插值求出掃描線上位于多邊形內(nèi)每一象素點(diǎn)的光亮度值。圖點(diǎn)的光亮度值。圖4(a)顯示一掃描線與多邊形相交，交點(diǎn)為顯示一

36、掃描線與多邊形相交，交點(diǎn)為a點(diǎn)和點(diǎn)和b點(diǎn)，點(diǎn)，p是掃描線上位于多邊形內(nèi)的任一點(diǎn)，多邊形三個(gè)頂點(diǎn)的光是掃描線上位于多邊形內(nèi)的任一點(diǎn)，多邊形三個(gè)頂點(diǎn)的光亮度分別為亮度分別為I1，I2和和I3。取。取a點(diǎn)的光亮度點(diǎn)的光亮度Ia為為I1和和I2的線性插值，的線性插值，b點(diǎn)的光亮度點(diǎn)的光亮度Ib為為I1和和I3的線性插值，的線性插值，p點(diǎn)的光亮度則為點(diǎn)的光亮度則為Ia和和Ib的線性的線性插值，即：插值，即： 其中其中u,v,t稱為插值參數(shù)稱為插值參數(shù)(相當(dāng)于以端點(diǎn)為原點(diǎn)歸一化后的長度坐相當(dāng)于以端點(diǎn)為原點(diǎn)歸一化后的長度坐標(biāo)標(biāo))。,)1 (,)1 (,)1 (3121bapbaIttIIIvvIIIuuII

37、abpbtVVbVvVVaVu/313212等值線等值面的生成課件 采用采用Gouraud明暗處理不但可以克服用多邊形表示曲面時(shí)光亮度明暗處理不但可以克服用多邊形表示曲面時(shí)光亮度的不連續(xù)現(xiàn)象，而且計(jì)算量也很小。事實(shí)上，由于線性插值可使的不連續(xù)現(xiàn)象，而且計(jì)算量也很小。事實(shí)上，由于線性插值可使用增量法進(jìn)行計(jì)算，其運(yùn)算量僅涉及一次加法運(yùn)算。如在上例中，用增量法進(jìn)行計(jì)算，其運(yùn)算量僅涉及一次加法運(yùn)算。如在上例中，可沿掃描線從左至右的順序計(jì)算可沿掃描線從左至右的順序計(jì)算AB區(qū)段上所有象素的光亮度。區(qū)段上所有象素的光亮度。設(shè)設(shè)Ia和和Ib已經(jīng)確定，已經(jīng)確定，p1和和p2點(diǎn)是相鄰兩象素的坐標(biāo)，點(diǎn)是相鄰兩象素的

38、坐標(biāo)，a、b兩點(diǎn)的插兩點(diǎn)的插值參數(shù)之差為值參數(shù)之差為 t，那么，不難發(fā)現(xiàn)，那么，不難發(fā)現(xiàn)p2點(diǎn)光亮度點(diǎn)光亮度Ip2和和p1點(diǎn)光亮度點(diǎn)光亮度Ip1之間有下列關(guān)系：之間有下列關(guān)系： 由于由于 I在同一掃描線上為常數(shù)，因此計(jì)算一相鄰象素的光亮度僅在同一掃描線上為常數(shù)，因此計(jì)算一相鄰象素的光亮度僅需一次加法運(yùn)算。這種增量方式的光亮度計(jì)算使需一次加法運(yùn)算。這種增量方式的光亮度計(jì)算使Gouraud明暗處明暗處理廣泛用于實(shí)時(shí)圖形生成。理廣泛用于實(shí)時(shí)圖形生成。 在在Gouraud明暗處理中，計(jì)算多邊形頂點(diǎn)的光亮度可采用明暗處理中，計(jì)算多邊形頂點(diǎn)的光亮度可采用Phong光照模型。光照模型。IItIIIIpbap

39、p112/ )(aKIKIKIIsnssddaacoscos等值線等值面的生成課件等值線等值面的生成課件Marching Cubes(MC)方法方法 (4) 用用MC方法求等值面的算法流程方法求等值面的算法流程 將三維離散規(guī)則數(shù)據(jù)分層讀入內(nèi)存；將三維離散規(guī)則數(shù)據(jù)分層讀入內(nèi)存； 掃描其中兩層數(shù)據(jù)，逐個(gè)構(gòu)造這兩層之間的體元，每個(gè)體元掃描其中兩層數(shù)據(jù)，逐個(gè)構(gòu)造這兩層之間的體元，每個(gè)體元中的中的8個(gè)頂點(diǎn)取自相鄰的兩層；個(gè)頂點(diǎn)取自相鄰的兩層； 將體元各個(gè)頂點(diǎn)的值與給定的等值面值將體元各個(gè)頂點(diǎn)的值與給定的等值面值Ft進(jìn)行比較，根據(jù)比較進(jìn)行比較，根據(jù)比較的結(jié)果進(jìn)行分類，構(gòu)造該體元的狀態(tài)表；的結(jié)果進(jìn)行分類，構(gòu)

40、造該體元的狀態(tài)表； 根據(jù)狀態(tài)表，查得與該狀態(tài)值對應(yīng)的等值面分布模式，確定根據(jù)狀態(tài)表，查得與該狀態(tài)值對應(yīng)的等值面分布模式，確定將與等值面相交的體元邊界；將與等值面相交的體元邊界； 通過線性插值，計(jì)算體元邊界與等值面的交點(diǎn)坐標(biāo)，按對應(yīng)通過線性插值，計(jì)算體元邊界與等值面的交點(diǎn)坐標(biāo)，按對應(yīng)的模式將這些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片；的模式將這些交點(diǎn)連接成三角形，構(gòu)成該單元中的等值面片； 利用中心差分方法，求出體元各頂點(diǎn)處的梯度，再次通過線利用中心差分方法，求出體元各頂點(diǎn)處的梯度，再次通過線性插值方法，求出三角形各頂點(diǎn)處的法向；性插值方法，求出三角形各頂點(diǎn)處的法向； 根據(jù)各三角面片各頂點(diǎn)的坐標(biāo)

41、值及法向量繪制等值面圖象。根據(jù)各三角面片各頂點(diǎn)的坐標(biāo)值及法向量繪制等值面圖象。等值線等值面的生成課件Marching Cubes (MC)方法方法 2MC方法的加速算法方法的加速算法 Marching Cube方法是逐個(gè)單元地檢測是否存在等值面，還要計(jì)方法是逐個(gè)單元地檢測是否存在等值面，還要計(jì)算等值面與體元邊界的交點(diǎn)，再由標(biāo)準(zhǔn)的連接模式將各個(gè)交點(diǎn)連算等值面與體元邊界的交點(diǎn)，再由標(biāo)準(zhǔn)的連接模式將各個(gè)交點(diǎn)連接成等值面片。事實(shí)上，據(jù)研究，真正與等值面相交的體元占總接成等值面片。事實(shí)上，據(jù)研究，真正與等值面相交的體元占總數(shù)據(jù)量很小的一部分（至多數(shù)據(jù)量很小的一部分（至多10%左右），計(jì)算過程中左右），計(jì)

42、算過程中30-70%的的時(shí)間用在了空體元的檢測上，從加快時(shí)間用在了空體元的檢測上，從加快Marching Cube方法的角度方法的角度出發(fā)，有必要研究一種快速有效的空間數(shù)據(jù)的遍歷方法和相應(yīng)的出發(fā)，有必要研究一種快速有效的空間數(shù)據(jù)的遍歷方法和相應(yīng)的數(shù)據(jù)表達(dá)形式，以加速對空體元的檢測和排除。另一方面，對于數(shù)據(jù)表達(dá)形式，以加速對空體元的檢測和排除。另一方面，對于一條與等值面相交的體元的邊，它同時(shí)被四個(gè)單元共用，這表明一條與等值面相交的體元的邊，它同時(shí)被四個(gè)單元共用，這表明在這四個(gè)單元內(nèi)求等值面時(shí)都要用到這個(gè)交點(diǎn)，保存該交點(diǎn)的位在這四個(gè)單元內(nèi)求等值面時(shí)都要用到這個(gè)交點(diǎn)，保存該交點(diǎn)的位置及法向量對于加速

43、算法具有重要意義。置及法向量對于加速算法具有重要意義。等值線等值面的生成課件 對于規(guī)則網(wǎng)格數(shù)據(jù)，其體元是一個(gè)六面體單元，若采用空間八叉對于規(guī)則網(wǎng)格數(shù)據(jù)，其體元是一個(gè)六面體單元，若采用空間八叉樹來表示這種體數(shù)據(jù)，則可以加快運(yùn)算速度。樹來表示這種體數(shù)據(jù)，則可以加快運(yùn)算速度。 Marching Cube方法的另一個(gè)重要問題是抽取的等值面三角片數(shù)方法的另一個(gè)重要問題是抽取的等值面三角片數(shù)量巨大，有時(shí)一個(gè)體元可以生成多達(dá)量巨大，有時(shí)一個(gè)體元可以生成多達(dá)12個(gè)三角片，當(dāng)三維數(shù)據(jù)的個(gè)三角片，當(dāng)三維數(shù)據(jù)的數(shù)據(jù)量很大時(shí)，三角片的數(shù)量也非常大。這給等值面的繪制和交數(shù)據(jù)量很大時(shí)，三角片的數(shù)量也非常大。這給等值面的繪

44、制和交互操作帶來很大困難。互操作帶來很大困難。Schroeder提出了在不影響圖形質(zhì)量的情提出了在不影響圖形質(zhì)量的情況下，通過對原等值面三角片網(wǎng)重排結(jié)點(diǎn)，合并簡化，生成最優(yōu)況下，通過對原等值面三角片網(wǎng)重排結(jié)點(diǎn)，合并簡化，生成最優(yōu)化意義下的化意義下的Delaunay三角化網(wǎng)，可以有效加快圖形的實(shí)時(shí)顯示，三角化網(wǎng)，可以有效加快圖形的實(shí)時(shí)顯示，這對于這對于Marching Cube方法的實(shí)用是非常有意義的。方法的實(shí)用是非常有意義的。等值線等值面的生成課件Marching Cubes (MC)方法方法 3MC方法存在的問題方法存在的問題 (1) MC方法構(gòu)造的三角面片是三維等值面的近似表示方法構(gòu)造的三

45、角面片是三維等值面的近似表示 首先，在首先，在MC方法中，等值面與體元邊界的交點(diǎn)是基于函數(shù)值在方法中，等值面與體元邊界的交點(diǎn)是基于函數(shù)值在體元邊界上呈線性變化這一假設(shè)而求出的。當(dāng)數(shù)據(jù)密度高、體元體元邊界上呈線性變化這一假設(shè)而求出的。當(dāng)數(shù)據(jù)密度高、體元很小時(shí)，這一假設(shè)接近于實(shí)際情況。但是，在稀疏數(shù)據(jù)中，體元很小時(shí)，這一假設(shè)接近于實(shí)際情況。但是，在稀疏數(shù)據(jù)中，體元較大，如果仍然認(rèn)為函數(shù)值在體元邊界上呈線性變化，將會產(chǎn)生較大，如果仍然認(rèn)為函數(shù)值在體元邊界上呈線性變化，將會產(chǎn)生較大誤差。這時(shí)，需要根據(jù)不同的具體情況對函數(shù)值沿體元邊界較大誤差。這時(shí)，需要根據(jù)不同的具體情況對函數(shù)值沿體元邊界的變化作其它適

46、當(dāng)?shù)募僭O(shè)，才能較準(zhǔn)確地求出等值面。的變化作其它適當(dāng)?shù)募僭O(shè)，才能較準(zhǔn)確地求出等值面。 其次，即使函數(shù)值沿體元邊界作線性變化這一假設(shè)符合實(shí)際，那其次，即使函數(shù)值沿體元邊界作線性變化這一假設(shè)符合實(shí)際，那么通過線性插值求得的交點(diǎn)位置是準(zhǔn)確的，但是，將體元中同一么通過線性插值求得的交點(diǎn)位置是準(zhǔn)確的，但是，將體元中同一個(gè)面上兩條相鄰邊上的交點(diǎn)簡單地用直線連接起來也是一種近似個(gè)面上兩條相鄰邊上的交點(diǎn)簡單地用直線連接起來也是一種近似(如下圖所示如下圖所示)。等值線等值面的生成課件等值線等值面的生成課件 為了說明這一問題，需要引入當(dāng)體元各邊界上函數(shù)值均為線性變?yōu)榱苏f明這一問題，需要引入當(dāng)體元各邊界上函數(shù)值均為線

47、性變化時(shí)的等值面模型。如圖化時(shí)的等值面模型。如圖3.5所示，所示，P(x, y, z)為小體元中的任意點(diǎn)，為小體元中的任意點(diǎn)，體元中的數(shù)據(jù)沿體元中的數(shù)據(jù)沿x, y, z三個(gè)方向均是線性變化的。如果點(diǎn)三個(gè)方向均是線性變化的。如果點(diǎn)P1，P2為點(diǎn)為點(diǎn)P沿沿y軸在立方體兩個(gè)面上的投影，軸在立方體兩個(gè)面上的投影，P11、P12、P21、P22分別為分別為P1，P2點(diǎn)沿點(diǎn)沿z軸在立方體平面上的投影。設(shè)軸在立方體平面上的投影。設(shè)V為為y軸上的坐標(biāo)分量，軸上的坐標(biāo)分量，f為函數(shù)值，那么，通過三次線性插值，可得：為函數(shù)值，那么，通過三次線性插值，可得： (1) 其中其中P1，P2兩點(diǎn)的值可由兩點(diǎn)的值可由P11

48、，P12和和P21，P22插值求得，而插值求得，而P11、P12、P21、P22四個(gè)點(diǎn)的值又可以由它們所在體元內(nèi)的一條邊上的四個(gè)點(diǎn)的值又可以由它們所在體元內(nèi)的一條邊上的兩個(gè)頂點(diǎn)插值得到。這樣，通過三次線性插值運(yùn)算，就可以求得兩個(gè)頂點(diǎn)插值得到。這樣，通過三次線性插值運(yùn)算，就可以求得P(x, y, z)點(diǎn)的函數(shù)值，（點(diǎn)的函數(shù)值，（1）式可具體展開為：）式可具體展開為：)()()(),(212122PfPfVVVVPfzyxfPPPP等值線等值面的生成課件 其中系數(shù)其中系數(shù)ai ( i= 0, 7 )取決于體元取決于體元8個(gè)頂點(diǎn)處的函數(shù)值，如果給個(gè)頂點(diǎn)處的函數(shù)值，如果給定的等值面的值為定的等值面的值

49、為Ft，那么，等值面就被定義為滿足如下方程的，那么，等值面就被定義為滿足如下方程的點(diǎn)的集合點(diǎn)的集合 (2) 改變改變Ft的值，就可以得到不同等值面的表達(dá)式。的值，就可以得到不同等值面的表達(dá)式。 由上述等值面方程可以方便地求出某等值面與體元邊界面的交線由上述等值面方程可以方便地求出某等值面與體元邊界面的交線方程。不失一般性，設(shè)某邊界面所在平面的方程為方程。不失一般性，設(shè)某邊界面所在平面的方程為z=z0，代入方，代入方程式程式(2)，可得，可得 (3) 上式可進(jìn)一步表示為：上式可進(jìn)一步表示為：xyzazxayzaxyazayaxaazyxf76543210),(tFzyxf),(tFxybybxb

50、b3210等值線等值面的生成課件 （4） 顯然，上述方程表示的是一條雙曲線，即等值面與體元中某一個(gè)顯然，上述方程表示的是一條雙曲線，即等值面與體元中某一個(gè)面的交線是一條雙曲線或其中的一支。如果用一條直線來表示這面的交線是一條雙曲線或其中的一支。如果用一條直線來表示這條雙曲線，則會引起誤差（如圖所示）。如果體元很小，這一誤條雙曲線，則會引起誤差（如圖所示）。如果體元很小，這一誤差是可以忽略不記的。對于稀疏的三維數(shù)據(jù)，這種近似引起的誤差是可以忽略不記的。對于稀疏的三維數(shù)據(jù)，這種近似引起的誤差是難以接受的，可通過自適應(yīng)剖分算法將三角形按給定的逼近差是難以接受的，可通過自適應(yīng)剖分算法將三角形按給定的逼

51、近精度遞歸地分成子三角形，使這些子三角形的頂點(diǎn)滿足方程精度遞歸地分成子三角形，使這些子三角形的頂點(diǎn)滿足方程(3)，且子三角形與等值面的最大距離小于給定的容差。且子三角形與等值面的最大距離小于給定的容差。032313)(bFbbxbbybt等值線等值面的生成課件Marching Cubes (MC)方法方法 (2) 連接方式上的二義性連接方式上的二義性 Marching Cubes方法可以看成是二維等值線網(wǎng)格序列法在三維空方法可以看成是二維等值線網(wǎng)格序列法在三維空間中的推廣。在網(wǎng)格序列法中，如果矩形網(wǎng)格單元間中的推廣。在網(wǎng)格序列法中，如果矩形網(wǎng)格單元4個(gè)頂點(diǎn)中有個(gè)頂點(diǎn)中有兩個(gè)頂點(diǎn)的值大于等值線的

52、值，另兩個(gè)頂點(diǎn)的值小于等值線的值，兩個(gè)頂點(diǎn)的值大于等值線的值，另兩個(gè)頂點(diǎn)的值小于等值線的值，且這兩個(gè)頂點(diǎn)交叉分布，那么等值線的連接就出現(xiàn)二義性。同理，且這兩個(gè)頂點(diǎn)交叉分布，那么等值線的連接就出現(xiàn)二義性。同理，在在Marching Cubes方法中，如果正六面體單元的方法中，如果正六面體單元的6個(gè)矩形表面中個(gè)矩形表面中出現(xiàn)與此相同的情形，那么該正六面體單元中的等值面連接必然出現(xiàn)與此相同的情形，那么該正六面體單元中的等值面連接必然會出現(xiàn)二義性，這樣的面稱為二義性面，包含會出現(xiàn)二義性，這樣的面稱為二義性面，包含1個(gè)以上的二義性個(gè)以上的二義性面的體元，即為具有二義性的體元，如下圖所示。事實(shí)上，在面的體

53、元，即為具有二義性的體元，如下圖所示。事實(shí)上，在Marching Cubes方法的方法的15種模式中，第種模式中，第3、6、7、10、12、13等等6種情況是具有二義性的。種情況是具有二義性的。等值線等值面的生成課件等值線等值面的生成課件Marching Cubes (MC)方法方法 4用雙曲線漸近線方法判別和消除二義性用雙曲線漸近線方法判別和消除二義性 MC方法存在連接方式的二義性問題在該方法提出后不久，就由方法存在連接方式的二義性問題在該方法提出后不久，就由M.J.Durst提出來了，這一問題如果不解決，將造成等值面連接提出來了，這一問題如果不解決，將造成等值面連接上的錯(cuò)誤。如在兩個(gè)相鄰體

54、元的公共面上，可能會出現(xiàn)兩種不同上的錯(cuò)誤。如在兩個(gè)相鄰體元的公共面上，可能會出現(xiàn)兩種不同的連接方式，從而形成空洞。的連接方式，從而形成空洞。 盡管人們已經(jīng)提出了幾種不同的判別和消除二義性的方法，但以盡管人們已經(jīng)提出了幾種不同的判別和消除二義性的方法，但以G.M.Nielson等人提出的漸近線法等人提出的漸近線法(1991)最為常用。最為常用。 如前所述，在一般情況下，等值面與體元邊界面所在平面的交線如前所述，在一般情況下，等值面與體元邊界面所在平面的交線是一條雙曲線或其中的一支。該雙曲線的兩支及其漸近線與體元是一條雙曲線或其中的一支。該雙曲線的兩支及其漸近線與體元的一個(gè)邊界面的相對位置關(guān)系可用

55、下圖的一個(gè)邊界面的相對位置關(guān)系可用下圖5來表示。在該圖所列的來表示。在該圖所列的四種狀態(tài)中，當(dāng)雙曲線的兩支均與體元的某邊界面相交時(shí)，就會四種狀態(tài)中，當(dāng)雙曲線的兩支均與體元的某邊界面相交時(shí)，就會出現(xiàn)連接方式的二義性。出現(xiàn)連接方式的二義性。 在出現(xiàn)二義性的情況中，雙曲線的兩支將邊界面劃分為在出現(xiàn)二義性的情況中，雙曲線的兩支將邊界面劃分為3個(gè)區(qū)域，個(gè)區(qū)域，顯然，雙曲線漸近線的交點(diǎn)總是和邊界面中呈對角分布的一對頂顯然，雙曲線漸近線的交點(diǎn)總是和邊界面中呈對角分布的一對頂點(diǎn)落在同一區(qū)域內(nèi)，這一性質(zhì)就成為解決二義性問題的基礎(chǔ)。點(diǎn)落在同一區(qū)域內(nèi)，這一性質(zhì)就成為解決二義性問題的基礎(chǔ)。等值線等值面的生成課件等值線

56、等值面的生成課件 根據(jù)根據(jù)(4)式，漸近線方程可寫為：式，漸近線方程可寫為： 當(dāng)出現(xiàn)二義性時(shí)，需要計(jì)算當(dāng)出現(xiàn)二義性時(shí)，需要計(jì)算f(x, y, z0)的值。如果的值。如果f(x, y, z0)Ft，則漸近線的交點(diǎn)應(yīng)與數(shù)值大于則漸近線的交點(diǎn)應(yīng)與數(shù)值大于Ft的一對頂點(diǎn)落在同一區(qū)域，如圖的一對頂點(diǎn)落在同一區(qū)域，如圖6(a)所示，可連接所示，可連接M1M2、M3M4，否則漸近線交點(diǎn)與數(shù)值小于，否則漸近線交點(diǎn)與數(shù)值小于Ft的一對頂點(diǎn)落在同一區(qū)域，如圖的一對頂點(diǎn)落在同一區(qū)域，如圖6(b)所示，可連接所示，可連接M1M3、M2M4。在圖在圖6中，當(dāng)中，當(dāng)f(x, y, z0)Ft時(shí)，對漸進(jìn)線的交點(diǎn)標(biāo)以正值，其

57、對應(yīng)時(shí)，對漸進(jìn)線的交點(diǎn)標(biāo)以正值，其對應(yīng)的二義面稱為正值二義面的二義面稱為正值二義面(記為記為PAF)。當(dāng)。當(dāng)f(x, y, z0)Ft時(shí)，對漸時(shí)，對漸進(jìn)線的交點(diǎn)標(biāo)以負(fù)值，其對應(yīng)的二義面稱為負(fù)值二義面進(jìn)線的交點(diǎn)標(biāo)以負(fù)值，其對應(yīng)的二義面稱為負(fù)值二義面(記為記為NAF)。 0740613107405232zaazaabbyzaazaabbx等值線等值面的生成課件等值線等值面的生成課件 在所列的全部在所列的全部15種模式中，第種模式中，第0、1、2、4、5、8、9、11、14這這9種模式下不存在二義性面，因而它們只存在種模式下不存在二義性面，因而它們只存在1種連接方式。第種連接方式。第3、6兩種模式，

58、各存在一個(gè)二義性面，因此各有兩種連接方式。第兩種模式，各存在一個(gè)二義性面，因此各有兩種連接方式。第10、12兩種模式，各存在兩個(gè)二義性面，因而各有兩種模式，各存在兩個(gè)二義性面，因而各有4種連接方式。種連接方式。第第7種模式有種模式有3個(gè)二義性面，因而有個(gè)二義性面，因而有8種連接方式。第種連接方式。第13種模式有種模式有6個(gè)二義性面，因而有個(gè)二義性面，因而有64種連接方式。將以上各種情況加在一起，種連接方式。將以上各種情況加在一起，共有共有93種不同的連接方式。對于存在二義性的體元，按上述方法種不同的連接方式。對于存在二義性的體元，按上述方法解決二義性問題，雖然增加了計(jì)算工作量，但是為了得出完全

59、正解決二義性問題，雖然增加了計(jì)算工作量，但是為了得出完全正確的結(jié)果卻是十分必要的。確的結(jié)果卻是十分必要的。等值線等值面的生成課件三三 Marching Tetrahedra (MT)方法方法 Marching Tetrahedra方法簡稱為方法簡稱為MT方法，亦稱四面體剖分法，方法，亦稱四面體剖分法，它是在它是在MC方法的基礎(chǔ)上發(fā)展起來的。該方法首先將立方體單元方法的基礎(chǔ)上發(fā)展起來的。該方法首先將立方體單元剖分為四面體，然后在其中構(gòu)造等值面。提出這種方法的原因很剖分為四面體，然后在其中構(gòu)造等值面。提出這種方法的原因很多。首先，由于四面體是最簡單的多面體，其它類型的多面體都多。首先，由于四面體是

60、最簡單的多面體，其它類型的多面體都能剖分為四面體。其次，將立方體剖分為四面體后，在四面體中能剖分為四面體。其次，將立方體剖分為四面體后，在四面體中構(gòu)造的等值面的精度要比在立方體中構(gòu)造的等值面要高。而最直構(gòu)造的等值面的精度要比在立方體中構(gòu)造的等值面要高。而最直接的原因是企圖通過在四面體內(nèi)構(gòu)造等值面來避免接的原因是企圖通過在四面體內(nèi)構(gòu)造等值面來避免MC方法中存方法中存在的二義性問題。在的二義性問題。等值線等值面的生成課件 1MT方法的基本原理及存在的問題方法的基本原理及存在的問題 可以將一個(gè)立方體剖分為可以將一個(gè)立方體剖分為5個(gè)、個(gè)、6個(gè)和個(gè)和24個(gè)四面體，個(gè)四面體，5個(gè)或個(gè)或6個(gè)四面?zhèn)€四面體的剖