面向無支撐3D打印的近似金字塔形狀分解

周鈺琛 黃嘉誠 岳興春 彭勇 宋威

摘? 要：FDM法是當前3D打印中應用最廣泛的方法之一，該方法有許多優點，但也存在的需要添加支撐結構才能打印懸垂部分的缺點。針對該缺點，設計了一種近似金字塔形狀分解的方法，通過采樣平面對模型進行分區，構建點的分類投票矩陣，通過kd-tree加速的分區聚類算法對模型進行分解。結果表明，該分解方法能成功將原模型分解為若干不需要支撐即可進行3D打印的部分。

關鍵詞：3D打?。粺o支撐；采樣平面；DBSCAN聚類；投票矩陣

中圖分類號：TP391? 文獻標識碼：A? ? 文章編號：2096-4706（2023）06-0149-05

Approximate Pyramid Shape Decomposition for Support-Free 3D Printing

ZHOU Yuchen1， HUANG Jiacheng1， YUE Xingchun1， PENG Yong1， SONG Wei2

（1.School of Internet of Things， Jiangnan University， Wuxi? 214122， China;

2.School of Artificial Intelligence and Computer Science， Jiangnan University， Wuxi? 214122， China）

Abstract： The FDM method is currently one of the most widely used methods in 3D printing. This method has many advantages， but also has the disadvantage of requiring the addition of support structures to print overhangs. Aiming at this shortcoming， a method of approximate pyramid shape decomposition is designed. The model is partitioned by sampling planes， the classification voting matrix of points is constructed， and the model is decomposed by the kd-tree accelerated partition clustering algorithm. The results show that this decomposition method can successfully decompose the original model into several parts that can be 3D printed without support.

Keywords： 3D printing; support-free; sampling plane; DBSCAN clustering; voting matrix

0? 引? 言

FDM（Fused Deposition Modeling）法，即熔積成型法是現在使用最為廣泛的3D打印方法之一。FDM法的工作原理是通過加熱的噴嘴將材料熔化并擠出，再將材料逐層放置于構建平臺。每次只能放置一層材料，直至部件構建完成。FDM法具有打印機結構簡單、成本低、成型速度快等優點，但對于平行于構建平臺的模型懸垂部分，需要在打印時添加支撐結構并在打印結束后去除，耗費大量時間和材料。

無支撐打印的實現目前主要分為通過多軸機械臂實現和通過模型分割實現兩個方面。多軸機械臂能從多個方向進行打印。王錚等[1]提出了通過多叉分解樹進行多軸機械臂路徑規劃，從而削減支持的方法。張帆等[2]提出了一種基于EtherCAT的協同控制方法，控制多軸機械臂完成無支撐打印。

通過模型分割減少支撐甚至實現無支撐3D打印也一直是人們追求的目標。Yang等[3]提出了一種針對殼模型內部填充算法實現自支撐；黃常標[4]等人提出了基于邊界的分割方法，實現模型Z的無干涉分解；Herholz等人[5]基于高度場實現模型無支撐分解；易兵等人[6]提出基于高斯映射法向聚類分割方法，將模型分解為各類特征形狀；Wei等人[7]以骨架為基礎，將薄殼模型分解可無支撐打印的部分。

本文基于多邊形凸分解思想，提出一種基于近似金字塔形狀的模型分解方法，首先讀入模型的STL模型并進行預處理，然后通過在平行于打印方向上生成一定采樣平面，將模型中的點進行分類；再通過kd-tree加速的DBSCAN分區聚類算法將各個相同分類且連通的點聚合成塊，每個塊在打印方向上都是近似金字塔形狀，每個塊都不需要支撐便能使用FDM法進行打印。實驗結果顯示本方法達到了設計要求。

1? STL模型的讀取和預處理

STL文件是當前3D打印領域被廣泛使用的打印模型文件。STL文件包含多個三角形面片的定義，每個三角形面片的定義包括三角形各個定點的三維坐標及三角形面片的法矢量。本文中STL模型的讀取和預處理主要包括根據STL文件建立半邊數據結構、模型的封閉性檢測和模型漏洞的填補，最后在STL模型內生成點云或者將STL模型進行體素化處理。

1.1? 建立半邊數據結構

半邊數據結構是以邊為中心的數據結構。該結構能夠存儲網格模型頂點、邊、面間的拓撲關系，使得對網格模型的局部查找操作更加高效。半邊數據結構由頂點（Vertex）、半邊（HalfEdge）、邊（Edge）、面（Face）和模型（Mesh）五部分構成。半邊數據結構的類關系如圖1所示。

