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

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

（內蒙古科技大學機械工程學院，內蒙古包頭014000）

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

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

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

1 人機交互分段算法

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

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

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

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

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

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

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

2 自動分段算法

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

2.1 體素化分段算法

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

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

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

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

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

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

2.2 特征識別式分段算法

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

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

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

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

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

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

2.3 多目標優化分段算法

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

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

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

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

圖7 魯班鎖連接結構Fig.7 Luban lock connection structure

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

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

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

2.4 聚類式分段算法

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

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

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

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

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

3 結論與展望

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

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

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

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

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