基于多級細分的彩色模型表面體素化算法

王 莉，張祥云，周正友

(1.西安交通大學 機械制造系統工程國家重點實驗室，陜西 西安 710049；2.西安增材制造國家研究院有限公司，陜西 西安 710399)

0 引言

近年來，基于體素的三維模型的概念被首次提出，并逐漸引起各領域研究工作者的重視。相較于傳統采用幾何多邊形表達物體幾何信息的三維模型，體素模型是一種采用大量規則體素的有序組合來表示三維物體的模型。體素模型的基本單元體素與二維空間中的像素類似，是數字數據于三維空間分割上的最小單位，可同時包含空間位置、顏色、法向量、材質和透明度等一系列屬性[1]。體素模型是一種全信息建模表達方式，其不僅能表達模型的外表形狀、顏色等信息，還能描述模型內部的材質屬性，因此被廣泛應用于三維成像、醫學影像、檢測碰撞模型，以及體素級多材料3D打印[2-3]和功能梯度材料打印[4,5]等領域。

在增材制造領域，聚合物噴射成型技術(PolyJet)、立體噴墨打印技術(Three-Dimension Printing, 3DP)等工藝均具有體素級成型能力。PolyJet工藝通過噴射裝置將打印材料以微小液滴的形式排布在打印平面的指定位置處，并使用紫外光照射材料圖案使其固化，從而實現體素化3D打印成型。3DP工藝與PolyJet工藝類似，不同的是3DP工藝噴射的是液態粘結劑，將零件截面“印刷”在事先鋪平并壓實的材料粉末上，噴射的液態粘結劑的各項參數通氧可以實現體素級控制。上述體素級增材制造工藝與三維體素模型相互配合可輕易成型任意復雜材質/色彩的打印件，如多材料模型、復雜功能梯度材料、彩色模型打印成型等。

多材料、多色彩模型打印成型的前提是獲取相應的體素模型。在數字模型方面，模型的多材質屬性和多色彩屬性均可通過色彩進行表示和區分，因此本文將彩色模型作為體素化處理的對象。目前，基于幾何多邊形的三維模型體素化是獲取體素模型的一種重要手段。三維模型體素化算法一般包括表面體素化和內部體素化兩部分，本文研究內容主要集中在前者。一種簡單的體素化思想是將模型空間均勻分割為空間體素陣列，通過判斷模型邊界與體素的位置關系標記模型表面體素，從而實現三維模型的表面體素化。一般來說，為得到精確體素模型，通常需要設置較小的體素尺寸。然而在上述操作過程中，隨著預設體素尺寸的減小，體素數量和體素化時間將呈指數級增長；同時較大的幾何多邊形和較小的體素容易導致體素的誤標記，從而出現體素缺失、體素模型表面出現孔洞或破裂等問題。針對上述問題，研究者展開了廣泛的研究，并提出了不同的解決方法。

SZUCKI等[6]在均勻體素模型的基礎上，進一步將特征區域的體素細分為N×N×N個子體素，僅保留子體素中與模型相交的部分，從而得到多分辨率體素模型。BERGS等[7]以邊界表示模型所在空間作為根節點，通過遞歸地將根節點空間分割為8個相等的立方體，檢查并保留與模型相交的子節點，保留下來的子節點體素又將作為下一級分割的父節點，重復上述步驟直至達到預設體素閾值或者遞歸深度，最終得到原始模型的體素化表示。該算法中，邊界表示模型的多邊形尺寸決定了八叉樹分割的體素閾值不能太小，否則可能導致得到的體素模型表面出現孔洞或破裂等缺陷。穆斌等[8]針對當前體素化算法效率低的問題，提出一種“家譜”式的八叉樹節點位置描述方法，大大提高了八叉樹節點檢索效率。此外，通過投影面積判斷體素與模型的位置關系，完成模型的實體體素化，但該算法計算量較大。王鴻亮等[9]提出一種基于“樹型結構和線性結構”雙層次八叉樹模型及其編碼規則，利用樹型結構實現體素位置的快速定位，而線性結構能更準確地表達實體邊界和模型內部空間，兩者的結合較好地平衡時間和空間特性，實現STL模型高效準確體素化。劉晨燕等[10]針對體素模型表面分辨率增加時，體素化時間和體素數量急劇增長的問題，提出基于邊界狀態約束的表面體素細分算法，通過多級加密獲得多分辨率體素模型。該算法提供了一種三維模型的多級實體體素化表示，但在表面體素化方面并不具備明顯優勢。趙芳壘等[11]提出一種基于STL模型的表面體素化算法，通過細分三角面片頂點并建立細分頂點和體素間的關系，基本實現了表面體素化的過程，但該算法過程中產生的體素數量隨體素化分辨率的增加而急劇增加，因此難以滿足較高分辨率的體素化需求。此外，部分研究者嘗試使用圖像處理器(Graphics Processing Unit, GPU)以提高體素化效率，如YOUNG等[12]利用GPU強大的并行計算能力，提出一種基于GPU加速的邊界表示模型的多級體素化算法。在生成邊界表示模型的體素化表示上，該算法比CPU體素化算法快40倍。

