層次多叉樹映射布爾體廓后驗(yàn)誤差的自適應(yīng)層切

郭洪帥，張樹有，伊國棟，劉曉健,2，譚建榮

(1.浙江大學(xué) 流體動力基礎(chǔ)件與機(jī)電系統(tǒng)全國重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310027；2.浙江大學(xué) 寧波科創(chuàng)中心，浙江 寧波，315100)

在給定構(gòu)建方向的情況下，不同的層厚設(shè)計對熔融沉積成型零件模型的打印精度和性能有重要影響[1].層切設(shè)計方法將零件模型分割成連續(xù)的2D 輪廓序列，通過輪廓層次關(guān)系判斷規(guī)劃打印路徑軌跡.合理的層厚設(shè)計將大大減小由于逐層累計材料造成的階梯效應(yīng)[2]，提高模型的表面打印精度.此外，層切設(shè)計及輪廓層次關(guān)系是路徑規(guī)劃研究的基礎(chǔ)，是整個增材制造過程中必不可少的處理環(huán)節(jié).

層切算法根據(jù)層厚是否變化主要分為兩類：均勻?qū)雍窈妥赃m應(yīng)層厚.均勻?qū)雍袼惴ê唵?、使用廣泛，自適應(yīng)層厚算法制造的零件精度更高和構(gòu)建時間更短[3-4].階梯誤差與模型構(gòu)建方向和層厚直接相關(guān)，在構(gòu)建方向確定的情況下，自適應(yīng)層厚算法可以最大化減小模型在特征變化部位的層切厚度，減小階梯誤差對表面打印精度的影響，提高零件局部特征域的打印精度，尤其是對于復(fù)雜零件的制造，自適應(yīng)層厚算法相比均勻?qū)雍袼惴ǜ邇?yōu)勢[5].自適應(yīng)層厚算法通過分析模型的特征變化確定層厚變化部位[6].現(xiàn)有方法主要通過最小厚度切割或檢查尖銳特征點(diǎn)獲取模型幾何形狀變化區(qū)域，通過特定切面上的幾何形狀來評估局部變化偏差，當(dāng)偏差小于設(shè)定的閾值時執(zhí)行層厚設(shè)計策略.自適應(yīng)層厚算法需要大量的切面與模型的求交運(yùn)算，計算代價非常高，當(dāng)相鄰切片之間存在復(fù)雜幾何形狀時，評估誤差較大[7].

針對不同層厚對零件模型表面體積誤差的影響，本研究提出層次多叉樹映射布爾體廓后驗(yàn)誤差的自適應(yīng)層切方法.對零件模型重建拓?fù)浜筇崛∪我鈱虞喞h(huán)并計算內(nèi)核域，通過拓?fù)溆成渑袛噍喞h(huán)層次關(guān)系，根據(jù)輪廓環(huán)層次關(guān)系多叉樹映射體廓布爾運(yùn)算，設(shè)定層變閾值計算自適應(yīng)層厚，通過體廓后驗(yàn)誤差驗(yàn)證所提算法的有效性.

1 輪廓環(huán)層次關(guān)系計算

1.1 任意層閉合輪廓環(huán)集合提取

輪廓是3D 模型投影到2D 上最內(nèi)和最外邊線的集合[8]，零件模型（如孔類、分支類零件）的層切面內(nèi)不止一個輪廓，內(nèi)、外輪廓提供軌跡邊界及材料填充區(qū)域的準(zhǔn)確描述.在層切算法中，輪廓環(huán)Loop 是模型在指定層切面處閉合輪廓的有向多邊形表示，通過多邊形輪廓環(huán)表征模型各層切面內(nèi)的輪廓，可以減少輪廓頂點(diǎn)數(shù)目，提高計算效率.在層切面內(nèi)劃定零件模型打印區(qū)域，是層切設(shè)計的必要中間處理過程.軌跡規(guī)劃和噴頭補(bǔ)償過程均須計算輪廓偏移，而偏移算法通常需要計算輪廓多邊形而非結(jié)構(gòu)化的線段列表[9].

在原始網(wǎng)格模型中，任意面間的鄰接關(guān)系未知，建立零件模型的Rg-Tree[10]來提取指定層高的鄰接面集：給定任意層高z，所有與XOY平行的切平面Pz存在交點(diǎn)的面片定義為當(dāng)前層的層切面，根據(jù)Rg-Tree 中模型的拓?fù)潢P(guān)系依次匹配層切面中所有面鄰接關(guān)系，進(jìn)而確定當(dāng)前層輪廓.根據(jù)層厚計算輪廓層高zi，解析任意面fi的頂點(diǎn)及其法向，基于頂點(diǎn)在Z方向的最小值zmin、最大值zmax及層厚u確定fi所屬的層數(shù)ni，將fi存入列表.一般情況下，zmin、zmax并不恰好等于層高zi，即fi可能落在多個層切面內(nèi)，fi所屬的分層一般為[nmin]～[nmax]，其中nmin=zmin/u，nmax=zmax/u，[n]表示不小于n的最小整數(shù).

對于2D 閉合可定向的二維流形M，不存在退化面并且沒有自交或偽接觸，特別地，任意面間的交集要么是空，要么是兩者的一條邊或者一個頂點(diǎn)，因此Pz與M相交的面必是首尾相接的封閉面集.對于任意層封閉面集，基于Rg-Tree，從任意面fi依次匹配其鄰接面直至返回至fi，得到封閉面集Fi.設(shè)第i層數(shù)據(jù)共有m組輪廓面集即F={F1,···,Fm}，對F中面添加標(biāo)記，將fi存儲到Fi，基于Rg-Tree 查詢fi的未標(biāo)記鄰接面片fadj（同一層鄰接面不可能多于3 個），將fadj存入Fi完成一個輪廓的鄰接匹配；若閉合輪廓匹配完成后F中還有未標(biāo)記的面片，則匹配第2 個閉合輪廓直至所有未標(biāo)記面片標(biāo)記為空.

根據(jù)投影及相似關(guān)系，計算Pz與F的交點(diǎn)，并按照各面的鄰接順序排列所有交點(diǎn)，將F={F1,···,Fm}轉(zhuǎn)換為輪廓面集C={C1,···,Cm}.設(shè)Pz在Z向的坐標(biāo)為zi，將fi投影至XOY平面，利用相似關(guān)系計算交點(diǎn)在X及Y方向的坐標(biāo)值集合Ii={(x1,y1,zi),(x2,y2,zi),···,(xs,ys,zi)}.進(jìn)一步確定交點(diǎn)的先后順序，任意層高zi下，C中交點(diǎn)按照拓?fù)溧徑雨P(guān)系連接為首尾相連的多邊形.考慮任意Ci的集合Fi={f1,f2,···,fn}，若Pz穿過F，則s≤n（若穿過fi頂點(diǎn)，則s＜n）；如圖1(a)所示，輪廓在沒有穿過面片頂點(diǎn)的情況下，n=s.無論逆時針或者順時針連接交點(diǎn)建立多邊形，通過第2 個面片的交點(diǎn)順序唯一確定，否則多邊形輪廓因交點(diǎn)缺失而無法有效閉合.一般情況下，層厚的數(shù)量級很小，zi不會穿過面片頂點(diǎn)，本研究默認(rèn)Fi同Pz存在2 個交點(diǎn)（相鄰面片僅有1 個交點(diǎn)重合）.如圖1(b) 所示，以任意面片集合Fi為例，假設(shè)f1的交點(diǎn)為(v1,v2)，f2的交點(diǎn)為待定.如果插入v1、v2（其中f1的2 個點(diǎn)插入順序任意），第2 個面片的插入點(diǎn)可能會存在（a1，a2）或者（a2，a1），（b1，b2）或者（b2，b1）2 種情況，插入順序正確是偶然情況，比如插入點(diǎn)b，但是有可能插入錯誤的a，無論是哪種情況只能是其中之一.

圖1 輪廓交點(diǎn)有序連接Fig.1 Ordered connection of contour intersections

如圖2 所示為插入點(diǎn)分析圖，插入點(diǎn)順序判斷規(guī)則如下.1) |v1a1|≡0 或者|v1a2|≡0，為情況I：若|v1a1|≡0，第3 個點(diǎn)插入a2，否則插入a1，交點(diǎn)順序?yàn)槿鐖D2(a)的逆時針.2) |v2b1|≡0 或者|v2b2|≡0，為情況II：若|v2b1|≡0，第3 個點(diǎn)插入b2，否則插入b，交點(diǎn)順序?yàn)槿鐖D2(b)的順時針.3) 按照拓?fù)溧徑禹樞颍瑥牡? 個面片的2 個交點(diǎn)(vi+1,vi+2)開始，若|vivi+1|≡0，則插入vi+2,，否則插入vi+1.

圖2 插入點(diǎn)分析Fig.2 Analysis of insertion points

1.2 基于拓?fù)溆成涞妮喞h(huán)層次關(guān)系計算

層次關(guān)系判斷方法主要有射線法和坐標(biāo)極值法[11].射線法通過作平行于坐標(biāo)軸的射線判斷包含關(guān)系，需要大量的輔助射線并控制射線的間距；坐標(biāo)極值法效率高，但會出現(xiàn)凹點(diǎn)輪廓環(huán)誤判.本研究提出基于拓?fù)溆成浯_定輪廓環(huán)層次關(guān)系判別算法.通過內(nèi)核域計算，對內(nèi)核點(diǎn)連線同輪廓的交點(diǎn)作拓?fù)溆成?，根?jù)映射軸點(diǎn)的極值排序確定輪廓環(huán)層次關(guān)系，實(shí)現(xiàn)對應(yīng)輪廓層次關(guān)系的有效判斷.相比于射線法，所提方法只進(jìn)行1 次拓?fù)溆成浼纯膳袛鄬哟侮P(guān)系，不僅減少了線段與輪廓環(huán)求交次數(shù)，還降低了算法的計算量.

