Jean-Daniel Boissonnat et la troisième dimension du multimédia

© INRIA / Photo Jim Wallace

Après des études d’ingénieur à Supelec, Jean-Daniel Boissonnat se lance dans une thèse sur l’identification des modes flexibles de satellites munis de grandes antennes. Plutôt que poursuivre ces recherches à l’Agence Spatiale Européenne, il préfère intégrer l’INRIA en 1981 et commence ses recherches sur la géométrie algorithmique, un domaine dont il est un des précurseurs.

En 1986, l’INRIA lui offre la possibilité de monter sa propre équipe de recherche, PRISME. PRISME s’intéresse principalement aux aspects géométriques de la robotique : modélisation de l’environnement, calcul de l’espace de travail des mécanismes et planification de trajectoires. Quelques années après, les axes de recherche ont évolué et en 2002, Jean-Daniel Boissonnat monte une nouvelle équipe, GEOMETRICA, qui a pour ambition de développer le calcul géométrique certifié.

L’histoire commence dans les années quatre-vingts ; Jean-Daniel Boissonnat a rejoint l’équipe de l’INRIA où François Germain et George Kryze viennent de développer l’un des premiers capteurs 3D. Il s’agit de mesurer précisément les coordonnées de points à la surface d’un objet tridimensionnel. Pour cela, un faisceau laser en balaie la surface et deux caméras filment le tout, restituant par stéréo les coordonnées dans l’espace de chaque point éclairé de la surface.

Capteur 3D.

Ce nouveau type de données ouvre de nouvelles directions de recherche. À partir de ces points éparpillés dans l’espace, comment peut-on reconstituer un objet 3D visible et manipulable sur ordinateur ? Peut-on imaginer un logiciel qui dessinerait la surface de l’objet, en traçant des triangles entre les points et en combinant ces petites surfaces pour reconstituer la surface globale ? Il s’agit en fait de structurer les données acquises par le capteur et de retrouver la topologie de l’objet. Jean-Daniel Boissonnat a l’idée d’utiliser une structure de données qu’étudie la toute nouvelle discipline qu’est alors la géométrie algorithmique : la « triangulation de Delaunay ». Il publie un article qui constitue le point de départ de la recherche sur le sujet. La « triangulation de Delaunay » est aujourd’hui universellement utilisée pour la reconstruction de surface.

Concrétiser l’idée

De la première idée à sa concrétisation, il faudra quinze années de recherche, un travail de longue haleine guidé par la curiosité, des instants d’opportunité, des pressions industrielles, une équipe, des partenaires, et un « happy end », car un logiciel développé par Jean-Daniel Boissonnat et son équipe est aujourd’hui intégré dans CATIA, le progiciel de CAO de Dassault Systèmes, leader incontesté, et utilisé donc par la plupart des grands industriels dans le monde.

Pourquoi si longtemps ? Pour qu’un logiciel soit utilisable, il faut qu’il reconstitue fidèlement l’objet observé, en toute circonstance. De plus, il ne suffit pas de « savoir » que la reconstitution est fidèle, il faut démontrer et garantir la fiabilité de la représentation géométrique.

Or, à peine se pose-t-on la question que des problèmes surgissent, liés, par exemple, aux variations de densité des points. Si le capteur balaie l’objet, on aura de nombreux points sur une ligne, puis, le capteur changeant de ligne, on aura de nombreux points sur la ligne suivante. Entre les deux lignes, rien. Lorsque le logiciel voudra utiliser les points les plus voisins pour réaliser la triangulation, ce seront souvent ceux qui sont alignés, inutilisables pour faire un triangle. C’est la première difficulté, d’ordre mathématique : définir un bon échantillonnage et trouver des méthodes qui garantissent que l’objet reconstruit à partir de cet échantillon est une bonne approximation de la réalité.

Échantillonnage et maillage de surfaces.
Image : projet GEOMETRICA.

Le deuxième défi sur lequel ont travaillé les chercheurs est lié à l’efficacité et à la fiabilité des calculs. Il est courant de devoir traiter des centaines de milliers voire des millions de points. Il faut alors pouvoir faire aveuglément confiance au programme et le résultat doit néanmoins être disponible très rapidement. La fiabilité et l’efficacité sont en général des objectifs antagonistes. Résoudre cet antagonisme est la clé de la qualité logicielle en géométrie. C’est un enjeu qui continue de mobiliser l’équipe GEOMETRICA qu’anime aujourd’hui Jean-Daniel Boissonnat.

En quinze ans, les progrès en algorithmique ont été spectaculaires et ont permis la commercialisation de deux logiciels de reconstruction de surface baptisés Nuages. L’un a été adopté en 2000 par Dassault Systèmes. L’autre version adaptée au cas des images médicales équipe les scanners médicaux de Siemens.

Une avance européenne

Conscients de la nécessité de comparer, regrouper et mettre en cohérence tous les travaux accomplis en géométrie algorithmique, les chercheurs européens prennent alors une initiative qui reçoit le soutien financier de la Communauté Européenne. Ce projet conduit à la création de la « bibliothèque » CGAL (Computational Geometry Algorithms Library), qui implémente ce que la géométrie algorithmique a produit de plus utile. L’équipe qu’anime Jean-Daniel Boissonnat fait partie des principaux partenaires de CGAL. Le développement de CGAL a contribué à structurer une communauté dynamique de chercheurs européens qui a pris une avance décisive dans le domaine des logiciels de géométrie algorithmique.

Pour progresser dans la recherche, chacun peut utiliser CGAL qui est disponible en open source. Plusieurs des principaux laboratoires de recherche américains qui travaillent sur la reconstruction de surface utilisent les codes de calcul de triangulations développés par les chercheurs de GEOMETRICA et disponibles dans CGAL. Pour l’exploitation industrielle des logiciels de CGAL, une startup, Geometry Factory, a été créée en janvier 2003.

Aujourd’hui les capteurs 3D ne sont plus des objets de laboratoire. Un tissu industriel riche se développe à partir de la reconstruction de surface autour d’applications très diverses, de la culture à la médecine. L’équipe de Jean-Daniel Boissonnat poursuit ses recherches sur des objets plus complexes et sur d’autres aspects de la modélisation géométrique : maillages anisotropes, segmentation de données 3D, représentations multiéchelles, compression. Les applications visées sont principalement le calcul scientifique, le graphique, la médecine et la biologie structurale.