3d打印STL文件拓撲結構的建立

STL 文件中，一個三角面片包含外法向量和按右手螺旋規(guī)則排列的三個頂點。STL文件格式規(guī)整、結構清晰，但是從實際的實體幾何拓撲模型轉換成 STL 的三角面片時，采用頂點和共邊“分裂”方式存儲，丟失了最初的拓撲關系，同時還增加了大量重頂點、重邊的冗余數據，從而造成了 STL 文件在后使用過程中的不便利，因此要重新建立 STL文件的拓撲結構。

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

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

建立數據結構的算法分為兩大步。第一步首先根據 STL 格式的數據建立頂點和邊的存儲結構，第二步采用快速排序算法把所有頂點結點按照z坐標的值從小到大進行排序。根據算法生成數據存儲結構圖，如圖所示：

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

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

太高端了，留著慢慢研究