快速成型技術(shù)中分段算法的研究綜述

王春香，紀(jì)康輝，王 耀，劉 流

（內(nèi)蒙古科技大學(xué)機(jī)械工程學(xué)院，內(nèi)蒙古包頭014000）

快速成型（rapid prototyping）是在現(xiàn)代CAD/CAM（computer aided design/computer aided manu‐facturing，計(jì)算機(jī)輔助設(shè)計(jì)/計(jì)算機(jī)輔助制造）技術(shù)、激光技術(shù)、計(jì)算機(jī)數(shù)控技術(shù)、精密伺服驅(qū)動(dòng)技術(shù)以及新材料技術(shù)的基礎(chǔ)上發(fā)展起來的新興技術(shù)，其基本原理為“分層制造，逐層疊加”［1］，可實(shí)現(xiàn)數(shù)字化模型到實(shí)體模型的轉(zhuǎn)化。但在快速成型技術(shù)的實(shí)際應(yīng)用中，存在幾個(gè)較為突出的問題，如表1所示。

表1 分段算法應(yīng)用情況Table 1 Application of segmentation algorithm

針對(duì)表1所示的情況，若直接進(jìn)行等厚分層或自適應(yīng)分層處理，則均無(wú)法得到較好的分層效果。為了更好地解決上述問題，引入分段算法。分段算法是表面分割算法的延伸。表面分割是指將模型表面分割為多個(gè)區(qū)域，而分段處理是對(duì)模型進(jìn)行體分割，即基于由大變小的原則將完整的三維模型分割為多個(gè)子部分，將模型的整體成型轉(zhuǎn)換為多個(gè)分塊模型的成型與拼接。按照應(yīng)用方法的不同，可將分段算法劃分為多種類型。本文將從人機(jī)交互分段和自動(dòng)分段（包括體素化分段、特征識(shí)別式分段、多目標(biāo)優(yōu)化分段和聚類式分段）兩個(gè)方面對(duì)分段算法展開分析，對(duì)相關(guān)文獻(xiàn)進(jìn)行對(duì)比并對(duì)各分段算法的適用情況進(jìn)行總結(jié)，旨在為快速成型技術(shù)的相關(guān)研究提供參考。

1 人機(jī)交互分段算法

對(duì)于在成型方向上有多個(gè)精度和粗糙度要求的待加工模型，在進(jìn)行分層處理時(shí)，目前仍無(wú)法自動(dòng)且準(zhǔn)確地判斷其分段界線，須人為地輸入各個(gè)段塊的邊界位置，以完成分段處理。

Mani等［2］根據(jù)模型的幾何形狀和粗糙度要求，人為地設(shè)定了模型表面的分段位置，以進(jìn)行人工干預(yù)分段。王春香等［3］從裝配要求出發(fā)，考慮現(xiàn)有等厚分層算法的優(yōu)勢(shì)與不足，提出了按照成型方向上不同的精度要求，對(duì)具有裝配要求的零件模型進(jìn)行分段等厚分層的思想。Liu 等［4］基于給定的誤差，將點(diǎn)云數(shù)據(jù)劃分為多個(gè)區(qū)域。Li等［5］基于快速行進(jìn)分水嶺和標(biāo)記控制的方法，提出了自動(dòng)閾值設(shè)置和手動(dòng)閾值調(diào)節(jié)相結(jié)合的方法以減少堆棧操作，克服了視覺直觀分段控制中存在的困難，解決了可操作性差的問題，提高了分段質(zhì)量及縮短了算法運(yùn)行時(shí)間。

目前，主流的分層算法包括等厚分層算法和自適應(yīng)分層算法，但這2種算法均無(wú)法兼顧成型精度和成型效率［1］。基于分段處理思想，結(jié)合等厚分層算法和自適應(yīng)分層算法對(duì)模型進(jìn)行劃分，即先分段后分層，如圖1所示［6］。但目前這種混合分層算法存在模型分段界線不明確和難以自動(dòng)劃分的問題，仍須采用人機(jī)交互方式，即人為地判定等厚分層算法或自適應(yīng)分層算法的使用界限。Tyberg 等［7］提出了局部自適應(yīng)思想，即先將模型細(xì)分為多個(gè)區(qū)域，再基于誤差最小原則對(duì)每個(gè)區(qū)域進(jìn)行自適應(yīng)分層。Wang等［8］利用基于視覺顯著性分段方法，手動(dòng)地將模型劃分為具有不同顯著性的區(qū)域，并單獨(dú)對(duì)每個(gè)區(qū)域進(jìn)行自適應(yīng)分層。

