王春香，郝志博，陳浩宏

(1.內蒙古科技大學機械學院，內蒙古包頭014010;2.包頭市萬佳信息工程有限公司，內蒙古包頭014010)

0 前言［1－8］

STL 格式的模型為大多數快速成型設備所接受，其分層算法的好與壞直接影響到快速型成技術的精度要求和制造效率，直接制約著零件的實用性和投產，因此快速成型技術的分層算法成為了研究熱點。

按照對三角形面片的信息利用方式的不同可以將三角形面片的分層算法分為以下3 類:

(1)基于三角形面片位置信息的分層算法。這種算法是按照三角形面片中的頂點坐標z 值的大小對STL 模型進行排序，將不同的三角形面片按照頂點z值坐標上的最小值和最大值從小到大進行分類排序，以便于減少三角形面片與分層切平面的位置判斷次數，提高分層的效率。但是分類排序過程中類的劃分十分模糊，不能完全杜絕位置關系無效判定;而且分層過程中類的劃分也十分耗時。

(2)基于三角形面片的拓撲信息的分層算法。該算法是根據三角形面頂點坐標依次建立點、線、面的鏈表或者根據平衡二叉樹對STL 模型建立整體的拓撲信息，使得相鄰的三角形面片之間具有毗鄰關系，當分層切平面與一個三角形面片相切時，便可以通過三角形面片的毗鄰關系依次查找出其他與該分層切平面相交的三角形面片，最后按順序輸出分層輪廓線。該方法的局限性在于對模型建立拓撲關系非常耗時，尤其在模型數據量較大時十分耗費內存資源。

(3)基于三角形面片的局部拓撲信息的分層算法。這種算法是針對上述兩種算法的改進，用以提高三角形面片的搜索效率。該算法首先建立一個三角形面片集，然后將與某一層分層切平面相交的三角形面片動態(tài)地儲存在該集合中，當分層切平面從上一層到下一層時，把不與該層相交的三角形面片從集合中剔除，將與該層相交的新三角形面片加入集合，然后對這些在集合中的三角形面片建立局部的拓撲關系，進行求交運算，最終輸出該層的輪廓線。該算法局限性在于集合中動態(tài)儲存三角形面片和局部拓撲關系的建立仍是比較費時的工作。

面向STL 模型的分層切片算法要求分層程序具有較高的穩(wěn)定性和時效性。本文作者提出一種基于三角形面片的排序精簡方法，提取只與分層切平面相交的三角形面片，提高了分層效率，尤其是在數據量較大的模型下，其高效性更為突出，而且經過多次驗證該算法具有較高的穩(wěn)定性。

1 算法的基本思想

該算法在總結分析以上優(yōu)點，得出以下的結論:基于三角形面片在分層方向上的最大值和最小值的不同，最小值小的先被切到，而最小值大的后被切到;當三角形面片的最小值大于該分層切平面的高度值或者當三角形面片的最大值小于該分層切平面的高度值時都不會與該分層切平面相交;相鄰的兩個分層切平面相交的三角形面片集合之間變化很小。依據這些原理，對STL 模型中的三角形面片進行剔除和排除，用以精簡數據，直接提取出只與分層截面相交的三角形面片，最后將分切層平面與每個三角面片進行求交運算，無需建立三角形面片之間的拓撲關系，直接輸出分層截面輪廓線。

2 算法實現(xiàn)的基本過程

應用MATLAB 軟件的強大矩陣邏輯運算功能，快速地實現(xiàn)了該算法。該算法具體實現(xiàn)過程如下:

2.1 數據的讀取

由于STL 模型數據是由字符串與數值混合在一起，所以必須對模型中每一個三角形面片的3 個頂點坐標以及三角形面片法向量坐標進行提取。通過整行讀取的形式對STL 模型數值數據進行提取，即對STL模型中的數據一行一行讀取，然后采用不同限定條件對模型中三角形面片數據中的頂點坐標和法向量坐標分別提取，最終用兩個矩陣分別對應表示出所有三角形頂點坐標以及向量坐標。其表示形式如下:

