月面地形重构系统中的并行Delaunay算法设计  

Parallel Delaunay algorithm design in lunar surface terrain reconstruction system

作　　者：王喆[1] 高三红[1] 郑慧英[1] 李立春[2] 

机构地区：[1]北京跟踪与通信技术研究所,北京100094 [2]北京航天飞行控制中心,北京100094

出　　处：《计算机应用》2013年第8期2177-2183,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61173080)

摘　　要：三角剖分过程是影响三维重建系统实时性的瓶颈之一,为提高三角剖分速度,基于共享内存多核计算机设计并实现了并行Delaunay算法。该算法在分治三角剖分算法的基础上,通过改进子三角网归并过程及Delaunay三角网优化过程避免了并行计算中的数据竞争问题。利用月面仿真实验场真实地形数据在50万到500万不同规模的点云数据集上进行了实验,加速比最高可达6.44。除此之外,对算法复杂度、加速比以及并行效率进行了全面分析,并将算法实际应用于月面地形重构系统,实现了虚拟地形的快速构建。Triangulation procedure is one of the time bottle-necks of 3D reconstruction system.To increase the speed of triangulation procedure,a parallel Delaunay algorithm was designed based on a shared memory multi-core computer.The algorithm employed divide-and-conquer method and improved conquer procedure and Delaunay mesh optimization procedure to avoid data competition problem.Experiments were conducted on datasets with range from 500 000 to 5 000 000 gathered on the lunar surface simulation ground,and the speedup of the algorithm reached 6.44.In addition,the algorithm complexity and parallel efficiency were fully analyzed and the algorithm was applied in the lunar surface terrain reconstruction system to realize fast virtual terrain reconstruction.

关 键 词：DELAUNAY算法 并行计算 地形重构 开放多处理 多维树 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]