Dans cette thèse, une approche pratique pour la génération de maillages triangulaires isotropes est proposée. En 2D comme en 3D, l'ob jectif consiste à mailler un domaine donné, pouvant avoir une géométrie complexe. L'approche présentée consiste à entrelacer des étapes de raffinement de Delaunay et des étapes d'optimisation de maillages dans le but de générer des maillages gradés de qualité. L'utilisateur peut contrôler les caractéristiques du maillage en définissant des critères de taille et de forme des simplexes, ainsi que de topologie et d'approximation. Les méthodes par éléments finis, largement utilisées en simulation, nécessitent des maillages gradés, composés de simplexes bien formés. Des alternatives aux méthodes de raffinement de Delaunay usuelles sont développées. Les méthodes d'optimisation de maillages proposées permettent d'optimiser la position des sommets intérieurs et de ceux du bord. Les caractéristiques du bord du domaine à mailler, et en particulier des arêtes vives, sont préservées par ces méthodes. En 2D, l'optimisation est basée sur l'algorithme de Lloyd et les diagrammes de Voronoi centrés (CVT). En 3D, une extension naturelle des triangulations de Delaunay optimales (ODT) de Chen, capable d'optimiser la position des sommets du bord du maillage, est introduite. Notre algorithme de maillage tétraédrique est enrichi par une étape de post-traitement permettant d'améliorer de façon significative la qualité des angles dièdres du maillage. Nous montrons que l'entrelacement d'étapes de raffinement et d'optimisation permet d'obtenir des maillages de meilleure qualité que ceux générés par les méthodes connues en termes d'angles dans les simplexes et de complexité.

Dans cette thèse, nous nous sommes intéressés au problème de l'extraction d'une surface à partir de la représentation volumique d'un objet. Dans ce but, nous nous sommes concentrés sur les méthodes de division spatiale. Ces approches divisent le volume afin de construire une approximation par morceaux de la surface de l'objet. L'idée générale consiste à faire des approximations surfaciques locales qui seront ensuite combinées pour extraire une surface unique représentant l'objet. Les approches basées sur l'algorithme " Marching Cubes " (MC) présentent des défaut par rapport à la qualité et l'adaptativité de la surface produite. Même si une considérable quantité d'améliorations ont été apportées à la méthode originale, la plus grande partie des algorithmes fournissent la solution à un ou deux défauts mais n'arrivent pas à surmonter toutes ses limitations.Les méthodes duales sont plus adaptées pour utiliser un échantillonnage adaptatif sur le volume d'intérêt. Ces méthodes reposent sur la génération de surfaces duales à celles construites par MC ou se basent sur des grilles duales. Elles construisent des maillages moins denses et en même temps capables de mieux approcher les détails de l'objet. De plus, des améliorations récentes garantissent que les maillages extraits ont de bonnes propriétés topologiques et géométriques.Nous avons étudié les caractéristiques spécifiques des objets volumiques par rapport à leur géométrie et à leur topologie. Nous avons exploré l'état de l'art sur les approches de division spatiale afin d'identifier leurs avantages et leurs inconvénients ainsi que les implications de leur utilisation sur des objets volumiques. Nous avons conclu qu'une approche duale était la mieux adaptée pour obtenir un bon compromis entre qualité du maillage et qualité de l'approximation. Dans un second temps, nous avons proposé et développé un pipeline de génération de surfaces basé sur une combinaison d'une approche duale et de la recherche de composantes connexes n-dimensionnels pour mieux reproduire la topologie et la géométrie des objets originels. Dans un troisième temps, nous avons présenté une extension "out-of-core" de notre chaîne de traitements pour l'extraction des surfaces à partir de grands volumes. Le volume est divisé pour générer des morceaux de surface de manière indépendante et garde l'information nécessaire pour les connecter afin de produire une surface unique topologiquement correcte.L'approche utilisée permet de paralléliser le traitement pour accélérer l'obtention de la surface. Les tests réalisés ont permis de valider la méthode sur des données volumiques massives. / In this document, we have been interested in the surface extraction from the volumetric representation of an object. With this objective in mind, we have studied the spatial subdivision surface extraction algorithms. This approaches divide the volume in order to build a piecewise approximation of the surface. The general idea is to combine local and simple approximations to extract a complete representation of the object's surface.The methods based on the Marching Cubes (MC) algorithm have problems to produce good quality and to handle adaptive surfaces. Even if a lot of improvements to MC have been proposed, these approaches solved one or two problems but they don't offer a complete solution to all the MC drawbacks. Dual methods are more adapted to use adaptive sampling over volumes. These methods generate surfaces that are dual to those generated by the Marching Cubes algorithm or dual grids in order to use MC methods. These solutions build adaptive meshes that represent well the features of the object. In addition, recent improvements guarantee that the produced meshes have good geometrical and topological properties.In this dissertation, we have studied the main topological and geometrical properties of volumetric objects. In a first stage, we have explored the state of the art on spatial subdivision surface extraction methods in order to identify theirs advantages, theirs drawbacks and the implications of theirs application on volumetric objects. We have concluded that a dual approach is the best option to obtain a good compromise between mesh quality and geometrical approximation. In a second stage, we have developed a general pipeline for surface extraction based on a combination of dual methods and connected components extraction to better capture the topology and geometry of the original object. In a third stage, we have presented an out-of-core extension of our surface extraction pipeline in order to extract adaptive meshes from huge volumes. Volumes are divided in smaller sub-volumes that are processed independently to produce surface patches that are later combined in an unique and topologically correct surface. This approach can be implemented in parallel to speed up its performance. Test realized in a vast set of volumes have confirmed our results and the features of our solution.

Cette thèse d'habilitation présente une synthèse de contributions dans le domaine du traitement numérique de la géométrie sous la forme de concepts et d'algorithmes pour la reconstruction de surfaces, l'approximation de surfaces, le remaillage quadrangle de surfaces et la génération de maillages.

Pour utiliser efficacement les moyens de simulation, l'analyse mécanique par éléments finis (ÉF) doit être préparée en posant les hypothèses et en simplifiant le domaine d'étude. L'adaptation des modèles de conception (CAO) pour le calcul se traduit par l'élimination des détails de forme et de topologie afin de générer un maillage ÉF dont la taille des éléments est adaptée au comportement mécanique et à la précision souhaitée (carte de tailles). Actuellement, la préparation des modèles CAO pour le calcul ÉF reste une tâche longue et difficile à cause du manque d'outils automatiques pour éliminer ces détails et générer des maillages adaptés. Notre travail contribue aux recherches concernant le passage entre les modèles CAO et les modèles de calcul ÉF en traitant trois points : la simplification des aspects de forme d'une pièce CAO, l'adaptation de la topologie du modèle BREP, la génération de maillages trans-carreaux. Nous proposons des critères d'identification de détails de forme qui reposent sur les caractéristiques de forme CAO et les besoins du maillage ÉF (carte de tailles, conditions aux limites). Ces critères identifient les transformations CAO nécessaires pour simplifier la forme du modèle. Nous avons mis en place la structure et les opérateurs de Topologie des Contraintes deMaillage (TCM), qui visent à adapter la topologie d'un modèle CAO pour représenter uniquement les entités pertinentes pour la génération du maillage. Les opérateurs TCM gèrent des transformations topologiques de haut niveau (par exemple découpage-suppression d'arête), et regroupent les surfaces et courbes sous-jacentes pour former des entités géométriques composites. Le processus d'adaptation est automatisé par des critères d'identification de détails qui déterminent automatiquement les opérations topologiques TCM nécessaires pour adapter la topologie aux contraintes du maillage : carte de tailles, géométrie, et zones de conditions aux limites. La dernière partie de notre contribution étend la génération de maillages par approche frontale aux entités géométriques composites. Cette extension propose la génération de trajectoires trans-carreaux pour la progression frontale et la construction des images des éléments sur les carreaux d'une surface composite. Cette méthode utilise la géométrie exacte du modèle, ne nécessite pas de re-paramétrisation, et présente l'avantage de ne pas être limitée par la topologie et la forme des surfaces composites.

Nous étudions dans cette thèse la génération de maillages anisotropes basée sur la triangulation de Delaunay et le diagramme de Voronoi. Nous considérons tout d'abord les maillages anisotropes localement uniformes, développés par Boissonnat, Wormser et Yvinec. Bien que l'aspect théorique de cette approche soit connu, son utilité pratique n'a été que peu explorée. Une étude empirique exhaustive est présentée et révèle les avantages, mais aussi les inconvénients majeurs de cette méthode. Dans un second temps, nous étudions les diagrammes de Voronoi anisotropes définis par Labelle et Shewchuk. Nous donnons des conditions suffisantes sur un ensemble de points pour que le dual du diagramme soit une triangulation plongée en toute dimension ; un algorithme générant de tels ensembles est conçu. Ce diagramme est utilisé pour concevoir un algorithme qui génère efficacement un maillage anisotrope pour des domaines de dimension intrinsèque faible plongés dans des espaces de dimension large. Notre algorithme est prouvable, mais les résultats sont décevants. Enfin, nous présentons le diagramme de Voronoi Riemannien discret, qui utilise des avancées récentes dans l'estimation de distances géodésiques et dont le calcul est grandement accéléré par l'utilisation d'un graphe anisotrope. Nous donnons des conditions suffisantes pour que notre structure soit combinatoirement équivalente au diagramme de Voronoi Riemannien et que son dual utilisant des simplexes droits mais aussi courbes est une triangulation plongée en toute dimension. Nous obtenons de bien meilleurs résultats que pour nos autres techniques, mais dont l'utilité reste limitée / In this thesis, we study the generation of anisotropic meshes using the concepts of Delaunay triangulations and Voronoi diagrams. We first consider the framework of locally uniform anisotropic meshes introduced by Boissonnat, Wormser and Yvinec. Despite known theoretical guarantees, the practicality of this approach has only been hardly studied. An exhaustive empirical study is presented and reveals the strengths but also the overall impracticality of the method. In a second part, we investigate the anisotropic Voronoi diagram introduced by Labelle and Shewchuk and give conditions on a set of seeds such that the corresponding diagram has a dual that is an embedded triangulation in any dimension; an algorithm to generate such sets is devised. Using the same diagram, we propose an algorithm to generate efficiently anisotropic triangulations of low-dimensional manifolds embedded in high-dimensional spaces. Our algorithm is provable, but produces disappointing results. Finally, we study Riemannian Voronoi diagrams and introduce discrete Riemannian Voronoi diagrams, which employ recent developments in the numerical computation of geodesic distances and whose computation is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete structure is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both straight and curved simplices. We obtain significantly better results than with our other methods, but the overall utility of

La Méthode des Éléments Finis (MEF) est probablement la technique la plus utilisée pour la modélisation du comportement mécanique des solides. Elle s'appuie pour cela sur une discrétisations du domaine modélisé en éléments géométrique simples. Cette partition porte le nom de maillage. La solution<br />numérique calculée par la MEF dépend directement du maillage utilisé. <br /><br />Dans le domaine médical, les solides modélisés sont de géométrie complexe. De ce fait, nous privilégions une génération de maillage par recalage élastique. Cette méthode permet d'adapter un maillage prédéfini (atlas) aux données du patient afin de représenter le domaine à modéliser. Le recalage élastique applique un déplacement aux sommets de l'atlas sans en changer sa topologie. Les méthodes de recalage élastique ne prennent cependant pas en considération les éléments, par conséquent il est possible de produire des éléments invalides et de mauvaise qualité. Cette thèse présente une méthode de réparation des éléments après application d'un recalage élastique.<br /><br />Les méthodes de recalage élastique peuvent être limitées lorsque, pour une région spécifique du domaine modélisé, une discrétisation plus fine est requise alors qu'elle ne figure pas dans le maillage atlas. Par exemple dans le domaine de la neurochirurgie, un maillage d'une densité plus importante peut être nécessaire dans la région de la voie d'abord, entre la craniotomie et la tumeur car dans cette région d'intérêt une précision accrue de la simulation est requise. Nous proposons dans cette thèse une méthode de génération de maillage comportant un raffinement local. Cette méthode est appliquée à la neurochirurgie.

La simulation numérique des écoulements (CFD) est largement utilisée aujourd'hui dans l'industrie aéronautique, de l'avant-projet à la conception des appareils. En parallèle, la puissance des calculateurs s'est accrue, permettant d'effectuer des simulations résolvant les équations de Navier-Stokes moyennées (RANS) dans un délai de restitution acceptable du point de vue industriel. Cependant, les configurations simulées sont de plus en plus complexes géométriquement, rendant la réalisation du maillage très coûteuse en temps humain. Notre objectif est de proposer une méthode permettant de simplifier la génération de maillages autour de géométries complexes, en exploitant les avantages de la méthode Chimère, tout en levant les difficultés principales rencontrées par cette méthode dans le calcul des connectivités. Dans notre approche, le domaine de calcul est découpé en régions proches et en régions éloignées des corps. Des grilles curvilignes de faible extension décrivent les régions autour des corps. Le maillage de fond est défini par un ensemble de grilles cartésiennes superposées aux grilles de corps, qui sont engendrées et adaptées automatiquement selon les caractéristiques de l'écoulement. Afin de traiter des maillages recouvrants autour de géométries complexes sans surcoût humain, les différentes grilles sont regroupées par composant Chimère. Des relations d'assemblage sont alors définies entre composants, en s'inspirant de la Géométrie de Construction des Solides (CSG), où un solide peut être construit par opérations booléennes successives entre solides primitifs. Le calcul des connectivités Chimère est alors réalisé de manière simplifiée. Des simulations RANS sont effectuées autour d'un fuselage d'hélicoptère avec mât de soufflerie et autour d'une aile NACA0015 en incidence, afin de mettre en oeuvre la méthode. / Computational fluid dynamics (CFD) is widely used today in aeronautics, while the computing power has increased, enabling to perform simulations solving Reynolds-averaged Navier-Stokes equations (RANS) within an acceptable time frame from the industrial point of view. However, the configurations are more and more geometrically complex, making the mesh generation step prohibitive. Our aim is here to propose a method enabling a simplification of the mesh generation over complex geometries, taking advantage of the Chimera method and overcoming the major difficulties arising when performing overset grid connectivity. In our approach, the computational domain is partitioned into near-body regions and off-body regions. Near-body regions are meshed by curvilinear grids of short extension describing the obstacles involved in the simulation. Off-body mesh is defined by a set of adaptive Cartesian grids, overlapping near-body grids. In order to consider overset grids over complex geometries with no additional cost, grids are gathered by Chimera component, and assembly relations are defined between them, inspired by Constructive Solid Geometry, where a solid can result from boolean operations between primitive solids. The overset grid connectivity is thus simplified. RANS simulations are performed over a helicopter fuselage with a strut, and over a NACA0015 wing.

La majorité des algorithmes de reconstruction de surface sont optimisés pour s'appliquer à des données de haute qualité. Les résultats obtenus peuvent alors être inutilisables si les données proviennent de solutions d'acquisition bon marché. Notre première contribution est un algorithme de reconstruction de surfaces à partir de données de stéréo vision. Il combine les informations liées aux points 3D avec les images calibrées afin de combler l'imprécision des données. L'algorithme construit une soupe de triangles 3D à l'aide des images calibrées et à l'issue d'une phase de prétraitement du nuage de points. Pour épouser au mieux la surface de la scène, on contraint cette soupe de triangle 3D à respecter des critères de visibilité et de photo-consistance. On calcule ensuite un maillage à partir de la soupe de triangles à l'aide d'une technique de reconstruction qui combine les triangulations de Delaunay contraintes et le raffinement de Delaunay. Notre seconde contribution est un algorithme qui construit, à partir d'un nuage de points 3D échantillonnés sur une surface, un maillage de surface qui représente fidèlement les arêtes vives. Cet algorithme génère un bon compromis entre précision et complexité du maillage. Dans un premier temps, on extrait une approximation des arêtes vives de la surface sous-jacente à partir du nuage de points. Dans un deuxième temps, on utilise une variante du raffinement de Delaunay pour générer un maillage qui combine les arêtes vives extraites avec une surface implicite obtenue à partir du nuage de points. Notre méthode se révèle flexible, robuste au bruit; cette méthode peut prendre en compte la résolution du maillage ciblé et un champ de taille défini par l'utilisateur. Nos deux contributions génèrent des résultats efficaces sur une variété de scènes et de modèles. Notre méthode améliore l'état de l'art en termes de précision.

