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

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

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

(1. 大連民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧 大連 116600； 2.大連民族大學(xué)大連市民族文化數(shù)字技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116600； 3. 大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026)

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

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

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

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

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

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

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

1.1 MC規(guī)格化算法

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

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

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

1.2 改進(jìn)的MC算法

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

圖1 文獻(xiàn)[14]中15種基本等值面

圖2 由8個(gè)單位為1的體素合并的體素

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

圖3 單位為2的體素中構(gòu)建等值面

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

圖4 原始MC算法與改進(jìn)的MC算法構(gòu)造等值面對(duì)比

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

圖5 改進(jìn)MC算法中15種基本等值面

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

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

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

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

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

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

表1 改進(jìn)MC算法、原始MC算法和文獻(xiàn)[9]方法單向Hausdorff距離

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

圖7 Bunny模型單向Hausdorff距離趨勢(shì)

圖8 Santa模型單向Hausdorff距離趨勢(shì)

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

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

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

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

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

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

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

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

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

2.2 有向三角面片鏈碼算法

有向三角面片鏈碼算法是新的面片遍歷方法，因此沿用三角面片鏈碼算法中的數(shù)據(jù)結(jié)構(gòu)定義，同時(shí)也沿用了對(duì)原始三維網(wǎng)格模型的預(yù)處理過程，詳細(xì)過程參考文獻(xiàn)[9]。有向三角面片鏈碼算法流程具體如下：

輸入：規(guī)格化三維網(wǎng)格模型面片數(shù)據(jù)。

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

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

步驟1.1.隨機(jī)選取一個(gè)遍歷標(biāo)志位為0(未遍歷)的三角面片1，將其遍歷標(biāo)志置為1，按默認(rèn)順序?qū)⒃撁嫫?個(gè)頂點(diǎn)記為1_1，1_2，1_3。

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

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

步驟2. 構(gòu)建一條有向三角面片鏈碼編碼。

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

步驟2.2.將連接面片記為2，將2中與1_3相等的點(diǎn)記為2_1，與1_2相等的點(diǎn)記為2_2，第3點(diǎn)記為2_3，并將1數(shù)據(jù)結(jié)構(gòu)中連接邊標(biāo)識(shí)位置0。執(zhí)行步驟2.5。

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

步驟2.4. 記連接面片為2，將2中與1_1相等的點(diǎn)記為2_1，與1_3相等的點(diǎn)記為2_2，第3點(diǎn)記為2_3，并將1數(shù)據(jù)結(jié)構(gòu)中連接邊標(biāo)識(shí)位置1。

步驟2.5.將2的遍歷標(biāo)志位置1。

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

步驟2.7.計(jì)算2_3到2_1的相對(duì)位置，在e下三角面片定義表中查找，確定2數(shù)據(jù)結(jié)構(gòu)中的面片編碼。

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

步驟2.9. 將1數(shù)據(jù)結(jié)構(gòu)中連接邊標(biāo)識(shí)位置0，完成一條有向三角面片鏈碼編碼的構(gòu)建。

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

2.3 實(shí)驗(yàn)與分析

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

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

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

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

圖11 三角面片鏈碼壓縮率趨勢(shì)

圖12 有向三角面片壓縮率趨勢(shì)

3 結(jié)束語

本文首先提出了改進(jìn)MC規(guī)格化算法，通過重新定義MC算法中的體素大小，以及重新構(gòu)建等值面，獲得可適用于三角面片鏈碼算法，高質(zhì)量的規(guī)格化三角網(wǎng)格模型。并在此基礎(chǔ)上，提出三角面片鏈碼算法的改進(jìn)方法，有向三角面片鏈碼算法。通過控制三角面片的遍歷方向，采用優(yōu)先遍歷右連接面片原則，實(shí)現(xiàn)三維網(wǎng)格模型數(shù)據(jù)壓縮效率的提高。通過對(duì)多個(gè)模型實(shí)驗(yàn)，證明本文算法具有更好的模型數(shù)據(jù)壓縮效果。但如何將三維模型的如法向量、顏色、材質(zhì)和紋理信息等信息加入到有向三維面片鏈碼方法中，實(shí)現(xiàn)多方位的模型壓縮是今后的一個(gè)研究方向；另如何提高算法運(yùn)行效率，也是需要優(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] 劉迎, 劉學(xué)慧, 吳恩華. 基于模版的三角網(wǎng)格拓?fù)鋲嚎s[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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]. 機(jī)械科學(xué)與技術(shù), 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

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

Scientific Research Project of Liaoning Education Department (LJYT201911)

劉尚武(1994-)，男，河南南陽人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。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–)，男，河南安陽人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。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