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.

Réalisé en cotutelle avec l'Université de Grenoble. / La complexité des mondes virtuels ne cesse d’augmenter et les techniques de modélisation classiques peinent à satisfaire les contraintes de quantité nécessaires à la production de telles scènes. Les techniques de génération procédurale permettent la création automatisée de mondes virtuels complexes à l’aide d’algorithmes, mais sont souvent contre-intuitives et par conséquent réservées à des artistes expérimentés. En effet, ces méthodes offrent peu de contrôle à l’utilisateur et sont rarement interactives. De plus, il s’agit souvent pour l’utilisateur de trouver des valeurs pour leurs nombreux paramètres en effectuant des séries d’essais et d’erreurs jusqu’à l’obtention d’un résultat satisfaisant, ce qui est souvent long et fastidieux. L’objectif de cette thèse est de combiner la puissance créatrice de la génération procédurale avec un contrôle utilisateur intuitif afin de proposer de nouvelles méthodes interactives de modéli- sation de mondes virtuels. Tout d’abord, nous présentons une méthode de génération procédurale de villages sur des terrains accidentés, dont les éléments sont soumis à de fortes contraintes de l’environnement. Ensuite, nous proposons une méthode interactive de modélisation de cascades, basée sur un contrôle utilisateur fin et la génération automatisée d’un contenu cohérent en regard de l’hydrologie et du terrain. Puis, nous présentons une méthode d’édition de terrains par croquis, où les éléments caractéristiques du terrain comme les lignes de crêtes sont analysés et déformés pour correspondre aux silhouettes complexes tracées par l’utilisateur. Enfin, nous proposons une métaphore de peinture pour la création et l’édition interactive des mondes virtuels, où des tech- niques de synthèse d’éléments vectoriels sont utilisées pour automatiser la déformation et l’édition de la scène tout en préservant sa cohérence. / The complexity required for virtual worlds is always increasing. Conventional modeling tech- niques are struggling to meet the constraints and efficiency required for the production of such scenes. Procedural generation techniques use algorithms for the automated creation of virtual worlds, but are often non-intuitive and therefore reserved to experienced programmers. Indeed, these methods offer fewer controls to users and are rarely interactive. Moreover, the user often needs to find values for several parameters. The user only gets indirect control through a series of trials and errors, which makes modeling tasks long and tedious. The objective of this thesis is to combine the power of procedural modeling techniques with intuitive user control towards interactive methods for designing virtual worlds. First, we present a technique for procedural modeling of villages over arbitrary terrains, where elements are subjected to strong environmental constraints. Second, we propose an interactive technique for the procedural modeling of waterfall sceneries, combining intuitive user control with the automated generation of consistent content, in regard of hydrology and terrain constraints. Then, we describe an interactive sketch-based technique for editing terrains, where terrain features are extracted and deformed to fit the user sketches. Finally, we present a painting metaphor for virtual world creation and editing, where methods for example-based synthesis of vectorial elements are used to automate deformation and editing of the scene while maintaining its consistency.