基于八叉樹的簡化構型三角片等值面削減算法

徐雷， 王華鋒， 潘海俠， 林廣艷， 陳櫟曦

(北京航空航天大學 軟件學院, 北京 100083)

可視化技術是諸多數據密集型領域的一種重要研究手段。近年來，等值面算法在三維數據場可視化方面得到了廣泛地應用和發展。Lorensen和Cline[1]于1987年提出的MC(Marching Cubes)算法作為等值面提取最為流行的經典算法，其原理簡單易于實現，自從被提出以來，得到了業界廣泛地使用，包括生物化學[2]、生物醫學[3-4]、數字雕刻[5]、環境科學[6]、自然現象呈現[7]以及可視化算法分析[8]等。但經典的MC算法也有一些不足之處，如存在拓撲結構的二義性[9]、對高分辨率數據集計算效率低[10-11]及產生的結果集規模龐大[12]等問題。

近年來，針對MC算法的改進層出不窮。本文著眼于MC算法產生結果集規模龐大這一問題，介紹了現階段主要的改進方法，并且介紹了一種基于簡化構型的SMC(Simplified Marching Cubes)算法。根據簡化構型的特點，針對SMC算法的兩方面問題提出了一種改進的OSMC(Octree based Simplified Marching Cubes)算法，依次介紹了算法的八叉樹構建、八叉樹收縮和三角片提取3步。在實驗與討論的部分通過對MC算法、SMC算法、OSMC算法三者實驗數據的對比，從表面形態、三角片削減率和分辨率增長3個方面說明OSMC算法的優勢并探討了其原因。

1 相關研究成果

近年來，越來越多的高分辨率數據集被投入使用。MC算法產生龐大的三角片數量給后期的渲染造成了很大壓力，同時也加重了存儲負擔。不少研究人員針對這一問題，提出了諸多解決方案。總體上看，這一問題的解決方案大致分為兩類。

第一類是對生成的網格數據采取網格削減算法。如Schroeder等[13]于1992年提出的漸進網格算法與Garland和Heckbert[14]于1997年提出的二次誤差邊折疊算法。這類算法的輸入是多邊形網格數據，是在規模較大的網格數據已經被生成之后再采用一定方式來刪除頂點面片等幾何元素，是一種事后補救方法。這類方法通常處理費時，并且建立輔助結構會占據大量存儲空間，并不是針對本文提出問題的理想解決方案，因此不作過多探討。

第二類是采取避免生成較多三角片的表面重建方法。相比于事后削減的方法，這一類方法利用了圖像數據的特點，效率更高。Montani等[15]提出了一種離散化的DiscMC算法，這種算法通過將插值點選擇在體元邊的中點，提高了相鄰體元間的三角形共面的概率。然后再將共面的三角形合并成平面多邊形，以此來減少三角片。其在2000年又進一步改進了此方法，提高了DiscMC算法對等值面的逼近程度[16]。Shu等[17]于1995年提出一種自適應的MC算法，這種算法在執行過程中不斷地重復對體數據劃分子體，直到在子體內尋找到相對于等值面的誤差在一定范圍內逼近表面。這樣就能夠實現使用較少的三角片來表示等值面。Shekhar等[18]于1996年針對Shu等[17]的方法削減程度不足的問題又提出了一種使用了八叉樹結構削減三角片的算法，其中使用了表面追蹤技術，避免了處理空體元。在體元合并中評估誤差，保證誤差在給定閾值之內，最后修補縫隙、生成三角片。八叉樹是在表面重建算法中重要的一種數據結構，能夠用于代表隱函數[19-20]和自適應提取等值面[21-22]。

