Quad Layouts – Generation and Optimization of Conforming Quadrilateral Surface Partitions

Abstract

The efficient, computer aided or automatic generation of quad layouts, i.e. the partitioning of an object’s surface into simple networks of conforming quadrilateral patches, is a task that – despite its importance and utility in Computer Graphics and Geometric Modeling – received relatively low attention in the past. As a consequence, this task is most often performed manually by well-trained experts in practice, where quad layouts are of particular interest for surface representation and parameterization tasks. Deeper analysis reveals the inherent complexity of this problem, which might be one of the underlying reasons for this situation. In this thesis we investigate the structure of the problem and the commonly relevant quality criteria. Based on this we develop novel efficient solution strategies and algorithms for the generation of high quality quad layouts. In particular, we present a fully automatic as well as an interactive pipeline for this task. Both are based on splitting the hard problem into sub-problems with a simpler structure each. For each sub-problem we design efficient, custom-tailored optimization algorithms motivated by the geometric nature of these problems. In this process we pay attention to compatibility, such that these algorithms can be applied in sequence, forming the stages of efficient quad layouting pipelines. An important aspect of the quad layout problem is the complexity of the quality objective. The quality typically is a function of the layout’s structural complexity, its topological connectivity, and its geometrical embedding, i.e. of discrete, combinatorial, and continuous aspects. Furthermore, application-specific demands can be quite fuzzy and hard to formalize. Our automatic pipeline follows a generic set of quality criteria that are common to most use cases. The best solution to make possible the optimization with respect to more specific design intents is to include the user in the process, enabling them to infuse their expert knowledge. In contrast to prevalent manual construction processes our interactive pipeline supports the user to a large extent. Structural consistency is automatically taken care of, geometrically appropriate design operations are automatically proposed, and next steps that should be taken are indicated. In this way the required effort is reduced to a minimum, while still full design flexibility is provided. Finally, we present novel methods for the computation of geodesic distances and paths on surfaces – for standard as well as anisotropic metrics. These play a critical key role in several parts of our pipelines and shortcomings of available solutions compelled the development of novel alternatives.