publications | Franck Ledoux

2025

Validity-first automatic polycube labeling for CAD models

Sébastien Mestrallet, Christophe Bourcier, and Franck Ledoux

In SIAM International Meshing Roundtable 2025, Fort Worth, TX, USA, 3-6 March, 2025

Abs PDF Website

For many simulation codes, block-structured hex meshes re- main preferred while their automatic generation is unsolved. We investigate the usage of a polycube-based approach. More specifically, we focus on the labeling stage, which consists in assigning each boundary facet to one of the 6 signed principal axis. Similar works are confronted with 2 challenges: over- constraining validity criteria, and the conflated processing of validity criteria with quality metrics. We tackle these obstacles with automatic routines based on semi-global labeling oper- ators. Our approach is successfully tested on CAD models, which are of interest for many numerical simulation problems.
Monte Carlo Tree Search for Coarse Hex Blocking Generation

Paul Bourmaud, Rao Garimella, Navamita Ray, and 3 more authors

In SIAM International Meshing Roundtable 2025, Fort Worth, TX, USA, 3-6 March, 2025

Abs PDF

Decomposition of CAD models into shapes amenable for automatic meshing such as blocks is a crucial step in hexahedral mesh generation. In this paper, we propose a Monte Carlo Tree Search (MCTS) based approach to obtain possible decomposition solutions for a given CAD model which can be subsequently used for mesh generation. This prototype study shows promises in automating the decomposition of complex shapes into blocks and could be combined in the future with machine learning methods to enhance the method.

2024

Mixed-Order Meshes through rp-adaptivity for Surface Fitting to Implicit Geometries

Ketan Mittal, Veselin A. Dobrev, Patrick Knupp, and 4 more authors

2024

DOI

2023

Coupe: A Modular, Multi-threaded Mesh Partitioning Platform

Hubert Hirtz, Cédric Chevalier, Franck Ledoux, and 1 more author

In Euro-Par 2022: Parallel Processing Workshops: Euro-Par 2022 International Workshops, Glasgow, UK, August 22–26, 2022, Revised Selected Papers, Glasgow, United Kingdom, 2023

Abs DOI

Mesh partitioning used for load balancing in distributed numerical simulations is typically managed with tools that are good enough but not optimal. Their use scope is not explicitly dedicated to load balancing, and they cannot make use of all available information. In this paper, the mesh partitioning problem and the context for its use are precisely defined. Then, existing tools are presented, along with their characteristics and features that are missing. Finally, a new partitioning platform – the subject of my PhD thesis – is presented: its architecture, software engineering choices made along the way, and how it can be the best fit for load balancing distributed simulations. The platform is open-source and is hosted on GitHub: .
Block-structured quad meshing for supersonic flow simulations

Claire Roche, Franck Ledoux, Jérôme Breil, and 1 more author

In SIAM International Meshing Roundtable 2023, Amsterdam, 6-9 March, 2023

PDF
Coupe: a mesh partitioning platform

Cédric Chevalier, Hubert Hirtz, Franck Ledoux, and 1 more author

In SIAM International Meshing Roundtable 2023, Amsterdam, 6-9 March, 2023

PDF
Formal definition of hexahedral blocking operations using N-G-maps

Valentin Postat, Nicolas Le Goff, Simon Calderan, and 2 more authors

In SIAM International Meshing Roundtable 2023, Amsterdam, 6-9 March, 2023

PDF

2022

Robust Quantization for Polycube Maps

F. Protais, M. Reberol, N. Ray, and 3 more authors

Comput. Aided Des., Sep 2022

DOI
Evocube: A Genetic Labelling Framework for Polycube-Maps

C. Dumery, F. Protais, S. Mestrallet, and 2 more authors

Computer Graphics Forum, Sep 2022

Abs DOI

Abstract Polycube-maps are used as base-complexes in various fields of computational geometry, including the generation of regular all-hexahedral meshes free of internal singularities. However, the strict alignment constraints behind polycube-based methods make their computation challenging for CAD models used in numerical simulation via finite element method (FEM). We propose a novel approach based on an evolutionary algorithm to robustly compute polycube-maps in this context. We address the labelling problem, which aims to precompute polycube alignment by assigning one of the base axes to each boundary face on the input. Previous research has described ways to initialize and improve a labelling via greedy local fixes. However, such algorithms lack robustness and often converge to inaccurate solutions for complex geometries. Our proposed framework alleviates this issue by embedding labelling operations in an evolutionary heuristic, defining fitness, crossover, and mutations in the context of labelling optimization. We evaluate our method on a thousand smooth and CAD meshes, showing Evocube converges to accurate labellings on a wide range of shapes. The limitations of our method are also discussed thoroughly.
Hex-Mesh Generation and Processing: A Survey

Nico Pietroni, Marcel Campen, Alla Sheffer, and 7 more authors

ACM Trans. Graph., Oct 2022