綜上所述，多種三維模型表面體素化算法被提出來提升體素模型分辨率和體素化效率、減少體素數量，但均存在缺陷，如：通過“均一體素模型+局部線性細分”算法得到的模型細節加密處過渡不平滑；隨著體素分辨率增加，八叉樹數據結構導致體素數量呈指數級增加；基于硬件加速的體素化算法對硬件依賴性高，通用性不強等。此外，上述算法未考慮模型包圍盒尺寸對體素化精度的影響，且在得到的體素化表示在模型曲率較小處容易出現孔洞或破裂等缺陷。此外，體素模型的材質定義也尚未涉及，而這對于體素級增材制造技術是十分重要的。

針對上述問題，本文提出一種基于八叉樹分割和線性細分的彩色模型表面體素化方法。該方法首先通過均勻細分三角面片獲取模型體素化所需的加密點云數據；然后以三維模型包圍盒空間為根節點建立空間八叉樹數據結構，通過一分為八的方式逐步細分表面體素，并刪除非表面體素，獲得較高分辨率表面體素模型。在此基礎上，通過M×N×K線性加密葉節點體素，將葉節點體素規范至接近立方體的狀態，極大地提升了體素模型的精度。通過色彩插值和一種基于距離影響因子的體素顏色計算方法完成表面體素色彩值的定義。

1 模型數據預處理

1.1 OBJ格式文件

為研究彩色模型表面體素化算法及其在彩色3D打印中的應用，本文選擇OBJ格式模型作為研究對象。相比于增材制造領域的標準輸入文件格式STL，OBJ模型文件同時包含了模型的幾何信息、模型表面顏色信息和模型材質信息，這一特點正好契合于多材料增材制造對于打印材質和顏色分布描述的需求。

OBJ文件本質上是一種文本文件，其通過關鍵字對三維模型的點、線、面等信息進行標記區分和存儲，OBJ文件中主要的數據類型如表1所示。

表1 OBJ三維模型文件格式說明

1.2 算法實現總流程

本文的算法流程如圖1所示，具體實施步驟如下：

步驟1三角面片頂點加密。算法執行之前需要輸入體素閾值Lvt作為三角面片細分依據和體素分割的終止條件。在表面體素分割過程中，為避免部分三角面片過大導致的體素信息缺失、體素模型表面破裂等現象，對模型三角面片網格進行均勻細分加密，以保證生成的表面體素能夠完全封閉。

步驟2表面體素樹型分割。首先以三維模型包圍盒空間為八叉樹根節點，通過一分為八的方式逐步完成模型體素化過程。在八叉樹細分過程中不斷檢測體素與點集的關系，將包含有點集的體素設為非空節點，否則為空節點，并刪除空點。使用八分法均勻分割非空節點體素，并以八叉樹結構進行存儲。每次完成體素細分后，均需檢測子體素與點集的狀態，并刪除空節點。不斷重復上述步驟，直至表面體素最小邊小于預設的體素閾值。

步驟3二次線型加密?？紤]到模型包圍盒形狀對體素形狀和體素模型精度的影響，提出一種體素線性加密方法，即將八叉樹最后一層的體素在空間三方向上同時均勻分割，使得加密后的體素三方向上的尺寸均滿足體素閾值的要求。二次線性細分極大地提高了體素模型的精度，同時也避免了過大的體素數量。

步驟4表面體素顏色計算。本文提出一種基于距離影響因子的體素顏色計算方法。選擇距離某體素最近的4個頂點顏色為該體素的顏色影響點，按照距離越遠影響越小的標準，計算表面體素的顏色，完成體素模型的顏色定義。

1.3 三角面片頂點細分算法

