没有合适的资源?快使用搜索试试~ 我知道了~
针对三维模型转换为STL文件后会丢失三角面间的拓扑关系,在对STL格式文件进行读取和分析时,提出了一种基于半边结构和哈希表的快速拓扑重构算法。在读取数据过程中,通过哈希表建立无重复位置信息的点表,并在其中维护一个未添加邻接面的半边集合。依据该集合和拓扑算法完善面的拓扑关系,实现在读取数据的过程中快速建立面的拓扑关系。
资源推荐
资源详情
资源评论
基于半边结构的基于半边结构的STL文件快速拓扑算法文件快速拓扑算法
针对三维模型转换为STL文件后会丢失三角面间的拓扑关系,在对STL格式文件进行读取和分析时,提出了一种
基于半边结构和哈希表的快速拓扑重构算法。在读取数据过程中,通过哈希表建立无重复位置信息的点表,并
在其中维护一个未添加邻接面的半边集合。依据该集合和拓扑算法完善面的拓扑关系,实现在读取数据的过程
中快速建立面的拓扑关系。
0 引言引言
自3D打印技术问世之后,凭借其复杂性低、成本低廉、软件开源、易于推广等特点在国内外得到了迅速的发展
[1]
。
STL(Stereo Lithography)文件是由美国3D System公司于1987年制定的接口协议,由于其格式简单、读写便利,成为3D打印
过程中最常用的数据存储格式
[2]
。STL文件由离散的三角面片组成,存放了模型的点云的位置信息和三角面片的法向量,但其
丢失了面与面之间的拓扑关系,同时,单个点被多次记录,造成了大量的数据冗余
[3]
。在快速成型过程中,待支撑位置查询、
模型分层切片等操作均需要三角面间的拓扑关系
[4]
,因此,建立合理的数据结构剔除冗余信息,采用高效的算法建立拓扑关系
就显得尤为重要。
针对STL文件读写的局限,国内外专家提出多种解决方案。侯聪聪等
[5]
提出基于链表的数据存储和拓扑结构,建立点、边、
面表进行数据存储,虽剔除了STL文件中的重复点,但每次建立拓扑关系时,均对整个边表进行遍历,算法性能较低;王增
波
[6]
采用哈希表作为基础结构,将有效数据仅保存一次,提升了数据的添加和查找速度,几乎可以在常数时间内快速完成,但
建立拓扑关系时,依旧是对已存数据进行遍历,不仅效率较低,还存在部分数据查找遗漏的现象;王彦云等
[7]
优化了哈希表的
冲突解决方案,采用二分查找的方法对相同key值的链表进行查找,提升了查表速度,但拓扑算法效率依旧较低;钱乘等
[8]
也
采用哈希表进行数据存储,存储数据的同时对每个点记录其所属三角面片,全部存储完毕后,再对所有面片进行遍历,建立拓
扑关系,不存在遗漏,但读取完成后,需要再次遍历面表寻找邻接面;张应中等
[9]
利用半边结构进行拓扑关系建立,巧妙地将
点与面的信息存入边,利用三角面中顶点的存放顺序来保存边的信息,精简了存储结构,但拓扑算法复杂,并且需要在读入全
部顶点的情况下建立拓扑关系。
基于以上算法的研究,本文提出一种基于哈希表的、利用半边结构的数据存储和三角面拓扑算法,在读取数据过程中,一
方面剔除冗余数据,一方面快速建立面的拓扑关系,每读入一个三角面信息,进行数据存放的同时,在点表中维护一个未添加
邻接面的半边集合。当数据读取完成后,建立无重复数据的点表和面表,完善三角面间的拓扑关系。
1 STL文件文件
STL格式文件分为ASCII码和二进制两种,其中,二进制格式的文件数据结构如图1所示,与ASCII相比存储更加紧凑,占用
空间较小,会在文件起始位置记录三角面片总数Num,在后续建立哈希表时也能依据此选择更加合适的表长。
由欧拉公式可知,存储正确的三角网格文件,三角面的数量约为顶点的2倍
[10]
,而在STL文件中,每存储一次面片信息,都
会重复存储3个点的位置坐标,使得存的储顶点数量是面片数量的3倍
[11]
。由此可得,每个顶点在STL文件中平均记录了6次,
所以在进行拓扑关系建立前,需要先对冗余信息进行辨别和剔除,使每个顶点仅存储一次,减少数据存储量,提升算法效率。
2 采用半边结构的拓扑数据结构采用半边结构的拓扑数据结构
2.1 半边的二元组表示半边的二元组表示
本文采用文献[9]提出的精简半边结构作为基础,使用三角面的标志和半边在面中的序号来表示半边。如图2所示,顶点A、
B、C、A按照逆时针顺序连线构成面M
1
;顶点D、A、C、D连线构成面M
2
,半边L
2
可以表示为[M
1
,2],即M
1
面中的第2条半
边,半边L
6
可以表示为[M
2
,3],即M
2
面中的第3条半边。
资源评论
weixin_38629391
- 粉丝: 3
- 资源: 929
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功