Il y a une décennie, le contenu numérique virtuel était limité à quelques applications - majoritairementles jeux vidéos, les films en 3D et la simulation numérique. Aujourd'hui, grâce à l'apparition de cartes graphiques performantes et bon marché, les objets 3D sont utilisés dans de nombreuses applications. A peu près tous les terminaux possédant des capacités d'affichage - des clusters de visualisation haute performance jusqu'aux smart phones - intègrent maintenant une puce graphique qui leur permet de faire du rendu 3D. Ainsi, les applications 3D sont bien plus variées qu'il y a quelques années. On citera par exemple la réalité virtuelle et augmentée en temps réel ou les mondes virtuels 3D. Dans ce contexte, le besoin de méthodes efficaces pour la transmission et la visualisation des données 3D est toujours plus pressant. De plus, la taille des maillages 3D ne cesse de s'accroître avec la précision de la représentation. Par exemple, les scanners 3D actuels sont capables de numériser des objets du monde réel avec une précision de seulement quelques micromètres, et génèrent des maillages contenant plusieurs centaines de millions d''el'ements. D'un autre côté, une précision accrue en simulation numérique requiert des maillages plus fins, et les méthodes massivement parallèles actuelles sont capables de travailler avec des milliards de mailles. Dans ce contexte, la compression de ces données - en particulier la compression de maillages - est un enjeu important. Durant la décennie passée, de nombreuses méthodes ont été développées pour coder les maillages polygonaux. Néanmoins, ces techniques ne sont plus adaptées au contexte actuel, car elles supposentque la compression et la d'ecompression sont des processus sym'etriques qui ont lieu sur un mat'erielsimilaire. Dans le cadre actuel, au contraire, le contenu 3D se trouve cr'e'e, compressé et distribué par des machines de hautes performances, tandis que l'exploitation des données - par exemple, la visualisation - est effectuée à distance sur des périphériques de capacité plus modeste - éventuellement mobiles - qui ne peuvent traiter les maillages de grande taille dans leur int'egralité. Ceci fait de lacompression de maillage un processus intrinsèquement asymétrique.Dans cette thèse, notre objectif est d'étudier et de proposer des méthodes pour la compression de maillages de grande taille. Nous nous intéressons plus particulièrement aux méthodes d'accès aléatoire, qui voient la compression comme un problème intrinsèquement asymétrique. Dans ce modèle, le codeur a accès à des ressources informatiques importantes, tandis que la décompression estun processus temps réel (souple) qui se fait avec du matériel de plus faible puissance. Nous décrivons un algorithme de ce type et l'appliquons au cas de la visualisation interactive. Nous proposons aussi un algorithme streaming pour compresser des maillages hexaèdriques de très grande taille utilisés dans le contexte de la simulation numérique. Nous sommes ainsi capables decompresser des maillages comportant de l'ordre de 50 millions de mailles en moins de deux minutes, et en n'utilisant que quelques mégaoctets de mémoire vive. Enfin, nous proposons, indépendamment de ces deux algorithmes, un cadre théorique général pour améliorer la compression de géométrie. Cet algorithme peut être utilisé pour développer des méthodes de prédiction pour n'importe quel algorithme basé sur un paradigme prédictif - ce qui est la cas dela majorité des méthodes existantes. Nous dérivons ainsi des schémas de prédictions compatibles avec plusieurs méthodes de la littérature. Ces schémas augmentent les taux de compression de 9% enmoyenne. Sous des hypothèses usuelles, nous utilisons aussi ces résultats pour prouver l'optimalité de certains algorithmes existants.