給定任意多邊形P，若P內(nèi)存在點(diǎn)o，使得對于P內(nèi)的任意點(diǎn)p的線段op完全位于P內(nèi)，則點(diǎn)o的軌跡為P的內(nèi)核域[12].如圖3 所示，陰影部分即為P的內(nèi)核域K，將K中的任意點(diǎn)k作為判斷輪廓環(huán)層次關(guān)系的輔助點(diǎn)，以k為起始點(diǎn)的射線與P有且僅有一個交點(diǎn).K由P的邊線裁切而成，K必定為凸多邊形.依次掃描多邊形P的頂點(diǎn)構(gòu)造凸多邊形序列{K1,K2,···,Kn-1}，其中Kn-1=K(P)為所求內(nèi)核域[12].根據(jù)P在坐標(biāo)軸上的最大值和最小值初始化矩形內(nèi)核域K，計算P所有頂點(diǎn)的凹凸性，以當(dāng)前點(diǎn)及其后繼點(diǎn)所構(gòu)成直線l判斷當(dāng)前點(diǎn)的前驅(qū)點(diǎn)Ppre在該直線的左邊或右邊.通過l將P分為2 個部分，選擇1 個部分作為臨時內(nèi)核處理并下個點(diǎn)：若當(dāng)前點(diǎn)為凸點(diǎn)，則選擇的核與Ppre方向相同；若當(dāng)前點(diǎn)為凹點(diǎn)，則選擇的核與Ppre方向相反，更新臨時核至所有點(diǎn)計算完畢并輸出內(nèi)核域K(P)頂點(diǎn)集合.對于凹點(diǎn)過多的輪廓環(huán)，以其中凹點(diǎn)計算輔助內(nèi)核點(diǎn).

圖3 輪廓環(huán)的內(nèi)核域計算Fig.3 Kernel region calculation of contour loop

對于存在厚度的實(shí)體模型，任意2 個輪廓環(huán)存在2 種層次關(guān)系：包含或相離.如圖4(a)所示，L1、L2、L3均為有序交點(diǎn)連接的復(fù)雜多邊形輪廓環(huán)，其中L1包含L2、L3，L2、L3相離.以L1、L2為例，分析任意2 個輪廓環(huán)層次關(guān)系.分別計算L1、L2，內(nèi)核點(diǎn)I1、I2及線段與L1、L2交點(diǎn)集合C（nc為交點(diǎn)個數(shù)）；依次判斷C內(nèi)所有點(diǎn)與L1的關(guān)系.若交點(diǎn)均在L1外，則兩環(huán)相離；若交點(diǎn)個數(shù)為0 或者存在的交點(diǎn)均在L1內(nèi)，則兩環(huán)為包含關(guān)系.根據(jù)交點(diǎn)個數(shù)nc進(jìn)行如下情況分析.1) 若nc≤1，則L2在L1內(nèi)部，即L2?L1，如圖4(b) 所示；若L2在L1外部，必有nc＞1，如圖4(c)所示，反之不一定成立.2) 當(dāng)nc＞1 時，對交點(diǎn)c∈C，采用拓?fù)溆成浞╗13]將所有交點(diǎn)橫坐標(biāo)映射至X軸，對C內(nèi)所有點(diǎn)按X分方向從小到大排序，以X方向上最小和最大的2 個點(diǎn)cmin、cmax作為判斷輔助點(diǎn)，依據(jù)點(diǎn)在多邊形內(nèi)外的判斷方法[14]，若cmin、cmax均在L1內(nèi)，則L2?L1，如圖5(a)所示；否則，L1與L2相離，如圖5(b)所示.

圖4 輪廓環(huán)層次關(guān)系（nc ≤1 ）Fig.4 Hierarchical relationship of contour loops (nc ≤1)

圖5 輪廓環(huán)層次關(guān)系（nc＞1）Fig.5 Hierarchical relationship of contour loops (nc＞1)

1.3 多實(shí)體的輪廓環(huán)層次關(guān)系計算

對所有的輪廓環(huán)分別計算最小外接矩形R，以面積最大矩形包圍的輪廓環(huán)LR作為基環(huán).無論是單實(shí)體還是多實(shí)體模型，基環(huán)一定是外輪廓環(huán).單實(shí)體基環(huán)只有一個，多實(shí)體基環(huán)個數(shù)則由實(shí)體個數(shù)決定，但LR必定是其中任意實(shí)體的基環(huán).如圖5(a)所示為單實(shí)體實(shí)例，所有的輪廓環(huán)只在一個最大的輪廓環(huán)L1內(nèi)部（均在基環(huán)內(nèi)部）.假定單實(shí)體內(nèi)包含n個輪廓環(huán)L1～Ln，L1～Ln的層次關(guān)系按算法 1 計算.

算法 1基于拓?fù)溆成涞妮喞h(huán)層次關(guān)系判斷

輸入：輪廓環(huán)L1～Ln

輸出：L1～Ln層次關(guān)系集合H

每個實(shí)體分別對應(yīng)1 個基環(huán)，根據(jù)基環(huán)數(shù)目可以判斷實(shí)體個數(shù).對于單實(shí)體，當(dāng)i=1 時，實(shí)際上是對L1與L2～Ln環(huán)作層次關(guān)系判斷；若存在與L1相離的環(huán)，則當(dāng)前層切面是多實(shí)體輪廓環(huán).如圖6 所示為多實(shí)體層切面的輪廓環(huán)L={L1,L2,L3,···,Ln}，假定L1為基環(huán)，從L中剔除L1及其內(nèi)部輪廓環(huán)后，依次判斷L中所有輪廓環(huán)同L1的位置關(guān)系：凡是與L1相離的LR為第2 個實(shí)體的基環(huán)，從L中剔除LR（假設(shè)為L2）及其內(nèi)部輪廓環(huán)，L中與L1～L2均相離的LR為第3 個實(shí)體的基環(huán)，依次類推.若存在m（m＞ 1）個基環(huán)，則將多實(shí)體分解為m個單實(shí)體，按照單實(shí)體判斷方式（算法 1）對m個基環(huán)內(nèi)所有輪廓環(huán)層次關(guān)系進(jìn)行判定.

