STL数据快速拓扑重建关键算法  

Efficient Algorithm of Topological Reconstruction for STL Data

作　　者：戴宁[1] 廖文和[1] 陈春美[1] 

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

出　　处：《计算机辅助设计与图形学学报》2005年第11期2447-2452,共6页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2005AA420240);南京市医学科技发展计划(ZKX0420)

摘　　要：在反求工程中,散乱数据点云的曲面重构常采用三角网格模型,建立三角网格之间拓扑关系的速度是影响曲面重建效率的关键因素之一 .本文提出了基于V-F结构的平衡二叉树(AVL)顶点聚合算法,简化数据文件的存储容量至原来的18%～25%,并有效地去除了大量冗余数据点;采用虚AVL的快速邻边搜索优化算法,实现了相邻半边的快速搜索,高效地构建半边拓扑结构,最后通过各种零件重建速度的比较说明本文方法是高效的、可扩展的 .How to efficiently reconstruct the topological structure of a large number of STL data is a bottle-neck in reverse engineering. In this paper an integrated vertexes algorithm of AVL tree is introduced based on the V-F structure to delete a large number of redundant vertexes and reduce the size of data file up to 18%-25% of the original one. Then, an optimal search algorithm based on virtual AVL tree is conducted to efficiently reconstruct the half-edge topological structure. Finally, some test examples show that the proposed algorithm is both efficient and extensible.

关 键 词：STL 拓扑 半边结构 AVL树 V—F结构 

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