Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La compression est un incontournable lorsque des modèles triangulaires 3D massifs doivent être transmis via un réseau de communication. La compression se doit d'être sans perte lorsque les modèles sont utilisés à des fins métrologiques. Cependant, les modèles capturés par scanneurs 3D contiennent généralement des artefacts de numérisation tels que la présence de trous dans le maillage, de petits regroupements distincts de triangles sous forme de surfaces ou de volumes ainsi que de singularités non-manifold (c.-à-d. un sommet appartenant à deux regroupement de triangles distincts). Ces aberrations rendent les techniques de compression standards inaptes à compresser sans échec le modèle. Ce mémoire propose une extension à une technique de compression et décompression sans perte des données topologiques nommée Edgebreaker. Le remplissage des trous par l'addition d'un sommet, l'insertion de faces triangulaires afin de lier les îlots ainsi que la duplication des sommets non-manifold sont proposées comme étapes de prétraitement afin de rendre le modèle compatible avec l'approche standard d'Edgebreaker. Les résultats obtenus démontrent que la solution proposée permet la compression sans perte de modèles hautement bruités à de hauts taux de compression. Les taux de compression résultants obtenus par notre approche se comparent également avec les taux observables pour des modèles sans imperfections compressés par Edgebreaker.

Une conséquence du lemme de Céa permet de déterminer l’ordre de convergence optimal d’une solution estimée par la méthode des éléments finis. L’hypothèse importante qui est faite pour obtenir cette convergence est que la solution doit être suffisamment régulière. Dans ce mémoire, nous montrerons l’impact de l’adaptation sur la convergence de problèmes de diffusion ayant une singularité dans leur gradient. Afin de retrouver l’ordre optimal de la méthode sur des problèmes où cette hypothèse est fausse, nous développerons une méthode d’adaptation de maillage faite a posteriori, c’est-à-dire que l’on doit déjà avoir une approximation initiale de la solution pour l’utiliser. L’adaptation est dite hiérarchique et utilise le fait qu’une meilleure approximation peut être trouvée à partir de l’approximation initiale. Cette méthode est en développement depuis quelques années et a été étudiée en détail dans la thèse de Bois [2].

L’adaptation de maillages anisotrope permet d’améliorer grandement la précision de méthodes numériques telles que la méthode des éléments finis. L’adaptation peut être très coûteuse en temps de calcul, mais montre un grand potentiel de parallélisation. Ce projet consiste à développer une implémentation parallèle de l’adaptation de maillages anisotrope basée sur des estimateurs métrique et hiérarchique. On introduit les notions de base de l’adaptation et de la programmation parallèle. On développe une stratégie de parallélisation applicable à la fois en deux dimensions et en trois dimensions. Enfin, on applique cette stratégie dans le cadre de la méthode des éléments finis dans le but d’en évaluer l’efficacité et la rapidité.

Ce mémoire porte sur l'adaptation de maillage par métrique. Plus précisément, on s'intéresse à développer la métrique discutée dans l'article [10] de Pagnutti & Ollivier-Gooch puis à voir l'amélioration d'une telle méthode d'adaptation de maillage sur la résolution numérique d'une équation aux dérivées partielles par éléments finis. On présente d'abord l'intuition derrière l'adaptation de maillage par métrique, d'où on introduit une approximation de l'erreur d'interpolation. On parle de la convergence d'une solution numérique. Pour se mettre en situation de maillage par métrique classique et l'adaptation hiérachique. Puis, au vif du sujet, on explique l'approche de l'adaptation de maillage de Pagnutti & Ollivier-Gooch. On parle aussi des actions permettant d'adapter nos maillages. Enfin, on résout numériquement des équations aux dérivées partielles avec opérateur laplacien par la méthode des élments finis sur des maillages uniformes et adaptés par nos 3 méthodes d'adaptation. On y considère des cas 1D, 2D et 3D.

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.

