Fast and Accurate Method for Finding Shortest Path and Distances on 3D Models.

What is it about?

Discrete geodesic problem is asking to find the shortest path between 2 points on 3D surfaces. This problem holds fundamental applications in computer graphics and vision. In this article, we propose a novel method to speed up the Discrete Geodesic Graph approach for solving this problem by up to 100x. This approach is capable of providing geodesic distances and paths with very high accuracy, reaching $10^{-7}$ precision accuracy easily. Discrete Geodesic graph approach builds a graph consisting of the mesh vertices as nodes. The edges in this graph connect each node to the nearest nodes in a local region on top of the mesh. Its weights are the geodesic distances between the 2 vertices that it connects.

Featured Image

Why is it important?

Discrete Geodesic is a fundamental problem in computer graphics and vision with varying applications, from shape matching, texture mapping, surface parametrizations and many others. This new method proposes solution that is up to 100x faster than previous approaches for finding highly accurate solutions to this problem.