LAUSR

Geodesics measure the shortest distance between points on curved surfaces and are a fundamental tool in digital geometry processing. Although there are many algorithms for computing geodesic paths, most of them are designed for a single type of geometric domain (typically a triangle mesh), thus diminishing its practical usage. In this paper, we propose a general framework for computing geodesic paths for various geometric domains, including meshes, point clouds, implicit surfaces and parametric surfaces. Our key idea is to decouple geodesic computation from the type of the input surfaces. Discretizing the initial path by a sequence of points{x_i}, i=1,2,…,n that can only move on the surface, we minimize H(||x_i-x_(i+1)||), i=1,2,…,n. We show that the point sequence yielded by our approach is also a minimizer of the traditional geodesic length function, and the points are evenly spaced along the path. Our method encodes 3D geometry by signed distance functions (SDF) and can work for all types of input. We also propose a simple yet effective strategy to generate initial paths. We demonstrate the advantages of our methods over the conventional geodesic path algorithms in terms of accuracy, performance and scalability. Finally, we show that our method can be extended to solve general minimal-cost path problem.