基于Hash函数的TIN拓扑关系重建

Reconstruction of Topological Relation in TIN Based on Hash Function

STL模型是CAD、景观造型器等图形处理软件中常用的三角形网络文件格式,该文件由于不带有三角形的拓扑关系,使其不便与GIS中的地形模型(如TIN)进行叠置分析等操作。提出一种基于Hash函数的STL模型的三角形拓扑重建算法,讨论Hash函数设计和评价,给出基于Hash函数的TIN拓扑重建算法和拓扑检查方法,并通过实例对该算法进行验证。

The STL （STereo Lithography） file is commonly used in CAD,sight emulator and other fields. Because this file format has no topology relation and it is difficult to analysis with terrain model such as TIN, it is necessary to reconstruct the topological relation of STL model. In the past, reconstruction of topological relation usually is time consuming. There are two methods traditionally. One is adding the triangles to the model one by one. The other one is using some special data structure to speed the topological reconstruction. This paper provides a new algorithm to reconstruct the topology of STL model based on Hash function. The current Hash functions are reviewed,and a Hash function is chosen, which is suited for reconstruction of topological relation in TIN. Besides, a new topological reconstruction algorithm based on the Hash function has been designed. It is divided into two steps. In the first step, point topology of TIN has been established. Hash table is built using Hash function when scanning the STL file. The purpose is to delete the repeating points from STL and establish the point topological relation that is the relating triangles with points. The second step is to build the triangle topology. In this process, triangles that have same side are found out using Hash function. Finally an example to validate the alorithrn is given.