1.2? 模型的封閉性檢測和漏洞填補

理想情況下，3D打印使用的STL網格模型應該是完全封閉的。但現實中因為各種原因，讀入的STL網格模型可能存在表面孔洞，并不是封閉的，因此需要對網格模型進行封閉性檢測，并對漏洞進行填補。

首先檢測模型是否是封閉的。對網格模型的所有邊進行檢查，如果發現某一條邊A只被一個網格面所包含，則認為這條邊是一條邊界邊，在這條邊的附近存在漏洞。利用半邊數據結構，找到這條邊A指向的頂點P，并檢查P連接的所有邊，找出與點P相連的下一條邊界邊A1，通過找出A1指向的頂點P1，以此類推。當第二次找到邊A或者頂點P時，說明回到了起點，找到了一個漏洞，將所有找到的邊和頂點作為漏洞輪廓的邊集H和點集V記錄下來。

之后對點集V進行Delaunay三角剖分，目的是在點集V內生成滿足最大化最小角性質和最小化外接圓性質的三角形網格。實現模型漏洞的填補。

最后在封閉的STL模型內生成點云，也可以對STL模型進行體素化處理。本文選擇的是生成點云的處理。

2? 點的分類投票

在讀入STL模型并進行相關預處理后，對模型內的點依據金字塔形狀進行分類，構建分類投票矩陣。

2.1? 近似金字塔形狀

設一個多邊形S有一底邊（面）B（S），對多邊形內部任意一點P，作P到P在B（S）上的垂直投影點P′的連線；若線段PP′完全在S內，則稱S為近似金字塔形的多邊形。設多邊形S垂直于B（S）向上的方向為O（S），則多邊形S內的每個點都必須從底邊（面）B（S）上的某個點沿O（S）可見。與B（S）相對的邊（面），在沿O（S）方向定義了一個能描述多邊形S高度的函數，如圖2所示。

從上述定義可以知道，如果多邊形S是近似金字塔形的，則使用FDM法打印該多邊形時，只要將底面B（S）選作構建平臺，則不需要添加額外的支撐結構即可完成打印，因為S中不存在平行于B（S）的懸垂部分。

最理想的分解目標是找到使得金字塔形狀最少的模型分解結果。然而該目標的實現非常困難。文獻[8]中Fekete和Mit-chell證明了該類形狀分解問題在3D空間內是NP-hard問題，即難以為該目標找到一個多項式時間復雜度的算法；該目標可能沒有多項式時間的解，同時未必可以在多項式時間內驗證一個解的正確性。

因此本文的方法旨在產生一種模型分解結果，同時讓分解的數量盡可能少，但不驗證分解的結果是否使得金字塔形狀最少。

2.2? 點的分類投票

模型的打印方向一般為Z方向，因此垂直于Z方向產生若干平行于XOY平面的采樣平面。設采樣平面集D{D0，D1，D2，…，DN}，D內的點按Z坐標由小到大的順序排列。產生采樣平面的目的是作為近似金字塔形狀的底面，讓模型內的點都能被分類到以某個采樣平面為底面的金字塔形狀中。若模型內的點在以某個采樣平面為底面的金字塔形狀中，則稱該點投票給該采樣平面。

為了產生盡可能少的分解結果，沿Z軸正向和負向的兩個方向考察模型S內的點P （xp， yp， zp），判斷該點P沿這兩個采樣方向能否投票給某一采樣平面。以點P為頂點，分別向Z軸正向和負向作射線，設正向射線與S的沿射線方向的第一個交點為Q （xQ， yQ， zQ），負向射線與S的沿射線方向的第一個交點為R （xR， yR， zR）。如圖3所示。通過比較交點的Z坐標與各采樣平面的Z坐標來判斷點P能投票給哪些采樣平面。

2.3? 投票矩陣的構建