圖6 多實(shí)體輪廓環(huán)層次關(guān)系Fig.6 Hierarchical relationships of multi-entity contour loops

輪廓環(huán)向判斷常用的方法主要有向面積法、格林公式法、網(wǎng)格法等[15]，基于輪廓環(huán)層次關(guān)系，采用有向面積法優(yōu)先確定基環(huán)環(huán)向，再依次判斷基環(huán)內(nèi)部輪廓環(huán)向.將當(dāng)前層所有輪廓環(huán)頂點(diǎn)及輪廓環(huán)起始點(diǎn)索引在程序中載入，初始化層次關(guān)系矩陣ML，分別記錄任意2 個輪廓環(huán)的層次關(guān)系，輪廓環(huán)層次關(guān)系及環(huán)向判斷的流程如圖7 所示.

圖7 輪廓環(huán)層次關(guān)系及環(huán)向判斷流程Fig.7 Judgment process of hierarchical relationship and direction for contour loops

2 層次關(guān)系多叉樹構(gòu)建

為了表達(dá)各層切面內(nèi)所有輪廓環(huán)的層次關(guān)系，基于輪廓環(huán)層次關(guān)系矩陣構(gòu)建多叉（N-ary）樹管理輪廓環(huán)層次關(guān)系，實(shí)現(xiàn)輪廓環(huán)層次化存儲、查詢與數(shù)據(jù)轉(zhuǎn)換.多叉樹中每個結(jié)點(diǎn)是獨(dú)立存儲的數(shù)據(jù)結(jié)構(gòu)，記錄1 個輪廓環(huán)（包括有序頂點(diǎn)集合、環(huán)向、索引key 值、布爾符號、面積等信息）及對其父、子結(jié)點(diǎn)的引用.其中第1 層只有1 個結(jié)點(diǎn)（即根結(jié)點(diǎn)Root），從第2 層開始，每個子結(jié)點(diǎn)包含1 個或者多個子結(jié)點(diǎn)，根據(jù)對輪廓環(huán)層次關(guān)系及環(huán)向的研究需要，層次多叉樹的成員屬性及其結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的定義如圖8 所示.

圖8 層次多叉樹的數(shù)據(jù)結(jié)構(gòu)Fig.8 Data structure of N-ary tree

對于層次關(guān)系矩陣ML，元素L12=0 表示L1與L2相離，L12=1 表示L1包含L2，L12=-1 表示L2包含L1.根結(jié)點(diǎn)所在層為0，以每一層切面輪廓數(shù)據(jù)為基本單位，Loop 的環(huán)號為結(jié)點(diǎn)的索引值，層高h(yuǎn)用于確定布爾運(yùn)算符.根據(jù)ML依次插入各個Loop，若h為奇數(shù)，則Loop 布爾符號為正；若為偶數(shù)，則布爾符號為負(fù).N-ary 樹構(gòu)建完畢后所有Loop 的包含關(guān)系與之映射關(guān)系也唯一確定.任意Loop 的插入規(guī)則：對于待插入環(huán)Li，優(yōu)先處理存在包含關(guān)系的Loop，若Li與已插入的Loop 不存在包含關(guān)系，則Li必為根結(jié)點(diǎn)的子結(jié)點(diǎn)；若存在包含關(guān)系（包括多層嵌套包含關(guān)系），則在N-ary樹中必然屬于同一個分支.進(jìn)一步，已插入結(jié)點(diǎn)的Loop，對存在包含關(guān)系的Loop 結(jié)點(diǎn)進(jìn)行判斷，多層嵌套包含（單層也適用）關(guān)系下，Li必然存在于不存在子結(jié)點(diǎn)的結(jié)點(diǎn)Lc下，通過該條件可以判定插入位置Lc.確定插入位置后仍然需要判斷Li與插入結(jié)點(diǎn)處的Lc是包含還是被包含關(guān)系，利用多叉樹的子函數(shù)add 和insert_node 插入Li，即如果是包含關(guān)系，Li作為子結(jié)點(diǎn)用add 函數(shù)，如果是被包含關(guān)系，Li作為Lc父結(jié)點(diǎn)用insert_node 函數(shù)插入，須注意Loop 下標(biāo)的對應(yīng)關(guān)系及其插入位置.層次關(guān)系樹構(gòu)建算法的核心是新結(jié)點(diǎn)的插入位置判斷.根據(jù)層次關(guān)系建立對應(yīng)層高父子結(jié)點(diǎn)的映射關(guān)系，N-ary 樹的構(gòu)建如算法 2 所示.算法中，函數(shù)T.add_node()表示以當(dāng)前結(jié)點(diǎn)cur_node 作為父結(jié)點(diǎn)插入子結(jié)點(diǎn)node_i，函數(shù)T.insert_node()表示以當(dāng)前結(jié)點(diǎn)cur_node 作為子結(jié)點(diǎn)插入父結(jié)點(diǎn)node_i.N-ary 樹中，同一層次Loop 方向相同，存在層次關(guān)系的2 個Loop 的方向必定相反，如果基環(huán)的環(huán)向給定，則其他輪廓環(huán)向隨之確定.