在表面體素過程中，需要判斷體素與模型的關系，只有與模型表面有交集的體素才會被保留下來。體素與模型關系的判定方法一般分為基于三角面片的判定方法和基于頂點的判定方法兩類。前一種方法需要判斷體素與三角形的相交關系，若三角面片集合中存在三角形與體素相交，則將其標記為表面體素，否則為空體素。判斷三角形與體素相交關系的方法往往計算量較大，如分離軸算法[13]中，對于任意一組體素和三角面片，需要判斷二者在13個分離軸方向上的投影是否重疊，計算量十分巨大。后一種通過判斷體素與頂點的位置關系確定體素與模型的關系，相較于前一種方法計算量更少，算法效率更高。因此，本文選擇后一種方法作為表面體素化方法。

用于描述彩色模型外形的三角面片尺寸差異往往會很大，比如在曲率較小的區域三角面片尺寸較小，而在曲率較大的區域三角面片尺寸變得很大。若對原始模型直接進行八叉樹分割，則可能出現如圖2所示的情況，即由于三角面片尺寸過大，導致對應體素內部不包含任何一個頂點，因此體素被判定為空節點，繼而被刪除。該情況下，體素模型精度受到嚴重影響，甚至可能出現模型表面破裂等現象。

為提高體素模型精度、保證體素模型表面能夠完全封閉，有必要對三角面片集進行加密細分，使其能夠滿足正常體素化對三角面片尺寸的需求。針對這一問題，趙芳壘等[11]提出了一種基于體素細分面積閾值的三角面片細分方法。細分面積閾值是指閾值體素的體對角三角形面積，如圖3所示，當模型三角面片面積大于面積閾值時，則需要對三角面片進行分割。

然而該方法細化后的三角面片仍可能導致細分體素的誤刪，如圖3所示，三角形面積大于閾值三角形面積。因此，本文提出了基于最大邊長比的三角面均勻細化算法，通過判斷三角面片最大邊長與閾值體素邊長關系決定是否需要加密，滿足邊長關系的三角面片被均勻細分為多個相似小三角面片，所有小三角面片的并集組成新的頂點數據。單個三角面片加密算法的具體步驟如圖4所示。

具體步驟如下：

步驟1對于給定三角面片，首先計算三角形三邊邊長并選出最大邊長Lmax。比較最大邊長Lmax和預設的閾值體素邊長Lvt，當三角形最大邊長大于閾值體素邊長時則需要對三角形進行加密。三角形邊的分割段數n由式(1)得到：

(1)

式中ceil()為向上取整函數。

步驟2根據步驟1得到的邊長分割段數將三角形三邊均勻分割成n段，使用平行于三角形三邊的線段連接生成的頂點，即可將三角形分割為若干相似小三角形，所有小三角形的頂點集合就是分割后生成的點集。為計算新頂點的坐標，引入兩個向量a、b，a和b的方向為三角形相鄰兩邊的逆時針方向，長度為相應兩邊分割后小線段的長度，如圖5所示。對于分割生成的頂點，本文采用向量平移方式，按照三角形的等分層數快速計算其空間位置，并通過線性插值計算新點的色彩信息。因此，三角形分割后產生的全部頂點坐標可表示為：

{(x,y,z)}=(x1,x2,x3)+a×j+b×k;

0≤j≤n,0≤k≤j。

(2)

步驟3在OBJ三維模型中，三角面片的邊由兩個三角面片共享，三角面片的頂點則由若干個三角面片共享。經過三角形加密細分生成的頂點集合中存在大量重復的點，重復頂點的存在將導致嚴重的數據冗余，影響算法效率，因此有必要對新生成的點集進行檢測，判斷并刪除重復頂點。為此，本文使用C++標準庫容器中的排序算法實現這一目的。經過排序去冗后，得到重采樣后無重復的頂點集合。

對模型所有三角面片均質性上述操作后，即得到數據密度足夠高的點云數據。將其應用于三維模型表面體素化，將極大地提升表面體素化精度，并有效避免了表面體素誤刪、體素模型表面破裂等情況。

2 體素模型生成與表面體素細化

2.1 八叉樹數據結構

八叉樹結構是平面四叉樹在空間上的推廣，是一種描述三維空間的樹狀數據結構，常用于三維模型在空間上的表達和存儲。在八叉樹結構中，所有節點均采取一分為八的方式，如圖7所示，因此每個節點都有8個子節點，這8個子節點表達內容的并集與父節點所表達的內容始終是一致的，即八叉樹每一層上節點和并集與根節點是等價的。此外八叉樹結構中父節點與子節點間的嚴格邏輯關系，使得八叉樹節點的查詢和遍歷效率大大提高。

