CGAL — Computational Geometry Algorithms Library

Introduction

CGAL is an open-source C++ library that provides robust, efficient implementations of geometric algorithms. Used across academia and industry for meshing, shape reconstruction, geometry processing, and spatial indexing, it emphasizes exact computation to avoid floating-point failures.

What CGAL Does

• Computes Delaunay triangulations, Voronoi diagrams, and convex hulls in 2D and 3D
• Generates surface and volume meshes with quality guarantees for simulation workflows
• Processes point clouds with reconstruction, simplification, and normal estimation
• Performs Boolean operations on polygonal meshes (union, intersection, difference)
• Provides spatial search structures including kd-trees and range trees

Architecture Overview

CGAL is organized as a collection of packages, each implementing a family of geometric algorithms. It uses exact arithmetic kernels (via GMP/MPFR) to guarantee correct geometric predicates, avoiding robustness issues that plague floating-point geometry. A traits-based design lets users swap kernels for performance vs. exactness tradeoffs.

Self-Hosting & Configuration

• Install headers and link against CGAL, GMP, and MPFR libraries
• Available through apt, Homebrew, vcpkg, Conan, and conda-forge
• Header-only for many packages; only a few require compiled library components
• Choose between exact (Exact_predicates_exact_constructions_kernel) and fast (Exact_predicates_inexact_constructions_kernel) computation kernels
• Integrates with CMake via find_package(CGAL)

Key Features

• Exact geometric computation prevents robustness failures in degenerate cases
• Comprehensive coverage: triangulations, meshes, arrangements, Boolean ops, and more
• Industrial-grade mesh generation for FEM, CFD, and 3D printing applications
• Extensive point cloud processing for LiDAR and photogrammetry pipelines
• Active development with regular releases and long-term maintenance

Comparison with Similar Tools

• Boost.Geometry — Boost.Geometry covers basic 2D operations; CGAL provides deeper algorithms including 3D meshing and exact computation
• Open3D — Open3D focuses on 3D data visualization and learning; CGAL specializes in rigorous computational geometry
• libigl — libigl targets geometry processing research with Eigen integration; CGAL offers broader algorithm coverage with exactness guarantees
• VTK — VTK is a visualization toolkit; CGAL provides the underlying geometric computation that VTK can display

FAQ

Q: Why does CGAL use exact arithmetic? A: Floating-point errors can cause geometric predicates to return wrong results, leading to crashes or invalid output. Exact arithmetic eliminates this class of bugs.

Q: Is CGAL fast despite exact arithmetic? A: Yes. CGAL uses lazy evaluation and filtered kernels that fall back to exact arithmetic only when needed, keeping most computations fast.

Q: What license does CGAL use? A: CGAL uses a dual license: GPL for open-source projects and a commercial license for proprietary use.

Q: Can CGAL process large point clouds? A: Yes. CGAL's point cloud packages handle millions of points with spatial indexing and stream processing.

Sources

• https://github.com/CGAL/cgal
• https://doc.cgal.org/