三角网格表面任意两点间并行近似测地线算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (10): 197-200.

• 图形、图像、模式识别 • 上一篇下一篇

三角网格表面任意两点间并行近似测地线算法

于方

包头师范学院信息科学与技术学院，内蒙古包头 014030

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-04-01 发布日期:2011-04-01

Parallel approximate geodesic path algorithm on triangular mesh

YU Fang

School of Information Science and Technology，Baotou Normal University，Baotou，Inner Mongolia 014030，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-01 Published:2011-04-01

摘要/Abstract

摘要： 为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销，提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径，并用源分割法映射子网格数据；所有处理器并行执行，对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作；最后基于局部细化后的细分图并行，求得所有点对间的近似测地线长度和路径。实验结果表明，该并行近似测地线算法能够有效降低求解该类问题的计算时间，计算效率大大提高。

关键词: 三角网格, 近似测地线, 并行算法, 局部细分法

Abstract: To reduce time cost of computing all pairs shortest path on triangular mesh，a parallel approximate geodesic path algorithm base on local-subdivision algorithm is presented.Two pairs initial shortest path is computed by using matrix-multiplication parallel shortest path algorithm and adopting source-partition method to map sub-mesh data for every processor.Then all processors subdivide edges of owned pairs’ initial shortest path neighborhood triangular faces concurrently，and get a new approximate shortest path base on this subdivision graph at last.The experimental results show that using this parallel approximate shortest path algorithm can reduce computing time efficiently and improve computing efficiency greatly.

Key words: triangular mesh, approximate geodesic path, parallel algorithm, local-subdivision

于方. 三角网格表面任意两点间并行近似测地线算法[J]. 计算机工程与应用, 2011, 47(10): 197-200.

YU Fang. Parallel approximate geodesic path algorithm on triangular mesh[J]. Computer Engineering and Applications, 2011, 47(10): 197-200.

[1]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[2]	赵云成，王琳，盛步云，赵飞宇. 综合曲率约束的在线网格模型分割方法研究[J]. 计算机工程与应用, 2020, 56(16): 176-182.
[3]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[4]	陈亚中1，李振军1，李荣华1，毛睿1，乔少杰2. TSCAN：利用并行策略改进的图结构聚类算法[J]. 计算机工程与应用, 2019, 55(1): 76-83.
[5]	王德政1，张益农1，杨帆2. 基于MapReduce的并行PLS过程监控算法实现[J]. 计算机工程与应用, 2018, 54(24): 61-65.
[6]	孙劲光1，吴素红2. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217-222.
[7]	叶丽斐，黄常标，杨儒骁. 复杂三角网格模型刀具组合优化加工研究[J]. 计算机工程与应用, 2016, 52(21): 235-240.
[8]	肖和，杨旭静，郑娟. 离散三角网格模型顶点法矢量估算[J]. 计算机工程与应用, 2016, 52(19): 196-200.
[9]	喻津1，周浩杰2，柴志雷1. 一种基于众核架构的稠密光流并行计算方法[J]. 计算机工程与应用, 2016, 52(16): 186-191.
[10]	曾博1，2，雷友诚1，王丛知2，邱维宝2，冯歌2，曾成志2，杨戈2，郑海荣2. 基于CUDA的声辐射力弹性成像算法研究[J]. 计算机工程与应用, 2015, 51(18): 249-254.
[11]	李敏1，2，宋曰聪1，吴斌3，彭保3. 基于Beowulf机群中改进粒子滤波的3D人体运动跟踪[J]. 计算机工程与应用, 2015, 51(14): 17-22.
[12]	林俊锋，黄常标，祁杨停. 三角网格模型分治加工中区域分割算法的研究[J]. 计算机工程与应用, 2015, 51(12): 184-188.
[13]	张伟，赵云飞. 基于三角网格构建的扫描测头半径三维补偿[J]. 计算机工程与应用, 2014, 50(4): 262-270.
[14]	马献德1，谢小峰2. 三角网格曲面上离散曲率改进算法[J]. 计算机工程与应用, 2014, 50(13): 196-200.
[15]	王艳艳1，惠丽峰1，罗晓锋2，张荣国3. 三角网格顶点重要度的自适应Loop细分算法[J]. 计算机工程与应用, 2014, 50(13): 201-204.

三角网格表面任意两点间并行近似测地线算法

Parallel approximate geodesic path algorithm on triangular mesh

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics