Mesh Cutting For Low-Distortion Parameterization

Computer graphics has been rapidly developed in recent years,and many graphics technologies are widely used in various areas from industrial design to daily life.Some of the latest technologies,such as 3D printing and autopilot,need to process a large amount of 3D mesh data,thus digital geometry processing plays a very important role.One of the basic problems is how to calculate a low-distortion parameterization of a mesh.For a closed mesh,the distortion of parameterization is closely related to the position of the cut If the position of the cut is appropriate,the final parameterized distortion will be low;if the cut position is not good,i.e.the cut does not pass through some extrusive areas,it will result in higher distortion of the parameterization.This dissertation focuses on how to cut a cdosed mesh into disk-topology.The goal is to reduce the isometric distortion of the subsequent planar parameterization while keeping the cut shorter.Since the cut must pass through some special areas so that the distortion can be reduced,the main idea of this dissertation is to detect some points that the cut must pass through,called distortion points,and then construct a cut connecting these distortion points.First of all,this dissertation introduces a sphere-based mesh cutting method that can calculate high-quality cuts to generate planar parameterizations of low isometric distortion.It has been observed that spherical and planar conformal parameterizations have similar distortion distributions in the extrusive regions,and these regions result in high isometric distortions in parameterizations.Based on this observation,the method uses the spherical parameterization of the input mesh to guide the construction of the cut.After the input mesh is parameterized onto the sphere as conformal as possible,a divisive-type hierarchical clustering method is used to find the distortion points in the high isometric distortion regions,and the cut can be obtained by connecting these distortion points.This approach produces better cuts than previous methods,resulting in lower isometric distortion.The dissertation demonstrates the effectiveness and practical robustness of the proposed method over a dataset of more than 5000 meshes,which are parameterized by two existing parameterization methods to generate low isometric distortions.Mesh parameterization usually requires low isometric distortion,and the edge path that cuts the closed mesh into a disk topology should pass some distortion points;other-wise,the parameterization will have high isometric distortion.In order to further study how to find the distortion point,this dissertation proposes a method to automatically detect the distortion point using a voting strategy.The method involves two parts:the generation of candidate distortion points and the voting of candidate distortion points.Given a closed triangle mesh,repeat the following three steps to generate candidate distortion points:(1)Randomly cut the input mesh into a disk-topology mesh;(2)Cal-culate an as-conformal-as-possible planar parameterization;(3)Using the hierarchical clustering method to detect the distortion points.Finally,the final distortion points are generated by voting.The effectiveness of the algorithm in various closed meshes for zero genus and high genus is demonstrated.Compared with other state-of-the-art methods,this method shows stronger practical robustness in the detection of distortion points.At the same time,the distortion points produced by this method can be used for three subsequent applications,including low distortion planar parameterization,semi-automatic landmark correspondence,and isotropic remeshing.Since the above methods find the distortion points,and the cuts passing through these points will not lead to high distortion,this dissertation continues to study how to construct the cut as short as possible.This problem can be formulated to a classic Steiner tree problem,by considering the mesh itself as an undirected graph with the dis-tortion points as the terminals.Thus,the goal is to find a minimum Steiner tree passing through these terminals.Since this problem is an NP-hard problem,and some heuristic algorithms cannot find the optimal solution,this dissertation adopts and improves a ge-netic algorithm,which approximates the optimal Steiner tree problem in a short time,and results in a shorter cut.Compared with the previous heuristic algorithms,it can be observed that the cut found by this method is shorter and the error with the optimal solution is smaller.