Cette thèse de doctorat aborde spécifiquement le problème de la métamorphose entre différents maillages 3D, qui peut assurer un niveau élevé de qualité pour la séquence de transition, qui devrait être aussi lisse et progressive que possible, cohérente par rapport à la géométrie et la topologie, et visuellement agréable. Les différentes étapes impliquées dans le processus de transformation sont développées dans cette thèse. Nos premières contributions concernent deux approches différentes des paramétrisations: un algorithme de mappage barycentrique basé sur la préservation des rapports de longueur et une technique de paramétrisation sphérique, exploitant la courbure Gaussien. L'évaluation expérimentale, effectuées sur des modèles 3D de formes variées, démontré une amélioration considérable en termes de distorsion maillage pour les deux méthodes. Afin d’aligner les caractéristiques des deux modèles d'entrée, nous avons considéré une technique de déformation basée sur la fonction radial CTPS C2a approprié pour déformer le mappage dans le domaine paramétrique et maintenir un mappage valide a travers le processus de mouvement. La dernière contribution consiste d’une une nouvelle méthode qui construit un pseudo metamaillage qui évite l'exécution et le suivi des intersections d’arêtes comme rencontrées dans l'état-of-the-art. En outre, notre méthode permet de réduire de manière drastique le nombre de sommets normalement nécessaires dans une structure supermesh. Le cadre générale de métamorphose a été intégré dans une application prototype de morphing qui permet à l'utilisateur d'opérer de façon interactive avec des modèles 3D et de contrôler chaque étape du processus / This Ph.D. thesis specifically deals with the issue of metamorphosis of 3D objects represented as 3D triangular meshes. The objective is to elaborate a complete 3D mesh morphing methodology which ensures high quality transition sequences, smooth and gradual, consistent with respect to both geometry and topology, and visually pleasant. Our first contributions concern the two different approaches of parameterization: a new barycentric mapping algorithm based on the preservation of the mesh length ratios, and a spherical parameterization technique, exploiting a Gaussian curvature criterion. The experimental evaluation, carried out on 3D models of various shapes, demonstrated a considerably improvement in terms of mesh distortion for both methods. In order to align the features of the two input models, we have considered a warping technique based on the CTPS C2a radial basis function suitable to deform the models embeddings in the parametric domain maintaining a valid mapping through the entire movement process. We show how this technique has to be adapted in order to warp meshes specified in the parametric domains. A final contribution consists of a novel algorithm for constructing a pseudo-metamesh that avoids the complex process of edge intersections encountered in the state-of-the-art. The obtained mesh structure is characterized by a small number of vertices and it is able to approximate both the source and target shapes. The entire mesh morphing framework has been integrated in an interactive application that allows the user to control and visualize all the stages of the morphing process

La réalité virtuelle représente aujourd'hui une technologie à part entière puisqu'elle autorise la simulation, la navigation et l'interaction avec un univers sensoriel synthétisé de toutes pièces. Les potentialités offertes par la réalité virtuelle ont été très bien perçues lorsque les ordinateurs graphiques ont été capables d'assurer un rendu des images à une cadence interactive. De plus, l'augmentation des capacités des machines coïncide aujourd'hui avec un développement vertigineux des réseaux, ce qui décuple littéralement le champ d'application de la réalité virtuelle. Plusieurs difficultés subsistent toutefois pour développer les services de télécommunications associés : le volume des données est considérable, l'affichage est coûteux en calculs et la nature des données nécessite une prise en compte spécifique dans le contexte client-serveur. Si l'on ajoute à cela l'inégalité des capacités des terminaux et la variabilité des réseaux, on obtient une synthèse du triple challenge de la thèse : le stockage, la transmission et la visualisation de scènes 3D complexes. On pourrait aussi résumer la problématique en endossant le temps d'une phrase, le rôle d'un opérateur de télécommunication : "quels que soient : le terminal, le volume de données à transmettre et le débit du réseau, l'utilisateur doit pouvoir visualiser à tout moment une image attractive". Ce mémoire relève le défi sous la forme de briques technologiques susceptibles de s'assembler pour composer un moteur de transmission et d'affichage de scènes 3D en réseau. Il propose des solutions correspondant à un schéma courant en codage de l'information audiovisuelle : simplification, approximation, et codage échelonnable. Il reste cependant une spécificité propre à la 3D : la visualisation. En effet, il est d'une part plus coûteux de projeter un polygone à l'écran plutôt que d'afficher un pixel, et d'autre part le point de vue hautement variable d'une caméra influence sensiblement la pertinence des données transmises. Le premier chapitre, introductif, fournit une compréhension naturelle de la problématique et les trois autres suivent logiquement l'ordre des opérations appliquées sur les scènes 3D : la simplification et l'approximation, le codage et la visualisation. Plus précisément, les maillages composant les objets d'une scène sont simplifiés par fusion d'arête et approximés par minimisation de volume. Ils sont ensuite encodés par une technique de conquête sur les arêtes exploitant les valences des sommets. L'échelonnabilité est, quant à elle, obtenue sur les positions par une technique apparentée aux plans binaires de raffinement. Le codage des textures est adressé par intégration d'une technique développée au sein du laboratoire, cette dernière combinant la transformée en cosinus discrète et les éléments finis sur une hiérarchie de maillages triangulaires. Sur le terminal, la visualisation dépendant du point de vue est assurée par une technique de reconstruction adaptative des surfaces fonctionnant par subdivision successive des régions d'intérêt et des silhouettes. Nous montrons qu'une telle reconstruction s'applique en cours de transmission et s'adapte aisément à la puissance graphique d'un terminal.

