王春香，紀康輝，王 耀，劉 流

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

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

表1 分段算法應用情況Table 1 Application of segmentation algorithm

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

1 人機交互分段算法

對于在成型方向上有多個精度和粗糙度要求的待加工模型，在進行分層處理時，目前仍無法自動且準確地判斷其分段界線，須人為地輸入各個段塊的邊界位置，以完成分段處理。

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

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

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

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

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

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

2 自動分段算法

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

2.1 體素化分段算法

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

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

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

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

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

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

2.2 特征識別式分段算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 聚類式分段算法

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

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

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

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

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

3 結(jié)論與展望

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

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

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

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

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