Nous présentons de nouveaux schémas numériques pour l'approximation de problèmes de diffusion hétérogène et anisotrope sur des maillages généraux. Sous des hypothèses correspondant aux cas industriels, nous montrons qu'un premier schéma, qui est centré sur les mailles, possède un petit stencil et converge dans le cas de tenseurs discontinus. La preuve de la convergence repose sur des propriétés de consistance des gradients discrets issus du schéma. Dans une seconde partie, nous proposons des méthodes de correction non linéaire du schéma initial pour obtenir le principe du maximum. L'efficacité de ces schémas est étudiée sur des tests numériques ayant fait l'objet de bancs d'essais d'une grande variété de schémas de volumes finis. Les comparaisons avec les schémas volumes finis classiques montrent l'apport de ces schémas en termes de précision. Nous montrons ainsi le bon comportement de ces schémas sur des maillages déformés, et le maintien de la précision des schémas non-linéaires, alors que les oscillations ont été supprimées / We present a new scheme for the discretization of heterogeneous anisotropic diffusion problems on general meshes. With light assumptions, we show that the algorithm can be written as a cell-centered scheme with a small stencil and that it is convergent for discontinuous tensors. The key point of the proof consists in showing both the strong and the weak consistency of the method. Besides, we study non-linear corrections to correct the FECC scheme, in order to satisfy the discrete maximum principle (DMP).The efficiency of the scheme is demonstrated through numerical tests of the 5th & 6th International Symposium on Finite Volumes for Complex Applications - FVCA 5 & 6. Moreover, the comparison with classical finite volume schemes emphasizes the precision of the method. We also show the good behaviour of the algorithm for nonconforming meshes. In addition, we give some numerical tests to check the existence for the non-linear FECC schemes

De nombreux domaines utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose à la fois le problème du stockage et de l'adaptativité des algorithmes à une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l'augmentation incessante de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l'utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques. Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement non-structurées. (2) Une méthode de classification de cellules qui permet d'accélérer l'extraction d'isosurfaces grâce à une pré-sélection des seules cellules intersectées. (3) Un algorithme d'interpolation temporelle d'isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l'évolution d'isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L'originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable à n'importe quel système creux, dont ceux issus de maillages fortement non-structurés / This thesis proposes new tools for visualization and computation on strongly unstructured grids. Visualization of such grids that have variable geometry and topology, poses the problem of how to store data and how algorithms could handle such variability. Doing computations on such grids poses the problem of solving large sparse unstructured linear systems. The ever-growing parallel power of GPUs makes them more and more valuable for handling theses tasks. However, using GPUs calls for defining new algorithms highly adapted to their specific programming model. Most recent algorithms for Geometry Processing or Computational Fluid Dynamics (CFD) are using new types of grids made of arbitrary polyhedra, in other words strongly unstructured grids. In case of CFD simulations, these grids can be mapped with scalar or vector fields representing physical properties (for example : density, porosity, permeability). Our contributions are: (1) An efficient generic visualization method that uses GPU's power to accelerate isosurface extraction for large unstructured grids. (2) An adaptative cell classification method that accelerates isosurface extraction by pre-selecting only intersected cells. (3) An efficient algorithm for temporal interpolation of isosurfaces. This algrithm helps to visualize in a continuous maner the evolution of isosurfaces through time. (4) A massively parallel algorithm for solving large sparse unstructured linear systems on the GPU. Its originality comes from its adaptation to sparse matrices with random pattern, which enables to solve any sparse linear system, thus the ones that come from strongly unstructured grids

