王春香，郝志博，陳浩宏

(1.內(nèi)蒙古科技大學(xué)機(jī)械學(xué)院，內(nèi)蒙古包頭014010;2.包頭市萬(wàn)佳信息工程有限公司，內(nèi)蒙古包頭014010)

0 前言［1－8］

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

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

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

(2)基于三角形面片的拓?fù)湫畔⒌姆謱铀惴?。該算法是根?jù)三角形面頂點(diǎn)坐標(biāo)依次建立點(diǎn)、線、面的鏈表或者根據(jù)平衡二叉樹對(duì)STL 模型建立整體的拓?fù)湫畔?，使得相鄰的三角形面片之間具有毗鄰關(guān)系，當(dāng)分層切平面與一個(gè)三角形面片相切時(shí)，便可以通過(guò)三角形面片的毗鄰關(guān)系依次查找出其他與該分層切平面相交的三角形面片，最后按順序輸出分層輪廓線。該方法的局限性在于對(duì)模型建立拓?fù)潢P(guān)系非常耗時(shí)，尤其在模型數(shù)據(jù)量較大時(shí)十分耗費(fèi)內(nèi)存資源。

(3)基于三角形面片的局部拓?fù)湫畔⒌姆謱铀惴?。這種算法是針對(duì)上述兩種算法的改進(jìn)，用以提高三角形面片的搜索效率。該算法首先建立一個(gè)三角形面片集，然后將與某一層分層切平面相交的三角形面片動(dòng)態(tài)地儲(chǔ)存在該集合中，當(dāng)分層切平面從上一層到下一層時(shí)，把不與該層相交的三角形面片從集合中剔除，將與該層相交的新三角形面片加入集合，然后對(duì)這些在集合中的三角形面片建立局部的拓?fù)潢P(guān)系，進(jìn)行求交運(yùn)算，最終輸出該層的輪廓線。該算法局限性在于集合中動(dòng)態(tài)儲(chǔ)存三角形面片和局部拓?fù)潢P(guān)系的建立仍是比較費(fèi)時(shí)的工作。

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

1 算法的基本思想

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

2 算法實(shí)現(xiàn)的基本過(guò)程

應(yīng)用MATLAB 軟件的強(qiáng)大矩陣邏輯運(yùn)算功能，快速地實(shí)現(xiàn)了該算法。該算法具體實(shí)現(xiàn)過(guò)程如下:

2.1 數(shù)據(jù)的讀取

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

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

datan= ［ni nj nk;…］

其中“;”代表每一行的分隔符，“datatri”代表三角形面片頂點(diǎn)坐標(biāo)矩陣，“datan”代表三角形面片法向量坐標(biāo)矩陣。每三行頂點(diǎn)坐標(biāo)與一行法向量坐標(biāo)相對(duì)應(yīng)組成一組數(shù)據(jù)，這么一組對(duì)應(yīng)數(shù)據(jù)表示一個(gè)三角形面片。這樣STL 模型的讀取初步完成。

2.2 數(shù)據(jù)的整合和第一次排序

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

(1)第一次數(shù)據(jù)整合

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

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

將轉(zhuǎn)置后的矩陣轉(zhuǎn)換為9 行n/3 列的矩陣。這樣完成了三角形面片3 個(gè)頂點(diǎn)坐標(biāo)的整合，轉(zhuǎn)換后的矩陣中的每一列代表一個(gè)三角形面片的3 個(gè)頂點(diǎn)。

(2)第一次排序

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

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

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

(3)第二次整合

第二次整合，即三角形面片的3 個(gè)頂點(diǎn)坐標(biāo)矩陣與法矢量矩陣的整合。將第一次排序完成的三角形面片頂點(diǎn)坐標(biāo)矩陣和三角形面片法向量坐標(biāo)矩陣進(jìn)行對(duì)應(yīng)合并。由于在第一次整合和第一次排序過(guò)程中，本文始終沒(méi)有打亂三角形面片頂點(diǎn)坐標(biāo)矩陣和三角形面法向量坐標(biāo)矩陣的對(duì)應(yīng)關(guān)系。所以對(duì)于這一次的整合就變得十分簡(jiǎn)單，其表示形式如下:

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

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

2.3 數(shù)據(jù)的分層排序過(guò)程

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

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

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

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

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

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

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

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

為了能夠獲得只與分層切平面相交的三角形面片，對(duì)刪除后矩陣作第三次排序，然后將不與分層切平面相交的三角形面片排除，提取出只與分層切平面相交的三角形面片。這一過(guò)程中不能夠?qū)ψ钚≈荡笥诜謱忧衅矫娴娜切蚊嫫M(jìn)行剔除，而只是用排除的方法，是為了提取只與分層切平面相交的三角形面片。而在(1)中的刪除是對(duì)已不會(huì)再與其他分層切平面相交的三角形面片的徹底刪除，達(dá)到數(shù)據(jù)精簡(jiǎn)的目的。經(jīng)過(guò)本次過(guò)程能夠把與該分層切平面相交的三角形面片全部提取出來(lái)。

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

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

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

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

3 實(shí)例分析

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

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

快速成型技術(shù)中，分層方向的不同，模型在制造精度、制作時(shí)間以及需要添加的支撐都會(huì)不同，那么對(duì)模型的成型效率和制作成本都會(huì)產(chǎn)生較大的影響。文中分別從z、y、x 3 個(gè)方向?qū)蓚€(gè)模型進(jìn)行分層處理試驗(yàn)，具體結(jié)果如下:

3.1 卡扣

該卡扣是由三維掃描點(diǎn)云經(jīng)過(guò)轉(zhuǎn)換得到的STL模型，該模型尺寸12.02 mm×29.00 mm×7.33 mm，面片個(gè)數(shù)50 329 個(gè)，頂點(diǎn)個(gè)數(shù)26 379 個(gè)，分層厚度為0.1 mm，3 個(gè)制作方向如圖1所示。

圖1 卡扣的分層圖

3.2 斗齒

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

圖2 斗齒的分層圖

表1 文獻(xiàn)［9］與文中算法相同精度對(duì)同一模型的分層對(duì)比

4 結(jié)束語(yǔ)

通過(guò)對(duì)STL 模型的排序、精簡(jiǎn)數(shù)據(jù)，直接提取只與分層切平面相交的三角形面片，然后快速輸出截面輪廓線。通過(guò)實(shí)例顯示該算法在保證精度的前提下，以較快的速度獲得所需數(shù)據(jù)，在與文獻(xiàn)［9］的對(duì)比中，文中算法不僅穩(wěn)定性較高，而且速度較快，尤其在數(shù)據(jù)量較大的時(shí)候其運(yùn)行速度明顯快于文獻(xiàn)［9］，是文獻(xiàn)［9］運(yùn)行速度的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］.西安交通大學(xué)學(xué)報(bào)，2000，34(1):37－40.

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

［4］李仲陽(yáng)，謝存禧，楊家紅.基于STL 文件的快速成型分層算法與毗鄰?fù)負(fù)湫畔⒌目焖偬崛。跩］.計(jì)算機(jī)工程與應(yīng)用，2002，4(7):3235－3236.

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

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

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

［8］馬良，黃衛(wèi)東.基于STL 數(shù)據(jù)模型動(dòng)態(tài)拓?fù)渲貥?gòu)的快速切片算法［J］.中國(guó)激光，2008，35(10):1623－1626.

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