By David Bommes
In the last years the fascinating evolution of our digital age has resulted in the birth of countless applications that require or work on 3D geometric data. With 3D laser scanners, CAD systems and interactive sculpting tools, today the creation of digital geometry has become comparatively simple and widely available. However, the resulting unstructured shape discretizations are typically only sufficient for basic tasks as for instance visualization. The success of more demanding applications like product design, animation or simulation is strongly dependent on harder to obtain high-quality shape discretizations. One important class of widely applied discretizations consists of structure aligned quad meshes. On the one hand such quad meshes exhibit many highly desirable properties like e.g. an implicit globally smooth parameterization of the surface. But on the other hand automatic quad mesh generation is notoriously difficult due to global topological restrictions and thus requires very sophisticated algorithms.
My talk covers challenges as well as recent advances in quad mesh generation. Based on the idea of integer-grid maps (IGMs) I will show how to formulate the quad mesh generation problem as an instance of mixed-integer nonlinear programming. With the help of geometric insight it is furthermore possible to modify the formulation into a low-dimensional mixed-integer quadratic program, which is much better suited for modern branch-and-cut optimizer. The resulting algorithm does not only outperform previous approaches in terms of mesh quality but also provides rich user-controls for interactive mesh design.