3d打印STL文件拓?fù)浣Y(jié)構(gòu)的建立

STL 文件中,，一個(gè)三角面片包含外法向量和按右手螺旋規(guī)則排列的三個(gè)頂點(diǎn),。STL文件格式規(guī)整,、結(jié)構(gòu)清晰,，但是從實(shí)際的實(shí)體幾何拓?fù)淠Ｐ娃D(zhuǎn)換成 STL 的三角面片時(shí)，采用頂點(diǎn)和共邊“分裂”方式存儲(chǔ),，丟失了最初的拓?fù)潢P(guān)系,，同時(shí)還增加了大量重頂點(diǎn)、重邊的冗余數(shù)據(jù),，從而造成了 STL 文件在后使用過程中的不便利,，因此要重新建立 STL文件的拓?fù)浣Y(jié)構(gòu)。

假設(shè)一個(gè)實(shí)體模型包含 F 個(gè)三角面片,，而每個(gè)三角形有三條邊,，共有 3F 條邊。根據(jù)前面所述的 STL 文件一致性規(guī)則,，每一條組成三角形的邊有且只有兩個(gè)三角形面片與之相連,，即每一條邊有兩個(gè)三角形共享。除去重復(fù)的 50%,，模型中不重復(fù)的邊數(shù)為 1.5F,，記作 E。設(shè)模型包含的不重復(fù)的頂點(diǎn)數(shù)為 V 由歐拉公式
可知：
V+F≈E （3.1）
其中,，V 為空間模型的頂點(diǎn)總數(shù),，E 為空間模型的棱邊總數(shù)，F(xiàn) 為空間模型的三角面片總數(shù),。將 E 約等于 1.5F 帶入式（3.1）,，可以求得：
V≈0.5F （3.2）
在式（3.2）中，實(shí)體模型中不重復(fù)的頂點(diǎn)只有 0.5F 個(gè),。根據(jù) STL 文件的記錄方式,，實(shí)際被保存的頂點(diǎn)數(shù)目為 3F 個(gè)，對(duì)比可知,，如果直接將三角形一個(gè)一個(gè)的保存起來將會(huì)浪費(fèi)大約 2.5F 個(gè)頂點(diǎn)的儲(chǔ)存空間,，對(duì)于大型的 STL 文件，這勢(shì)必對(duì)運(yùn)算速度造成較大影響,，所以,，本文只保存不重復(fù)的實(shí)體模型頂點(diǎn)，邊的信息可從頂點(diǎn)中獲得,。這里,，為不重復(fù)的頂點(diǎn)建立一個(gè)頂點(diǎn)坐標(biāo)順序表，每讀入一個(gè)三角形,，依次判斷它的三個(gè)頂點(diǎn)是否已經(jīng)在表中存在,，如果已經(jīng)存在，則不再保存,；如果表中還沒有這個(gè)點(diǎn),，則將它插入其中,。同時(shí)根據(jù)頂點(diǎn)建立邊鏈表，最后將頂點(diǎn)順序表依照 Z 值的大小進(jìn)行快速排序,。下面提出一種基于 STL 模型建立拓?fù)浣Y(jié)構(gòu)信息的算法,。該算法首先根據(jù) STL 文件的規(guī)則，建立數(shù)據(jù)結(jié)構(gòu),，在該數(shù)據(jù)結(jié)構(gòu)中,，每一個(gè)頂點(diǎn)只被存儲(chǔ)一次，過濾掉重復(fù)頂點(diǎn),，節(jié)約了存儲(chǔ)空間,。邊的信息可以從頂點(diǎn)與頂點(diǎn)的關(guān)系中得出，因此在存取頂點(diǎn)時(shí)為每個(gè)小三角面片建立邊的關(guān)系,，然后以頂點(diǎn)為起點(diǎn)建立邊的存儲(chǔ)結(jié)構(gòu),，將邊組成鏈表。邊之間的關(guān)系以及三角面片的拓?fù)浣Y(jié)構(gòu)可以在邊鏈表和頂點(diǎn)結(jié)點(diǎn)的關(guān)系中得出,。算法主要的優(yōu)點(diǎn)是把所有的頂點(diǎn)按照從小到大順序排列,，因?yàn)榉謱悠矫媸前凑?Z 值從小到大分層的，分層時(shí)數(shù)據(jù)不需要進(jìn)行分組,，只需要考慮 Z 值小于分層平面的頂點(diǎn)組成的順序表,，若是一個(gè)分層平面與 Z 值小于該平面的某頂點(diǎn)的所有的邊都沒有交點(diǎn)，那么下一個(gè)分層平面就不再考慮從該頂點(diǎn)出發(fā)的邊,，減少了求交時(shí)的比較次數(shù)

