王 莉，張祥云，周正友

(1.西安交通大學(xué) 機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710049；2.西安增材制造國(guó)家研究院有限公司，陜西 西安 710399)

0 引言

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

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

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

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

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

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

1 模型數(shù)據(jù)預(yù)處理

1.1 OBJ格式文件

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

OBJ文件本質(zhì)上是一種文本文件，其通過(guò)關(guān)鍵字對(duì)三維模型的點(diǎn)、線、面等信息進(jìn)行標(biāo)記區(qū)分和存儲(chǔ)，OBJ文件中主要的數(shù)據(jù)類型如表1所示。

表1 OBJ三維模型文件格式說(shuō)明

1.2 算法實(shí)現(xiàn)總流程

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

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

步驟2表面體素樹型分割。首先以三維模型包圍盒空間為八叉樹根節(jié)點(diǎn)，通過(guò)一分為八的方式逐步完成模型體素化過(guò)程。在八叉樹細(xì)分過(guò)程中不斷檢測(cè)體素與點(diǎn)集的關(guān)系，將包含有點(diǎn)集的體素設(shè)為非空節(jié)點(diǎn)，否則為空節(jié)點(diǎn)，并刪除空點(diǎn)。使用八分法均勻分割非空節(jié)點(diǎn)體素，并以八叉樹結(jié)構(gòu)進(jìn)行存儲(chǔ)。每次完成體素細(xì)分后，均需檢測(cè)子體素與點(diǎn)集的狀態(tài)，并刪除空節(jié)點(diǎn)。不斷重復(fù)上述步驟，直至表面體素最小邊小于預(yù)設(shè)的體素閾值。

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

步驟4表面體素顏色計(jì)算。本文提出一種基于距離影響因子的體素顏色計(jì)算方法。選擇距離某體素最近的4個(gè)頂點(diǎn)顏色為該體素的顏色影響點(diǎn)，按照距離越遠(yuǎn)影響越小的標(biāo)準(zhǔn)，計(jì)算表面體素的顏色，完成體素模型的顏色定義。

1.3 三角面片頂點(diǎn)細(xì)分算法

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

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

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

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

具體步驟如下：

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

(1)

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

步驟2根據(jù)步驟1得到的邊長(zhǎng)分割段數(shù)將三角形三邊均勻分割成n段，使用平行于三角形三邊的線段連接生成的頂點(diǎn)，即可將三角形分割為若干相似小三角形，所有小三角形的頂點(diǎn)集合就是分割后生成的點(diǎn)集。為計(jì)算新頂點(diǎn)的坐標(biāo)，引入兩個(gè)向量a、b，a和b的方向?yàn)槿切蜗噜弮蛇叺哪鏁r(shí)針方向，長(zhǎng)度為相應(yīng)兩邊分割后小線段的長(zhǎng)度，如圖5所示。對(duì)于分割生成的頂點(diǎn)，本文采用向量平移方式，按照三角形的等分層數(shù)快速計(jì)算其空間位置，并通過(guò)線性插值計(jì)算新點(diǎn)的色彩信息。因此，三角形分割后產(chǎn)生的全部頂點(diǎn)坐標(biāo)可表示為：

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

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

(2)

步驟3在OBJ三維模型中，三角面片的邊由兩個(gè)三角面片共享，三角面片的頂點(diǎn)則由若干個(gè)三角面片共享。經(jīng)過(guò)三角形加密細(xì)分生成的頂點(diǎn)集合中存在大量重復(fù)的點(diǎn)，重復(fù)頂點(diǎn)的存在將導(dǎo)致嚴(yán)重的數(shù)據(jù)冗余，影響算法效率，因此有必要對(duì)新生成的點(diǎn)集進(jìn)行檢測(cè)，判斷并刪除重復(fù)頂點(diǎn)。為此，本文使用C++標(biāo)準(zhǔn)庫(kù)容器中的排序算法實(shí)現(xiàn)這一目的。經(jīng)過(guò)排序去冗后，得到重采樣后無(wú)重復(fù)的頂點(diǎn)集合。

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

2 體素模型生成與表面體素細(xì)化

2.1 八叉樹數(shù)據(jù)結(jié)構(gòu)

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

