CGAL: The Open Source Computational Geometry Algorithms Library

Google Tech Talks
March, 3 2008

ABSTRACT

Introduction
Project mission statement, history, internal organization, partners, CGAL in numbers.

What's in CGAL
A survey on available data structures and algorithms, as well as examples how and by whom they are used. Topics include Triangulations, Voronoi diagrams, Boolean operations on polygons and polyhedra, arrangements of curves and their applications, Mesh generation, Geometry processing, Alpha shapes, Convex hull algorithms, Operations on polygons, Search structures, Interpolation, Shape analysis, fitting, and distances, Kinetic data structures...

Generic Programming Paradigm
CGAL data structures are C++ template classes and functions, usually taking several template parameters (with default values for ease of use). This gives developers an incredible flexibility to adapt the data structures to their needs, which is important internally for code reuse, and important for end users, as they typically integrate CGAL in already existing applications. Parts of CGAL are also interfaced with languages and software like Python, Java, Scilab, Qt and the Ipe drawing editor.

Exact Geometric Computing Paradigm
We present how to make geometric algorithms correct, robust, and nevertheless fast, by combining floating point arithmetic with exact arithmetic, and clever filtering mechanisms to switch between these two modes. These mechanisms can be used for geometric predicates, as well as for geometric constructions, which instead of a discrete return value generate new geometric entities.

Conclusion and Outlook
A wrapup, and a sneak preview on algorithms that might make it into future releases of CGAL.

Speaker: Andreas Fabri, PhD, GeometryFactory
As member of the initial development team of the CGAL project, Andreas is one of the architects of the CGAL software. For several years he chaired the CGAL Editorial Board. In 2003, Andreas founded the GeometryFactory as spin-off of the CGAL project, offering licenses, service and support to commercial users. Andreas received his PhD in 1994 from the Ecole des Mines de Paris, while working on geometric algorithms for parallel machines at INRIA.


Speaker: Sylvain Pion, PhD, INRIA Sophia-Antipolis
Sylvain got involved in the CGAL project during his PhD, which he received in 1999 at INRIA. He worked then on providing generic solutions to numerical robustness issues arising in geometric algorithms. Later on he worked on the efficiency of some fundamental geometric algorithms such as 3D Delaunay triangulations. He is now also involved in C++ standardization, and is working on parallel geometric algorithms. He is employed as researcher at INRIA, and is the current chair of the CGAL Editorial Board.

Category:

People & Blogs

Tags:

• google
• techtalks
• techtalk
• engedu
• talk
• talks
• googletechtalks
• education

[peterwilson69]

Ok... I'll be the first person in 5738 views/people to comment. I found CGAL confusing at first, so I really appreciate this video.

[OldAndCranky]

Excellent presentation. I'm taking a CG course right now, so the course material & CGAL are going together hand-in-hand very nicely. Thanks a lot.

[touristtam]

God the second talker is hard to follow. Nice presentation overall. I wished the presentation would actually present the algorythm that have been implemented and not what they do (I can look up that by myself).

[TerryAdam1993]

y reply to a 9 month old comment

[0121ryanh117]

@TerryAdam1993 youtube partners can upload any shit they want.

[Z3r0XoL]

08:40 i started to draw exactly those when i was 10, i had no idea it was in this math library stuff xD

also i did know there was more than one possible way, nice to see there are ways tha are named so i can draw them like that xD

[Z3r0XoL]

I think there are serveral reasons for why they cant do that.

[cyborgtroy]

They bought YouTube.

No, seriously, Google OWNS YouTube. They could replace all your videos with porn if they thought it would be funny.

[TerryAdam1993]

how did you get a hour long video?

[supergopi]

is this similar to mathematica??

but an open source one?