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

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

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

關(guān)鍵詞：3D打印；無支撐；采樣平面；DBSCAN聚類；投票矩陣

中圖分類號：TP391? 文獻(xiàn)標(biāo)識碼：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）法，即熔積成型法是現(xiàn)在使用最為廣泛的3D打印方法之一。FDM法的工作原理是通過加熱的噴嘴將材料熔化并擠出，再將材料逐層放置于構(gòu)建平臺。每次只能放置一層材料，直至部件構(gòu)建完成。FDM法具有打印機(jī)結(jié)構(gòu)簡單、成本低、成型速度快等優(yōu)點(diǎn)，但對于平行于構(gòu)建平臺的模型懸垂部分，需要在打印時(shí)添加支撐結(jié)構(gòu)并在打印結(jié)束后去除，耗費(fèi)大量時(shí)間和材料。

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

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

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

1? STL模型的讀取和預(yù)處理

STL文件是當(dāng)前3D打印領(lǐng)域被廣泛使用的打印模型文件。STL文件包含多個三角形面片的定義，每個三角形面片的定義包括三角形各個定點(diǎn)的三維坐標(biāo)及三角形面片的法矢量。本文中STL模型的讀取和預(yù)處理主要包括根據(jù)STL文件建立半邊數(shù)據(jù)結(jié)構(gòu)、模型的封閉性檢測和模型漏洞的填補(bǔ)，最后在STL模型內(nèi)生成點(diǎn)云或者將STL模型進(jìn)行體素化處理。

1.1? 建立半邊數(shù)據(jù)結(jié)構(gòu)

半邊數(shù)據(jù)結(jié)構(gòu)是以邊為中心的數(shù)據(jù)結(jié)構(gòu)。該結(jié)構(gòu)能夠存儲網(wǎng)格模型頂點(diǎn)、邊、面間的拓?fù)潢P(guān)系，使得對網(wǎng)格模型的局部查找操作更加高效。半邊數(shù)據(jù)結(jié)構(gòu)由頂點(diǎn)（Vertex）、半邊（HalfEdge）、邊（Edge）、面（Face）和模型（Mesh）五部分構(gòu)成。半邊數(shù)據(jù)結(jié)構(gòu)的類關(guān)系如圖1所示。

1.2? 模型的封閉性檢測和漏洞填補(bǔ)

理想情況下，3D打印使用的STL網(wǎng)格模型應(yīng)該是完全封閉的。但現(xiàn)實(shí)中因?yàn)楦鞣N原因，讀入的STL網(wǎng)格模型可能存在表面孔洞，并不是封閉的，因此需要對網(wǎng)格模型進(jìn)行封閉性檢測，并對漏洞進(jìn)行填補(bǔ)。

首先檢測模型是否是封閉的。對網(wǎng)格模型的所有邊進(jìn)行檢查，如果發(fā)現(xiàn)某一條邊A只被一個網(wǎng)格面所包含，則認(rèn)為這條邊是一條邊界邊，在這條邊的附近存在漏洞。利用半邊數(shù)據(jù)結(jié)構(gòu)，找到這條邊A指向的頂點(diǎn)P，并檢查P連接的所有邊，找出與點(diǎn)P相連的下一條邊界邊A1，通過找出A1指向的頂點(diǎn)P1，以此類推。當(dāng)?shù)诙握业竭匒或者頂點(diǎn)P時(shí)，說明回到了起點(diǎn)，找到了一個漏洞，將所有找到的邊和頂點(diǎn)作為漏洞輪廓的邊集H和點(diǎn)集V記錄下來。

之后對點(diǎn)集V進(jìn)行Delaunay三角剖分，目的是在點(diǎn)集V內(nèi)生成滿足最大化最小角性質(zhì)和最小化外接圓性質(zhì)的三角形網(wǎng)格。實(shí)現(xiàn)模型漏洞的填補(bǔ)。

最后在封閉的STL模型內(nèi)生成點(diǎn)云，也可以對STL模型進(jìn)行體素化處理。本文選擇的是生成點(diǎn)云的處理。

2? 點(diǎn)的分類投票

在讀入STL模型并進(jìn)行相關(guān)預(yù)處理后，對模型內(nèi)的點(diǎn)依據(jù)金字塔形狀進(jìn)行分類，構(gòu)建分類投票矩陣。

2.1? 近似金字塔形狀

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

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

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

因此本文的方法旨在產(chǎn)生一種模型分解結(jié)果，同時(shí)讓分解的數(shù)量盡可能少，但不驗(yàn)證分解的結(jié)果是否使得金字塔形狀最少。

2.2? 點(diǎn)的分類投票

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

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

2.3? 投票矩陣的構(gòu)建

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

（1）

3? DBSCAN聚類分解

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

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

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

核心點(diǎn)：在其鄰域半徑Eps內(nèi)點(diǎn)數(shù)目大于等于Minpts的點(diǎn)。

噪聲點(diǎn)：在其鄰域半徑Eps內(nèi)點(diǎn)數(shù)目小于于Minpts的點(diǎn)。

直接密度可達(dá)：若點(diǎn)p是核心點(diǎn)，點(diǎn)q在點(diǎn)p的Eps鄰域內(nèi)，則稱點(diǎn)q到點(diǎn)p直接密度可達(dá)。

