移動立方體算法面二義性問題研究

王錚　李瑞明

摘 要：在三維表面建模技術中，Marching Cubes算法是應用最為廣泛的方法之一。該算法簡單高效，但是也存在一定的不足之處，比如面的二義性問題。構造等值面時，在特定情況下對相同的等值點可以采取不同的連接方式，就會產生二義性，這將使得生成的等值面拓撲結構不一致，導致物體表面模型有孔洞。針對這一問題，本文提出了一種基于插值點連線交點的解決方法，通過計算插值點連線交點的場函數值，唯一確定二義性面上等值線的連接方式，解決了面二義性，保證了等值面拓撲結構的一致。

關鍵詞：三維表面建模；Marching Cubes算法；二義性

中圖分類號：TP311 文獻標識碼：A

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 same 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 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；Marching Cubes algorithm；ambiguous cases

1 引言（Introduction）

三維表面建模是運用計算機圖形學和圖像處理技術，將科學計算過程中產生的數據及計算結果轉換為物體的表面圖形和圖像顯示出來，并進行交互處理的理論、方法和技術。隨著科學計算可視化的發(fā)展，加之圖形硬件的更新?lián)Q代，三維建模技術越來越多的應用于生活、工程和科研領域[1]。作為三維表面建模技術的經典算法之一，Marching Cubes算法至今仍然被廣泛使用，而針對算法存在的不足之處，也不斷有學者和研究人員進行研究和改進[2]。本文首先介紹了Marching Cubes算法的基本原理，然后分析了面二義性問題并且介紹了兩種經典的解決方案——四面體剖分法和雙曲線漸近線法，最后借鑒雙曲線漸近線法的思路提出了一種基于插值點連線交點的新方法，在解決面二義性問題的同時簡化了計算步驟，縮短了運行時間。

2 Marching Cubes算法原理（The principle of

Marching Cubes algorithm）

Marching Cubes算法是目前三維表面重建中基于等值面抽取中最常用的方法。它在體素中提取等值面，通過逐個處理體素，對于與等值面相交的體素，用三角片近似表示其內部的等值面片。由于算法在構造等值面的過程中會依次處理每個體素，就好像沿著體素向前移動，這是算法得名的原因。

以三維礦體建模為例，Marching Cubes算法的步驟如下：

（1）讀取相鄰兩層切片數據。

（2）體素化切片數據，將兩切片對應的相鄰四個像素構成一個立方體。

（3）按順序逐個處理體素，確定每個體素內三角面片的剖分方式。首先要確定等值面的值，即閾值，通過比較體素頂點場函數值與閾值的大小關系確定體素是否和等值面相交。頂點與等值面的關系有兩種，要么在等值面內（包括在等值面上），要么在等值面外，因此8個頂點與等值面的關系情況就有28即256種，即一個體素和等值面相交的情況有256種。接下來根據連接方式的互補對稱性和旋轉對稱性，將256種相交情況進行化解，最終得到15種[3]體素內等值面的連接方式。

（4）求體素與等值面的交點。

（5）計算表面法向量，形成光照。

3 面二義性問題（The problem of ambiguous cases）

Marching Cubes算法的面二義性問題由J.Durst首先提出[4]。在一個和等值面相交的體素中，假設其中一個面與等值面有交線，在該面的四個頂點中，如果位于一條對角線上的一對頂點的場函數值都大于等值面閾值，而另外一條對角線上的兩個頂點的場函數值都小于等值面閾值，那么此時等值線的連接方法有兩種，這就是二義性問題，這樣的面稱為二義性面，如圖2所示。如果二義性面剛好是兩個相鄰體素的公共面，在連接三角形面片的時候，一個體素采取圖2（a）的連接方式，而另外一個體素采取了圖2（b）的連接方式，此時就出現(xiàn)了相鄰體素在公共面上等值面連接方式不一致的情況，最終會導致生成的物體表面出現(xiàn)“孔洞”，不能保證曲面的封閉性。endprint

4 經典解決方法（Classic solutions）