圖1 模型的單一分層與基于分段的混合分層對(duì)比Fig.1 Comparison of single layering and mixed layer‐ing based on segmentation for model

應(yīng)用分段算法也可將實(shí)體零件模型分為內(nèi)、外兩部分，鑒于內(nèi)部永不可見，可采用比外部層厚大的層厚進(jìn)行分層。Sabourin等［9］運(yùn)用2種分層算法對(duì)模型內(nèi)、外部分進(jìn)行處理：外部精度要求高，采用較小層厚進(jìn)行自適應(yīng)分層；內(nèi)部則采用較大層厚進(jìn)行等厚分層，如圖2所示［10］。Tyberg等［11］利用Stratasys公司的FDM1600 型快速成型機(jī)驗(yàn)證了文獻(xiàn)［9］中分段算法的可行性，該分段算法可使零件模型的成型時(shí)間大幅縮短。

圖2 基于內(nèi)外分段的模型混合分層Fig.2 Hybrid layering of model based on inner and outer segmentation

然而，上述混合分層算法需要有專業(yè)人員通過人機(jī)交互方式來輸入模型分段的邊界位置。對(duì)于邊界特征明顯的模型，其段塊界線易確定；但對(duì)于具有多曲率、多凹凸特征的模型，其段塊界線較為模糊，不易精確劃分且劃分時(shí)要考慮后續(xù)制作過程，這對(duì)專業(yè)能力有要求，從而導(dǎo)致適用人群受到限制。

2 自動(dòng)分段算法

針對(duì)人機(jī)交互分段算法在實(shí)際應(yīng)用中存在局限的問題，國(guó)內(nèi)外學(xué)者開展了關(guān)于自動(dòng)分段算法的研究。自動(dòng)分段是指在無(wú)人為干預(yù)的情況下直接得到準(zhǔn)確的分段界線，自動(dòng)地將整個(gè)模型劃分為多個(gè)段塊。本文將從體素化、特征識(shí)別和多目標(biāo)優(yōu)化等角度入手，以曲率、二面角等多個(gè)因素作為判斷依據(jù)，結(jié)合區(qū)域生長(zhǎng)、聚類等多種算法，對(duì)不同的自動(dòng)分段算法進(jìn)行分析和總結(jié)。

2.1 體素化分段算法

體素化（voxelization）是指將物體的幾何表示形式轉(zhuǎn)化成最接近該物體形狀的體素形式。體素化分段是基于由大變小的原則，將一個(gè)整體模型轉(zhuǎn)化成遵循同一劃分規(guī)則的多個(gè)體素塊模型。不同形狀體素塊的優(yōu)缺點(diǎn)如表2所示。體素化分段可有效解決模型無(wú)法一次成型的問題，通過將模型劃分成多個(gè)體素塊，利用轉(zhuǎn)換成型方向等方法，有效避免了支撐結(jié)構(gòu)的存在。

表2 不同形狀體素塊的優(yōu)缺點(diǎn)對(duì)比Table 2 Comparison of advantages and disadvantages of voxel blocks with different shapes

