技術(shù)報(bào)告移動(dòng)立方體算法面二義性問(wèn)題

1、計(jì)劃類別 項(xiàng)目編號(hào) 項(xiàng)目技術(shù)報(bào)告課題名稱 項(xiàng)目主持人 承擔(dān)單位 題目：移動(dòng)立方體算法面二義性問(wèn)題研究在三維表面建模技術(shù)中，Marching Cubes算法是應(yīng)用最為廣泛的方法之一。該算法簡(jiǎn)單高效，但是也存在一定的不足之處，比如面的二義性問(wèn)題。構(gòu)造等值面時(shí)，在特定情況下對(duì)相同的等值點(diǎn)可以采取不同的連接方式，就會(huì)產(chǎn)生二義性，這將使得生成的等值面拓?fù)浣Y(jié)構(gòu)不一致，導(dǎo)致物體表面模型有孔洞。針對(duì)這一問(wèn)題，本文提出了一種基于插值點(diǎn)連線交點(diǎn)的解決方法，通過(guò)計(jì)算插值點(diǎn)連線交點(diǎn)的場(chǎng)函數(shù)值，唯一確定二義性面上等值線的連接方式，解決了面二義性，保證了等值面拓?fù)浣Y(jié)構(gòu)的一致。關(guān)鍵詞：三維表面建模；Marching Cub

2、es算法；二義性Abstract：In the 3D surface modeling technology，Marching Cubes is one of the most widely used algorithms.The algorithm is simple and efficient，but there are also some shortcomings，such as the ambiguous cases.When constructing the isosurface，if different connection methods are applied on the s

3、ame equivalent point in the specific case，ambiguity will be produced，which will cause the inconsistency of the generated isosurface topological structure，and eventually produce holes on the object surface.To solve this problem，this paper proposes a solution based on the intersection of interpolation

4、 points.By calculating the field function values of the intersection of interpolation points，the connection method of the isolines can be uniquely determined，which solves the ambiguity problem and guarantees the consistency of the isosurface topological structure.Keywords：3D surface modeling；Marchin

5、g Cubes algorithm；ambiguous cases1 引言（Introduction）三維表面建模是運(yùn)用計(jì)算機(jī)圖形學(xué)和圖像處理技術(shù)，將科學(xué)計(jì)算過(guò)程中產(chǎn)生的數(shù)據(jù)及計(jì)算結(jié)果轉(zhuǎn)換為物體的表面圖形和圖像顯示出來(lái)，并進(jìn)行交互處理的理論、方法和技術(shù)。隨著科學(xué)計(jì)算可視化的發(fā)展，加之圖形硬件的更新?lián)Q代，三維建模技術(shù)越來(lái)越多的應(yīng)用于生活、工程和科研領(lǐng)域1。作為三維表面建模技術(shù)的經(jīng)典算法之一，Marching Cubes算法至今仍然被廣泛使用，而針對(duì)算法存在的不足之處，也不斷有學(xué)者和研究人員進(jìn)行研究和改進(jìn)2。本文首先介紹了Marching Cubes算法的基本原理，然后分析了面二義性問(wèn)題并且介紹了

6、兩種經(jīng)典的解決方案四面體剖分法和雙曲線漸近線法，最后借鑒雙曲線漸近線法的思路提出了一種基于插值點(diǎn)連線交點(diǎn)的新方法，在解決面二義性問(wèn)題的同時(shí)簡(jiǎn)化了計(jì)算步驟，縮短了運(yùn)行時(shí)間。2 Marching Cubes算法原理（The principle ofMarching Cubes algorithm）Marching Cubes算法是目前三維表面重建中基于等值面抽取中最常用的方法。它在體素中提取等值面，通過(guò)逐個(gè)處理體素，對(duì)于與等值面相交的體素，用三角片近似表示其內(nèi)部的等值面片。由于算法在構(gòu)造等值面的過(guò)程中會(huì)依次處理每個(gè)體素，就好像沿著體素向前移動(dòng)，這是算法得名的原因。以三維礦體建模為例，Marchin

