Thèse doctorat : Informatique : Rennes 1 : 2006. / Thèse en anglais qui contient un long résumé en français. Bibliogr. p. 101-109.

Thèse doctorat : Informatique : Rennes 1 : 2008. Thèse doctorat : Informatique : University of central Florida (Orlando) : 2008. / Titre provenant de la page du titre du document électronique. Bibliogr. p. 109-114.

Afin de créer des productions toujours plus réalistes, les industries du jeu vidéo et du cinéma cherchent à générer des environnements de plus en plus larges et complexes. Cependant, la modélisation manuelle des objets 3D dans de tels décors se révèle très coûteuse. A l’inverse, les méthodes de génération procédurale permettent de créer facilement une grande variété d’objets, tels que les plantes et les bâtiments. La modélisation par règles de grammaire offre un outil de haut niveau pour décrire ces objets, mais utiliser correctement ces règles s’avère très souvent compliqué. De plus, aucune solution de modélisation basée grammaire ne supporte l’édition et la visualisation d’environnements massifs en temps interactif. Dans un tel scénario, les artistes doivent modifier les objets en dehors de la scène avant de voir le résultat intégré.Dans ces travaux de recherche, nous nous intéressons à la génération procédurale et au rendu d’environnements à grande échelle. Nous voulons aussi faciliter la tâche des artistes avec des outils intuitifs de contrôle de grammaires. Tout d’abord nous proposons un système permettant la génération procédurale en parallèle sur le GPU en temps interactif. Pour cela, nous adoptons une approche d’expansion indépendante par segment, permettant une amplification des données en parallèle. Nous étendons ce système pour générer des modèles basés sur une structure interne, tels que les toits. Nous présentons aussi une solution utilisant des contextes externes pour contrôler facilement les grammaires par le biais de surface ou de texture. Pour finir nous intégrons un système de niveaux de détails et des techniques d’optimisation permettant la génération, l’édition et la visualisation interactives d’environnements à grande échelle. Grâce à notre système il est possible de générer et d’afficher interactivement des scènes comprenant des milliers de bâtiments et d’arbres, représentant environ 2 téraoctets de données. / With the increasing computing and storage capabilities of recent hardware, movie and video games industries desire huger realistic environments. However, modeling such sceneries by hand turns out to be highly time consuming and costly. On the other hand, procedural modeling provides methods to easily generate high diversity of elements such as vegetation and architecture. While grammar rules bring a high-level powerful modeling tool, using these rules is often a tedious task, necessitating frustrating trial and error process. Moreover, as no solution proposes real-time generation and rendering for massive environments, artists have to work on separate parts before integrating the whole and see the results.In this research, we aim to provide interactive generation and rendering of very large sceneries, while offering artist-friendly methods for controlling grammars behavior. We first introduce a GPU-based pipeline providing parallel procedural generation at render time. To this end we propose a segment-based expansion method working on independent elements, thus allowing for parallel amplification. We then extend this pipeline to permit the construction of models relying on internal contexts, such as roofs. We also present external contexts to control grammars with surface and texture data. Finally, we integrate a LOD system with optimization techniques within our pipeline providing interactive generation, edition and visualization of massive environments. We demonstrate the efficiency of our pipeline with a scene comprising hundred thousand trees and buildings each, representing 2 terabytes of data.

Rechercher les similarités entre séquences est une opération fondamentale en bioinformatique, que cela soit pour étudier des questions biologiques ou bien pour traiter les données issues de séquenceurs haut-débit. Il y a un vrai besoin d'algorithmes capables de traiter des millions de séquences rapidement. Pour trouver des similarités approchées, on peut tout d'abord considérer de petits mots exacts présents dans les deux séquences, les graines, puis essayer d'étendre les similarités aux voisinages de ces graines. Cette thèse se focalise sur la deuxième étape des heuristiques à base de graines : comment récupérer et comparer efficacement ces voisinages des graines, pour ne garder que les bons candidats ? La thèse explore différentes solutions adaptées aux processeurs massivement multicoeurs: aujourd'hui, les GPUs sont en train de démocratiser le calcul parallèle et préparent les processeurs de demain. La thèse propose des approches directes (extension de l'algorithme bit-parallèle de Wu-Manber, publiée à PBC 2011, et recherche dichotomique) ou bien avec un index supplémentaire (utilisation de fonctions de hash parfaites). Chaque solution a été pensée pour tirer le meilleur profit des architectures avec un fort parallélisme à grain fin, en utilisant des calculs intensifs mais homogènes. Toutes les méthodes proposées ont été implémentés en OpenCL, et comparées sur leur temps d'exécution. La thèse se termine par un prototype de read mapper parallèle, MAROSE, utilisant ces concepts. Dans certaines situations, MAROSE est plus rapide que les solutions existantes avec une sensibilité similaire.