構造投票矩陣M=（bik）（n+1）（m+1），其中n為采樣平面數量，m+1為點的數量，前n+1行表示對應下標的采樣平面能接受哪些點的投票，第n+2行表示點P能投票的最遠的采樣平面。對于一個采樣平面，若某點能向上投票給該平面，則在矩陣中將該行對應的列賦值為1，若能向下投票給該平面，則賦值為-1。每一列第n+2行的絕對值表示該列對應的點能投票最遠采樣平面在平面集D中的下標；符號代表投票方向，正號代表向上投票，負號代表向下投票。初始化令矩陣內所有元素值為0。如式（1）。對于交點Q，按下標由大到小的順序，依次比較D內的平面Di與點Q的Z坐標。找到第一個平面Dg，使得ZDg≤ZQ，則認為平面Dg是點P向上投票的最遠采樣平面，計算點P到平面Dg的距離h1=ZDh-ZP，并讓點P投票向上給所有位于點P和平面Dg之間的采樣平面，即在投票矩陣中，讓所有對應的bik=1。同樣地，對于交點R，則按下標由小到大的順序，依次比較平面Di與點R的Z坐標，當找到第一個平面Dh，使得ZDh ≥ZR，則認為平面Dh是點R向下投票的最遠采樣平面。如圖4所示。計算點P到平面Dh的距離h2=ZP-ZDh，讓點R向下投票給所有位于點R和平面Dh之間的所有采樣平面，即在投票矩陣中，讓所有對應的bik=-1。比較h1和h2，若h1＞h2，則認為平面Dg為點P的最遠投票平面，且對應的b（n+1）k=g，g為平面Dg的下標。反之則認為平面Dh為點P的最遠投票平面，并讓對應的b（n+1）k=-h，h為平面Dh的下標。

（1）

3? DBSCAN聚類分解

對模型中的點進行分類并構造投票矩陣后，使用經kd-tree加速的分區DBSCAN聚類算法對點進行聚類。聚類的目的是找出一個連通的區域，該區域內的點能沿同一方向投票給同一采樣平面，也就是說，該區域內的點能與同一采樣平面構成一個連通的金字塔形狀。

3.1? kd-tree加速的DBSCAN聚類算法

DBSCAN算法是一種基于密度的聚類算法，可以發現滿足某一密度條件的任意形狀的聚類。DBSCAN定義了兩個關鍵參數：Eps鄰域半徑和Minpts最小點集。由這兩個參數又定義了如下幾個概念：

核心點：在其鄰域半徑Eps內點數目大于等于Minpts的點。

噪聲點：在其鄰域半徑Eps內點數目小于于Minpts的點。

直接密度可達：若點p是核心點，點q在點p的Eps鄰域內，則稱點q到點p直接密度可達。

密度可達：設區域內一連串的點ci（i=1， 2， …，n），設a=c1，b=cn，若ci到ci-1均直接密度可達，則認為a和b密度可達。

DBSCAN聚類的思想是，首先找出一個核心點，將區域中所有與該核心點密度可達的點都聚為一類。之后找出下一個核心點，重復上述過程，直到區域中所有點都完成聚類。

傳統的DBSCAN聚類算法在檢查點Eps鄰域內點的數量時采用暴力遍歷的方法，效率比較低下，在區域內點的數量較多時嚴重影響運行速度。kd-tree是一種用于對多維空間數據進行劃分和存儲的二叉樹數據結構。本文先對區域內的點建立kd-tree，并利用最高優先級的思想結合DFS深度優先搜索實現kd-tree內的最近鄰查詢，來加速DBSCAN算法的Eps鄰域檢查。

3.2分區參數確定

為了使分解邊界更加清晰，同時為了能自適應確定DBSCAN算法的Eps鄰域半徑和Minpts最小點集兩個參數，減小人為選擇參數對聚類結果的影響，依據k-dist圖的思想，對模型內的點進行分區。以投票矩陣M作為分區依據，不論投票方向，將能投票到同一采樣平面的點分在同一區，同一個點可以被允許存在于多個不同的分區中。對每一個分區，利用kd-tree快速計算分區內每個點與其第k近鄰點之間的距離。區域內的點都是三維坐標點，k值取比維度高1，k=4，按距離由小到大的順序對分區內的點進行排序。以排序后的點的序號為橫坐標，點到第k近鄰點之間的距離為縱坐標，畫出k-dist圖，如圖5所示。從圖可知，大部分點的第k近鄰距離都比較接近，小部分點的第k近鄰距離較大。利用4階多項式（2）對k-dist圖進行曲線擬合，利用式（3）計算二階導數并獲得曲線（x0， f （x0））拐點（x0， f （x0））。將 f （x0）作為該分區的Eps鄰域半徑，k值作為Minpts的值。

（2）

（3）

3.3? 對模型內點聚類分解

使用上述改進DBSCAN算法對點進行聚類?；谪澬乃枷耄瑸榱双@得盡可能少的分解結果，將核心點能投票的最遠采樣平面規定為參考平面，對應的投票方向為參考方向，目的是為了讓聚類生成的金字塔形狀擁有盡量大的高度?？疾焖信c核心點密度可達的點，將能夠以參考方向投票給參考平面的點加入聚類，目的是獲得盡量大的連通區域，將盡量多連通且能與參考平面構成金字塔形狀的點加入聚類。具體步驟如下：

