劉尚武，魏 巍,3，段曉東，劉勇奎

三維模型有向三角面片鏈碼壓縮方法

劉尚武1,2，魏 巍1,2,3，段曉東1,2，劉勇奎1

(1. 大連民族大學計算機科學與工程學院，遼寧 大連 116600； 2.大連民族大學大連市民族文化數字技術重點實驗室，遼寧 大連 116600； 3. 大連海事大學信息科學技術學院，遼寧 大連 116026)

首先提出一種適用于三角面片鏈碼算法的改進MC規(guī)格化方法，使用單位為2的體素作為改進MC算法中的單位體素，并使用其中的27個頂點重新構建等值面，最終獲取高質量的規(guī)格化三角網格模型。在新的規(guī)格化模型上提出一種新的面片遍歷方式，在三角面片鏈碼算法的基礎上，采用優(yōu)先遍歷右連接面片原則，控制面片的遍歷方向，該方法能夠減少面片遍歷次數，并且延長面片鏈碼的平均長度。實驗結果表明，采用新的規(guī)格化方法和新的遍歷方法，壓縮效果與原三角面片鏈碼相比，具有明顯的提升。

面片鏈碼；三維模型；體素；規(guī)格化

如今，三維模型被廣泛地應用于各行業(yè)中。隨著計算機硬件的發(fā)展，尤其是圖形計算及顯示能力的提高，圖形工作者為了追求高質量的三維模型，不斷提高三維模型的精度，從而增加了模型的數據量。例如：使用激光掃描儀得到的高精度稠密點云模型；為了追求高逼真紋理貼圖而構建的稠密網格模型；以及通過多幅圖像拼接融合構建的大場景三維模型等。其中最為基本的是模型的頂點數量以及面片數量的增加。高精度的三維模型在視覺上具有很好的表示效果，但在非圖形處理的普通計算機中，仍受到處理器性能、存儲空間以及傳輸速度等限制。

為了減少三維模型的存儲空間，研究人員在三維模型數據壓縮技術上做了大量的研究。其中一個研究方向是用鏈碼技術對三維模型數據進行壓縮。比如經典的FREEMAN[1]鏈碼。其首次提出用鏈碼表示三維數字曲線，在三維空間中，把鏈碼結構在體素上量化，每個體素圴有26個方向，以此構建三維模型的體素節(jié)點，該方法也被稱為F26鏈碼。之后，鏈碼技術被廣泛地應用于三維模型的表示。BRIBIESCA[2]提出用基于正交方向的二進制鏈碼技術來表示三維曲線。在正交的2個線段上，僅用0和1兩個二進制編碼來表示下一個正交線段方向，以此類推用二進制編碼序列表示三維曲線。SáNCHEZ-CRUZ等[3]提出一種三維相對鏈碼，由參考向量、支持向量和變化方向向量組成，該方法在26個連通分量的三維體素中搜索相對變化，得到有向最簡路徑。

鏈碼技術不僅在三維曲線的表示上有著較好的效果，在三維模型表面的表示中同樣表現優(yōu)異。ROSSIGNAC[4]提出的Edgebreaker算法是較早的拓撲壓縮算法之一，該算法使用了鏈碼壓縮的思想。其原理是在遍歷模型網格過程中，始終維持一個有向邊界，用于區(qū)分已遍歷面片和未遍歷面片，用5個標識符記錄當前遍歷面片與邊界的關系，得到面片的遍歷順序，最終使用Huffman編碼得到壓縮效果。文獻[5-7]是對Edgebreaker算法的改進，在提高壓縮效率的同時，保留了鏈碼技術的思想。LEMUS等[8]提出一種表示三維模型表面的鏈碼方法，并定義了9個方向的變化，對每個方向賦予一個碼值，可用一條鏈碼表示全封閉三維模型。該方法可用于表示任何全封閉模型的體素化表面。魏巍等[9]提出了三角面片鏈碼算法，其在基于體素規(guī)格化面片的基礎上，定義了13種連接邊，用連接邊和面片第三點的位置來表示三角面片，并對此編碼。由于鏈碼本身的平移不變形和旋轉不變性，在表示三維模型時不會破環(huán)其原有拓撲結構，并能夠完整地還原三維曲線或三維模型。以上研究成果均體現了其優(yōu)點。