上述幾種方法均是利用了等值面局部形態特點來進行三角片削減，Cui和Liu[23]于2008年與Vignoles等[24]于2011年各自提出了一種不同于上述幾種方法簡化思路的算法。2種算法實現細節有所不同，但其核心思想一致，都使用了一種簡化后的體元構型，為方便起見將文獻[13-14]提出的方法統一稱作SMC算法。使用簡化后的構型，減少了部分體元中提取三角片的數量，從而削減了三角片數，同時提高了計算效率，并且不會存在二義性問題。SMC算法在對低分辨率數據使用時產生的表面與MC算法差別顯著，逼近程度低于MC算法，故未能有廣泛應用。但隨著近年來高分辨率數據得到越來越多的應用，簡化構型的優勢便體現出來。在高分辨率數據上，SMC算法和MC算法產生的表面的形態差別變得幾乎可以忽略不計，故其為MC算法的合理替代方案，并且廣泛應用于實踐之中。但由于簡化構型僅是在體元內部的簡化，無法考慮等值面局部形態特征，因而SMC算法存在較大的改進空間。主要體現在如下2個方面:

1) 對于部分數據集，SMC算法削減率較低。原因在于并非所有的簡化構型都比MC算法構型具有更少的三角片數，若數據場內有相當比例活動體元正屬于這類構型，則SMC算法無法削減這些體元的三角片數。

2) 無法很好地應對分辨率的提高。原因在于體數據分辨率提高后體元數量會大大增加，僅是體元內部的簡化無法應對體元總數的增加帶來的影響。

本文提出的OSMC算法，既利用了簡化構型的優點，同時也考慮了等值面局部形態特征。OSMC算法與SMC算法產生的表面形狀完全相同，但三角片數量更少。并且對于具有較多平坦區域的數據集，OSMC算法能有效地彌補SMC算法削減程度不足的問題，同時還能夠較好地應對數據集分辨率的增長。

2 OSMC算法

2.1 簡化構型

SMC算法中的簡化構型是基于MC算法構型做出的簡化模型。

假設等值面sc={(x,y,z):F(x,y,z)=c}，其中sc為等值面集合，(x,y,z)為點的坐標，F為映射函數，c為等值面的值。若等值面穿過了2個相鄰體素所構成的邊，體素位置坐標分別為Vl(xl,yl,zl)和Vh(xh,yh,zh)，相應體素值分別為Il

(1)

若將插值點的位置總取為Vh，即

V=Vh

(2)

則會使一部分三角形的頂點位置重合，如此操作，便會導致生成的三角形產生退化。對MC算法的所有基本構型采取式(2)的操作即形成簡化構型，即SMC算法構型。圖1和圖2中對比顯示了15種MC算法構型與其對應的SMC算法構型。可以看出在簡化構型中一部分三角形在頂點移動后退化消失，導致多種構型產生的三角形減少甚至消失，也直接導致最終產生的等值面的三角形的數量會相應減少。

將基于簡化構型提取出三角片所構成的表面成為SMC表面。SMC表面相比于MC表面有如下3個特點：①SMC表面的所有三角片的頂點都是體素點；②組成SMC表面的三角片只有3種可能形狀和有限種法線方向；③與MC表面相比，SMC表面位置略向高于等值面的方向偏移，形成一定的系統誤差，此誤差隨著數據集分辨率的提高而減少。

OSMC算法是基于八叉樹的特性來實現局部共面三角片的合并。OSMC算法一共分為3步:八叉樹構建、八叉樹收縮以及三角片提取，流程如圖3所示。2.2～2.4節分別對這3個步驟進行詳細說明。

圖1 MC算法構型Fig.1 MC algorithm configuration

圖2 SMC算法構型Fig.2 SMC algorithm configuration

圖3 OSMC算法流程Fig.3 Flowchart of OSMC algorithm

2.2 八叉樹構建

2.2.1 活動體元尋找方法

無論是MC算法還是SMC算法，插值和提取三角片等計算都是針對活動體元。活動體元的8個頂點體素根據其體素值大小共有256種有限的情況，每一種情況即是一個體元狀態(cube configuration)。若令體元C的8個端點體素值依次為I0，I1，…，I7，則體元狀態的計算方法如下:

(3)

config(C)=B0∨B1…∨B7