算法 2基于輪廓環(huán)層次關(guān)系構(gòu)建多叉樹

3 布爾體廓后驗(yàn)誤差估計的自適應(yīng)層切

3.1 布爾體廓關(guān)聯(lián)自適應(yīng)層厚

將輪廓環(huán)層次關(guān)系映射為樹高，作為層厚變化系數(shù)實(shí)現(xiàn)自適應(yīng)層切.對模型M進(jìn)行均勻?qū)忧蓄A(yù)處理，沿構(gòu)建方向d以層厚u均勻?qū)忧校僭O(shè)在d下M的最大高度為hmax，最小高度為hmin，則打印層數(shù)LN=(hmax-hmin)/u，令mi為hi下輪廓環(huán)集合的數(shù)目.定義體廓為Li在u下的布爾體積，計算式為

式中：(-1)j為布爾運(yùn)算符號，j為Li所在N-ary 樹中的樹高，hN為樹的最大高度，為Li內(nèi)多邊形輪廓的面積，假設(shè),(x2,y2),···,(xr,yr)}，

式中：xn+1=x1;yn+1=y1;s=1,2,···,r.定義相鄰兩層的體廓變化量為

確定模型M在層高h(yuǎn)i處的細(xì)節(jié)特征變化情況，若體廓變化量超過一定的閾值，則該部位可能為需要減小層厚u的位置.即便A(Li)與A(Li+1)相近，但的形狀可能存在差異.假設(shè)Li、Li+1包含輪廓數(shù)相同，定義相鄰兩層環(huán)長變化量為

作為判斷打印層細(xì)節(jié)特征的參考量，Len(Loop)表示輪廓環(huán)長.環(huán)數(shù)mi作為每層判斷實(shí)體子特征數(shù)，定義環(huán)數(shù)變化量為

式中：wV,wL,wm為權(quán)重因子（wL＜wV＜wm＜0.5 ），用于確定體廓特征的參考比重.在自適應(yīng)層切的參數(shù)設(shè)計中，層厚u默認(rèn)為t0，其中0.01＜t＜1.00.從第2 層開始，依次計算相鄰兩層的切片數(shù)據(jù)并計算（ρ 為層變閾值），則無需改變切片厚度；否則應(yīng)減小層厚.層厚ti（i＞1）的計算式為

3.2 體廓后驗(yàn)誤差估計

基于牙尖高度（cusp height）的體積誤差計算方法[16]，無法計算存在輪廓環(huán)層次關(guān)系的任意層體積誤差.為了精確計算自適應(yīng)層切的逐層體積誤差，提出體廓后驗(yàn)誤差估計方法.后驗(yàn)誤差是模型層切后，在輪廓環(huán)層次關(guān)系已知的情況下求得模型的層切體積誤差，而牙尖高度法根據(jù)層厚直接計算（不需要層切數(shù)據(jù)）層切體積誤差.

基于N-ary 樹對輪廓環(huán)層次關(guān)系的映射關(guān)系，計算當(dāng)前層的切片的體廓作為實(shí)際體積Vr，如圖9所示.根據(jù)微積分基本定理，只要u→0，當(dāng)前層體積即為所有微分打印層的體積之和，表達(dá)式為

圖9 布爾體廓計算體積誤差Fig.9 Volume error calculation by Boolean volume contour

進(jìn)一步減小層厚（u＜0.01 mm），將微分后的體廓之和近似為該層的理論體積Vc，定義當(dāng)前層的體積誤差Ve為

式中：Vr由式(1)計算得到.假設(shè)當(dāng)前層厚為u，若減小層厚為w，則將理論體積Vc近似表示為

式中：切片體積vci由式(1)計算得到，[u/w]表示不大于[u/w]的最大整數(shù).若對整個模型按照w層切，按照式(10)計算任意多連通域的復(fù)雜模型體積.通過定義體廓誤差計算模型特征變化部位的局部體積誤差，驗(yàn)證所提方法的有效性.與牙尖高度法相比，采用體廓后驗(yàn)誤差計算方法，可以更加精確地計算每一層體積誤差，有助于驗(yàn)證在體廓特征部位的層切結(jié)果，使特征部位的層厚更合理且體積誤差更小.

如圖10 所示為基于體廓后驗(yàn)誤差的自適應(yīng)層切設(shè)計流程.通過預(yù)層切及Rg-Tree 的拓?fù)潢P(guān)系，確定各層切面內(nèi)所有輪廓環(huán)的層次關(guān)系，根據(jù)N-ary 樹進(jìn)行層次關(guān)系的映射轉(zhuǎn)換，通過布爾運(yùn)算計算當(dāng)前層輪廓環(huán)數(shù)據(jù)的自適應(yīng)層變系數(shù)，得到模型的自適應(yīng)層切高度，通過控制層厚閾值，基于布爾體廓計算各層的后驗(yàn)體積誤差，驗(yàn)證所提自適應(yīng)層切方法的有效性.

圖10 自適應(yīng)層切流程圖Fig.10 Flowchart of adaptive slice

4 實(shí)例驗(yàn)證