本文提出一種用于三角面片鏈碼算法的三維模型重構方法。同時在參考文獻[9]三角面片鏈碼算法的基礎上，提出一種新的三角網格遍歷方法，有向三角面片鏈碼。在模型規(guī)格化算法(marching cubes，MC)[10]的基礎上進行改進，通過改變體素單位長度，以及重新定義MC算法中的等值面，獲得可用于三角面片鏈碼算法的規(guī)格化模型。在數據壓縮時，通過控制三角面片的遍歷方向，增加三角面片鏈的平均長度，從而減少面片鏈的數量，對三角面片鏈進行編碼，實現三維模型的數據壓縮。該方法能有效地減少整個三維模型的碼值數。通過對多個三維模型進行測試，該方法在三角面片鏈碼算法的基礎上進一步提高了三維模型壓縮效率，表現效果較好。

1 三維模型規(guī)格化表示

1.1 MC規(guī)格化算法

三維模型表面多用三角網格來表示。其僅包含點、邊、面3種基本信息，因此具有良好的拓撲結構。在三維模型不同精度的區(qū)域，均可使用大小不同的三角網格表示。如在較為平坦的模型表面，可使用相對較大的三角面片表示，而對于變化復雜的模型表面，可使用多個小三角面片表示。這樣的表示方式能夠很好地保留模型的原始模樣，但由于三角面片大小不一，毫無規(guī)律可循，難以進行數據壓縮。因此，對于三維網格模型，需要將其進行基于體素的規(guī)格化切分。

目前，已有很多對三維網格模型規(guī)格化進行研究，并提出了多種規(guī)格化算法[11-13]。其中，MC算法是基于體素的三維模型表面規(guī)格化較為經典算法之一，其主要思想是在單位體素中尋找一個等值面將模型和外界進行分隔，并用這樣的等值面重新表示三維模型表面。圖1為參考文獻[14]中作者Lorensen給出的15種基本等值面。

在MC算法中，等值面是由單位體素中棱長上選擇的點構成，并非由體素頂點構成，此外，面片頂點的選擇是由該條棱長上2個端點的權重決定的，因此其位置是不固定的。由此獲得的三角面片，沒有統(tǒng)一的標準，不適用于三角面片鏈碼算法。

1.2 改進的MC算法

MC算法中體素的單位為1，為了獲得由體素頂點構成的三角面片，將8個單位為1的體素合并成一個單位為2的體素，同時保留8個體素中的所有頂點，如圖2所示。在這樣一個單位為2的體素中，共有27個頂點，將頂點編號為1，3，7，9，19，21，25，27的頂點作為狀態(tài)點，即這8個點有2種狀態(tài)：在模型內部和模型外部，剩下的19個頂點為等值面的構造點。

圖1 文獻[14]中15種基本等值面

圖2 由8個單位為1的體素合并的體素

在MC算法中，等值面的構造點位于體素兩端同時有實點(在模型內部)和虛點(在模型外部)的棱長上，在單位為2的體素中構造等值面，同樣運用這種思想。如圖3所示，頂點19為實點，頂點25為虛點，因此在棱長1925上，選擇22作為等值面的構造點。同樣，頂點20，2，6，18和16也被選擇為等值面的構造點。此外，為了保證規(guī)格化三角面片是由單位體素頂點構成，單個等值面的頂點必須在同一體素內。此時，頂點14是唯一一個被8個單位體素共用的頂點，因此復雜等值面的三角面片可以經過頂點14來構造。在圖3中，新的等值面一共由8個三角面片組成，每個面片均是由單位體素的頂點構成。

圖3 單位為2的體素中構建等值面

