1　引　言

  快速成型技術(shù)(RapidPrototypingTechnology)是一種基于離散堆積成型思想的新型成形技術(shù)[1]，自80年代產(chǎn)生以來(lái)得到了迅速的發(fā)展。由于其具有生產(chǎn)的敏捷性、制造技術(shù)的高度集成化以及適合于制造幾乎任何形狀等的優(yōu)點(diǎn)廣泛應(yīng)用于機(jī)械、電子、汽車、玩具、通訊、航空航天等領(lǐng)域。其基本制造原理為：將CAD模型在計(jì)算機(jī)內(nèi)用切片軟件沿Z方向切片離散，得到一系列具有一定厚度的薄片，然后激光束(或紫外光束)在計(jì)算機(jī)的控制下在二維的切片層面上固化或粘結(jié)某一區(qū)域，從而形成零件實(shí)體的一個(gè)層面，隨后再同樣固化下一個(gè)層面，如此反復(fù)，逐漸堆積便形成一個(gè)三維零件。快速成形技術(shù)根據(jù)制造工藝的不同可以分為：疊層實(shí)體制造(LOM)、選擇形激光燒結(jié)(SLS)、光固化法(SL)、熔融沉積制造法(FDM)、三維立體印刷法(TDP)等。

STL文件是CAD實(shí)體數(shù)據(jù)模型經(jīng)三角化網(wǎng)格化處理后的數(shù)據(jù)文件，是用許多空間三角形小平面逼近原CAD實(shí)體模型，因?yàn)镾TL文件格式簡(jiǎn)單而且不需要復(fù)雜的CAD系統(tǒng)支持，現(xiàn)在已經(jīng)發(fā)展成為CAD系統(tǒng)與快速成型系統(tǒng)之間數(shù)據(jù)交換格式的不成文標(biāo)準(zhǔn)。盡管STL文件在快速成型領(lǐng)域有著極其廣泛的應(yīng)用，但是其缺點(diǎn)也是十分明顯的，例如缺少三角面片之間的拓?fù)湫畔ⅲ疫€會(huì)有裂縫、間隙、面片重疊和法向量反轉(zhuǎn)的錯(cuò)誤[2]。由于STL文件所固有的缺陷，使得切片之后得到的輪廓信息有大量的冗余數(shù)據(jù)，甚至?xí)a(chǎn)生輪廓線不封閉等錯(cuò)誤。如果我們不對(duì)這些冗余數(shù)據(jù)和錯(cuò)誤不加以處理，就很難進(jìn)行以后光斑的半徑補(bǔ)償?shù)纫院髷?shù)據(jù)處理，影響零件加工的穩(wěn)定性和加工效率，甚至不能成型正確的零件形狀。因此對(duì)截面輪廓數(shù)據(jù)進(jìn)行優(yōu)化處理就顯得十分的必要。

2　切片輪廓數(shù)據(jù)的特性

STL文件用許多空間小三角形來(lái)表示零件的表面，對(duì)每一個(gè)空間小三角形面片用三角形的三個(gè)頂點(diǎn)的坐標(biāo)及三角形面片的法向量來(lái)描述，法向量由零件的內(nèi)部指向外部，三角形三個(gè)頂點(diǎn)的次序與法向量滿足右手規(guī)則。

STL文件中每相鄰的兩個(gè)三角形只能有一條公共邊。STL文件有兩種格式，一種是ASCII格式，另一種是二進(jìn)制格式。ASCII格式的STL文件具有可讀性，但占用較大的空間，大約是二進(jìn)制STL文件的五倍。

ASCII格式的STL文件結(jié)構(gòu)如下：

solid ASCII　　　　　　　　　　　//ASCII為文件名
facet normal nx ny nz//三角形面片的法向量
　　outer loop
　　　　vertex V1xV1yV1z//頂點(diǎn)V1的坐標(biāo)
　　　　vertex V2xV2yV2z//頂點(diǎn)V2的坐標(biāo)
　　　　vertex V3xV3yV3z//頂點(diǎn)V3的坐標(biāo)
　　end loop
end facet

在快速成型技術(shù)中，對(duì)模型的切片過(guò)程實(shí)際上就是一個(gè)平面和平面求交的過(guò)程，也就是由平行于XOY的一系列平行平面和組成模型的三角面片求交的過(guò)程。實(shí)際上這個(gè)過(guò)程也可以認(rèn)為是直線和平面的求交，即組成三角形面片的三條邊和平行于XOY平面的求交。在這個(gè)過(guò)程中，首先選取切片平面(z=zi)，然后在STL文件中搜索與這個(gè)Z平面相交的所有三角面片，記錄下這樣的一個(gè)個(gè)交點(diǎn)，假如STL文件沒(méi)有錯(cuò)誤的話，就會(huì)得到一系列Z值不相同的封閉的截面輪廓多邊形。

STL切片之后的截面輪廓信息是指由一系列有序點(diǎn)集，順序連接構(gòu)成的多個(gè)折線。其中第i條折線的點(diǎn)集為：

Vi={v1，v2，…，vn}其中n為點(diǎn)數(shù)。

它們必須符合三條規(guī)則：

1這條折線應(yīng)該是簡(jiǎn)單的封閉的，構(gòu)成一個(gè)多邊形。不應(yīng)該存在自相交和不封閉的情況，自相交的情況很少出現(xiàn)，本文只對(duì)比較常見(jiàn)的輪廓不封閉給出了相應(yīng)的算法。

2vn是足以描述這條折線的最少的點(diǎn)。其中不應(yīng)該存在多余的數(shù)據(jù)點(diǎn)，本文對(duì)于冗余點(diǎn)的去除提出了一種有效的算法。

3切片之后得到多條封閉的折線形成的截面多邊形組成實(shí)體區(qū)域的邊界，必須對(duì)這些邊界識(shí)別并進(jìn)行方向性處理，其正向規(guī)定為：沿封閉折線前進(jìn)時(shí)，區(qū)域總保持在左側(cè)，如圖1所示。#p#分頁(yè)標(biāo)題#e#

圖1　輪廓區(qū)域邊界的方向

3　輪廓信息錯(cuò)誤的修正算法

3.1　錯(cuò)誤的輪廓信息

由于CAD系統(tǒng)的計(jì)算精度以及網(wǎng)格化功能的漏洞等問(wèn)題，會(huì)造成由CAD模型向STL模型轉(zhuǎn)化時(shí)，在大曲率曲面的交界處會(huì)出現(xiàn)孔洞等缺陷，這些缺陷的存在會(huì)導(dǎo)致切片后截面輪廓的不封閉。在實(shí)際的切片過(guò)程中，首先對(duì)STL文件建立鄰接關(guān)系的鏈表[3]，每一個(gè)小三角形面片都有三個(gè)鄰接的三角形面片，當(dāng)在某個(gè)層面切片時(shí)，先隨機(jī)地找到要切的第一個(gè)三角形，然后尋找這個(gè)三角形的鄰接三角形，找到的三角形如果在切片范圍內(nèi)，那么朝向這個(gè)方向進(jìn)行切片，每切一個(gè)三角形都是通過(guò)他的鄰接三角形進(jìn)行下一個(gè)切片，直到回到第一個(gè)被切的三角形。如果STL文件有孔洞，那么在孔洞周邊的小三角形就會(huì)只有兩個(gè)甚至只有一個(gè)鄰接三角形。在這種情況下，切片過(guò)程不會(huì)回到第一個(gè)被切的三角形，結(jié)果一條輪廓線被分成兩段甚至幾段。

如圖2所示，在某個(gè)層面進(jìn)行切片時(shí)，由于孔洞，造成的不封閉，程序中將其強(qiáng)制閉合的情況。

圖2　不封閉截面輪廓的強(qiáng)制閉合

3.2　錯(cuò)誤輪廓信息的修正算法

作者把切片得到的輪廓數(shù)據(jù)存放在循環(huán)鏈表中，如果同一截面有多個(gè)輪廓，它們每一個(gè)輪廓環(huán)用一個(gè)鏈表，盡管一條輪廓環(huán)可能由于錯(cuò)誤被分成了幾段。下面為鏈表的數(shù)據(jù)結(jié)構(gòu)。

