基于哈希表的STL文件拓扑关系快速重建算法

钱　乘，李　震，江本赤，王　刚

（安徽工程大学 机械与汽车工程学院，安徽 芜湖 241000）

STL（surface tesselation language）文件格式是美国3D SYSTEMS公司于1988年制定的一个接口协议［1］。STL文件由逼近三维模型表面的多个三角形面片构成，但它已经丢失了原有的拓扑关系，且所记录的每个三角形顶点都至少被记录4次，平均被记录6次，造成了数据大量冗余。STL文件三角形间无拓扑关系且存在数据极大冗余，造成后续切片处理效率低，模型整体打印时间长。因此，构建合理的数据结构去除冗余数据，根据数据结构建立拓扑结构极其重要。

目前，研究人员已提出了多种STL文件拓扑关系的重建算法。张应中等［2］构造半边编码的三角网格拓扑数据结构实现拓扑重构，但构造该数据结构时程序复杂且拓扑重建运算效率较低；侯聪聪等［3］构造链表数据结构重建拓扑关系，但在去除冗余数据时，遍历整体链表会降低算法效率；陈萍等［4］利用三角形间半边拓扑结构遍历所构建的红黑树实现拓扑重构，但建树与检测平衡性在一定程度上降低了算法效率；杨晟院等［1］构建平衡二叉树的数据结构进行顶点聚合去除冗余数据，采用虚平衡二叉树进行快速邻边搜索实现拓扑重建，但当数据量较大时，建树与调整平衡需要花费时间，会降低算法效率；王增波［5］及王彦云等［6］构建哈希表实现冗余数据的去除以及快速的拓扑重建，但忽略了不同坐标可能存在相同关键字的情况，造成冗余数据去除与拓扑关系重建错误。

考虑到哈希表算法结构简单且时间复杂度较低，在冗余数据剔除与三角形间拓扑关系重建上具有较高效率，我们提出了基于哈希表的STL文件拓扑关系快速重建算法。算法主要是在分析STL文件信息的基础上，采用除留余数法与链地址法建立哈希表，在建立哈希表的同时完成对冗余数据的剔除、点表的建立及面表中的点索引值的建立，通过面表中记录的每个三角形的3个顶点坐标索引值的两两组合，得到点表中记录的共同三角形面片的索引值，根据共同面片索引值对面表中邻接面进行赋值，进行快速拓扑关系重建。

1　STL文件信息存储特点

STL文件中每个三角形面片的定义都包括三角形3个顶点的坐标以及单位法向量。三角形顶点坐标按照逆时针顺序存储，单位法向量方向指向模型外部。STL文件有两种格式：ASCII格式与二进制格式。二进制格式是采用固定字节给出三角形面片几何信息的，包含80 B的头文件信息、4 B的三角形面片个数信息、50 B描述三角形面片的信息。ASCII格式则以关键字为标志逐行给出三角形面片几何信息，数据格式如图1所示。ASCII格式与二进制格式相比更具可读性和直观性，方便对数据进行进一步处理。

图1　STL文件的ASCII格式结构

2　哈希表及STL文件拓扑重建

2.1　哈希表的建立

哈希表是可以根据关键字直接进行访问的数据结构。它采用函数映射的思想，将关键字映射到表中某个位置来访问记录，可以加快查找速度。映射函数叫作哈希函数，存放记录的数据叫作哈希表［7］。哈希表的建立需要两个关键步骤：哈希函数的设计与哈希冲突的解决方法。

2.1.1哈希函数的设计

哈希函数的设计目标主要有两个：一是使关键字的哈希地址在连续内存单元地址上尽可能地均匀分布，一是运算过程尽可能简单以提高哈希地址的计算速度。哈希函数的设计方法有直接定址法、数字分析法和除留余数法等［7］。我们选用除留余数法设计哈希函数。

根据欧拉方程

可知，哈希表的长度可设定为

这里Nvertex、Nfacet和Nedge分别为STL模型实际顶点、三角形面片的数量和边的数量，Nvertex＇为STL文件记录的顶点数目［8］。

假设顶点坐标为（vx，vy，vz），则关键字为

除留余数法就是用关键字 ki（0≤i≤Nvertex＇-1）除以不大于哈希表长度m的整数p所得余数作为哈希地址的方法。除留余数法建立的哈希函数为

其中：mod为求余运算；p取最接近m的素数，以减少哈希冲突的可能性。

2.1.2哈希冲突的解决方法

哈希表的建立过程中会出现这样的问题：不同的关键字 ki与 kj（i≠j）会存在相同的哈希地址 h（ki）=h（kj），这种现象称为哈希冲突。哈希冲突的解决方法有开放地址法、再哈希法和链地址法等［7］。由于链地址法具有处理冲突简单、无堆积现象等优势，我们采用链地址法处理哈希冲突。链地址法将具有哈希冲突的关键字ki链接在该哈希地址对应的链表中。采用链地址法建立的链表结构如图2所示。

