<figure><img src="image_1.png" /></figure>

HAL
open science

# CGAL: The Computational Geometry Algorithms Library

Monique Teillaud

► To cite this version:

Monique Teillaud. CGAL: The Computational Geometry Algorithms Library. GD23 - 31st International Symposium on Graph Drawing and Network Visualization, Sep 2023, Palerme, Italy. hal-04241529

HAL Id: hal-04241529

https://inria.hal.science/hal-04241529

Submitted on 24 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# CGAL: The Computational Geometry Algorithms Library

Monique Teillaud

<figure><img src="image_2.png" /></figure>

## To cite this version:

Monique Teillaud. CGAL: The Computational Geometry Algorithms Library. GD23 - 31st International Symposium on Graph Drawing and Network Visualization, Sep 2023, Palerme, Italy. hal-04241529

HAL Id: hal-04241529

https://inria.hal.science/hal-04241529v1

Submitted on 24 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

The Computational Geometry Algorithms Library

<figure><img src="image_4.png" /></figure>

Monique Teillaud

<figure><img src="image_5.png" /></figure>

Loria

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

UNIVERSITÉ
DE LORRAINE
<figure><img src="image_4.png" /></figure>

The Computational Geometry Algorithms Library

<figure><img src="image_5.png" /></figure>

Monique Teillaud

01101100
01101111
01100101
01100101
01100001
01101100
01101111
01100101
01100101

1110000111
1110010111
1110010111
1110010111

1000101111
1000101111
1000101111
1000101111

Loria

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

UNIVERSITÉ
DE LORRAINE
Travel by train

plane: Paris → Palermo 0.43 T CO₂

train: Nancy → Palermo 0.08 T CO₂

https://www.goodplanet.org

<figure><img src="image_9.png" /></figure>
# Travel by train

plane: Paris → Palermo 0.43 T CO₂

train: Nancy → Palermo 0.08 T CO₂

https://www.goodplanet.org

<figure><img src="image_9.png" /></figure>
This talk
This talk
# This talk

## NOT

* a CGAL course

* an advertisement for CGAL
# This talk

## NOT

* a CGAL course

* an advertisement for CGAL
# This talk

## Ingredients to CGAL success

invitation email from PC chairs:

> "We hope that your invited talk would give us some insight in the famed CGAL project, its genesis, central deliberations scientifically and organizationally, and lessons learned over the years, with all the ups and downs regarding student code, quality considerations but also fruitful synergies."
# This talk

## Ingredients to CGAL success

invitation email from PC chairs:

> “We hope that your invited talk would give us some insight in the famed CGAL project, its genesis, central deliberations scientifically and organizationally, and lessons learned over the years, with all the ups and downs regarding student code, quality considerations but also fruitful synergies.”
Is CGAL successful ?
Is CGAL successful ?
Is CGAL successful ?

* several thousands of downloads for each release

* included in debian, macports, etc
Is CGAL successful ?

* several thousands of downloads for each release

* included in debian, macports, etc
# Is CGAL successful ?

## Projects using CGAL

* Art

* Architecture, Buildings Modeling, Urban Modeling

* Astronomy

* Computational Geometry and Geometric Computing

* Computer Graphics

* Computational Topology and Shape Matching

* Computer Vision, Image Processing, Photogrammetry

* Games, Virtual Worlds

* Geographic Information Systems

* Geology and Geophysics

* Geometry Processing

* Mathematics

* Medical Modeling and Biophysics

* Mesh Generation and Surface Reconstruction

* 2D and 3D Modelers

* Molecular Modeling

* Motion Planning

* Optimization

* Particle Physics, Materials, Nanostructures, Microstructures, Fluid Dynamics

* Peer-to-Peer Virtual Environment

* Sensor Networks
# Is CGAL successful ?

## Projects using CGAL

* Art

* Architecture, Buildings Modeling, Urban Modeling

* Astronomy

* Computational Geometry and Geometric Computing

* Computer Graphics

* Computational Topology and Shape Matching

* Computer Vision, Image Processing, Photogrammetry

* Games, Virtual Worlds

* Geographic Information Systems

* Geology and Geophysics

* Geometry Processing

* Mathematics

* Medical Modeling and Biophysics

* Mesh Generation and Surface Reconstruction

* 2D and 3D Modelers

* Molecular Modeling

* Motion Planning

* Optimization

* Particle Physics, Materials, Nanostructures, Microstructures, Fluid Dynamics

* Peer-to-Peer Virtual Environment

* Sensor Networks
# Is CGAL successful ?

## A few commercial users

<figure><img src="image_10.png" /></figure>
# Is CGAL successful ?

## A few commercial users

<figure><img src="image_10.png" /></figure>
# Is CGAL successful ?

## 39th International Computational Geometry Week

### Test of Time Award

presented at the 2023 Symposium on Computational Geometry to

### The CGAL Project

for

its profound impact on the SoCG community over many years

<figure><img src="image_11.png" /></figure>

Pankaj K. Agarwal
 committee chair
Is CGAL successful ?

**39th International Computational Geometry Week**

**Test of Time Award**

presented at the 2023 Symposium on Computational Geometry to

**The CGAL Project**

for

**its profound impact on the SoCG community over many years**

<figure><img src="image_11.png" /></figure>

Pankaj K. Agarwal
 committee chair
# Is CGAL successful ?

“Dear CGAL Editorial Board,

The SoCG ToT Award Committee has chosen the **CGAL project** as one of the recipients of the

**2023 SoCG Test of Time Award.**

In this case the Committee deliberately and **exceptionally overstepped its mandate** of honoring individual papers since it strongly believes that CGAL is a **contribution** to the **SoCG Community** whose **impact** as a whole has been and still is at least as **strong** and **profound** as that of any individual paper.

Congratulations to all of you for this well deserved **recognition**. ”

Pankaj Agarwal, Siu-Wing Cheng, Raimund Seidel, Emo Welzl
(SoCG ToT Award Committee)

<figure><img src="image_12.png" /></figure>
# Is CGAL successful ?

“Dear CGAL Editorial Board,

The SoCG ToT Award Committee has chosen the **CGAL project** as one of the recipients of the

**2023 SoCG Test of Time Award.**

In this case the Committee deliberately and **exceptionally overstepped its mandate** of honoring individual papers since it strongly believes that CGAL is a **contribution** to the **SoCG Community** whose **impact** as a whole has been and still is at least as **strong** and **profound** as that of any individual paper.

Congratulations to all of you for this well deserved **recognition**. ”

Pankaj Agarwal, Siu-Wing Cheng, Raimund Seidel, Emo Welzl
(SoCG ToT Award Committee)
# Is CGAL successful ?

“Dear CGAL Editorial Board, The CGAL ToT Award Committee has chosen the **CGAL project** as one of the recipients of the