(4)

式中:Bi為體元狀態;isovalue為等值面的值;Ii為體素值;∨符號代表位運算或。

config(C)不為0或255的體元即為活動體元。標準MC算法是通過全維度掃描所有體元，逐個求取體元狀態config(C)來尋找活動體元，而往往活動體元只占全部體元總數的很小一部分，這導致算法近80%的計算時間花費在訪問非活動體元上。為了提高時間效率，不少算法采用其他方式去尋找活動體元，例如文獻[21]采用八叉樹組織圖像數據，文獻[18]的表面追蹤。但這些方法都有一定的局限性，往往只適用于某些有特殊性的場合。例如文獻[21]的方法主要針對一次預處理、多次重建的應用場合；而文獻[18]的方法必須人工選擇種子體元作為輸入參數。一般場合下，數據場體素值分布情況應當是完全未知的，任何一個體元都必須至少被遍歷到一次才能獲取其體元狀態。所以為了不失一般性，OSMC算法采用遍歷所有體元的方式尋找活動體元。實際上，任何方法只要能利用實際應用場合的特點找到活動體元，都可以替代全部遍歷的方式。采用何種方式取決于對算法時間效率和通用性的權衡。

2.2.2 為活動體元創建節點

對每一個活動體元，需要為其創建對應的節點。OSMC算法采用指針式八叉樹，其任意節點N均包含父節點p和8個子節點c0，c1，…，c7的指針以及一個數據域data，為了讓每個節點總能指代自然數表示的立方體范圍，八叉樹對空間按2的冪劃分。因此OSMC算法的八叉樹T所指代的空間尺寸應為大于體數據最長維的最小的2的冪。設數據場為:DF={(x,y,z),x∈[0,w],y∈[0,h],z∈[0,d]}，則T的深度計算式為

n=depth(T)=「lb(max{w+1,h+1,d+1})?

(5)

則T實際所能表示的最大空間包圍盒R(T)在3個坐標軸上范圍均為[0,2n-1]。對T中任意非葉節點，其子節點對應著將父節點空間范圍各個維度等分之后的子立方體空間范圍。依據這樣的劃分方式，利用節點之間的父子關系即可以求出N所指代的空間包圍盒R(N)。對于葉子節點，R(N)的3個維度的上下界均相等，即有

R(Nleaf)={(xmin,ymin,zmin)}

(6)

因而葉節點Nleaf可以與一個三維坐標對應。樹的初始狀態只包含一個根節點。每當找到一個活動體元C(x,y,z)，為其建立葉節點需要確定其在各層的層內索引ki,0≤i≤n-1。層內索引反映了從根節點建立葉節點的路徑，利用八叉樹空間劃分與體元坐標二進制位的對應關系，能夠求得層內索引。層內索引的求法如下：

ki=4×[x?(n-i)∧ 1 ]+2×

[y?(n-i)∧ 1]+1×[z?(n-i)∧ 1]

(7)

式中：符號“∧”代表位運算與；符號“?”代表位運算邏輯右移。

本步驟執行到對所有活動體元都有對應的節點為止。經過此步形成的八叉樹有如下2個特點：①八叉樹的所有葉節點與活動體元坐標一一對應。②所有的葉子節點均處在同一深度。

2.3 八叉樹收縮

八叉樹收縮是一個自底向上迭代的過程。從八叉樹depth(T)-1層節點開始，嘗試將子節點的信息歸并到父節點，相應節點內的體元合并成為更大的“超體元”(super cell)，若成功則刪除子節點。這一步驟的關鍵是判斷節點能夠收縮的條件。為此首先提出“共面構型”的概念，共面構型是指滿足如下任意條件之一的體元構型：

1) 該體元為空體元。

2) 該體元構型內含有三角片且三角片均在同一平面。

3) 該體元構型內不含三角片，但其互補構型內含有三角片且三角片均在同一平面。

圖1和圖2中符合條件2)的構型均為第8、9號構型；符合條件3)的為第1、2號構型；其余10種構型為非共面構型。

