Toggle Quick Contact Bar

Quad Meshing

We offer a fully-automated, high-quality, robust, pure quad mesh generation algorithm developed by the Mesh Generation and Optimization (MGO) group from the RWTH Aachen University.

Quad mesh of a mechanical piece (input)

Mesher Highlights


Fully automatic

Our quad mesher is entirely automatic, providing users with a simple “one-click” API from input to quad mesh: all the parameters are automatically set up to provide a good output.

Fine-grained control is also possible, providing access for the user to many options such as:

  • size: the target edge length is the only parameter that has to be provided by the user, but a default value can be automatically deduced;
  • good approximation of sharp edges (automatic detection based on an angle bound, or manual);
  • preservation of input constrained vertices;

Our algorithm also offers better control than other methods over the valence of vertices, enabling to:

  • generate a mesh where all vertices are regular (valence 4), if the topology allows it;
  • set singularities manually (on vertices of the input triangle mesh).

Reliable

Quadrangular mesh generation is difficult and one of the key factors to judge the strength of a mesh generation algorithm is its robustness. The meshing algorithm is based on Mixed-Integer Quadratic Programming simplified by a complexity reduction algorithm and singularity separating conditions, making the approach introduced by the MGO group robust. Their experiments show that the reliability of the resulting algorithm does not only annihilate the main drawback of parameterization-based quad-remeshing but moreover enables a global search for high-quality coarse quad layouts.

An extensive nightly testsuite (testing both numerous input models and platforms) is maintained to ensure that the continuous improvements do not cause any regression.

High Quality

Smooth distortion distribution

Whereas most quad meshers are based on greedy techniques (such as using local flips), our quad mesher is based on a global energy minimization approach which automatically creates very smooth meshes.

Quad mesh of a character (right) (input, left)

Low singularity count

Vertices of a quad mesh with valence other than four are generally undesired. The global approach of our algorithm enables constructing quad meshes with much fewer singularities than other quad mesh algorithms.

Quad mesh of the fertility model. Ours (left) possess much fewer singularities than Instant Meshes’ (right) — Figure from Jakob, Wenzel, et al. “Instant field-aligned meshes.” ACM Trans. Graph.

Post-processing improvements

Post-processing mesh smoothing can be used to increase the quality of the quad mesh. Smoothing is designed to honor feature edges and constrained vertices that have been set ahead of the mesh generation process. It is furthermore possible to smooth only a user-defined subpart of the quad mesh. Automatic re-projection to the input geometry can be activated or not.

Customizable

Placement of feature vertices and edges

When the input has sharp edges, users may want to preserve the corresponding one-dimensional features through the meshing process, so that they appear in the output quad mesh.

Quad mesh without (left) and with (right) protection of input features.

Direction prescription

Directions can be drawn on the input mesh to indicate a desired orientation of the quadrangular elements.

Quad meshes over a square generated using user-specified direction fields (shown as red segments). Note that the user-specified fields are not defined everywhere; the rest of the field is constructed automatically to align with the boundary of the surface.

Alignment with the boundary

The default behavior of our quad meshing algorithm is to force alignment of the cross field with the input boundaries. Hence, the quadrangular elements follow the boundary geometry on the boundary “layer”, which can introduce distortion in the geometry of the quads compared to what it could be if only based on the curvature lines. One of the latest features of our quad meshing algorithm is that it can generate a quad mesh, aligned with principal curvature lines, or with a prescribed cross field, that does not align with the boundary of the input. The “boundary layer” is hence not as regular as the rest of the mesh, because it is cropped by the boundaries, but the “central” part of the mesh is not influenced by the geometry of the boundary.

Quad mesh (colored) generated with the “no boundary alignement” option. Boundary elements are not necessarily quads, but they follow the geometry of the input triangle mesh (wire frame).

Fine-tuning regularity

Thanks to its global formulation, the quad meshes produced by our algorithm already produce few singularities. In addition, explicit control over irregular vertices is provided: singular vertices (i.e. vertices with a valence higher or lower than 4) can be manually added or removed to move singularities to meaningful positions in the mesh.

Combination with CGAL


The IGM quad meshing algorithm is sensitive to degeneracies such as isolated vertices, self-intersections, or degenerate faces in the input mesh. The presence of these elements can also make the quad meshing algorithm fail. In addition, the quality of the output is related to that of the input triangle mesh. CGAL offers numerous tools to produce a high-quality input mesh adapted to the needs of the quad meshing algorithm.

  • Mesh Repair: removal of self-intersections, removal of degenerate faces, stitching of connected components, etc.
  • Mesh Pre-processing: automatic detection of features, triangular remeshing of the triangulated input surface, etc.
  • Mesh Generation: the quad meshing algorithm benefits from the input triangle mesh having high quality. CGAL offers tools to generate surface meshes from various types of inputs, or to remesh existing triangle meshes to improve the quality.
  • Mesh Post-Processing: once the quad mesh has been generated, the mesh processing tools of CGAL can be immediately applied.

Reparation of a mesh using CGAL’s hole filling algorithm.

To make the integration of the quad mesher with CGAL seamless, GeometryFactory has developed a CGAL-like API, and published the documentation as the IGM User Manual.

Continuous Development


Several improvements and new features are under development to satisfy customer requests.

Sizing field

It can be desirable to provide a sizing field defined over the domain to be meshed, instead of a constant target edge length. This feature is under development.

Robustness improvements

GeometryFactory and RWTH are constantly testing new models and inputs to detect issues and further improve the robustness of the process.

About


the Mesh Generation and Optimization group (RWTH)

The IGM Quad Meshing Algorithm was born within the RWTH’s Computer Graphics Lab, led by Prof. Dr. Leif Kobbelt, and more precisely within the Mesh Generation and Optimization group (MGO), then led by Prof. Dr. David Bommes, one of the most influential research teams in the domain of quadrangular and hexahedral mesh generation. Their research on quad mesh generation started in 2009 with the seminal works of Bommes et al. on Mixed-Integer Grid Optimization. Over the following years, this work has been gradually enhanced to yield one of the most powerful quad mesh generation algorithms.