# [PhD proposal] Combine grid placement with other meshing tools

**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:**

hexahedral mesh. In practice, we introduce more degrees of freedom by considering global parameterizations instead of deformation. In this case, the deformation functions have some discontinuities that make it possible to represent a much larger family of hexahedral meshes: the deformed grid can be cut and glued to itself in a non-trivial way.

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. Placing a (deformed) grid inside a volume gives a very regular hexahedral mesh. However, it is very difficult to fill the whole volume with such a grid: the boundary alignment constraints may be locally (fillet, chamfer) or globally (thread on screws) incompatible. In these cases, a global parameterization algorithm simply fails to mesh the model. To deal with this issue, we will integrate the grid placement algorithms in a more complete meshing process. To do so, we will analyze the conflicting constraints and solve them by preprocessing and post-processing. We will also try to better exploit the combinatorial structure of the grid, despite possible geometric inversions, as it is locally done in [Lyon2016]. Improving only the global parameterization will not be sufficient for two reasons: local constraints often require a complex combinatorial configuration (not a deformed grid) to be respected, and the positivity of the parameterization Jacobian is not guaranteed. We will identify and manage complex local configurations using our previous results [Staten2009, Kowalski2012a], and explore means to exploit parts of the global

parameterization without explicitly requiring needing positive Jacobian. We have tried this latter approach in [Kowalski2012b, Kowalski2014], and we plan to produce block structured hexahedral meshes by tracing hexahedron layers from the global parameterization.

We can actually generate hexahedral dominant meshes by a post-processing step that remeshes the part of the model that is not successfully filled by hexahedra. It makes the process robust, but it would be much better to detect conflicting constraints earlier, before it deteriorates the global parameterization. Indeed, the hexahedral meshes have a “very rigid” combinatorial structure that makes it possible for a (local) constraint to have an impact on the whole mesh. This new way to think about the problem leads to interesting theoretical questions: what are the conditions on the boundary conditions for a valid global parameterization to exist.

**Organization of the project:**

The project will be split into two main parts:

- Months 1-18: pre-processing the model. Here, we will address the pre-processing of the model to help the GP. We will focus on conflicting configurations of the feature edges. The starting point will be to observe failure cases, define the regions that will be impacted, and remove them from the domain to be remeshed (the post-processing will deal with it). Then, we will better manage these regions by replacing them by local hexahedral mesh patterns, and we will try to get an exhaustive classification of conflicting cases. We will manage this problem at two levels: by proposing new solutions to local conflicting configurations, and by determining mesh configurations along feature edges that respect global constraints [Kowalski2012a]. The first aspect builds on top of the results of our results on polycubes, with more degrees of freedom to solve them. Indeed, inner singularities can prevent local conflicting cases to occur, and local meshing patterns can generate more types of constraints on the surrounding frame field.
- Months 18-36: Extract hexahedral mesh from integers variables only. The basic idea of using global parameterization is to define the hexahedral mesh as the pre-image of the unit grid by a parameterization function. This process assumes that the parameterization function is locally one to one, with consistent orientation enforced by the positive Jacobian condition. In practice, this is very difficult to enforce, but robust extraction [Lyon2016] accepts some local constraint violation. It is very interesting to consider that this algorithm works well thanks to the variables that are constrained to be integers; this is the same set of variables that defines the combinatorial structure

of the hexahedral mesh. We would like to improve the robustness of the process by completely ignoring the geometry of parameterization. In theory, we could extract the hexahedral mesh combinatory using only variables that are constrained to be integers. The geometry can always be optimized directly on the final mesh, that is likely to be a better discretization for this purpose. If we consider the case of polycubes, the combinatorial structure of the hexahedral mesh is quite easy to extract; the length of the edges of the polycube are directly given by the difference of its vertices coordinates, that are constrained to be integers. It determines directly the combinatorial structure of the final mesh and let us experiment to directly optimize the geometry on the hexahedral mesh. From this point, we can start introducing a singularity graph and extend the combinatorial reconstruction with it. We will experiment it by introducing singularity graphs of increasing complexity until we can generalize the approach to any singularity graph. The risk is that the problem may be too difficult to tackle, but we will at least have a solution for simple cases, plus the geometric optimization of the hexahedral mesh geometry that could help to improve our other results.

**Candidate profile:**

We are looking for a doctoral student with good knowledge in mathematics and more specifically in optimization, analysis and differential geometry. Initial training may be in applied mathematics or computer science. The desired skills and knowledge (or to be acquired) are:

- The languages used are: C++.
- The practice of graphic computing or CAD systems.
- A good knowledge of differential geometry and general topology.

**Bibliography:**

- [Kowalski2012a] N. Kowalski, F. Ledoux, M.L. Staten, S.J. Owen, Fun sheet matching: towards automatic block

decomposition for hexahedral meshes, Engineering with Computers, 2012. - [Kowalski2012b] N. Kowalski, F. Ledoux, P. Frey, A PDE based approach to multi-domain partitioning and quadrilateral

meshing, International Meshing Roundtable 2012. - [Kowalski2014] N. Kowalski, F. Ledoux, P. Frey, Block-structured Hexahedral Meshes for CAD Models Using 3D Frame

Fields, International Meshing Roundtable 2014. - [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. - [Slotnick2014] J. Slotnick, A. Khodadoust, J. Alonso, D. Darmofal, G. William, L. Elizabeth and D. Mavriplis,CFD Vision

2030 Study: A Path to Revolutionary Computational Aerosciences, NASA/CR-2014-218178, NF1676L-18332. - [Sokolov2016] D. Sokolov, N. Ray, L. Untereiner and B. Lévy. 2016. Hexahedral-Dominant Meshing. ACM Transactions

on Graphics 35. - [Staten2009] M.L. Staten, J.F. Shepherd, F. Ledoux, K. Shimada, Hexahedral Mesh Matching: Converting nonconforming hexahedral-to-hexahedral interfaces into conforming interfaces, International journal for numerical

methods in engineering, 2009.

No offers are available for now.