**2023 SoCG Test of Time Award.**

grateful

In this case the Committee **deliberately** and **exceptionally** overstepped its mandate of honoring individual papers since it strongly believes that CGAL is a **contribution** to the **SoCG Community** and the **impact** as a whole has been and still is at least as **strong** and **profound** as that of any individual paper.

Congratulations to all of you for this well-deserved **recognition**. ”

proud

Pankaj Agarwal, Siu-Wing Cheng, Raimund Seidel, Emo Welzl
(SoCG ToT Award Committee)
# Is CGAL successful ?

“Dear CGAL Editorial Board, The CGAL ToT Award Committee has chosen the **CGAL project** as one of the recipients of the

**2023 SoCG Test of Time Award.**

grateful

In this case the Committee **deliberately and exceptionally overstepped its mandate** of honoring individual papers since it **strongly believes that CGAL is a contribution to the SoCG Community** and **its impact as a whole has been and still is at least as strong and profound as that of any individual paper.**

Congratulations to all of you for this well-deserved **recognition**. ”

proud

thrilled
honored

Pankaj Agarwal, Siu-Wing Cheng, Raimund Seidel, Emo Welzl
(SoCG ToT Award Committee)
Historical Context
Historical Context
An Assessment (90's)

Computational Geometry: mostly theoretical

Smart algorithms, often hard/impossible to implement

A few pieces of software here and there

Not stable

Code often lost when students leave
An Assessment (90's)

Computational Geometry: mostly theoretical

Smart algorithms, often hard/impossible to implement

A few pieces of software here and there

Not stable

Code often lost when students leave
# 1996 CG Impact Task Force Report

Nina Amenta

Tetsuo Asano

Gill Barequet

Marshall Bern

Jean-Daniel Boissonnat

John Canny

**Bernard Chazelle**

Ken Clarkson

David Dobkin

Bruce Donald

Scot Drysdale

Herbert Edelsbrunner

David Eppstein

A. Robin Forrest

Steve Fortune

Ken Goldberg

Michael Goodrich

Leonidas J. Guibas

Pat Hanrahan

Chris M. Hoffmann

Dan Huttenlocher

Hiroshi Imai

David Kirkpatrick

D.T. Lee

Kurt Mehlhorn

Victor Milenkovic

Joe Mitchell

Mark Overmars

Richard Pollack

Raimund Seidel

Micha Sharir

Jack Snoeyink

Godfried Toussaint

Seth Teller

Herb Voelcker

Emo Welzl

Chee Yap
1996 CG Impact Task Force Report

Nina Amenta

Tetsuo Asano

Gill Barequet

Marshall Bern

Jean-Daniel Boissonnat

John Canny

**Bernard Chazelle**

Ken Clarkson

David Dobkin

Bruce Donald

Scot Drysdale

Herbert Edelsbrunner

David Eppstein

A. Robin Forrest

Steve Fortune

Ken Goldberg

Michael Goodrich

Leonidas J. Guibas

Pat Hanrahan

Chris M. Hoffmann

Dan Huttenlocher

Hiroshi Imai

David Kirkpatrick

D.T. Lee

Kurt Mehlhorn

Victor Milenkovic

Joe Mitchell

Mark Overmars

Richard Pollack

Raimund Seidel

Micha Sharir

Jack Snoeyink

Godfried Toussaint

Seth Teller

Herb Voelcker

Emo Welzl

Chee Yap
1996 CG Impact Task Force Report

Among the key recommendations:

* Production and distribution of **usable (and useful) geometric codes**

* **Reward structure** for implementations in academia
1996 CG Impact Task Force Report

Among the key recommendations:

* Production and distribution of **usable (and useful) geometric codes**

* **Reward structure** for implementations in academia
Local software projects in Europe

<figure><img src="image_13.png" /></figure>

Universiteit
Utrecht

PlaGeo, SpaGeo

ETH zürich

XYZ GeoBench

max planck institut
informatik

LEDA

INRIA
SOPHIA-ANTIPOLIS

C++GAL
Local software projects in Europe

<figure><img src="image_12.png" /></figure>

Universiteit
Utrecht

PlaGeo, SpaGeo

ETH zürich

XYZ GeoBench

max planck institut
informatik

LEDA

INRIA
SOPHIA-ANTIPOLIS

C++GAL
Local software projects in Europe

<figure><img src="image_14.png" /></figure>

Universiteit
Utrecht

ETH zürich

max planck institut
informatik

INRIA
SOPHIA-ANTIPOLIS

PlaGeo, SpaGeo

XYZ GeoBench

LEDA

C++GAL

cigale (cicada)

Francis Avnaim

<figure><img src="image_15.png" /></figure>
Local software projects in Europe

<figure><img src="image_13.png" /></figure>

Universiteit
Utrecht

ETH zürich

max planck institut
informatik

INRIA
SOPHIA-ANTIPOLIS

PlaGeo, SpaGeo

XYZ GeoBench

LEDA

C++GAL

cigale (cicada)

Francis Avnaim

<figure><img src="image_14.png" /></figure>
A Strong Will to Gather Efforts
A Strong Will to Gather Efforts
# Initial Funding (FP4 ESPRIT Program)

## Consortium

<figure><img src="image_16.png" /></figure>

Universiteit
Utrecht

ETH zürich

<figure><img src="image_17.png" /></figure>

max planck institut
informatik

<figure><img src="image_18.png" /></figure>

RINRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_19.png" /></figure>

TEL AVIV
UNIVERSITY

Freie Universität Berlin

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

**Mark Overmars**

Peter Widmayer, Emo Welzl

**Kurt Mehlhorn**

**Jean-Daniel Boissonnat**

Dan Halperin

Helmut Alt

Stefan Näher

Sabine Stifter
Initial Funding (FP4 ESPRIT Program)

Consortium

<figure><img src="image_15.png" /></figure>

Universiteit
Utrecht

ETH zürich

max planck institut
informatik

<figure><img src="image_16.png" /></figure>

RINRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_17.png" /></figure>

TEL AVIV
UNIVERSITY

Freie Universität Berlin

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

Mark Overmars

Peter Widmayer, Emo Welzl

Kurt Mehlhorn

Jean-Daniel Boissonnat

Dan Halperin

Helmut Alt

Stefan Näher

Sabine Stifter
# Initial Funding (FP4 ESPRIT Program)

## Consortium

<figure><img src="image_22.png" /></figure>

Universiteit
Utrecht

ETH

zürich

<figure><img src="image_23.png" /></figure>

max planck institut
informatik

<figure><img src="image_24.png" /></figure>

RINRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_25.png" /></figure>

TEL AVIV
UNIVERSITY

Freie Universität

<figure><img src="image_26.png" /></figure>

Berlin

<figure><img src="image_27.png" /></figure>

JLU

JOHANNES KEPLER
UNIVERSITÄT LINZ

<figure><img src="image_28.png" /></figure>

CGAL: Oct **1996** (21 months)

GALIA: Nov 1998 (18 months)
# Initial Funding (FP4 ESPRIT Program)

## Consortium

<figure><img src="image_20.png" /></figure>

Universiteit
Utrecht

ETH

zürich

<figure><img src="image_21.png" /></figure>

max planck institut
informatik

<figure><img src="image_22.png" /></figure>

RINRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_23.png" /></figure>

TEL AVIV
UNIVERSITY

Freie Universität

<figure><img src="image_24.png" /></figure>

Berlin

<figure><img src="image_25.png" /></figure>

JLU

JOHANNES KEPLER
UNIVERSITÄT LINZ

<figure><img src="image_26.png" /></figure>

CGAL: Oct **1996** (21 months)

GALIA: Nov 1998 (18 months)
Promote the research in computational geometry

"make the large body of geometric algorithms developed in the field of CG available for industrial applications"

Mission Statement

CGAL EU Project Proposal, 1996

Create a reward structure for implementations
in academia
Promote the research in computational geometry

"make the large body of geometric algorithms developed in the field of CG available for industrial applications"

Mission Statement

CGAL EU Project Proposal, 1996

Create a reward structure for implementations
in academia
## Promote the research in computational geometry

*"make the large body of geometric algorithms developed in the field of CG available for industrial applications"*

Mission Statement

CGAL EU Project Proposal, 1996

## Create a reward structure for implementations

in academia

High quality

<figure><img src="image_29.png" /></figure>

* Robustness

* Tests

* Documentation

* Review

* etc
## Promote the research in computational geometry

*"make the large body of geometric algorithms developed in the field of CG available for industrial applications"*

Mission Statement

CGAL EU Project Proposal, 1996

## Create a reward structure for implementations

in academia

High quality

<figure><img src="image_27.png" /></figure>

* Robustness

* Tests

* Documentation

* Review

* etc
Technical choices
Technical choices
Pre-history

At a meeting at Utrecht University in January 1995,
Olivier Devillers, Andreas Fabri, Wolfgang Freiseisen,
Geert-Jan Giezeman, Mark Overmars, Stefan Schirra,
Otfried Schwarzkopf, and Sven Schönherr

discussed the foundations of the **CGAL** kernel.

Many design and software engineering issues were addressed, e.g.

* naming conventions,

* coupling of classes (flat versus deep class hierarchy),

* memory allocation,

* programming conventions,

* mutability of atomic objects, points and vectors,

* storing additional information,

* orthogonality of operations on the kernel objects,

* viewing non-constant-size objects like polygons as dynamic data structures (and hence not as part of the (innermost) kernel).

[ CGAL Manual ]
Pre-history

At a meeting at Utrecht University in January 1995,
Olivier Devillers, Andreas Fabri, Wolfgang Freiseisen,
Geert-Jan Giezeman, Mark Overmars, Stefan Schirra,
Otfried Schwarzkopf, and Sven Schönherr

discussed the foundations of the **CGAL** kernel.

Many design and software engineering issues were addressed, e.g.

* naming conventions,

* coupling of classes (flat versus deep class hierarchy),

* memory allocation,

* programming conventions,

* mutability of atomic objects, points and vectors,

* storing additional information,

* orthogonality of operations on the kernel objects,

* viewing non-constant-size objects like polygons as dynamic data structures (and hence not as part of the (innermost) kernel).

[ CGAL Manual ]
CGAL first generation dinosaurs

Andreas Fabri

Geert-Jan Giezeman

Lutz Kettner

Stefan Schirra

Sven Schönherr

<figure><img src="image_30.png" /></figure>

INRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_31.png" /></figure>

Universiteit
Utrecht

ETH zürich

<figure><img src="image_32.png" /></figure>

max planck institut
informatik

<figure><img src="image_33.png" /></figure>

Berlin
CGAL first generation dinosaurs

Andreas Fabri

Geert-Jan Giezeman

Lutz Kettner

Stefan Schirra

Sven Schönherr

<figure><img src="image_28.png" /></figure>

INRIA
SOPHIA-ANTIPOLIS

<figure><img src="image_29.png" /></figure>

Universiteit
Utrecht

ETH zürich

<figure><img src="image_30.png" /></figure>

max planck institut
informatik

<figure><img src="image_31.png" /></figure>

Berlin
Language

C++
Language

C++
Language

C++

Design

genericity/flexibility through **templates**

STL-like:

```cpp
template <class T>
void swap(T &a, T &b)
{
    T tmp = a; a = b; b = tmp;
}
```

[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000. ]
Language

C++

Design

genericity/flexibility through **templates**

STL-like:

```cpp
template <class T>
void swap(T &a, T &b)
{
    T tmp = a; a = b; b = tmp;
}
```

[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000. ]
## (Extendible) Kernel

* Constant-size objets

* Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]
## (Extendible) Kernel

* Constant-size objets

* Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]
# Structure

