A first of its kind in the computational geometry community

Each year the “Symposium on Computational Geometry (SoCG)”, a prestigious international conference, presents an opportunity to pay tribute to some of its members. The Test of Time Award is awarded by the committee to an important article that has had a significant impact on both the community and the discipline.

But the 2023 edition of the SoCG, held in Dallas, saw the committee make an exception to this rule. On 15 June of this year Monique Teillaud, Senior Researcher at the Inria Nancy Grand-Est centre with the Gamble project team (a joint undertaking with Loria) and Andreas Fabri, CEO of GeometryFactory, were presented with the famous award on behalf of the CGAL project for software development – something that had never happened before.

“Since its beginnings the best part of 30 years ago, CGAL has brought together a group of passionate scientists from Inria and other leading research institutes. We are proud that the community has chosen to recognise us in this way, underlining the quality of the work we have done together. This award gives us the feeling that we have really accomplished something”, says Monique Teillaud.

Dialogue between research and industrial transfer

This award brings to the fore just how important the discipline of computational geometry is. Despite being chiefly theoretical, it has attracted interest from whole sections of our economy. The world has grown increasingly digital and automated over the past twenty years. The design of many complex systems, for instance, is based on the large-scale use of digital simulation by engineers, and mass production of a whole host of objects would not be possible without automation. That is before we even get on to the digital technology that is central to everything from the most sophisticated instruments to the most basic mass market software.

“Computational geometry plays a really crucial role in the digital world in that it can be used to create mathematical representations of objects manipulated by many digital systems”, explains Pierre Alliez, leader of the Titane project-team at the Inria center at Université Côte d’Azur.

CGAL is a library (a collection of source code files, ready to use for computer programs) which features a set of computational geometry algorithms. It is used on a daily basis by engineers and researchers from the worlds of academia and industry for a wide range of applications. From three-dimensional surface meshes and topographical or geometric surveying, to working out trajectories and the positioning of antennae, the possibilities are endless. A number of public and private stakeholders have used this library for projects in fields such as urban modelling, architecture, astronomy, medical modelling and biophysics.

Widespread use of CGAL means there has been regular dialogue between the scientists behind it and its users. This has encouraged new ways of thinking and new research questions, in addition to helping new PhD subjects to emerge. Research and transfer feed off one another. One of the strengths of the project is that it has helped to promote proper dialogue. Problems in industry and academia create new questions for scientists to tackle, helping to drive forward research and, as a consequence, the CGAL library.

An active international community

Prior to the popularity it enjoys today, CGAL emerged in 1996 thanks to the visionary strategy of an international consortium. They believed that, in order to identify useful applications, research into computational geometry would need software that met the quality requirements familiar to the world of industry.

“30 years ago research into computational geometry was highly theoretical, with a lot of algorithms, theorems and proofs. There was some interest from industry in some of this research, but the algorithms were often too complicated to be used, and even when they were it was rarely robust. And so the CGAL collective was born. The aim was to focus on more practical aspects”, explains Monique Teillaud.

Two EU projects helped to get things off the ground, bringing together partners from Europe and Israel, and over time came more projects and sources of financing. The first version of the library was released in 1997, as CGAL took its first steps. Four years later, in 2001, the members of the project decided to set up an editorial committee.

“Within the committee we developed a set of rules and procedures for governing the project, coordinating the process for proofreading submissions. Those on the committee all shared the same goal of working in the interests of the project. We opted to take a collaborative approach to research”, says Monique Teillaud.

Their strategy paid off, as CGAL continued to burnish its reputation. In 2003 it became open-source with a dual licence (free and commercial), and the project took on new contributors. That same year Andreas Fabri launched GeometryFactory. Beginning life as a startup supported by Inria, it was tasked with distribution of the tool, in addition to maintenance and user support.

What is it that makes this library so special? “Taking an algorithm developed through theoretical research and putting it into an IT tool is a real challenge given that computers process numbers with finite precision. One of the things that sets CGAL apart, and one of the reasons for its success, is that it features advanced digital methods which can be used to execute algorithms with the precision of a perfect computer”. Pierre Alliez, leader of the Titane project-team – Inria center at Université Côte d’Azur.

The strength of a collective

“Results are continuous: each new version provides users with a range of features, and there are more and more users all the time, both in academia and in industry. A lot of industrial stakeholders choose not to disclose how they use CGAL, which is somewhat frustrating as we would like to be able to talk about these success stories. But this is testament to the strategic nature of this tool, which meets a wide range of needs”, says Monique Teillaud. “Many scientific communities are envious of our project: I have been invited to share feedback on CGAL with the graph drawing community, for example, which would like to try something similar.”

The project no doubt owes its success to the quality and the complementarity of the skillsets of the people working on it, linked to software development and transfer. From mathematics and algorithmics to programming and engineering, no one member of the project has all of the knowledge required, and that is the strength of the collective.

So, what does the future have in store for CGAL? “Whether theoretical or more applied, research challenges are not in short supply”, says Monique Teillaud. “This will give young scientists an opportunity to conduct interesting research – especially given that Inria is one of only a few places in the world where software production is recognised and assessed as research work.” So, who’s up for providing the CGAL project with some fresh blood and continuing the adventure?