Modéliser avec des squelettes est une alternative très séduisante aux "points de contrôle" souvent placés à l'extérieur des formes : cette approche, analogue à un fil de fer dans une forme modelée, permet de créer des modèles de toutes géométries et topologies. Pour cela, il faut que les formes définies par chacun des squelettes soient capable de se mélanger de manière lisse. Introduites en informatique graphique dans les années 90, les surfaces implicites sont la principale solution à ce problème. Elles constituent un modèle puissant à la fois pour la modélisation d'objets tridimensionnels et pour leur animation: leur construction par squelette et leurs capacités de mélange par sommation des champs potentiels qui les définissent permettent en effet la conception progressive et le stockage compact d'objets volumiques, ainsi que l'animation de déformations pouvant comprendre des changements de topologie. Les surfaces implicites, et plus particulièrement les surfaces de convolution, forment donc un modèle particulièrement adapté à la modélisation par squelette. Toutefois, elles présentent un certain nombre de défaut qui les ont rendu inutilisables en pratique. Cette thèse propose de nouveaux modèles implicites à squelettes, s'inspirant de la convolution mais basés aussi sur des déformations de l'espace. Ils permettent : - une génération plus aisée de forme le long de squelettes formés de courbes (des arc d'hélices), - un meilleur contrôle des formes tant au niveau de leur épaisseur que de leur mélange, notamment - nos modèles sont invariant par homothétie ce qui les rend plus intuitif, - la génération de surfaces ayant une topologie plus proche de celle des squelettes, - la génération de détails fins engendrés par un bruit procédural, les détails se comportant de manière cohérente avec la surface (et les squelettes) sous-jacente.

Les points critiques d’une fonction scalaire (minima, points col et maxima) sont des caractéristiques importantes permettant de décrire de gros ensembles de données, comme par exemple les données topographiques. L’acquisition de ces données introduit souvent du bruit sur les valeurs. Un grand nombre de points critiques sont créés par le bruit, il est donc important de supprimer ces points critiques pour faire une bonne analyse de ces données. Le complexe de Morse-Smale est un objet mathématique qui est étudié dans le domaine de la Visualisation Scientifique car il permet de simplifier des fonctions scalaires tout en gardant les points critiques les plus importants de la fonction étudiée, ainsi que les liens entre ces points critiques. Nous proposons dans cette thèse une méthode permettant de construire une fonction qui correspond à un complexe de Morse-Smale d’une fonction définie sur R^2 après suppression de paires de points critiques dans celui-ci.Tout d’abord, nous proposons une méthode qui définit une surface interpolant des valeurs de fonction aux points d’une grille de façon monotone, c’est-à-dire en ne créant pas de point critique. Cette surface est composée d’un ensemble de patchs de Bézier triangulaires cubiques assemblés de telle sorte que la surface soit globalement C^1. Nous donnons des conditionssuffisantes sur les valeurs d fonction et les valeurs de dérivées partielles aux points de la grille afin que la surface soit croissante dans la direction (x+y). Il n’est pas évident de créer des valeurs de dérivées partielles en chaque point de la grille vérifiant ces conditions. C’est pourquoi nous introduisons deux algorithmes : le premier permet de modifier des valeurs de dérivées partielles données en entrée afin que celles-ci vérifient les conditions et le second calcule des valeurs de dérivées partielles à partir des valeurs de fonctions aux points de la grille.Ensuite, nous décrivons une méthode de reconstruction de champs scalaires à partir de complexes de Morse-Smale simplifiés. Pour cela, nous commençons par approximer les 1-cellules (les liens entre les points critiques dans le complexe de Morse-Smale, ceux-ci sont décrits par des polylignes) par des courbes composées de courbes de Bézier cubiques. Nous décrivons ensuite comment notre interpolation monotone de valeurs aux points d’une grille est utilisée pour construire des surfaces monotones interpolant les courbes construites précédemment. De plus, nous montrons que la fonction reconstruite contient tout les points critiques du complexe de Morse-Smale simplifié et n’en contient aucun autre. / Critical points of a scalar function (minima, saddle points and maxima) are important features to characterize large scalar datasets, like topographic data. But the acquisition of such datasets introduces noise in the values. Many critical points are caused by the noise, so there is a need to delete these extra critical points. The Morse-Smale complex is a mathematical object which is studied in the domain of Visualization because it allows to simplify scalar functions while keeping the most important critical points of the studied function and the links between them. We propose in this dissertation a method to construct a function which corresponds to a Morse-Smale complex defined on R^2 after the suppression of pairs of critical points.Firstly, we propose a method which defines a monotone surface (a surface without critical points).This surface interpolates function values at a grid points. Furthermore, it is composed of a set of triangular cubic Bézier patches which define a C^1 continuous surface. We give sufficient conditions on the function values at the grid points and on the partial derivatives at the grid points so that the surface is increasing in the (x+y) direction. It is not easy to compute partial derivatives values which respect these conditions. That’s why we introduce two algorithms : the first modifies the partial derivatives values on input such that they respect the conditions and the second computes these values from the function values at the grid points.Then, we describe a reconstruction method of scalar field from simplified Morse-Smale complexes. We begin by approximating the 1-cells of the complex (which are the links between the critical points, described by polylines) by curves composed of cubic Bézier curves. We then describe how our monotone interpolant of values at grid points is used to construct monotone surfaces which interpolate the curves we computed before. Furthermore, we show that the function we compute contains all the critical points of the simplified Morse-Smale complex and has no others.

Ce travail de thèse en Mathématiques Appliquées a été effectué au sein du service Capteurs et Systèmes Electroniques (SCSE) au CEA-Leti, organisme majeur de la recherche publique française implanté à Grenoble. Il s'inscrit dans le cadre d'une collaboration avec le laboratoire de mathématiques appliquées Jean Kuntzmann (LJK) de l'Université Joseph Fourier (UJF). Le Leti développe des systèmes de capteurs de données terrestres (magnétomètres, accéléromètres...) capables de se géoréférencer de manière autonome. Placés sur des objets, ces dispositifs de capteursfournissent leur orientation propre dans l'espace, et ouvrent donc un vaste champ d'applications dans le domaine de l'acquisition et la reconstruction de formes.Le problème de la reconstruction de surfaces à partir de données d'orientation non structurées est par essence un problème mal posé. Cependant, des travaux précédents effectués au Leti ont permis de dégager un protocole fournissant un cadre valide pour le processus de reconstruction. Les capteurs ont été intégrés dans les rubans Morphosense : ces rubans souples équipés de noeuds de capteurs selon unegéométrie connue permettent ainsi le développement d'algorithmes de reconstruction de la courbe suivie par le ruban. L'application de rubans Morphosense sur une surface physique permet alors d'acquérir la famille des courbes suivies par les rubans et tracées sur la surface. Il s'agit ensuite d'exploiter le réseau des courbes ainsi obtenues pour reconstruire la surface. Dans un premier temps, nous revisitons la question de la reconstruction du ruban. Nous proposons des algorithmes de reconstruction de la courbe 3D suivie par le ruban Morphosense prenant maintenant en compte l'intégralité des données fournies par les capteurs d'orientation, ainsi que les propriétés méca-niques du ruban qui le conduisent à suivre des courbes géodésiques sur une surface. De ce point de vue, la reconstruction peut être considérée comme optimale.On étudie ensuite un ensemble de méthodes pour la reconstruction de surfaces à partir d'un réseau de courbes rubans. Dans le cas général, un tel type de réseau conduit à des problèmes de fermeture et d'estimation de données manquantes. La question de la fermeture, d'ordre essentiellement numérique et liée à des contraintes différentielles, concerne le réseau des courbes et la difficulté d'obtenir des contoursfermés. La question cruciale de l'estimation des données manquantes traduit le fait qu'aucune information sur la surface n'est connue et accessible en dehors du réseau des courbes rubans.Afin de s'affranchir de ces problèmes et de proposer des solutions pratiques pour la reconstruction, il est nécessaire de faire des hypothèses sur le modèle de surfaces à reconstruire ou sur la topologie de réseau de courbes acquises. Les méthodes développées s'inscrivent donc dans l'une des deux approchessuivantes.– D'une part des méthodes de reconstruction de surfaces développables et quasi-développables, qui modélisent de manière satisfaisante les surfaces étudiées dans le cadre de nombreuses applications.– D'autre part des méthodes de reconstruction à partir d'une topologie spécifique de réseaux de courbes (courbes quasi-planaires, contour ouvert), permettant de résoudre le problème de fermeture.L'ensemble des méthodes proposées dans ces travaux permet ainsi de formuler un processus global de reconstruction de surfaces, qu'il est possible d'adapter aux problèmes étudiés en pratique, afin de proposer une solution à la fois simple et précise dans chaque cas. La validation des résultats dans le cadre des données réelles fournies par les rubans Morphosense nous a conduit à développer des dispositifs métrologiques. Enfin, notons que le contexte général des données d'orientation étudié ici soulève des problématiques peu classiques, voire nouvelles, auxquelles nous avons essayé d'apporter des solutions originales, en particulier au travers d'algorithmes d'interpolation et d'optimisation. / This PhD thesis in applied mathematics was conducted within the Electronic Systems andSensors department of the CEA-Leti (Atomic Energy and Alternative Energies Commission - Laboratory for Electronics and Information Technologies), a major organism for technological research located in Grenoble, France. This work originated from a partnership with the applied mathematics laboratory (LJK) of the Joseph Fourier university (UJF). The Leti develops embedded systems equiped with micro-sensors (magnetometers, accelerometers...) from which it is possible to retrieve informations about their spatial orientation. These systems allow for innovative applications in the field of shape acquisition and reconstruction. The problem of reconstructing surfaces from unstructured orientation data is ill-posed. However, previous work done within the Leti came up with a valid reconstruction protocol. The micro-sensors were integrated into the Morphosense ribbon : this flexible ribbon instrumented with sensor knots according to a known geometry is at the core of a number of reconstruction algorithms for the curves followed by the ribbon. When lied on a physical surface, Morphosense ribbons then allow the acquisition and reconstruction of a network of curves on the surface, that are then used for the reconstruction of the entire surface. We first propose new algorithms for curve reconstruction thanks to the Morphosense ribbon. Those new methods now integrate the orientation informations provided by the sensors in their entirety, as well as the mechanical properties of the ribbon that force it to follow geodesic curves on a surface. From this point of view, the curve reconstruction can be considered optimal, as it integrates all the information embedded in the ribbons' structure. We then study a set of methods for the reconstruction of surfaces using a network of ribbon curves. Such a network generally leads to problems linked to the closure of the network and missing data estimation. The closure of the network is essentially a numerical problem related to differential constraints. The missing data corresponds to the lack of information on the surface outside the network of curves. In order to deal with these problems and propose practical solutions for the reconstruction, hypotheses either on the surface models or the topology of the network of curves are required. Therefore, the developed methods fall within the two following approaches.– On the one hand, reconstruction methods for developable and quasi-developable surfaces, which are a good approximation for the surfaces considered in numerous applications.– On the other hand, reconstruction methods from networks of curves with specific topologies (quasi-planar curves, open network) so as to deal with the closure problem.The set of methods developed in this work allow to formulate a global process for the reconstruction of surfaces, with flexible algorithms adapting to the different practical situations, so as to propose a solution both simple and precise in each case. The validation of our results in the case of real sensors data provided by the Morphosense ribbons also led us to develop metrological device. Finally, notice that the general context of reconstruction from orientation data studied here raises original theorical problems, to which we tried to answer with innovative solutions through interpolation and optimization algorithms.

Les propriétés de symétrie d'un objet représenté sous la forme d'un modèle B-Rep CAO sont analysées localement et globalement à travers une approche de type diviser pour conquérir. La surface frontière de l'objet est décrite à partir de surfaces canoniques fréquemment utilisées dans les formes de composants mécaniques. La première phase de l'analyse consiste en la génération de faces et d'arêtes maximales indépendantes du processus de modélisation de l'objet mais préservant ses propriétés de symétrie. Ces faces et arêtes constituent des ensembles infinis de points traités globalement. La seconde phase est l'étape de division consistant en la création de plan et axes de symétrie de candidats pour les faces et arêtes maximales générées précédemment. Enfin, suit l'étape de propagation de ces plans et axes de symétrie représentant la phase de conquête et déterminant les propriétés de symétrie locales et globales de l'objet et caractérisant ses zones non-symétriques. / Symmetry properties of objects described as B-Rep CAD models are analyzed locally as well as globally through an approach of type divide-and-conquer. The boundary of the object is defined using canonical surfaces frequently used when shaping mechanical components. Then, the first phase consists in generating maximal faces and edges that are independent from the object modelling process but that preserve its symmetry properties. These faces and edges form infinite sets of points that are processed globally. The second phase is the division one that creates candidate symmetry planes and axes attached to the previous maximal edges and faces. Finally, comes the propagation step of these candidate symmetry planes and axes forming the conquer phase that determines the local as well as the global symmetries of the object while characterizing its asymmetric areas.

La génération de mondes virtuels est un domaine de recherche très actif en informatique graphique : la modélisation de plantes, d’arbres, de bâtiments, de villes ou de terrains, et les simulations de vieillissement sont des domaines très explorés. Dans ce contexte, les changements d’apparences constituent également un domaine de recherche important, de part leur impact majeur dans le réalisme des scènes virtuelles produites. Ces travaux se concentrent sur la mise au point d’approches procédurales permettant de représenter les changements d’apparence sous la forme de décorations géométriques (accumulation de neige ou formation de glace, dépôt de feuilles mortes, etc.) à la fois à grande échelle et avec un très haut niveau de détail. Nous proposons d’abord un modèle d’organisation hiérarchique de scènes qui repose sur un arbre de construction dont les feuilles sont des objets environnementaux, des objets qui génèrent eux mêmes leurs décorations géométriques. Nous présentons ensuite un formalisme implicite pour définir l’environnement, qui contient l’ensemble des informations guidant la génération des décorations. Finalement, nous détaillons quatre méthodes de génération procédurale pour la création des décorations géométriques (neige, glace, herbes, feuilles) des objets environnementaux. / Procedural modeling of virtual worlds is an active research field in computer science. A large amount of methods have been published in this field : modeling of plants, trees, buildings, cities or terrains, and aging and weathering simulations. In this context, changes of appearance are a very active research field too, due to the way they impact the realism of produced virtual scenes. This research focuses on a procedural method that can represent the changes of appearance as geometrical decorations (snowfall, ice growth, leaves deposits, etc.) on very big scenes with a high level of details. We first propose a hierarchical scene design based on a construction tree whose leaves are environmental objects, a new kind of objects that generate their own geometrical decorations. We then present an implicit formalism to define the environment that contains all the information needed to guide decorations generation. Finally, we detail four procedural methods for generating the geometrical decorations (snow, ice, grass, leaves) of the environmental objects.

Cette thèse porte sur un des problèmes majeurs issus du domaine de la Conception Assistée par Ordinateur (CAO) à savoir celui de l'intersection. On aborde cette problèmatique avec une approche novatrice passant par une nouvelle forme de représentation des surfaces dites \og procédurales \fg{}. Cette dernière se base sur des approximants plus fins que les triangles habituellement utilisés, il s'agit de carreaux de surfaces paramétrées polynomiales de bas degré. L'approximation ainsi obtenue possède des caractères intéressants en termes de qualité et de représentation. Cependant, la mise en oeuvre d'une telle stratégie nécessite l'élaboration d'outils adaptés. En particulier, pour le problème d'intersection, il faut savoir intersecter efficacement les approximants. Pour cela, une méthode algorithmique permet de se focaliser uniquement sur des configurations d'intersection \og pertinentes \fg{}. Plusieurs méthodes sur l'intersection des surfaces paramétrées polynomiales sont ensuite exposées de manière effective. Enfin, les aspects d'implémentation sont également abordés à travers l'intégration des algorithmes développés dans un modeleur algébrique géométrique.

La représentation des surfaces du monde réel dans la mémoire d'une machine peut désormais être obtenue automatiquement via divers périphériques de capture tels que les scanners 3D. Ces nouvelles sources de données, précises et rapides, amplifient de plusieurs ordres de grandeur la résolution des surfaces 3D, apportant un niveau de précision élevé pour les applications nécessitant des modèles numériques de surfaces telles que la conception assistée par ordinateur, la simulation physique, la réalité virtuelle, l'imagerie médicale, l'architecture, l'étude archéologique, les effets spéciaux, l'animation ou bien encore les jeux video. Malheureusement, la richesse de la géométrie produite par ces méthodes induit une grande, voire gigantesque masse de données à traiter, nécessitant de nouvelles structures de données et de nouveaux algorithmes capables de passer à l'échelle d'objets pouvant atteindre le milliard d'échantillons. Dans cette thèse, je propose des solutions performantes en temps et en espace aux problèmes de la modélisation, du traitement géométrique, de l'édition intéractive et de la visualisation de ces surfaces 3D complexes. La méthodologie adoptée pendant l'élaboration transverse de ces nouveaux algorithmes est articulée autour de 4 éléments clés : une approche hiérarchique systématique, une réduction locale de la dimension des problèmes, un principe d'échantillonage-reconstruction et une indépendance à l'énumération explicite des relations topologiques aussi appelée approche basée-points. En pratique, ce manuscrit propose un certain nombre de contributions, parmi lesquelles : une nouvelle structure hiérarchique hybride de partitionnement, l'Arbre Volume-Surface (VS-Tree) ainsi que de nouveaux algorithmes de simplification et de reconstruction ; un système d'édition intéractive de grands objets ; un noyau temps-réel de synthèse géométrique par raffinement et une structure multi-résolution offrant un rendu efficace de grands objets. Ces structures, algorithmes et systèmes forment une chaîne capable de traiter les objets en provenance du pipeline d'acquisition, qu'ils soient représentés par des nuages de points ou des maillages, possiblement non 2-variétés. Les solutions obtenues ont été appliquées avec succès aux données issues des divers domaines d'application précités.

La modélisation géométrique est utilisée dans de nombreux domaines pour la construction d’objets 3D, l’animation ou les simulations. Chaque domaine est soumis à ses propres contraintes et nécessiterait un outil dédié. En pratique, un même outil est utilisé pour plusieurs domaines, en factorisant les caractéristiques communes. Ces modeleurs fournissent un ensemble d'opérations types, que l'utilisateur compose pour construire ses objets. Pour des opérations plus spécifiques, les outils actuels offrent des API.La plate-forme Jerboa propose un outil de génération d'opérations géométriques personnalisées. Elles sont définies graphiquement par des règles de transformations de graphes. Des vérifications automatiques de préservation de la cohérence des objets sont faites lors de l’édition qui peuvent être enrichies par des propriétés métiers. Notre contribution a consisté à étendre le langage par des scripts, pour composer les règles et réaliser des opérations complexes. Nous avons étendu les vérifications automatiques, en particulier pour assurer la cohérence géométrique. Enfin, nous avons modifié le processus d'application des opérations pour augmenter les possibilités de contrôle.Pour valider cette approche, nous avons développé un modeleur dédié à la géologie, pour la représentation du sous-sol, en collaboration avec l'entreprise Géosiris. Nous avons défini un flux d'activité avec Géosiris en suivant des contraintes spécifiques à la géologie. Grâce à la rapidité de développement des opérations dans Jerboa, nous avons pu prototyper et tester rapidement plusieurs algorithmes de reconstruction du sous-sol, pour les appliquer sur des données réelles fournies par l'entreprise. / Geometric modeling is used in various scopes for 3D object construction, animation or simulations. Each domain must cope with its constraints and should have its dedicated tool. In fact, several common characteristics of different domains are factored in a single tool. These modelers contain sets of basic operations that the user composes to build his objects. For more specific operations, current common tools offer API.Jerboa’s platform allows to generate personalized geometrical operations. These are defined by graph transformation rules. During their design, many automated verifications are done for the preserving of object consistency. They also be enriched with additional properties. Our contribution consists in extending the Jerboa language with scripts to compose rules and define complex operations. We also extended automated verifications, in particular to ensure geometric consistaency. Finally, we modified operations application process, in order to increase user control possibilities.To validate this approach, we have implemented a geological dedicated modeler for subsoil modeling, in collaboration with Geosiris Company. We defined a workflow with Geosiris that follows specific geological reconstruction constraints. Thanks to the Jerboa rapid prototyping mecanism, we developped and quickly tested several subsoil reconstruction algorithms, and apply them to real data provided by the company.

Le dessin est la manière la plus courante de communiquer sur les formes.Ainsi, l'utilisation de l'esquisse comme outil dans le processus de modélisation de contenus 3D est une approche attrayante.Cependant, dans le monde des machines, les dessins sont encore difficiles à interpréter comme des représentations de formes 3D.Ce défi a été relevé par de nombreux travaux de recherche, car tirer parti du peu de connaissances que nous possédons sur la perception n’est pas anodin.Ma thèse se concentre sur les limites de ce qui peut être inféré à partir de dessins uniques de formes lisses sans aucune aide de l'utilisateur.Dans un premier temps, nous avons choisi une catégorie de forme, à savoir les animaux et autres créatures pour lesquels une connaissance préalable aide à résoudre le problème.Ensuite, nous avons proposé de généraliser certaines parties de la solution pour aborder le cas des formes organiques libres.Ce manuscrit présente donc les solutions respectives que nous avons développées.La première permet de déduire des modèles 3D plausibles d’animaux à partir d’une seule esquisse de vue latérale en utilisant des principes anatomiques pour interpréter les éléments du dessin et déduire des décalages de profondeur entre les éléments.La seconde est une approche qui consiste à décomposer les représentations de formes lisses avec des points de recouvrement non triviaux en un ensemble de silhouettes de parties structurelles ordonnées en profondeur, qui peuvent être utilisées à des fins d'édition et d'animation.Beaucoup d'idées connexes ont été explorées en parallèle, et celles présentées dans ce manuscrit me donnent confiance en l'avenir de ce domaine de recherche. / Drawing is the most common way to communicate about shapes.Thus, using sketching as a tool in the process of modeling 3D content is an attractive approach.However in the world of machines, drawings are still difficult to interpret as shape depictions.This has been the challenge tackled by many different research works since leveraging the little we know about perception is non trivial.My thesis focuses on pushing the limits of what can be inferred from single drawings of smooth shapes without any help from the user.In a first attempt we chose to select a category of shape namely animals and other creatures for which prior knowledge helps to solve the problem.Then we proposed to generalize parts of the solution to tackle the case of free form organic shapes.This manuscript thus presents the respective solutions we developed. The first one is able to infer plausible 3D models of animals from a single side-view sketch using anatomic principles to both interpret the drawing's elements and infer depth offsets between these elements.The second is an approach to decompose depictions of smooth shapes with non trivial cusp points into a set of structural parts' silhouettes ordered in depth, which can be used for editing and animation purposes.Many related ideas were explored on the way, and the ones presented in this manuscript leaves me confident about the future of this field of research.

L'imagerie médicale est une ressource de données principale pour différents types d'applications. Bien que les images concrétisent beaucoup d'informations sur le cas étudié, toutes les connaissances a priori du médecin restent implicites. Elles jouent cependant un rôle très important dans l'interprétation et l'utilisation des images médicales. Dans cette thèse, des connaissances anatomiques a priori sont intégrées dans deux applications médicales. Nous proposons d'abord une chaîne de traitement automatique qui détecte, quantifie et localise des anévrismes dans un arbre vasculaire segmenté. Des lignes de centre des vaisseaux sont extraites et permettent la détection et la quantification automatique des anévrismes. Pour les localiser, une mise en correspondance est faite entre l'arbre vasculaire du patient et un arbre vasculaire sain. Les connaissances a priori sont fournies sous la forme d'un graphe. Dans le contexte de l'identification des sous-parties d'un organe représenté sous forme de maillage, nous proposons l'utilisation d'une ontologie anatomique, que nous enrichissons avec toutes les informations nécessaires pour accomplir la tâche de segmentation de maillages. Nous proposons ensuite un nouvel algorithme pour cette tâche, qui profite de toutes les connaissances a priori disponibles dans l'ontologie. / Medical imaging is a principal data source for different applications. Even though medical images represent a lot of knowledge concerning the studied case, all the a priori knowledge known by the specialist remains implicit. Nevertheless this a priori knowledge has a major role in the interpretation and the use of the images. In this thesis, anatomical a priori knowledge is integrated in two medical applications. First, an automatic processing pipeline is proposed in order to detect, quantify and localize aneurysms on a segmented cerebrovascular tree. Centerlines of blood vessels are extracted and then used to automatically detect aneurysms and quantify them. To localize aneurysm, a matching is made between the cerebrovascular tree of the patient and a healthy one. The a priori knowledge, in this case, is represented by a graph. In the context of identifying sub-parts of an organ represented by a mesh, we propose the use of an anatomical ontology. This ontology is first enhanced by all information necessary to achieve the task of mesh segmenting. A new algorithm using this ontology to accomplish the segmentation task is then proposed.