一种三维拓扑信息提取的并行实现方法  

A Parallel Algorithm for 3D Topology Information Extraction

作　　者：王成彰[1] 郭立[1] 刘鹏[1] 于昊[1] 

机构地区：[1]中国科学技术大学电子科学与技术系,安徽合肥230027

出　　处：《通信技术》2013年第8期167-170,共4页Communications Technology

基　　金：国家自然科学基金(批准号:61071173)

摘　　要：针对三维拓扑信息提取算法数据量大,计算复杂的问题,提出了一种基于Reeb图描述的三维拓扑信息提取的并行实现方法。在已得到目标三角形网格的前提下,利用三维网格数据的顶点坐标和三角面关系,通过计算测地距离来构造莫尔斯函数,并根据顶点的三角面关系提取Reeb图;通过分析Reeb图提取计算过程中各步骤的耗时与并行性,对提取算法的关键模块进行并行优化。实验表明,经过并行化,在双核平台上的加速比可达到1.70。Aiming at the problems of large data amount and high computation complexity in 3D topological information extraction algorithm,an algorithm based on Reeb Graph is proposed.With the acquired triangular mesh,vertex geodesic distance is calculated by vertex coordinates and triangular correlation of 3-dimensional mesh data,which is employed to construct Morse function.And then 3-dimensional Reeb Graph could be extracted in accordance with the triangular relationship.Based on analysis of the parallelism and computing time for each step of Reeb Graph extraction process,parallel method is presented to accelerate the speed of the key modules of extraction algorithm.Experiments show that with parallel optimization of the algorithm modules,the speedup ratio on the dual-core processor could reach 1.70.

关 键 词：拓扑结构 REEB图 测地距离 莫尔斯函数 并行算法 

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