7、g Cubes算法的步驟如下：（1）讀取相鄰兩層切片數(shù)據(jù)。（2）體素化切片數(shù)據(jù)，將兩切片對(duì)應(yīng)的相鄰四個(gè)像素構(gòu)成一個(gè)立方體。（3）按順序逐個(gè)處理體素，確定每個(gè)體素內(nèi)三角面片的剖分方式。首先要確定等值面的值，即閾值，通過(guò)比較體素頂點(diǎn)場(chǎng)函數(shù)值與閾值的大小關(guān)系確定體素是否和等值面相交。頂點(diǎn)與等值面的關(guān)系有兩種，要么在等值面內(nèi)（包括在等值面上），要么在等值面外，因此8個(gè)頂點(diǎn)與等值面的關(guān)系情況就有28即256種，即一個(gè)體素和等值面相交的情況有256種。接下來(lái)根據(jù)連接方式的互補(bǔ)對(duì)稱性和旋轉(zhuǎn)對(duì)稱性，將256種相交情況進(jìn)行化解，最終得到15種3體素內(nèi)等值面的連接方式。（4）求體素與等值面的交點(diǎn)。（5）計(jì)算表面法

8、向量，形成光照。3 面二義性問(wèn)題（The problem of ambiguous cases）Marching Cubes算法的面二義性問(wèn)題由J.Durst首先提出4。在一個(gè)和等值面相交的體素中，假設(shè)其中一個(gè)面與等值面有交線，在該面的四個(gè)頂點(diǎn)中，如果位于一條對(duì)角線上的一對(duì)頂點(diǎn)的場(chǎng)函數(shù)值都大于等值面閾值，而另外一條對(duì)角線上的兩個(gè)頂點(diǎn)的場(chǎng)函數(shù)值都小于等值面閾值，那么此時(shí)等值線的連接方法有兩種，這就是二義性問(wèn)題，這樣的面稱為二義性面，如圖2所示。如果二義性面剛好是兩個(gè)相鄰體素的公共面，在連接三角形面片的時(shí)候，一個(gè)體素采取圖2（a）的連接方式，而另外一個(gè)體素采取了圖2（b）的連接方式，此時(shí)就出現(xiàn)了相

9、鄰體素在公共面上等值面連接方式不一致的情況，最終會(huì)導(dǎo)致生成的物體表面出現(xiàn)“孔洞”，不能保證曲面的封閉性。endprint4 經(jīng)典解決方法（Classic solutions）為了解決面二義性問(wèn)題，不少學(xué)者進(jìn)行了研究分析，得出了一些方法，下面就其中比較典型的方法進(jìn)行介紹。（1）四面體剖分法四面體剖分是解決面二義性問(wèn)題比較簡(jiǎn)單的一種方法。算法的思想就是把一個(gè)體素進(jìn)行分割，將其分成幾個(gè)四面體，然后在每個(gè)四面體內(nèi)求取與等值面的交點(diǎn)、提取等值面。與立方體體素相比，四面體的面都是三角形，而三角形中等值線的連接方式是唯一的。對(duì)于每個(gè)四面體，每個(gè)頂點(diǎn)有兩種狀態(tài)，四個(gè)頂點(diǎn)一共有16種狀態(tài)，根據(jù)對(duì)稱性和反轉(zhuǎn)性進(jìn)行

10、化解，最終等值面構(gòu)型只有三種，如圖3（a）所示。四面體與等值面是否相交的判斷方法和立方體體素一樣，都是根據(jù)頂點(diǎn)場(chǎng)函數(shù)值與等值面閾值的關(guān)系進(jìn)行判斷。如果頂點(diǎn)場(chǎng)函數(shù)值全部大于或者全部小于等值面值，那么該四面體與等值面不相交，如圖3（a）所示；如果一個(gè)頂點(diǎn)場(chǎng)函數(shù)值大于等值面值而另外三個(gè)頂點(diǎn)的場(chǎng)函數(shù)值小于等值面值，或者相反，一個(gè)頂點(diǎn)場(chǎng)函數(shù)值小于等值面值而另外三個(gè)頂點(diǎn)場(chǎng)函數(shù)值大于等值面值，則四面體與等值面相交，如圖3（b）所示；當(dāng)四面體兩個(gè)頂點(diǎn)場(chǎng)函數(shù)值大于等值面值而另外兩個(gè)頂點(diǎn)的場(chǎng)函數(shù)值小于等值面值時(shí)，等值面構(gòu)造如圖3（c）所示。四面體剖分有很多種方式，可以將立方體體素分為5個(gè)、6個(gè)或更多個(gè)四面體，分割