OSMC算法收縮節點的基本原理是：對八叉樹上的一個節點N，若其子節點c0，c1，…，c7中分別提取的三角片構成集合Tc，Tc中所有三角片均共面且有相同的法向量，則此三角片集合組成的形狀等價于對N提取三角片集合TN所組成的形狀，且一定有Card(TN)≤Card(Tc)成立。這樣使用更少的三角片組成相同平面區域就能實現三角片數量的削減。顯然只有屬于共面構型的c0,c1,…,c7才能滿足此條件，共面構型為有限種可枚舉的情況，因此上述原理不難被證明。這樣節點收縮的問題便轉化為子節點中提取的三角片是否共面的問題。

在空間解析幾何中，平面方程一般形式為Ax+By+C′z=D，三元組(A,B,C′)是決定法線方向的參數。而D值反映了其空間位置。2個三角片若共面，則其一定具有相同的法線方向和D值。通過2.1節對構型的分析可以得知，共面構型內三角片所在的平面方程形式只可能是如表1的13種可能。

表1 平面方程類型Table 1 Types of plane equation

對于位置在數據場原點的共面構型的體元C0(0,0,0)，三角片的方程A0x+B0y+C0z=D0是由體元狀態config(C0)唯一決定的。因為方程形式只有有限種，所以可以建立兩者的函數映射關系：方程：config(C)→(Ac,Bc,Cc,Dc)和法向量：config(C)→(Ac,Bc,Cc)。一般地，對于共面構型體元C(xc,yc,zc)，其三角片所在平面方程相對C0存在一個平移關系，方程解析式為

Ac(x-xc)+Bc(y-yc)+Cc(z-zc)=Dc

(8)

令D=Acxc+Bcyc+Cczc+Dc，則四元組(Ac,Bc,Cc,Dc)就能夠反映體元C中三角片相對于整個數據場F的平面方程。又由于具有映射關系：方程：config(C)→(Ac,Bc,Cc)，所以二元組即能充分反映體元的三角片位置信息。八叉樹的所有葉節點，由于和活動體元一一對應，所以其形式為

Nleaf={p,c0，c1，…,c7,}

(9)

綜上所述，八叉樹T上任意一個節點N能收縮，其子節點c0,c1,…,c7必須滿足如下條件：

1) 若N為葉節點，非空ci為共面構型。

2) 若N不為葉節點，非空ci為收縮成功的節點。

3) 對于任意非空的ci,cj,i≠j，有

normal(config(ci))=normal(config(cj))

(10)

4) 對于任意非空的ci,cj,i≠j，有Di=Dj。

收縮操作首先對倒數第2層節點執行，每成功執行一次收縮操作，當前節點記錄下的從子節點繼承來的D值，并利用config(c0),config(c1),…,config(c7)計算config(N)，同時刪掉子節點。當某個節點收縮操作失敗后，其父節點也不再進行收縮，直到所有的節點都不能再收縮后結束。可以采用FIFO的容器實現這樣自底向上的迭代操作。

2.4 三角片提取

八叉樹T收縮完成后，葉節點不再都處于同一深度，一部分節點對應單體元，即處在depth(T)層的節點。而在depth(T)層之上的葉節點對應的是“超體元”。超體元即是收縮了下層節點后形成的廣義體元。對單體元和超體元，提取三角片的方法有所不同。OSMC算法本步驟采用程序遍歷八叉樹葉節點，依次判斷節點屬于單個體元還是超體元。對其分別用不同的方法求取三角片集合TN，直到所有葉節點都被訪問為止。

2.4.1 對單體元的三角片提取

節點N對應單個體元即說明N的父節點收縮失敗。由2.1節對SMC算法的分析可知其生成三角片的頂點都位于體素點上。對N的三角片提取可直接使用SMC算法的查找表，根據體元狀態索引即可獲取三角片體元頂點的組成方式，而三角片頂點的位置可由節點空間范圍R(N)確定，這樣就得到三角形集合TN，即

