Projets

My work spans computer graphics to computational geometry and topology. With an overall goal of shape analysis and understanding, my research interests include the acquisition, reconstruction and processing of 3D shapes.

I have worked on shapes digitized with laser scanners as well as medical imagery. These shapes range from human bodies and organs to animals, trees, plants or even mechanical parts.

Keywords: mesh generation, shape understanding, geometry processing, computational topology, feature detection, 3D shape analysis.

 

 

Surface mesh generation from 3D point clouds

Le domaine. La numérisation d’objets réels est de plus en plus
utilisée dans des domaines tels que la CAO, l’architecture, la simulation scientifique ou la fabrication additive. Les outils d’acquisition (scanner laser, Kinect, photogrammétrie,…) permettent de produire des représentations numériques d’objets sous forme de nuages de points 3D qui échantillonnent la surface de ces objets. Il faut alors produire à partir de ces points un maillage qui approxime ou interpole les points d’entrée. (Par exemple, la figure ci-contre est une reconstruction du château Saint Gallen à partir d’un échantillon LIDAR de 14 millions de points.) C’est un problème fondamental mais difficile car il faut choisir le maillage le plus « probable » selon des critères mal définis.

Objectifs : Diverses méthodes ont été proposées pour aborder ce problème de reconstruction : Ball Pivoting, Cocone, Poisson . . . Certaines se comportent très bien en pratique, mais avec peu de garanties théoriques sur la qualité du résultat. D’autres sont bien comprises théoriquement mais s’avèrent moins efficaces en pratique. L’objectif de ce travail est de concilier ces deux types d’approches.
Les méthodes qui offrent des garanties théoriques commencent par calculer un premier volume approximant la surface, puis s’en servent pour filtrer une subdivision bien choisie de l’espace 3D ambiant, produisant ainsi une soupe de triangles qu’elles traitent (suppression de slivers, recollements locaux) pour obtenir un maillage. La subdivision de l’espace ambiant est généralement la tétraèdralisation de Delaunay de l’échantillon, l’approximation volumique varie (union de boules ou de co-cones par exemple). Si l’échantillon est suffisamment précis, le maillage produit est garanti d’être une bonne approximation géométrique et topologique de la surface originelle.

Nous avons récemment proposé une variante de ces méthodes qui s’affranchit de la construction (coûteuse) d’une subdivision de l’espace ambiant. Il s’agit de calculer directement le diagramme de Voronoï des points d’entrée restreint à l’union de disques centrés aux points et orthogonaux aux normales estimées de la surface aux points. Cela revient à calculer de manière indépendante la facette de Voronoï restreinte pour chaque point d’entrée, par une routine de type polygon-plan clipping. La figure de droite montre les facettes de Voronoï calculées, sur un cheval, pour différentes valeur du rayon des disques.
Cette méthode se comporte expérimentalement très bien, notamment car elle se parallélise très facilement.
Actuellement, elle est déjà déployée par plusieurs industriels, dont Trimble , fabriquant de scanners 3D. L’objectif de ce stage est d’étudier ses performances d’un point de vue théorique. On étudiera en particulier les  techniques similaires de construction locales développées en géométrie algorithmique. On s’efforcera notamment de décrire de quelle manière le maillage reconstruit s’éloigne d’une triangulation de Delaunay restreinte.

 

Building modelling from LIDAR data

Reconnaissance de bâtiments à partir de nuages de points 3D

Contexte : La numérisation d’objets réels est de plus en plus utilisée dans des domaines tels que l’urbanisme, l’architecture ou l’aménagement d’espaces publics. Les outils d’acquisition tels que les lidars ou la photogrammétrie permettent de produire des représentations numériques de villes entières sous forme de nuages de points 3D échantillonnant les surfaces des objets de l’environnement.
Aujourd’hui, le processus de création d’une maquette numérique à partir de tels relevés est long, fastidieux et essentiellement manuel. Dans ce processus de rétro conception, l’opérateur humain trace à la main les éléments constitutifs de la maquette de sorte à coller au mieux au nuage de points.

Par exemple, la figure ci-contre représente une maquette virtuelle de la ville de Monaco, générée avec le logiciel RhinoCity à partir de données lidar et de photogrammétrie. Des outils d’assistance semi-automatiques émergent sur le marché, mais ils ne répondent pas suffisamment au besoin, tant en termes de précision que d’efficacité.

Notre équipe de recherche travaille en collaboration avec la société RhinoTerrain qui est spécialisée dans la géomatique et l’imagerie 3D. Elle développe une nouvelle génération d’outils 3D de “Géo-Modélisation” dédiés à la production structurée de données géoréférencées et standardisées. Un des axes R&D de la société porte sur l’optimisation du processus de réalisation d’une maquette 3D à partir des relevés pouvant provenir de sources différentes (points 3D lidar, images satellites, photos,
etc.). L’objectif est, bien sûr, de réduire les coûts liés à la constitution des maquettes, d’accroître sa compétitivité et d’accélérer l’adhésion des industriels à la méthodologie. L’objectif à long terme est de développer un outil permettant d’assister le dessinateur dans la création des maquettes 3D de manière semi-manuelle.

 

Geological modelling from LIDAR data

Détections des lignes caractéristiques à partir de données scanners de massifs rocheux

Contexte : L’interprétation de données numériques de massifs rocheux, également nommé affleurements, est une étape cruciale pour l’analyse des corps géologiques, leur géométrie et leur agencement. Elle est nécessaire pour la compréhension et la reconstitution spatio-temporelle des phénomènes de formation du sous-sol.

Aujourd’hui, le scanner LIDAR est un système de télémesure attrayant car il offre la possibilité d’obtenir la géométrie d’un affleurement en un temps raisonnable. Lors des campagnes de récoltes de données par LIDAR, l’acquisition de la géométrie des affleurements s’effectue soit par voie terrestre, soit par LIDAR aéroporté dans le cas des falaises (cf. figure ci-contre). Cependant, les volumes générés atteignent souvent plusieurs millions de points pour quelques kilomètres d’acquisition. Du fait des quantités de données à traiter, l’interprétation réalisée de façon manuelle se révèle fastidieuse et chronophage. Elle s’attache principalement à relever, à partir des données numériques d’affleurements, les points décrivant les discontinuités i.e. les limites stratigraphiques et les fractures. L’automatisation partielle de cette étape constitue le principal objectif de ce travail, à long terme.