datatri= ［v1x v1y v1z;v2x v2y v2z;v3x v3y v3z;…］

datan= ［ni nj nk;…］

其中“;”代表每一行的分隔符，“datatri”代表三角形面片頂點坐標矩陣，“datan”代表三角形面片法向量坐標矩陣。每三行頂點坐標與一行法向量坐標相對應組成一組數據，這么一組對應數據表示一個三角形面片。這樣STL 模型的讀取初步完成。

2.2 數據的整合和第一次排序

數據的整合包括兩個部分:(1)將每一個三角形面片的3 個頂點坐標進行整合;(2)STL 模型中三角形面片頂點矩陣與三角形面片法向量矩陣的整合。三角形面片的頂點矩陣與法向量矩陣的整合是以三角形面片的3 個頂點坐標的整合為基礎的，將這些數據整合后使得每一個三角形面片的信息儲存在一個矩陣中的一行內，便于后續(xù)過程的需要。

(1)第一次數據整合

由于MATLAB 中的運算都是按一列一列順序進行，而讀取STL 模型數據的每一個頂點坐標都是按行提取的，若要整合一個三角形面片的3 個頂點坐標則必須將其作一次轉置，使之成為3 行n 列的矩陣，其表示形式如下:

datatri’ = ［v1x v2x v3x…vnx;v1y v2y v3y…vny;v1z v2z v3z…vnz］

將轉置后的矩陣轉換為9 行n/3 列的矩陣。這樣完成了三角形面片3 個頂點坐標的整合，轉換后的矩陣中的每一列代表一個三角形面片的3 個頂點。

(2)第一次排序

整合三角形面片的3 個頂點坐標后，為了后續(xù)的排序方便，在三角形面片的頂點矩陣與法向量矩陣整合之前，先對STL 模型中的每一個三角形面片頂點進行第一次排序，對模型的每一個三角形面片的3 個頂點按照其在分層方向上的分量的大小進行升序排列。這個過程在MATLAB 中的具體實現(xiàn)為:將第一次整合后的矩陣進行轉置，將其轉換為n/3 行9 列矩陣，依次提取矩陣中的每一行，將其轉換為3 行3 列矩陣，對該3 行3 列矩陣進行轉置，按照其中的某一列三值的大小對矩陣排序。(這樣就把每一個三角形面片劃分了出來，然后根據頂點坐標在分層方向上分量的大小對三角形面片的3 個頂點進行第一次排序。)排序后將3 行3 列矩陣轉置，然后將其轉換為一行。一行一行地將其輸出，組成一個n/3 行9 列的矩陣。(這樣將頂點排序后的每一個三角形面片放回到了原位置，該操作不僅完成了三角形面片的排序，而且輸出的矩陣可以直接和對應的法向量矩陣相結合組成三角形面片矩陣)這個n/3 行9 列的矩陣表示形式為:

datatrinew= ［v1x v1y v1z v2x v2y v2z v3x v3y v3z;…］

其中“v1x v1y v1z v2x v2y v2z v3x v3y v3z”是排序完成以后的3 個頂點坐標，并且每個三角形面片的3 個頂點的坐標處在該矩陣中的一行。

(3)第二次整合

第二次整合，即三角形面片的3 個頂點坐標矩陣與法矢量矩陣的整合。將第一次排序完成的三角形面片頂點坐標矩陣和三角形面片法向量坐標矩陣進行對應合并。由于在第一次整合和第一次排序過程中，本文始終沒有打亂三角形面片頂點坐標矩陣和三角形面法向量坐標矩陣的對應關系。所以對于這一次的整合就變得十分簡單，其表示形式如下:

data= ［datan，datatrinew］= ［ni nj nk v1x v1y v1z v2x v2y v2z v3x v3y v3z;…］

整合和第一次排序后的矩陣能夠完整地表示STL模型的幾何信息，而且使得原有的STL 模型數據得到精簡，經過第一次的坐標排序以后，使得每一個三角形面片的頂點坐標變得有序化，為后期的排序節(jié)省了許多時間，對后續(xù)工作的完成十分重要。

2.3 數據的分層排序過程

