Quadrilateral Surface Mesh Generation for Animation and Simulation

Besides triangle meshes, quadrilateral meshes are the most prominent discrete representation of surfaces embedded in 3D. Especially in sophisticated applications like for instance animation and simulation, they are often preferred due to their tensor-product nature, which induces several practical advantages. In contrast to their wide area of application, the available generation algorithms for high-quality quadrilateral meshes are still nonsatisfying compared to their triangle mesh counterparts. The main reason consists in the intrinsically more difficult topology, which requires global instead of local considerations. This thesis is devoted to novel algorithms that are specifically designed for the practical requirements in animation and simulation. First we will discuss important quality criteria, stemming from these applications. It turns out that, although the goal of both application areas is quite diverse, the quality criteria, which characterize a high-quality quad mesh, are identical. Apart from topological regularity, applications benefit from quadrilaterals with low distortion, well chosen curvature alignment to achieve good approximation and a coarse patch-structure in order to enable powerful mapping techniques as well as multi-level solver. Based on mixed-integer optimization and graph theory we propose carefully designed algorithms that are able to generate high-quality quadmeshes with the aforementioned properties in a fully automatic manner. Furthermore, the designer or engineer is still equipped with maximal control by the possibility of interactively influencing the automatic solution by means of additional high-level constraints.