圖4給出了原始MC算法和改進MC算法在同一種情況下構造的等值面。與原始MC算法相比，改進MC算法在構造等值面點集的選擇上做了變化，不僅選擇了兩端分別為實點和虛點的棱長上的點，同時也選擇了體素面的中點，以及體素內部中點作為等值面的構造點。改進的MC算法保留了選擇等值面構造點的思想，同時利用單位體素頂點，將等值面中的三角面片限制在單位體素內，每個三角面片都由單位體素的頂點構成，這樣的三角面片與面片鏈碼中的三角面片相同，因此，改進MC算法所生成的規(guī)格化模型可以使用面片鏈碼進行壓縮。同時，改進的MC算法只對原始MC算法中等值面的構造方法做了改動，并不影響原始MC算法生成高質量三維網格模型的特點，因此由改進MC算法對三維網格模型進行規(guī)格化表示，能夠獲得更好的規(guī)格化模型。

圖4 原始MC算法與改進的MC算法構造等值面對比

在改進MC算法中，對每一種等值面類型均進行了重新定義，圖5給出了改進MC算法中15種基本等值面構造方法，與MC算法相同，剩余的所有等值面類型均由這15種基本類型組合而成。

圖5 改進MC算法中15種基本等值面

1.3 改進MC算法規(guī)格化效果

在算法實現過程中，使用文獻[14]的優(yōu)化方法進行編碼，以提高程序的效率。通過對Armadillo，Bunny，Happy Buddha，Panther和Santa模型進行測試，得到的改進規(guī)格化模型如圖6所示。其中，原規(guī)格化方法為文獻[9]的方法。從圖6中可以看出，對于三角面片鏈碼規(guī)格化方法，改進MC算法所獲得的規(guī)格化模型更為平滑，面片更為規(guī)律。在文獻[9]的三角面片鏈碼算法中，三角面片在模型表面的表現是影響壓縮效果的一個重要因素。當模型表面不夠平整，毫無規(guī)律，易出現幾個面片構成的閉環(huán)，形成較短的面片鏈，進而影響模型的壓縮程度。而當模型表面較為平滑時，就可減少短鏈出現的概率。同時，在Meshlab軟件上對三維模型進行檢測，使用改進MC算法獲得的規(guī)格化模型均具有，沒有縫隙、沒有孔洞、沒有相交面片和非流形邊的高質量特點，可見改進MC算法在直觀上具有較好的重建效果。

在三維模型中，一個極為重要的指標是模型重建誤差。本文采用單向Hausdorff距離測量改進MC算法的誤差值。Hausdorff距離是HUTTENLOCHER等[15]在1993年提出的圖像對比算法，即測量2個點集的匹配程度。對于點集的每一個點，Hausdorff距離計算了與點集中最近點的距離，并取最大距離值作為2個點集的誤差值。對于2個不同的點集，Hausdorff距離能夠準確地度量其在空間上的匹配程度，是非常實用的誤差計算方法。由于規(guī)格化模型與原始模型的頂點數量差異過大，因此采用單向Hausdorff距離作為判斷標準。

以Bunny模型為例，表1給出了1萬~10萬不同面片數量級的單向Hausdorff距離。從表中可以看出，對于不同面片數量的規(guī)格化模型，其誤差均在0.100 0以下。同時，文獻[9]中規(guī)格化方法的平均誤差為0.024 2，改進MC算法的平均誤差為0.033 1。在Hausdorff距離評判標準中，臨界值為0.100 0，即重建誤差小于0.100 0時，重建效果可被接受。因此，改進MC算法的模型重建誤差雖然比文獻[9]方法要大一些，但仍然在接受范圍之內，所以同樣有著較好的重建效果。

圖6 改進MC規(guī)格化算法與原規(guī)格化算法效果((a) Armadillo原始模型；(b) Bunny原始模型；(c) Happy原始模型；(d) Panther原始模型；(e) Santa原始模型；(1)~(3)改進MC算法3萬、5萬、10萬面片；(4)~(6)原規(guī)格化方法3萬、5萬、10萬面片)