11、的數(shù)量不同，產(chǎn)生的四面體形態(tài)也不同，比如當(dāng)把立方體素剖分為5個(gè)四面體時(shí)形成的四面體并不全部相同，而剖分為24個(gè)四面體時(shí)形成的四面體是全部相同的。不同的劃分方式有不同的特點(diǎn)，分成5個(gè)四面體時(shí)產(chǎn)生的三角面片較少，但是由于是不全等劃分，處理起來(lái)比較復(fù)雜。分成24個(gè)全等四面體會(huì)產(chǎn)生較多的三角面片，但是插值計(jì)算過(guò)程比較容易。另外，在一個(gè)立方體體素中采用不同的方式剖分四面體生成的等值面構(gòu)型5也不同，如圖4所示。綜上所述，雖然四面體剖分法可以解決二義性問(wèn)題，而且生成的物體表面比較光滑，但是由于算法過(guò)程相對(duì)比較復(fù)雜，生成的三角面片較多，因此結(jié)果不是非常理想。（2）雙曲線漸近線法雙曲線漸近線方法是由G.M.Ni

12、elson6等提出的，該方法是面二義性問(wèn)題最經(jīng)典的解決方法。通常情況，體素表面與等值面的交線是雙曲線。在二義性面上，交線的兩個(gè)分支將體素平面分成三部分，不管如何劃分，漸近線的交點(diǎn)都會(huì)和一條對(duì)角線上的兩個(gè)頂點(diǎn)在同一個(gè)部分。如果漸近線交點(diǎn)的場(chǎng)函數(shù)值大于等值面的場(chǎng)函數(shù)值，則交點(diǎn)與場(chǎng)函數(shù)值大于等值面值的兩個(gè)頂點(diǎn)在相同區(qū)域；如果漸近線交點(diǎn)的場(chǎng)函數(shù)值小于等值面的場(chǎng)函數(shù)值，則交點(diǎn)與場(chǎng)函數(shù)值小于等值面值的兩個(gè)頂點(diǎn)在相同區(qū)域。這是雙曲線漸近線方法的基本思想。等值面與體素表面的相交關(guān)系有六種情況，相交產(chǎn)生的交點(diǎn)數(shù)量五種情況，其中交點(diǎn)數(shù)為2時(shí)相交關(guān)系有兩種，如圖5所示。相比四面體剖分法，雙曲線漸近線法沒(méi)有增加額外存

13、儲(chǔ)空間，而且算法效率比較高。MC算法的面二義性問(wèn)題會(huì)導(dǎo)致生成的物體表面出現(xiàn)孔洞，也就是生成的表面模型不正確。針對(duì)這一問(wèn)題，本文借鑒雙曲線漸近線的判別方法，提出一種解決方法，首先分別連接二義性面上處于對(duì)邊的一對(duì)交點(diǎn)，兩條連線會(huì)有一個(gè)交點(diǎn)，然后比較該交點(diǎn)場(chǎng)函數(shù)值與該面四個(gè)頂點(diǎn)的場(chǎng)函數(shù)值的關(guān)系來(lái)確定二義性面的連接方式。（1）基本思想Marching Cubes算法的前提是數(shù)據(jù)場(chǎng)沿著體素棱邊呈線性變化，即立方體網(wǎng)格的每條棱邊和等值面的交點(diǎn)最多為一個(gè)，每個(gè)面與等值面的交點(diǎn)最多為四個(gè)，其中與等值面交點(diǎn)為4的面是二義性面。重建物體表面時(shí)，等值點(diǎn)的連接是以直線段近似代替曲線的。因此一個(gè)二義性面上，兩條等值線將

14、把該面分為三個(gè)區(qū)域，如圖6所示，而相對(duì)邊插值點(diǎn)連線的交點(diǎn)一定和其中一對(duì)相對(duì)頂點(diǎn)處于同一區(qū)域。假設(shè)圖中實(shí)心點(diǎn)的場(chǎng)函數(shù)值大于給定的等值面閾值，在等值面內(nèi)，而空心頂點(diǎn)的場(chǎng)函數(shù)值小于等值面閾值，在等值面外，此時(shí)只要計(jì)算對(duì)邊插值點(diǎn)連線交點(diǎn)的場(chǎng)函數(shù)值，如果其值大于閾值，則該點(diǎn)也在等值面內(nèi)，可以確定其與兩個(gè)實(shí)心頂點(diǎn)在同一區(qū)域，如圖6（a）所示，此時(shí)二義性面上中間的六邊形區(qū)域在等值面內(nèi)，兩邊的兩個(gè)三角形區(qū)域在等值面外。相反，若對(duì)邊插值點(diǎn)連線交點(diǎn)的場(chǎng)函數(shù)值小于等值面閾值，則其在等值面外，如圖6（b）所示，此時(shí)二義性面兩邊的兩個(gè)三角形區(qū)域在等值面內(nèi)。因此通過(guò)計(jì)算對(duì)邊插值點(diǎn)連線交點(diǎn)的場(chǎng)函數(shù)值即可確定二義性面的等值線

