劉尚武　魏巍　矯宇鵬

摘要：通過對(duì)三維模型原始三角面片的規(guī)格化，對(duì)原模型內(nèi)的三角面片進(jìn)行基于體素的劃分和表示。將規(guī)格化后的三角面片進(jìn)行基于連接邊的分類，并對(duì)每一連接邊類型對(duì)應(yīng)的三角面片的位置進(jìn)行編碼。通過找尋規(guī)格化后的三角面片之間的表示特點(diǎn)，探索具有規(guī)律性的存儲(chǔ)方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效的降低三維模型的存儲(chǔ)空間，提高存儲(chǔ)效率。

關(guān)鍵詞：體素；規(guī)格化；連接邊；三角面片

中圖分類號(hào)：000000 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2016.04.008

0 引言

近年來，計(jì)算機(jī)三維模型的表示與存儲(chǔ)方法成為計(jì)算機(jī)模型構(gòu)建領(lǐng)域的研究熱點(diǎn)。目前，三維模型的表示大多采用三角面片法，這種方法有很多優(yōu)點(diǎn)：面、邊、點(diǎn)及其拓?fù)潢P(guān)系完備，有利于生成和繪制線框圖、投影圖，有利于計(jì)算幾何特性，易于同繪圖軟件銜接和關(guān)聯(lián)等。但是，由于三角面片的大小與形狀各異，毫無規(guī)律，使得數(shù)據(jù)的保存比較復(fù)雜。本文在三角面片表示的基礎(chǔ)上，對(duì)面片進(jìn)行規(guī)格化，重新對(duì)三維模型進(jìn)行基于體素的表示，使模型的三角面片成為類型已知和大小可控的面片。通過對(duì)模型進(jìn)行分層處理，探索規(guī)格化后三角面片之間的聯(lián)系，從而達(dá)到壓縮模型存儲(chǔ)空間的目的。用本文的方式存儲(chǔ)三維模型，可以極大的壓縮模型數(shù)據(jù)，節(jié)省空間。

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

1.1 三維模型的表示和提取

用SolidWorks軟件對(duì)模型文件進(jìn)行處理，生成對(duì)應(yīng)的VRML文件（.wr1）。提取文件內(nèi)各三角面片的點(diǎn)信息和面片索引信息，獲得三角面片的點(diǎn)表與面表。這類三維模型的表達(dá)方式是常用由大小形狀各異的三角面片組成，為本文所描述的原始模型。

1.2 體素的表示

由于原始模型中三角面片毫無規(guī)律可循，為了解決這個(gè)問題，提出體素的概念。將三維空間用平行于坐標(biāo)面的平面劃分成小方格（即體素），這樣在每個(gè)體素內(nèi)由8個(gè)頂點(diǎn)中的任意3個(gè)頂點(diǎn)可組成一個(gè)三角面片。這樣的三角面片數(shù)量和位置是固定的，所以對(duì)每個(gè)三角面片用一個(gè)數(shù)字來表示。在表示三維物體模型時(shí)，在物體的邊界體素上從上述三角面片中找一個(gè)與物體表面最接近的三角面片來表示物體。將這些三角面片連接起來就可表示整個(gè)三維物體。如此獲得的三維模型全部是用已知的三角面片構(gòu)成，整理和應(yīng)用起來都更加方便、有序。

1.3 規(guī)格化

把原始模型中未知的三角面片轉(zhuǎn)換成基于體素的已知的三角面片，稱為規(guī)格化。其方法是，先對(duì)原始模型分層，再確定點(diǎn)面信息。

分層的過程，對(duì)原始模型的三角面片按垂直于某一坐標(biāo)軸的切面進(jìn)行切割，獲得當(dāng)前切面與模型三角面片的交點(diǎn)對(duì)。觀察點(diǎn)對(duì)不難發(fā)現(xiàn)，對(duì)于任意一個(gè)點(diǎn)對(duì)，必有另外兩個(gè)點(diǎn)對(duì)與其擁有公共點(diǎn)。照此關(guān)系鏈接所有點(diǎn)對(duì)，可得到當(dāng)前層的輪廓線。按照此方法，對(duì)原始模型進(jìn)行分割，生成各層輪廓線。