因此，本文定義空間八叉樹結構節點結構體如下：

typedef struct _OctreeNode

{

ModelColornodeColor;

VectorpointCloudInNode;

double xMin,xMax;

double yMin,yMax;

double zMin,zMax;

struct _OctreeNode * parent;

struct _OctreeNode * child[8];

}OctreeNode;

式中：xMin，xMax，yMin，yMax，zMin，zMax為節點空間的位置信息；parent 為父指針，指向其父節點；child[8]為子指針，指向8個子節點；另外，由于本文研究彩色三維模型的表面體素化，因此增加nodeColor存儲節點空間的顏色信息。

2.2 模型空間分割

八叉樹各層節點合集始終與根節點等價的特性，使得八叉樹能夠很好地描述和分割三維空間，因為無論進行多少層的加密細分，八叉樹的最后一層節點始終能夠表達出初始空間的全部信息。將八叉樹應用于三維模型所在空間的分割細化中，通過不斷分割節點產生子節點，提高體素模型精度，同時也保證了模型信息的完整性。

本文采用八叉樹數據結構分割三維模型并存儲模型信息，如圖6所示，首先將模型的包圍盒空間作為八叉樹結構的根節點，然后模型空間被均勻分割為8個小空間，每個小空間都是八叉樹根節點的子節點。此后，以上一次分割產生的小空間為父節點，將其均勻分割為8個更小的空間，作為該節點的8個子節點。不斷重復細分過程，直到滿足迭代過程的終止條件。本文采用最小體素尺寸作為八叉樹結構分割的終止條件，即當最后一層八叉樹節點體素的最小邊長小于預設的體素閾值時，空間細分停止，基于八叉樹三維模型體素化算法結束。

與完整八叉樹結構不同，為了獲得三維體素模型，需要對節點狀態進行判斷，保留滿足要求的節點，刪除不滿足要求的節點。節點狀態通過節點空間與三維模型點集的關系來判定，本文規定若節點空間內包含至少一個頂點，則表示該節點空間與模型為相交關系，因此將該節點標記為非空節點，否則標記為空節點。如圖7所示，在基于八叉樹結構的空間細分過程中，只有非空節點空間才需要繼續分割，產生子節點，非空節點空間則被刪除。

上述操作結束之后，將得到一棵多層次空間八叉樹，模型的頂點信息全部存儲在八叉樹的非空節點中。提取八叉樹最后一層的全部非空子節點，即得到三維模型對應的體素模型。

2.3 表面體素的線性細分

由于八叉樹均勻分割空間的特性，八叉樹中任意一層節點的對應體素的形狀與模型包圍盒形狀均是相似的。如圖8a所示為八叉樹分割算法結束之后得到的葉節點體素，其長寬高分被設置為l、w、h，其中l>w>h。根據八叉樹分割算法，葉節點體素中只有最短邊滿足算法終止條件，即wLvt，h>Lvt。但由于模型包圍盒的尺寸比例，葉節點體素的另外兩邊尺寸可能遠大于體素閾值，同時由于加密三角面片的三邊長度均小于體素閾值，因此一個葉節點體素內部可能包含多個頂點。這些頂點分布在體素的部分或全部區域，其中沒有頂點分布的區域是體素模型不需要的，這些區域的存在會嚴重影響體素模型的精度。因此，為進一步提高體素模型的精度，有必要繼續細分葉節點體素，使細分后的體素三邊均滿足體素閾值要求。

此時若繼續采用八叉樹結構細分葉節點體素，體素還需八等分的次數可由式(3)～式(5)得出：

(3)

(4)

m=max(log2α,log2β)。

(5)

在圖8中，假設八叉樹葉節點體素三邊l、w、h之比為4∶2∶1，則α=4，β=2，此時計算m=2，因此還需進行兩次八叉樹分割。不考慮細分后刪除空節點的影響，記葉節點體素數量為M，繼續采用八叉樹細分后新的葉節點體素數量為M1，則M1可表示為：

M1=M×8m。

(6)

