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坐标的值从小到大进行排序。
1618 0
登陆后参与评论
2024-11-26 09:41:32
2024-11-26 09:34:52
2024-11-26 09:26:04
2024-11-22 10:29:56
2024-11-21 08:54:01
2024-11-21 08:52:43
2024-11-21 08:51:52
2024-11-21 08:47:37
2024-11-19 11:05:45
2024-11-19 11:01:39
2024-11-19 10:57:07
2024-11-19 10:54:25