DOI
Hex Me If You Can

P.-A. Beaufort, M. Reberol, D. Kalmykov, and 3 more authors

Computer Graphics Forum, Oct 2022

Abs DOI

Abstract HexMe consists of 189 tetrahedral meshes with tagged features and a workflow to generate them. The primary purpose of HexMe meshes is to enable consistent and practically meaningful evaluation of hexahedral meshing algorithms and related techniques, specifically regarding the correct meshing of specified feature points, curves, and surfaces. The tetrahedral meshes have been generated with Gmsh, starting from 63 computer-aided design (CAD) models from various databases. To highlight and label the diverse and challenging aspects of hexahedral mesh generation, the CAD models are classified into three categories: simple, nasty, and industrial. For each CAD model, we provide three kinds of tetrahedral meshes (uniform, curvature-adapted, and box-embedded). The mesh generation pipeline is defined with the help of Snakemake, a modern workflow management system, which allows us to specify a fully automated, extensible, and sustainable workflow. It is possible to download the whole dataset or select individual meshes by browsing the online catalog. The HexMe dataset is built with evolution in mind and prepared for future developments. A public GitHub repository hosts the HexMe workflow, where external contributions and future releases are possible and encouraged. We demonstrate the value of HexMe by exploring the robustness limitations of state-of-the-art frame-field-based hexahedral meshing algorithm. Only for 19 of 189 tagged tetrahedral inputs all feature entities are meshed correctly, while the average success rates are 70.9% / 48.5% / 34.6% for feature points/curves/surfaces.

2020

A Multilevel Mesh Partitioning Algorithm Driven by Memory Constraints

Cédric Chevalier, Franck Ledoux, and Sébastien Morais

Oct 2020

Abs DOI

Abstract Running numerical simulations on HPC architectures requires distributing data to be processed over the various available processing units. This task is usually done by partitioning tools, whose primary goal is to balance the workload while minimizing inter-process communication. However, they do not take the memory load and memory capacity of the processing units into account. As this can lead to memory overflow, we propose a new approach to address mesh partitioning by including ghost cells in the memory usage and by considering memory capacity as a strong constraint to abide. We model the problem using a bipartite graph and present a new greedy algorithm that aims at producing a partition according to the memory capacity. This algorithm focuses on memory consumption, and we use it in a multi-level approach to improving the quality of the returned solutions during the refinement phase. The experimental results obtained from our benchmarks show that our approach can yield solutions respecting memory constraints for instances where traditional partitioning tools fail.

2019

Guaranteed quality-driven hexahedral overlay grid method

Nicolas Le Goff, Franck Ledoux, Jean-Christophe Janodet, and 1 more author

In 28th International Meshing Roundtable, Buffalo, USA, Oct 2019

PDF
Dual-based user-guided hexahedral block generation using frame fields

Simon Caldéran, Franck Ledoux, and Guillaume Hutzler

In 28th International Meshing Roundtable, Buffalo, USA, Oct 2019

PDF
Hexahedral Overlay Grid Method with Guaranteed Element Quality

Nicolas Le Goff, Franck Ledoux, Jean-Christophe Janodet, and 1 more author

In IX International Conference on Adaptive Modeling and Simulation (ADMOS 2019), Alicante, Spain, May 2019. CIMNE, Oct 2019

PDF
Accurate Manycore-Accelerated Manifold Surface Remesh Kernels

Hoby Rakotoarivelo, and Franck Ledoux

Oct 2019

Abs DOI

In this work, we devise surface remesh kernels suitable for massively multithreaded machines. They fulfill the locality constraints induced by these hardware, while preserving accuracy and effectiveness. To achieve that, our kernels rely on: a point projection based on geodesic computations,a mixed diffusion-optimization smoothing kernel,an optimal direction-preserving transport of metric tensors,a fine-grained parallelization dedicated to manycore architectures.

2018

Hexahedral mesh modification to preserve volume

Nicolas Le Goff, Franck Ledoux, and Steven Owen

Computer-Aided Design, Oct 2018

Abs DOI

In this work, we provide a new post-processing procedure for automatically adjusting node locations of an all-hex mesh to better match the volume of a reference geometry. This process is particularly well-suited for mesh-first approaches, as overlay grid ones. In practice, hexahedral meshes generated via an overlay grid procedure, where a precise reference geometry representation is unknown or is impractical to use, do not provide for precise volumetric preservation. A discrete volume fraction representation of the reference geometry MI on an overlay grid is compared with a volume fraction representation of a 3D finite element mesh MO. This work introduces the notion of localized discrepancy between MI and MO and uses it to design a procedure that relocates mesh nodes to more accurately match a reference geometry. We demonstrate this procedure on a wide range of hexahedral meshes generated with the Sculpt code and show improved volumetric preservation while still maintaining acceptable mesh quality.
Hex-dominant meshing: Mind the gap!