## (Extendible) Kernel

- Constant-size objets

- Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

## Basic Library

- Data Structures & Algorithms

- Triangulations, Arrangements, etc
# Structure

## (Extendible) Kernel

- Constant-size objets

- Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

## Basic Library

- Data Structures & Algorithms

- Triangulations, Arrangements, etc
# Structure

## (Extendible) Kernel

- Constant-size objets

- Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

## Basic Library

- Data Structures & Algorithms

- Triangulations, Arrangements, etc

## Support Library

- I/O, Visualization

→ rely on external tools
# Structure

## (Extendible) Kernel

- Constant-size objets

- Operations on them

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

## Basic Library

- Data Structures & Algorithms

- Triangulations, Arrangements, etc

## Support Library

- I/O, Visualization

→ rely on external tools
<figure><img src="image_34.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
{
    typedef typename Geom traits::Point_3 Point;

    Vertex handle insert(const Point& p) { ... }
}
```
<figure><img src="image_32.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
{
    typedef typename Geom traits::Point_3 Point;

    Vertex handle insert(const Point& p) { ... }
}
```
Structure

GeomTraits concept

<figure><img src="image_35.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
```

```cpp
{
    typedef typename Geom traits::Point_3 Point;

    Vertex_handle insert(const Point& p) { ... }
}
```

<figure><img src="image_36.png" /></figure>

is a **model**

```cpp
typedef CGAL::Exact predicates_inexact constructions_kernel K;
```
<figure><img src="image_33.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
{
    typedef typename Geom traits::Point_3 Point;

    Vertex handle insert(const Point& p) { ... }
}
```

<figure><img src="image_34.png" /></figure>

is a **model**

