[PhD proposal] Improve global parameterization algorithms

Title: Improve global parameterization algorithms

Supervisor: Dmitry Sokolov ( dmitry.sokolov@univ-lorraine.fr )

Hosting team: PIXEL ( https://pixel.inria.fr )

Grant type : Competing for a doctoral contract of the University of Lorraine

Application deadline: 21/05/2020


Key words:

Geometry processing, meshing


Topic details:

Our challenge is to build automatic hexahedral meshing solutions, which compare effectively with handmade models in terms of quality, but at the advantage of huge savings in overall time thanks to the automation. Mesh generation is an important step in the technical analysis process, often neglected to privilege development of solvers. Business analysis shows that it now represents a bottleneck for the development and adoption of numerical simulation in the industry. A specific focus of the project is therefore put on the interaction between the research and the industrial partners who are committed to beta-test and validate the results. We are planning to confront research results with industrial needs, and orient the research axes toward meshes proven to be useful for the industry.

In spite of all past setbacks in developing automated hexahedral meshing methods, to be compared with the maturity and efficiency of tetrahedral meshing approaches, the expectations and needs of the numerical simulation world for efficient hexahedral methods are still extremely high.

A new and original idea to generate hexahedral meshes was proposed recently [Sokolov2016, Ray2018]. It comes from the observation that good quality hexahedral meshes look like a deformed grid almost everywhere. The idea of global parameterization is to build a transformation f from the domain to a parametric space, where the deformed domain can be meshed by a regular grid. The inverse transformation f -1 applied to this grid produces the hexahedral mesh of the domain, aligned with the boundary of the object. The strength of this approach is that the transformation may admit some discontinuities. Let us show an example on Figure 2: we start from a tetrahedral mesh (left) and we want deform it in a way that its boundary is aligned with the unit grid. To allow for a singular edge (valence 3) in the output (right), the input mesh is cut open along the highlighted faces and the central edge is mapped onto a grid line (middle). The regular integer grid then induces the hexahedral mesh with the desired topology.

Global parameterizations are constructed in two steps: the Frame Field (FF) step defines the orientation of the grid at each point of the domain, and the Cube Covering (CC) step generates a global parameterization that will align the final mesh with the orientation (FF) defined in the first step. When both steps succeed, the result is a very regular full hexahedral mesh. Unfortunately, the FF step may generate an orientation field with a topological structure (its singularity graph) that is not valid for the second step, and the CC step often generates invalid mappings with (locally) negative Jacobians. Our objective is to improve the quality and robustness of these two steps.

Organization of the project:

The project will be split into three main parts:

  • Months 1-9: Locally integrable Frame Fields. Frame Fields are actually generated by a heuristic that minimizes the field rotation; it seems fair to minimize the bending of the deformed grid. However, it can produce singularity graphs from which it is impossible to derive a valid parameterization. In fact, valid singularity graphs are extremely constrained: the only valid singularity curves are following one direction of the frame field, and the two other directions define a 2D frame field that is singular on the singularity curve. This constraint can be enforced a posteriori by combinatorial optimizations [Li2012], but this strategy is only local. We want to study an alternative approach that will incorporate the integrability constraints directly during the field generation. The frame field optimization basically propagates inside the domain the constraints that are defined on the boundary. These constraints enforce one axis of the frame field to be equal to the normal of the surface of the domain. The singularity graph of the frame comes from locations where it must deal with contradicting constraints, but most of them have only two of the three axis that have constraints: the last direction remains well defined. Our idea is to define this “stable” vector field in the domain, and constraint the other two directions to avoid rotating when being advected by this direction. This approach will mimic the sweeping operation done in hexahedral mesh modeling. To reach our objective, we need to define a stable direction field inside the domain, and to smooth the frame field such that it does not rotate when moving in the stable direction. Our current frame field optimization algorithm relies on spherical harmonics to merge constraints inside the domain, and it will be easier to derive a locally stable vector field from this representation. The challenge will be to handle complex objects where this stable direction is not represented by the same axis everywhere in the domain.Simply fixing the stable direction and minimizing the frame field curvature will not guarantee that singularities will align to the stable direction; we need to constraint the field to have minimal rotation when moving in the stable direction. We will try to enforce it by two approaches: in the solver by a strong anisotropy term or Lagrange multipliers, or by manipulating a new set of variables that naturally enforce the constraint. We hope that frame fields generated by this task will exhibit less configurations that cannot be integrated in the CC step.
  • Months 9-24: Gradually fix failure cases of the CC step. Computing a valid global parameterization from a frame field is a very challenging objective. If we see it as the deformation that maps our final mesh to a regular grid, we can see that there are two key components in such a parameterization: the first one determines the combinatorial structure of the hexahedral mesh, and the second one gives its geometry. At first, we could think that the geometry is the most important part because it determines if the mapping is valid to extract a hexahedral mesh, and the quality of the hexahedra. In fact, it is possible to extract a hexahedral mesh [Lyon2016] even when the mapping is locally invalid, and bad local geometries can be improved directly on the hexahedral mesh in a postprocessing step. On the other hand, a bad combinatorial structure can force the geometry to be degenerated in large portions of the domain. The objective of this task will be to improve the quality of the combinatorial part of the parameterization. The CC step computes the parameterization as a linear mapping on the input tetrahedral mesh. The image of each tetrahedron is given by the coordinates of its vertices in the parameterization, and these coordinates are numerically optimized to be aligned with the frame field (geometric criteria) and to ensure that the pre-image of the grid will produce a hexahedral mesh (integer constraints). It is possible to avoid many degeneracies by fixing some constraints to the integer variables. For example, if we could enforce to have at least one layer on hexahedron in a thin domain, it would prevent the geometry of the entire domain to collapse. This task aims to determine the most common failure configurations, to detect them, and inject them in the solver. This later point is not straightforward because we use our own solver to resolve the mixed-integer optimization problem. We expect that this task should strongly reduce the number failure cases and will so allow us to produce coarse hexahedral meshes.
  • Months 24-36: Obtain guarantees of the robustness of the CC step: The objective is to push forward the contribution of the previous task: instead of fixing the most common failure cases, we will propose a solution with guarantees to avoid regions to collapse. This problem is much more difficult, and requires a more theoretical approach. We will address the problem by extending the 2D approach [Campen2015] developed for the quad remeshing problem. The idea is to decompose the domain into hexahedral regions (that are not conform), define a regular subdivision of these regions that will eliminate non-conformities, and map the number of subdivisions to the integers variables of the CC step optimization problem. This decomposition is only used to prove that there exists a valid parameterization with these integer constraints. We have already worked on tracing such surfaces [Kowalski2012b], but it required tracing a surface as perpendicular as possible to vector field that is not curl free. Now, we can generate a curl free fields by computing the geometric part of the parameterization, making it easy to trace such surfaces. Completing this task would be a great achievement, both from a theoretical point of view, and in practice to produce meshes with large hexahedra.

Candidate profile:



[Campen2015] M. Campen, D. Bommes and L. Kobbelt. 2015. Quantized global parametrization. ACM Transactons on Graphics 34.

[Kowalski2012b] N. Kowalski, F. Ledoux, P. Frey, A PDE based approach to multi-domain partitioning and quadrilateral meshing, International Meshing Roundtable 2012.

[Li2012] Y. Li, Y. Liu, W. Xu, W. Wang, B. Guo, All-hex Meshing Using Singularity-restricted Field, ACM Transactions on graphics 2012.

[Lyon2016] M. Lyon, D. Bommes, L. Kobbelt, HexEx: Robust Hexahedral Mesh Extraction, ACM Transactions on Graphics, 2016

[Ray2018] N. Ray, D. Sokolov, M. Reberol, F. Ledoux, B. Lévy, Hex-dominant meshing: Mind the gap!, Computer-Aided Design, Volume 102, 2018.

[Sokolov2016] D. Sokolov, N. Ray, L. Untereiner and B. Lévy. 2016. Hexahedral-Dominant Meshing. ACM Transactions on Graphics 35.

Logo d'Inria