一種用於3d列印切片的快速生成方法與流程
2023-05-14 09:21:26 2
本發明涉及3d列印領域，具體涉及3d列印過程中的切片生成。
背景技術：
3d切片是通過切片平面與三維網格模型中的三角面片求交得到。由於三角網格模型通常包含大量的三角面片，如果採用直接求交的方法，其時間開銷將十分巨大，在實際生產過程中基本上不適用。目前，常用的3d切片生成技術通常利用空間剖分樹，如二叉空間剖分樹、八叉樹等數據結構進行加速，減少不必要的三角面片與切片平面的求交次數，從而達到降低時間複雜度的目的。然而，這些空間剖分樹的數據結構往往實現複雜，並且未針對切片平面為平面這一特殊情況進行優化，使得現有的方法實現複雜，生成效率不高。
本發明通過對三角網格中的三角面片根據其最小z值進行分類，構建分類三角面片鍊表，從而快速確定每個切片平面求交時，是否存在新的三角面片與該切片平面有交，極大程度上減少判斷三角面片是否與切片平面有交的次數。通過求交得到切片平面與三角網格的截面輪廓線後，基於二維多邊形掃描填充的算法，可以快速判斷與區分填充區域與空洞區域，減少多邊形內外的判斷。該方法數據結構簡單，魯棒性強，可快速高效的實現3d列印過程中的切片生成。
技術實現要素：
針對目前3d切片方法中數據結構複雜，實現困難，生成效率不高的不足，本發明通過對三角網格中的三角面片根據其最小z值進行分類，構建分類三角面片鍊表，減少判斷三角面片與切片平面是否有交的次數，從而提高切片中輪廓線的生成效率。基於生成的切片輪廓線，結合二維多邊形掃描線填充算法，快速判斷輪廓線之間的填充區域與空洞區域，減少多邊形內外的判斷，從而提高切片中列印路徑生成的效率。
本發明為實現上述目的所採用的技術方案為：
3d列印切片的快速生成分為三個步驟：三維網格的預處理、切片輪廓線的生成與切片中列印路徑的生成。本發明分別針對每個步驟進行優化以提高切片的生成效率，簡化實現的複雜度。
1、三維網格的預處理
三維網格的預處理主要是為了簡化後續兩個步驟運算的複雜度，主要包括模型方向的調整與模型包圍盒的計算。首先，根據用戶列印的需求，調整模型的方向，使得模型的z軸沿著列印方向，從而切片平面均為平行於XOY平面，簡化後續的求交運算；而後計算模型的包圍盒，從而確定3d列印的列印範圍。
2、切片輪廓線的生成
切片輪廓線主要通過切片平面與三角網格中各個三角面片求交得到。通過對三角網格中的三角面片按照其最小z值進行分類，構建分類三角面片鍊表，從而快速判斷存在哪些三角面片開始與切片平面有交，減少三角面片與切片平面求交的次數，提高切片生成的效率。具體步驟包括：
步驟1：根據3d列印的層厚設置d，以及預處理中確定的列印範圍[zb,zt]，確定列印的切片層數n＝(zt-zb)/d；
步驟2：將三角網格中的各個三角面片按三個頂點中的最小z值zmin進行分類，構建分類三角面片鍊表(簡稱分類面表)。分類的準則為：(1)若三個頂點中的最小z值和最大z值的差別小於給定的層厚d，則說明該三角面片位於該切片平面內，忽略該三角面片；(2)根據公式(1)計算該三角面片的類別k，將該三角面片的索引fid以及最大z值對應的類別kmax插入到第k個鍊表中。最終的分類面表如圖1所示。
k＝(zmin-zb)/d (1)
步驟3：自底向上遍歷所有的切片平面zk＝zb+kd，計算切片平面與三角面片的交點。
步驟3.a：從分類面表中取出第0個鍊表中的所有三角面片到當前待求交三角面片鍊表(簡稱活化面表)中，計算切片平面z0與活化面表中各三角面片的交點。此時的交點即為各個三角面片中的對應的頂點；
步驟3.b：設置k＝1；
步驟3.c：判斷活化面表中的各個三角面片是否與切片平面k依然存在交點，即判斷k<＝kmax。若成立，則依然存在交點，否則，不再存在交點，將該三角面片從活化面表中刪除；
步驟3.d：判斷是否有新的三角面片需要加入求交，即判斷第k類分類面表是否為空。若不為空，則將該鍊表中的三角面片加入到當前活化面表；
步驟3.e，計算當前活化面表中各三角面片與切片平面的交點。對於三角形的每條邊，若邊的兩個端點跨越切片平面的兩邊，計算該邊與切片平面的交點。由於分類邊表中已經將三個頂點均位於同一類的情形過濾，因此每個三角面片會得到兩個交點，從而形成切片輪廓線中的一條邊。
步驟3.f：根據三角形的鄰接關係，將求交得到的每條邊首尾相連得到當前切片層的輪廓線；
步驟3.g：設置k＝k+1；
步驟3.h：重複步驟3.c到3g，直到分類面表及活化面表中的三角面片均為空。
3、切片列印路徑的生成
切片列印路徑的生成，其主要目的是確定當前列印方向中哪些區域是填充區域，哪些區域是空洞區域，對於填充區域，利用掃描線對其進行填充。空洞區域與填充區域的判斷，等價於多邊形內外的判斷。因此，基於步驟2中獲得的切片輪廓線，可將該問題轉化為多邊形的掃描填充的問題。通過掃描線與輪廓線的交點性質，可消除點在多邊形內外的判斷，從而提高切片列印路徑的生成效率。具體步驟包括：
步驟1：根據印表機在y軸方向的精度d以及預處理過程中得到的y方向的列印範圍[yb,yt]，確定掃描線的條數n＝(yt-yb)/d；
步驟2：將切片輪廓線中的各邊按兩個頂點中的最小y值ymin進行分類，構建分類邊表。分類的準則為：(1)若兩個頂點中的最小y值和最大y值的差別小於給定的精度d，則忽略該邊；(2)根據公式(2)計算該邊的類別k，將該邊的索引eid以及最大y值對應的類別kmax插入到第k個鍊表中。
k＝(ymin-yb)/d (2)
由於掃描線每次移動d，掃描線與邊的交點的x值只會變化一個常數d/m，因此預先計算該值並保存在分類邊表中。最終的分類邊表如圖2所示。
步驟3：自底向上遍歷所有的掃描線yk＝yb+kd，計算掃描線與各邊的交點。
步驟3.a：從分類邊表中取出第0個鍊表中的所有邊到當前待求交邊表(簡稱活化邊表)中，計算掃描線y0與活化邊表中各邊的交點。此時的交點即為活化邊表中各邊的下頂點；
步驟3.b：順序取出兩兩交點，交點之間的部分即為填充區域，其他部分為空洞區域；
步驟3.c：設置k＝1；
步驟3.d：判斷活化邊表中的各邊是否與yk依然存在交點，即判斷k<＝kmax。若成立，則依然存在交點，否則不再存在交點，將該邊從活化邊表中刪除；
步驟3.e：判斷是否有新的邊需要加入求交，即判斷第k類分類邊表是否為空。若不為空，則將該鍊表中的邊加入到當前活化面表；
步驟3.f：計算當前活化邊表中各邊與掃描線的交點。實際上只需在上一個交點的x坐標的基礎上增加d/m即可，即：xk＝xk-i+d/m。
步驟3.g：順序取出兩兩交點，交點之間的部分即為填充區域，其他部分為空洞區域；
步驟3.i：設置k＝k+1；
步驟3.h，重複步驟3.d到3.g，直到分類邊表及活化邊表中的邊均為空。
有益效果
本發明的用於3d列印切片的快速生成方法，通過對三角網格中的三角面片根據其最小z值進行分類，構建分類三角面片鍊表，減少判斷三角面片與切片平面是否有交的次數，從而提高了切片中輪廓線的生成效率。基於生成的切片輪廓線，結合二維多邊形掃描線填充算法，快速判斷輪廓線之間的填充區域與空洞區域，減少多邊形內外的判斷，從而提高切片中列印路徑生成的效率。因此，該發明方法可降低生成3d列印切片的時間複雜度與實現複雜度，提高3d列印切片的生成效率。
附圖說明
圖1為分類面表的結構示意圖。
圖2為分類邊表的結構示意圖。
圖3為生成3d列印切片的算法流程圖。
具體實施方式
下面結合附圖對本發明進一步說明。
如圖3所示，3d列印切片的快速生成分為三個步驟：三維網格的預處理、切片輪廓線的生成與切片中列印路徑的生成。
輸入一個三維模型，首先對其進行方向調整並計算其包圍盒，以確定三維模型的列印範圍，切片層數以及掃描線的條數。
而後針對每個切片平面，計算三維模型與切片平面相交的輪廓線。其具體步驟包括：
步驟1：根據3d列印的層厚設置d，以及預處理中確定的列印範圍[zb,zt]，確定列印的切片層數n＝(zt-zb)/d；
步驟2：將三角網格中的各個三角面片按三個頂點中的最小z值zmin進行分類，構建分類分類面表。
步驟3：自底向上遍歷所有的切片平面zk＝zb+kd，計算切片平面與三角面片的交點。根據三角面片的鄰接關係，將交點連接形成輪廓線。
基於切片得到的輪廓線，最後確定哪些區域為填充區域，哪些區域為空洞區域，並對填充區域利用掃描線填充算法進行填充。其具體步驟包括：
步驟1：根據印表機在y軸方向的精度d以及預處理過程中得到的y方向的列印範圍[yb,yt]，確定掃描線的條數n＝(yt-yb)/d；
步驟2：將切片輪廓線中的各邊按兩個頂點中的最小y值ymin進行分類，構建分類邊表。由於掃描線每次移動d，掃描線與邊的交點的x值只會變化一個常數d/m，因此可預先計算該值並保存在分類邊表中。
步驟3：自底向上遍歷所有的掃描線yk＝yb+kd，計算掃描線與各邊的交點。順序取出兩兩交點，交點之間的部分即為填充區域，其他部分為空洞區域。