Nicolas Ray, Dmitry Sokolov, Maxence Reberol, and 2 more authors

Computer-Aided Design, Oct 2018

Proceeding of SPM 2018 Symposium

Abs DOI

We propose a robust pipeline that can generate hex-dominant meshes from any global parameterization of a tetrahedral mesh. We focus on robustness in order to be able to benchmark different parameterizations on a large database. Our main contribution is a new method that integrates the hexahedra (extracted from the parameterization) into the original object. The main difficulty is to produce the boundary of the result, composed of both faces of hexahedra and tetrahedra. Obviously, this surface must be a good approximation of the original object but, more importantly, it must be possible to remesh the volume bounded by this surface minus the extracted hexahedra (called void). We enforce these properties by carefully tracking and eliminating all possibilities of failure at each step of our pipeline. We tested our method on a large collection of objects (200+) with different settings. In most cases, we obtained results of very good quality as compared to the state-of-the-art solutions. To ease reproducing our results and benchmarks, we provide a C++ implementation of the pipeline in the supplemental materials.

2017

Scalable fine-grained metric-based remeshing algorithm for manycore/NUMA architectures

Hoby Rakotoarivelo, Franck Ledoux, Franck Pommereau, and 1 more author

In Lecture Notes in Computer Science, Aug 2017

Abs DOI PDF

In this paper, we present a fine-grained multi-stage metric-based triangular remeshing algorithm on manycore and NUMA architectures. It is motivated by the dynamically evolving data dependencies and workload of such irregular algorithms, often resulting in poor performance and data locality at high number of cores. In this context, we devise a multi-stage algorithm in which a task graph is built for each kernel. Parallelism is then extracted through fine-grained independent set, maximal cardinality matching and graph coloring heuristics. In addition to index ranges precalculation, a dual-step atomic-based synchronization scheme is used for nodal data updates. Despite its intractable latency-boundness, a good overall scalability is achieved on a NUMA dual-socket Intel Haswell and a dual-memory Intel KNL computing nodes (64 cores). The relevance of our synchronization scheme is highlighted through a comparison with the state-of-the-art.
Volume preservation improvement for interface reconstruction hexahedral methods

Nicolas Le Goff, Franck Ledoux, and Steven Owen

Procedia Engineering, Aug 2017

26th International Meshing Roundtable, IMR26, 18-21 September 2017, Barcelona, Spain

Abs DOI

We propose a new post-processing procedure for automatically adjusting node locations of an all-hex mesh to better match the volume of a reference geometry. Hexahedral meshes generated via an overlay grid procedure, where a precise reference geometry representation is unknown or is impractical to use, do not provide for precise volumetric preservation. A discrete volume fraction representation of the reference geometry MI on an overlay grid is compared with a volume fraction representation of a 3D finite element mesh MO. This work proposes a procedure that uses the localized discrepancy between MI and MO to drive node relocation operations to more accurately match a reference geometry. We demonstrate this procedure on a wide range of hexahedral meshes generated with the Sculpt code and show improved volumetric preservation while still maintaining acceptable mesh quality.
Hex-dominant meshing for CAD models with boundary-alignment constraints

Franck Ledoux, Bruno Lévy, Nicolas Ray, and 1 more author

In VIII International Conference on Adaptive Modeling and Simulation (ADMOS 2017), Verbania, Italia, June 2017. CIMNE. , Aug 2017

PDF

2016

Fine-grained Locality-aware Parallel Scheme for Anisotropic Mesh Adaptation

Hoby Rakotoarivelo, Franck Ledoux, and Franck Pommereau

Procedia Engineering, Aug 2016

25th International Meshing Roundtable

Abs DOI

In this paper, we provide a fine-grained parallel scheme for anisotropic mesh adaptation on NUMA11Non-Uniform Memory Access architectures. Data dependencies are expressed by a graph for each kernel, and concurrency is extracted through fine-grained graph coloring. Tasks are structured into bulk-synchronous steps to avoid data races and to aggregate shared-data accesses. To ensure performance prediction, time cost and load imbalance are theoretically characterized. The devised scheme was evaluated on a 4 NUMA node (2-socket) machine, and a mean efficiency of 70% was reached on 32 cores for 3 kernels out of 4. The impact of irregular degree distribution and data layout on scalability is highlighted.
FPT Approximation Algorithm for Scheduling with Memory Constraints

Eric Angel, Cédric Chevalier, Franck Ledoux, and 2 more authors

In European Conference on Parallel Processing, Aug 2016
Analysis of non-meshable automatically generated frame fields

Ryan Viertel, Matt Staten, and Franco Ledoux

In 25th International Meshing Roundtable, Aug 2016

Abs PDF