經過多級八叉樹細分后，M很容易增長到十萬甚至百萬數量級，此時在M的基礎上再進行m次的八叉樹分割，M1將會以M為基數呈指數級增長，這將極大地增加內存負擔，并降低算法效率。另外，經過多次八叉樹分割，葉節點體素在較短邊長上被分割至遠小于體素閾值的長度，因此在該方向上可能出現體素誤刪的情況，造成體素模型精度損失。

針對這一問題，本文在八叉樹結構細分的基礎上提出一種二次線性加密的體素細分算法，該方法在保證體素模型精度的前提下，盡量避免了不必要的體素分割，降低體素數量、提高算法效率。線性加密算法是指，對于經過八叉樹加密后的葉節點體素，僅在其不滿足體素閾值的方向上進行線性均勻細分，使得細分后體素三邊均滿足體素閾值的要求。

類似地，在不考慮空節點體素刪除的影響下，采用線性細分后的體素數量M2可表示為：

M2=M×α×β。

(7)

通過比較式(6)和式(7)可知，M1始終大于M2，并且當l、h與Lvt的比值越大，兩者的差距將會迅速增大。以圖8所示情況為例，計算M1為64M，計算M2為8M，二者相差8倍。因此，二次線性加密方法在保證體素化精度的同時，有效地避免了不必要的體素分割，降低了體素數量。

對線性細分得到的新體素，判斷其是否包含頂點信息，刪除未包含頂點的空節點體素，保留的體素包含了全部頂點信息、并且三邊均滿足體素閾值。完成上述操作后，得到無顏色信息的表面體素模型。

2.4 表面體素顏色計算

在OBJ模型中，模型的顏色信息存儲在三角面片頂點中，而體素模型的顏色信息則以體素為單位進行存儲，并且在RGB顏色模型下，顏色信息可用一個三維向量表示，形如C(R, G, B)。因此，為實現彩色模型的表面體素化，還需完成模型顏色信息從三角面片頂點向體素的轉換。在顏色信息的轉換過程中，考慮到彩色模型表面顏色漸變的特點，可以簡單地認為越靠近體素的頂點顏色對體素顏色的影響越大，因此本文選擇體素包含的全部頂點作為體素顏色計算的參照點，并采用遠小近大的原則計算體素顏色，如圖9所示。

為衡量體素周圍的頂點顏色對體素顏色的影響程度，本文提出一種基于距離的顏色影響因子λ，該影響因子的定義如下：

(8)

則體素的顏色可通過式(9)得到:

(9)

式中:Ci和Cv分別表示四頂點顏色和體素顏色，Si分別表示頂點與體素中心的距離。

3 算法驗證

本文彩色模型表面體素化算法在Visual Studio環境下以C++語言編寫應用軟件，處理器為Intel(R)Core(TM)i5-8400 2.8 GHz，運行內存為8 GB。軟件使用單線運行，以OpenGL編寫的C++程序顯示OBJ模型。本文選擇CAD建模的法蘭盤、校碑、豌豆射手、小黃人共4種彩色OBJ模型為主要實驗對象，如圖10所示，根據關鍵詞完成模型數據的分割并分別存儲在對應的數據容器中，即模型的數據重建，重建模型數據將作為后續體素化算法的初始數據。

3.1 算法效果

彩色模型表面體素化以彩色模型包圍盒為八叉樹根節點，通過不斷細分并保留表面體素，去除非表面體素，逐步還原出模型的表面形狀，如圖11所示。圖12展示了小黃人彩色模型表面體素多級細分過程，隨著表面體素細分程序的執行，模型表面體素尺寸不斷減小，表面模型模型精度不斷提高。在OBJ模型三角面片細分足夠密集的前提下，本文算法理論上可以通過不斷細分表面體素，實現任何級別的表面體素精度。

越高的體素模型精度要求越小的體素分割閾值，因此在不考慮其他影響因素的前提下，可以通過設置更小的體素閾值以實現更高的體素化精度。圖12是校碑模型分別在1.6 mm、0.8 mm、0.4 mm、0.2 mm、0.1 mm和0.05 mm體素閾值下的表面體素化結果，如圖12所示隨著體素閾值設定值的減小，組成相應體素模型的體素尺寸逐漸減小，并且未包含三角頂點的表面體素不斷被剔除，體素化精度不斷提高，體素模型逐漸刻畫出OBJ模型表面形狀特征。

