One of our goals is to develop efficient and robust algorithms for meshing surfaces and volumes. We are especially interested in meshing surfaces with quadrangular elements and meshing volumes in hexaedral elements (as shown in the figure).
The quad or hex elements are oriented along vector fields (e.g., main directions of curvature). We have developed a formalism to manipulate these vector fields, taking into account their N-fold symmetry and controlling their topology/singularities [ACM TOG 2008]. We have also developed an algorithm that lets the topology emerge [ACM TOG 2009].
From these vector fields, we reconstruct a quad mesh using two alternative techniques:
Parameterization: A possibility consists in integrating the vector field to obtain parametric coordinates. Thus we have developped a periodic global parameterization method that generates a coordinate system aligned with these vector fields [ACM TOG 2006], and a spline-fitting algorithm based on this global parameterization [EG/ACM SGP 2007].
Sampling: Another possibility is based on sampling theory. We have studied algorithms to minimize the quantization noise power (Lloyd relaxation). We proved that the quantization noise power is a function of class C2, and designed a Newton-based algorithm with faster speed of convergence [ACM TOG 2009]. To apply this algorithm to surface meshing, we developed a fast and exact method to compute a Restricted Voronoi Diagram [ACM/EG SGP 2009], i.e. the intersection between a 3D Voronoi diagram and a surface. We generalized the quantization noise power to higher momenta, and defined Lp Centroidal Voronoi Tesselation, a sampling algorithm that produces cubical Voronoi cells [ACM TOG/SIGGRAPH 2010].