Recent methods for frame field generation in two and three dimensions are reviewed. Frame fields generated automatically in 2D and 3D are analyzed with respect to quad and hex mesh generation. Problems are identified with automatically generated frame fields that prevent mesh generation via current methods. Specifically, there exist geometries that contain limit cycles and cannot be parameterized or decomposed by separatrices of the frame field. In 3D, singularity lines occur that minimize the field curvature but do not align with the frame field. These types of singularities make it impossible to create a mesh that both follows the frame field, and simultaneously respects the singularity as an irregular node in the mesh. Specific examples are presented that illustrate these problems. For each example, streamlines are used to help visualize properties of the frame fields, problems are analyzed, and options to potentially mitigate such problems are discussed.
Smoothness driven frame field generation for hexahedral meshing

N. Kowalski, F. Ledoux, and P. Frey

Computer-Aided Design, Aug 2016

23rd International Meshing Roundtable Special Issue: Advances in Mesh Generation

Abs DOI

For many years, providing an algorithm to generate hexahedral meshes that fulfill minimal geometric criteria (boundary-alignment, minimum of singularity vertices) and that is not limited to a category of geometries has been an open issue. In the past couple of years, techniques using 3D frame fields have emerged to design such meshes (Huang et al., 2011; Li et al., 2012). Those methods are based on a two-step process where a 3D frame field is built by assigning a frame to each cell of a tetrahedral mesh, then a parametrization algorithm is applied to generate a hexahedral mesh. In this work, we propose a novel algorithm to generate block-structured hexahedral meshes for any CAD domain Ω. This work differs from previous ones in many points: (1) the proposed approach does not need to start from a pre-meshed quad boundary; (2) The frame field initialization does not put singularity lines around the medial object of Ω; (3) Conceptually, frames are assigned to the vertices and not to the cells of the tetrahedral mesh; (4) The parametrization process is replaced by a constructive algorithm that generates a block structure, which partitions Ω in meshable regions.

2015

Automatic domain partitioning for quadrilateral meshing with line constraints

Nicolas Kowalski, Franck Ledoux, and Pascal Frey

Eng. with Comput., Jul 2015

Abs DOI

In this paper, we present an algorithm for partitioning any given 2D domain into regions suitable for quadrilateral meshing. It is able to preserve the symmetry of the domain if any, and can deal with inner boundaries and multidomain geometries. Moreover, this method keeps the number of singularities at the junctions of the regions to a minimum. Although each part of the domain, being four-sided, can be easily meshed using a structured method, we provide a meshing process that guarantees near perfect quality for most quadrilaterals of the resulting mesh. The partitioning stage is achieved by solving a PDE-constrained equation based on the geometric properties of the domain boundaries. An analysis of the generated mesh quality is provided at the end, showcasing that the meshes obtained through our algorithm are especially suitable for finite element methods.

2014

Block-structured Hexahedral Meshes for CAD Models Using 3D Frame Fields

N. Kowalski, F. Ledoux, and P. Frey

Procedia Engineering, Jul 2014

23rd International Meshing Roundtable (IMR23)

Abs DOI

In the past couple of years, techniques using 3D frame fields have emerged to design hexahedral meshes[1,2]. Those methods are based on a two-step process where a 3D frame field is built by assigning a frame to each cell of a tetrahedral mesh, then a parametrization algorithm is applied to generate a hexahedral mesh. In this paper, we propose a novel algorithm to generate block-structured hexahedral meshes for any CAD domain Ω. This work differs from previous ones in several points: (1) the proposed approach does not start from a pre-meshed boundary; (2) The frame field initialization does not put singularity lines around the medial object of Ω; (3) Frames are assigned to the vertices and not to the cells of the tetrahedral mesh; (4) We do not perform a parametrization process but we generate a block structure that partition Ω in meshable regions.

2013

An imprinting algorithm to insert geometric details into hexahedral meshes

Nicolas Le Goff, Franck Ledoux, and Jean-Christophe Weill

In VI International Conference on Adaptive Modeling and Simulation (ADMOS 2013), pages 412–423, Lisbon, Portugal, June 2013.CIMNE., Jul 2013

Abs PDF

In numerous computational engineering applications, hexahedral meshes may be preferred over tetrahedral meshes. However, automatic hexahedral meshing remains an unsolved issue and thus generating a hexahedral mesh is known as a time-consuming stage that requires a lot of user interactions in the simulation process. A possible way for designing and optimizing a CAD model or a geometric shape requires parametric studies where the shape is enriched by inserting geometric details into it. Then we must ”adapt” the initial mesh and not generate it anew for each new detail taken into account. In order to perform such studies with hexahedral meshes, we provide an imprinting method allowing us to automatically add geometric details into an existing mesh. This addition is done using geometric projections, sheets (layers of hexahedral elements) insertions and combinatorial algorithms while preserving the hexahedral mesh structure as best as possible.
A PDE Based Approach to Multidomain Partitioning and Quadrilateral Meshing

Nicolas Kowalski, Franck Ledoux, and Pascal Frey

In Proceedings of the 21st International Meshing Roundtable, Jul 2013

Abs

In this paper, we present an algorithm for partitioning any given 2d domain into regions suitable for quadrilateral meshing. It can deal with multidomain geometries with ease, and is able to preserve the symmetry of the domain. Moreover, this method keeps the number of singularities at the junctions of the regions to a minimum. Each part of the domain, being four-sided, can then be meshed using a structured method. The partitioning stage is achieved by solving a PDE constrained problem based on the geometric properties of the domain boundaries.
A Constraint-Based System to Ensure the Preservation of Sharp Geometric Features in Hexahedral Meshes

Franck Ledoux, Nicolas Le Goff, Steve J. Owen, and 2 more authors

In Proceedings of the 21st International Meshing Roundtable, Jul 2013

Abs

Generating a full hexahedral mesh for any 3D geometric domain is still a challenging problem. Among the different attempts, the octree-based methods are the most efficient from an engineering point of view. But the main drawback of such methods is the lack of control near the boundary. In this work, we propose an a posteriori technique based on the notion of the fundamental mesh in order to improve the mesh quality near the boundary. This approach is based on the resolution of a constraint problem defined on the topology of the CAD model that we have to discretize.

2012

A new exceptional points method with application to cell-centered Lagrangian schemes and curved meshes

A. Claisse, B. Després, E. Labourasse, and 1 more author

Journal of Computational Physics, Jul 2012

Abs DOI

The aim of this paper is the numerical simulation of compressible hydrodynamic strong implosions, which take place for instance in Inertial Confinement Fusion. It focuses in particular on two crucial issues, for such calculations: very low CFL number at the implosion center and approximation error on the initial geometry. Thus, we propose an exceptional points method, which is translation invariant and suitable to curved meshes. This method is designed for cell-centered Lagrangian schemes (GLACE [8], [13], [14], EUCCLHYD [25], [26], [27], [28], [29]). Several numerical examples on significant test cases are presented to show the relevance of our approach.
Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Nicolas Kowalski, Franck Ledoux, Matthew L. Staten, and 1 more author

Eng. with Comput., Jul 2012

Abs

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for arbitrary geometries is still an open problem. This layered structure usually requires topological modifications to propagate globally, thus preventing the general development of meshing algorithms such as Delaunay’s algorithm for tetrahedral meshes or the advancing-front algorithm based on local decisions. To automatically produce an acceptable hexahedral mesh, we claim that both global geometric and global topological information must be taken into account in the mesh generation process. In this work, we propose a theoretical classification of the layers or sheets participating in the geometry capture procedure. These sheets are called fundamental, or fun-sheets for short, and make the connection between the global layered structure of hexahedral meshes and the geometric surfaces that are captured during the meshing process. Moreover, we propose a first generation algorithm based on fun-sheets to deal with 3D geometries having 3- and 4-valent vertices.
Load Balancing for Mesh Based Multi-Physics Simulations in the Arcane Framework

Cédric Chevalier, and Franck Ledoux

In B.H.V. Topping, (Editor), "Proceedings of the Eighth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 4, Jul 2012

Abs DOI

On large computers, numerical simulation codes run using distributed memory on a large number of processing units. This implies that many technical issues must be addressed to achieve good performance including: data distribution, data exchange between processes, load balancing, etc. In an industrial context, this can be addressed by using a development framework such as Arcane. Arcane manages all technical aspects while ensuring high performance using thousands of cores. In this paper the focus is on improving the timings for various dynamic mesh based multi-physics simulations by optimising the data distribution. The goal is to determine the assignment of the mesh entities on the processors in a way that the overall running time of the simulation is the lowest. This is mainly a load balancing problem which can be solved as a mesh partitioning problem. Graph or hypergraph partitioning tools, such as ParMetis, Scotch or Zoltan can be used to solve it. The paper demonstrates how to efficiently use these tools to solve load balancing issues. Through dynamic multi-physics experiments it is shown that good framework driven load balancing can be achieved by using appropriate characterisations of computational costs. It is shown that a fully automated characterisation based on timing measures is generally not sufficient to obtain good load balancing, especially for multi-step simulations. Ideally, each phase of the simulation might be characterised by an elementary cost associated with each cell of the mesh. For dynamic simulations, timings, even one for each physics phase, do not perfectly fit. In this paper, an approach is proposed, that requires a minimal instrumentation of physics code implementation to count elementary costs. Using the approach, a mono or multi criteria graph partitioning can be used to achieve better quality mesh distributions. For mono-criterion partitioning, it is shown that the Arcane framework can be used to perform a correct merging of each phase criterion into a single one by load balancing the memory, which can be accurately computed knowing only the number of entities as their associated data are Arcane variables. Using these methods, good speed-ups can be achieved on large complex two- or three-dimensional simulations with millions of mesh cells and millions of highly mobile particles, specially at a large scale (thousands of MPI processes). These methods and observations are not specific to the Arcane framework and may also benefit any dynamic simulation codes. Some issues with standard graph models for mesh and current graph partitioning tools are described. Some have to be solved in the future to enable really efficient exascale computing for this kind of simulation
An Independent Mesh Model Process to Write Meshing Algorithms

Charles De Bellabre, Franck Ledoux, and Jean-Christophe Weill

In B.H.V. Topping, (Editor), "Proceedings of the Eighth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 32, Jul 2012

Abs DOI

One of the main building blocks of computational simulations is the mesh data structure. Depending on the numerical approximation methods or the meshing algorithm to be implemented, the mesh data structure must provide drastically different features. In order to provide a single and uniform way to handle any type of meshes, general meshing infrastructures have been developed in the last few years. In this work, is on one of them, the C++ generic mesh data structure (GMDS) framework, which intensively uses generic programming, and allows users to select the mesh model, i.e. a combination of available cells and connections, that best fits their requirements. At compile-time, the GMDS provides a tailored mesh data structure both in computation time and memory footprint, which fits as best as possible the algorithm requirements. A mesh framework such as GMDS provides code sharing and a uniform access to any kind of mesh model whatever the developer’s requirements. However, some main issues remain to be solved in an industrial context: how to select the mesh model that best fits the requirements of an algorithm? and how to combine algorithms requiring different mesh models without space memory duplication? In order to provide a first answer, a new level of abstraction has been added into GMDS: for any mesh model, at compile-time some pieces of C++ source code to retrieve the connections that are not kept in memory according to the mesh model are built. These pieces of source code are a direct implementation of combinatorial terms that must be exhibited to build missing connections. For instance, if an algorithm is built for a mesh model where nodes, edges and faces are available and the connection from faces to edges and edges to nodes are kept in memory, it is possible to obtain the nodes of a face by traversing its adjacent edges. In order to illustrate the benefits of this approach, an algorithm is implemented that generates a Delaunay triangulation. The source code obtained runs for 105 different mesh models with different performances both in computational time and memory footprint

2010

Topological and geometrical properties of hexahedral meshes

Franck Ledoux, and Jason Shepherd

Eng. with Comput., Aug 2010

Abs

Over the years, there have been a number of practical studies with working definitions of ‘mesh’ as related to computational simulation, however, there are only a few theoretical papers with formal definitions of mesh. Algebraic topology papers are available that define tetrahedral meshes in terms of simplices. Algebraic topology and polytope theory has also been utilized to define hexahedral meshes. Additional literature is also available describing particular properties of the dual of a mesh. In this paper, we give several formal definitions in relation to hexahedral meshes and the dual of hexahedral meshes. Our main goal is to provide useful, understandable and minimal definitions specifically for computer scientists or mathematicians working in hexahedral meshing. We also extend these definitions to some useful classifications of hexahedral meshes, including definitions for ‘fundamental’ hexahedral meshes and ‘minimal’ hexahedral meshes.
Hexahedral Mesh Matching: Converting non-conforming hexahedral-to-hexahedral interfaces into conforming interfaces

Matthew L. Staten, Jason F. Shepherd, Franck Ledoux, and 1 more author

International Journal for Numerical Methods in Engineering, Aug 2010

Abs DOI

Abstract This paper presents a new method, called Mesh Matching, for handling non-conforming hexahedral-to-hexahedral interfaces for finite element analysis. Mesh Matching modifies the hexahedral element topology on one or both sides of the interface until there is a one-to-one pairing of finite element nodes, edges and quadrilaterals on the interface surfaces, allowing mesh entities to be merged into a single conforming mesh. Element topology is modified using hexahedral dual operations, including pillowing, sheet extraction, dicing and column collapsing. The primary motivation for this research is to simplify the generation of unstructured all-hexahedral finite element meshes. Mesh Matching relaxes global constraint propagation which currently hinders hexahedral meshing of large assemblies, and limits its extension to parallel processing. As a secondary benefit, by providing conforming mesh interfaces, Mesh Matching provides an alternative to artificial constraints such as tied contacts and multi-point constraints. The quality of the resultant conforming hexahedral mesh is high and the increase in number of elements is moderate. Copyright © 2009 John Wiley & Sons, Ltd.
Topological modifications of hexahedral meshes via sheet operations: a theoretical study

Franck Ledoux, and Jason Shepherd

Eng. with Comput., Aug 2010

Abs

Recently there has been a renewed interest in performing topological modifications on hexahedral meshes to enable clean up, mesh improvement, generation of more complex hexahedral topologies, and a deepened understanding of methods for producing hexahedral topologies in increasingly complex geometries. Additionally, generation of all-hexahedral topologies in arbitrary models remains an open-problem in the computational geometry community. In this paper we provide surveys of important research efforts in local hexahedral topology modification, and provide some formalization of many of these methods. We also provide some additional proofs giving credance to the community held notion that these topology modifications are feasible despite the historic difficulty in developing the methodologies for performing the modifications. Additionally, some formalization of modification operations will be provided for hexahedral sheet-based methods and a demonstration of how these operations are related to the atomic operations proposed by Tautges et al.
Definition of a Generic Mesh Data Structure in the High Performance Computing Context

