Lloyds energy minimization in the L p norm for quadrilateral surface mesh generation
Indirect methods recombine the elements of triangular meshes to produce quadrilaterals. The resulting quadrilaterals are usually randomly oriented, which is not desirable. However, by aligning the vertices of the initial triangular mesh, precisely oriented quads can be produced. Levys algorithm is a non-linear optimization procedure that can align points according to a locally defined orientation matrix. It minimizes an energy functional based on the L p distance. The triangulation of a set of vertices smoothed with Levys algorithm is mainly composed of right-angled triangles, which is ideal for quad recombination. An implementation of Levys algorithm based on numerical integration is presented. The implementation has the advantage of not modifying the edge meshes. It also features automatic calculation of the orientation angle. When used in combination with an indirect recombination algorithm, it can create quads of varying size and orientation. It has been tested on two-dimensional surfaces as well as globally parametrized three-dimensional surfaces. The results demonstrate an increase in the number of nodes having four neighbors and an improvement of the quads quality. The development took place in the framework of the Gmsh free software.
non-linear optimization clipped voronoi diagrams centroidal voronoi tessellations quad mesh generation