基于红黑树的STL数据快速拓扑重建算法  

An Efficient Algorithm for Topological Reconstruction of STL Data

作　　者：安涛[1] 戴宁[1] 廖文和[1] 袁天然[1] 

机构地区：[1]南京航空航天大学,南京210016

出　　处：《机械科学与技术》2008年第8期1031-1034,共4页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家高技术研究发展(863)计划项目(2005AA420240);江苏省科技攻关项目(BE2005014);南京市科技发展计划项目(200504022);南京市医学科技发展计划项目(ZKX0420)资助

摘　　要：STL文件是一种应用广泛的三角网格表示文件,其中拓扑结构的构建直接关系到后续应用的效果。本文提出的基于红黑树的STL文件快速拓扑重建算法以红黑树为基础数据结构,采用以三角片为单位的思想,将冗余点去除与拓扑结构的建立相融合,完成了对STL文件的半边拓扑结构的快速重建,同时还保证了良好的可扩展性。经实例测试,该算法可以高效、稳定的完成STL文件的拓扑重建工作。How to efficiently reconstruct the topological structure of a large amount of STL data is a bottle-neck in reverse engineering. In this paper, we present a topological reconstruction algorithm based on red-black tree. The algorithm takes the triangular facet as a processing unit. Deleting the redundant vertexes and searching the neighbors are integrated into one process. It also possesses good extendability. The algorithm has been tested with many examples. All results show that it is both efficient and stable.

关 键 词：STL文件 拓扑重建 三角面片 红黑树 

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