Fast Geodesic Distance Query Based On High-dimensional Embedding

The geodesic distance is the shortest distance between any two points on the sur-face.Given a triangular grid,calculating the discrete geodesic distance on the triangular grid is also an important research topic in the field of computer vision and computer graphics.The previous work is mainly devoted to the area of single source all destina-tions,that is,given a source point,calculating the geodesic distance to all other vertices.For this problem,people have given many different ways to solve it,and it can be solved in linear time now.On the other hand,given any two points on the grid,it is also a com-mon problem to query the geodesic distance between these two points.For this problem,people have also proposed some algorithms.However,these algorithms either require a large storage space,or the accuracy is not ideal.How to provide a geodetic distance query algorithm that occupies a small storage space and is accurate enough is the core of the work of this article.In this thesis,we develop a novel method for fast geodesic distance query.The key idea is to embed the mesh into a high-dimensional space,such that the Euclidean distance in the high-dimensional space can induce the geodesic distance in the original manifold surface.However,directly solving the high-dimensional embedding problem is not feasible due to large number of variables and high non-linearity of the embed-ding sproblem.We overcome the challenges by two novel ideas.First,instead of taking all vertices as variables,we embed only the saddle vertices,which greatly reduces the problem complexity.We then compute a local embedding for each non-saddle ver-tex.Second,to reduce the large approximation error resulting from pure Euclidean embedding,we propose a cascaded optimization approach that repeatedly introduces additional embedding coordinates with a non-Euclidean function to reduce the approxi-mation residual.Using the precomputed data,our approach can determine the geodesic distance between any two vertices in near constant time.Computational results show that our method is more accurate than the other geodesic distance query methods.