此外，表1中還給出了體素單位為2的情況下使用原始MC算法得到重建模型的誤差值略高于改進MC算法，但兩者相差并不大。其差異來源于2種算法重建模型的頂點數量不同以及單向Hausdorff距離的計算方式。通過對比圖1和圖5可以看出，改進MC算法提取的等值面數量和頂點數量要多于原始MC算法。在體素單位為2的情況下，原始MC算法將體素作為一個整體進行等值面的提取，而改進MC算法是通過8個單位為1的體素合并為單位為2的體素，雖然操作體素的單位為2，但等值面的構建是在單位為1的體素中完成，因此改進MC算法重構的模型有更多的頂點。Hausdorff距離是計算2個點集之間最近點的最大距離，當重建模型的頂點數量更多時，最近點的距離也會相對減小。因此原始MC算法的誤差值會略大于改進MC算法。

表1 改進MC算法、原始MC算法和文獻[9]方法單向Hausdorff距離

通過圖7可以發(fā)現，Bunny模型中的重建誤差值，隨著面片數量的增多逐步減小?？梢灶A見，當模型達到一定精細程度時，由于面片數量足夠多，以至于可以忽略模型重建的誤差。但是，這種現象并不適用于所有模型，比如圖8中Santa模型的誤差數據，雖然其誤差也是隨著面片數量的增多而逐步減小，但效果卻并不明顯。

圖7 Bunny模型單向Hausdorff距離趨勢

圖8 Santa模型單向Hausdorff距離趨勢

2 有向三角面片鏈碼表示三維模型

2.1 有向三角面片鏈碼主要思想

在文獻[9]的三角面片鏈碼算法中，為了能夠完整表示三維網格模型，采用了雙向分層的遍歷方法。首先在三維空間坐標系中選取一個坐標軸方向，對整個模型進行分層遍歷，再選取另外一個坐標軸方向，進行分層遍歷。這種遍歷方式能夠規(guī)則地構造面片鏈，并有效控制其數量，但存在部分相同的三角面片會同時被2個方向的分層遍歷的問題，由此造成數據冗余，而且隨著模型規(guī)模的增長，重復遍歷的面片數量會隨之增多，使得采用該算法壓縮的文件會顯著增高。因此，在新的面片鏈碼算法中，如何減少三角面片遍歷數量是算法改進的主要思路。

三角面片包含3條邊和3個頂點。在三維網格模型中，1條邊僅被2個三角面片共用，這個特性保證了三角面片之間連接的唯一性。假設一個三角面片與上一個面片連接的邊為入邊，與下一個連接的邊為出邊，與入邊或出邊連接的，必定有且僅有一個三角面片。該特點適用于規(guī)格化模型中的所有三角面片，從一個三角面片開始，確定其入邊后，選取該面片另外2條邊中的任意一條作為出邊，便能使用面片鏈碼算法中的定義將2個面片連接在一起。分層遍歷是為了將面片遍歷維持在同一層，且從遍歷開始到結束都有著固定的方向，其束縛了面片遍歷的選擇性。因此，在新的面片遍歷方法中，要舍棄雙向分層遍歷的思想，保證每個面片只遍歷一次，消除三維網格模型數據壓縮時的數據冗余。

若是在無約束的情況下，隨機遍歷三角面片，將會造成不可控的結果。最好的結果是所有面片在一條面片鏈上，最壞的結果是面片鏈成環(huán)狀，包圍著一個三角面片，被包圍的一個三角面片需要單獨成鏈。這種對面片鏈的長度無法預知的情況是不理想的。因此，在遍歷三角面片時需要給定一個遍歷方向，讓面片遍歷變的可控，即有向三角面片鏈碼。如圖9所示，遍歷三角面片，設1是第一個面片，任意選取12作為入邊，則13和23中的任意一條邊可被選擇為1的出邊。設頂點1為面片1的第一頂點，2和3分別為第二、第三頂點，根據面片頂點的相對位置，1的右出邊為23，左出邊為13。在遍歷1時，優(yōu)先選擇與23相連接的三角面片作為下一個遍歷面片，即優(yōu)先選擇右連接面片，若與23連接的三角面片已經被遍歷，則選擇與13連接的三角面片，若其同樣被遍歷，則1為當前面片鏈的最后一個面片。

圖9 有向三角面片鏈碼算法

在遍歷每一個三角面片時均選擇優(yōu)先遍歷右連接面片原則，三角面片鏈的遍歷路徑為螺旋狀向外延伸。圖10為有向三角面片鏈碼遍歷路徑。

