Output details

Geodesic computation on implicit surfaces

Originality: A geodesic is defined as the shortest path between two arbitrary points on a surface. It is an important metric for curved shapes, such as an animated human character. To date, little research has been undertaken tackling the problem of geodesic computation on point clouds, such as those produced from 3D acquisition devices, e.g. laser scanners. The main challenge is that scattered points do not explicitly define a coherent surface, making geodesic computations difficult. Our work presents a solution to this problem and presents an algorithm that can compute geodesic curves on point clouds considerably faster than existing methods.

Significance: The main contribution is that our proposed algorithm can finish the geodesic computation of one source to all destinations in a polynomial time complexity, which is very fast. Due to the high computational cost from existing animation techniques, efficiency with a fundamental algorithm like this offers a significant time saving in an industrial context. Since 3D scans are now available for ordinary users, there is a rapid increase in point cloud datasets available on the internet which require modelling, de-noising and editing within tight budget and time constraints. As geodesic computations are an essential intrinsic representation of the underlying geometry, many geometry processing methods will benefit from our work.

Rigour: In this research, we applied the well-established geodesic curvature flow to discrete geodesic computation on point clouds. The development has been supported by a thorough review of existing literature. To evaluate the effectiveness of our algorithm, we give the error bounds of the proposed algorithm and the estimation of the computational complexity. Experiments and analysis also demonstrated the effectiveness of our algorithm. In addition, different numerical cases have also been examined to ensure the correctness of the development.