La bibliothèque logicielle open source CGAL fait entrer la recherche en géométrie algorithmique dans l'industrie

Une première dans la communauté de la géométrie algorithmique

Chaque année, à l’occasion du "Symposium on Computational Geometry (SoCG)", prestigieuse conférence internationale consacrée à la géométrie algorithmique, la communauté du domaine souhaite mettre à l’honneur certains de ses membres. En leur remettant le "Test of Time Award", le comité récompense un article marquant, dont les résultats ont un impact fort sur la communauté et la discipline.

L’édition 2023 de SoCG, tenue à Dallas, déroge pourtant à cette règle. Le 15 juin dernier, en effet, Monique Teillaud, directrice de recherche chez Inria Nancy Grand-Est au sein de l’équipe Gamble (commune avec le Loria) et Andreas Fabri, dirigeant de GeometryFactory, ont reçu le fameux prix au nom du projet CGAL pour un développement logiciel : une première !

« Depuis ses débuts il y a bientôt 30 ans, l’aventure CGAL a mobilisé un collectif de scientifiques passionnés, issus d’Inria et d’autres institutions de recherche de premier plan. Nous sommes fiers de cette preuve de reconnaissance venue de notre communauté, qui souligne la qualité du travail réalisé ensemble. Nous avons reçu ce prix avec le sentiment d’un bel accomplissement », confie Monique Teillaud.

Un dialogue entre recherche et transfert industriel

Récompenser un logiciel de géométrie algorithmique, c’est mettre en lumière l’importance d’une discipline, avant tout théorique, dont les résultats intéressent cependant des pans entiers de notre économie. Ces vingt dernières années, notre monde s’est fortement numérisé et robotisé : la conception de nombreux systèmes complexes se fonde par exemple sur un usage massif de la simulation numérique par les ingénieurs, et la production en série de multiples objets ne saurait aujourd’hui se passer de robots – et que dire des technologies numériques, nichées au cœur des instruments des plus sophistiqués ou dans le moindre des logiciels grand public ?

« La géométrie algorithmique est un précieux serviteur du monde numérique, car elle permet de représenter mathématiquement les objets manipulés par nombre de systèmes numérisés ! », résume Pierre Alliez, responsable de l’équipe-projet Titane, au centre Inria d'Université Côte d'Azur.

CGAL est une bibliothèque (autrement dit une collection de fichiers de code source, prêts à l’emploi pour des programmes informatiques) intégrant un ensemble d’algorithmes de géométrie algorithmique. Ingénieurs et chercheurs, des mondes académique et industriel, l’utilisent quotidiennement pour des applications très variées : maillages tridimensionnels de surfaces, relevés de données topographiques ou géométriques, définition de trajectoires, placement d’antennes… ses applications sont innombrables ! Cette bibliothèque d’algorithmes a permis à plusieurs acteurs du public ou du privé de mener à bien des projets dans les domaines de la modélisation urbaine, de l’architecture, de l’astronomie, de la modélisation médicale ou encore de la biophysique.

Cette utilisation large de la bibliothèque CGAL permet d’avoir un échange régulier entre les scientifiques à l’origine de CGAL et ses utilisateurs. Ce dialogue permet de soulever de nouvelles réflexions, de nouvelles questions de recherche, de faire émerger de nouveaux sujets de thèse par exemple. La recherche et le transfert s’alimentent mutuellement. Un véritable dialogue s’est installé : c’est l’une des forces du projet. Des problématiques industrielles et académiques ouvrent ainsi de nouvelles questions aux scientifiques, faisant progresser la recherche et par conséquent CGAL.

Une communauté internationale mobilisée

Avant de devenir l’outil plébiscité qu’il est aujourd’hui, CGAL doit sa naissance en 1996 à la stratégie visionnaire d’un consortium international qui considérait que, pour trouver des applications utiles, la recherche en géométrie algorithmique devait s’appuyer sur un logiciel satisfaisant les exigences de qualité dont le monde industriel est familier.

« Il y a 30 ans, les recherches autour de la géométrie algorithmique étaient très théoriques (algorithmes, théorèmes, preuves). Le monde industriel avait un intérêt pour certains de ces travaux, mais les algorithmes étaient souvent trop compliqués pour être implémentés et les quelques implémentations étaient rarement robustes. Le collectif CGAL est né. L’objectif était de travailler sur des aspects plus pratiques », explique Monique Teillaud.

Deux projets européens ont permis d’amorcer la démarche, agrégeant des partenaires en Europe et Israël, que d’autres projets et sources de financement sont venus progressivement compléter. La première version de la bibliothèque a été diffusée en 1997 : CGAL accomplissait ses premiers pas ! Quatre ans plus tard, en 2001, les membres du projet décident de créer un comité éditorial.

« Au sein de ce comité, nous avons élaboré les règles et procédures régissant le projet, et nous coordonnons au jour le jour le processus de relecture des soumissions. Les membres du comité sont animés par la seule ambition de servir l’intérêt du projet… La démarche que nous adoptons est celle d’une recherche collaborative » résume Monique Teillaud.

Cette stratégie s’avère payante, car CGAL ne cesse de croître en notoriété : en 2003, elle devient un logiciel open source, avec double licence (libre et commerciale) et le projet accueille alors de nouveaux contributeurs. La même année, Andreas Fabri crée GeometryFactory, au départ une startup soutenue par Inria, chargée de la distribution de l’outil, de sa maintenance et du support à ses utilisateurs.

En quoi cette bibliothèque est-elle remarquable ? « Assurer le transfert d’un algorithme issu de travaux théoriques au sein d’un outil informatique est un véritable défi, car un ordinateur manipule des nombres à la précision finie… L’une des spécificités de CGAL, et des raisons de son succès, est d’intégrer des méthodes numériques avancées permettant d’opérer des algorithmes avec la précision d’un ordinateur parfait ! ». Pierre Alliez, responsable de l’équipe-projet Titane - Centre Inria d'Université Côte d'Azur

La force d’un collectif

« Les résultats sont continus : chaque nouvelle version apporte son lot de fonctionnalités aux utilisateurs, dont le nombre ne cesse de croitre, dans le monde académique comme industriel. Beaucoup d’acteurs industriels préfèrent rester discrets sur leurs usages de CGAL : c’est un peu frustrant, car nous aimerions communiquer sur ces réussites… mais cela témoigne surtout du caractère stratégique de cet outil, qui répond à des demandes multiples, éclaire Monique Teillaud. Le projet nous est envié par de nombreuses communautés scientifiques : je suis par exemple invitée pour partager le retour d’expérience de CGAL devant la communauté du dessin de graphes qui aimerait s’engager dans une voie similaire… »

La réussite du projet tient sans doute à la qualité et la complémentarité des compétences engagées dans la durée, autour du développement et du transfert du logiciel. Mathématiques, algorithmique, programmation, ingénierie, etc. : aucun des membres du projet ne possède individuellement toutes les connaissances requises, et c’est la force du collectif.

L’avenir de CGAL ? « Les enjeux de recherche, qu’ils soient théoriques ou plus appliqués, ne manquent pas » assure Monique Teillaud. Ils seront l’occasion pour de jeunes scientifiques de conduire des travaux intéressants – d’autant qu’Inria est l’un des rares endroits au monde où la production logicielle est reconnue et évaluée en tant que travail de recherche… ». Alors, qui est partant pour renouveler l’équipe et prolonger l’aventure CGAL ?