（1）遍歷模型內的點，依據點能投票的最遠參考平面獲取對應分區的Eps和Minpts，并利用kd-tree判斷當前點是否為核心點。發現一個核心點P后，建立一個新的簇C。并將點P標記為已處理。否則標記為噪聲點。

（2）通過投票矩陣，檢索投票矩陣中點P對于列的第n+2行的值，獲取點P能投票的最遠采樣平面和對應的采樣方向。作為當前聚類的采樣參考平面和采樣參考方向，分別設為平面D和方向O（P）。

（3）遍歷點P的Eps鄰域中的點，將所有能以方向O（P）投票給平面D的點加入簇C。

（4）考察簇C中除點P以外的點，通過kd-tree判斷是否為核心點。若為核心點，則將該核心點Eps鄰域內能以方向O（P）投票給平面D的點加入簇C，同時將該點標記為已處理。若為噪聲點，則只標記為已處理。

（5）重復步驟（4），直到簇C內所有點都被考察且簇C不再擴展為止。此時簇C便是一個近似金字塔形狀的聚類塊。

（6）重復步驟（1）至（5），直到所有點都被處理為止，完成聚類。

聚類流程如圖6所示。

4? 分解結果

對分別包含20 000、50 000、100 000個點的模型，分別對其進行傳統DBSCAN聚類、kd-tree加速的DBSCAN聚類和10個分區的kd-tree加速DBSCAN分區聚類，計算聚類完成所用的時間。如表1所示。可見經kd-tree加速的DBSCAN聚類算法能大幅加速聚類過程。分區聚類的聚類時間相比直接聚類有所增長，但也能自適應生成Eps和Minpts，免去了設定參數的步驟。

利用本方法對模型A、模型B進行近似金字塔形狀分解，分解結果如圖7～10所示。

相關聚類信息如表2所示。可以看到本方法能將模型垂直于打印方向的懸垂部分分解成塊，且盡量使每一個塊更大，來獲得盡量少的分解結果，基本達到設計要求。

5? 結? 論

本文提出了一種用于STL模型的近似金字塔形狀分解方法，目的是將STL模型分解成能夠實現無支撐3D打印的部分。人為地在模型中劃分出投票平面，將模型內的點依據投票平面進行分類，并使用kd-tree加速的DBSCAN聚類算法將各點聚類成塊。實際結果表明，本方法能夠將模型在一定方向上分割成可無支撐打印的部分，且盡量減少分割數量，基本達到設計要求。

本方法目前還存在分割結果受投票平面影響較大、各分割部分間邊界不夠平滑、分割數量依然可以優化等問題。后續工作將引入對模型表面的特征提取方法，合理劃分投票平面；考慮使用Douglas Peucker算法對邊界進行細化和擬合；建立一套評價方法，用于衡量分解數量是否盡可能少。進一步提升分解的質量。

參考文獻：

[1] 王錚，趙東標.FDM五軸3D打印支撐消減算法研究 [J/OL].機械科學與技術：1-5（2022-05-17）.DOI：10.13433/j.cnki.

1003-8728.20200652.

[2] 張帆，肖述文，涂一文，等.多軸機械臂3D打印的運動-擠料協同控制方法 [J].機械設計與研究，2021，37（6）：141-147+154.

[3] YANG Y，CHAI S，FU X M. Computing interior support-free structure via hollow-to-fill construction [J]. Computers & Graphics，2017，70：148-156.

[4] 黃常標，劉斌，江開勇，等.基于邊界分割的STL模型三維分段 [J].機械科學與技術，2014，33（6）：870-874.

[5] HERHOLZ P，MATUSIK W，ALEXA M. App-roximating Free-form Geometry with Height Fields for Manufacturing [J].Computer Graphics Forum，2015，34（2）：239-251.

[6] 易兵，劉振宇，譚建榮.基于高斯映射的CAD網格法向聚類分割方法[J].機械工程學報，2015，51（7）：115-123.

[7] WEI X，QIU S，ZHU L，et al. Toward support-free 3d printing：a skeletal approach for partitioning models [J].IEEE Trans Vis Comput Graph，2017，24（10）：2799-2812.

[8] FEKETE S P，MITCHELL J S B. Terrain decomposition and layered manufacturing [J].Int J Comput Geom Appl，2001，11（6）：647-668.

作者簡介：周鈺?。?996—），男，仫佬族，廣西柳州人，碩士研究生，主要研究方向：嵌入式系統設計與集成；彭勇（1964—），男，漢族，江蘇南京人，碩士，副教授，主要研究方向：嵌入式系統設計與集成。

收稿日期：2022-10-27