3d打印STL文件拓扑结构的建立

STL 文件中，一个三角面片包含外法向量和按右手螺旋规则排列的三个顶点。STL文件格式规整、结构清晰，但是从实际的实体几何拓扑模型转换成 STL 的三角面片时，采用顶点和共边“分裂”方式存储，丢失了最初的拓扑关系，同时还增加了大量重顶点、重边的冗余数据，从而造成了 STL 文件在后使用过程中的不便利，因此要重新建立 STL文件的拓扑结构。

假设一个实体模型包含 F 个三角面片，而每个三角形有三条边，共有 3F 条边。根据前面所述的 STL 文件一致性规则，每一条组成三角形的边有且只有两个三角形面片与之相连，即每一条边有两个三角形共享。除去重复的 50%，模型中不重复的边数为 1.5F，记作 E。设模型包含的不重复的顶点数为 V 由欧拉公式
可知：
V+F≈E （3.1）
其中，V 为空间模型的顶点总数，E 为空间模型的棱边总数，F 为空间模型的三角面片总数。将 E 约等于 1.5F 带入式（3.1），可以求得：
V≈0.5F （3.2）
在式（3.2）中，实体模型中不重复的顶点只有 0.5F 个。根据 STL 文件的记录方式，实际被保存的顶点数目为 3F 个，对比可知，如果直接将三角形一个一个的保存起来将会浪费大约 2.5F 个顶点的储存空间，对于大型的 STL 文件，这势必对运算速度造成较大影响，所以，本文只保存不重复的实体模型顶点，边的信息可从顶点中获得。这里，为不重复的顶点建立一个顶点坐标顺序表，每读入一个三角形，依次判断它的三个顶点是否已经在表中存在，如果已经存在，则不再保存；如果表中还没有这个点，则将它插入其中。同时根据顶点建立边链表，最后将顶点顺序表依照 Z 值的大小进行快速排序。下面提出一种基于 STL 模型建立拓扑结构信息的算法。该算法首先根据 STL 文件的规则，建立数据结构，在该数据结构中，每一个顶点只被存储一次，过滤掉重复顶点，节约了存储空间。边的信息可以从顶点与顶点的关系中得出，因此在存取顶点时为每个小三角面片建立边的关系，然后以顶点为起点建立边的存储结构，将边组成链表。边之间的关系以及三角面片的拓扑结构可以在边链表和顶点结点的关系中得出。算法主要的优点是把所有的顶点按照从小到大顺序排列，因为分层平面是按照 Z 值从小到大分层的，分层时数据不需要进行分组，只需要考虑 Z 值小于分层平面的顶点组成的顺序表，若是一个分层平面与 Z 值小于该平面的某顶点的所有的边都没有交点，那么下一个分层平面就不再考虑从该顶点出发的边，减少了求交时的比较次数

表示顶点信息的结点数据结构如下：
Class CVertex{
Public:
int id; //该顶点的 id 号
float Vx,Vy,Vz; //Vx、Vy、Vz 分别为该顶点的 x、y、z 坐标
CEdge *firstedge; //firstedge 为指针，指向以该顶点为端点的第一条边
};
在存储边的信息时，为了方便记录各条边之间的关系，在同一个三角面片上的三条边的顺序按照 STL 规则的右手螺旋法则来记录。下面给出三个数据结构定义：
定义 1：三条边按照右手规则的顺序，在某边前面的边称为某边的前接边。
定义 2：三条边按照右手规则的顺序，在某边后面的边称为某边的后序边。
定义 3：每条边出现在两个三角面片中，所以每条边被存储两次。这两条边的端点
相同，方向相反，其中一条边称为另一条边的剩余半边。
表示边的边结点数据结构如下所示：
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坐标的值从小到大进行排序。根据算法生成数据存储结构图，如图所示：

3d打印STL文件拓扑结构的建立

数据结构建立算法：
第 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）放置在它之前，将所有大于枢轴顶点的顶点放置在它之后。按照这种规则可将所有顶点以枢轴为分间线分割为两个子序列，{Lvertex[s].Vz, Lvertex[s+1].Vz,...,
Lvertex[i-1].Vz }和{Lvertex[i+1].Vz, Lvertex[i+2].Vz,..., Lvertex[m].Vz }，则可完成一趟快速排序过程；然后按照这种规则分别对两个子表再一次进行排列，递归下去；最后直到将所有的顶点依照顶点的 Vz 值排列有序。
其一趟排序过程：
（1）附设两个指针 low 和 high，初值分别为 low=0，high=n；
（2）设枢轴顶点为 pivotkey，初值为 pivotkey=Lvertex[0].Vz；
（3）从 high 的位置向前搜索找到第一个小于 pivotkey 值的顶点且和枢轴顶点交换数据；
（4）从 low 的位置向后搜索找到第一个大于 pivotkey 值的顶点且和枢轴顶点交换数据；
（5）当 low！=high 循环第（3）步和第（4）步。

太高端了，留着慢慢研究