Hu等［12］和耿國(guó)華［13］將模型劃分為類金字塔狀體素塊，如圖3所示，前者將分段與ECP（exact cover problem，精確覆蓋問題）相聯(lián)系，并運(yùn)用聚類方法推導(dǎo)得到一組類金字塔狀的模型段塊，相較于經(jīng)典的凸分段算法［14］，該方法產(chǎn)生的段塊數(shù)量較少；后者根據(jù)FDM（fused deposition modeling，熔融沉積成型）工藝，提出了一種全局最優(yōu)的模型分段與“打包”算法，將分段與“打包”加工相結(jié)合，以消耗的支撐材料和成型體積為約束條件，得到了一組模型分段的最優(yōu)解。但是，Hu等采用的方法過度依賴于聚類方法，在理論上無(wú)法保證分段效果最優(yōu)。魏瀟然等［15］先采用區(qū)域生長(zhǎng)算法對(duì)模型進(jìn)行分區(qū)，并分析了各分區(qū)的多個(gè)候選劃分方向，然后采用空間期望和椎體期望確定各個(gè)切分平面，將模型分成多個(gè)不需要支撐結(jié)構(gòu)的椎體模型。雖然上述算法可將模型分段為類金字塔狀和椎體形的體素塊，減少或避免了因支撐而產(chǎn)生的材料消耗，便于模型的成型制作，但其并未考慮模型成型后的拼接問題。

圖3 類金字塔狀體素塊Fig.3 Pyramid-like voxel block

為解決成型后的拼接問題，很多學(xué)者將模型劃分為常規(guī)形狀的體素塊。Krause等［16］先將CAD模型分段成多個(gè)長(zhǎng)方體體素塊，然后分別對(duì)每個(gè)長(zhǎng)方塊進(jìn)行切片分層，每一層的厚度取決于所需的表面粗糙度。Zhou等［17］采用連續(xù)折疊序列將三維模型轉(zhuǎn)化為多個(gè)立方體體素塊（如圖4所示），各體素塊之間可形成樹形連接結(jié)構(gòu)。Medellin等［18］和Chan等［19］采用規(guī)則分段和不規(guī)則分段相結(jié)合的方法對(duì)模型進(jìn)行分段處理，對(duì)于規(guī)則分段，以圓柱體體素塊和正方體體素塊為基本單元；對(duì)于不規(guī)則分段，從實(shí)際裝配要求出發(fā)，在接口處形成形狀互補(bǔ)的凹陷/凸起結(jié)構(gòu)。此外，上述文獻(xiàn)也考慮了多個(gè)段塊之間的光滑圓弧過渡連接結(jié)構(gòu)，形成了單獨(dú)的過渡塊。

圖4 立方體體素塊Fig.4 Cube voxel block

2.2 特征識(shí)別式分段算法

特征識(shí)別式分段算法以二面角、特征環(huán)等為模型分段的判斷依據(jù)，同時(shí)結(jié)合閾值、凹凸信號(hào)值等對(duì)模型進(jìn)行特征識(shí)別，以找到分段的邊界位置，實(shí)現(xiàn)模型的分段處理。結(jié)合實(shí)際應(yīng)用情況，可形成多種特征識(shí)別式分段算法，該類算法可有效地解決成型范圍過大和存在多個(gè)最優(yōu)加工方向的模型的分段問題。

湯瑞清等［20］和Jiang 等［21］針對(duì)STL（stereolithog‐raphy，立體光刻）模型，提出了一種基于二面角的特征識(shí)別式分段算法，即通過比較相鄰三角形的法向夾角與預(yù)設(shè)的角度閾值來識(shí)別STL模型的分段邊界特征。王澤昊等［22］提出了一種基于凹凸信號(hào)最小值邊界檢測(cè)的三角網(wǎng)格模型分段算法，通過邊界凹凸信號(hào)最小值的檢測(cè)，實(shí)現(xiàn)了對(duì)三角網(wǎng)格模型分段邊界特征的提取。上述特征識(shí)別式分段算法的優(yōu)缺點(diǎn)如表3所示。

表3 不同特征識(shí)別式分段算法的優(yōu)缺點(diǎn)對(duì)比Table 3 Comparison of advantages and disadvantages of different feature recognition segmentation algorithms

然而，上述算法中的模型大多為STL模型，存在因面片近似逼近模型表面而引起的分段邊界線提取不準(zhǔn)確的問題。為此，王會(huì)鳳等［23］提出了基于特征的模型多目標(biāo)優(yōu)化分段算法，先采用基于圖的特征識(shí)別方式［24］進(jìn)行可加工性分析，再根據(jù)基于約束條件建立的目標(biāo)函數(shù)對(duì)模型的最優(yōu)分段面進(jìn)行選取，并運(yùn)用遺傳算法進(jìn)行多目標(biāo)優(yōu)化，從而完成模型的分段；Chiu等［25］基于識(shí)別得到的特征對(duì)模型凸出部分進(jìn)行分段，將其劃分為特征一致的小尺寸模型，該方法適用于具有懸臂特征的模型。