15、連接方式。（2）算法步驟為了方便尋找二義性面，在算法實(shí)現(xiàn)過(guò)程中，除了要定義點(diǎn)類（CPoint）、邊類（CEdge）和體素類（CCube）之外，還定義了面類（CSquare），以計(jì)算一個(gè)面與等值面的交點(diǎn)個(gè)數(shù)，從而判斷是否是二義性面。在一個(gè)體素中使用插值點(diǎn)連線交點(diǎn)法確定二義性面連接方法的步驟如下：a.讀取一個(gè)體素；b.讀取第i+個(gè)面；c.如果i=5，則執(zhí)行4，否則執(zhí)行步驟e；d.如果該面與等值面的交點(diǎn)個(gè)數(shù)n=4，則計(jì)算該面上對(duì)邊插值點(diǎn)連線交點(diǎn)的場(chǎng)函數(shù)值，根據(jù)場(chǎng)函數(shù)值結(jié)果選擇相應(yīng)的連接方式，否則轉(zhuǎn)到步驟b；e.讀取下一個(gè)體元數(shù)據(jù)。在一個(gè)體元中查找面和查找一個(gè)面與等值面的交點(diǎn)數(shù)目n時(shí)，都要增加判斷條件

16、，當(dāng)前體元六個(gè)面全部查找完畢后，要重新讀取下一個(gè)體元數(shù)據(jù)；當(dāng)前面不是二義性面或者是二義性面但是已經(jīng)處理完畢后，要繼續(xù)查找下個(gè)面。（3）算法效果本算法是借鑒雙曲線漸近線算法得出的，雙曲線漸近線算法已經(jīng)解決了面二義性問(wèn)題，而本算法在解決面二義性問(wèn)題的前提下，相對(duì)雙曲線漸近線算法而言，計(jì)算量較小，等值面與四條棱邊的交點(diǎn)可以通過(guò)頂點(diǎn)坐標(biāo)插值計(jì)算求得，因此其連線交點(diǎn)比計(jì)算雙曲線漸近線交點(diǎn)要容易一些，當(dāng)然算法的前提是在重建過(guò)程中以直線段近似代替雙曲線。由圖7可見(jiàn)，比起雙曲線漸近線法，基于插值點(diǎn)連線交點(diǎn)的方法重建結(jié)果也可以達(dá)到預(yù)期效果，沒(méi)有出現(xiàn)由面二義性導(dǎo)致的表面孔洞現(xiàn)象。而二者的差別主要在計(jì)算量上，重建上

17、述圖形所需時(shí)間上表所示，使用插值點(diǎn)連線交點(diǎn)法重建三維表面所需時(shí)間少于雙曲線漸近線法，而隨著數(shù)據(jù)場(chǎng)規(guī)模的增大，這一特點(diǎn)將表現(xiàn)得更為明顯。endprint6 結(jié)論（Conclusion）Marching Cubes算法的面二義性問(wèn)題是因?yàn)檫B接方式不確定導(dǎo)致的。當(dāng)兩個(gè)相鄰體素的公共面是二義性面時(shí)，只要保證兩個(gè)體素在公共面上的等值線連接方式一樣，就可以解決這一問(wèn)題。本文借鑒了雙曲線漸近線方法的思路，通過(guò)將二義性面進(jìn)行區(qū)域劃分來(lái)確定一種唯一的連接方式，不但解決了面二義性問(wèn)題，而且因?yàn)橛?jì)算簡(jiǎn)單，使得算法更加簡(jiǎn)潔高效，取得了較好的效果。參考文獻(xiàn)（References）1 Minho Chang，et al.

18、Interactive marching cubes algorithm for intraoral scannersJ.The International Journal of Advanced Manufacturing Technology，2017，89（5-8）：2053-2062.2 Seungki Kim，et al.A Novel Interpolation Scheme for Dual Marching Cubes on Octree Volume Fraction DataJ.Computers & Graphics，2017，66（8）：169-178.3 Adriano Lopes an