(smctable(config(N)),R(N))→TN

(11)

2.4.2 對超體元的三角片提取

超體元節點N中雖然三角片的頂點依然是體素點，但不一定是超體元的8個頂點。如圖4所示。

從該超體元對應的八叉樹節點數據域中可以獲得三角片空間位置信息，則三角片所在的平面方程參數便可以求取。因為三角片的頂點實在超體元邊上，需要使用標準MC算法的查找表來確定被穿過的體元邊集合EN和三角片的集合TN的信息，即

EN=mctable(config(N))

(12)

(config(N),EN)→TN

(13)

之后再采用空間解析幾何的方法，通過EN中每一條體元邊ei的直線方程與平面方程ANx+

圖4 超體元提取三角片Fig.4 Triangle extraction for super cell

BNy+CNz=DN聯立求解三角片頂點位置，公式如下：

(14)

3 實驗與討論

本節將通過實驗證明OSMC算法的優越性。本文算法采用C++實現，實驗硬件平臺為 Intel(R) Xeon(R) X5650 6核 CPU，內存 32 GB，操作系統為64位Windows 7。所有實驗均在相同的軟硬件環境下進行。

3.1 公開數據集實驗

OSMC算法被應用于公開數據集上進行測試。圖5為MC算法、SMC算法和OSMC算法分別對尺寸為256像素×256像素×128像素的Engine數據集重建表面后形成的模型預覽圖。可以看出，表面的整體形態上三者區別并不明顯，而將圖像的局部進行放大后，如圖6所示，可以看出MC表面與SMC表面細節上略有差別，而OSMC表面與SMC表面是完全一致的。也就是OSMC表面對等值面的逼近誤差與SMC算法是相同的。該誤差產生的原因是因為使用了SMC算法簡化構型，在分辨率不算高的Engine數據上能夠在細節上體現出與MC表面的區別。

圖7為MC算法、SMC算法和OSMC算法在Engine數據集局部位置三角片集合的構成情況。從對比圖中可以看出：SMC算法在形狀不規則的區域的三角片密度低于MC算法，但在平坦區域的三角片密度和MC算法一樣；OSMC算法在平坦區域合并了大部分共面三角片，使角片密度降低，而在形狀不規則區域三角片密度和SMC算法相同。綜合起來看，OSMC算法相比于MC算法，既在形狀不規則區域具有較低三角片密度，也在平坦區域有更少三角片密度，不過細節部分略有損失。而與SMC算法比較而言，細節部分保存完好，更顯優勢。

圖5 3種算法對Engine 數據產生的表面全視圖Fig.5 Isosurface full view of three algorithms on Engine data set

表2列舉了9組數據集分別在MC算法、SMC算法、OSMC算法下重建表面生成的三角片總數，以及OSMC算法對MC、SMC算法的削減率對比。可以看出，對于不同的數據集，算法的削減程度有所差別。SMC算法在對總體形態不規則程度較高的數據集上相比MC算法有較好的削減率，例如Skull、Lobster數據集。OSMC算法的削減程度則相對較低，但也依然超過了SMC算法。在具有較大比例規則表面的數據集上，OSMC算法表現非常出色，在SMC算法的基礎上依然有顯著的削減，例如Engine、Fan、Table和Teapot數據集，并且可以很好地保留SMC算法的所有細節。

圖6 細節表面圖Fig.6 Detailed surface

圖7 表面三角片構成情況Fig.7 Composition of surface triangle

數據集三角片數削減率/%MC算法SMC算法OSMC算法OSMC較SMC算法OSMC較MC算法Engine622764432370259479-40．0-58．3Fan508928370256179179-51．6-64．8Table47554843969290073-79．5-81．1Teapot745152508798304008-40．2-59．2Bonsai644340435994372986-14．5-42．1Skull184240411142081033229-7．3-43．9Backpack398583628760442066527-28．1-48．2Phantom745731652968683557633-32．8-52．3Lobster1245556721914632738-12．4-49．2