图2　哈希表数据结构

2.2　点表与面表数据结构

三角形间拓扑关系的重建是先通过面表中记录的顶点坐标索引值的两两组合得到点表中记录的共同三角形面片的索引值，再根据共同面片索引值对面表中邻接面进行赋值。可见，建立合理的点表与面表数据格式非常重要。

2.2.1点表的结构

在建立点表时，可以将每个点的数据结构看作点表中的单元。每个单元包含点坐标的索引值、点坐标和所属三角形面片索引值。关键字在哈希表中的地址作为点坐标的索引值。点表单元结构如图3所示。

图3　点表单元结构

2.2.2面表的结构

在建立面表时，可以将每个面的数据结构看作面表中的单元。面表单元结构如图4所示。每个单元包含三角形面片的索引值、3个顶点坐标的索引值、每条边的邻接三角形面片索引值。为方便后续切片，将边的顺序按照逆时针方向分为第一、第二、第三条边（在图4中用英文单词表示），然后获取每条边的邻接三角形面片索引值。

图4　面表单元结构

2.3　拓扑重建算法

在建立哈希表的同时，以不完整的哈希表作为查找表进行冗余坐标的剔除。在STL文件中，由于数据量庞大，建立哈希表时可能存在相同关键字对应不同点坐标的情况。因此，我们将冗余坐标的判断条件定为关键字相同且该关键字对应的坐标值也相同。STL文件中三角形间拓扑关系的重建，实际上是根据STL模型三角形间的共边规则进行拓扑重建。拓扑关系重建算法步骤如下：

1）顺序读取一个三角形面片的顶点坐标。

2）根据式（4）与式（5）变换顶点坐标，得到关键字及哈希地址。

3）在该哈希地址对应的链表中查找。若未查到该关键字的记录，就将该关键字存入链表中，建立该顶点的点单元数据；若查到该关键字的记录，转到4）。

4）将该顶点坐标与已记录的坐标进行比较。若坐标值相同，则视为冗余数据，在已存在的点表单元数据中记录该顶点所属面片的索引值；若坐标值不同，则将该关键字存入链表中，建立该顶点的点单元数据。

5）在面表中记录该顶点的索引值。

6）若三角形面片顶点坐标读取完成，则转到步骤7）；若未完成，则转到 1）。

7）顺序读取面表中面单元结构顶点索引值数据。

8）将3个顶点坐标索引值以逆时针方向两两组合，得到点表中2个点单元数据共同所属三角形面片的索引值，然后去除所读取的三角形面片索引值，以余留三角形面片索引值对面表单元数据中的邻接面进行赋值。

9）检查面表中面表单元是否被完全读取。若未完全读取，则转到7）；否则，结束程序。

3　实验及结果分析

为了验证STL文件拓扑关系重建算法的可靠性与可行性，给出如图5所示的模型。图5（a）为三维模型，图5（b）为利用拓扑重建算法建立的STL模型。通过对比图 5（a）与图 5（b）模型，可观察到 STL模型与三维模型表面完全符合，且STL模型中三角形拓扑关系没出现拓扑混乱的情况。

在图5（a）三维模型的STL文件中，三角形面片数为394、顶点数为1 182、占用存储空间为112 KB。在利用哈希表对STL文件中坐标信息进行处理后，去除冗余顶点的数目为989、占用存储空间为34 KB。可见，利用哈希表删除STL文件中的冗余坐标可大幅度降低STL文件占用的存储空间。

对于图5（b）STL模型，利用本文拓扑重建算法重建时间为0.015 s，文献［4］的拓扑重建算法重建时间为0.118 s，文献［6］拓扑重建算法重建时间为0.013 s。文献［6］的拓扑重建时间虽然小于本文拓扑重建算法，但文献［6］在通过哈希表建立三角形拓扑关系时，忽略了不同坐标可能存在相同关键字的情况，易造成冗余数据去除与拓扑关系重建错误。

在图5（a）所示三维模型的 STL文件中任意给定一个三角形，如图6（a）所示面表中索引值为35的三角形面片［即图5（b）模型中箭头指向处］，利用拓扑重建算法可迅速查找到与其邻接的三角形面片，按照逆时针规则分别为三角形面片20、80和21。图6（b）为利用本文拓扑重建算法建立该三角形的局部拓扑关系的示意图。可以看出，使用本算法能更清晰地观察三角形间拓扑关系，说明算法在STL文件拓扑关系的重建上具有较好的效果。

图5　STL模型的拓扑重建效果图

图6　STL模型的局部拓扑重建效果图

4　结论

在建立哈希表的同时以不完整的哈希表作为查找表，进行冗余坐标的剔除，可以有效减少STL文件占用的存储空间，方便文件传输以及后续数据处理。通过点表与面表中点索引值的运用，高效建立STL文件三角形间拓扑关系，提高了切片效率，可降低模型的整体打印时间。