Les diagrammes de Voronoi sont des structures de données fondamentales qui ont été étudiées en détail dans le domaine de la géométrie algorithmique. Un diagramme de Voronoi peut être défini comme le diagramme de minimisation d'un ensemble fini de fonctions continues. On interprète en général chacune de ces fonctions comme la fonction distance à un objet. Le diagramme de Voronoi correspondant partitionne l'espace de définition en régions, chacune d'entre elle réunissant les points qui sont plus proches d'un object que de tous les autres. On peut définir de nombreuses variantes des diagrammes de Voronoi, selon les classes d'objets, de fonctions distance et d'espace de définition considérés. Les diagrammes affines, c'est-à-dire les diagrammes dont les cellules sont des polytopes convexes, sont bien connus. Leurs propriétés peuvent être déduites de celles des polytopes, et on peut les construire efficacement. <br /><br />La première partie de cette thèse s'attache à présenter et classifier les diagrammes de Voronoi. Nous cataloguons les variétés de diagrammes de Voronoi les plus étudiées, avant de les replacer dans le contexte des diagrammes de Voronoi abstraits, une notion initialement proposée par Klein. Cela nous permet de présenter dans un cadre général la question de la caractérisation des diagrammes de Voronoi classiques en fonction de la forme de leurs bissecteurs, un point de vue développé d'abord par Aurenhammer.<br /><br />Dans une deuxième partie, nous nous concentrons sur l'étude des diagrammes de Voronoi anisotropes, et sur les façons de calculer leur maillage dual, dans les cas où il est bien défini. Si celui-ci ne l'est pas, nous étudions des méthodes de raffinement du diagramme en vue d'obtenir un dual bien défini. Nous utilisons d'abord les définitions de Labelle et Shewchuk et la procédure de linéarisation présentée dans la partie précédente. Cela nous permet ensuite de définir un algorithme qui apparaît comme une conséquence naturelle de la première partie.<br /><br />La troisième partie est consacrée à une approche différente de la génération de maillages anisotropes. En remplaçant la définition de maillage anisotrope par celle de maillage anisotrope localement uniforme, nous parvenons à construire simplement un algorithme prouvé de génération de maillage anisotrope en dimension 2 et 3.<br /><br />Enfin, la quatrième partie de cette thèse considère l'application d'un autre type de diagramme de Voronoi, les diagrammes de puissance, à la question du routage glouton dans les réseaux ad hoc. Ici encore, les propriétés locales des triangulations jouent un rôle crucial. Nous montrons comment l'obtention de certaines propriétés locales des triangulations régulières, qui sont une généralisation des triangulations de Delaunay, permet de garantir des propriétés globales en termes de routage.

Ce travail porte sur les maillages du territoire utilisés pour mettre en œuvre l'action publique contre la précarité<br />sociale. Il interroge la non-concordance de ces découpages et partant, cherche à comprendre les raisons d'être de<br />chacun. A partir de l'exemple de l'action sociale départementale et de la politique de la ville en Ile-de-France, on<br />s'interroge sur les relations entre les principes de découpages et le dessin des mailles d'une part, et les fonctions<br />associées aux mailles et les usages qui en sont fait, d'autre part. On porte une attention particulière à la confrontation<br />du tracé des mailles avec les répartitions spatiales de la précarité sociale. Une première partie justifie l'approche<br />spatiale retenue pour aborder les deux politiques publiques. Une seconde partie est consacrée à la mise en évidence<br />des divisions socio-spatiales de la région francilienne, puis à la définition des contextes locaux de la précarité sociale,<br />à l'échelon communal et infra-communal. Dans une troisième, on aborde les maillages de l'action sociale<br />départementale, en cherchant à faire la part de ce qui, dans ces maillages, relève du territoire « professionnel », des<br />impératifs gestionnaires ou encore du territoire politique. La quatrième partie porte sur les cadres territoriaux dans<br />lesquels est mise en œuvre la politique de la ville, en interrogeant en particulier l'intercommunalité des contrats de<br />ville franciliens ainsi que les usages et les représentations associés aux « zones urbaines sensibles ». Au final, la<br />discordance des maillages apparaît davantage comme le signe, que la cause, des difficultés des institutions et des<br />professionnels à coordonner leur action.

Cette thèse est consacrée aux études théoriques et numériques des problèmes sui- vants qui sont liés à l'adaptation de maillage anisotrope : Les métriques et estimateurs d'erreur, les modifications locales de maillages hexaédriques et quadrilatéraux. Nous procédons à la mise en oeuvre de nouveaux algorithmes, schémas numériques et méthodes dans ces deux parties ; notamment en codant dans le logiciel Freefem++ de nouvelles méthodes de reconstruction d'estimateurs d'erreur et de construction de métriques. Nous étudions trois des méthodes de reconstruction de la matrice hessienne, estimateur d'erreur d'interpolation de Lagrange à l'ordre deux qui sont : La reconstruction de la matrice hessienne par moindres carrés, la méthode basée sur la formule de Green, l'approximation locale de la fonction par un polynôme du second degré. Nous proposons une nouvelle approche basée sur l'interpolation polynomiale locale par maille et un schéma aux différences finies. Nous établissons des propriétés de sta- bilité et de convergence ainsi que des résultats numériques en dimension deux. Nous étudions aussi la reconstruction des dérivées troisièmes par moindres carrés. Nous pro- posons également de nouvelles estimations d'erreur d'interpolation de Lagrange grâce à un développement de Taylor à l'ordre trois sans calcul direct de dérivées troisièmes. Il est aussi proposé un algorithme de construction de métriques à partir d'une estima- tion d'erreur pouvant être représentée localement par une courbe fermée, applicable à l'erreur d'interpolation polynomiale d'ordre supérieur. Enfin, nous proposons de nouvelles façons de raffiner ou dé-raffiner localement les maillages hexaédriques. Nous faisons une étude des techniques existantes en proposant de nouvelles caractérisations des transformations locales de maillages quadrilatéraux et hexaédriques.