鑒于特征交匯處會(huì)形成特征環(huán)，可通過識(shí)別和重新構(gòu)造特征環(huán)的方法來確定模型的分段邊界線，從而實(shí)現(xiàn)模型的分段處理。Hao 等［26］通過提取特征邊緣并構(gòu)造特征環(huán)，基于合適的環(huán)路和節(jié)點(diǎn)將復(fù)雜的大尺寸模型劃分為具有相似形狀節(jié)點(diǎn)的簡(jiǎn)單小模型（如圖5所示），該算法基于模型表面曲率進(jìn)行分段處理，相比基于點(diǎn)和面的分段方式，其計(jì)算量大大減少；但是，雖可直接將特征環(huán)作為模型的分段邊界線，但要求待分段模型表面具有顯著特征，導(dǎo)致該算法的適用性并不強(qiáng)。對(duì)于結(jié)構(gòu)較為簡(jiǎn)單的模型，可結(jié)合上述算法和體素化分段算法或矩陣劃分算法進(jìn)行模型分段處理。Kazemi等［27］運(yùn)用交互循環(huán)方法和交互表面方法分別識(shí)別模型的特征，若識(shí)別的特征存在交集，則以該特征輪廓線作為分段邊界線，對(duì)模型進(jìn)行分段處理。紀(jì)小剛［28］基于三維模型與分層切平面相交形成的多個(gè)分段輪廓線，利用三角形網(wǎng)格對(duì)相鄰的分段輪廓線進(jìn)行填充，并在分段處加入空間封閉面，從而完成模型的分段處理。

圖5 基于特征環(huán)的模型分段Fig.5 Model segmentation based on feature loop

2.3 多目標(biāo)優(yōu)化分段算法

多目標(biāo)優(yōu)化分段算法是從實(shí)際成型應(yīng)用的影響因素入手，先建立打分評(píng)價(jià)機(jī)制，構(gòu)建各影響因素的約束條件，再以各影響因素作為目標(biāo)函數(shù)中的變量并對(duì)其賦予相應(yīng)的權(quán)重，由此將模型分段問題轉(zhuǎn)化為目標(biāo)函數(shù)最優(yōu)解求解問題。這類多目標(biāo)優(yōu)化分段算法可有效解決成型尺寸過大且無(wú)法一次成型的模型的分段問題。

Yao等［29］提出了6個(gè)模型分段質(zhì)量評(píng)價(jià)指標(biāo)：應(yīng)力負(fù)載、表面細(xì)節(jié)、界面面積、包裝大小、可打印性和組裝性，并采用層次集方法將這6個(gè)評(píng)價(jià)指標(biāo)集成到1個(gè)分段邊界線尋優(yōu)算法中，重復(fù)進(jìn)行局部多目標(biāo)優(yōu)化，直至找到最優(yōu)的模型分段邊界線，如圖6所示。相比于基于網(wǎng)格和粒子的表示方法，基于層次集的表示方法能更加靈活地處理模型多目標(biāo)優(yōu)化分段問題。Oh 等［30］從加工時(shí)間、加工成本和表面粗糙度這3 個(gè)因素出發(fā)，對(duì)模型進(jìn)行區(qū)域劃分，再將劃分后的模型按最優(yōu)加工方向進(jìn)行加工。Cheng 等［31］將零件成型精度、打印時(shí)間和穩(wěn)定性作為評(píng)價(jià)指標(biāo)，在將實(shí)體模型的表面劃分為不同類型的子表面后，對(duì)每個(gè)子表面賦予相應(yīng)的權(quán)重，以確定最優(yōu)的分段結(jié)果，并完成模型的優(yōu)化分段。該算法不僅適用于平面、圓柱面類模型，也適用于復(fù)雜曲面類模型，適用范圍較為廣泛。

圖6 基于層次集方法的模型分段Fig.6 Model segmentation based on hierarchical set method

