计算机应用 ›› 2015, Vol. 35 ›› Issue (9): 2611-2615.DOI: 10.11772/j.issn.1001-9081.2015.09.2611

• 虚拟现实与数字媒体 • 上一篇    下一篇

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

郭洪帅1, 孙殿柱1, 李延瑞2, 李聪1   

  1. 1. 山东理工大学 机械工程学院, 山东 淄博 255049;
    2. 西安交通大学 机械工程学院, 西安 710049
  • 收稿日期:2015-04-23 修回日期:2015-06-02 出版日期:2015-09-10 发布日期:2015-09-17
  • 通讯作者: 孙殿柱(1956-),男,山东烟台人,教授,博士,主要研究方向:CAD/CAM、逆向工程,dianzhus@sdut.edu.cn
  • 作者简介:郭洪帅(1989-),男,山东潍坊人,硕士研究生,主要研究方向:逆向工程、点云处理;李延瑞(1979-),男,山东郯城人,博士研究生,主要研究方向:三维数据处理、曲面重建;李聪(1985-),男,山东菏泽人,硕士,主要研究方向:逆向工程、曲面重建。
  • 基金资助:
    国家自然科学基金资助项目(51075247)。

Dynamic spatial index of mesh surface for supporting STL data source

GUO Hongshuai1, SUN Dianzhu1, LI Yanrui2, LI Cong1   

  1. 1. School of Mechanical Engineering, Shandong University of Technology, Zibo Shandong 255049, China;
    2. School of Mechanical Engineering, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China
  • Received:2015-04-23 Revised:2015-06-02 Online:2015-09-10 Published:2015-09-17

摘要: 针对STL文件格式存在网格顶点数据冗余以及缺乏面片邻接信息等缺陷,提出一种基于多维动态空间索引的显式曲面拓扑重建算法,在消除网格顶点数据复本的过程中逐步构建网格曲面顶点的KD树,通过该索引提高顶点数据复本消除效率,并基于KD树叶节点层数据存储的开放性融入半边数据结构,实现曲面拓扑结构的快速重建。最后,对6个不同规模的数据模型进行实验:与采用R*-Tree、数组、散列表作为索引等方法相比,所提出的KD树与半边结构融合的动态空间索引在处理近百万面片的数据文件时,去除冗余顶点用时11.93 s,拓扑重建仅仅需要2.87 s,大大减少了冗余顶点的去除时间和拓扑重建时间,并且有效支持网格曲面拓扑邻域信息的快速查询,查询时间在1 ms之内,远小于对比算法所用时间。实验结果表明:所提算法能够提高网格曲面冗余顶点去除效率和拓扑重建效率,实现网格曲面拓扑邻域信息的快速查询。

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

Abstract: 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.

Key words: STereo Lithography (STL) file format, K-Dimensional Tree (KD Tree), half-edge data structure, surface topology reconstruction, k-neighborhood query

中图分类号: