2025Activity‌​‌ reportTeamPIXEL

2.1 Scientific​​​‌ grounds

Mesh generation is​ a notoriously difficult task.​‌ A quick search on​​ the NSF grant web​​​‌ page with “mesh generation​ AND finite element” keywords​‌ returns more than 30​​ currently active grants for​​ a total of $8​​​‌ million. NASA indicates mesh‌ generation as one of‌​‌ the major challenges for​​ 2030  38, and​​​‌ estimates that it costs‌ 80% of time and‌​‌ effort in numerical simulation.​​ This is due to​​​‌ the need for constructing‌ supports that match both‌​‌ the geometry and the​​ physics of the system​​​‌ to be modeled. In‌ our team we pay‌​‌ a particular attention to​​ scientific computing, because we​​​‌ believe it has a‌ world changing impact.

It‌​‌ is very unsatisfactory that​​ meshing, i.e. just “preparing​​​‌ the data” for the‌ simulation, eats up the‌​‌ major part of the​​ time and effort. Our​​​‌ goal is to change‌ the situation, by studying‌​‌ the influence of shapes​​ and discretizations, and inventing​​​‌ new algorithms to automatically‌ generate meshes that can‌​‌ be directly used in​​ scientific computing. This goal​​​‌ is a result of‌ our progressive shift from‌​‌ pure graphics (“Geometry and​​ Lighting”) to real-world problems​​​‌ (“Shape Fidelity”).

 

Meshing is‌​‌ central in geometric modeling​​ because it provides a​​​‌ way to represent functions‌ on the objects being‌​‌ studied (texture coordinates, temperature,​​ pressure, speed, etc.). There​​​‌ are numerous ways to‌ represent functions, but if‌​‌ we suppose that the​​ functions are piecewise smooth,​​​‌ the most versatile way‌ is to discretize the‌​‌ domain of interest. Ways​​ to discretize a domain​​​‌ range from point clouds‌ to hexahedral meshes; let‌​‌ us list a few​​ of them sorted by​​​‌ the amount of structure‌ each representation has to‌​‌ offer (refer to Figure​​ 1).

• At one​​​‌ end of the spectrum‌ there are point clouds:‌​‌ they exhibit no structure​​ at all (white noise​​​‌ point samples) or very‌ little (blue noise point‌​‌ samples). Recent explosive development​​ of acquisition techniques (e.g.​​​‌ scanning or photogrammetry) provides‌ an easy way to‌​‌ build 3D models of​​ real-world objects that range​​​‌ from figurines and cultural‌ heritage objects to geological‌​‌ outcrops and entire city​​ scans. These technologies produce​​​‌ massive, unstructured data (billions‌ of 3D points per‌​‌ scene) that can be​​ directly used for visualization​​​‌ purposes, but this data‌ is not suitable for‌​‌ high-level geometry processing algorithms​​ and numerical simulations that​​​‌ usually expect meshes. Therefore,‌ at the very beginning‌​‌ of the acquisition-modeling-simulation-analysis pipeline,​​ powerful scan-to-mesh algorithms are​​​‌ required. It is to‌ be noted, however, with‌​‌ the advent of machine​​ learning, more and more​​​‌ non-critical simulations are performed‌ using nonlinear approximants such‌​‌ as neural netwoks (e.g.,​​ PINNs). In this case,​​​‌ no mesh is required‌ and a point cloud‌​‌ can be sufficient.

  During​​ the last decade, many​​​‌ solutions have already been‌ proposed  33, 14‌​‌, 28, 27​​, 18, but​​​‌ the problem of building‌ a good mesh from‌​‌ scattered 3D points is​​ far from being solved.​​​‌ Beside the fact that‌ the data is unusually‌​‌ large, the existing algorithms​​​‌ are challenged also by​ the extreme variation of​‌ data quality. Raw point​​ clouds have many defects,​​​‌ they are often corrupted​ with noise, redundant, incomplete​‌ (due to occlusions): they​​ all are uncertain.​​​‌

• Triangulated surfaces are ubiquitous,​ they are the most​‌ widely used representation for​​ 3D objects. Some applications​​​‌ like 3D printing do​ not impose heavy requirements​‌ on the surface: typically​​ it has to be​​​‌ watertight, but triangles can​ have an arbitrary shape.​‌ Other applications like texturing​​ require very regular meshes,​​​‌ because they suffer from​ elongated triangles with large​‌ angles.

  While being a​​ common solution for many​​​‌ problems, triangle mesh generation​ is still an active​‌ topic of research. The​​ diversity of representations (meshes,​​​‌ NURBS, ...) and file​ formats often results in​‌ a “Babel” problem when​​ one has to exchange​​​‌ data. The only common​ representation is often the​‌ mesh used for visualization,​​ that has in most​​​‌ cases many defects, such​ as overlaps, gaps or​‌ skinny triangles. Re-injecting this​​ solution into the modeling-analysis​​​‌ loop is non-trivial, since​ again this representation is​‌ not well adapted to​​ analysis.

• Tetrahedral meshes are​​​‌ the volumic equivalent of​ triangle meshes, they are​‌ very common in the​​ scientific computing community. Tetrahedral​​​‌ meshing is now a​ mature technology. It is​‌ remarkable that still today​​ all the existing software​​​‌ used in the industry​ is built on top​‌ of a handful of​​ kernels, all written by​​​‌ a small number of​ individuals 20, 36​‌, 42, 22​​, 35, 37​​​‌, 21, 47​.

  Meshing requires a​‌ long-term, focused, dedicated research​​ effort that combines deep​​​‌ theoretical studies with advanced​ software development. We have​‌ the ambition to bring​​ this kind of maturity​​​‌ to a different type​ of mesh (structured, with​‌ hexahedra), which is highly​​ desirable for some simulations,​​​‌ and for which, unlike​ tetrahedra, no satisfying automatic​‌ solution exists. In the​​ light of recent contributions,​​​‌ we believe that the​ domain is ready to​‌ overcome the principal difficulties.​​