表示頂點(diǎn)信息的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下：
Class CVertex{
Public:
int id; //該頂點(diǎn)的 id 號(hào)
float Vx,Vy,Vz; //Vx,、Vy、Vz 分別為該頂點(diǎn)的 x,、y,、z 坐標(biāo)
CEdge *firstedge; //firstedge 為指針，指向以該頂點(diǎn)為端點(diǎn)的第一條邊
};
在存儲(chǔ)邊的信息時(shí),，為了方便記錄各條邊之間的關(guān)系,，在同一個(gè)三角面片上的三條邊的順序按照 STL 規(guī)則的右手螺旋法則來記錄。下面給出三個(gè)數(shù)據(jù)結(jié)構(gòu)定義：
定義 1：三條邊按照右手規(guī)則的順序,，在某邊前面的邊稱為某邊的前接邊,。
定義 2：三條邊按照右手規(guī)則的順序，在某邊后面的邊稱為某邊的后序邊,。
定義 3：每條邊出現(xiàn)在兩個(gè)三角面片中,，所以每條邊被存儲(chǔ)兩次。這兩條邊的端點(diǎn)
相同,，方向相反,，其中一條邊稱為另一條邊的剩余半邊。
表示邊的邊結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下所示：
Class CEdge{
Public:
int flag; //標(biāo)志域,，取 0 或 1
int sid,eid; //sid,eid 為該邊開始端點(diǎn)和結(jié)束端點(diǎn)的 id 值
int nsid,neid; //nsid,neid 為該邊后序邊的開始端點(diǎn)和結(jié)束端點(diǎn)的 id 值
CEdge *edgenext; //edgenext 為指針,，指向下一條鄰接邊
};
記錄邊的結(jié)點(diǎn)信息時(shí)同時(shí)記錄了它的后序邊的位置，根據(jù)后序邊可以表示同一個(gè)三角面片三條邊之間的拓?fù)湫畔�,，而且根�?jù)邊的開始端點(diǎn)和結(jié)束端點(diǎn)的 id 值可以得出它的剩余半邊的信息,。

建立數(shù)據(jù)結(jié)構(gòu)的算法分為兩大步。第一步首先根據(jù) STL 格式的數(shù)據(jù)建立頂點(diǎn)和邊的存儲(chǔ)結(jié)構(gòu),，第二步采用快速排序算法把所有頂點(diǎn)結(jié)點(diǎn)按照z坐標(biāo)的值從小到大進(jìn)行排序,。根據(jù)算法生成數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)圖，如圖所示：