(1)第二次排序和數據的刪除

經過數據整合和第一次的排序，雖然三角形面片在模型的整體矩陣中仍以散亂的方式儲存，但是每一個三角形面片卻有規(guī)律可循了。因此對模型的整體矩陣進行排序精簡，用以達到對模型的快速分層要求。

每一個三角形面片頂點的坐標按照其在分層方向上分量的大小進行了升序排列，且每一個三角形面片的所有數據都在矩陣中的一行，那么按照三角形面片頂點坐標在分層方向上的最大值的大小對整合后的整個矩陣進行升序排列，這樣STL 模型中的三角形面片的第二次排序進行完成。

如果三角形面片在分層方向上的最大值小于某一分層切平面，那么說明該三角形面片就不會與該分層切平面相切，由于STL 模型分層處理時是按照分層平面由小到大進行切割，那么該三角形面片也不會與以后的分層切平面相交，這樣可以直接剔除該三角形面片，以便減少內存的占有量。

三角形面片第二次排序在MATLAB 中實現(xiàn)方式:將整合后的矩陣按照其中一列的數值大小進行升序排序(這一列的數值是每一個三角形面片頂點坐標在分層方向上的最大值，也就是按照每個三角形面片頂點在分層方向的最大值的大小進行升序排序)。

剔除三角形面片的過程在MATLAB 中實現(xiàn)方式:將整理后的那一列中所有小于分層切平面高度值的數值所屬的行全部刪除，由于在MATLAB 中不能按照數值的大小直接將整理后的列中小于分層切平面高度值的數值所屬的行直接刪除，所以只能通過查找小于分層切平面高度值的數值所在矩陣中的行數中最大的那一行，然后將這一行以及行數小于這一行的行全部刪除，經過這一過程后，將整個矩陣進行了精簡。這一過程也就是將所有頂點在分層方向最大值小于該分層切平面的高度值的三角形面片剔除，達到了精簡數據的目的。

(2)第三次排序和相交數據的提取

經過第二次的排序和數據的刪除，已經將頂點在分層方向上的分量的最大值小于分層切平面的三角形剔除，經過刪除后的矩陣只剩下與平面相交的三角形面片和最小值大于該分層切平面的三角形面片。

為了能夠獲得只與分層切平面相交的三角形面片，對刪除后矩陣作第三次排序，然后將不與分層切平面相交的三角形面片排除，提取出只與分層切平面相交的三角形面片。這一過程中不能夠對最小值大于分層切平面的三角形面片進行剔除，而只是用排除的方法，是為了提取只與分層切平面相交的三角形面片。而在(1)中的刪除是對已不會再與其他分層切平面相交的三角形面片的徹底刪除，達到數據精簡的目的。經過本次過程能夠把與該分層切平面相交的三角形面片全部提取出來。

三角形面片第三次排序在MATLAB 中實現(xiàn)方式:在第二次排序和數據刪除后的矩陣中，找到三角形面片頂點坐標在分層方向分量最小值的那一列，將該矩陣的行按照這一列中的數值大小進行升序排列。經過第三次排序后，使得剩余三角形面片按照其頂點坐標在分層方向上的最小值的大小進行了有序的排列。

相交數據的提取在MATLAB 中實現(xiàn)方式:矩陣第三次排序完成后，將其排序列中數值大于分層切平面高度值的行全部排除，從該矩陣中的排序列里尋找到小于或者等于分層切平面的數值所在的最大行，然后從該矩陣中提取出這一行到最后一行，這部分矩陣中的數據就是與該分層切平面相交的所有三角形面片的數據信息。這一步主要是將頂點坐標在分層方向上的分量的最小值大于分層切平面高度值的三角形面片進行排除，然后把所有與分層切平面相交的三角形面片直接提取出來。

2.4 分層切平面與三角形面片的求交