圖10 有向三角面片鏈碼遍歷路徑

有向三角面片鏈碼遍歷三角面片有2個優(yōu)點：①按照螺旋狀向外延伸的遍歷路徑，可以緊密的遍歷三角面片，在已遍歷的區(qū)域不會出現被面片鏈包圍的面片，減少了單個面片或少數面片成鏈，即短鏈出現的概率；②與分層遍歷相比，分層遍歷僅能遍歷屬于當前層的三角面片，而有向三角面片鏈碼在遍歷時沒有該限制，只要有連接的面片，便可以一直遍歷下去，因此有向三角面片鏈碼構造的面片鏈的平均長度要比分層遍歷的平均長度更長。同時有向三角面片鏈碼對每個三角面片只遍歷一次，降低了大量的數據冗余。

2.2 有向三角面片鏈碼算法

有向三角面片鏈碼算法是新的面片遍歷方法，因此沿用三角面片鏈碼算法中的數據結構定義，同時也沿用了對原始三維網格模型的預處理過程，詳細過程參考文獻[9]。有向三角面片鏈碼算法流程具體如下：

輸入：規(guī)格化三維網格模型面片數據。

輸出：有向三角面片鏈碼算法編碼。

步驟1.模型首個面片讀取與編碼。

步驟1.1.隨機選取一個遍歷標志位為0(未遍歷)的三角面片1，將其遍歷標志置為1，按默認順序將該面片的3個頂點記為1_1，1_2，1_3。

步驟1.2.計算1_2到1_1的相對位置，在連接邊定義表中查找或-，確定1的連接邊類型1_i。若查到，則將1_1，1_2互換。

步驟1.3.計算1_3到1_1的相對位置，在1_i下三角面片定義表中查找，確定1的面片編碼。

步驟2. 構建一條有向三角面片鏈碼編碼。

步驟2.1.在未遍歷面片中尋找與1_21_3連接的三角面片。若找到，執(zhí)行步驟2.2，否則，執(zhí)行步驟2.3。

步驟2.2.將連接面片記為2，將2中與1_3相等的點記為2_1，與1_2相等的點記為2_2，第3點記為2_3，并將1數據結構中連接邊標識位置0。執(zhí)行步驟2.5。

步驟2.3.在所有未遍歷面片中尋找與1_11_3連接的三角面片。若找到，執(zhí)行步驟2.4，否則，執(zhí)行步驟2.9。

步驟2.4. 記連接面片為2，將2中與1_1相等的點記為2_1，與1_3相等的點記為2_2，第3點記為2_3，并將1數據結構中連接邊標識位置1。

步驟2.5.將2的遍歷標志位置1。

步驟2.6.計算2_2到2_1的相對位置，在連接邊定義表中查找或，確定2的連接邊類型2若查到，則將2_1，2_2互換。

步驟2.7.計算2_3到2_1的相對位置，在e下三角面片定義表中查找，確定2數據結構中的面片編碼。

步驟2.8.將2記為1，重復步驟2.1至步驟2.7。

步驟2.9. 將1數據結構中連接邊標識位置0，完成一條有向三角面片鏈碼編碼的構建。

步驟3. 重復步驟1至步驟2，直至遍歷三維模型所有面片，構建整個模型的有向三角面片鏈碼編碼。

2.3 實驗與分析

根據上述算法，選取三維模型Armadillo，Bunny，Satan，Panther和Happy Buddha為例，分別統(tǒng)計了各模型1~5萬面片的具體規(guī)格化面片數量，以及分別使用三角面片鏈碼算法和有向面片鏈碼算法的具體情況，包括模型壓縮后的存儲空間和壓縮率，見表2。需要注意的是，表2中三角面片鏈碼算法的面片個數是去除掉重復面片后的計數。此外，壓縮率的計算是由規(guī)格化后與壓縮后的模型文件計算得出，這是因為規(guī)格化模型的面片數量和頂點數量與原始模型不同。