采用如圖11 所示的飛行器傳感器支架模型測試輪廓環(huán)層次關(guān)系計算、層次關(guān)系多叉樹構(gòu)建、自適應(yīng)層切及體廓后驗(yàn)誤差計算等方法.該模型包含多孔、多分支子特征，對輪廓環(huán)層次關(guān)系的測試具有很強(qiáng)的針對性，曲面特征適用于自適應(yīng)層切方法的驗(yàn)證.測試環(huán)境為Ubuntu 20.04，實(shí)現(xiàn)語言為Python 3.8.10，層切模型可視化及渲染采用VTK 9.2.2 實(shí)現(xiàn).

圖11 測試模型及網(wǎng)格結(jié)構(gòu)Fig.11 Test model with mesh structure

4.1 任意層切面內(nèi)輪廓環(huán)層次關(guān)系及環(huán)向計算

對網(wǎng)絡(luò)模型構(gòu)建Rg-Tree，選擇層切面輪廓最為復(fù)雜的構(gòu)建方向測試模型各個層切面內(nèi)輪廓環(huán)的層次關(guān)系.取構(gòu)建方向d為(-1,0,0)，層厚u=8.901 mm，進(jìn)行輪廓環(huán)層次關(guān)系測試.由Rg-Tree提取網(wǎng)格任意層的拓?fù)溧徑用嫫?，如圖12(a) 所示.其中第7 層切片共277 個鄰接面片，4 個輪廓的面片依次為100-55-59-63，切片高度x7=9.394 mm；第10 層切片共438 個鄰接面片，8 個輪廓的面片依次為42-39-68-73-69-66-41-40，切片高度為x10=36.098 mm.

圖12 任意輪廓面片集合提取Fig.12 Extraction of arbitrary contour facet set

分別計算模型在層高x7、x10下的層切面同各個面片的交點(diǎn)如圖13 所示.根據(jù)Rg-Tree 實(shí)現(xiàn)模型任意層Loop 拓?fù)渲亟?在VTK 的渲染下，將第7 層和第10 層輪廓同層切面的交點(diǎn)依次連接形成有序閉合Loop 并繪制輪廓環(huán)如圖14(a)所示.標(biāo)記第7 層和第10 層的多邊形輪廓面片索引號如圖14(b)所示.根據(jù)輪廓層切數(shù)據(jù)分別計算各層輪廓面積AL、周長LL和環(huán)數(shù)NL（數(shù)值歸一化處理）如圖15 所示，其中第6 層僅有1 個輪廓，但是該層輪廓多邊形的面積最大.

圖13 輪廓交點(diǎn)計算Fig.13 Intersection calculation of contours

圖14 輪廓拓?fù)渲亟懊嫫饕朏ig.14 Topology reconstruction of contour with facet index

圖15 層切可視化及各層輪廓環(huán)數(shù)據(jù)Fig.15 Slice visualization and contour loop data of each layer

4.2 層次多叉樹映射體廓布爾運(yùn)算

對第7 層和第10 層的所有輪廓環(huán)計算層次關(guān)系并計算環(huán)向，如圖16 所示.第7 層共4 個輪廓環(huán)，L1～L4均為基環(huán)且互為相離關(guān)系，如圖16(a)所示.第10 層共8 個輪廓環(huán)，L3、L4、L5、L6為基環(huán)；且L3包含L1，L4包含L7，L5包含L8，L6包含L2，如圖16(b)所示.第10 層8 個Loop 輸出層次關(guān)系如表1 所示.表中，0 表示兩個輪廓環(huán)是相離關(guān)系，1 表示包含關(guān)系，-1 表示被包含關(guān)系，+表示正向（逆時針），-表示反向（順時針），=表示自身輪廓環(huán).由輪廓環(huán)層次關(guān)系，構(gòu)建第10 層輪廓N-ary 樹，將8 個輪廓根據(jù)面積大小順序依次插入樹中，映射層次關(guān)系為樹的高度，通過廣度優(yōu)先遍歷所有結(jié)點(diǎn)，以P、C、D、A、L分別表示父結(jié)點(diǎn)、子結(jié)點(diǎn)、環(huán)向、面積、周長，輸出各結(jié)點(diǎn)如表2 所示.10 層N-ary 樹結(jié)構(gòu)如圖17 所示，各層的Loop 結(jié)點(diǎn)序號表示按面積倒序插入.

表1 第10 層輪廓環(huán)層次關(guān)系Tab.1 Hierarchical relationship of 10th contour loops

表2 第10 層輪廓構(gòu)建層次多叉樹結(jié)點(diǎn)信息Tab.2 N-ary tree node information of 10th slice contour

圖16 輪廓環(huán)層次關(guān)系判斷Fig.16 Hierarchical relationship judgment of contour loops

4.3 體廓后驗(yàn)誤差的自適應(yīng)層切及打印

