Level sets are extensively used for the visualization of scalar fields. The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. It is obtained by mapping each connected component of a level set to a point. The Reeb graph and its loop-free version called the contour tree serve as an effective user interface for selecting meaningful level sets and for designing transfer functions for volume rendering. It also finds several other applications in the field of scientific visualization. In this thesis, we focus on designing algorithms for efficiently computing the Reeb graph of scalar functions and using the Reeb graph for effective visualization of scientific data. We have developed three algorithms to compute the Reeb graph of PL functions defined over manifolds and non-manifolds in any dimension. The first algorithm efficiently tracks the connected components of the level set and has the best known theoretical bound on the running time. The second algorithm, utilizes an alternate definition of Reeb graphs using cylinder maps, is simple to implement and efficient in practice. The third algorithm aggressively employs the efficient contour tree algorithm and is efficient both theoretically, in terms of the worst case running time, and practically, in terms of performance on real-world data. This algorithm has the best performance among existing methods and computes the Reeb graph at least an order of magnitude faster than other generic algorithms. We describe a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. We also employ the Reeb graph in four different applications – surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data. Finally, we introduce the notion of topological saliency that captures the relative importance of a topological feature with respect to other features in its local neighborhood. We integrate topological saliency with Reeb graph based methods and demonstrate its application to visual analysis of features.

A growing number of 3D graphic applications have an impact on today's society. These applications are being used in several domains ranging from digital entertainment, computer aided design, to medical applications. In this context, a 3D object search engine with a good performance in time consuming and results becomes mandatory. We propose a novel approach for 3D-model retrieval based on closed curves. Then we enhance our method to handle partial 3D-model retrieval. Our method starts by the definition of an invariant mapping function. The important properties of a mapping function are its invariance to rigid and non rigid transformations, the correct description of the 3D-model, its insensitivity to noise, its robustness to topology changes, and its independance on parameters. However, current state-of-the-art methods do not respect all these properties. To respect these properties, we define our mapping function based on the diffusion and the commute-time distances. To prove the properties of this function, we compute the Reeb graph of the 3D-models. To describe the whole 3D-model, using our mapping function, we generate indexed closed curves from a source point detected automatically at the center of a 3D-model. Each curve describes a small region of the 3D-model. These curves lead to create an invariant descriptor to different transformations. To show the robustness of our method on various classes of 3D-models with different poses, we use shapes from SHREC 2012. We also compare our approach to existing methods in the state-of-the-art with a dataset from SHREC 2010. For partial 3D-model retrieval, we enhance the proposed method using the Bag-Of-Features built with all the extracted closed curves, and show the accurate performances using the same dataset

Un nombre croissant d’applications graphiques 3D ont un impact sur notre société. Ces applications sont utilisées dans plusieurs domaines allant des produits de divertissement numérique, la conception assistée par ordinateur, aux applications médicales. Dans ce contexte, un moteur de recherche d’objets 3D avec de bonnes performances en résultats et en temps d’exécution devient indispensable. Nous proposons une nouvelle méthode pour l’indexation de modèles 3D basée sur des courbes fermées. Nous proposons ensuite une amélioration de notre méthode pour l’indexation partielle de modèles 3D. Notre approche commence par la définition d’une nouvelle fonction d’application invariante. Notre fonction d’application possède des propriétés importantes : elle est invariante aux transformations rigides et non rigides, elle est insensible au bruit, elle est robuste à de petits changements topologiques et elle ne dépend pas de paramètres. Cependant, dans la littérature, une telle fonction qui respecte toutes ces propriétés n’existe pas. Pour respecter ces propriétés, nous définissons notre fonction basée sur la distance de diffusion et la distance de migration pendulaire. Pour prouver les propriétés de notre fonction, nous calculons le graphe de Reeb de modèles 3D. Pour décrire un modèle 3D complet, en utilisant notre fonction d’application, nous définissons des courbes de niveaux fermées à partir d’un point source détecté automatiquement au centre du modèle 3D. Chaque courbe décrit alors une région du modèle 3D. Ces courbes créent un descripteur invariant à différentes transformations. Pour montrer la robustesse de notre méthode sur différentes classes de modèles 3D dans différentes poses, nous utilisons des objets provenant de SHREC 2012. Nous comparons également notre approche aux méthodes de l’état de l’art à l’aide de la base SHREC 2010. Pour l’indexation partielle de modèles 3D, nous améliorons notre approche en utilisant la technique sacs de mots, construits à partir des courbes fermées extraites, et montrons leurs bonnes performances à l’aide de la base précédente / A growing number of 3D graphic applications have an impact on today’s society. These applications are being used in several domains ranging from digital entertainment, computer aided design, to medical applications. In this context, a 3D object search engine with a good performance in time consuming and results becomes mandatory. We propose a novel approach for 3D-model retrieval based on closed curves. Then we enhance our method to handle partial 3D-model retrieval. Our method starts by the definition of an invariant mapping function. The important properties of a mapping function are its invariance to rigid and non rigid transformations, the correct description of the 3D-model, its insensitivity to noise, its robustness to topology changes, and its independance on parameters. However, current state-of-the-art methods do not respect all these properties. To respect these properties, we define our mapping function based on the diffusion and the commute-time distances. To prove the properties of this function, we compute the Reeb graph of the 3D-models. To describe the whole 3D-model, using our mapping function, we generate indexed closed curves from a source point detected automatically at the center of a 3D-model. Each curve describes a small region of the 3D-model. These curves lead to create an invariant descriptor to different transformations. To show the robustness of our method on various classes of 3D-models with different poses, we use shapes from SHREC 2012. We also compare our approach to existing methods in the state-of-the-art with a dataset from SHREC 2010. For partial 3D-model retrieval, we enhance the proposed method using the Bag-Of-Features built with all the extracted closed curves, and show the accurate performances using the same dataset