通過對數據的排序，精簡，提取出了只與分層切平面相交的三角形面片。對分層切平面與三角形面片的求交提出兩種方法。(1)應用文獻［8］中的Trioutline 函數直接獲得分層切平面與三角形平面的交線段，然后采用邊輸出邊制造的方法輸出輪廓線;(2)對提取的三角形面片建立點表，求得切平面與其中一個三角形面片的兩個交點后，按照順序查找與其相鄰的三角形面片，然后獲得與其相鄰的三角形面片另一個頂點，順序求交直到切平面與初次相交的三角形面片再次相交時為止;這樣求交，對每個三角形面片的每一個邊只需求得一次交點，節(jié)省了對同一邊兩次求交所浪費的時間。

3 實例分析

快速成型技術要求分層算法要有較高的穩(wěn)定性，而且在滿足精度的前提下，能夠很快地對模型進行分層運算，快速地輸出快速成型機能夠接受的分層輪廓線。

通過兩個實例對該程序的快速性及穩(wěn)定性進行驗證。每一個例子都是以ASCII 的形式對STL 模型的進行讀取。分層算法是在DELL N5010(處理器CPU:Intel(R)Core3)的Windows7 系統(tǒng)中安裝的MATLAB R2010a 編程語言環(huán)境下運行的。

快速成型技術中，分層方向的不同，模型在制造精度、制作時間以及需要添加的支撐都會不同，那么對模型的成型效率和制作成本都會產生較大的影響。文中分別從z、y、x 3 個方向對兩個模型進行分層處理試驗，具體結果如下:

3.1 卡扣

該卡扣是由三維掃描點云經過轉換得到的STL模型，該模型尺寸12.02 mm×29.00 mm×7.33 mm，面片個數50 329 個，頂點個數26 379 個，分層厚度為0.1 mm，3 個制作方向如圖1所示。

圖1 卡扣的分層圖

3.2 斗齒

該斗齒模型也是由三維掃描點云轉換得到的STL模型，尺寸為:97.64 mm ×222.00 mm ×89.69 mm，面片個數:101 462 個，頂點個數:50 727 個，由于該面片數據量較大，為了便于觀察，將分層層厚設置為:3 mm，分別從z、y、x 3 個方向分層，如圖2所示。

圖2 斗齒的分層圖

表1 文獻［9］與文中算法相同精度對同一模型的分層對比

4 結束語

通過對STL 模型的排序、精簡數據，直接提取只與分層切平面相交的三角形面片，然后快速輸出截面輪廓線。通過實例顯示該算法在保證精度的前提下，以較快的速度獲得所需數據，在與文獻［9］的對比中，文中算法不僅穩(wěn)定性較高，而且速度較快，尤其在數據量較大的時候其運行速度明顯快于文獻［9］，是文獻［9］運行速度的10 倍左右。

［1］PAN Haipeng，ZHOU Tianrui.Generation and Optimization of Slice Profile Data in Rapid Prototyping and Manufacturing［J］.Journal of Materials Processing Technology，2007，187/188:623－626.

［2］胡德洲，李占利，李滌塵，等.基于STL 模型幾何特征分類快速分層處理算法研究［J］.西安交通大學學報，2000，34(1):37－40.

［3］牟小云，鄭建明，田靜云.基于坐標分層的STL 模型切片算法的研究［J］.機床與液壓，2008，36(7):52－53.

［4］李仲陽，謝存禧，楊家紅.基于STL 文件的快速成型分層算法與毗鄰拓撲信息的快速提?。跩］.計算機工程與應用，2002，4(7):3235－3236.

［5］趙吉賓，劉偉軍.快速成型中基于STL 模型的分層算法研究［J］.應用基礎與工程學報，2008，16(2):224－233.

［6］溫佩芝，黃文明，吳成柯.一種改進的STL 文件快速分層算法［J］.計算機應用，2008，28(7):1766－1768.

［7］趙保軍，汪蘇，陳五一.STL 數據模型的快速切片算法［J］.北京航空航天大學學報，2004，30(4):329－333.

［8］馬良，黃衛(wèi)東.基于STL 數據模型動態(tài)拓撲重構的快速切片算法［J］.中國激光，2008，35(10):1623－1626.

［9］王春香，李振華.STL 模型分層算法的優(yōu)化及應用［J］.機械設計與制造，2013(3):87－90.