Franck Ledoux, Jean-Christophe Weill, and Yves Bertrand

In B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero, (Editors), "Developments and Applications in Engineering Computational Technology", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 3, Aug 2010

Abs DOI

One of the main building blocks of computational simulations is the mesh data structure. Depending on the numerical approximation methods or the meshing algorithm to implement, the mesh data structure can have to provide drastically different features. Some algorithms require a full tetrahedral mesh where nodes and tetrahedra are stored while others require a full hexahedral mesh with the knowledge of faces and specific topological connections. As each application requires different features, a usual issue is to develop a mesh data structure tailored for each application. We claim that this approach is not the right one in an industrial context. First, from a software engineering point of view, it is better to reuse existing solutions and thus to consider at least the object-oriented paradigm. Second, the development of a mesh data structure is a difficult and time-consuming task, especially in the high performance computing context (HPC) context, i.e. massive parallel distributed-memory architectures. For these reasons, the need for general meshing infrastructures has been recognised and several development efforts have been undertaken in the last few years. But none of these different solutions fits our requirements: we want a generic framework allowing the developer to select the type of cells and the incidence and adjacency relationships that must be stored in the mesh; the mesh data structure must efficiently support mesh modification in sequential and in parallel and it must not consume too much memory. This last point is particularly crucial in the HPC context. Indeed, HPC architectures tend to use more and more processors and to have a global distributed memory space that expands, but the memory space per processor tends to decrease. Thus, we have developed a mesh data framework which is a C++ library called GMDS, for generic mesh data structure. Generic is used here with two meanings: first, this data structure can handle any combination of available cells and connections; second, it is based on the generic programming paradigm. Currently, GMDS provides two mesh representations. The first one is a traditional cell-based model that is optimised in memory consumption while the second one is based on the combinatorial map model, which is greedier in memory consumption. In this chapter, we review different existing mesh representations and libraries and we describe the main specificity of the GMDS framework. Especially, we show how generic programming and the usage of local ids, instead of pointers, help us to minimise the memory consumption. We also show the parallelism model used in GMDS. This model is based on a traditional master-slave model that minimises the duplication of data on each processor. Moreover, we give some details about the cell migration process, which is implemented in GMDS

2008

Local Topological Modification of Hexahedral Meshes Part II: Combinatorics and Relation to Boy Surface

Katerina Jurkova, Franck Ledoux, Raphael Kuate Rickmeyer, and 2 more authors

In ESAIM: Proc. CEMRACS 2007, Aug 2008

Abs DOI PDF

Hexahedral meshes are structured as a set of ordered layer of hexes which makes local topological modifications difficult to do. For instance, removing an hex generally implies to remove a complete layer of hexes. Few works focus on local topological modifications in hexahedral meshes. In this paper, we provide some results which extend and complete some existing works [1,14,15,17], proving in a first part that the flipping operations defined by M. BERN and D. EPPSTEIN are combinatorially free and showing in a second part how to introduce a Boy surface into a dual mesh. This operation allows us to modify the parity of the number of hexes in the primal mesh, thing that can not be done by the M. BERN and D. EPPSTEIN basis of operations.
An Extension of the Reliable Whisker Weaving Algorithm

Franck Ledoux, and Jean-Christophe Weill

In Proceedings of the 16th International Meshing Roundtable, Aug 2008

Abs DOI

In many FEM applications, hexahedral meshes are necessary to get the best results. However the automatic generation of an hexahedral mesh from an arbitrary 3D geometry still remains a challenge. In this paper, we propose an extension of the reliable Whisker Weaving algorithm [6]. The Whisker Weaving algorithm starts from a pre-meshed quadrilateral surface, it generates hexahedral meshes for a large spectrum of 3D geometries successfully, but it often creates poor-shaped hex elements. We show that considering geometric information in the shrinking loop selection process can provide better results. We introduce criteria to handle non-convex geometries, parallel loops and sheets bounded by several loops.

2006

A Pragmatic Coupled Approach to Fit Three-Dimensional Meshes onto CAD Geometries

Franck Ledoux, Eric Brière l’Isle, and Jean-Christophe Weill a

In B.H.V. Topping, G. Montero, R. Montenegro, (Editors), "Proceedings of the Fifth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 7, Aug 2006

Abs DOI