鏈表的頭節(jié)點(diǎn)為：

struct Head
{
floatLayHeight；　　//該層輪廓的高度
boolInOrOut；//內(nèi)外環(huán)標(biāo)志，外環(huán)為0
boolHaveBug；//錯(cuò)誤標(biāo)志，輪廓有錯(cuò)為1
DataPoint*Pointer；//指針　
}

數(shù)據(jù)節(jié)點(diǎn)為：

struct DataPoint
{
floatXdata，Ydata；//數(shù)據(jù)點(diǎn)的x，y坐標(biāo)
boolHaveGap；//斷點(diǎn)標(biāo)志
DataPoint*Pointer；//指針
}

在本文中，如果輪廓不封閉，在頭節(jié)點(diǎn)置錯(cuò)誤標(biāo)志；在斷開(kāi)處，置數(shù)據(jù)節(jié)點(diǎn)的斷點(diǎn)標(biāo)志。如圖3所示截面輪廓不閉合，同一輪廓被分成了兩段輪廓線AB和AC，其輪廓信息數(shù)據(jù)都存放在同一個(gè)鏈表中，但是兩段輪廓線的走向可能不相同。斷開(kāi)點(diǎn)之間的距離一般十分接近，所以可以比較容易地將斷開(kāi)點(diǎn)連接上。

圖3　不封閉的截面輪廓及其修正

對(duì)于輪廓數(shù)據(jù)不封閉的修正算法具體步驟為：

(1)調(diào)入輪廓信息的鏈表，檢查頭節(jié)點(diǎn)的錯(cuò)誤標(biāo)志，如果該鏈表沒(méi)有錯(cuò)，調(diào)入新的鏈表；如果鏈表有錯(cuò)，進(jìn)入(2)。
(2)搜索鏈表各個(gè)節(jié)點(diǎn)的斷點(diǎn)標(biāo)志，找出所有斷開(kāi)點(diǎn)。
(3)計(jì)算各個(gè)斷開(kāi)點(diǎn)之間的距離，連接距離較近的斷開(kāi)點(diǎn)，并且修正各段輪廓線的方向。如圖3(a)所示，一個(gè)有錯(cuò)的切片輪廓沒(méi)有將其強(qiáng)制閉合的情況，圖3(b)為修正后的結(jié)果。

4　輪廓信息冗余數(shù)據(jù)的濾除算法

4.1　輪廓信息冗余數(shù)據(jù)分析

由于STL文件格式本身的特點(diǎn)，使得切片之后得到的截面輪廓信息有大量的冗余數(shù)據(jù)，這些冗余數(shù)據(jù)的存在，不僅影響以后的信息處理，如光斑的半徑補(bǔ)償[4]；而且影響最后對(duì)零件的加工，如對(duì)一條直線多次進(jìn)行插補(bǔ)，造成加工過(guò)程不穩(wěn)定，效率低下。

STL文件的粗糙程度與產(chǎn)生STL時(shí)CAD系統(tǒng)指定的毗鄰誤差有關(guān)，當(dāng)STL模型的毗鄰誤差較小時(shí)，用來(lái)近似零件表面的三角形面片數(shù)目較多，當(dāng)STL模型的毗鄰誤差較大時(shí)，用來(lái)近似零件表面的三角形面片數(shù)目較少。輪廓信息就是用一系列平行于XOY平面的截平面去截交STL模型，得到的STL模型在某個(gè)平面上截面的內(nèi)外輪廓環(huán)。在進(jìn)行零件加工時(shí)，激光或者其他的光源在掃描截面實(shí)體部分時(shí)，為了使零件更加光滑，減小粗糙度，還要進(jìn)行截面輪廓型的掃描。而當(dāng)STL模型的精度較高時(shí)，切片得到的輪廓環(huán)會(huì)有大量的細(xì)碎線段。同時(shí)在同一條直線段上還會(huì)存在多個(gè)數(shù)據(jù)點(diǎn)，以及在同一個(gè)數(shù)據(jù)點(diǎn)上有多個(gè)重合點(diǎn)的存在。如圖4所示，截交平面L1在切STL模型時(shí)在靠近頂點(diǎn)V1處，得到幾段相當(dāng)短小的線段；截交平面L2在切STL模型是剛好經(jīng)過(guò)頂點(diǎn)V2，在得到的輪廓信息中就會(huì)存在幾個(gè)坐標(biāo)完全相同的數(shù)據(jù)；截交平面L3在切STL模型時(shí)，由于小三角面F1、F2和F3在同一個(gè)平面上，在得到的輪廓信息中，直線段T1T4，還會(huì)存在冗余頂點(diǎn)數(shù)據(jù)T2和T3。#p#分頁(yè)標(biāo)題#e#

