劉尚武　魏巍　矯宇鵬

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

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

中圖分類號：000000 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2016.04.008

0 引言

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

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

1.1 三維模型的表示和提取

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

1.2 體素的表示

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

1.3 規(guī)格化

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

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

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

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

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

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

2 壓縮算法流程

2.1 面片分類

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

2.2 遍歷模型

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

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

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

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

3 結(jié)語

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