支持STL数据源的网格曲面动态空间索引  

Dynamic spatial index of mesh surface for supporting STL data source

作　　者：郭洪帅 孙殿柱[1] 李延瑞[2] 李聪[1] 

机构地区：[1]山东理工大学机械工程学院,山东淄博255049 [2]西安交通大学机械工程学院,西安710049

出　　处：《计算机应用》2015年第9期2611-2615,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(51075247)

摘　　要：针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。Focusing on the issue that there exist defects of vertex data redundancy and lack of adjacency information among the faces in the STereo Lithography （STL） file format, an explicit algorithm of surface topology reconstruction was presented based on the multi-dimensional dynamic spatial index. During the process of eliminating the copies of the mesh vertex data, the K-Dimensional Tree （ KD Tree） of the vertices on the mesh surface was gradually built. The efficiency of eliminating the vertex copies was improved by the index and the surface topology was rapidly built based on the storage openness of the data in the leaf node layer of KD-tree, in which the half-edge data structure could be integrated. Finally, compared with methods using R ＊ -Tree, array and hash table as index, the proposed dynamic spatial index integrated KD-Tree with half-edge date structure used 11.93 s to remove redundant vertices and 2.87 s to reconstruct surface topology when dealing with the data file of nearly one million faces, which significantly reduced the time of eliminating the redundant vertices and surface topology reconstruction. And the index effectively supported quick query of the topology information of mesh surface with the query time in 1 ms, which was far less than the comparison algorithms. The experimental results show that the proposed algorithm can improve the efficiency of eliminating the vertex data redundancy and the topological reconstruction as well as achieve quick query of the topology information of mesh surface.

关 键 词：STL文件格式 K维树 半边结构 曲面拓扑重建 k-近邻查询 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]