Les algorithmes les plus récents de traitement numérique de la géométrie ou bien encore de simulation numérique de type CFD (Computational Fluid Dynamics) utilisent à présent de nouveaux types de grilles composées de polyèdres arbitraires, autrement dit des grilles fortement non-structurées. Dans le cas de simulations de type CFD, ces grilles peuvent servir de support à des champs scalaires ou vectoriels qui représentent des grandeurs physiques (par exemple : densité, porosité, perméabilité). La problématique de cette thèse concerne la définition de nouveaux outils de visualisation et de calcul sur de telles grilles. Pour la visualisation, cela pose `a la fois le problème du stockage et de l'adaptativité des algorithmes `a une géométrie et une topologie variables. Pour le calcul, cela pose le problème de la résolution de grands systèmes linéaires creux non-structurés. Pour aborder ces problèmes, l'augmentation incessante ces dernières années de la puissance de calcul parallèle des processeurs graphiques nous fournit de nouveaux outils. Toutefois, l'utilisation de ces GPU nécessite de définir de nouveaux algorithmes adaptés aux modèles de programmation parallèle qui leur sont spécifiques. Nos contributions sont les suivantes : (1) Une méthode générique de visualisation tirant partie de la puissance de calcul des GPU pour extraire des isosurfaces à partir de grandes grilles fortement nonstructurées. (2) Une méthode de classification de cellules qui permet d'accélérer l'extraction d'isosurfaces grâce à une pré-sélection des seules cellules intersectées. (3) Un algorithme d'interpolation temporelle d'isosurfaces. Celui-ci permet de visualiser de manière continue dans le temps l'évolution d'isosurfaces. (4) Un algorithme massivement parallèle de résolution de grands systèmes linéaires non-structurés creux sur le GPU. L'originalité de celui-ci concerne son adaptation à des matrices de motif arbitraire, ce qui le rend applicable `a n'importe quel système creux, dont ceux issus de maillages fortement non-structurés.

Cette étude présente des algorithmes de génération et d'améliorations de maillages en simplexes pour la methode des éléments finis (triangles en 2d et tetraedres en 3D). Dans une première partie, après avoir montre que tout domaine plan défini par un contour extérieur et un ensemble de points internes représentant sa discrétisation peut être triangule, on expose et on justifie un algorithme simple de maillages en triangles. On prouve ensuite que l'opération de changement de diagonales dans un quadrilatère convexe permet d'atteindre toute les topologies realisables. Dans la seconde partie, on étudie le cas tridimensionnel et on donne quelques propriétés sur l'existence d'une tetraedrisation quand on se fixe le maillage en facettes triangulaires de la surface extérieure du domaine et les points internes pour la discrétisation. On décrit plusieurs heuristiques d'améliorations topologiques de maillages tetraedriques et on compare leur efficacité pratique sur quelques exemples industriels tires de la mécanique des fluides: on examine ainsi un algorithme glouton généralisant la démarche bidimensionnelle, un algorithme base sur la methode statistique du recuit simule et des algorithmes de type Divide and Conquer couples avec des procédures non topologiques simples comme le barycentrage des Nuds d'une discrétisation. Ces derniers algorithmes provoquent des améliorations conséquentes même sur des maillages de topologies très défavorables

Cette thèse traite de la modélisation 3D d'un objet à partir de données sensorielles obtenues par des capteurs laser ou stéréoscopiques. Ce processus nécessite plusieurs étapes, étudiées durant la thèse; chacune fait l'objet d'un chapitre du manuscrit. La première phase consiste à acquérir des données sensorielles depuis divers points de vue: nous avons exploité les nombreuses données 3D disponibles sur le Web, mais nous avons aussi testé nos algorithmes sur des données 3D denses acquises par stéréovision; nous avons pour ce faire, exploité et analysé des méthodes de calibrage et de stéréovision préexistantes dans notre laboratoire. Les nuages de points 3D de chaque image sont ensuite recalés par un algorithme de type ICP "Iteration Closest Point"; afin de réduire le temps de calcul, la méthode a été adaptée pour utiliser des informations spécifiques des images comme les points de contour ou les sommets d'un maillage local plus ou moins sous-échantillonné. Nous comparons deux stratégies: recalage entre images successives ou recalage incrémental, entre l'image courante et le modèle courant. Les méthodes proposées ont été évaluées et comparées selon différents critères: temps d'exécution, sensibilité à l'estimée initiale, à la résolution... La méthode de recalage a également été testée afin de recaler des coupes laser acquises par un robot mobile évoluant dans un environnement intérieur. La partie suivante est la fusion des vues issues du recalage pour obtenir un seul modèle après chaque recalage incrémental ou à la fin du processus de recalage. La représentation choisie est un maillage triangulaire. Ce maillage est construit par une version adaptée de l'algorithme de la boule pivotante, ou "Ball Pivoting Algorithm" (BPA), proposé initialement par l'équipe de G.Taubin: nous avons choisi cette méthode car elle permet la construction d'un maillage à partir de points 3D ayant une distribution et une précision non uniforme. Notre version de BPA effectue la segmenta tion simultanée des surfaces et le recyclage des maillages existants. Le maillage obtenu est comparé avec ceux construits par déformation d'une surface active. Dans un contexte Robotique, nous avons étudié le problème de la planification des positions du capteur pour la prise des vues, problème plus connu sous le nom de "Next Best View". Le but est la minimisation du nombre de vues nécessaires pour modéliser un objet, tout en favorisant la convergence du processus du recalage. Nous avons poursuivi d'abord des travaux fondés sur l'optimisation d'une fonction d'utilité; du fait de problèmes de convergence, une méthode plus simple a été mise en oeuvre dans le cas particulier de la modélisation d'un objet posé sur une table, par un capteur stéréo monté sur un bras manipulateur mobile. Finalement toutes ces méthodes ont été validées, d'abord sur des données de synthèse pour les analyser, puis sur des données précises acquises par télémétrie laser ou profilométrie, et enfin sur des données que nous avons acquises par stéréo dans le monde réel.

Un schéma compact de haute précision basé sur le résidu (RBC) a été développé au laboratoire SINUMEF pour la simulation numérique d'écoulements compressibles en maillages structurés. Certaines proriétés intéressantes font de ce schéma un bon choix pour les calculs d'écoulements compressibles. L'objectif de cette thèse est donc de développer un schéma basé sur le résidu (RB) en maillages non-structurés avec une précision d'ordre élevé. A cette fin, deux approches ont été explorées. La première est basé sur la méthode des volumes finies en non-structuré et conduit à un schéma basé sur le résidu appelé FV-RB. Le seconde approche s'appuie sur une nouvelle formulation spatiale dite volumes spectraux (SV) et mène au schéma SV-RB. Le schéma FV-RB a été développé à l'ordre 2 et 3. Avec cette version du schéma, de nombreux cas tests sont calculés: écoulement d'un fluide parfait et visqueux, subsonique, transonique et hypersonique, stationnaire et instationnaire, en 2D et en 3D. Une analyse de la précision et du coût de calcul est effectuée pour le schéma FV-RB. Dans la seconde approche, un schéma SV-RB est développé à l'ordre 2 et 3 pour résoudre le problème d'advection pure et les équations d'Euler. A travers quelques cas tests, une comparaison de la précision et l'efficacité est effectuée entre le schéma RB et un solveur de Riemman classique, et entre deux formulations du schéma RB développés ici.