3.2 人類肺部結節CT數據實驗

將OSMC算法應用于真實的人類肺部結節CT數據，數據的最大分辨率為55像素×55像素×120像素。

如圖8所示，人類肺部結節形狀不規則，細節部分很多。細節部分對于診斷病情卻至關重要，而OSMC算法在這方面表現得很好，對細節刻畫很仔細，能夠生成和SMC算法完全一樣的網格。

表3列出了針對不同病人的完全不同的肺部結節CT數據，以及MC、SMC和OSMC算法生成的三角片的個數。可以看出，對于不同的肺部結節數據，盡管OSMC與SMC算法生成的網格形狀是完全一樣的，但是OSMC算法生成的三角片更少，最多能少20%左右。

圖9展示了圖8中肺部結節上不平滑的一個小觸角處生成的網格形狀。可以看出，OSMC和SMC算法生成的形狀完全一樣，但是在SMC算法生成的形狀一致的幾個相鄰三角片處，OSMC算法能夠合并簡化網格，使生成的三角片數量減少。

圖8 3種算法人體肺部結節數據產生的網格和表面全視圖Fig.8 Mesh and isosurface full view of three algorithms on human pulmonary nodule data set

數據集三角片數削減率/%MC算法SMC算法OSMC算法OSMC較SMC算法OSMC較MC算法肺部結節11165275246498-13．64-44．23肺部結節2199213661160-15．08-41．77肺部結節3370425642012-21．53-45．68肺部結節417360107449198-14．39-47．02肺部結節516212100988623-14．61-46．81肺部結節6250521625813583-16．45-45．78肺部結節7443442563824213-5．56-45．40肺部結節8199721171411350-3．11-43．17總計-10．80-45．37

圖9 3種算法人體肺部結節CT數據結果表面細節三角片構成情況Fig.9 Triangles mesh part view of three algorithms on CT human pulmonary nodule data set

綜上，OSMC算法在面對等值面較粗糙細節較多的數據時，能夠完整地保留等值面的所有細節部分，不會改變生成的等值面的形狀，并且在相對平滑的部分完成合并簡化，有效地減少了生成的三角片的數量。

3.3 地質數據實驗

筆者還在真實的地質斷面分離數據上測試了OSMC算法，其中最大數據的分辨率為1 000像素×1 000像素×500像素。圖10展示了MC、SMC和OSMC算法對同一個地質斷面數據生成的等值面，由于分辨率很高，可以看出，OSMC算法生成的結果與MC算法很相近，與SMC算法完全一樣。

表4列出了在7個不同的地質斷面分離數據上使用這3個算法生成的等值面的三角片個數以及相對于標準MC、SMC算法，OSMC算法生成三角片的數量的減少比率。顯然，OSMC算法在此類數據上表現非常好，相對于MC和SMC算法，OSMC算法生成的三角片數量都遠少于前者，減少比率最高可以達到80%，平均都在50%以上。

圖11展示了OSMC算法之所以表現的如此優異的原因。因為地質斷面數據在其外部邊緣處非常平滑，并且數據量巨大，傳統的MC和SMC算法對每一個小的區域都要生成一個三角片。但其實這些三角片都是共面并且完全一樣的，而OSMC算法可以將這些很多共面的小的三角片合并成一個大的三角片。這樣既沒有改變等值面的形狀，并且大大減少了處于邊緣的平滑的部分三角片數量。MC算法需要生成幾萬乃至幾十萬個三角片，但是OSMC算法只需要幾百或者幾千個就可以了。

圖10 3種算法對地質體數據產生的表面全視圖Fig.10 Isosurface full view of three algorithms on geological data set

圖12展示了在地質斷面部分MC、SMC和OSMC算法生成的等值面的結果。可以看出，OSMC算法生成的等值面與SMC算法完全一樣，沒有丟失任何原本的斷面信息，并且在局部共面的地方進行了合并簡化，使生成的三角片相應減少。