線性細分是在八叉樹體素化表示的基礎上，通過將體素進一步細分至接近立方體的體素類型并刪除未包含點的體素，極大地提高體素模型的精度。圖13為線性細分處理前后的體素模型效果圖及局部細節圖，從圖中可以看出，經過線性細分處理，體素模型精度得到明顯提升。在未經過線性細分之前，校碑體素模型中的體素形狀與校碑包圍盒是一致的，此時由于校碑包圍盒尺寸的影響，體素模型中體素的大部分空間并未占據模型數據點，這導致體素模型細節特征十分模糊，如校碑模型上的文字部分。經過線性細分處理后，體素模型精度明顯提高，校碑模型上的文字清晰度大大提高。

圖14顯示了法蘭盤、校碑、豌豆射手、小黃人等OBJ彩色模型在0.1 mm體素閾值下的表面體素化結果。

值得注意的是，本文算法同樣適用于“蓋面”和“雙面紙”等薄層結構[11]，例如本文算法在處理上述模型中的豌豆射手的葉子結構時獲得了不錯的實驗結果。

3.2 算法數據

為準確評價本文算法的性能，本文以法蘭盤、校碑、豌豆射手、小黃人等4種彩色模型為實驗對象，分別在1.6 mm、0.8 mm、0.4 mm、0.2 mm、0.1 mm體素閾值下，獲得了相應的體素模型和算法詳細數據，主要包括上述模型在不同體素閾值下的八叉樹迭代次數、八叉樹分割后表面體素數量、線性細分后表面體素數量和程序運行時間，具體如表2所示。通過表中數據可以得出以下結論：

表2 各彩色模型表面體素化的參數

(1)對于同一個彩色模型，隨著體素閾值快速減小(負指數級)，八叉樹分割迭代次數的線性增加。

(2)同時，迭代次數的增加伴隨著表面體素模型的體素數量和程序運行時間呈指數級快速增加，如圖15和圖16所示。

以豌豆射手模型為例，該模型體素化閾值從0.4 mm減小到0.2 mm時，經過附加一輪的體素分割細化，體素模型的精度僅提高一倍時，體素化模型的總體素數量增加為之前的3.69倍，程序運行時間增加為3.90倍。不斷的細化迭代固然實現了更高精度的體素模型精度，但勢必造成更大的數據存儲壓力和更低的算法效率。因此，在實際操作時，在模型精度滿足要求的前提下，應盡可能地使用更大的體素閾值，以減小內存壓力、提升算法效率。

(3)線性細分是本文算法提升體素化精度的重要過程，通過算法原理推斷和實驗數據分析均可以得到結論：輸入模型包圍盒長寬高中兩兩之比越是遠離1，即模型越是細扁，體素模型線性細分對體素模型精度的提升越是明顯。同時，模型越是細扁，線性細分之后表面體素數量增加越快。以校碑模型和豌豆射手模型為例，當體素閾值設為0.1 mm時，線性細分導致體素模型表面體素分別增加為103.49倍和5.14倍。因此，對于細扁模型，應同時考慮體素化精度和線性細分導致迅速增加的體素數量，選擇合適的體素化閾值。

可以預知，在體素化精度和算法效率方面，本文提出的算法具有明顯的優勢。相比于文獻[2]等提出的體素化方法，本文算法通過提前細分三角面片的方式，保證在較小體素閾值的情況下，彩色模型仍能夠實現表面體素化，且體素化模型不會出現孔洞、裂縫等缺陷。文獻[11]提出一種分割模型包圍盒空間，通過標記細分采樣點所在體素，以實現三維模型表面體素化。為更好地與本文算法進行對比，在相同的硬件條件下采用不同的體素化閾值，即不同的體素化分辨率，對同一模型進行體素化處理，本文算法與文獻[11]產生的體素數量如表3所示。

表3中，本文算法的累計體素數量是指在多級八叉樹分割和線性分割過程中產生的全部體素數量之和，文獻[11]的總體體素數量是指模型在xyz三軸上等距分割產生的全部體素數量之和，二者均是各自算法中影響算法效率和數據量的重要參數。從表中可以看出，在較小體素化分辨率下，本文算法產生的累計體素數量略大于文獻[11]產生的總體體素數量，但隨著體素化分辨率增加，文獻[11]的總體體素數量迅速超過本文算法的累計體素數量，且體素化分辨率越大，二者差距越大。

表3 本文算法與文獻[11]算法數據比較