• Finally, at the most​​​‌ structured end of the​ spectrum there are hexahedral​‌ meshes composed of deformed​​ cubes (hexahedra). They are​​​‌ preferred for certain physics​ simulations (deformation mechanics, fluid​‌ dynamics ...) because they​​ can significantly improve both​​​‌ speed and accuracy. This​ is because (1) they​‌ contain a smaller number​​ of elements (5-6 tetrahedra​​​‌ for a single hexahedron),​ (2) the associated tri-linear​‌ function basis has cubic​​ terms that can better​​​‌ capture higher-order variations, (3)​ they avoid the locking​‌ phenomena encountered with tetrahedra​​ 12, (4) hexahedral​​​‌ meshes exploit inherent tensor​ product structure and (5)​‌ hexahedral meshes are superior​​ in direction dominated physical​​​‌ simulations (boundary layer, shock​ waves, etc). Being extremely​‌ regular, hexahedral meshes are​​ often claimed to be​​​‌ The Holy Grail for​ many finite element methods​‌  13, outperforming tetrahedral​​ meshes both in terms​​​‌ of computational speed and​ accuracy.

  Despite 30 years​‌ of research efforts and​​ important advances, mainly by​​​‌ the Lawrence Livermore National​ Labs in the U.S.​‌ 41, 40,​​ hexahedral meshing still requires​​ considerable manual intervention in​​​‌ most cases (days, weeks‌ and even months for‌​‌ the most complicated domains).​​ Some automatic methods exist​​​‌ 26, 44,‌ that constrain the boundary‌​‌ into a regular grid,​​ but they are not​​​‌ fully satisfactory either, since‌ the grid is not‌​‌ aligned with the boundary.​​ The advancing front method​​​‌ 10 does not have‌ this problem, but generates‌​‌ irregular elements on the​​ medial axis, where the​​​‌ fronts collide. Thus, there‌ is no fully automatic‌​‌ algorithm that results in​​ satisfactory boundary alignment.​​​‌

3.1‌ Point clouds

Currently, transforming‌​‌ the raw point cloud​​ into a triangular mesh​​​‌ is a long pipeline‌ involving disparate geometry processing‌​‌ algorithms:

• Point pre-processing: colorization,​​ filtering to remove unwanted​​​‌ background, first noise reduction‌ along acquisition viewpoint;
• Registration:‌​‌ cloud-to-cloud alignment, filtering of​​ remaining noise, registration refinement;​​​‌
• Mesh generation: triangular mesh‌ from the complete point‌​‌ cloud, re-meshing, smoothing.

The​​ output of this pipeline​​​‌ is a locally-structured model‌ which is used in‌​‌ downstream mesh analysis methods​​ such as feature extraction,​​​‌ segmentation in meaningful parts‌ or building Computer-Aided Design‌​‌ (CAD) models.

It is​​ well known that point​​​‌ cloud data contains measurement‌ errors due to factors‌​‌ related to the external​​ environment and to the​​​‌ measurement system itself  39‌, 32, 15‌​‌. These errors propagate​​ through all processing steps:​​​‌ pre-processing, registration and mesh‌ generation. Even worse, the‌​‌ heterogeneous nature of different​​ processing steps makes it​​​‌ extremely difficult to know‌ how these errors propagate‌​‌ through the pipeline. To​​ give an example, for​​​‌ cloud-to-cloud alignment it is‌ necessary to estimate normals.‌​‌ However, the normals are​​ forgotten in the point​​​‌ cloud produced by the‌ registration stage. Later on,‌​‌ when triangulating the cloud,​​ the normals are re-estimated​​​‌ on the modified data,‌ thus introducing uncontrollable errors.‌​‌

We plan to develop​​ new reconstruction, meshing and​​​‌ re-meshing algorithms, with a‌ specific focus on the‌​‌ accuracy and resistance to​​ all defects present in​​​‌ the input raw data.‌ We think that pervasive‌​‌ treatment of uncertainty is​​ the missing ingredient to​​​‌ achieve this goal. We‌ plan to rethink the‌​‌ pipeline with the position​​ uncertainty maintained during the​​​‌ whole process. Input points‌ can be considered either‌​‌ as error ellipsoids  43​​ or as probability measures​​​‌  24. In a‌ nutshell, our idea is‌​‌ to start by computing​​ an error ellipsoid  46​​​‌, 29 for each‌ point of the raw‌​‌ data, and then to​​ cumulate the errors (approximations)​​​‌ made at each step‌ of the processing pipeline‌​‌ while building the mesh.​​ In this way, the​​​‌ final users will be‌ able to take the‌​‌ knowledge of the uncertainty​​ into account and rely​​​‌ on this confidence measure‌ for further analysis and‌​‌ simulations. Quantifying uncertainties for​​ reconstruction algorithms, and propagating​​​‌ them from input data‌ to high-level geometry processing‌​‌ algorithms has never been​​ considered before, possibly due​​​‌ to the very different‌ methodologies of the approaches‌​‌ involved. At the very​​ beginning we will re-implement​​​‌ the entire pipeline, and‌ then attack the weak‌​‌ links through all three​​​‌ reconstruction stages.

3.2 Parameterizations​

One of the favorite​‌ tools we use in​​ our team are parameterizations,​​​‌ and we have major​ contributions to the field:​‌ we have solved a​​ fundamental problem formulated more​​​‌ than 60 years ago​ 2. Parameterizations provide​‌ a very powerful way​​ to reveal structures on​​​‌ objects. The most omnipresent​ application of parameterizations is​‌ texture mapping: texture maps​​ provide a way to​​​‌ represent in 2D (on​ the map) information related​‌ to a surface. Once​​ the surface is equipped​​​‌ with a map, we​ can do much more​‌ than a mere coloring​​ of the surface: we​​​‌ can approximate geodesics, edit​ the mesh directly in​‌ 2D or transfer information​​ from one mesh to​​​‌ another.

