1　引　言

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

STL文件是CAD實體數(shù)據(jù)模型經(jīng)三角化網(wǎng)格化處理后的數(shù)據(jù)文件，是用許多空間三角形小平面逼近原CAD實體模型，因為STL文件格式簡單而且不需要復(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)用，但是其缺點也是十分明顯的，例如缺少三角面片之間的拓撲信息，而且還會有裂縫、間隙、面片重疊和法向量反轉(zhuǎn)的錯誤[2]。由于STL文件所固有的缺陷，使得切片之后得到的輪廓信息有大量的冗余數(shù)據(jù)，甚至?xí)a(chǎn)生輪廓線不封閉等錯誤。如果我們不對這些冗余數(shù)據(jù)和錯誤不加以處理，就很難進行以后光斑的半徑補償?shù)纫院髷?shù)據(jù)處理，影響零件加工的穩(wěn)定性和加工效率，甚至不能成型正確的零件形狀。因此對截面輪廓數(shù)據(jù)進行優(yōu)化處理就顯得十分的必要。

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

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

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

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

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

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

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

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

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

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

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

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

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

3　輪廓信息錯誤的修正算法

3.1　錯誤的輪廓信息

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

如圖2所示，在某個層面進行切片時，由于孔洞，造成的不封閉，程序中將其強制閉合的情況。

圖2　不封閉截面輪廓的強制閉合

3.2　錯誤輪廓信息的修正算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

成立，則可以去掉點A。

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

當(dāng)滿足公式(2)時，因為取值很小，所以|PA|、|PB和sin∠APB中至少有一個值很小，此時，A點為重合點或者PAB在同一條直線上，也有可能三角形PAB十分微小，以至于小于加工精度，可以將A點去除。

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

圖6　多個重合點刪除的情況

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

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

5　截面輪廓內(nèi)外邊界的自動識別

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

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

由定義可知，多邊形的特征點可定時多邊形的凸頂點，通過特征點可以判斷輪廓多邊形的走向。如圖7所示，Vi為多邊形的特征點，是凸頂點，可通過計算Vi點鄰近的兩條邊的矢量積，來判斷多邊形為順時針還是逆時針。

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

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

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

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

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

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

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

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

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

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

6　結(jié)　論

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