本文算法需要多級細分，且每一級細分之后都會生成新的體素表示，下一級體素表示總是上一級的子集，在空間上存在重復表示的情況，而文獻[11]僅進行一次體素化分割，體素之間沒有重復表示，因此在較小體素化分辨率下本文算法產生的累計體素數量會略大于文獻[11]。本文采用八叉樹結構+線性結構的方式逐級分割模型，如圖17所示，每一級分割后，分割產生的新體素中只有與細分頂點有交集的部分才會被保留，被保留的部分將作為這一級分割的體素化表示，同時也自動成為下一級分割的父節點。相比于文獻[11]的一次性分割至指定體素閾值，本文算法避免了各級分割中無用體素的存儲和后續分割，因此算法產生的累計體素數量的增長速度得到有效控制，特別是在體素化分辨率越大的情況下，本文在該點上表現出越明顯的優勢。由表3可以看出，當體素閾值由0.2 mm減小為0.1 mm時，文獻[11]產生的總體體素數量增長至上一級的8倍，而本文算法產生的累計體素數量僅增長至上一級的約4倍左右。

表3中，有效體素數量是指最終的體素化模型所包含的體素數量。理論上，在相同的體素化分辨率下，本文算法和文獻[11]算法得到的體素模型的有效體素數量應該相等，表3中的實驗數據證實了這一點。表3中，模型在體素閾值為1.6 mm和0.8 mm下進行體素化處理，本文算法和文獻[11]算法產生的有效體素數量存在細微差異，這主要是因為在使用本文算法和文獻[11]算法時，通過預設體素閾值計算最終體素模型分辨率，即模型在xyz三軸上的分割段數不一樣導致的，如體素閾值為1.6mm時，本文算法的體素化分辨率是32×16×8，而文獻[11]的體素化分辨率是25×13×7。

4 結束語

本文針對現有三維模型表面體素化過程容易出現表面破裂、體素模型精度低等問題，提出一種彩色模型表面體素化算法，該算法以OBJ彩色模型作為算法研究對象，將八叉樹數據結構應用于模型分割過程。針對OBJ模型部分三角面片過大導致的表面體素模型出現破裂的現象，提出一種基于最大邊長比的三角面片均勻細分算法，保證得到的體素模型能夠完全封閉。針對現有表面體素化模型精度較低的現象，本文提出一種表面體素線性細分算法，大大提高了體素模型的精度。最后，本文使用了多個OBJ模型對上述算法進行了驗證，實驗結果表明，即是設定較小的體素分割閾值，算法仍然能夠保證所得體素模型的全封閉性。

本文算法具有以下意義：

(1)充分利用了模型本身的三角面信息，間接通過三角面的線和面信息，實現三角面的頂點密化，結合八叉樹分割的終止條件，嚴格保證了體素模型的表面封閉性。

(2)結合模型包圍盒的形狀，對八叉樹結構中的體素線性細分分割，使體素的形狀趨向于正方體，細化體素尺寸，極大地提高了體素模型的精度。

(3)本文算法同樣適用于薄層結構的表面體素化，這是基于模型輪廓的體素化算法所不能實現的功能。

(4)在體素級增材制造領域，基于本文算法得到的彩色體素模型，材質分布定義和色彩管理將變得十分容易，如定義復雜的功能梯度材料的分布和彩色模型3D打印過程中的色彩管理。此外，體素模型經過簡單的切片和填充過程，即可得到彩色增材制造所需的切片文件。切片文件將會決定在何處噴射何種成型材料(PolyJet技術)或者何種類型的粘結劑(3DP技術)。

在不考慮三角面片近似造成的原始三維模型精度損失外，本文算法可以通過減小體素閾值得到任意精度的體素化模型，然而這也將導致巨大的體素數量和時間成本。因此，下一步研究主要集中在通過將滿足要求的鄰近體素合并或者在體素分割時不處理無需分割的體素，以實現更高的體素化效率和更小的體素數量。如，此處“滿足要求的鄰近體素”可以定義為空間坐標之一相同并且可以合并為新體素的鄰近體素，“無需分割的體素”則可以是最后一次八叉樹分割后，所得子節點全部被保留的父體素。

另外，本文的體素化算法僅處理模型的表面形狀和色彩信息，然而在聚合物噴射成型工藝的眾多應用場景中，存在模型表面體素化+內部體素化的需求，即模型實體體素化，如復雜功能梯度材料模型、半透明彩色模型3D打印應用中，模型內部的材質或顏色定義是不可或缺的。因此，如何高效準確地實現三維模型實體體素化也是下一步的研究方向之一。