CGAL（Computational Geometry Algorithms Library）是一个功能强大的开源C++库，旨在提供高效、可靠的几何算法。它在全球范围内拥有广泛的用户群体，GitHub上的Star数量超过5.6K，体现了其在计算几何领域的重要地位和活跃的社区支持。无论是学术研究还是工业应用，CGAL都提供了从二维到三维、从基础到高级的全面几何解决方案。

🔍 CGAL概览

CGAL提供了丰富的数据结构和算法，覆盖了计算几何的多个领域，包括三角剖分、Voronoi图、布尔运算、点云处理、网格生成等。其设计哲学是将几何与计算分离，使得算法不依赖于具体的数值类型，从而保证了代码的通用性和鲁棒性。

1.1 核心特性

CGAL的核心特性包括：

• 丰富的几何数据结构和算法：包括三角剖分、凸包、多边形网格处理、曲面和体积网格生成等。

• 高精度和鲁棒性：通过精确谓词和精确构造技术，避免了几何计算中的数值不稳定性问题。

• 灵活的架构设计：采用模板和概念编程，允许用户自定义几何内核和数据结构。

• 多领域应用支持：涵盖计算机图形学、CAD/CAM、GIS、机器人、计算机视觉等多个领域。

• 开源许可：采用双许可模式（GPL v3+和商业许可），既适合学术研究，也适合商业应用。

1.2 模块化架构

CGAL采用模块化设计，主要模块包括：

• 基础内核：提供点、向量、直线、平面等基本几何对象及其操作。

• 三角剖分与Voronoi图：包括二维和三维的Delaunay三角剖分、规则三角剖分等。

• 多边形网格处理：提供多边形网格的读写、简化、细分、修复等功能。

• 布尔运算：支持多边形和多面体的并、交、差等布尔操作。

• 点云处理：包括点云滤波、重建、曲面拟合等算法。

• 网格生成：提供二维和三维的曲面和体积网格生成功能。

🛠️ 核心功能详解

2.1 三角剖分与Voronoi图

三角剖分是计算几何的基础，CGAL提供了全面的三角剖分功能：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/point_generators_3.h>
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using DT3 = CGAL::Delaunay_triangulation_3<K>;
int main()
{
    // 创建3D点生成器
    CGAL::Random_points_in_cube_3<K::Point_3> randp(2.0);
    // 创建Delaunay三角剖分
    DT3 delaunay;
    // 插入随机点
    for (int i = 0; i < 100; ++i) {
        delaunay.insert(*randp++);
    }
    // 输出统计信息
    std::cout << "Number of vertices: " << delaunay.number_of_vertices() << std::endl;
    std::cout << "Number of finite cells: " << delaunay.number_of_finite_cells() << std::endl;
    return 0;
}

此代码演示了如何在三维空间中创建Delaunay三角剖分，这是许多几何算法的基础。

2.2 多边形网格处理

CGAL的多边形网格处理模块提供了丰富的网格操作功能：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/stitch_borders.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
namespace PMP = CGAL::Polygon_mesh_processing;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
int main()
{
    Mesh mesh;
    // 读取网格文件
    if (!PMP::IO::read_polygon_mesh("input.off", mesh)) {
        std::cerr << "Failed to read mesh file" << std::endl;
        return 1;
    }
    std::cout << "Before stitching:" << std::endl;
    std::cout << "Vertices: " << mesh.number_of_vertices() << std::endl;
    std::cout << "Edges: " << mesh.number_of_edges() << std::endl;
    std::cout << "Faces: " << mesh.number_of_faces() << std::endl;
    // 缝合边界
    PMP::stitch_borders(mesh);
    std::cout << "After stitching:" << std::endl;
    std::cout << "Vertices: " << mesh.number_of_vertices() << std::endl;
    std::cout << "Edges: " << mesh.number_of_edges() << std::endl;
    std::cout << "Faces: " << mesh.number_of_faces() << std::endl;
    // 保存处理后的网格
    CGAL::IO::write_polygon_mesh("output.off", mesh);
    return 0;
}

此示例展示了网格边界缝合功能，该功能能够识别并连接网格中重复的顶点，从而修复不完整的网格结构。

2.3 布尔运算

CGAL支持对三维实体进行布尔运算：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
namespace PMP = CGAL::Polygon_mesh_processing;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
int main()
{
    // 创建两个相交的立方体网格
    Mesh mesh1, mesh2;
    // 此处省略网格创建代码...
    // 执行布尔并集运算
    Mesh result;
    bool success = PMP::corefine_and_compute_union(mesh1, mesh2, result);
    if (success) {
        std::cout << "Boolean union operation succeeded" << std::endl;
        std::cout << "Result mesh has " << result.number_of_vertices() << " vertices" << std::endl;
        CGAL::IO::write_polygon_mesh("union_result.off", result);
    } else {
        std::cerr << "Boolean union operation failed" << std::endl;
    }
    return 0;
}

