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

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2177-2183.

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

王喆¹,高三红¹,²,郑慧英¹,²,李立春³

1. 北京跟踪与通信技术研究所，北京 100094
2.
3. 北京航天飞行控制中心，北京 100094

收稿日期:2013-02-23 修回日期:2013-04-16 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 王喆
作者简介:王喆(1988-)，男，河南濮阳人，硕士研究生，主要研究方向：并行计算、虚拟现实;
高三红(1965-)，男，河南焦作人，研究员，硕士，主要研究方向：计算机仿真;
郑慧英(1979-)，女，河南开封人，工程师，硕士，主要研究方向：计算机网络技术;
李立春(1978-)，男，河北元氏人，工程师，博士，主要研究方向：计算机视觉。
基金资助:
国家自然科学基金资助项目

Parallel Delaunay algorithm design in lunar surface terrain reconstruction system

WANG Zhe¹,GAO Sanhong¹,ZHENG Huiying¹,LI Lichun³

Received:2013-02-23 Revised:2013-04-16 Online:2013-09-11 Published:2013-08-01
Contact: WANG Zhe

摘要/Abstract

摘要： 三角剖分过程是影响三维重建系统实时性的瓶颈之一，为提高三角剖分速度，基于共享内存多核计算机设计并实现了并行Delaunay算法。该算法在分治三角剖分算法的基础上，通过改进子三角网归并过程及Delaunay三角网优化过程避免了并行计算中的数据竞争问题。利用月面仿真实验场真实地形数据在50万到500万不同规模的点云数据集上进行了实验，加速比最高可达6.44。除此之外，对算法复杂度、加速比以及并行效率进行了全面分析，并将算法实际应用于月面地形重构系统，实现了虚拟地形的快速构建。

关键词: Delaunay算法, 并行计算, 地形重构, 开放多处理, 多维树

Abstract: 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 500000 to 5000000 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.

Key words: Delaunay algorithm, parallel computing, terrain reconstruction, Open Multiple Processing (OpenMP), K-Dimension tree (KD-tree)

中图分类号:

TP311.1

王喆高三红郑慧英李立春. 月面地形重构系统中的并行Delaunay算法设计[J]. 计算机应用, 2013, 33(08): 2177-2183.

WANG Zhe GAO Sanhong ZHENG Huiying LI Lichun. Parallel Delaunay algorithm design in lunar surface terrain reconstruction system[J]. Journal of Computer Applications, 2013, 33(08): 2177-2183.

参考文献

[1] JET PROPULSION LABORATORY. Mars exploration rover [Z]. NASA Facts, 2005.
[2] VERGAUWEN M, M POLLEFEYS, L GOOL. A stereo vision system for support of planetary surface exploration [J]. Machine Vision and Applications, 2003, 14(1):5-14.
[3] GEORGE C, EMILY L, SHAN M. Demonstration of LMMP workflow system using cloud computing architecture [C]// SECLOUD’11, Waikiki, Honolulu, 2011
[4] BACH B, GEORGE C, RICHARD K, et al. Demonstration of LMMP (Lunar Mapping and Modeling) using Amazon’s elastic compute cloud [C]// SECLOUD’11, Waikiki, Honolulu, 2011
[5] JOHN J, LUCA C, CHRIS A, et al. Mattmann evaluating cloud computing in the NASA DESDynI ground data system[C]// SECLOUD’11, Waikiki, Honolulu, 2011
[6] GREEN P J, R SIBSON. Computing dirichlet tessellafons in the plane [J]. The Computer Journal, l978, 21:168-173.
[7] LEWIS B A, J S ROBIRTSON. Triangulation of planar regions with applications [J]. The Computer Journal, 1978,21:324-332.
[8] A AGGARWAL, B CHAZELLE, L GUIBAS, et al. Parallel computational geometry. Algorithmica, 3:293–327, 1998.
[9] M CHEN, T CHUANG, J WU. Efficient parallel implementations of 2D Delaunay triangulation with high performance ortran. In Proceedings of 10th SIAM Conference on Parallel Processing for Scientific Computing, 2001.
[10] T OKUSANYA, J PERAIRE. 3D parallel unstructured mesh generation. AMD, 220:109–115, 1997.
[11] N CHRISOCHOIDES, D NAVE. Simultaneous mesh generation and partitioning for Delaunay meshes. In Proceedings of the Eighth International Meshing Roundtable, pages 55–66, 1999.
[12] N CHRISOCHOIDES, D NAVE. Parallel Delaunay mesh generation kernel. International Journal for Numerical Methods in Engineering, 58:161–176, 2003.
[13] DANIEL K B, E B Guy, C KADOW. Engineering a compact parallel delaunay algorithm in 3D [C]. SCG’06, Sedona, Arizona, USA, June 5-7, 2006.
[14] 罗斌. 基于约束数据域三角剖分的高精度DEM快速生成技术及实现[D]. 西安:长安大学. 2006
[15] TAMMINEN M. Comment on quad-and octrees.Communications of the ACM,1984,30(3):204－212.
[16] PAUL G B, J S NORRIS, M W POWELL, et al. Multi-Mission activity planning for mars lander and rover missions[C]. IEEEAC. 2004.