為了解決面二義性問題，不少學者進行了研究分析，得出了一些方法，下面就其中比較典型的方法進行介紹。

（1）四面體剖分法

四面體剖分是解決面二義性問題比較簡單的一種方法。算法的思想就是把一個體素進行分割，將其分成幾個四面體，然后在每個四面體內求取與等值面的交點、提取等值面。與立方體體素相比，四面體的面都是三角形，而三角形中等值線的連接方式是唯一的。對于每個四面體，每個頂點有兩種狀態(tài)，四個頂點一共有16種狀態(tài)，根據對稱性和反轉性進行化解，最終等值面構型只有三種，如圖3（a）所示。四面體與等值面是否相交的判斷方法和立方體體素一樣，都是根據頂點場函數值與等值面閾值的關系進行判斷。如果頂點場函數值全部大于或者全部小于等值面值，那么該四面體與等值面不相交，如圖3（a）所示；如果一個頂點場函數值大于等值面值而另外三個頂點的場函數值小于等值面值，或者相反，一個頂點場函數值小于等值面值而另外三個頂點場函數值大于等值面值，則四面體與等值面相交，如圖3（b）所示；當四面體兩個頂點場函數值大于等值面值而另外兩個頂點的場函數值小于等值面值時，等值面構造如圖3（c）所示。

四面體剖分有很多種方式，可以將立方體體素分為5個、6個或更多個四面體，分割的數量不同，產生的四面體形態(tài)也不同，比如當把立方體素剖分為5個四面體時形成的四面體并不全部相同，而剖分為24個四面體時形成的四面體是全部相同的。不同的劃分方式有不同的特點，分成5個四面體時產生的三角面片較少，但是由于是不全等劃分，處理起來比較復雜。分成24個全等四面體會產生較多的三角面片，但是插值計算過程比較容易。另外，在一個立方體體素中采用不同的方式剖分四面體生成的等值面構型[5]也不同，如圖4所示。綜上所述，雖然四面體剖分法可以解決二義性問題，而且生成的物體表面比較光滑，但是由于算法過程相對比較復雜，生成的三角面片較多，因此結果不是非常理想。

（2）雙曲線漸近線法

雙曲線漸近線方法是由G.M.Nielson[6]等提出的，該方法是面二義性問題最經典的解決方法。通常情況，體素表面與等值面的交線是雙曲線。在二義性面上，交線的兩個分支將體素平面分成三部分，不管如何劃分，漸近線的交點都會和一條對角線上的兩個頂點在同一個部分。如果漸近線交點的場函數值大于等值面的場函數值，則交點與場函數值大于等值面值的兩個頂點在相同區(qū)域；如果漸近線交點的場函數值小于等值面的場函數值，則交點與場函數值小于等值面值的兩個頂點在相同區(qū)域。這是雙曲線漸近線方法的基本思想。

等值面與體素表面的相交關系有六種情況，相交產生的交點數量五種情況，其中交點數為2時相交關系有兩種，如圖5所示。相比四面體剖分法，雙曲線漸近線法沒有增加額外存儲空間，而且算法效率比較高。

MC算法的面二義性問題會導致生成的物體表面出現(xiàn)孔洞，也就是生成的表面模型不正確。針對這一問題，本文借鑒雙曲線漸近線的判別方法，提出一種解決方法，首先分別連接二義性面上處于對邊的一對交點，兩條連線會有一個交點，然后比較該交點場函數值與該面四個頂點的場函數值的關系來確定二義性面的連接方式。

（1）基本思想

Marching Cubes算法的前提是數據場沿著體素棱邊呈線性變化，即立方體網格的每條棱邊和等值面的交點最多為一個，每個面與等值面的交點最多為四個，其中與等值面交點為4的面是二義性面。重建物體表面時，等值點的連接是以直線段近似代替曲線的。因此一個二義性面上，兩條等值線將把該面分為三個區(qū)域，如圖6所示，而相對邊插值點連線的交點一定和其中一對相對頂點處于同一區(qū)域。