然而，上述3種分段算法均以多個(gè)因素作為模型分段目標(biāo)函數(shù)的約束條件，但均未考慮段塊的后續(xù)拼接問題。考慮到段塊單獨(dú)成型后須拼接為整體，則應(yīng)在分段時(shí)預(yù)留連接位置，以便于后續(xù)拼接。Lau等［32］提出了一種預(yù)留螺釘連接口的多目標(biāo)優(yōu)化分段算法，通過在對(duì)家具模型分段時(shí)預(yù)留螺釘連接口的方式，實(shí)現(xiàn)了各零部件模型單獨(dú)打印成型后的后續(xù)裝配。Xin等［33］基于魯班鎖的構(gòu)造原理，將模型分段為連接件和被連接件兩部分，連接件部分采用魯班鎖連接結(jié)構(gòu)形式，如圖7所示，該連接結(jié)構(gòu)不需要粘結(jié)劑且穩(wěn)定性很高。Wang等［34］從優(yōu)化打印方向的角度來提高各模型段塊的表面打印質(zhì)量，并在段塊切面上設(shè)計(jì)了連接器，以便分段模型成型后的手工組裝和拆卸，如圖8所示。

圖7 魯班鎖連接結(jié)構(gòu)Fig.7 Luban lock connection structure

圖8 基于預(yù)留連接器的模型組裝Fig.8 Model assembly based on reserved connector

在對(duì)模型進(jìn)行分段時(shí)，還須考慮段塊的數(shù)量。Luo 等［35］提出了“Chopper”框架，并制定了一些理想劃分的評(píng)價(jià)指標(biāo)，包括可裝配性、分塊數(shù)量、可打印性、美觀性和結(jié)構(gòu)穩(wěn)定性，并建立相應(yīng)的目標(biāo)函數(shù)，采用定向搜素（beam search）優(yōu)化方式逐步構(gòu)建最優(yōu)的BSP（binary space partitioning，二叉空間分割）樹，并通過用戶指導(dǎo)生成模型段塊，如圖9所示。該方法對(duì)分段約束的選擇和目標(biāo)函數(shù)的建立有很大的參考價(jià)值，但未將打印材料的選擇和支撐結(jié)構(gòu)的構(gòu)建納入優(yōu)化體系。

圖9 基于“Chopper”框架的模型分段Fig.9 Model segmentation based on‘Chopper’frame

2.4 聚類式分段算法

聚類分析是目前最常用的數(shù)據(jù)分析處理技術(shù)之一，其通過簇劃分使數(shù)據(jù)集形成若干個(gè)性質(zhì)相似的聚類，屬于無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法［36］。在模型分段過程中，較常使用自適應(yīng)譜聚類、迭代聚類和層次聚類等算法。在很多情況下，常通過結(jié)合聚類算法和其他算法來實(shí)現(xiàn)模型的自動(dòng)分段。聚類式分段算法可有效解決存在多個(gè)最優(yōu)加工方向的模型的分段問題。

石晨晨［37］為了將三角網(wǎng)格聚類成單元，引入了打印方向這一對(duì)成型質(zhì)量至關(guān)重要的因素，并采用投票的方法對(duì)每個(gè)打印方向上的三角網(wǎng)格進(jìn)行投票，將打印方向相同的三角網(wǎng)格聚類成一個(gè)單元；形成聚類單元后，對(duì)所有打印方向上的聚類單元進(jìn)行相似度測(cè)量，形成聚類單元之間的相似度矩陣，并以此作為譜聚類的依據(jù)來對(duì)單元進(jìn)行分塊，從而完成STL 模型表面的分割；最后采用SVM（support vector machine，支持向量機(jī)）算法生成相鄰塊之間的切割平面，從而完成STL模型的分段，效果如圖10所示。該算法極大地提高了加工效率，但受限于加工效率和支撐材料的消耗。對(duì)于復(fù)雜模型，采用該算法分段時(shí)產(chǎn)生的段塊較少，不利于后續(xù)拼接，而且段塊少不但不能提高加工效率，反而會(huì)延長(zhǎng)加工時(shí)間。