```cpp
typedef CGAL::Exact predicates_inexact constructions_kernel K;
```
<figure><img src="image_37.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
```

```cpp
{
    typedef typename Geom traits::Point_3 Point;

    Vertex_handle insert(const Point& p) { ... }
}
```

<figure><img src="image_38.png" /></figure>

is a **model**

```cpp
typedef CGAL::Exact predicates_inexact constructions_kernel K;
typedef CGAL::Delaunay triangulation_3<K> Delaunay;
```

```cpp
int main()
```

```cpp
{
    Delaunay T;
    p = Point(0,0,0);
    T.insert(p);
}
```
<figure><img src="image_35.png" /></figure>

```cpp
template < class Geom traits, class Tds = Default >
class Delaunay triangulation_3;
```

```cpp
{
    typedef typename Geom traits::Point_3 Point;

    Vertex handle insert(const Point& p) { ... }
}
```

<figure><img src="image_36.png" /></figure>

is a **model**

```cpp
typedef CGAL::Exact predicates_inexact constructions_kernel K;
typedef CGAL::Delaunay triangulation_3<K> Delaunay;
```

```cpp
int main()
```

```cpp
{
    Delaunay T;
    p = Point(0,0,0);
    T.insert(p);
}
```
<figure><img src="image_39.png" /><figcaption>Remco Veltkamp</figcaption></figure>

<figure><img src="image_40.png" /></figure>

[ CGAL Manual ]
<figure><img src="image_37.png" /><figcaption>Remco Veltkamp</figcaption></figure>

<figure><img src="image_38.png" /></figure>

[ CGAL Manual ]
Editorial Board

(2001)
Editorial Board

(2001)
new package ≃ journal article

Quality

*"Reward structure for implementations in academia"*
new package ≃ journal article

Quality

*"Reward structure for implementations in academia"*
# Project Rules

* Responsibilities

Developer vs. Editor

Release / Review managers

* Voting rules

* Contribution process
# Project Rules

* Responsibilities

Developer vs. Editor

Release / Review managers

* Voting rules

* Contribution process
* Responsibilities

Developer vs. Editor

Release / Review managers

* Voting rules

* Contribution process

**A profitable investment**

prevent the same discussions from going on and on
* Responsibilities

Developer vs. Editor

Release / Review managers

* Voting rules

* Contribution process

**A profitable investment**

prevent the same discussions from going on and on
**Discusses** arising questions

Maintains the **website**

**Represents** the CGAL project

etc
**Discusses** arising questions

Maintains the **website**

**Represents** the CGAL project

etc
Current Members

Pierre Alliez

Guillaume Damiand

Andreas Fabri

Efi Fogel

Michael Hoffmann

Sébastien Loriot

Marc Pouget

Laurent Rineau

Monique Teillaud

<figure><img src="image_41.png" /></figure>

Sophia Antipolis

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

review manager

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

TELAVU
UNIVERSITY

ETH Zürich

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

Loria

<figure><img src="image_48.png" /></figure>

Nancy

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

Loria

<figure><img src="image_51.png" /></figure>

Nancy

release manager
Current Members

Pierre Alliez

Guillaume Damiand

Andreas Fabri

Efi Fogel

Michael Hoffmann

Sébastien Loriot

Marc Pouget

Laurent Rineau

Monique Teillaud

<figure><img src="image_39.png" /></figure>

Sophia Antipolis

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

review manager

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

TELAVU
UNIVERSITY

ETH Zürich

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

Loria

<figure><img src="image_46.png" /></figure>

Nancy

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

Loria

<figure><img src="image_49.png" /></figure>

Nancy

release manager
No Chairperson

Board Manager

* period of 6 months

* round-robin process
No Chairperson

Board Manager

* period of 6 months

* round-robin process
Infrastructure
Infrastructure
<figure><img src="image_52.png" /></figure>
<figure><img src="image_50.png" /></figure>
Submission / Review

<figure><img src="image_53.png" /></figure>
## Submission / Review

<figure><img src="image_51.png" /></figure>
Previously:

Home-made LaTeX tools

Nowadays:

Doxygen

+ Home-made scripts
Previously:

Home-made LaTeX tools

Nowadays:

Doxygen

+ Home-made scripts
Previously:

cvs then svn at INRIA

Nowadays:

github
Previously:

cvs then svn at INRIA

Nowadays:

github
Installation

Evolution = Simplification

initially: rough process

then cmake
Installation

Evolution = Simplification

initially: rough process

then cmake
Evolution = Simplification

initially: rough process

then cmake

nowadays easier than ever

* "Since CGAL version 5.0, CGAL is header-only by default, which means that there is no need to build CGAL before it can be used."
Evolution = Simplification

initially: rough process

then cmake

nowadays easier than ever

* "Since CGAL version 5.0, CGAL is header-only by default, which means that there is no need to build CGAL before it can be used."
install CGAL dependencies + Qt

brew install cgal

brew install qt5

download CGAL sources with examples and demos

https://github.com/CGAL/cgal/releases/CGAL-5.6.zip

set up environment variables

CGAL_DIR=/Users/teillaud/CGAL-5.6

Qt5_DIR=/opt/homebrew/Cellarqt@5/5.15.10_1/lib/cmake

compile demos

cd CGAL_DIR/demo/Your_favorite_package

mkdir build; cd build

cmake ..

make

run the demo(s)
* install CGAL dependencies + Qt

brew install cgal

brew install qt5

* download CGAL sources with examples and demos

https://github.com/CGAL/cgal/releases/CGAL-5.6.zip

* set up environment variables

CGAL_DIR=/Users/teillaud/CGAL-5.6

Qt5_DIR=/opt/homebrew/Cellarqt@5/5.15.10_1/lib/cmake

* compile demos

cd CGAL_DIR/demo/Your_favorite_package

mkdir build; cd build

cmake ..

make

* run the demo(s)
Open-Source Project
Open-Source Project
November, 2003 (Release 3.0)

Contributions welcome

Double licence

<figure><img src="image_54.png" /></figure>

suits the needs of most academic users

Commercial

for companies that sell their software
November, 2003 (Release 3.0)

Contributions welcome

Double licence

<figure><img src="image_52.png" /></figure>

suits the needs of most academic users

Commercial

for companies that sell their software
<figure><img src="image_55.png" /></figure>

January, 2003, INRIA startup

Andreas Fabri

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>
January, 2003, INRIA startup

Andreas Fabri

<figure><img src="image_53.png" /></figure>
January, 2003, INRIA startup

Andreas Fabri

<figure><img src="image_58.png" /></figure>

sells

commercial licenses

support

Ownership stays to the institutes/universities of authors
January, 2003, INRIA startup

Andreas Fabri

<figure><img src="image_54.png" /></figure>

sells

commercial licenses

support

Ownership stays to the institutes/universities of authors
Responsible for **long-term maintenance**

- C++ / compilers evolutions
- portability
- etc

Maintenance of **infrastructure**

- github
- wiki
- provider for the website
- testsuite
- documentation tools

releases
Responsible for **long-term maintenance**

- C++ / compilers evolutions
- portability
- etc

Maintenance of **infrastructure**

- github
- wiki
- provider for the website
- testsuite
- documentation tools

releases
<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

testsuite

<figure><img src="image_61.png" /></figure>
<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>

testsuite

<figure><img src="image_57.png" /></figure>
<figure><img src="image_62.png" /></figure>

Would the CGAL project have survived without GF...?

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>
Would the CGAL project have survived without GF...?

<figure><img src="image_58.png" /></figure>
<figure><img src="image_65.png" /></figure>

Andreas Fabri

Laurent Rineau

Sébastien Loriot

Jane Tournois

Mael Rouxel-Labbé

Sven Oesau

Rao Fu (PhD student in collaboration with INRIA)

<figure><img src="image_66.png" /></figure>
<figure><img src="image_59.png" /></figure>

Andreas Fabri

Laurent Rineau

Sébastien Loriot

Jane Tournois

Mael Rouxel-Labbé

Sven Oesau

Rao Fu (PhD student in collaboration with INRIA)

<figure><img src="image_60.png" /></figure>
<figure><img src="image_67.png" /></figure>

April fool jokes

2008: **The Large Hadron Collider Together With the CGAL Periodic Triangulations Prove the Existence of the Higgs Boson**

The downside of this breakthrough result is that the PhD student who worked on the periodic triangulations stopped working, telling everybody, that whatever he still finds out during his career is irrelevant, as he expects to get the Fields Medal in about 9, and the Nobel Prize for Physics in about 32 years.

*caught several (big) fishes!*

<figure><img src="image_68.png" /></figure>
<figure><img src="image_61.png" /></figure>

April fool jokes

2008: **The Large Hadron Collider Together With the CGAL Periodic Triangulations Prove the Existence of the Higgs Boson**

The downside of this breakthrough result is that the PhD student who worked on the periodic triangulations stopped working, telling everybody, that whatever he still finds out during his career is irrelevant, as he expects to get the Fields Medal in about 9, and the Nobel Prize for Physics in about 32 years.

caught several (big) fishes!

<figure><img src="image_62.png" /></figure>
<figure><img src="image_69.png" /></figure>

## April fool jokes

2008: **The Large Hadron Collider Together With the CGAL Periodic Triangulations Prove the Existence of the Higgs Boson**

The downside of this breakthrough result is that the PhD student who worked on the periodic triangulations stopped working, telling everybody, that whatever he still finds out during his career is irrelevant, as he expects to get the Fields Medal in about 9, and the Nobel Prize for Physics in about 32 years.

*caught several (big) fishes!*

2014: **Google Summer of Code project Google Grass**

The goal is to find out if a moderate consumption of cannabis makes software developers more creative and more productive.

<figure><img src="image_70.png" /></figure>
<figure><img src="image_63.png" /></figure>

April fool jokes

2008: **The Large Hadron Collider Together With the CGAL Periodic Triangulations Prove the Existence of the Higgs Boson**

The downside of this breakthrough result is that the PhD student who worked on the periodic triangulations stopped working, telling everybody, that whatever he still finds out during his career is irrelevant, as he expects to get the Fields Medal in about 9, and the Nobel Prize for Physics in about 32 years.

*caught several (big) fishes!*

2014: Google Summer of Code project **Google Grass**

The goal is to find out if a moderate consumption of cannabis makes software developers more creative and more productive.

<figure><img src="image_64.png" /></figure>
Research
Research
<figure><img src="image_71.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms
<figure><img src="image_65.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms
## Examples

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /><figcaption>Bounding Volumes</figcaption></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /><figcaption>Polyhedral Surface</figcaption></figure>

<figure><img src="image_77.png" /></figure>

<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /><figcaption>BooleanOperations</figcaption></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

Ínria

<figure><img src="image_82.png" /><figcaption>Triangulations</figcaption></figure>

<figure><img src="image_83.png" /><figcaption>Voronoi Diagrams</figcaption></figure>

<figure><img src="image_84.png" /></figure>

Ínria

<figure><img src="image_85.png" /><figcaption>Mesh Generation</figcaption></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /><figcaption>Subdivision</figcaption></figure>

<figure><img src="image_88.png" /><figcaption>Simplification</figcaption></figure>

<figure><img src="image_89.png" /><figcaption>Parameterization</figcaption></figure>

<figure><img src="image_90.png" /><figcaption>Streamlines</figcaption></figure>

<figure><img src="image_91.png" /><figcaption>Ridge Detection</figcaption></figure>

<figure><img src="image_92.png" /><figcaption>Neighbour Search</figcaption></figure>

<figure><img src="image_93.png" /><figcaption>Kinetic Data structures</figcaption></figure>

<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

TEL AVIU UNIVERSITY

<figure><img src="image_96.png" /><figcaption>Arrangement</figcaption></figure>

<figure><img src="image_97.png" /><figcaption>Intersection Detection</figcaption></figure>

<figure><img src="image_98.png" /><figcaption>Minkowski Sum</figcaption></figure>

<figure><img src="image_99.png" /><figcaption>PCA</figcaption></figure>

<figure><img src="image_100.png" /><figcaption>Polytope distance</figcaption></figure>

<figure><img src="image_101.png" /></figure>

ETH zürich

<caption>QP Solver</caption>
## Examples

<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /><figcaption>Bounding Volumes</figcaption></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /><figcaption>Polyhedral Surface</figcaption></figure>

<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /><figcaption>BooleanOperations</figcaption></figure>

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

Ínria

<figure><img src="image_76.png" /><figcaption>Triangulations</figcaption></figure>

<figure><img src="image_77.png" /><figcaption>Voronoi Diagrams</figcaption></figure>

<figure><img src="image_78.png" /></figure>

Ínria

<figure><img src="image_79.png" /><figcaption>Mesh Generation</figcaption></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /><figcaption>Subdivision</figcaption></figure>

<figure><img src="image_82.png" /><figcaption>Simplification</figcaption></figure>

<figure><img src="image_83.png" /><figcaption>Parameterization</figcaption></figure>

<figure><img src="image_84.png" /><figcaption>Streamlines</figcaption></figure>

<figure><img src="image_85.png" /><figcaption>Ridge Detection</figcaption></figure>

<figure><img src="image_86.png" /><figcaption>Neighbour Search</figcaption></figure>

<figure><img src="image_87.png" /><figcaption>Kinetic Data structures</figcaption></figure>

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>

TEL AIVU UNIVERSITY

<figure><img src="image_90.png" /><figcaption>Arrangement</figcaption></figure>

<figure><img src="image_91.png" /><figcaption>Intersection Detection</figcaption></figure>

<figure><img src="image_92.png" /><figcaption>Minkowski Sum</figcaption></figure>

<figure><img src="image_93.png" /><figcaption>PCA</figcaption></figure>

<figure><img src="image_94.png" /><figcaption>Polytope distance</figcaption></figure>

<figure><img src="image_95.png" /></figure>

ETH zürich

<caption>QP Solver</caption>
<figure><img src="image_102.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms
<figure><img src="image_96.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms
<figure><img src="image_103.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms

Helps researchers (in many fields)
<figure><img src="image_97.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms

Helps researchers (in many fields)
<figure><img src="image_104.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms

Helps researchers (in many fields)

Raises new research questions
<figure><img src="image_98.png" /></figure>

Result of research

Teams integrate their **favorite** algorithms

Helps researchers (in many fields)

Raises new research questions
[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000 ]

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]
[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000 ]

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]
[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000 ]

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

[ I. Emiris, A. Kakargias, S. Pion, M. Teillaud, and E. Tsigaridas. Towards an Open Curved Kernel. SoCG 2003 ]

[ P. de Castro, F. Cazals, S. Loriot, and M. Teillaud. Design of the CGAL 3D spherical kernel and application to arrangements of circles on a sphere. CGTA 2009 ]

etc

<figure><img src="image_105.png" /></figure>
[ A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Software: Practice and Experience 2000 ]

[ S. Hert, M. Hoffmann, L. Kettner, S. Pion, and M. Seel. An adaptable and extensible geometry kernel. Workshop on Algorithm Engineering, LNCS 2001 ]

[ I. Emiris, A. Kakargias, S. Pion, M. Teillaud, and E. Tsigaridas. Towards an Open Curved Kernel. SoCG 2003 ]

[ P. de Castro, F. Cazals, S. Loriot, and M. Teillaud. Design of the CGAL 3D spherical kernel and application to arrangements of circles on a sphere. CGTA 2009 ]

etc

<figure><img src="image_99.png" /></figure>
Implementation “Details”

“In theory, there is no difference between theory and practice.
In practice, there is.”
Implementation “Details”

“In theory, there is no difference between theory and practice.
In practice, there is.”
The real RAM model does not exist!
The real RAM model does not exist!
The real RAM model does not exist!

Exact Geometric Computation paradigm [Yap]

decisions from **exact predicates**

≠ **exact arithmetics**

Filtering
The real RAM model does not exist!

Exact Geometric Computation paradigm [Yap]

decisions from **exact predicates**

≠ **exact arithmetics**

Filtering
ex: **predicates** for Delaunay triangulations

<figure><img src="image_106.png" /></figure>

$$ \text{orient}(p, q, r) = \text{sign} \begin{vmatrix} 1 & 1 & 1 \\ p_x & q_x & r_x \\ p_y & q_y & r_y \end{vmatrix} $$

<figure><img src="image_107.png" /></figure>

$$ \text{in_disk}(p, q, r, s) = \text{sign} \begin{vmatrix} 1 & x_p & y_p & x_p^2 + y_p^2 \\ 1 & x_q & y_q & x_q^2 + y_q^2 \\ 1 & x_r & y_r & x_r^2 + y_r^2 \\ 1 & x_s & y_s & x_s^2 + y_s^2 \end{vmatrix} $$

center and radius are **not** computed

sign of polynomial expression
rational input points
ex: **predicates** for Delaunay triangulations

<figure><img src="image_100.png" /></figure>

$$ \text{orient}(p, q, r) = \text{sign} \begin{vmatrix} 1 & 1 & 1 \\ p_x & q_x & r_x \\ p_y & q_y & r_y \end{vmatrix} $$

<figure><img src="image_101.png" /></figure>

$$ \text{in_disk}(p, q, r, s) = \text{sign} \begin{vmatrix} 1 & x_p & y_p & x_p^2 + y_p^2 \\ 1 & x_q & y_q & x_q^2 + y_q^2 \\ 1 & x_r & y_r & x_r^2 + y_r^2 \\ 1 & x_s & y_s & x_s^2 + y_s^2 \end{vmatrix} $$

center and radius are **not** computed

sign of polynomial expression
rational input points
<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>
<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /></figure>
<figure><img src="image_110.png" /></figure>

<figure><img src="image_111.png" /></figure>

easy cases are more frequent

⇒ cost ≃ cost of approximate (double) computation
<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

easy cases are more frequent

⇒ cost ≃ cost of approximate (double) computation
[ L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, C-K. Yap
Classroom examples of robustness problems in geometric computations.
ESA 2004 - CGTA 2008 ]

[ C. Li, S. Pion, C-K. Yap
Recent progress in exact geometric computation.
Journal of Logic and Algebraic Programming 2005 ]

etc
[ L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, C-K. Yap
Classroom examples of robustness problems in geometric computations.
ESA 2004 - CGTA 2008 ]

[ C. Li, S. Pion, C-K. Yap
Recent progress in exact geometric computation.
Journal of Logic and Algebraic Programming 2005 ]

etc
Degenerate cases

“We will assume that no subset of $d + 2$ sites are cospherical or lie on a same hyperplane.”

Degenerate cases do exist!
Degenerate cases

“We will assume that no subset of $d + 2$ sites are cospherical or lie on a same hyperplane.”

Degenerate cases **do** exist!
Degenerate cases

"We will assume that no subset of $d + 2$ sites are cospherical or lie on a same hyperplane."

Degenerate cases do exist!

Removing a vertex in a 3D Delaunay triangulation
problem with co-circular points (in 3D)

symbolic perturbation
only perturbs the in_sphere predicate

[ O. Devillers and M. Teillaud.
Perturbations for Delaunay and weighted Delaunay 3D Triangulations.
SODA 2003 - CGTA 2011 ]
Degenerate cases

"We will assume that no subset of $d + 2$ sites are cospherical or lie on a same hyperplane."

Degenerate cases do exist!

Removing a vertex in a 3D Delaunay triangulation
problem with co-circular points (in 3D)

symbolic perturbation
only perturbs the in_sphere predicate

[ O. Devillers and M. Teillaud.
Perturbations for Delaunay and weighted Delaunay 3D Triangulations.
SODA 2003 - CGTA 2011 ]
# Efficiency

Algorithmic tricks

Olivier Devillers’ EuroCG’12 invited talk

https://members.loria.fr/Olivier.Devillers/EuroCG2012/
Algorithmic tricks

Olivier Devillers’ EuroCG’12 invited talk

https://members.loria.fr/Olivier.Devillers/EuroCG2012/
ex: 3D periodic triangulations, requested by astrophysicists

<figure><img src="image_112.png" /></figure>

ESA' 09

generalization: SoCG'11 + DCG'16

CGAL'09 package

+ CGAL'18 3D periodic mesh generation

PhD thesis [Manuel Caroli, 2011]

+ inspiration for further work...
ex: 3D periodic triangulations, requested by astrophysicists

<figure><img src="image_106.png" /></figure>

ESA' 09

generalization: SoCG'11 + DCG'16

CGAL'09 package

+ CGAL'18 3D periodic mesh generation

PhD thesis [Manuel Caroli, 2011]

+ inspiration for further work...
An issue (not specific to CGAL)

Evaluation of experimental work
in the CG community
An issue (not specific to CGAL)

Evaluation of experimental work
in the CG community
Evaluation of experimental work
in the CG community

*The article is well written. However, it only includes one theoretical result, albeit useful for applications. As a theoretical scientist I cannot accurately assess the importance and impact of the implemented algorithms on the field.*

Anonymous SoCG reviewer

<figure><img src="image_113.png" /></figure>
Evaluation of experimental work
in the CG community

*The article is well written. However, it only includes one theoretical result, albeit useful for applications. As a theoretical scientist I cannot accurately assess the importance and impact of the implemented algorithms on the field.*

Anonymous SoCG reviewer
Evaluation of experimental work
in the CG community

Confidence

1. No familiarity (I do not understand the results).

Paper summary and comments for authors

"This reviewer did not understand the actual result.
The paper studies flips of triangulations of surfaces.

[...]

It is unclear [...] why it should be interesting to a
general algorithms audience.

I think it's a clear rejection.”

Anonymous SODA reviewer
Evaluation of experimental work
in the CG community

Confidence

1. No familiarity (I do not understand the results).

Paper summary and comments for authors
“*This reviewer did not understand the actual result.*
*The paper studies flips of triangulations of surfaces.*

[...]

It is unclear [...] why it should be interesting to a
general algorithms audience.

I think it's a clear rejection.”

Anonymous SODA reviewer

<figure><img src="image_107.png" /></figure>
People
People
gather **many** skills:

- mathematics

- algorithms

- C++

- development tools

- organization / project management

- contacts with application fields

- etc
gather **many** skills:

- mathematics

- algorithms

- C++

- development tools

- organization / project management

- contacts with application fields

- etc
“Reward structure for implementations in academia”

## Past and Current Contributors

Dmitry Anisimov
Ken Arroyo Ohori
Dror Atariah
Alon Baram
Matthias Bäsken
Eric Berberich
Mikhail Bogdanov
David Bommes
Mario Botsch
Sylvain Brandel
Yves Brise
Hervé Brönnimann
Francisc Bungiu
Fernando Cacciola
Manuel Caroli
Pedro de Castro
Frédéric Cazals
Raphaëlle Chaine
Panagiotis Cheilaris
David Cohen-Steiner
Éric Colin de Verdière
Keenan Crane
Tran Kai Frank Da
Christophe Delage
Olivier Devillers
Katrin Dobrindt
Pavel Emeliyanenko
Ester Ezra
Kaspar Fischer
Eyal Flato

Julia Flötotto
Wolfgang Freiseisen
Ben Galehouse
Xiang Gao
Bernd Gärtner (former editor)
Geert-Jan Giezeman
Maxime Gimeno
Simon Giraudot
Marc Glisse
Nir Goren
Gaël Guennebaud
Philippe Guigue
Ankit Gupta
Peter Hachenberger
Iddo Hanniel
Idit Haran
Sariel Har-Peled
Michael Hemmer (former editor)
Ross Hemsley
Thomas Herrmann
Susan Hert (former editor)
Shai Hirsch
Thien Hoang
Kai Hormann
Samuel Hornus
Kan Huang
Iordan Iordanov
Clément Jamin
Menelaos Karavelas (former editor)
Konstantinos Katrioplas

Waqar Khan
Michael Kerber
Lutz Kettner (former editor)
Stephen Kiazyk
Michal Kleinbort
Alexander Kobel
Nico Kruithof
Sandeep Kumar Dey
Florent Lafarge
Sylvain Lazard
Eran Leiserowitz
Bruno Lévy
Sebastian Limbach
Eugene Lipovetsky
Naama Mayer
Abdelkrim Mebarki
Quentin Mérigot
Naceur Meskini
Andreas Meyer
Jocelyn Meyron
Michal Meyerovitch
Philipp Moeller
Sebastian Morr
Liangliang Nan
Oren Nechushtan
Gabriele Neyer
Sven Oesau
Steve Oudot
Markus Overtheil
Eli Packer

## Web page

Evanthia Papadopoulou
Frédéric Paradis
Dmitrii Pasechnik
Aymeric Pellé
Luis Peñaranda
Sylvain Pion (former editor)
Roza Pogalnikova
Asaf Porat
Sigal Raab
François Rebufat
Joachim Reichel
Mael Rouxel-Labbé
Daniel Russel
Niv Sabath
Laurent Saboret
Nader Salman
Oren Salzman
Stefan Schirra
Sven Schönherr
Michael Seel
Ophir Setter
Shahar Shamai
Le-Jeng Shiue
Weisheng Si
Daniel Sieger
Johannes Singler
Olga Sorkine-Hornung
Andrea Tagliasacchi
Hans Tangelder
Stéphane Tayeb

Remy Thomasse
Alexandru Tifrea
Jane Tournois
Quincy Tse
Alex Tsui
George Tzoumas
Radu Ursu
Carl Van Geem
Thijs Van Lankveld
Amir Vaxman
Christina Vaz
Remco Veltkamp (former editor)
Yannick Verdie
Aurélien Vialon
Ivo Vigan
Ron Wein (former editor)
Wieger Wesselink
Frans Wessendorp
Patrick Wenzlaff
Camille Wormser
Shihao Wu
Ning Xu
Yin Xu
Ilker O. Yaz
Mariette Yvinec (former editor)
Lingjie Zhu
Afra Zomorodian
Guy Zucker
Baruch Zukerman
Tali Zvi
“Reward structure for implementations in academia”

## Past and Current Contributors

Dmitry Anisimov
Ken Arroyo Ohori
Dror Atariah
Alon Baram
Matthias Bäsken
Eric Berberich
Mikhail Bogdanov
David Bommes
Mario Botsch
Sylvain Brandel
Yves Brise
Hervé Brönnimann
Francisc Bungiu
Fernando Cacciola
Manuel Caroli
Pedro de Castro
Frédéric Cazals
Raphaëlle Chaine
Panagiotis Cheilaris
David Cohen-Steiner
Éric Colin de Verdière
Keenan Crane
Tran Kai Frank Da
Christophe Delage
Olivier Devillers
Katrin Dobrindt
Pavel Emeliyanenko
Ester Ezra
Kaspar Fischer
Eyal Flato

Julia Flötotto
Wolfgang Freiseisen
Ben Galehouse
Xiang Gao
Bernd Gärtner (former editor)
Geert-Jan Giezeman
Maxime Gimeno
Simon Giraudot
Marc Glisse
Nir Goren
Gaël Guennebaud
Philippe Guigue
Ankit Gupta
Peter Hachenberger
Iddo Hanniel
Idit Haran
Sariel Har-Peled
Michael Hemmer (former editor)
Ross Hemsley
Thomas Herrmann
Susan Hert (former editor)
Shai Hirsch
Thien Hoang
Kai Hormann
Samuel Hornus
Kan Huang
Iordan Iordanov
Clément Jamin
Menelaos Karavelas (former editor)
Konstantinos Katrioplas

Waqar Khan
Michael Kerber
Lutz Kettner (former editor)
Stephen Kiazyk
Michal Kleinbort
Alexander Kobel
Nico Kruithof
Sandeep Kumar Dey
Florent Lafarge
Sylvain Lazard
Eran Leiserowitz
Bruno Lévy
Sebastian Limbach
Eugene Lipovetsky
Naama Mayer
Abdelkrim Mebarki
Quentin Mérigot
Naceur Meskini
Andreas Meyer
Jocelyn Meyron
Michal Meyerovitch
Philipp Moeller
Sebastian Morr
Liangliang Nan
Oren Nechushtan
Gabriele Neyer
Sven Oesau
Steve Oudot
Markus Overtheil
Eli Packer

## Web page

Evanthia Papadopoulou
Frédéric Paradis
Dmitrii Pasechnik
Aymeric Pellé
Luis Peñaranda
Sylvain Pion (former editor)
Roza Pogalnikova
Asaf Porat
Sigal Raab
François Rebufat
Joachim Reichel
Mael Rouxel-Labbé
Daniel Russel
Niv Sabath
Laurent Saboret
Nader Salman
Oren Salzman
Stefan Schirra
Sven Schönherr
Michael Seel
Ophir Setter
Shahar Shamai
Le-Jeng Shiue
Weisheng Si
Daniel Sieger
Johannes Singler
Olga Sorkine-Hornung
Andrea Tagliasacchi
Hans Tangelder
Stéphane Tayeb

Remy Thomasse
Alexandru Tifrea
Jane Tournois
Quincy Tse
Alex Tsui
George Tzoumas
Radu Ursu
Carl Van Geem
Thijs Van Lankveld
Amir Vaxman
Christina Vaz
Remco Veltkamp (former editor)
Yannick Verdie
Aurélien Vialon
Ivo Vigan
Ron Wein (former editor)
Wieger Wesselink
Frans Wessendorp
Patrick Wenzlaff
Camille Wormser
Shihao Wu
Ning Xu
Yin Xu
Ilker O. Yaz
Mariette Yvinec (former editor)
Lingjie Zhu
Afra Zomorodian
Guy Zucker
Baruch Zukerman
Tali Zvi
Package Authors

Manual

CGAL 5.0.1 - 3D Periodic Triangulations

CGAL 5.0.1 - 3D Periodic Triangulations

► User Manual

► Reference Manual

Refinement Relationships

Is Model Relationships

Has Model Relationships

Bibliography

► Class and Concept List

► Examples

User Manual

Authors

Manuel Caroli, Aymeric Pellé, Mael Rouxel-Labbé and Monique Teillaud

<figure><img src="image_114.png" /></figure>
Package Authors

Manual

CGAL 5.0.1 - 3D Periodic Triangulations

<figure><img src="image_108.png" /></figure>
"Reward structure for implementations in academia"

CGAL developers appreciated by

companies (Google, Intel, Apple, ...)

<figure><img src="image_115.png" /></figure>

<figure><img src="image_116.png" /></figure>

research institutes (INRIA, ETHZ, ...?)
"Reward structure for implementations in academia"

CGAL developers appreciated by

companies (Google, Intel, Apple, ...)

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>

research institutes (INRIA, ETHZ, ...?)
*"Reward structure for implementations in academia"*

Personal experience

Visibility **outside** computational geometry

*“Are you the Monique from CGAL?”*

My most cited paper: “Triangulations in CGAL”
*"Reward structure for implementations in academia"*

Personal experience

Visibility **outside** computational geometry

*“Are you the Monique from CGAL?”*

My most cited paper: “Triangulations in CGAL”
# Developer Meetings

1 or 2 / year

~ 10-20 participants = developers + guests

Discussions / decisions

<figure><img src="image_117.png" /></figure>

Dagstuhl, Sophia Antipolis, Zurich, Tel Aviv,
Nancy, Heraklion, Lyon, Paris, Utrecht
# Developer Meetings

1 or 2 / year

~ 10-20 participants = developers + guests

Discussions / decisions

<figure><img src="image_111.png" /></figure>

Dagstuhl, Sophia Antipolis, Zurich, Tel Aviv,
Nancy, Heraklion, Lyon, Paris, Utrecht
# Developer Meetings

1 or 2 / year

~ 10-20 participants = developers + guests

Discussions / decisions

## Integration

- technical help

- sense of belonging

<figure><img src="image_118.png" /></figure>

Dagstuhl, Sophia Antipolis, Zurich, Tel Aviv,
Nancy, Heraklion, Lyon, Paris, Utrecht
# Developer Meetings

1 or 2 / year

~ 10-20 participants = developers + guests

Discussions / decisions

Integration

technical help

sense of belonging

Dagstuhl, Sophia Antipolis, Zurich, Tel Aviv,
Nancy, Heraklion, Lyon, Paris, Utrecht

<figure><img src="image_112.png" /></figure>
pictures deleted

for HAL version

despair?

a bug?

a negative review?

playing Werewolves

in the wine cellar

in Dagstuhl
pictures deleted

for HAL version

despair?

a bug?

a negative review?

playing Werewolves

in the wine cellar

in Dagstuhl
<figure><img src="image_119.png" /></figure>

<figure><img src="image_120.png" /></figure>

pictures deleted
for HAL version
<figure><img src="image_113.png" /></figure>

<figure><img src="image_114.png" /></figure>

pictures deleted
for HAL version
48th developer meeting: 2023 April 24-28, Sophia Antipolis

picture deleted
for HAL version
48th developer meeting: 2023 April 24-28, Sophia Antipolis

picture deleted
for HAL version
# Ingredients - Summary

- Will + Goals

- Technical choices

- Project Management / Organization / Rules

- Infrastructure

- GeometryFactory

- Research

- People
# Ingredients - Summary

- Will + Goals

- Technical choices

- Project Management / Organization / Rules

- Infrastructure

- GeometryFactory

- Research

- People
Will + Goals

Technical choices

Project Management / Organization / Rules

Infrastructure

GeometryFactory

Research

People

THANK YOU
Will + Goals

Technical choices

Project Management / Organization / Rules

Infrastructure

GeometryFactory

Research

People

THANK YOU