Parameterizations constitute a​ family of methods that​‌ involve optimizing an objective​​ function, subject to a​​​‌ set of constraints (equality,​ inequality, being integer, etc.).​‌ Computing the exact solution​​ to such problems is​​​‌ beyond any hope, therefore​ approximations are the only​‌ resort. This raises a​​ number of problems, such​​​‌ as the minimization of​ highly nonlinear functions and​‌ the definition of direction​​ fields topology, without forgetting​​​‌ the robustness of the​ software that puts all​‌ this into practice.

 

We​ are particularly interested in​‌ a specific instance of​​ parameterization: hexahedral meshing. The​​​‌ idea 6, 4​ is to build a​‌ transformation $f$ from the​​ domain to a parametric​​​‌ space, where the distorted​ domain can be meshed​‌ by a regular grid.​​ The inverse transformation ${\mathrm{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: we start​‌ from a tetrahedral mesh​​ (Figure 2, left)​​​‌ and we want to​ deform it in a​‌ way that its boundary​​ is aligned with the​​​‌ integer grid. To allow​ for a singular edge​‌ in the output (the​​ valency 3 edge, Figure​​​‌ 2, right), the​ input mesh is cut​‌ open along the highlighted​​ faces and the central​​​‌ edge is mapped onto​ an integer grid line​‌ (Figure 2, middle).​​ The regular integer grid​​​‌ then induces the hexahedral​ mesh with the desired​‌ topology.

Current global parameterizations​​ allow grids to be​​​‌ positioned inside geometrically simple​ objects whose internal structure​‌ (the singularity graph) can​​ be relatively basic. We​​​‌ wish to be able​ to handle more configurations​‌ by improving three aspects​​ of current methods:

• Local​​​‌ grid orientation is usually​ prescribed by minimizing the​‌ curvature of a 3D​​ steering field. Unfortunately, this​​​‌ heuristic does not always​ provide singularity curves that​‌ can be integrated by​​ the parameterization. We plan​​​‌ to explore how to​ embed integrability constraints in​‌ the generation of the​​ direction fields. To address​​ the problem, we already​​​‌ identified necessary validity criteria:‌ for example, the permutation‌​‌ of axes along elementary​​ cycles that go around​​​‌ a singularity must preserve‌ one of the axes‌​‌ (the one tangent to​​ the singularity). The first​​​‌ step to enforce this‌ (necessary) condition will be‌​‌ to split the frame​​ field generation into two​​​‌ parts: first we will‌ define a locally stable‌​‌ vector field, followed by​​ the definition of the​​​‌ other two axes by‌ a 2.5D directional field‌​‌ (2D advected by the​​ stable vector field).
• The​​​‌ grid combinatorial information is‌ characterized by a set‌​‌ of integer coefficients whose​​ values are currently determined​​​‌ through numerical optimization of‌ a geometric criterion: the‌​‌ shape of the hexahedra​​ must be as close​​​‌ as possible to the‌ steering direction field. Thus,‌​‌ the number of layers​​ of hexahedra between two​​​‌ surfaces is determined solely‌ by the size of‌​‌ the hexahedra that one​​ wishes to generate. In​​​‌ these settings, degenerate configurations‌ arise easily, and we‌​‌ want to avoid them.​​ In practice, mixed integer​​​‌ solvers often choose to‌ allocate a negative or‌​‌ zero number of layers​​ of hexahedra between two​​​‌ constrained sheets (boundaries of‌ the object, internal constraints‌​‌ or singularities). We will​​ study how to inject​​​‌ strict positivity constraints into‌ these cases, which is‌​‌ a very complex problem​​ because of the subtle​​​‌ interplay between different degrees‌ of freedom of the‌​‌ system. Our first results​​ for quad-meshing of surfaces​​​‌ give promising leads, notably‌ thanks to motorcycle graphs‌​‌  17, a notion​​ we wish to extend​​​‌ to volumes.
• Optimization for‌ the geometric criterion makes‌​‌ it possible to control​​ the average size of​​​‌ the hexahedra, but it‌ does not ensure the‌​‌ bijectivity (even locally) of​​ the resulting parameterizations. Considering​​​‌ other criteria, as we‌ did in 2D  23‌​‌, would probably improve​​ the robustness of the​​​‌ process. Our idea is‌ to keep the geometry‌​‌ criterion to find the​​ global topology, but try​​​‌ other criteria to improve‌ the geometry.

3.3 Hexahedral-dominant‌​‌ meshing

All global parameterization​​ approaches are decomposed into​​​‌ three steps: frame field‌ generation, field integration to‌​‌ get a global parameterization,​​ and final mesh extraction.​​​‌ Getting a full hexahedral‌ mesh from a global‌​‌ parameterization means that it​​ has positive Jacobian everywhere​​​‌ except on the frame‌ field singularity graph. To‌​‌ our knowledge, there is​​ no solution to ensure​​​‌ this property, but some‌ efforts are done to‌​‌ limit the proportion of​​ failure cases. An alternative​​​‌ is to produce hexahedral‌ dominant meshes. Our position‌​‌ is in between those​​ two points of view:​​​‌

1. We want to produce‌ full hexahedral meshes;
2. We‌​‌ consider as pragmatic to​​ keep hexahedral dominant meshes​​​‌ as a fallback solution.‌

The global parameterization approach‌​‌ yields impressive results on​​ some geometric objects, which​​​‌ is encouraging, but not‌ yet sufficient for numerical‌​‌ analysis. Note that while​​ we attack the remeshing​​​‌ with our parameterizations toolset,‌ the wish to improve‌​‌ the tool itself (as​​ described above) is orthogonal​​​‌ to the effort we‌ put into making the‌​‌ results usable by the​​​‌ industry. To go further,​ our idea (as opposed​‌ to  31, 19​​) is that the​​​‌ global parameterization should not​ handle all the remeshing,​‌ but merely act as​​ a guide to fill​​​‌ a large proportion of​ the domain with a​‌ simple structure; it must​​ cooperate with other remeshing​​​‌ bricks, especially if we​ want to take final​‌ application constraints into account.​​

For each application we​​​‌ will take as an​ input domains, sets of​‌ constraints and, eventually, fields​​ (e.g. the magnetic field​​​‌ in a tokamak). Having​ established the criteria of​‌ mesh quality (per application!)​​ we will incorporate this​​​‌ input into the mesh​ generation process, and then​‌ validate the mesh by​​ a numerical simulation software.​​​‌

4.1​ Geometric Tools for Simulating​‌ Physics with a Computer​​

Numerical simulation is the​​​‌ main targeted application domain​ for the geometry processing​‌ tools that we develop.​​ Our mesh generation tools​​​‌ will be tested and​ evaluated within the context​‌ of our cooperation with​​ Hutchinson, experts in vibration​​​‌ control, fluid management and​ sealing system technologies. We​‌ think that the hex-dominant​​ meshes that we generate​​​‌ have geometrical properties that​ make them suitable for​‌ some finite element analyses,​​ especially for simulations with​​​‌ large deformations.

We also​ have a tight collaboration​‌ with a geophysical modeling​​ specialists via the RING​​​‌ consortium. In particular, we​ produce hexahedral-dominant meshes for​‌ geomechanical simulations of gas​​ and oil reservoirs. From​​​‌ a scientific point of​ view, this use case​‌ introduces new types of​​ constraints (alignments with faults​​​‌ and horizons), and allows​ certain types of nonconformities​‌ that we did not​​ consider until now.

Our​​​‌ cooperation with RhinoTerrain pursues​ the same goal: reconstruction​‌ of buildings from point​​ cloud scans allows to​​​‌ perform 3D analysis and​ studies on insolation, floods​‌ and wave propagation, wind​​ and noise simulations necessary​​​‌ for urban planification.

5.1 Awards

Étienne Corman​​​‌ has recieved a SIGGRAPH​ 2025 Best Paper Award​‌ (Honorable Mention) for his​​ algorithm 7, which​​​‌ dices surfaces into near-perfect​ rectangles. Such meshes are​‌ useful for everything from​​ retopology, to microfluidic simulation,​​​‌ to textile design, to​ architectural geometry. More on​‌ that in §7​​.

6.1 Latest software developments​‌

7.1‌​‌ Rectangular Surface Parameterization

Angle​​ preservation is a very​​​‌ interesting property for mesh‌ generation: it avoids shearing‌​‌ and anisotropy. It thus​​ favors square elements. Moreover,​​​‌ the equations defining these‌ conformal deformations are linear‌​‌ and depend only on​​ a scaling factor 11​​​‌. Injectivity is also‌ guaranteed without additional nonlinear‌​‌ energy.

However, conformal maps​​ have limitations: they do​​​‌ not generalize well to‌ 3D and do not‌​‌ easily allow the imposition​​ of internal constraints 30​​​‌. The goal of‌ this project is to‌​‌ retain their advantages (few​​ parameters, guaranteed injectivity, high-quality​​​‌ elements) while solving real-world‌ problems that require finer‌​‌ control over parameterization (alignment​​ constraints, prescribed singularities).

In​​​‌ this project, we studied‌ a new class of‌​‌ shear-free parameterizations: orthogonal maps​​. These allow independent​​​‌ stretching along two orthogonal‌ directions and thus generalize‌​‌ conformal maps. For a​​ planar domain, we define​​​‌ at each point a‌ local frame $({\mathrm{X‌‌}}_1,X_{\mathrm{2}})$, whose rotation​​​‌ and stretching along each‌ axis we control. More‌​‌ general atlases can be​​ obtained by using discontinuous​​​‌ frame fields and point‌ singularities. This approach transforms‌​‌ infinitesimal squares into rectangles,​​ an essential property for​​​‌ mesh generation and shape‌ optimization.

To theoretically study‌​‌ these orthogonal deformations,​​ we specify that for​​​‌ $f:{ℝ}^{\mathrm{2‌}}\to {ℝ}^2$ to‌​‌ be an orthogonal map,​​ then its Jacobian must​​​‌ be written in the‌ form:

where $(‌X_1,{\mathrm{X‌‌}}_2):{\mathrm{ℝ}}^2\to \mathrm{SO}(‌2)$ is a‌ rotation field and $\mathrm{a‌‌},b:{\mathrm{ℝ}}^2\to {ℝ}^{+‌}$ are functions governing the‌ stretching of the map‌​‌ (see Figure 3).​​ The map is then​​​‌ locally characterized by the‌ necessary condition:

After calculation, this​​​‌ integrability condition turns out‌ to be linear in‌​‌ the logarithm of the​​ scale factor in each​​​‌ direction, $log\left(\mathrm{a‌}\right)$ and $log(‌‌b)$.

 

Unlike previous​​​‌ approaches, which focused mainly​ on integrability guarantees, our​‌ method produces less distorted​​ maps while better preserving​​​‌ the directions of the​ frame field. Our algorithm​‌ also allows for user-defined​​ distortion measures, ensures alignment​​​‌ on sharp edges, and​ provides direct control over​‌ boundary behavior (lengths or​​ aspect ratios).

Using this​​​‌ approach, we generate high-quality​ anisotropic quadrilateral meshes. Empirical​‌ results show that we​​ outperform the most recent​​​‌ algorithms, whether from research​ or commercial domains, in​‌ terms of element quality,​​ accuracy, and asymptotic convergence​​​‌ rate for the numerical​ solution of PDEs (Figure​‌ 4).

This contribution,​​ presented in 7,​​​‌ was awarded the Best​ Paper Award (Honorable Mention)​‌ at SIGGRAPH 2025. It​​ represents a first step​​​‌ toward a 3D generalization​ for hexahedral mesh generation.​‌ Further study of these​​ orthogonal deformations is the​​​‌ subject of the ANR​ JCJC project ORTHOMAP,​‌ launched in April 2025.​​

 

7.2 Transport semi-discret exploitant​‌ des diagrames de Voronoi​​ distribués

 

The Voronoi diagram partitions​ space based on a​‌ set of points in​​ such a way that​​​‌ each region is associated​ with one point of​‌ the set (the seed).​​ Every point in space​​​‌ is assigned to the​ region whose seed is​‌ the closest.

This decomposition​​ is very popular because​​​‌ it is simple to​ understand and easy to​‌ manipulate. In particular, it​​ makes it possible to​​​‌ represent meshes without explicitly​ encoding their combinatorial structure,​‌ which is highly advantageous,​​ especially when the meshes​​​‌ evolve during the execution​ of an algorithm. This​‌ was the case in​​ Lloyd’s algorithm and, more​​​‌ recently, in fluid simulation​ and cosmology. In both​‌ of these latter cases,​​ the simulation of the​​​‌ dynamics is carried out​ over a number of​‌ time steps, and at​​ each time step a​​​‌ semi-discrete optimal transport problem​ must be solved, in​‌ which a Voronoi diagram​​ is used inside an​​​‌ inner loop.

In these​ algorithms, the computation of​‌ the Voronoi diagram is​​ the main bottleneck and​​​‌ is therefore worth optimizing.​ A few years ago,​‌ we proposed a GPU-based​​ version that dramatically accelerated​​​‌ the computations 1.​ This year, we introduced​‌ a cluster-based version 8​​, capable of scaling​​​‌ to datasets with more​ than ${10}^8$ points,​‌ as required for cosmological​​ simulations. Our strategy is​​ still to compute the​​​‌ diagram locally and on‌ demand in order to‌​‌ build the matrices needed​​ for the simulation, without​​​‌ ever explicitly constructing the‌ complete diagram. The distribution‌​‌ of the computations over​​ a cluster is achieved​​​‌ by decomposing the domain,‌ with particular care taken‌​‌ to handle cells whose​​ computation requires access to​​​‌ seeds distributed across different‌ nodes of the cluster.‌​‌ Our next step is​​ to scale-up to problems​​​‌ of 1 billion points‌ and above.

7.3 On‌​‌ Quad Mesh Extraction From​​ Messy Grid Preserving Maps​​​‌

 

Quadrilateral meshes​​ are widely appreciated in​​​‌ computer graphics and numerical‌ simulation for their regularity:‌​‌ almost everywhere, they resemble​​ a deformed grid, which​​​‌ makes them particularly easy‌ to manipulate. The downside‌​‌ of this highly appealing​​ structure is that it​​​‌ is difficult to generate.‌ For this reason, recent‌​‌ work has focused on​​ a new family of​​​‌ algorithms that define quad‌ meshes through a map‌​‌ of the object: the​​ quad mesh can then​​​‌ be obtained by taking‌ the image of a‌​‌ 2D unit grid by​​ the inverse of the​​​‌ mapping function. It is‌ even possible to model‌​‌ singular vertices (with valence​​ different from four) by​​​‌ tearing the map under‌ grid-preserving conditions.

One of‌​‌ the main challenges of​​ this approach is the​​​‌ generation of valid maps‌ (locally injective), which is‌​‌ a sufficient condition to​​ obtain a quad mesh​​​‌ on the surface. Despite‌ numerous works on this‌​‌ topic 2, the​​ linearity of the maps​​​‌ over each triangle, combined‌ with the presence of‌​‌ singularities, does not always​​ allow this condition to​​​‌ be satisfied. We therefore‌ focus on extracting quadrilateral‌​‌ meshes from maps that​​ may contain local foldovers.​​​‌ The idea is to‌ directly extract a structure‌​‌ from the map and​​ then apply operations that​​​‌ are equivalent to restoring‌ the bijectivity of the‌​‌ mapping.

Previous works (QEx​​ and HexEx 16,​​​‌ 25) have achieved‌ good results using this‌​‌ approach. Our method is​​ made significantly simpler by​​​‌ working on the dual‌ of the quadrangulation, as‌​‌ many special cases are​​ thereby avoided. Moreover, rather​​​‌ than repairing only the‌ most common foldover cases,‌​‌ we propose an analysis​​ of all possible foldover​​​‌ configurations. This led us‌ to two interesting observations:‌​‌ it is possible to​​ construct foldover cases that​​​‌ cannot be repaired within‌ the intermediate structure (although‌​‌ these are very rare),​​ and foldover repair may​​​‌ converge to several different‌ quad mesh combinatorics. For‌​‌ this latter case, we​​ propose a heuristic to​​​‌ improve mesh quality.

8.1 Bilateral contracts‌ with industry

Company: CEA‌​‌

Duration: 01/10/2025 – 1/10/2028​​

Participants: Dmitry Sokolov, Étienne​​​‌ Corman and Tristan Cheny‌

Abstract: This project is‌​‌ related to the Simulation​​​‌ program of the CEA​ DAM. Started in 1996,​‌ this program aims to​​ ensure reliability of the​​​‌ French nuclear charges, without​ nuclear experiment. To this​‌ purpose, it relies on​​ numerical simulation. Here, we​​​‌ focus on codes of​ the Simulation program that​‌ require to discretize studied​​ objects under the form​​​‌ of a mesh. Many​ of these codes require​‌ quadrangular meshes (in 2D)​​ or hexahedral meshes (in​​​‌ 3D) that are block-structured,​ with in addition a​‌ high control over the​​ direction and size of​​​‌ the mesh elements. The​ Pixel team has a​‌ strong expertise in hex-dominant​​ meshing, CEA has a​​​‌ strong background in numerical​ simulation within an industrial​‌ context. This collaborative project​​ aims to take advantage​​​‌ of both expertises.

9.1 Promoting scientific​‌ activities

Dmitry Sokolov is​​ an elected member of​​​‌ the executive board of​ the Association Française d'Informatique​‌ Graphique. AFIG is​​ a non-profit scientific association,​​​‌ its aim is to​ federate and animate the​‌ scientific community in fields​​ related to Computer Graphics,​​​‌ to disseminate information and​ events in the field,​‌ and to facilitate networking​​ and interaction between researchers,​​​‌ as well as between​ industry and research.

9.2 Teaching​‌ - Supervision - Juries​​ - Educational and pedagogical​​​‌ outreach

Prior to moving​ to Polytech Nancy, Dobrina​‌ Boltcheva was responsible of​​ software engineering study program​​​‌ at IUT Saint-Die and​ she was also in​‌ charge of the local​​ adaptation of the BUT​​​‌ Info program in Saint-Dié.​

Dmitry Sokolov was responsible​‌ for the 3d year​​ of computer science license​​​‌ at the Université de​ Lorraine.

• Master: Étienne Corman,​‌ Analysis and Deep Learning​​ on Geometric Data,  12h,​​​‌ M2, École Polytechnique
• Master:​ Étienne Corman, Geometry processing​‌ and geometric deep learning,​​  12h, M2, Master Mathématiques​​​‌ Vision Apprentissage
• BUT 2​ INFO : Dobrina Boltcheva,​‌ Algorithmics, 20h, 2A, IUT​​ Saint-Dié-des-Vosges
• BUT 2 INFO​​ : Dobrina Boltcheva, Analyse​​​‌ et concéption UML, 20h,‌ 2A, IUT Saint-Dié-des-Vosges
• BUT‌​‌ 2 INFO : Dobrina​​ Boltcheva, Software engineering, 20h,​​​‌ 2A, IUT Saint-Dié-des-Vosges
• BUT‌ 2 INFO : Dobrina‌​‌ Boltcheva, Computer Vision :​​ Image processing, 20h, 2A,​​​‌ IUT Saint-Dié-des-Vosges
• BUT 3‌ INFO : Dobrina Boltcheva,‌​‌ Advanced algorithmics, 20h, 3A,​​ IUT Saint-Dié-des-Vosges
• BUT 3​​​‌ INFO : Dobrina Boltcheva,‌ Graphical Application, 30h, 3A,‌​‌ IUT Saint-Dié-des-Vosges
• BUT 3​​ INFO : Dobrina Boltcheva,​​​‌ Advanced programming, 30h, 3A,‌ IUT Saint-Dié-des-Vosges
• License :‌​‌ Dmitry Sokolov, Logic, 30h,​​ 3A, Université de Lorraine​​​‌
• BUT 3 INFO :‌ Dmitry Sokolov, Logic, 32h,‌​‌ 3A, Université de Lorraine​​
• License : Dmitry Sokolov,​​​‌ Compilation, 16h, 3A, Université‌ de Lorraine
• Master :‌​‌ Dmitry Sokolov, Numerical modeling,​​ 15h, M2, Université de​​​‌ Lorraine

10.1 Major publications

• 1‌​‌ articleJ.Justine Basselin​​, L.Laurent Alonso​​​‌, N.Nicolas Ray‌, D.Dmitry Sokolov‌​‌, S.Sylvain Lefebvre​​ and B.Bruno Lévy​​​‌. Restricted Power Diagrams‌ on the GPU.‌​‌Computer Graphics Forum40​​2June 2021HAL​​​‌DOIback to text‌
• 2 articleV.Vladimir‌​‌ Garanzha, I.Igor​​ Kaporin, L.Liudmila​​​‌ Kudryavtseva, F.François‌ Protais, N.Nicolas‌​‌ Ray and D.Dmitry​​ Sokolov. Foldover-free maps​​​‌ in 50 lines of‌ code.ACM Transactions‌​‌ on GraphicsVolume 40​​issue 4July 2021​​​‌, Article No.102, pp‌ 1–16HALDOIback‌​‌ to textback to​​ text
• 3 articleN.​​​‌Nicolas Ray, D.‌Dmitry Sokolov, S.‌​‌Sylvain Lefebvre and B.​​Bruno Lévy. Meshless​​​‌ Voronoi on the GPU‌.ACM Trans. Graph.‌​‌376December 2018​​, 265:1--265:12URL: http://doi.acm.org/10.1145/3272127.3275092​​​‌DOI
• 4 articleN.‌Nicolas Ray, D.‌​‌Dmitry Sokolov and B.​​Bruno Lévy. Practical​​​‌ 3D Frame Field Generation‌.ACM Trans. Graph.‌​‌356November 2016​​, 233:1--233:9URL: http://doi.acm.org/10.1145/2980179.2982408​​​‌DOIback to text‌
• 5 articleN.Nicolas‌​‌ Ray and D.Dmitry​​ Sokolov. Robust Polylines​​​‌ Tracing for N-Symmetry Direction‌ Field on Triangulated Surfaces‌​‌.ACM Trans. Graph.​​333June 2014​​​‌, 30:1--30:11URL: http://doi.acm.org/10.1145/2602145‌DOI
• 6 articleD.‌​‌Dmitry Sokolov, N.​​Nicolas Ray, L.​​​‌Lionel Untereiner and B.‌Bruno Lévy. Hexahedral-Dominant‌​‌ Meshing.ACM Transactions​​​‌ on Graphics355​2016, 1 -​‌ 23HALDOIback​​ to text

10.2 Publications​​​‌ of the year

10.3 Cited​‌ publications

• 10 articleT.​​ C.Tristan Carrier Baudouin​​​‌, J.-F.Jean-François Remacle​, E.Emilie Marchandise​‌, F.François Henrotte​​ and C.Christophe Geuzaine​​​‌. A frontal approach​ to hex-dominant mesh generation​‌.Adv. Model. and​​ Simul. in Eng. Sciences​​​‌112014,​ 8:1--8:30URL: https://doi.org/10.1186/2213-7467-1-8DOI​‌back to text
• 11​​ inproceedingsM.Mirela Ben-Chen​​​‌, C.Craig Gotsman​ and G.Guy Bunin​‌. Conformal flattening by​​ curvature prescription and metric​​​‌ scaling.Computer Graphics​ Forum272Wiley​‌ Online Library2008,​​ 449--458back to text​​​‌
• 12 inproceedingsS. E.​Steven E. Benzley,​‌ K.Karl Ernest Perry​​, B. C.Brett​​​‌ Clark Merkley and G.​Greg Sjaardema. A​‌ Comparison of All-Hexahedral and​​ All-Tetrahedral Finite Element Meshes​​​‌ for Elastic and Elasto-Plastic​ Analysis.International Meshing​‌ Roundtable conf. proc.1995​​back to text
• 13​​​‌ inproceedingsT.Ted Blacker​. Meeting the Challenge​‌ for Automated Conformal Hexahedral​​ Meshing.9th International​​​‌ Meshing Roundtable2000,​ 11--20back to text​‌
• 14 miscCloud Compare​​.http://www.danielgm.net/cc/release/back to​​​‌ text
• 15 articleZ.​Zhengchun Du, M.​‌Mengrui Zhu, Z.​​Zhaoyong Wu and J.​​​‌Jianguo Yang. Measurement​ uncertainty on the circular​‌ features in coordinate measurement​​ system based on the​​​‌ error ellipse and Monte​ Carlo methods.Measurement​‌ Science and Technology27​​122016, 125016​​​‌URL: http://stacks.iop.org/0957-0233/27/i=12/a=125016back to​ text
• 16 articleH.-C.​‌Hans-Christian Ebke, D.​​David Bommes, M.​​​‌Marcel Campen and L.​Leif Kobbelt. QEx:​‌ Robust Quad Mesh Extraction​​.ACM Transactions on​​​‌ Graphics42013,​ 168:1--168:10HALDOIback​‌ to text
• 17 inproceedings​​D.David Eppstein,​​​‌ M. T.Michael T.​ Goodrich, E.Ethan​‌ Kim and R.Rasmus​​ Tamstorf. Motorcycle Graphs:​​​‌ Canonical Quad Mesh Partitioning​.Proceedings of the​‌ Symposium on Geometry Processing​​SGP '08Aire-la-Ville, Switzerland,​​​‌ SwitzerlandCopenhagen, DenmarkEurographics​ Association2008, 1477--1486​‌URL: http://dl.acm.org/citation.cfm?id=1731309.1731334back to​​ text
• 18 miscGRAPHITE​​​‌.http://alice.loria.fr/software/graphite/doc/html/back to​ text
• 19 articleX.​‌Xifeng Gao, W.​​Wenzel Jakob, M.​​​‌Marco Tarini and D.​Daniele Panozzo. Robust​‌ Hex-Dominant Mesh Generation using​​ Field-Guided Polyhedral Agglomeration.​​​‌ACM Transactions on Graphics​ (Proceedings of SIGGRAPH)36​‌4July 2017DOI​​back to text
• 20​​ articleP. L.P.​​​‌ L. George, F.‌F. Hecht and E.‌​‌E. Saltel. Fully​​ Automatic Mesh Generator for​​​‌ 3D Domains of Any‌ Shape.IMPACT Comput.‌​‌ Sci. Eng.23​​December 1990, 187--218​​​‌URL: http://dx.doi.org/10.1016/0899-8248(90)90012-YDOIback‌ to text
• 21 article‌​‌C.C. Geuzaine and​​ J.-F.J.-F. Remacle.​​​‌ Gmsh: a three-dimensional finite‌ element mesh generator.‌​‌International Journal for Numerical​​ Methods in Engineering79​​​‌112009, 1309-1331‌back to text
• 22‌​‌ inproceedingsY.Yasushi Ito​​, A. M.Alan​​​‌ M. Shih and B.‌ K.Bharat K. Soni‌​‌. Reliable Isotropic Tetrahedral​​ Mesh Generation Based on​​​‌ an Advancing Front Method‌.International Meshing Roundtable‌​‌ conf. proc.2004back​​ to text
• 23 inproceedings​​​‌B.Bruno Lévy,‌ S.Sylvain Petitjean,‌​‌ N.Nicolas Ray and​​ J.Jérome Maillot.​​​‌ Least squares conformal maps‌ for automatic texture atlas‌​‌ generation.ACM transactions​​ on graphics (TOG)21​​​‌ACM2002, 362--371‌back to text
• 24‌​‌ articleB.B. Lévy​​ and E.E. Schwindt​​​‌. Notions of Optimal‌ Transport theory and how‌​‌ to implement them on​​ a computer.Computer​​​‌ and Graphics2018back‌ to text
• 25 article‌​‌M.Max Lyon,​​ D.David Bommes and​​​‌ L.Leif Kobbelt.‌ HexEx: Robust Hexahedral Mesh‌​‌ Extraction.ACM Transactions​​ on Graphics354​​​‌2016back to text‌
• 26 inproceedingsL.Loïc‌​‌ Maréchal. A New​​ Approach to Octree-Based Hexahedral​​​‌ Meshing.International Meshing‌ Roundtable conf. proc.2001‌​‌back to text
• 27​​ miscMeshMixer.http://www.meshmixer.com/​​​‌back to text
• 28‌ miscMeshlab.http://www.meshlab.net/‌​‌back to text
• 29​​ inproceedingsC.C. Mezian​​​‌, B.Bruno Vallet‌, B.Bahman Soheilian‌​‌ and N.Nicolas Paparoditis​​. Uncertainty Propagation for​​​‌ Terrestrial Mobile Laser Scanner‌.SPRS - International‌​‌ Archives of the Photogrammetry,​​ Remote Sensing and Spatial​​​‌ Information Sciences2016back‌ to text
• 30 article‌​‌A.Ashish Myles and​​ D.Denis Zorin.​​​‌ Controlled-distortion constrained global parametrization‌.ACM Trans. Graph.‌​‌3242013back​​ to text
• 31 article​​​‌M.M. Nieser,‌ U.U. Reitebuch and‌​‌ K.K. Polthier.​​ CubeCover - Parameterization of​​​‌ 3D Volumes.Computer‌ Graphics Forum305‌​‌2011, 1397-1406URL:​​ https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8659.2011.02014.xDOIback to​​​‌ text
• 32 miscJ.-H.‌Jae-Han Park, Y.-D.‌​‌Yong-Deuk Shin, J.-H.​​Ji-Hun Bae and M.-H.​​​‌Moon-Hong Baeg. Spatial‌ Uncertainty Model for Visual‌​‌ Features Using a Kinect​​ Sensor.2012back​​​‌ to text
• 33 misc‌Point Cloud Library.‌​‌http://www.pointclouds.org/downloads/back to text​​
• 34 articleN.Nicolas​​​‌ Ray, W. C.‌Wan Chiu Li,‌​‌ B.Bruno Lévy,​​ A.Alla Sheffer and​​​‌ P.Pierre Alliez.‌ Periodic global parameterization.‌​‌ACM Transactions on Graphics​​ (TOG)2542006​​​‌, 1460--1485back to‌ text
• 35 articleSchöberl‌​‌. NETGEN An advancing​​ front 2D/3D-mesh generator based​​​‌ on abstract rules.‌Computing and visualization in‌​‌ science111997​​back to text
• 36​​​‌ articleM.Mark Shephard‌ and M.Marcel Georges‌​‌. Automatic three-dimensional mesh​​​‌ generation by the finite​ octree technique.International​‌ Journal for Numerical Methods​​ in Engineering324​​​‌1991back to text​
• 37 articleH.Hang​‌ Si. TetGen, a​​ Delaunay-Based Quality Tetrahedral Mesh​​​‌ Generator.ACM Trans.​ on Mathematical Software41​‌22015back to​​ text
• 38 techreportJ.​​​‌J. Slotnick, A.​A. Khodadoust, J.​‌J. Alonso, D.​​D. Darmofal, G.​​​‌G. William, L.​L. Elizabeth and D.​‌D. Mavriplis. CFD​​ Vision 2030 Study: A​​​‌ Path to Revolutionary Computational​ Aerosciences.NASA/CR-2014-218178, NF1676L-18332​‌2014back to text​​
• 39 articleS.Sylvie​​​‌ Soudarissanane, R.Roderik​ Lindenbergh, M.Massimo​‌ Menenti and P.Peter​​ Teunissen. Scanning geometry:​​​‌ Influencing factor on the​ quality of terrestrial laser​‌ scanning points.ISPRS​​ Journal of Photogrammetry and​​​‌ Remote Sensing664​2011, 389 -​‌ 399URL: http://www.sciencedirect.com/science/article/pii/S0924271611000098DOI​​back to text
• 40​​​‌ inproceedingsM. L.Matthew​ L. Staten, S.​‌ J.Steven J. Owen​​ and T.Ted Blacker​​​‌. Unconstrained Paving &​ Plastering: A New Idea​‌ for All Hexahedral Mesh​​ Generation.International Meshing​​​‌ Roundtable conf. proc.2005​back to text
• 41​‌ articleT. J.Timothy​​ J. Tautges, T.​​​‌Ted Blacker and S.​ A.Scott A. Mitchell​‌. The whisker weaving​​ algorithm.International Journal​​​‌ of Numerical Methods in​ Engineering1996back to​‌ text
• 42 articleN.​​ P.N. P. Weatherill​​​‌ and O.O. Hassan​. Efficient three-dimensional Delaunay​‌ triangulation with automatic point​​ creation and imposed boundary​​​‌ constraints.International Journal​ for Numerical Methods in​‌ Engineering37121994​​, 2005--2039URL: http://dx.doi.org/10.1002/nme.1620371203​​​‌DOIback to text​
• 43 inproceedingsM.Markus​‌ Ylimäki, J.Juho​​ Kannala and J.Janne​​​‌ Heikkilä. Robust and​ Practical Depth Map Fusion​‌ for Time-of-Flight Cameras.​​Image AnalysisChamSpringer​​​‌ International Publishing2017,​ 122--134back to text​‌
• 44 inproceedingsY.Yongjie​​ Zhang and C.Chandrajit​​​‌ Bajaj. Adaptive and​ Quality Quadrilateral/Hexahedral Meshing from​‌ Volumetric Data.International​​ Meshing Roundtable conf. proc.​​​‌2004back to text​
• 45 incollectionM.Muyang​‌ Zhang, J.Jin​​ Huang, X.Xinguo​​​‌ Liu and H.Hujun​ Bao. A wave-based​‌ anisotropic quadrangulation method.​​ACM SIGGRAPH 20102010​​​‌back to text
• 46​ articleD.Du Zhengchun​‌, W.Wu Zhaoyong​​ and Y.Yang Jianguo​​​‌. Point cloud uncertainty​ analysis for laser radar​‌ measurement system based on​​ error ellipsoid model.​​​‌Optics and Lasers in​ Engineering792016,​‌ 78 - 84URL:​​ http://www.sciencedirect.com/science/article/pii/S0143816615002675DOIback to​​​‌ text
• 47 miscCgal​, Computational Geometry Algorithms​‌ Library.http://www.cgal.orgback​​ to text