| Abstract |
We present a technique for computing piecewise linear approximations of geodesics on point set surfaces by min-
imizing an energy function defined for piecewise linear path. The function considers path length, closeness to the
surface for the nodes of the piecewise linear path and for the intermediate line segments. Our method is robust
with respect to noise and outliers. In order to avoid local minima, a good initial piecewise linear approximation
of a geodesic is provided by Dijkstra's algorithm that is applied to a proximity graph constructed over the point
set. As the proximity graph we use a sphere-of-influence weighted graph extended for surfel sets. The convergence
of our method has been studied and compared to results of other methods by running experiments on surfaces
whose geodesics can be computed analytically. Our method is presented and optimized for surfel-based repre-
sentations but it has been implemented also for MLS surfaces. Moreover, it can also be applied to other surface
representations, e.g., triangle meshes, radial-basis functions, etc. |