李 勇，宋占洋，尚会超，付晓莉

（中原工学院机电学院，河南 郑州451191）

1 引言

STL文件（Stereolithography，光固化立体造型术的缩写）作为一种三维模型数据格式，常用于CAD应用程序，例如快速成型系统中［1-2］。STL格式非常简单，其原理是所有模型的表面都可以看作一个多边形，多边形用一组三角面片进行分割，每个三角面片用一组表示其顶点坐标和法向矢量坐标信息的数据保存到文件中，分割模型的三角面片被随机的存储，彼此之间没有任何邻接关系［3］。

但是在实际应用时，STL格式文件最主要的缺点就是它的存储形式不包含模型表面结构和拓扑关系。在STL文件的生成算法中，每个顶点至少被6个三角形共有，这个共有的顶点坐标被重复存储，造成了大量冗余坐标信息［4］。

在进行模型处理时，需要重构三角网格，建立三角面片之间的拓扑关系。这种拓扑关系的建立是通过对每个顶点找到所有包含这个顶点的三角面片。从给定的三角面片集合中重建三角网格具有很大的复杂性，特别是对所含三角面片数量较多的模型文件［5-6］。

重构三角网格时，必须遍历三角网格上的每个顶点，将他们在一个坐标系中进行排序，删除重复顶点坐标，建立有规律的三角网格和邻接的三角形坐标信息。重构的三角网格中，所有顶点只存储一次，在计算机中执行这种操作的时间复杂度可达O（NlogN），其中N为三角网格中三角面片的个数，如果对于一个106-107量级的三角形面片数量来表达的模型表面，网格重构将会是非常耗时的过程［11］。……