CGAL : La bibliothèque logicielle open source CGAL fait entrer la recherche en géométrie algorithmique dans l’industrie
11 octobre 2023
Fruit de près de 30 ans de développement, dans lequel des équipes Inria se sont largement impliquées, la bibliothèque CGAL (Computational Geometry Algorithms Library) intègre les dernières innovations de la recherche en géométrie algorithmique. Plébiscité par des utilisateurs du monde entier, le projet vient en outre de recevoir un prix scientifique : une reconnaissance méritée pour une communauté tout entière.
Lire l’article source sur Inria.fr
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 ?
Une formidable aventure scientifique et entrepreneuriale
« J’ai la chance d’avoir contribué au projet CGAL depuis ses origines, au milieu des années 1990, période pendant laquelle nous avons réalisé les choix techniques structurants pour le développement du logiciel. À la fin des premiers projets européens qui ont lancé ces travaux, il devenait vital pour les partenaires de s’assurer de la pérennité de CGAL : la solution a été de créer une entreprise en charge de la maintenance évolutive et du support du logiciel.
Encouragé par Jean-Daniel Boissonnat, soutenu par Inria pendant deux ans, je me suis lancé dans l’aventure entrepreneuriale. Une idée séduisante… qui demande aussi de la persévérance : nous avons, par exemple, mis près de 10 ans à convaincre deux éditeurs de logiciels français de s’intéresser à CGAL, mais notre patience a fini par payer ! Une réussite pour l’entreprise est d’avoir établi des rapports de long terme avec une clientèle internationale, aux activités variées (systèmes d’informations géographiques, robotique, planification de chirurgie, impression 3D, pétrole, circuits intégrés, etc.).
Avec CGAL, nos clients apprécient de disposer d’un logiciel de qualité industrielle. En tant que gérant, je suis particulièrement fier de travailler avec des collaborateurs qui partagent les mêmes idées et valeurs, et qui ont les mêmes objectifs. L’innovation est collective : c’est particulièrement vrai pour GeometryFactory, qui cherche en permanence les innovations issues de publications scientifiques, pour les industrialiser et les proposer à ses clients… ».
Andreas Fabri (GeometryFactory)
En savoir plus
- Site web de CGAL
- La bibliothèque logicielle CGAL, présentation de Sylvain Pion (vidéo), Collège de France, 26/4/2017.
- Ressources CGAL
- SGP 2020 Graduate School: Geometric Computing with CGAL par Andreas Fabri (vidéo en anglais), GeometryFactory, 20/7/2020.