通過層次多叉樹，以層變系數(shù) Φ 映射模型的層厚變化，計算自適應(yīng)層高.為了提高對特征部位的計算精度，取10 組權(quán)重系數(shù)(wV、wL、wm)進(jìn)行測試，權(quán)重參數(shù)列表為([0.5,0.2,0.3],[0.5,0.3,0.2],[0.4,0.3,0.3],[0.3,0.4,0.3],[0.2,0.2,0.6],[0.3,0.3,0.4],[0.3,0.5,0.2],[0.2,0.5,0.3],[0.3,0.2,0.5],[0.2,0.3,0.5]).設(shè)置切片基數(shù)為30，閾值取0.1，通過切片、任意層拓?fù)銵oop 判斷、N-ary 樹映射層厚分別計算相鄰層的層變系數(shù)，如圖18 所示.盡管權(quán)重取值不同，但每組權(quán)值層變系數(shù)曲線反映的變化趨勢大致相同，只是變化幅度有所區(qū)別，根據(jù)層變系數(shù)曲線精確計算體廓特征區(qū)域如17 層（層高為0 mm）.

圖18 層變系數(shù)變化趨勢Fig.18 Trend of slice change coefficient

如圖19 所示，選取權(quán)值wV=0.3、wL=0.2、wm=0.5，采用閾值 ρ 分別為0.3、0.2、0.1 測試自適應(yīng)層切，以均勻?qū)雍駥忧?0 層作為對比.自適應(yīng)層切在滿足閾值的情況下，隨著閾值系數(shù)的減小，模型整體打印層數(shù)增加，層數(shù)分別為17、21、33，在模型左側(cè)、中間過渡部位（層高為0 mm）以及右側(cè)分支特征部位的層數(shù)逐漸增大，層厚顯著減小.相比于均勻?qū)忧?，根?jù)模型特征變化的自適應(yīng)層厚設(shè)計更加合理.

圖19 不同閾值的自適應(yīng)層切與均勻?qū)忧袑Ρ菷ig.19 Comparison between adaptive slice and uniform slice by different thresholds

根據(jù)所提出的體廓誤差計算方法及式(9)，分別計算不同閾值下各層體積誤差，結(jié)果對比如圖20所示.圖中，h為層高.當(dāng) ρ=0.3 時，打印層數(shù)為17，層高依次為[43.986,38.051,32.117,26.183,20.248,14.314,8.380,2.445,3.489,4.973,6.456,12.391,18.325,24.259,30.194,36.128,42.063]，體積誤差為26.582 mm3.當(dāng) ρ=0.2 時，打印層數(shù)為21，層高依次為[43.986,42.502,41.019,38.051,36.568,35.084,29.150,23.216,17.281,11.347,5.412,0.522,3.489,4.973,6.456,12.391,18.325,24.259,30.194,36.128,42.063]，體積誤差為17.294 mm3.當(dāng) ρ=0.1 時，打印層數(shù)為33，層高依次為[43.986,42.502,41.019,38.051,36.568,35.084,33.601,32.117,26.183,20.248,14.314,8.380,2.445,0.962,0.522,3.489,4.973,6.456,9.423,10.907,12.391,13.874,15.358,21.292,22.776,24.259,27.227,28.710,30.194,33.161,34.645,36.128,42.063]，體積誤差為13.322 mm3.當(dāng)采用均勻?qū)雍駥忧?7、21、33 層時，層厚分別為5.236、4.239、2.698 mm，體積誤差分別為30.873、20.593、15.612 mm3.可以看出，在層數(shù)相同的情況下，采自適應(yīng)層切整體體積誤差比均勻?qū)忧懈。謩e減少了13.899%、16.019%、14.668%，并且在層變系數(shù)最大處的區(qū)域的體積誤差顯著減小.取閾值為0.2 的自適應(yīng)層切21 層作為權(quán)值參數(shù)的最終選擇（0.3,0.3,0.2,0.5），可以看出，與均勻?qū)忧?0 層相比，21 層自適應(yīng)層切在整體體積誤差不增加的情況下（Ve=17.752、17.294 mm3），有效減少了分層數(shù)目.

圖20 不同閾值的體廓后驗(yàn)誤差對比Fig.20 Comparison of posterior error based on volume contour by different thresholds

在局部特征位置區(qū)域體積誤差對比中，當(dāng)閾值 ρ=0.3 時，層高0 mm 附近處體積誤差顯著減小；當(dāng) ρ=0.2 時，層高-40、0 mm 附近處體積誤差顯著減小；當(dāng) ρ=0.1 時，層高-40、0、25 mm 附近處體積誤差顯著減小.對于所提出的布爾體廓后驗(yàn)誤差計算方法，對模型采用不同的層厚：10.000、8.902、7.300、5.236、4.239、2.967、2.689、1.780、0.890、0.100、0.010 層切并計算體積誤差，同時基于牙尖高度采用不同的層厚：10.000、8.000、5.000、4.000、2.000、1.000、0.800、0.500、0.100、0.050、0.010、0.001 層切并計算體積誤差，結(jié)果如圖21 所示.可以看出，基于牙尖高度受層厚影響非常大，所提方法對層厚不敏感，基于體廓微分在采用數(shù)量級1 mm 計算的體積誤差與基于牙尖高度采用0.01 mm 計算的體積誤差相當(dāng)，隨著層厚的增加，體積誤差變化波動非常小.

圖21 不同方法體積誤差收斂驗(yàn)證對比Fig.21 Volume error convergence verification comparison of different methods

