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