Quad Layouts – Generation and Optimization of Conforming Quadrilateral Surface Partitions
No Thumbnail Available
Files
Date
2014-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description