得到各層輪廓線之后，將組成相鄰兩層輪廓線上的點(diǎn)進(jìn)行三角剖分。利用插點(diǎn)的方法將輪廓線上的三點(diǎn)組成一個(gè)新的小三角形，保證三角形都是單位大小且沒有任何輪廓線上的點(diǎn)剩余，在滿足上述兩個(gè)條件基礎(chǔ)上使輪廓線形狀改變盡可能小。如圖1所示。

最終得到的三維模型是一個(gè)基于體素的分層次規(guī)格化后的三角面片構(gòu)成的模型。以三維模型Bunny為例，規(guī)劃化后的模型表示如圖2所示。

1.4 規(guī)格化優(yōu)點(diǎn)

由于體素的規(guī)格是可控的，所以基于體素的三角面片的大小也是可以調(diào)整的。對(duì)于三維模型中難以構(gòu)建的細(xì)節(jié)問題，可以把體素的規(guī)格設(shè)置到足夠小，用細(xì)化后的三角面片來表示更為合適。而對(duì)于三維模型中簡(jiǎn)單的平面等，可以根據(jù)需要來設(shè)置體素的規(guī)格。圖3給出了用三種不同規(guī)格的倒示的同一個(gè)模型。

2 壓縮算法流程

2.1 面片分類

上述體素中，共有56種三角面片，可對(duì)這些三角面片進(jìn)行分類編號(hào)。體素中，每?jī)牲c(diǎn)連接都能成為某個(gè)三角面片的一條邊，稱為連接邊。經(jīng)分析，共有13種連接邊。每種連接邊和體素中其它任意一點(diǎn)連接都能構(gòu)成一個(gè)三角面片。把所有三角面片進(jìn)行歸類整理，可總結(jié)出每種連接邊下所有的三角面片種類及個(gè)數(shù)，其中不同連接邊對(duì)應(yīng)的三角面片可重復(fù)。

2.2 遍歷模型

對(duì)規(guī)格化后的三維模型，用基于體素的三角面片對(duì)其進(jìn)行分層遍歷。由于體素中的三角面片包含多個(gè)層次。在遍歷時(shí)，模型每層中按一個(gè)方向順序遍歷，不能遍歷完整的三維模型。為此，遍歷三維模型需要沿兩個(gè)方向分層遍歷。首先，沿x軸對(duì)模型進(jìn)行分層遍歷，再沿y軸對(duì)模型進(jìn)行分層遍歷。這樣，能夠?qū)崿F(xiàn)對(duì)三維模型的遍歷。

2.3 數(shù)據(jù)壓縮

在上述面片分類中，共分為13種連接邊。對(duì)連接邊進(jìn)行編號(hào)，并且對(duì)連接邊對(duì)應(yīng)的三角面片進(jìn)行編號(hào)。這樣每個(gè)三角面片，都可以用連接邊編號(hào)和面片編號(hào)來表示。由于規(guī)格化后的三維模型是分層遍歷，每層的三角面片可看作一個(gè)三角面片鏈。由此得到模型的各層編碼鏈。

對(duì)每一連接邊對(duì)應(yīng)的三角面片分別編號(hào)，最多需要4位二進(jìn)制數(shù)?？梢?，加上連接邊編號(hào)的一位二進(jìn)制數(shù)，表示一個(gè)三角面片總共只需5位二進(jìn)制數(shù)。對(duì)于規(guī)格化后的三維模型，所有面片都可以用5位二進(jìn)制數(shù)表示。這極大壓縮了原始模型的數(shù)據(jù)。對(duì)三維模型Bunny進(jìn)行了實(shí)驗(yàn)，具體壓縮效果如表1所示。

3 結(jié)語

三維模型應(yīng)用廣泛，其表示方法和數(shù)據(jù)存儲(chǔ)對(duì)模型的應(yīng)用有著重要的意義。本文提出一種基于體素的規(guī)格化三維模型三角面片表示方法。將規(guī)格化后的三角面片按層次遍歷，可獲得用固定比特位表示三角面片的鏈?zhǔn)酱鎯?chǔ)方式。由于定義的規(guī)格化三角面片的數(shù)據(jù)結(jié)構(gòu)占用存儲(chǔ)空間較小，因此可以有效的降低三維模型的存儲(chǔ)空間。