Lors de simulations numériques d'ordre élevé, la discrétisation sous-paramétrique du domaine de calcul peut générer des erreurs dominant l'erreur liée à la discrétisation des variables. De nombreux travaux proposent d'utiliser l'analyse isogéométrique afin de mieux représenter les géométries et de résoudre ce problème. Nous présenterons dans ce travail le couplage du schéma aux résidus distribués limité et stabilisé de Lax-Frieirichs avec l'analyse isogéométrique. En particulier, nous construirons une famille de fonctions de base permettant de représenter exactement les coniques et définies tant sur les éléments triangulaires que quadrangulaires : les fonctions de base de Bernstein rationnelles. Nous nous intéresserons ensuite à la génération de maillages précis pour l'analyse isogéométrique. Notre méthode consiste à créer un maillage courbe à partir d'un maillage linéaire par morceaux de la géométrie. Le maillage obtenu en sortie de notre procédure est non-structuré, conforme et assure la continuité de nos fonctions de base sur tout le domaine. Pour finir, nous décrirons les différentes méthodes d'adaptation de maillages développées : l'élévation d'ordre et le raffinement isotrope. Bien évidemment, la géométrie exacte du maillage courbe d'entrée est préservée au cours des processus d'adaptation.

Lors de simulations numériques d’ordre élevé, la discrétisation sous-paramétrique du domaine de calcul peut générer des erreurs dominant l’erreur liée à la discrétisation des variables. De nombreux travaux proposent d’utiliser l’analyse isogéométrique afin de mieux représenter les géométries et de résoudre ce problème.Nous présenterons dans ce travail le couplage du schéma aux résidus distribués limité et stabilisé de Lax-Frieirichs avec l’analyse isogéométrique. En particulier, nous construirons une famille de fonctions de base permettant de représenter exactement les coniques et définies tant sur les éléments triangulaires que quadrangulaires : les fonctions de base de Bernstein rationnelles. Nous nous intéresserons ensuite à la génération de maillages précis pour l’analyse isogéométrique. Notre méthode consiste à créer un maillage courbe à partir d’un maillage linéaire par morceaux de la géométrie. Le maillage obtenu en sortie de notre procédure est non-structuré, conforme et assure la continuité de nos fonctions de base sur tout le domaine. Pour finir, nous décrirons les différentes méthodes d’adaptation de maillages développées : l’élévation d’ordre et le raffinement isotrope. Bien évidemment, la géométrie exacte du maillage courbe d’entrée est préservée au cours des processus d’adaptation. / During high order simulations, the approximation error may be dominated by the errors linked to the sub-parametric discretization used for the geometry representation. Many works propose to use an isogeometric analysis approach to better represent the geometry and hence solve this problem. In this work, we will present the coupling between the limited stabilized Lax-Friedrichs residual distributed scheme and the isogeometric analysis. Especially, we will build a family of basis functions defined on both triangular and quadrangular elements and allowing the exact representation of conics : the rational Bernstein basis functions. We will then focus in how to generate accurate meshes for isogeometric analysis. Our idea is to create a curved mesh from a classical piecewise-linear mesh of the geometry. We obtain a conforming unstructured mesh which ensures the continuity of the basis functions over the entire mesh. Last, we will detail the curved mesh adaptation methods developed : the order elevation and the isotropic mesh refinement. Of course, the adaptation processes preserve the exact geometry of the initial curved mesh.