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

A Parallel Algorithm for 3D Topology Information Extraction

针对三维拓扑信息提取算法数据量大,计算复杂的问题,提出了一种基于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.