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

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

AGTB-RRT^(*):一种基于近似测地线避障策略的目标双向3D RRT^(*)路径规划算法

针对传统3D RRT^(*)全局路径规划算法存在的采样基数大、父节点重选计算量大、节点扩展盲目、搜索路径不平滑等问题,提出一种基于近似测地线避障策略的目标双向3D RRT^(*)路径规划算法(approximate geodesic target bidirectional RRT^(*),AGTB-RRT^(*)).首先,在双向目标点的连接路径上设置近似中位节点,并建立朝起点和目标点双向扩展的随机树,有效提高算法的搜索效率;建立基于单叶双曲面的启发式采样空间,有效减小采样基数和父节点重选计算量并降低内存占用.其次,对目标点和随机点进行阈值切换,并建立目标引力势场,有效降低节点扩展盲目性,提高算法的收敛速度.再次,对3D障碍物建立三角网格包络,并基于近似测地线方法使节点沿3D障碍物包络表面快速绕行,进而规划出一条代价小、速度快的局部避障路径.最后,采用B样条曲线拟合方法对整个生成路径进行优化处理,以得到一条平滑的最优可行路径.仿真实验结果验证了所提出AGTB-RRT^(*)算法在三维空间下用于路径规划的有效性和可行性.

三角网格模型上测地线算法的研究

对三角网格模型上测地线的算法进行研究,分为近似测地线算法和精确测地线算法,其中近似算法介绍经典的Fast Marching算法,精确算法以经典的MMP算法为主,并且对两种算法得到的测地线在准确度和时间复杂度上进行对比分析,得出实验数据,并对其应用进行简单介绍。