In many practical applications quadrilateral meshes are preferred over triangle meshes, two prominent areas being animation and simulation. However, the quality requirements are typically very strict such that fully automatic quadmesh generation remains a hard task. Therefore even today many quadmeshes, especially those in cutting edge applica-tions, are designed manually by experts equipped with the indispensable knowledge and experience. Studies uncovered that in many of todays workflows the costs of meshing are extremely high, ranging up to 80% of the total costs [MTTT98].
In the following two sections we will review two of those workflows in order to identify their quality requirements. The overall goal is the design of either fully automatic or alternatively semi-automatic quadmesh generation algorithms which are on the one hand able to meet the strict quality requirements and on the other hand greatly speedup the design process and thus reduce the mesh generation costs.
τ = (80,1473)
non-regular
τ = (16,267)
valence semi-regular
τ = (16,50)
semi-regular
τ = (4,1)
regular
Regularit y Flexibilit y
2.2.1. Animation
Today quadrilateral meshes are the state-of-the-art geometry representation in anima-tion. One reason is that most animation and rendering systems are based on subdivision surfaces (see [ZS00] for details) where the quadmesh is used as the so called control mesh, which represents the discrete DOF’s of the smooth surface in a geometrically reason-able way. The typically applied Catmull-Clark subdivision scheme generalizes bi-cubic uniform B-spline surfaces to arbitrary topology and is very well suited as a high-quality representation for smooth surfaces. By restricting the control mesh to regular quadmesh topology, bi-cubic uniform B-spline surfaces are automatically reproduced. In this spe-cial case of a regular control grid, the surface quality is optimal and consequently from a topological point of view, even though the handling of arbitrary topology is possible, the quadmesh should be as regular as possible.
The topological simplicity is often in conflict with geometric requirements. Maybe the most important one is that the quad elements have to be oriented carefully in order to well capture the local curvature. More precisely, in parabolic regions where the surface is bent in a single direction, a nice curvature distribution can be achieved only if the quad grid is aligned to the principal curvature directions (cf. [D’A00]) . A special case with infinite curvature in one direction are sharp creases which can be handled by an extended set of subdivision rules but again only if the edges of the quadmesh are well aligned, i.e. the sharp crease is explicitly represented by edges in the quadmesh.
In the animation community it is well known that irregular vertices (similarly non-quad faces) and badly oriented or heavily distorted non-quad elements are the main sources of artifacts that pop up in the rendering. Obviously, dynamic geometries like, e.g. , the face of a talking person are even more critical than their static counterparts since artifacts have to be prevented for many different configurations. Accordingly designers spend lots of work for puzzling out highly optimized so called “edge flows” that facilitate artifact-free animations.
Moreover, animation systems heavily exploit mapping techniques to decouple the rough geometric description from high frequency details. Most prominent examples are texture and displacement mapping techniques which are applied in order to rep-resent high frequencies in material as well as in geometry. A well chosen quadmesh
is perfectly adapted to such mapping tasks, since a quad can be naturally mapped to a two-dimensional array which perfectly fits into todays memory architectures. Thus, from this point of view it is highly desirable to work with quadmeshes which are semi-regular, i.e. meshes that can be partitioned into a few regular patches of rectangular shape, acting as mapping domains.
Altogether, to be useful in animation, a quadmesh has to be a good compromise of topological simplicity (semi-regular) and geometric approximation (element distortion, curvature orientation, feature preservation, ...). Unfortunately the violation of a single criterion makes the mesh useless, which explains the manual design pipelines still often chosen in practice.
Today a typical mesh generation process consists of three steps. In the first step an artist designs a new object, e.g. a character, and builds a prototype out of clay. In the second step, a digital model is captured by a 3D laser scanner in form of an un-structured and noisy triangle mesh. Once such a digital representation is available, a designer manually works out a coarse quadrilateral patch layout which on the one hand has to be well aligned to the structure and on the other hand leads to a semi-regular mesh. In this step the designer incorporates her expert knowledge by placing irregular vertices away from qualitatively critical areas that will undergo large deformations in the planned animation sequences. Finally the coarse patch layout is refined regularly to a semi-regular mesh of adequate sampling density.
The task we are facing in this thesis consists in the simplification of the third step, i.e. the conversion from a low-quality triangle mesh to a high-quality quadrilateral mesh suitable for animation. It is questionable whether or not this step can be ever fully automatized, since a well chosen mesh contains many fuzzy aspects that are hard to formalize or to “correctly” weight against each other. Therefore the holy grail of mesh generation will be an algorithm which on the one hand is able to generate optimal results w.r.t. to a specifically chosen quality metric but on the other hand still allows for simple and time efficient high-level user control in cases where this quality metric does not lead to the structure that a human designer prefers due to whatever reason.
2.2.2. Simulation
As discussed in the introduction, in simulation the main goal is to accurately predict the physical behavior of digitally represented objects. In this context the task of meshing is two-fold, since on the one hand it is essential to accurately represent the geometry of the object itself, while on the other hand the result of the simulation has usually to be accurately represented by the same mesh. To illuminate the importance of the first aspect imagine a thin-shell simulation of e.g. a car body. The mathematical formulation of such a physical system contains second derivatives of the surface geometry itself and thus might be strongly influenced by a naive non-smooth discretization. The second as-pect can be understood by investigating a simulation with a simple geometry like e.g. a cube. Here the geometry itself does not require a finely tessellated mesh, however, the simulation might necessitate a (locally) denser mesh to stay within an acceptable error tolerance. One example for such a setting would be heat propagation on a simple object but with complicated boundary conditions.
A successful trend in engineering, called Isogeometric Analysis [HCB05], consists in integrating Computer-Aided Design (CAD) and Finite Element Analysis (FEA) into a single process based on Non-Uniform Rational B-Splines (NURBS). One advantage of NURBS is that they can easily handle different kinds of refinements that are impor-tant in practice. The first option to achieve a more accurate function space consists in refining the control mesh itself, a so called h-refinement. Such a mesh refinement can be done either globally with B-Splines or locally by using a T-Spline generaliza-tion [SZBN03]. The second way to achieve a more expressive funcgeneraliza-tion space, which is called p-refinement, consists in increasing the degree of the polynomial basis functions.
Due to its tensor-product nature such a p-refinement is an easy task within a structured quadrilateral mesh, while it is extremely complicated in an arbitrary unstructured mesh.
Indeed, in our case of surfaces, a single NURBS-patch is represented by a regular control quadmesh. Although the overall task in simulation is quite different from the one in animation, interestingly the quality requirements turn out to be quite similar.
As before, a well chosen orientation of the quads is extremely important to on the one hand accurately capture the geometry itself and on the other hand capture the charac-teristics of the underlying partial differential equations (PDEs). The same holds for the preservation of sharp creases. In animation a “good shape” of the individual quads is
important to avoid visual artifacts, while in simulation a good shape is essential for the accuracy of the solution as well as for the conditioning of the discretized operators.
Today’s most powerful solution approaches are adaptive in the sense that they start with a very coarse representation and then locally refine the mesh where it is required until a given target accuracy is reached. Such adaptive approaches strongly benefits from a semi-regular mesh that consists of a small number of well aligned patches and consequently a small number of initial NURBS patches.