Key Technologies From Approximate Geodesics To Geodesic Voronoi Disagrams

In geometry,the geodesic distance is the shortest distance connecting two points on a surface while the path connecting two points is called geodesic path.Geodesic is the local shortest path of two points in curved space.It is considered as the extension of straight lines in curved space.Geodesic is a very important intrinsic quantity on surfaces.As a classic problem in computational geometry,it has great significance in the fields of science and engineering including computer graphics,digital healthcare,motion planning,industrial manufacturing,and deep learning.As the "Big Data Era" arrives,people need geometry processing algorithms to deal with a large amount of 3D data with higher efficiency and robustness.Although the geodesic problem has received a great deal of attention,how to solve the geodesic problem quickly and precisely on large-scale 3D models is still one of the key topics to be solved in the field of digital geometry processing.In the era of big data,geodesic computation using exact algorithms is relatively time-consuming.In most applications,people usually use approximate algorithms to report geodesic distances as efficiently as possible under the premise of ensuring accuracy.The current research focuses on how to find a flexible approximate geodesic algorithm that can achieve a good balance between accuracy,time,and memory usage.This dissertation studies how to efficiently and robustly report approximate geodesic distance(field)on surfaces including smooth surfaces and triangular mesh surfaces.Based on the proposed geodesic method,we explore how to efficiently construct approximate Voronoi diagrams on triangular surfaces.The main innovations and contributions of this thesis are as follows:(1)Geodesic distance fields on triangular surfaces based on the improved graph methodThe graph method based on Steiner point insertion is a classical method for computing the geodesic distance field on triangular meshes.It has got tons of attention due to its simple and easy error control.However,computational complexity of this kind of method increases sharply with the number of inserted Steiner points.In this dissertation,referring to the filtering rules in exact geodesic algorithms,we innovatively propose a filtering strategy for redundant events on graphs,which effectively solves the problem.At the same time,our method constructs a Steinerpoint graph that partitions the surface into mutually exclusive tracks,called geodesic tracks.It is helpful in increasing the accuracy in back-tracing shortest paths and extracting geodesic isolines.The framework can be extended to a wider class of geodesic variants,such as geodesic with non-constant density functions and/or anisotropic metrics,etc.(2)Construction of approximate geodesic Voronoi diagram on triangular meshesIn past research,people often applied exact geodesic algorithms to construct geodesic Voronoi diagrams(GVDs)on meshes.Since these exact algorithms need to spend massive time and memory,it has become a stumbling block of constructing geodesic Voronoi diagrams and further practical applications.In order to solve this problem,instead of using exact algorithms to obtain geodesic distance information,we construct graphs using Steiner points placed on mesh edges to report geodesic distances.It decreases the superfluous operations of geodesic distances to improve the efficiency of GVD construction in time and memory.Since geodesic Voronoi diagrams are constructed based on approximate geodesic distances,it can well balance the accuracy and time consumption by inserting Steiner points on triangle edges.In addition,we utilize the local Apollonius diagrams with weighted Steiner points to partition mesh triangles and extract hyperbolic/line segments for encoding complicated bisector structures of GVDs.(3)Geodesic paths on sweep surfaces based on the optimization methodWe propose a new method to compute geodesic paths based on an optimization strategy for sweep surfaces.The method inherits and develops the spirit of progressive shortening the curve.When the users specify the two endpoints(rather than "one point,one direction")on the sweep surface,the energy function is the sum of squared lengths of the polyline between two points.The algorithm establishes the energy function in the parameter domain rather than in Euclidean space.By repeatedly reducing the squared energy,the path becomes shorter and shorter.The algorithm terminates when the length difference between two successive iterations is less than an error tolerance.Compared with other related methods,the algorithm has advantages in error control,time efficiency,and so on.In addition,we extended the framework to geodesic spiral curves,path evolution in simulation and achieved excellent results.