當(dāng)采用更小的層厚（u=0.017 8 mm），各層體積誤差如圖22 所示，模型的體積誤差為6.348 mm3.當(dāng)u＜0.001 mm 時，可以準(zhǔn)確計算模型的體積；取u=0.001 mm，采用所提出方法計算模型各層切片的體積之和（模型體積）為47 831.829 mm3.作為對比，采用SolidWorks 和開源Trimesh 方法計算模型體積，分別為47 865.134、47 986.257 mm3.采用的層厚越小，計算精度越高，所提方法在0.001 mm即可達(dá)到SolidWorks、Trimesh 的計算精度.因此，采用式(9)通過體廓估算每層體積誤差是有效的.

圖22 基于布爾體廓計算5 000 層體積誤差Fig.22 Volume error of 5 000 layers calculated based on Boolean volume contour

采用3 組自適應(yīng)層厚策略，對比相對體積誤差法[17]、B 樣條插值法[18]中的自適應(yīng)層切算法和所提算法的打印實(shí)例，打印結(jié)果如圖23 所示.圖中，模型a、b、c 為相對體積誤差法[17]的打印實(shí)例，模型d、e、f 為B 樣條插值法[18]的打印實(shí)例，模型g、h、j 為所提算法的打印實(shí)例.分別對圖23中各模型的3 個區(qū)域進(jìn)行局部細(xì)節(jié)放大，初始層厚均設(shè)置為0.2 mm，對比結(jié)果如圖24 所示.在不同層厚范圍下，采用相對體積誤差法、B 樣條插值法以及所提算法對圖24 中的模型進(jìn)行層切，對比不同算法運(yùn)行的層切時間ts，結(jié)果如表3 所示.在層厚范圍變化更大的情況下（0.50u～2.00u），所提算法在判斷輪廓環(huán)層次關(guān)系方面更具優(yōu)勢，算法程序運(yùn)行最少；隨著層厚進(jìn)一步減?。?.25u～0.80u），當(dāng)構(gòu)建輪廓環(huán)層次關(guān)系多叉樹時，由于插入大量數(shù)據(jù)結(jié)點(diǎn)導(dǎo)致效率降低，雖然運(yùn)行時間有所提高，但跟其他2 種算法相差不大.

表3 不同層切方法的運(yùn)行時間對比Tab.3 Running time comparison of different slice algorithms

圖23 不同層切方法的實(shí)例打印結(jié)果Fig.23 Printing example of different slice methods

圖24 不同自適應(yīng)層厚局部放大細(xì)節(jié)對比結(jié)果Fig.24 Comparison results of local amplification details with different adaptive slice thicknesses

根據(jù)體廓誤差計算方法，在層厚為0.2 mm 的情況下，基于不同自適應(yīng)層厚系數(shù)采用均勻?qū)忧?、相對體積誤差法、B 樣條插值法以及所提算法對模型層切，分別對比圖24 中3 個采樣區(qū)域（I、II、III）的體積誤差、平均誤差、模型的整體體積誤差Vew以及總體層數(shù)，結(jié)果如表4 所示.可以看出，所提算法在體積誤差不增加的情況下，總體層數(shù)顯著減少；通過自適應(yīng)減小特征部位層厚，體積誤差進(jìn)一步減小（圖24(c)）；如果層厚系數(shù)設(shè)置過大導(dǎo)致層數(shù)過少，會增大局部區(qū)域體積誤差以及整體體積誤差（圖24(a)）.通過SopTop金相電鏡MX-6R 對圖24(c)中f-I、f-II、f-III、i-I、i-II、i-III 測量表面微觀形貌特征如圖25 所示.可以看出，所提算法在實(shí)現(xiàn)有效自適應(yīng)層切的情況下，I、II 特征部位處的成型精度更高.

表4 不同方法的自適應(yīng)層切結(jié)果實(shí)例對比Tab.4 Adaptive layering results comparison of different methods

圖25 金相電鏡實(shí)驗(yàn)測量微觀形貌特征Fig.25 Experiments measure of microscopic morphological features by metallographic electron microscopy

5 結(jié)語

針對構(gòu)建方向確定后的層切算法進(jìn)行研究，提出層次多叉樹映射布爾體廓后驗(yàn)誤差的自適應(yīng)層切方法，在整體模型體積誤差不增大的情況下減小了體廓特征部位的體積誤差，提高了表面成型精度.1) 基于Rg-Tree 局部拓?fù)漭喞亟ǚ椒?，獲取任意層切片中的閉合輪廓環(huán)，采用拓?fù)溆成浞椒▽⑤喞h(huán)映射至一維坐標(biāo)軸，根據(jù)極值排序?qū)喞h(huán)層次關(guān)系進(jìn)行有效判斷.2) 構(gòu)建層次關(guān)系多叉樹，將樹高映射體廓的布爾運(yùn)算，根據(jù)相鄰層的層變系數(shù)與層厚閾值的關(guān)系計算自適應(yīng)層高，減小了體廓特征部位的體積誤差，提高了表面成型精度.3) 提出體廓后驗(yàn)誤差估計方法，相比于基于牙尖高度體積誤差計算方法，所提方法對層厚不敏感，計算的體積誤差精度更高.復(fù)雜模型的輪廓環(huán)層次關(guān)系判斷會增加多叉樹的構(gòu)建時間，下一步將采用GPU 加速方法，實(shí)現(xiàn)輪廓環(huán)關(guān)系判斷的并行運(yùn)算，提高算法運(yùn)行效率.