綜上可以看出，本文OSMC算法在這種局部相對平滑的數據表現非常好。一方面，其生成的等值面的三角片數量較MC和SMC算法有很大比例的減少;另一方面，在需要精細刻畫的局部，OSMC算法沒有因為合并而改變原本等值面的形狀，也就沒有丟失任何信息。

表4 地質體數據結果三角片數及削減率的對比

圖11 地質體數據集上平滑部分的三角片構成情況Fig.11 Triangle mesh of flat area of geological data set

圖12 地質體數據集上非平滑部分的三角片構成情況Fig.12 Triangle mesh of uneven area of geological data set

3.4 分辨率增長下的實驗

表5和表6分別列舉了Table數據集和四面體數據集中MC算法、SMC算法和OSMC算法在數據集分辨率增加為原來的1、2、3、4倍時，三角片數量的增長情況。可以看出，當數據集分辨率變為原來的n倍后，MC算法和SMC算法的三角片數量變為接近原來的n2倍。而OSMC算法則以低于n2的速度增長。圖13和圖14中通過曲線來反映增長趨勢，由于MC算法和SMC算法增長倍率相差很小，故曲線幾乎合并為一條，而OSMC算法的倍率曲線則明顯較低。其原因在于OSMC算法在八叉樹收縮的步驟中合并了局部平坦區域中的體元，在分辨率提升的情況下，雖然這些區域的體元密度增加，但仍然會合并成相同的超體元。

從圖13和圖14中還可以看出，對于具有更大比例平坦表面的數據集，如四面體數據集，其增長曲線相比Table數據集更低。根據OSMC算法的特點不難推斷，若數據集不規則表面比例增大，則OSMC算法增長曲線會向MC和SMC算法的增長曲線靠近。這也說明OSMC算法削減程度與數據集表面的形態特征有關。

表5 Table數據集4種分辨率下實驗結果

表6 四面體數據集4種分辨率下實驗結果Table 6 Experimental results under four resolutions for tetrahedral data set

圖13 Table數據增長曲線Fig.13 Table data growth curves

圖14 四面體數據增長曲線Fig.14 Tetrahedral data growth curves

4 結 論

本文在簡化構型等值面的基礎上提出了普適通用的OSMC算法，使用八叉樹結構合并了等值面局部的部分共面三角片。

1) OSMC算法相對于SMC算法能進一步減少三角片的數量，同時保證生成表面的形態與其完全一致。

2) OSMC算法的削減效果在具有較多平坦區域的數據集上表現顯著，能有效彌補SMC算法對這類數據集削減程度不足的問題。

3) OSMC算法對實驗數據的平均削減率為55.1%，高于SMC算法的29.7%，在面對高分辨率的地質數據時其最高削減率達到了80%，平均也超過了50%，效果尤為明顯。

4) 在數據集分辨率逐漸增大的情況下,OSMC算法的結果集規模會以低于MC算法和SMC算法的速率增長。

OSMC算法也存在如下2方面的問題：一是合并體元的條件設置局限在共面構型上，限制了削減率的進一步提升。二是八叉樹的劃分方式可能會把共面三角片分在非兄弟節點上，這樣的情況在收縮時無法合并。所以下一步的研究方向是改善算法的合并條件以及八叉樹的收縮過程，進一步增加算法的削減率。

參考文獻 (References)

[1] LORENSEN W E,CLINE H E.Marching cubes: A high resolution 3D surface construction algorithm[C]∥ACM Siggraph Computer Graphics.New York:ACM,1987,21(4):163-169.

[2] HEIMBACH I,RHIEM F,BEULE F,et al.pyMolDyn:Identification,structure,and properties of cavities/vacancies in condensed matter and molecules[J].Journal of Computational Chemistry,2017,38(6):389-394.

[3] YIM P J,VASBINDER G B C,HO V B,et al.Isosurfaces as deformable models for magnetic resonance angiography[J].IEEE Transactions on Medical Imaging,2003,22(7):875-881.