This work is dedicated to the control of the accuracy of computational simulations of sound propagation and scattering. Assuming time-harmonic behaviour, the mathematical models are given as boundary value problems for the Helmholtz equation <i>Delta u+k2u=0 </i> in <i>Oméga</i>. A distinction is made between interior, exterior and coupled problems and this work focuses mainly on interior uncoupled problems for which the Helmholtz equation becomes singular at eigenfrequencies. As in other application fields, error control is an important issue in acoustic computations. It is clear that the numerical parameters (mesh size h and degree of approximation p) must be adapted to the physical parameter k. The well known ‘rule of the thumb’ for the h version with linear elements is to resolve the wavelength <i>lambda=2 pi k-1</i> by six elements characterising the approximability of the finite element mesh. If the numerical model is stable, the quality of the numerical solution is entirely controlled by the approximability of the finite element mesh. The situation is quite different in the presence of singularities. In that case, <i>stability</i> (or the lack thereof) is equally (sometimes more) important. In our application, the solutions are ‘rough’, i.e., highly oscillatory if the wavenumber is large. This is a singularity inherent to the differential operator rather than to the domain or the boundary conditions. This effect is called the <i>k-singularity</i>. Similarly, the discrete operator (“stiffness” matrix) becomes singular at eigenvalues of the discretised interior problem (or nearly singular at damped eigenvalues in solid-fluid interaction). This type of singularities is called the <i>lambda-singularities</i>. Both singularities are of global character. Without adaptive correction, their destabilizing effect generally leads to large error of the finite element results, even if the finite element mesh satisfies the ‘rule of the thumb’. The k- and lambda-singularities are first extensively demonstrated by numerical examples. Then, two <i>a posteriori</i> error estimators are developed and the numerical tests show that, due to these specific phenomena of dynamo-acoustic computations, <i>error control cannot, in general, be accomplished by just ‘transplanting’ methods that worked well in static computations</i>. However, for low wavenumbers, it is necessary to also control the influence of the geometric (reentrants corners) or physical (discontinuities of the boundary conditions) singularities. An <i>h</i>-adaptive version with refinements has been implemented. These tools have been applied to two industrial examples : the GLT, a bi-mode bus from Bombardier Eurorail, and the Vertigo, a sport car from Gillet Automobiles. As a conclusion, it is recommanded to replace the rule of the thumb by a criterion based on the control of the influence of the specific singularities of the Helmholtz operator. As this aim cannot be achieved by the <i>a posteriori</i> error estimators, it is suggested to minimize the influence of the singularities by modifying the formulation of the finite element method or by formulating a “meshless” method.