數(shù)據(jù)結(jié)構(gòu)建立算法：
第 1 步：根據(jù) STL 格式的數(shù)據(jù)文件建立頂點(diǎn)和邊的存儲(chǔ)結(jié)構(gòu),。
其算法如下：
（1）掃描 STL 格式的文件,，讀一個(gè)三角面片的信息；
（2）讀第一個(gè)頂點(diǎn)時(shí),，掃描頂點(diǎn)順序表,，根據(jù)頂點(diǎn)的值看是否已有該頂點(diǎn)。若無該頂點(diǎn),，則為該頂點(diǎn)生成一個(gè)新的 id 號(hào),，并把該頂點(diǎn)存入頂點(diǎn)順序表中；若有該頂點(diǎn)則不再存入該頂點(diǎn),。最后,，把第一個(gè)頂點(diǎn)的 id 號(hào)存儲(chǔ)到臨時(shí)變量 f1 中；
（3）讀第二個(gè)頂點(diǎn)時(shí),，掃描頂點(diǎn)順序表,，根據(jù)頂點(diǎn)的值看是否已有該頂點(diǎn)。若無該頂點(diǎn),，則為該頂點(diǎn)生成一個(gè)新的 id 號(hào),，并把該頂點(diǎn)存入頂點(diǎn)順序表中；若有該頂點(diǎn)則不再存入該頂點(diǎn),。最后,，把第二個(gè)頂點(diǎn)的 id 號(hào)存儲(chǔ)到臨時(shí)變量 f2 中；
（4）讀第三個(gè)頂點(diǎn)時(shí),，掃描頂點(diǎn)順序表,，根據(jù)頂點(diǎn)的值看是否已有該頂點(diǎn)。若無該頂點(diǎn),，則為該頂點(diǎn)生成一個(gè)新的 id 號(hào),，并把該頂點(diǎn)存入頂點(diǎn)順序表中；若有該頂點(diǎn)則不再存入該頂點(diǎn),。最后,，把第三個(gè)頂點(diǎn)的 id 號(hào)存儲(chǔ)到臨時(shí)變量 f3 中；
（5）生成第一條邊的結(jié)點(diǎn)，并把它鏈入以第一個(gè)頂點(diǎn)為表頭的鏈表中,。該邊的
flag=0,sid=f1,eid=f2,nsid=f2,neid=f3,；
（6）生成第二條邊的結(jié)點(diǎn)，并把它鏈入以第二個(gè)頂點(diǎn)為表頭的鏈表中,。該邊的
flag=0,sid=f2,eid=f3,nsid=f3,neid=f1,；
（7）生成第三條邊的結(jié)點(diǎn)，并把它鏈入以第三個(gè)頂點(diǎn)為表頭的鏈表中,。該邊的
flag=0,sid=f3,eid=f1,nsid=f1,neid=f2,；
（8）若 STL 文件沒有讀完則轉(zhuǎn)⑴，否則算法結(jié)束,。

第 2 步：采用快速排序算法,，對(duì)頂點(diǎn)結(jié)點(diǎn)按照 z 的值從小到大進(jìn)行排序。拓?fù)浣Y(jié)構(gòu)建立后,，對(duì)三角面片數(shù)據(jù)做排序處理,，依據(jù)每個(gè)三角形頂點(diǎn) z 值排序，按z 值從小到大排列有序,，考慮到時(shí)間,、空間復(fù)雜度和排序效率。排序算法采用快速排序法,。定義頂點(diǎn)順序表為 Cvertex Lvertex[n],，首先任意選取一頂點(diǎn) z 值（可選第一個(gè)頂點(diǎn)
Lvertex[0].Vz）作為樞軸，將所有小于樞軸頂點(diǎn)的頂點(diǎn)（這里頂點(diǎn)為頂點(diǎn)的 Vz 值,，下同為 Vz）放置在它之前,，將所有大于樞軸頂點(diǎn)的頂點(diǎn)放置在它之后。按照這種規(guī)則可將所有頂點(diǎn)以樞軸為分間線分割為兩個(gè)子序列,，{Lvertex[s].Vz, Lvertex[s+1].Vz,...,
Lvertex[i-1].Vz }和{Lvertex[i+1].Vz, Lvertex[i+2].Vz,..., Lvertex[m].Vz },，則可完成一趟快速排序過程；然后按照這種規(guī)則分別對(duì)兩個(gè)子表再一次進(jìn)行排列,，遞歸下去,；最后直到將所有的頂點(diǎn)依照頂點(diǎn)的 Vz 值排列有序。
其一趟排序過程：
（1）附設(shè)兩個(gè)指針 low 和 high,，初值分別為 low=0,，high=n；
（2）設(shè)樞軸頂點(diǎn)為 pivotkey,，初值為 pivotkey=Lvertex[0].Vz,；
（3）從 high 的位置向前搜索找到第一個(gè)小于 pivotkey 值的頂點(diǎn)且和樞軸頂點(diǎn)交換數(shù)據(jù)；
（4）從 low 的位置向后搜索找到第一個(gè)大于 pivotkey 值的頂點(diǎn)且和樞軸頂點(diǎn)交換數(shù)據(jù),；
（5）當(dāng) low,！=high 循環(huán)第（3）步和第（4）步。

太高端了，留著慢慢研究