布尔运算在CAD/CAM系统中极为重要，可以用于组合简单几何体构建复杂模型。

2.4 网格分割

CGAL提供了基于形状直径函数的网格分割算法：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/mesh_segmentation.h>
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef boost::graph_traits<Mesh>::face_descriptor face_descriptor;
int main()
{
    Mesh mesh;
    // 读取网格
    std::ifstream input("data/cactus.off");
    input >> mesh;
    // 创建SDF属性映射
    typedef Mesh::Property_map<face_descriptor, double> Facet_double_map;
    Facet_double_map sdf_property_map = mesh.add_property_map<face_descriptor, double>("f:sdf").first;
    // 计算形状直径函数值
    CGAL::sdf_values(mesh, sdf_property_map);
    // 创建分割ID属性映射
    typedef Mesh::Property_map<face_descriptor, std::size_t> Facet_int_map;
    Facet_int_map segment_property_map = mesh.add_property_map<face_descriptor, std::size_t>("f:sid").first;
    // 执行网格分割
    std::size_t number_of_segments = CGAL::segmentation_from_sdf_values(mesh, sdf_property_map, segment_property_map);
    std::cout << "Number of segments: " << number_of_segments << std::endl;
    // 输出每个面的分割ID
    for(face_descriptor f : faces(mesh)) {
        std::cout << segment_property_map[f] << " ";
    }
    std::cout << std::endl;
    return EXIT_SUCCESS;
}

网格分割算法能够将复杂的网格模型分解为有意义的部件，在计算机动画和几何建模中非常有用。

📊 应用场景

3.1 计算机图形学与CAD/CAM

在计算机图形学中，CGAL用于：

• 三维建模和实体构造

• 网格处理和质量优化

• 碰撞检测和物理模拟

• 参数化与纹理映射

CAD/CAM系统利用CGAL进行：

• 工程图纸的布尔运算

• 曲面重建和修复

• 公差分析与检测

3.2 地理信息系统

GIS应用受益于CGAL的：

• 地图叠加与空间分析

• 地形建模与可视化

• 路径规划与空间查询

3.3 科学计算与医学成像

在科学和医学领域，CGAL用于：

• 有限元网格生成

• 分子表面和体积计算

• 医学影像的三维重建

• 计算流体动力学网格生成

💻 实战示例：创建带孔洞的曲面网格

以下示例演示如何使用CGAL创建复杂的带孔洞曲面网格：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/remesh.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
namespace PMP = CGAL::Polygon_mesh_processing;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
// 创建简单的平面网格并添加孔洞
Mesh create_plane_with_holes(double width, double height, int subdivisions)
{
    Mesh mesh;
    // 创建顶点
    std::vector<vertex_descriptor> vertices;
    double step_x = width / subdivisions;
    double step_y = height / subdivisions;
    for (int i = 0; i <= subdivisions; ++i) {
        for (int j = 0; j <= subdivisions; ++j) {
            double x = j * step_x - width / 2.0;
            double y = i * step_y - height / 2.0;
            vertices.push_back(mesh.add_vertex(K::Point_3(x, y, 0.0)));
        }
    }
    // 创建面（除了中心区域）
    int hole_start = subdivisions / 3;
    int hole_end = 2 * subdivisions / 3;
    for (int i = 0; i < subdivisions; ++i) {
        for (int j = 0; j < subdivisions; ++j) {
            // 跳过中心区域以创建孔洞
            if (i >= hole_start && i < hole_end && 
                j >= hole_start && j < hole_end) {
                continue;
            }
            int v1 = i * (subdivisions + 1) + j;
            int v2 = v1 + 1;
            int v3 = (i + 1) * (subdivisions + 1) + j + 1;
            int v4 = (i + 1) * (subdivisions + 1) + j;
            mesh.add_face(vertices[v1], vertices[v2], vertices[v3]);
            mesh.add_face(vertices[v1], vertices[v3], vertices[v4]);
        }
    }
    return mesh;
}
int main()
{
    // 创建带孔洞的网格
    Mesh mesh = create_plane_with_holes(10.0, 10.0, 20);
    std::cout << "Original mesh: " << std::endl;
    std::cout << "Vertices: " << mesh.number_of_vertices() << std::endl;
    std::cout << "Faces: " << mesh.number_of_faces() << std::endl;
    // 三角化所有面
    PMP::triangulate_faces(mesh);
    std::cout << "After triangulation: " << std::endl;
    std::cout << "Faces: " << mesh.number_of_faces() << std::endl;
    // 保存结果
    CGAL::IO::write_polygon_mesh("plane_with_holes.off", mesh);