密度可達(dá)：設(shè)區(qū)域內(nèi)一連串的點(diǎn)ci（i=1， 2， …，n），設(shè)a=c1，b=cn，若ci到ci-1均直接密度可達(dá)，則認(rèn)為a和b密度可達(dá)。

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

傳統(tǒng)的DBSCAN聚類算法在檢查點(diǎn)Eps鄰域內(nèi)點(diǎn)的數(shù)量時(shí)采用暴力遍歷的方法，效率比較低下，在區(qū)域內(nèi)點(diǎn)的數(shù)量較多時(shí)嚴(yán)重影響運(yùn)行速度。kd-tree是一種用于對多維空間數(shù)據(jù)進(jìn)行劃分和存儲的二叉樹數(shù)據(jù)結(jié)構(gòu)。本文先對區(qū)域內(nèi)的點(diǎn)建立kd-tree，并利用最高優(yōu)先級的思想結(jié)合DFS深度優(yōu)先搜索實(shí)現(xiàn)kd-tree內(nèi)的最近鄰查詢，來加速DBSCAN算法的Eps鄰域檢查。

3.2分區(qū)參數(shù)確定

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

（2）

（3）

3.3? 對模型內(nèi)點(diǎn)聚類分解

使用上述改進(jìn)DBSCAN算法對點(diǎn)進(jìn)行聚類?；谪澬乃枷?，為了獲得盡可能少的分解結(jié)果，將核心點(diǎn)能投票的最遠(yuǎn)采樣平面規(guī)定為參考平面，對應(yīng)的投票方向?yàn)閰⒖挤较?，目的是為了讓聚類生成的金字塔形狀擁有盡量大的高度。考察所有與核心點(diǎn)密度可達(dá)的點(diǎn)，將能夠以參考方向投票給參考平面的點(diǎn)加入聚類，目的是獲得盡量大的連通區(qū)域，將盡量多連通且能與參考平面構(gòu)成金字塔形狀的點(diǎn)加入聚類。具體步驟如下：

（1）遍歷模型內(nèi)的點(diǎn)，依據(jù)點(diǎn)能投票的最遠(yuǎn)參考平面獲取對應(yīng)分區(qū)的Eps和Minpts，并利用kd-tree判斷當(dāng)前點(diǎn)是否為核心點(diǎn)。發(fā)現(xiàn)一個核心點(diǎn)P后，建立一個新的簇C。并將點(diǎn)P標(biāo)記為已處理。否則標(biāo)記為噪聲點(diǎn)。

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

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

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

（5）重復(fù)步驟（4），直到簇C內(nèi)所有點(diǎn)都被考察且簇C不再擴(kuò)展為止。此時(shí)簇C便是一個近似金字塔形狀的聚類塊。

（6）重復(fù)步驟（1）至（5），直到所有點(diǎn)都被處理為止，完成聚類。

聚類流程如圖6所示。

4? 分解結(jié)果

對分別包含20 000、50 000、100 000個點(diǎn)的模型，分別對其進(jìn)行傳統(tǒng)DBSCAN聚類、kd-tree加速的DBSCAN聚類和10個分區(qū)的kd-tree加速DBSCAN分區(qū)聚類，計(jì)算聚類完成所用的時(shí)間。如表1所示?？梢娊?jīng)kd-tree加速的DBSCAN聚類算法能大幅加速聚類過程。分區(qū)聚類的聚類時(shí)間相比直接聚類有所增長，但也能自適應(yīng)生成Eps和Minpts，免去了設(shè)定參數(shù)的步驟。

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

相關(guān)聚類信息如表2所示?？梢钥吹奖痉椒軐⒛Ｐ痛怪庇诖蛴》较虻膽掖共糠址纸獬蓧K，且盡量使每一個塊更大，來獲得盡量少的分解結(jié)果，基本達(dá)到設(shè)計(jì)要求。

5? 結(jié)? 論

本文提出了一種用于STL模型的近似金字塔形狀分解方法，目的是將STL模型分解成能夠?qū)崿F(xiàn)無支撐3D打印的部分。人為地在模型中劃分出投票平面，將模型內(nèi)的點(diǎn)依據(jù)投票平面進(jìn)行分類，并使用kd-tree加速的DBSCAN聚類算法將各點(diǎn)聚類成塊。實(shí)際結(jié)果表明，本方法能夠?qū)⒛Ｐ驮谝欢ǚ较蛏戏指畛煽蔁o支撐打印的部分，且盡量減少分割數(shù)量，基本達(dá)到設(shè)計(jì)要求。

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

參考文獻(xiàn)：

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

1003-8728.20200652.

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

[3] YANG Y，CHAI S，F(xiàn)U X M. Computing interior support-free structure via hollow-to-fill construction [J]. Computers & Graphics，2017，70：148-156.

[4] 黃常標(biāo)，劉斌，江開勇，等.基于邊界分割的STL模型三維分段 [J].機(jī)械科學(xué)與技術(shù)，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網(wǎng)格法向聚類分割方法[J].機(jī)械工程學(xué)報(bào)，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—），男，仫佬族，廣西柳州人，碩士研究生，主要研究方向：嵌入式系統(tǒng)設(shè)計(jì)與集成；彭勇（1964—），男，漢族，江蘇南京人，碩士，副教授，主要研究方向：嵌入式系統(tǒng)設(shè)計(jì)與集成。

收稿日期：2022-10-27