Multi-scale simplification and visualization of large 3D models

Simplification multi-échelle et visualisation de grands modèles 3D Cette thèse s'intéresse à la création et à la visualisation interactive de maillages surfaciques issus de données massives, telles que celles obtenues suite à l'emploi de scanners à télédétection laser ou de prises de vues multiples. Ces dernières années ont en effet vu l'accélération du développement, de la miniaturisation et de la démocratisation de ces dispositifs de capture visant une représentation fine du réel. Les données brutes issues des captures, par exemple en géographie, archéologie ou en médecine sont difficiles à exploiter car volumineuses et désordonnées. Pour faire face à ce défi, la première étape d'une chaîne de traitement consiste classiquement en la création d'un maillage très haute résolution. La solution retenue doit palier au mieux les bruits de mesure et reproduire la topologie de l'objet étudié. L'augmentation de la résolution des dispositifs de capture, des capacités de mémoire et de traitement du matériel de visualisation rend souvent impraticable la visualisation interactive des maillages haute résolution. Ces maillages de dizaines de millions voire plusieurs milliards d'éléments sont un défi pour le matériel et pour le transfert de données entre les composants de la chaîne. L'étape suivante implique la création d'une hiérarchie de maillages simplifiés dérivant de l'original, les pertes de détail à chaque simplification étant contrôlées. Bien que cette approche semble contourner le problème au lieu de le résoudre, seul le niveau de détail importe en visualisation. Ainsi, il devient possible de découper les niveaux de maillage en sous-parties, les sélectionner et les recombiner à la volée pour suivre les mouvements du point d'observation en optimisant partout le niveau de détail apparent. Dans la première partie de la thèse, nous proposons une approche qui s'attache à résoudre les deux difficultés principales inhérentes à la gestion simultanée de plusieurs morceaux de maillages de résolutions différentes : les défauts de jointures ("mesh cracks''), et les problèmes de discontinuité temporelle suite aux changements de résolutions ("LOD popping''). Cette approche, dans la longue lignée de travaux ayant abordé ces questions, s'inscrit au carrefour entre les techniques basées sur le morphing entre maillages et celles basées sur les multi-triangulations. Nous l'accompagnons d'une implémentation de référence, ainsi que d'un prototype de visualiseur léger servant de preuve de concept. La partie pré-traitement, qui construit la hiérarchie à partir du maillage haute résolution, se distingue par une capacité de l'ordre du million de triangles par seconde et par cœur de calcul, ce qui représente un ordre de grandeur de gain par rapports aux solutions existantes que nous avons pu tester. Dans la seconde partie de la thèse, nous abordons la question de la construction du maillage haute résolution à partir d'un nuage de points dans le cas spécifique du Lidar aéroporté. Nous montrons que la fiabilité des méthodes classiques d'estimation de normales peut être nettement améliorée en tenant compte de données propres à de tels relevés : horodatage des points et angle du faisceau laser notamment. Cette amélioration a une incidence cruciale sur la qualité de la reconstruction ultérieure d'un maillage surfacique par la méthode dite de Poisson. Cette dernière obtient le maillage comme surface de niveau d'une fonction scalaire, elle-même obtenue par la résolution d'un problème de Poisson pour lequel le nuage de points orientés intervient dans la définition du terme source. Nous appliquons ces méthodes aux données libres récentes des programmes Lidar suisse (SwissSurface3D) et français (Lidar HD), et montrons qu'elles permettent une reproduction plus fidèle que les méthodes classiques basées sur les grilles à pas régulier (modèle numériques de terrain), d'autant plus dans les zones montagneuses.