假設圖中實心點的場函數值大于給定的等值面閾值，在等值面內，而空心頂點的場函數值小于等值面閾值，在等值面外，此時只要計算對邊插值點連線交點的場函數值，如果其值大于閾值，則該點也在等值面內，可以確定其與兩個實心頂點在同一區(qū)域，如圖6（a）所示，此時二義性面上中間的六邊形區(qū)域在等值面內，兩邊的兩個三角形區(qū)域在等值面外。相反，若對邊插值點連線交點的場函數值小于等值面閾值，則其在等值面外，如圖6（b）所示，此時二義性面兩邊的兩個三角形區(qū)域在等值面內。因此通過計算對邊插值點連線交點的場函數值即可確定二義性面的等值線連接方式。

（2）算法步驟

為了方便尋找二義性面，在算法實現(xiàn)過程中，除了要定義點類（CPoint）、邊類（CEdge）和體素類（CCube）之外，還定義了面類（CSquare），以計算一個面與等值面的交點個數，從而判斷是否是二義性面。在一個體素中使用插值點連線交點法確定二義性面連接方法的步驟如下：

a.讀取一個體素；

b.讀取第i++個面；

c.如果i<=5，則執(zhí)行4，否則執(zhí)行步驟e；

d.如果該面與等值面的交點個數n=4，則計算該面上對邊插值點連線交點的場函數值，根據場函數值結果選擇相應的連接方式，否則轉到步驟b；

e.讀取下一個體元數據。

在一個體元中查找面和查找一個面與等值面的交點數目n時，都要增加判斷條件，當前體元六個面全部查找完畢后，要重新讀取下一個體元數據；當前面不是二義性面或者是二義性面但是已經處理完畢后，要繼續(xù)查找下個面。

（3）算法效果

本算法是借鑒雙曲線漸近線算法得出的，雙曲線漸近線算法已經解決了面二義性問題，而本算法在解決面二義性問題的前提下，相對雙曲線漸近線算法而言，計算量較小，等值面與四條棱邊的交點可以通過頂點坐標插值計算求得，因此其連線交點比計算雙曲線漸近線交點要容易一些，當然算法的前提是在重建過程中以直線段近似代替雙曲線。

由圖7可見，比起雙曲線漸近線法，基于插值點連線交點的方法重建結果也可以達到預期效果，沒有出現(xiàn)由面二義性導致的表面孔洞現(xiàn)象。而二者的差別主要在計算量上，重建上述圖形所需時間上表所示，使用插值點連線交點法重建三維表面所需時間少于雙曲線漸近線法，而隨著數據場規(guī)模的增大，這一特點將表現(xiàn)得更為明顯。endprint

6 結論（Conclusion）

Marching Cubes算法的面二義性問題是因為連接方式不確定導致的。當兩個相鄰體素的公共面是二義性面時，只要保證兩個體素在公共面上的等值線連接方式一樣，就可以解決這一問題。本文借鑒了雙曲線漸近線方法的思路，通過將二義性面進行區(qū)域劃分來確定一種唯一的連接方式，不但解決了面二義性問題，而且因為計算簡單，使得算法更加簡潔高效，取得了較好的效果。

參考文獻（References）

[1] Minho Chang，et al.Interactive marching cubes algorithm for intraoral scanners[J].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 Data[J].Computers & Graphics，2017，66（8）：169-178.

[3] Adriano Lopes and Ken Brodlie.Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurface[J].IEEE Transactions on Visualization and Computer Graphics，2003，9（1）：l6-29.

[4] Durst，M.J.Additional reference to Marching cubes[J].Comput.Graph，1988，22（2）：72-73.

[5] P.Cignoni，et al.Reconstruction of topologically correct and adaptive trilinear surfaces. Computers and Graphics，2000，24（3）：399-418.

[6] Nielson G，Hamann B.The asymptotic decider：resolving the ambiguity in marching cubes[C].Proceedings of Visualization' 91，Los Alamitos CA，1991.

作者簡介：

王 錚（1985-），男，碩士，助教.研究領域：計算機圖形學.

李瑞明（1989-），男，碩士，助教.研究領域：算法研究.endprint