圖4　輪廓信息冗余數(shù)據(jù)的產(chǎn)生

在輪廓信息中的微小線段，在當(dāng)前的快速成型系統(tǒng)的精度下，根本無(wú)法插補(bǔ)加工，可以去除這些數(shù)據(jù)；重合點(diǎn)和同一條直線段的多余點(diǎn)的數(shù)據(jù)，應(yīng)該剔除。

|S|≤ Q，( Q為定義的誤差范圍)。(2)

成立，則可以去掉點(diǎn)A。

圖5　冗余數(shù)據(jù)的去除方法

當(dāng)滿足公式(2)時(shí)，因?yàn)槿≈岛苄。詜PA|、|PB和sin∠APB中至少有一個(gè)值很小，此時(shí)，A點(diǎn)為重合點(diǎn)或者PAB在同一條直線上，也有可能三角形PAB十分微小，以至于小于加工精度，可以將A點(diǎn)去除。

如果只使用上述算法中的公式(2)判斷進(jìn)行去除冗余數(shù)據(jù)時(shí)，如果遇到下面的情況時(shí)可能會(huì)產(chǎn)生錯(cuò)誤。如圖6a，b所示，ABCDE之間的距離相當(dāng)近，首先計(jì)算三角形PAB的面積，滿足公式(2)，刪除點(diǎn)A。同樣，隨后BCD相繼被刪除，最后只剩下E點(diǎn)，以PE代替PABCDE，這樣多次累計(jì)，可能造成較大的誤差。

圖6　多個(gè)重合點(diǎn)刪除的情況

綜合上面提到的情況作者提出了相應(yīng)的算法，由于本文將輪廓信息數(shù)據(jù)存放在循環(huán)鏈表中，對(duì)于刪除操作的執(zhí)行效率較高。

Step1：判斷三角形APB的面積是否滿足公式(2)，如果滿足，進(jìn)入Step2，否則轉(zhuǎn)向Step4
Step2：計(jì)算三角形APB的面積是否等于零，如果等于零，直接刪除A點(diǎn)，轉(zhuǎn)向Step4，否則進(jìn)入Step3。
Step3：計(jì)算線段AB的長(zhǎng)度，如果AB小于設(shè)定的值δ(即AB為微小線段)，再計(jì)算BC的長(zhǎng)度，如果BC小于δ，繼續(xù)計(jì)算接下來(lái)的線段的長(zhǎng)度，直到E點(diǎn)，刪除BCD點(diǎn)；如果AB小于δ，刪除A點(diǎn)。
Step4：調(diào)入新的輪廓信息數(shù)據(jù)，轉(zhuǎn)向Step1。
Step5：到達(dá)頭節(jié)點(diǎn)，結(jié)束。

5　截面輪廓內(nèi)外邊界的自動(dòng)識(shí)別

在STL模型切片之后，得到的是一系列截面輪廓多邊形，在每一個(gè)截面上，可能有多個(gè)輪廓多邊形，這些輪廓多邊形可能是實(shí)體的內(nèi)邊界也可能是實(shí)體的外邊界，有的可能含有多個(gè)外邊界和內(nèi)邊界[5]，為了隨后的數(shù)據(jù)處理能夠順利進(jìn)行，必須將這些截面輪廓的內(nèi)外邊界進(jìn)行識(shí)別，并使輪廓數(shù)據(jù)遵循外邊界逆時(shí)針、內(nèi)邊界順時(shí)針的規(guī)則。基于STL模型的切片輪廓邊界所具有的特點(diǎn)，本文提出一種簡(jiǎn)單的內(nèi)外邊界識(shí)別算法。

