Parametrization Based Quad Meshing in Practical Applications

Surface representations are integral to computer graphics. There are many common types of surface representations that exist on a spectrum from unstructured to structured or from a low level to a high level of abstraction. Point clouds as captured by laser range scanners, for instance, occur near the bottom of this spectrum, whereas procedural models as created by highly skilled professionals in CAD systems can be counted amongst the most structured, most abstract surface representations.The more structured a surface representation, the broader the range of applications it is fit for. Hence, it is an ongoing effort in the field of computer graphics to find methods that transform surface representations of low structure and low level of abstraction into highly structured, more abstract representations.Quadrilateral (or quad) meshes lie somewhat in the middle of the spectrum of abstraction spanning from point clouds to procedural CAD models. Quad meshes are the preferred class of surface representation in several application domains such as modeling and animation in the entertainment industry. But even when quad meshes are merely used as an intermediate product in an effort to create an even more structured CAD representation, the quality and structure of the quad mesh carries over into the downstream representations derived from it. As a consequence, quad meshing has received a considerable amount of attention from researches in recent years and many quad meshing methods have been proposed. The most popular amongst those approaches are parametrization based quad meshing methods. These methods implement a three-stage pipeline where (1)~a cross field is synthesized on the input geometry, (2) an integer grid map, i.e. a parametrization guided by the cross field and inducing a quad mesh, is generated, and (3) the output quad mesh is traced in the integer grid map.The popularity of this family of methods is not only due to the great mesh quality these methods are capable of producing but especially due to the many versatile means of user control they offer (e.g. edge flow guidance or manipulation of irregular vertices). These means of control invite an interactive exploratory work flow where the user initially loads an input triangle mesh into the system and is then suggested a quad mesh by the remeshing system. The user then assesses this mesh, influences the system by one of the methods of user control it offers, is presented with a new quad mesh, and iterates this process until it converges to a satisfactory solution.Unfortunately, the implementation of such a work flow in practical applications is inhibited by two shortcomings: parametrization based quad meshing methods are quite sensitive regarding the quality of the input surface and their computation times easily reach minutes even for moderately complex meshes.In this thesis we tackle both of these shortcomings. We present a method to make parametrization based quad meshing robust against common types of flaws often encountered in the input meshes in practice, thus enabling direct quad meshing of surfaces without tedious pre-processing. This is achieved by reformulating the cross field synthesis as well as the parametrization stage in a scale-aware manner, thus effectively suppressing geometrical and topological noise and features that are too small to be represented in the output quad mesh.We also present a method to cope with degeneracies in the integer grid map that are commonly caused by those parametrization approaches that sacrifice validity guarantees on their output for the sake of much faster execution times. By enabling the use of these faster approaches, the quad meshing process can be sped up significantly.Finally, we present a framework to speed up parametrization based quad meshing specifically for interactive exploratory application scenarios. Using our framework we are able to handle highly complex input meshes with up to several millions of triangles at interactive rates. It is based on representing the input mesh at several levels of detail and propagating integer grid maps from coarser to finer levels while guaranteeing that the integer grid properties of the map are maintained