圖10 基于聚類算法的模型分段Fig.10 Model segmentation based on clustering algorithm

模型分段問題也可以轉(zhuǎn)化為關(guān)鍵節(jié)點(diǎn)劃分問題，即先找到可表征模型特征的關(guān)鍵節(jié)點(diǎn)，再根據(jù)相關(guān)判據(jù)進(jìn)行段塊劃分。高天一等［38］利用平均曲率骨架方法［39］對(duì)點(diǎn)云模型進(jìn)行骨架提取，并根據(jù)骨架之間的關(guān)系選擇關(guān)鍵節(jié)點(diǎn)，然后選擇同一領(lǐng)域內(nèi)距離質(zhì)心最近的點(diǎn)作為最終的關(guān)鍵節(jié)點(diǎn)，并以此關(guān)鍵節(jié)點(diǎn)作為改進(jìn)區(qū)域生長(zhǎng)算法的種子，從而完成點(diǎn)云模型的分段處理。但是，上述算法未保留點(diǎn)云和三角面片的關(guān)聯(lián)關(guān)系，會(huì)造成可視化過程中分段邊界線不光滑的問題。Jiang 等［40］采用PCA（principal component analy‐sis，主成分分析）方法將模型分段問題從三維轉(zhuǎn)化為二維，即先運(yùn)用網(wǎng)格收縮方法將三維網(wǎng)格模型收縮成平面骨架模型，然后采用PCA 方法對(duì)骨架進(jìn)行節(jié)點(diǎn)提取，并采用迭代聚類算法提取非節(jié)點(diǎn)，從而實(shí)現(xiàn)完整平面骨架模型的提取，最后利用遵循最小規(guī)則的空間掃描法將模型劃分成多個(gè)段塊，并考慮劃分后段塊的大小以及整個(gè)模型的對(duì)稱性、過渡約束和可裝配性，運(yùn)用貪婪算法進(jìn)行調(diào)整劃分，最終完成模型的分段處理，如圖11所示。但該算法不適用于缺乏明顯凹陷特征的模型，且未考慮最優(yōu)加工方向和支撐材料的問題。Hildebrand 等［41］通過法線層次聚類算法尋優(yōu)得到一組最優(yōu)的正交基，并按這3個(gè)正交方向?qū)δＰ瓦M(jìn)行分段。相較于傳統(tǒng)的PCA 方法，基于該算法產(chǎn)生的段塊的體積誤差較小，但計(jì)算量較大且耗時(shí)較長(zhǎng)。

圖11 基于節(jié)點(diǎn)提取的模型分段Fig.11 Model segmentation based on node extraction

3 結(jié)論與展望

本文總結(jié)了快速成型技術(shù)中的分段算法，從人機(jī)交互分段和自動(dòng)分段兩個(gè)方面展開分析，梳理了各分段算法的應(yīng)用情況及優(yōu)缺點(diǎn)，旨在為后續(xù)的分層處理提供參考，結(jié)論和展望如下。

1）綜合國(guó)內(nèi)外研究現(xiàn)狀可知，盡管現(xiàn)有分段算法眾多且面向不同成型模型，但其適用范圍仍然有限，且缺乏系統(tǒng)的分段效果評(píng)價(jià)標(biāo)準(zhǔn)。

2）在快速成型制造中，人機(jī)交互式分段算法得到了實(shí)際應(yīng)用，且成型工藝類型多為FDM及光固化。而自動(dòng)分段算法僅限于仿真模擬，在實(shí)際成型制造中的應(yīng)用仍有待研究。

3）目前僅少數(shù)分段算法考慮了模型分段后的拼接問題，但拼接類型仍有待進(jìn)一步研究。此外，分段時(shí)預(yù)留的裝配接口須考慮模型的性能及可行性。

4）現(xiàn)有分段算法的應(yīng)用對(duì)象多為斯坦福兔子等非工程用模型，針對(duì)工程應(yīng)用領(lǐng)域的零部件（如斗齒、鏈軌節(jié)）模型等的分段技術(shù)仍不成熟。未來可結(jié)合相關(guān)理論，拓寬分段處理在機(jī)械工程領(lǐng)域的應(yīng)用范圍。