定義。輪廓多邊形的特征點(diǎn)是指在多邊形的所有頂點(diǎn)中，x坐標(biāo)值最大而y坐標(biāo)值相對(duì)較小的那個(gè)頂點(diǎn)。

由定義可知，多邊形的特征點(diǎn)可定時(shí)多邊形的凸頂點(diǎn)，通過(guò)特征點(diǎn)可以判斷輪廓多邊形的走向。如圖7所示，Vi為多邊形的特征點(diǎn)，是凸頂點(diǎn)，可通過(guò)計(jì)算Vi點(diǎn)鄰近的兩條邊的矢量積，來(lái)判斷多邊形為順時(shí)針還是逆時(shí)針。

　　s=Vi-1Vi×ViVi+1(3)

如果s大于零，則該多邊形為逆時(shí)針(如圖7(a)所示)，如果s小于零，則該多邊形為順時(shí)針(如圖7(b)所示)。

圖7　輪廓多邊形走向的判別方法

內(nèi)外邊界識(shí)別的詳細(xì)算法描述如下：

Step1：搜索截面的所有輪廓多邊形的x坐標(biāo)的極大值點(diǎn)、極小值點(diǎn)和y坐標(biāo)的極大值點(diǎn)、極小值點(diǎn)，這些點(diǎn)所在的多邊形一定為外邊界，并對(duì)這些多邊形作外邊界標(biāo)志。

Step2：取余下未作標(biāo)志的一個(gè)多邊形，找到特征點(diǎn)，從該點(diǎn)起沿x軸正向作射線，求此射線與所有多邊形的交點(diǎn)個(gè)數(shù)，若交點(diǎn)個(gè)數(shù)為奇數(shù)，則此多邊形為內(nèi)邊界，并作內(nèi)邊界標(biāo)志，若交點(diǎn)個(gè)數(shù)為偶數(shù)，則此多邊形為外邊界，并作外邊界標(biāo)志； #p#分頁(yè)標(biāo)題#e#

Step3：判斷是否還有未作邊界標(biāo)志的多邊形，若有，則轉(zhuǎn)Step2。

Step4：查找輪廓多邊形的特征點(diǎn)，根據(jù)公式(2)判斷多邊形的走向，如果為內(nèi)邊界，則將多邊形走向改為順時(shí)針，如為外邊界將其改為逆時(shí)針。

Step5：直到所有多邊形判別完畢，自動(dòng)識(shí)別結(jié)束。

算法首先要找出輪廓極限點(diǎn)與各多邊形的特征點(diǎn)，然后利用其位置的特殊性識(shí)別出一些內(nèi)外邊界，當(dāng)然，該識(shí)別算法的時(shí)間復(fù)雜度與截面輪廓中多邊形的個(gè)數(shù)和邊數(shù)有關(guān)。該算法是一個(gè)通用的算法，適合于截面輪廓含有一個(gè)或多個(gè)內(nèi)外邊界的情況。

6　結(jié)　論

(1)本文所述截面輪廓的錯(cuò)誤修正算法，對(duì)于截面輪廓不封閉的情況，能夠較好的進(jìn)行修正。
(2)通過(guò)對(duì)截面輪廓信息冗余數(shù)據(jù)的濾除，提高了后續(xù)的數(shù)據(jù)處理的速度，在不失掉加工精度的情況下，提高加工的穩(wěn)定性和效率。
(3)通過(guò)利用截面的輪廓極限點(diǎn)和各多邊形的特征點(diǎn)快速地識(shí)別出實(shí)體截面輪廓的內(nèi)外邊界，為快速成形技術(shù)中激光光斑半徑的實(shí)時(shí)自動(dòng)補(bǔ)償提供了必要的前提條件。本文的算法已經(jīng)應(yīng)用到紫外光固化快速成型系統(tǒng)中，實(shí)踐證明，效果較為理想。