從表2中可以看出，當面片數為1萬時，除了Armadillo模型，其他模型的三角面片鏈碼算法壓縮效果要比有向三角面片鏈碼算法效果好。對于5個模型，1萬面片的三角面片鏈碼算法平均壓縮率為98.11%，而有向三角面片鏈碼算法的平均壓縮率為97.11%。隨著面片數量的增多，有向面片鏈碼算法的壓縮率要普遍高于三角面片鏈碼算法。對于2~5萬面片的模型，三角面片鏈碼算法的平均壓縮率分別為97.07%，95.90%，94.44%和93.19%，有向面片鏈碼算法的平均壓縮率分別為97.26%，97.33%，97.38%和97.41%。可以看出，三角面片鏈碼算法的壓縮率會隨著面片數量的增加而降低，而有向面片鏈碼算法能夠維持在一個較高水平的壓縮效果。因此當模型的精細程度較高時，有向三角面片鏈碼算法要比三角面片鏈碼算法有著絕對的優(yōu)勢。

表2 三角面片鏈碼算法(文獻[9]算法)和有向三角面片鏈碼算法(本文算法)壓縮效果

此外，通過對比同一個模型不同面片數量的壓縮率能夠發(fā)現，有向三角面片鏈碼算法的壓縮率隨著面片數量的增多，不僅能夠維持在較高的水平，并且還能以微小的差距逐步提高。例如Bunny模型，1~5萬面片的壓縮率分別為97.14%，97.32%，97.42%，97.43%和97.44%，5萬面片壓縮率比1萬面片高出0.30%。圖12顯示了5個模型的有向面片鏈碼算法壓縮率，從圖中可以看出，5個模型的壓縮率與面片數量均為正比關系。其中5萬面片壓縮率比1萬面片分別高出0.28%，0.30%，0.25%，0.17%和0.40%。圖11顯示了三角面片鏈碼算法，其壓縮率與面片數量均為反比關系，且壓縮率的下降幅度較大，5個模型5萬面片壓縮率比1萬面片分別低0.53%，6.94%，5.41%，6.91%和4.81%。相比之下，對于規(guī)格化面片數量越多的模型，有向面片鏈碼算法能夠有更好的壓縮效果。

圖11 三角面片鏈碼壓縮率趨勢

圖12 有向三角面片壓縮率趨勢

3 結束語

本文首先提出了改進MC規(guī)格化算法，通過重新定義MC算法中的體素大小，以及重新構建等值面，獲得可適用于三角面片鏈碼算法，高質量的規(guī)格化三角網格模型。并在此基礎上，提出三角面片鏈碼算法的改進方法，有向三角面片鏈碼算法。通過控制三角面片的遍歷方向，采用優(yōu)先遍歷右連接面片原則，實現三維網格模型數據壓縮效率的提高。通過對多個模型實驗，證明本文算法具有更好的模型數據壓縮效果。但如何將三維模型的如法向量、顏色、材質和紋理信息等信息加入到有向三維面片鏈碼方法中，實現多方位的模型壓縮是今后的一個研究方向；另如何提高算法運行效率，也是需要優(yōu)化的問題之一。

[1] FREEMAN H. Computer processing of line-drawing images[J]. ACM Computing Surveys, 1974, 6(1): 57-97.

[2] BRIBIESCA E. 3D-curve representation by means of a binary chain code[J]. Mathematical and Computer Modelling, 2004, 40(3-4): 285-295.

[3] SáNCHEZ-CRUZ H, LóPEZ-VALDEZ H H, CUEVAS F J. A new relative chain code in 3D[J]. Pattern Recognition, 2014, 47(2): 769-788.

