点云模型上近似测地线的计算

为了有效计算点云模型上任意两点间的近似测地线,将点云模型沿着直角坐标系中三坐标轴方向进行空间栅格划分后,建立表示点云模型的带权图,采用Dijkstra算法计算带权图上任意给定两点间的最短路径作为初始测地线;然后通过使能量函数最小化,用共轭梯度方法对初始测地线迭代优化,计算得到点云模型上任意给定两点间的近似测地线。该算法无需对点云模型进行网格化,无需对点云模型进行局部或全局的曲面重建,适合大规模点云模型上测地线的计算。

Computation of approximate geodesics on point cloud

In order to compute approximate geodesic efficiently between two points on point cloud, a weighted graph was constructed by splitting point cloud along the Cartesian coordinate axes, thus initial approximate geodesic between any two given points could be computed out using Dijkstra's algorithm. Then the conjugate gradient method was adopted to minimize the energy function defined; finally, approximate geodesic could be obtained after some iterative steps. This proposed algorithm avoids meshing or reconstructing the point cloud to be local or global surface, and it is suitable for computing geodesic on large scale point cloud.