因此，本文定義空間八叉樹結(jié)構(gòu)節(jié)點(diǎn)結(jié)構(gòu)體如下：

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為節(jié)點(diǎn)空間的位置信息；parent 為父指針，指向其父節(jié)點(diǎn)；child[8]為子指針，指向8個(gè)子節(jié)點(diǎn)；另外，由于本文研究彩色三維模型的表面體素化，因此增加nodeColor存儲(chǔ)節(jié)點(diǎn)空間的顏色信息。

2.2 模型空間分割

八叉樹各層節(jié)點(diǎn)合集始終與根節(jié)點(diǎn)等價(jià)的特性，使得八叉樹能夠很好地描述和分割三維空間，因?yàn)闊o(wú)論進(jìn)行多少層的加密細(xì)分，八叉樹的最后一層節(jié)點(diǎn)始終能夠表達(dá)出初始空間的全部信息。將八叉樹應(yīng)用于三維模型所在空間的分割細(xì)化中，通過(guò)不斷分割節(jié)點(diǎn)產(chǎn)生子節(jié)點(diǎn)，提高體素模型精度，同時(shí)也保證了模型信息的完整性。

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

與完整八叉樹結(jié)構(gòu)不同，為了獲得三維體素模型，需要對(duì)節(jié)點(diǎn)狀態(tài)進(jìn)行判斷，保留滿足要求的節(jié)點(diǎn)，刪除不滿足要求的節(jié)點(diǎn)。節(jié)點(diǎn)狀態(tài)通過(guò)節(jié)點(diǎn)空間與三維模型點(diǎn)集的關(guān)系來(lái)判定，本文規(guī)定若節(jié)點(diǎn)空間內(nèi)包含至少一個(gè)頂點(diǎn)，則表示該節(jié)點(diǎn)空間與模型為相交關(guān)系，因此將該節(jié)點(diǎn)標(biāo)記為非空節(jié)點(diǎn)，否則標(biāo)記為空節(jié)點(diǎn)。如圖7所示，在基于八叉樹結(jié)構(gòu)的空間細(xì)分過(guò)程中，只有非空節(jié)點(diǎn)空間才需要繼續(xù)分割，產(chǎn)生子節(jié)點(diǎn)，非空節(jié)點(diǎn)空間則被刪除。

上述操作結(jié)束之后，將得到一棵多層次空間八叉樹，模型的頂點(diǎn)信息全部存儲(chǔ)在八叉樹的非空節(jié)點(diǎn)中。提取八叉樹最后一層的全部非空子節(jié)點(diǎn)，即得到三維模型對(duì)應(yīng)的體素模型。

2.3 表面體素的線性細(xì)分

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

此時(shí)若繼續(xù)采用八叉樹結(jié)構(gòu)細(xì)分葉節(jié)點(diǎn)體素，體素還需八等分的次數(shù)可由式(3)～式(5)得出：

(3)

(4)

m=max(log2α,log2β)。

(5)

在圖8中，假設(shè)八叉樹葉節(jié)點(diǎn)體素三邊l、w、h之比為4∶2∶1，則α=4，β=2，此時(shí)計(jì)算m=2，因此還需進(jìn)行兩次八叉樹分割。不考慮細(xì)分后刪除空節(jié)點(diǎn)的影響，記葉節(jié)點(diǎn)體素?cái)?shù)量為M，繼續(xù)采用八叉樹細(xì)分后新的葉節(jié)點(diǎn)體素?cái)?shù)量為M1，則M1可表示為：

M1=M×8m。

(6)

經(jīng)過(guò)多級(jí)八叉樹細(xì)分后，M很容易增長(zhǎng)到十萬(wàn)甚至百萬(wàn)數(shù)量級(jí)，此時(shí)在M的基礎(chǔ)上再進(jìn)行m次的八叉樹分割，M1將會(huì)以M為基數(shù)呈指數(shù)級(jí)增長(zhǎng)，這將極大地增加內(nèi)存負(fù)擔(dān)，并降低算法效率。另外，經(jīng)過(guò)多次八叉樹分割，葉節(jié)點(diǎn)體素在較短邊長(zhǎng)上被分割至遠(yuǎn)小于體素閾值的長(zhǎng)度，因此在該方向上可能出現(xiàn)體素誤刪的情況，造成體素模型精度損失。

針對(duì)這一問(wèn)題，本文在八叉樹結(jié)構(gòu)細(xì)分的基礎(chǔ)上提出一種二次線性加密的體素細(xì)分算法，該方法在保證體素模型精度的前提下，盡量避免了不必要的體素分割，降低體素?cái)?shù)量、提高算法效率。線性加密算法是指，對(duì)于經(jīng)過(guò)八叉樹加密后的葉節(jié)點(diǎn)體素，僅在其不滿足體素閾值的方向上進(jìn)行線性均勻細(xì)分，使得細(xì)分后體素三邊均滿足體素閾值的要求。

類似地，在不考慮空節(jié)點(diǎn)體素刪除的影響下，采用線性細(xì)分后的體素?cái)?shù)量M2可表示為：

M2=M×α×β。

(7)

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

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

2.4 表面體素顏色計(jì)算

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

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

(8)

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

(9)

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

3 算法驗(yàn)證

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

3.1 算法效果

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

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

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

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

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

3.2 算法數(shù)據(jù)

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

表2 各彩色模型表面體素化的參數(shù)

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

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

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

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

可以預(yù)知，在體素化精度和算法效率方面，本文提出的算法具有明顯的優(yōu)勢(shì)。相比于文獻(xiàn)[2]等提出的體素化方法，本文算法通過(guò)提前細(xì)分三角面片的方式，保證在較小體素閾值的情況下，彩色模型仍能夠?qū)崿F(xiàn)表面體素化，且體素化模型不會(huì)出現(xiàn)孔洞、裂縫等缺陷。文獻(xiàn)[11]提出一種分割模型包圍盒空間，通過(guò)標(biāo)記細(xì)分采樣點(diǎn)所在體素，以實(shí)現(xiàn)三維模型表面體素化。為更好地與本文算法進(jìn)行對(duì)比，在相同的硬件條件下采用不同的體素化閾值，即不同的體素化分辨率，對(duì)同一模型進(jìn)行體素化處理，本文算法與文獻(xiàn)[11]產(chǎn)生的體素?cái)?shù)量如表3所示。

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

表3 本文算法與文獻(xiàn)[11]算法數(shù)據(jù)比較

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

表3中，有效體素?cái)?shù)量是指最終的體素化模型所包含的體素?cái)?shù)量。理論上，在相同的體素化分辨率下，本文算法和文獻(xiàn)[11]算法得到的體素模型的有效體素?cái)?shù)量應(yīng)該相等，表3中的實(shí)驗(yàn)數(shù)據(jù)證實(shí)了這一點(diǎn)。表3中，模型在體素閾值為1.6 mm和0.8 mm下進(jìn)行體素化處理，本文算法和文獻(xiàn)[11]算法產(chǎn)生的有效體素?cái)?shù)量存在細(xì)微差異，這主要是因?yàn)樵谑褂帽疚乃惴ê臀墨I(xiàn)[11]算法時(shí)，通過(guò)預(yù)設(shè)體素閾值計(jì)算最終體素模型分辨率，即模型在xyz三軸上的分割段數(shù)不一樣導(dǎo)致的，如體素閾值為1.6mm時(shí)，本文算法的體素化分辨率是32×16×8，而文獻(xiàn)[11]的體素化分辨率是25×13×7。

4 結(jié)束語(yǔ)

本文針對(duì)現(xiàn)有三維模型表面體素化過(guò)程容易出現(xiàn)表面破裂、體素模型精度低等問(wèn)題，提出一種彩色模型表面體素化算法，該算法以O(shè)BJ彩色模型作為算法研究對(duì)象，將八叉樹數(shù)據(jù)結(jié)構(gòu)應(yīng)用于模型分割過(guò)程。針對(duì)OBJ模型部分三角面片過(guò)大導(dǎo)致的表面體素模型出現(xiàn)破裂的現(xiàn)象，提出一種基于最大邊長(zhǎng)比的三角面片均勻細(xì)分算法，保證得到的體素模型能夠完全封閉。針對(duì)現(xiàn)有表面體素化模型精度較低的現(xiàn)象，本文提出一種表面體素線性細(xì)分算法，大大提高了體素模型的精度。最后，本文使用了多個(gè)OBJ模型對(duì)上述算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，即是設(shè)定較小的體素分割閾值，算法仍然能夠保證所得體素模型的全封閉性。

本文算法具有以下意義：

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

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

(3)本文算法同樣適用于薄層結(jié)構(gòu)的表面體素化，這是基于模型輪廓的體素化算法所不能實(shí)現(xiàn)的功能。

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

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

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