Efficient Geometry Optimization Based On Gradient Field

Among the many problems involved in Computer Graphics,solving a linear sys-tem has always played an important role and is an indispensable part of the solution algorithm.Although most problems solve sparse linear equations,as date dimension continues to increase,it is still a challenge to find the solution of large sparse linear system,especially in terms of running memory and running time.And when solving optimization related to gradients,the optimization variables are usually function values,not gradients values,which makes the processing not scalable.Because we have to con-vert function values into gradient values.In this paper,a new and novel algorithm based on gradient field is proposed.It does not need to solve linear equations and directly get the gradient values of the correspond-ing functions.Finally,the original function values are restored according to the gradient values,and can get the same precision compared with the solution of solving linear sys-tems directly.Because we do not solve large sparse linear system in the solving proce-dures,the algorithm is highly efficient.This paper starts from two problem applying this algorithm.One is computing local barycentric coordinates in the two-dimensional or three-dimensional region given control points;The local barycentric coordinates are re-quired to minimize the total variation of the barycentric coordinates functions which sat-isfy partition of unity and linear interpolati on and other properties.The other is geodesic distance computation in the two-dimensional and three-dimensional manifold;The com-putation of geodesic distance is to solve corresponding Eikonal Equation.The objective functions involved in these two problems are related to the gradients,so both problems can be transformed into constrained optimization problem with gradient variables,and can be efficiently solved by using ADMM algorithm.Because the ADMM algorithm and the problem itself have a separable structure,we can highly parallel process the algo-rithm.And after getting the corresponding gradient field,we apply a breadth-first search algorithm to recover the corresponding function values,and this operation can also be paralleled.Overall we proposed an efficient and highly parallel algorithm to solve the geometric problems,and do not need to solve any large sparse linear system equations in this process.