Efficient Foldover-Free Geometric Mapping Optimization

In computer graphics and digital geometry processing,geometric mapping transforms a geometric domain into another geometric domain.Geometric domain is usually represented by mesh model,so geometric mapping is a piecewise mapping consisting of linear or high-order mapping defined on each element.The task of computing geometric mapping is fundamental and essential,which is widely used in parameterizations,shape deformation,mesh optimization and simulation,etc.There is no zero or even negative volume in any natural material.Therefore,a geometric mapping is required to satisfy the locally foldover-free constraint.Computing foldover-free geometric mapping is usually formulated as a non-convex,nonlinear,constrained optimization problem.To solve the problem,various methods have been developed.However,there are still limitations.In this paper,a series of efficient methods are proposed to check,construct and optimize foldover-free geometric mapping.For piecewise linear mapping,if the initial mapping contains foldovers,we need to remove the foldovers and construct a foldover-free mapping.However,existing methods often rely on user inputs or cannot efficiently generate foldover-free and highquality results.In chapter three,we present an efficient method for computing locally foldover-free mappings with hard linear constraints.The method uses alternating iterations idea,which takes turns between the conformal distortion bound generation and monotonic mapping projection.Given a conformal distortion bound,the mapping projection process minimizes the distance from the mapping to the bounded distortion mapping space.After projection,the distortion of the updated mapping tends to be below the given bound,thereby significantly reducing foldovers.Since it is non-trivial to define an optimal bound,we introduce a practical conformal distortion bound generation scheme to facilitate subsequent projections.By alternately iterating the conformal distortion bounds generation step and the monotonically projection step,our method can fast compute high-quality and foldover-free mappings.Compared with existing methods,ours does not rely on additional inputs and is practically robust and efficient.If the initial mapping is foldover-free,more constraints or target energy can be added to meet more practical application requirements.For texture mapping,we can add the globally intersection-free constraint to obtain globally foldover-free parameterizations(bijective parameterizations),which can ensure one-to-one correspondence between 2D textures and 3D models.In chapter four,we propose a method to efficiently compute globally foldover-free parameterizations with low distortion on disk topology meshes.Our method relies on a second-order solver.To design an efficient solver,we develop two key techniques.First,we propose a coarse shell to reduce the number of collision constraints that are used to guarantee intersection-free boundaries.During the optimization process,the shell ensures the Hessian matrix with a fixed nonzero structure and a low density,thereby accelerating the optimization.The second is a triangle inequality-based barrier function that ensures non-intersecting boundaries.Our barrier function is C∞ inside the locally supported region and its convex second-order approximation is able to be analytically obtained.Compared to state-of-the-art methods for optimizing bijective parameterizations,our method exhibits better scalability and is about six times faster.The performance of our algorithm is comparable to state-of-theart locally foldover-free parameterizations.For piecewise high-order mapping,the mapping defined on each element is nonlinear,such as Bezier mapping.The elements present curved edges or surfaces by the non-linear mapping instead of straight edges and planes by the traditional linear mapping.The mesh is called a high-order curved mesh,which can approximate complexshaped boundaries with fewer elements than the traditional linear straight-edge mesh.Currently,higher-order curved meshes becoming more and more popular in the fields of graphics and engineering analysis due to their favorable numerical properties.For higher-order curved meshes,such as Bezier meshes,the Jacobian matrix is different everywhere in the entire element region.It is difficult to verify that a high-order mapping is foldover-free in the entire element region,which contains infinite points.In chapter five,we propose a novel algorithm to judge whether the Bezier mapping-based curved element contains foldover.Based on the relationship between the Lipschitz constant and the Hessian norm,the algorithm derives the Lipschitz constant of the minimum singular value of the Jacobian matrix by combining the differential properties of the Bernstein basis function.Using the Lipschitz constant,we calculate the lower bound of the minimum singular value over the entire domain,and then judge whether the mapping satisfies foldover-free in the entire domain by only checking on finite sampling points.Many experiments show that our method is robust and effective.