[4] BRONSON J R,SASTRY S P,LEVINE J A,et al.Adaptive and unstructured mesh cleaving[J].Procedia Engineering,2014,82:266-278.

[5] FERLEY E,CANI M P,GASCUEL J D.Practical volumetric sculpting[J].The Visual Computer,2000,16(8):469-480.

[6] STEIN R,SHIH A M,BAKER M P,et al.Scientific visualization of water quality in the Chesapeake bay[C]∥IEEE Visualization Conference.Piscataway,NJ:IEEE Press,2000:509-512.

[7] TREMBILSKI A.Two methods for cloud visualisation from weather simulation data[J].The Visual Computer,2001,17(3):179-184.

[8] KIM K,WITTENBRINK C M,PANG A.Data level comparison of surface classification and gradient filters[C]∥Volume Graphics 2001.Berlin:Springer,2001:19-34.

[9] NIELSON G M,HAMANN B.The asymptotic decider:Resolving the ambiguity in marching cubes[C]∥Proceedings of the 2nd Conference on Visualization’91.Piscataway,NJ:IEEE Press,1991:83-91.

[10] RECK F,DACHSBACHER C,GROSSO R,et al.Realtime iso-surface extraction with graphics hardware[C]∥Eurographics.

Geneva:Eurographics,2004:1-4.

[11] JOHANSSON G,CARR H.Accelerating marching cubes with graphics hardware[C]∥Proceedings of the 2006 Conference of the Center for Advanced Studies on Collaborative Research.Armonk:IBM Corporation,2006,6:39.

[12] NEWMAN T S,YI H.A survey of the marching cubes algorithm[J].Computers & Graphics,2006,30(5):854-879.

[13] SCHROEDER W J,ZARGE J A,LORENSEN W E.Decimation of triangle meshes[C]∥ACM Siggraph Computer Graphics.New York:ACM,1992,26(2):65-70.

[14] GARLAND M,HECKBERT P S.Surface simplification using quadric error metrics[C]∥Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques.New York:ACM Press/Addison-Wesley Publishing Co.,1997:209-216.

[15] MONTANI C,SCATENI R,SCOPIGNO R.Discretized marching cubes[C]∥Proceedings of the Conference on Visualization’94.Piscataway,NJ:IEEE Press,1994:281-287.

[16] MONTANI C,SCATENI R,SCOPIGNO R.Decreasing isosurface complexity via discrete fitting[J].Computer Aided Geometric Design,2000,17(3):207-232.

[17] SHU R,ZHOU C,KANKANHALLI M S.Adaptive marching cubes[J].The Visual Computer,1995,11(4):202-217.

[18] SHEKHAR R,FAYYAD E,YAGEL R,et al.Octree-based decimation of marching cubes surfaces[C]∥7th Annual IEEE Conference on Visualization.Piscataway,NJ:IEEE Press,1996:335-342.

[19] OHTAKE Y,BELYAEV A,ALEXA M,et al.Multi-level partition of unity implicits[C]∥ACM Siggraph 2005 Courses.New York:ACM,2005:173.

[20] KAZHDAN M,HOPPE H.Screened poisson surface reconstruction[J].ACM Transactions on Graphics (TOG),2013,32(3):29.

[21] WILHELMS J,VAN GELDER A.Octrees for faster isosurface generation[J].ACM Transactions on Graphics (TOG),1992,11(3):201-227.

[22] WESTERMANN R,KOBBELT L,ERTL T.Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces[J].The Visual Computer,1999,15(2):100-111.

[23] CUI S H,LIU J.Simplified patterns for extracting the isosurfaces of solid objects[J].Image and Vision Computing,2008,26(2):174-186.

[24] VIGNOLES G L,DONIAS M,MULAT C,et al.Simplified marching cubes:An efficient discretization scheme for simulations of deposition/ablation in complex media[J].Computational Materials Science,2011,50(3):893-902.