In many areas, it is crucial to get the mesh to properly follow the geometry. For instance, small variations in node position in a fluid flow simulation may provide chaotic result such as that of Rayleigh-Taylor instabilities. Conceptually, the easiest way to ensure the right level of accuracy is to perform the meshing with tight integration to the CAD geometry. Unfortunately our requirements drive us to another solution where CAD geometry generation and mesh generation are performed by separated tools. So we suggest a coupled approach between our own CAD system and the ICEM-CFD Hexa mesher [1] to produce high quality meshes while maintaining geometry accuracy. Our process is as follows: the CAD model is created in our CAD tool then exported to ICEM-CFD Hexa; the mesh is generated in ICEM-CFD Hexa; finally the mesh is brought back into our CAD tool where mesh nodes are projected onto the geometry. The numerical schemes that we use to simulate unsteady compressible flows require hexahedral mesh elements. Moreover our applications require a high level of accuracy. In some cases, the distance between mesh nodes and their geometric surfaces must be exact according to the floating point representation. The range of CAD-meshing tools we have studied does not guarantee a sufficient level of accuracy. Besides, the users of our software want a simple dedicated CAD-meshing tool that fits to their needs and not a complete and complex tool. Thus we are designing our own tools. As writing a complete hexahedral CAD-meshing tool is a huge task, we started by focusing on the accuracy problem. To achieve this goal, we suggest a loosely coupled approach where CAD generation is performed by our own CAD system and the mesh is generated by ICEM-CFD Hexa. Oceane is our own CAD-meshing tool built on open-source components: Open Cascade [2] (geometric kernel), VTK (visualization), Qt (user interface), Python (scripting) and Mesquite [3] (smoothing). Oceane users can build 3D geometric objects from 2D ones by applying revolution or sweeping. They can also generate primitive 3D geometric objects, perform Boolean operations, exchange data with commercial software (IGES/STEP formats), view and analyse meshes and so on. Here we describe our CAD-meshing process. First, the geometry is generated inside Oceane. This is the definition for the reference geometry. The geometry is then exported to ICEM CFD Hexa using either IGES or STEP format. We generate a hexahedral mesh with ICEM CFD Hexa. This mesh is then imported into our CAD system to check it against the reference geometry. To do that, we associate each mesh surface with one or more geometric surfaces. We select the mesh surfaces that we want to correct and Oceane performs the projection. A smoothing algorithm is then applied to spread the mesh surfaces modifications onto the complete surface mesh. Finally, the volume mesh is untangled and smoothed. The projection of mesh nodes onto geometric surfaces is driven by two main reasons. First, to work with a commercial tool like ICEM-CFD Hexa, we have to translate a geometric model designed in Oceane into a standard exchange format (IGES or STEP) readable by another tool. The geometry is so translated twice before getting a mesh. As not all software read and write IGES/STEP formats consistently, the loss of accuracy may be huge. Besides, even in an integrated CAD-meshing tool, the projection of the mesh onto the geometry must be done carefully. The atomic operation of mesh correction performed by Oceane is the orthogonal projection of a mesh node onto geometry. In our process, a mesh node may belong to one or more mesh surfaces, and each mesh surface may be associated to one or more geometric surfaces. So to avoid side effects, we take particular configurations into account. For instance, if a node belongs to only one mesh surface, we project the mesh node onto its corresponding geometric surfaces and we take the nearest projecting point. If a node belongs to two mesh surfaces, it must be projected onto a geometric curve or a set of geometric curves. Several particular cases are identified and treated. The first results of this approach allow us to get a satisfying level of accuracy. The use of both Open Cascade and Mesquite libraries has permitted us to smooth the mesh surfaces and to project them onto geometric surfaces. Moreover, this projecting algorithm could be used in the hexahedral mesh algorithms that we want to integrate into Oceane.

2002

Geometric Modelling with CASL

Franck Ledoux, Agnès Arnould, Pascale Le Gall, and 1 more author

In Recent Trends in Algebraic Development Techniques, Aug 2002

Abs DOI

This paper presents an experiment that demonstrates the feasibility of successfully applying CASL to design 3D geometric modelling software. It presents an abstract specification of a 3D geometric model, its basic constructive primitives together with the definition of the rounding high-level operation. A novel methodology for abstractly specifying geometric operations is also highlighted. It allows one to faithfully specify the requirements of this specific area and reveals new mathematical definitions of geometric operations. The key point is to introduce an inclusion notion between geometric objects, in such a way that the result of an operation is defined as the smallest or largest object satisfying some pertinent criteria. This work has been made easier by using different useful CASL features, like first-order logic, free types or structured specifications. Some assets of this specification are to be abstract, readable by researchers in geometric modelling and to simplify the programming process.

2000

Formal specification for a mathematics-based application domain: geometric modeling.

Franck Ledoux, Jean-Marc Mota, Agnès Arnould, and 3 more authors

Aug 2000

Rapport LaMI n°51, Université d’Evry-Val d’Essonne, Evry, ftp://ftp.lami.univ-evry.fr/pub/publications/reports/index.html