1　引　言

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

STL文件是CAD實體數據模型經三角化網格化處理后的數據文件，是用許多空間三角形小平面逼近原CAD實體模型，因為STL文件格式簡單而且不需要復雜的CAD系統支持，現在已經發展成為CAD系統與快速成型系統之間數據交換格式的不成文標準。盡管STL文件在快速成型領域有著極其廣泛的應用，但是其缺點也是十分明顯的，例如缺少三角面片之間的拓撲信息，而且還會有裂縫、間隙、面片重疊和法向量反轉的錯誤[2]。由于STL文件所固有的缺陷，使得切片之后得到的輪廓信息有大量的冗余數據，甚至會產生輪廓線不封閉等錯誤。如果我們不對這些冗余數據和錯誤不加以處理，就很難進行以后光斑的半徑補償等以后數據處理，影響零件加工的穩定性和加工效率，甚至不能成型正確的零件形狀。因此對截面輪廓數據進行優化處理就顯得十分的必要。

2　切片輪廓數據的特性

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

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

ASCII格式的STL文件結構如下：

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

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

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

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

它們必須符合三條規則：

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

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

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

圖1　輪廓區域邊界的方向

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

3.1　錯誤的輪廓信息

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

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

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

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

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

鏈表的頭節點為：

struct Head
{
floatLayHeight；　　//該層輪廓的高度
boolInOrOut；//內外環標志，外環為0
boolHaveBug；//錯誤標志，輪廓有錯為1
DataPoint*Pointer；//指針　
}

數據節點為：

struct DataPoint
{
floatXdata，Ydata；//數據點的x，y坐標
boolHaveGap；//斷點標志
DataPoint*Pointer；//指針
}

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

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

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

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

4　輪廓信息冗余數據的濾除算法

4.1　輪廓信息冗余數據分析

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

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

圖4　輪廓信息冗余數據的產生

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

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

成立，則可以去掉點A。

圖5　冗余數據的去除方法

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

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

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

綜合上面提到的情況作者提出了相應的算法，由于本文將輪廓信息數據存放在循環鏈表中，對于刪除操作的執行效率較高。

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

5　截面輪廓內外邊界的自動識別

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

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

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

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

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

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

內外邊界識別的詳細算法描述如下：

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

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

Step3：判斷是否還有未作邊界標志的多邊形，若有，則轉Step2。

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

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

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

6　結　論

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