[4] ROSSIGNAC J. Edgebreaker: connectivity compression for triangle meshes[J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(1): 47-61.

[5] ISENBURG M, SNOEYINK J. Spirale Reversi: Reverse decoding of the Edgebreaker encoding[J]. Computational Geometry, 2001, 20(1-2): 39-52.

[6] JONG B S, YANG W H, TSENG J L, et al. An efficient connectivity compression for triangular meshes[C]// Proceedings of Fourth Annual ACIS International Conference on Computer and Information Science (ICIS’05). New York: IEEE Press, 2005: 583-588.

[7] 劉迎, 劉學慧, 吳恩華. 基于模版的三角網格拓撲壓縮[J]. 計算機輔助設計與圖形學學報, 2007, 19(6): 703-707. LIU Y, LIU X H, WU E H. An mode-based connectivity compression for triangular meshes[J]. Journal of Computer-Aided Design & Computer Graphics, 2007, 19(6): 703-707 (in Chinese).

[8] LEMUS E, BRIBIESCA E, GARDU?O E. Representation of enclosing surfaces from simple voxelized objects by means of a chain code[J]. Pattern Recognition, 2014, 47(4): 1721-1730.

[9] 魏巍, 劉勇奎, 段曉東, 等. 三維模型面片鏈碼表示方法[J]. 計算機輔助設計與圖形學學報, 2017, 29(3): 537-548. WEI W, LIU Y K, DUAN X D, et al. Representation method of 3D model mesh chain code[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(3): 537-548 (in Chinese).

[10] LORENSEN W E, CLINE H E. Marching cubes: a high resolution 3D surface construction algorithm[C]//Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1987: 163-169.

[11] ACHANTA R, SHAJI A, SMITH K, et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11): 2274-2282.

[12] FABIJANSKA A, GOCLAWSKI J. The segmentation of 3D images using the random walking technique on a randomly created image adjacency graph[J]. IEEE Transactions on Image Processing, 2015, 24(2): 524-537.

[13] TASLI H E, CIGLA C, ALATAN A A. Convexity constrained efficient superpixel and supervoxel extraction[J]. Signal Processing: Image Communication, 2015, 33: 71-85.

[14] 侯增選, 張定華, 楊海成, 等. 體素模型表面優(yōu)化提取方法及圖形顯示[J]. 機械科學與技術, 2005, 24(3): 361-363,367. HOU Z X, ZHANG D H, YANG H C, et al. A new optimal method for surface extraction of the voxel model and graphic display[J]. Mechanical Science and Technology, 2005, 24(3): 361-363,367 (in Chinese).

[15] HUTTENLOCHER D P, KLANDERMAN G A, RUCKLIDGE W J. Comparing images using the Hausdorff distance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(9): 850-863.

Compression of directed surface chain code in 3D model

LIU Shang-wu1,2, WEI Wei1,2,3, DUAN Xiao-dong1,2, LIU Yong-kui1

(1. School of Computer Science and Engineering, Dalian Minzu University, Dalian Liaoning 116600, China; 2. Dalian Key Laboratory of Digital Technology for National Culture, Dalian Minzu University, Dalian Liaoning 116600, China; 3. School of Information Science and Technology, Dalian Maritime University, Dalian Liaoning 116026, China)

Firstly, an improved MC normalization method was proposed that was applicable to 3D triangular face chain code algorithm. The per unit length in voxel was set as 2 in the improved MC algorithm, and the 27 points in a voxel was employed to rebuild a contoured surface, eventually obtaining the high-quality standardization triangular mesh model. Secondly, with the new normalization model, a new face traverse method was proposed. Based on the 3D triangular face chain code algorithm, the priority traversal right connection face principle was utilized to take control of the direction of face traverse. This method can reduce the number of traverses, and extend the average length of the face chain code. Experimental results show that the new normalization and the new traversal method, compared with the original 3D triangular face chain code, can significantly improve the compression effect.

face chain code; 3D model; voxel; normalization

TP 391

10.11996/JG.j.2095-302X.2021020237

A

2095-302X(2021)02-0237-08

2020-08-09；

9 August，2020；

2020-08-23

23 August，2020

遼寧省教育廳科研項目(LJYT201911)

Scientific Research Project of Liaoning Education Department (LJYT201911)

劉尚武(1994-)，男，河南南陽人，碩士研究生。主要研究方向為計算機圖形學。E-mail：605964270@qq.com

LIU Shang-wu (1994-), male, master student. His main research interest covers computer graphics. E-mail：605964270@qq.com

魏 巍(1980–)，男，河南安陽人，副教授，博士。主要研究方向為計算機圖形學。E-mail：weiwei@dlnu.edu.cn

WEI Wei (1980-), male, associate professor, Ph.D. His main research interest covers computer graphics. E-mail：weiwei@dlnu.edu.cn