相关章节: 半边数据结构

6.1 曲面网格

理论基础

半边数据结构（Halfedge Data Structure）

半边数据结构是CGAL网格表示的核心，它提供了一种高效表示和操作多边形网格的方法。

基本概念：

顶点（Vertex）：3D空间中的点
半边（Halfedge）：有向边，从源顶点指向目标顶点
边（Edge）：一对相反的半边
面（Face）：由半边环围成的多边形

连接关系：

每个半边知道：
- 源顶点（source vertex）
- 目标顶点（target vertex）
- 相反半边（opposite halfedge）
- 下一个半边（next halfedge in face）
- 前一个半边（previous halfedge in face）
- 关联的面（incident face）

优势：

常数时间导航：任意方向的遍历都是O(1)
内存高效：每个边只存储一次（作为两个半边）
灵活的面类型：支持任意多边形面

表面网格的数学定义

流形（Manifold）表面：

每个边恰好关联两个面（边界边除外）
每个顶点的邻域拓扑等价于圆盘
无自相交

欧拉示性数： $χ = V - E + F = 2 - 2 g - b$ 其中 $V$ =顶点数， $E$ =边数， $F$ =面数， $g$ =亏格， $b$ =边界分量数。

定向性：

可定向表面：每个面的顶点顺序一致（逆时针或顺时针）
不可定向表面：如莫比乌斯带（CGAL不支持）

架构分析

Surface_mesh vs Polyhedron_3

CGAL提供两种主要的表面网格表示：

特性	Surface_mesh	Polyhedron_3
设计目标	通用网格处理	经典半边结构
面类型	任意多边形	仅三角形或四边形
属性系统	内置属性系统	通过Items模板
内存布局	连续存储	基于指针
动态修改	高效	较慢
迭代器稳定性	添加/删除后失效	更稳定

Surface_mesh 实现

头文件位置：CGAL/Surface_mesh.h

#include <CGAL/Surface_mesh.h>
 
// Surface_mesh 的简化定义
template <class P >  // P = Point类型
class Surface_mesh {
public:
    typedef P                                       Point;
    typedef typename Kernel_traits<P>::Kernel       Kernel;
    
    // 索引类型（轻量级，可拷贝）
    typedef SM_Index<SM_Vertex_index>               Vertex_index;
    typedef SM_Index<SM_Halfedge_index>             Halfedge_index;
    typedef SM_Index<SM_Edge_index>                 Edge_index;
    typedef SM_Index<SM_Face_index>                 Face_index;
    
    // 属性类型
    template <class T>
    using Vertex_property = Property_map<Vertex_index, T>;
    template <class T>
    using Halfedge_property = Property_map<Halfedge_index, T>;
    template <class T>
    using Edge_property = Property_map<Edge_index, T>;
    template <class T>
    using Face_property = Property_map<Face_index, T>;
    
private:
    // 核心连接关系数组
    std::vector<Vertex_index>   halfedge_to_target_vertex_;   // 半边->目标顶点
    std::vector<Halfedge_index> halfedge_to_next_;            // 半边->下一个半边
    std::vector<Halfedge_index> halfedge_to_prev_;            // 半边->前一个半边
    std::vector<Face_index>     halfedge_to_face_;            // 半边->关联面
    std::vector<Halfedge_index> vertex_to_halfedge_;          // 顶点->出射半边
    std::vector<Halfedge_index> face_to_halfedge_;            // 面->起始半边
    std::vector<Halfedge_index> opposite_halfedge_;           // 半边->相反半边
    
    // 属性管理器
    Property_container<Vertex_index>   vertex_properties_;
    Property_container<Halfedge_index> halfedge_properties_;
    Property_container<Edge_index>     edge_properties_;
    Property_container<Face_index>     face_properties_;
    
    // 必需属性：顶点位置
    Vertex_property<Point> vpoint_;
    
    // 已删除元素标记（垃圾回收）
    std::vector<bool> removed_vertices_;
    std::vector<bool> removed_edges_;
    std::vector<bool> removed_faces_;
    
public:
    // 构造函数
    Surface_mesh() {
        vpoint_ = add_vertex_property<Point>("v:point");
    }
    
    // 元素添加
    Vertex_index add_vertex(const Point& p);
    Face_index add_face(const std::vector<Vertex_index>& vertices);
    
    // 元素删除（标记删除，需调用collect_garbage()真正删除）
    void remove_vertex(Vertex_index v);
    void remove_edge(Edge_index e);
    void remove_face(Face_index f);
    void collect_garbage();  // 清理已删除元素
    
    // 连接关系查询
    Halfedge_index halfedge(Edge_index e, unsigned int i) const;  // i=0或1
    Edge_index edge(Halfedge_index h) const;
    
    Vertex_index source(Halfedge_index h) const;
    Vertex_index target(Halfedge_index h) const;
    
    Halfedge_index next(Halfedge_index h) const;
    Halfedge_index prev(Halfedge_index h) const;
    Halfedge_index opposite(Halfedge_index h) const;
    
    Halfedge_index halfedge(Vertex_index v) const;  // 顶点的出射半边
    void set_halfedge(Vertex_index v, Halfedge_index h);
    
    Face_index face(Halfedge_index h) const;
    Halfedge_index halfedge(Face_index f) const;
    void set_halfedge(Face_index f, Halfedge_index h);
    
    // 遍历
    Halfedge_index halfedge_around_target(Halfedge_index h, int& i) const;
    
    // 范围查询
    bool is_valid() const;
    bool is_empty() const;
    
    size_t number_of_vertices() const;
    size_t number_of_edges() const;
    size_t number_of_halfedges() const;
    size_t number_of_faces() const;
    
    // 边界查询
    bool is_boundary(Vertex_index v) const;
    bool is_boundary(Halfedge_index h) const;
    bool is_boundary(Edge_index e) const;
    
    // 属性管理
    template <class T>
    Vertex_property<T> add_vertex_property(const std::string& name, 
                                            const T t = T());
    template <class T>
    Vertex_property<T> get_vertex_property(const std::string& name) const;
    template <class T>
    void remove_vertex_property(Vertex_property<T>& p);
    
    // 类似的halfedge/edge/face属性管理...
    
    // 点访问
    const Point& point(Vertex_index v) const { return vpoint_[v]; }
    void set_point(Vertex_index v, const Point& p) { vpoint_[v] = p; }
    Vertex_property<Point> points() const { return vpoint_; }
    
    // 迭代器
    class Vertex_iterator;
    class Halfedge_iterator;
    class Edge_iterator;
    class Face_iterator;
    
    Vertex_iterator vertices_begin() const;
    Vertex_iterator vertices_end() const;
    Halfedge_iterator halfedges_begin() const;
    Halfedge_iterator halfedges_end() const;
    Edge_iterator edges_begin() const;
    Edge_iterator edges_end() const;
    Face_iterator faces_begin() const;
    Face_iterator faces_end() const;
    
    // 清除
    void clear();
    void clear_without_removing_property_maps();
    
    // I/O
    bool read(const std::string& filename);
    bool write(const std::string& filename) const;
};

Polyhedron_3 实现

头文件位置：CGAL/Polyhedron_3.h

#include <CGAL/Polyhedron_3.h>
 
// Polyhedron_3 的简化定义
template <class Kernel_,
          class Items_ = Polyhedron_items_3,
          class HalfedgeDS_ = HalfedgeDS_default>
class Polyhedron_3 {
public:
    typedef Kernel_                               Kernel;
    typedef Items_                                Items;
    typedef HalfedgeDS_                           HalfedgeDS;
    
    // 类型定义
    typedef typename Kernel::Point_3              Point_3;
    typedef typename Kernel::Plane_3              Plane_3;
    
    // 组合类型（由Items定义）
    typedef typename Items::template Vertex_wrapper<HalfedgeDS>   Vertex;
    typedef typename Items::template Halfedge_wrapper<HalfedgeDS> Halfedge;
    typedef typename Items::template Face_wrapper<HalfedgeDS>     Facet;
    
    typedef typename HalfedgeDS::Vertex_handle    Vertex_handle;
    typedef typename HalfedgeDS::Halfedge_handle  Halfedge_handle;
    typedef typename HalfedgeDS::Facet_handle     Facet_handle;
    
    typedef typename HalfedgeDS::Vertex_iterator  Vertex_iterator;
    typedef typename HalfedgeDS::Halfedge_iterator Halfedge_iterator;
    typedef typename HalfedgeDS::Facet_iterator   Facet_iterator;
    typedef typename HalfedgeDS::Edge_iterator    Edge_iterator;
    
    typedef typename HalfedgeDS::Halfedge_around_vertex_circulator 
                                                  Halfedge_around_vertex_circulator;
    typedef typename HalfedgeDS::Halfedge_around_facet_circulator  
                                                  Halfedge_around_facet_circulator;
    
private:
    HalfedgeDS hds_;  // 半边数据结构
    
public:
    // 构造函数
    Polyhedron_3() {}
    
    template <class InputIterator>
    Polyhedron_3(InputIterator begin, InputIterator end) {
        // 从点范围构造
    }
    
    // 访问半边数据结构
    const HalfedgeDS& halfedge_ds() const { return hds_; }
    HalfedgeDS& halfedge_ds() { return hds_; }
    
    // 元素创建
    Vertex_handle make_vertex() { return hds_.vertices_push_back(Vertex()); }
    Halfedge_handle make_edge() { return hds_.edges_push_back(Halfedge(), Halfedge()); }
    Facet_handle make_facet() { return hds_.faces_push_back(Facet()); }
    
    // 高级构造
    Halfedge_handle create_center_vertex(Facet_handle f);
    Halfedge_handle erase_center_vertex(Halfedge_handle h);
    Halfedge_handle split_edge(Halfedge_handle h);
    Halfedge_handle join_edge(Halfedge_handle h);
    Halfedge_handle split_facet(Halfedge_handle h1, Halfedge_handle h2);
    Halfedge_handle join_facet(Halfedge_handle h);
    
    // 遍历
    Vertex_iterator vertices_begin() { return hds_.vertices_begin(); }
    Vertex_iterator vertices_end() { return hds_.vertices_end(); }
    Halfedge_iterator halfedges_begin() { return hds_.halfedges_begin(); }
    Halfedge_iterator halfedges_end() { return hds_.halfedges_end(); }
    Facet_iterator facets_begin() { return hds_.faces_begin(); }
    Facet_iterator facets_end() { return hds_.faces_end(); }
    Edge_iterator edges_begin() { return hds_.edges_begin(); }
    Edge_iterator edges_end() { return hds_.edges_end(); }
    
    // 计数
    size_t size_of_vertices() const { return hds_.size_of_vertices(); }
    size_t size_of_halfedges() const { return hds_.size_of_halfedges(); }
    size_t size_of_facets() const { return hds_.size_of_faces(); }
    
    // 容量
    void reserve(size_t nv, size_t ne, size_t nf);
    void clear() { hds_.clear(); }
    
    // 有效性检查
    bool is_valid(bool verbose = false, int level = 0) const;
    bool is_closed() const;
    bool is_pure_bivalent() const;
    bool is_pure_trivalent() const;
    bool is_pure_triangle() const;
    bool is_pure_quad() const;
    
    // 欧拉运算
    Halfedge_handle euler_add_edge_and_vertex(Halfedge_handle h);
    void euler_remove_edge_and_vertex(Halfedge_handle h);
    Halfedge_handle euler_add_center_vertex(Facet_handle f);
    void euler_remove_center_vertex(Halfedge_handle h);
    Halfedge_handle euler_add_edge_between_vertices(Halfedge_handle h1, 
                                                     Halfedge_handle h2);
    void euler_remove_edge(Halfedge_handle h);
    
    // 法向计算
    void compute_facet_normals();
    void compute_vertex_normals();
    
    // 边界框
    Bbox_3 bbox() const;
    
    // 平面拟合
    Plane_3 fit_plane_to_facet(Facet_handle f) const;
    
    // I/O
    bool read(const std::string& filename);
    bool write(const std::string& filename) const;
};
 
// 默认Items定义
template <class Refs>
struct Polyhedron_vertex : public HalfedgeDS_vertex_base<Refs> {
    typedef typename Refs::Point_3 Point_3;
    Point_3 point;
    // 可以添加其他属性：法向、颜色、纹理坐标等
};
 
template <class Refs>
struct Polyhedron_facet : public HalfedgeDS_face_base<Refs> {
    typedef typename Refs::Plane_3 Plane_3;
    Plane_3 plane;
    // 可以添加其他属性
};
 
template <class Refs>
struct Polyhedron_items_3 {
    template <class Refs2>
    struct Vertex_wrapper {
        typedef Polyhedron_vertex<Refs2> Vertex;
    };
    template <class Refs2>
    struct Halfedge_wrapper {
        typedef HalfedgeDS_halfedge_base<Refs2> Halfedge;
    };
    template <class Refs2>
    struct Face_wrapper {
        typedef Polyhedron_facet<Refs2> Facet;
    };
};

实现细节

属性系统实现

// Property_map 的简化定义
template <class Index, class T>
class Property_map {
public:
    typedef Index   key_type;
    typedef T       value_type;
    typedef T&      reference;
    
private:
    std::vector<T> data_;  // 属性值数组
    T default_value_;      // 默认值
    
public:
    Property_map() {}
    Property_map(size_t n, const T& default_value = T())
        : data_(n, default_value), default_value_(default_value) {}
    
    // 访问元素
    reference operator[](Index idx) {
        return data_[idx];
    }
    
    const T& operator[](Index idx) const {
        return data_[idx];
    }
    
    // 检查是否有效
    bool is_valid() const { return !data_.empty(); }
    
    // 调整大小
    void resize(size_t n) {
        size_t old_size = data_.size();
        data_.resize(n);
        for (size_t i = old_size; i < n; ++i) {
            data_[i] = default_value_;
        }
    }
    
    // 清除
    void clear() { data_.clear(); }
    
    // 范围
    size_t size() const { return data_.size(); }
};
 
// Property_container 管理多个属性映射
template <class Index>
class Property_container {
private:
    std::map<std::string, std::shared_ptr<void>> properties_;
    std::vector<std::string> names_;
    
public:
    template <class T>
    Property_map<Index, T> add(const std::string& name, const T& default_value = T()) {
        auto map = std::make_shared<Property_map<Index, T>>();
        properties_[name] = map;
        names_.push_back(name);
        return *map;
    }
    
    template <class T>
    Property_map<Index, T> get(const std::string& name) const {
        auto it = properties_.find(name);
        if (it != properties_.end()) {
            return *std::static_pointer_cast<Property_map<Index, T>>(it->second);
        }
        return Property_map<Index, T>();  // 返回无效映射
    }
    
    template <class T>
    void remove(Property_map<Index, T>& prop) {
        // 查找并移除
    }
    
    void resize(size_t n) {
        for (auto& pair : properties_) {
            // 调整所有属性映射的大小
        }
    }
};

网格修改操作

// Surface_mesh 的面添加实现
template <class P>
typename Surface_mesh<P>::Face_index 
Surface_mesh<P>::add_face(const std::vector<Vertex_index>& vertices) {
    const size_t n = vertices.size();
    if (n < 3) return Face_index();  // 无效面
    
    // 检查顶点有效性
    for (auto v : vertices) {
        if (!is_valid(v)) return Face_index();
    }
    
    // 创建半边
    std::vector<Halfedge_index> halfedges(n);
    for (size_t i = 0; i < n; ++i) {
        halfedges[i] = add_edge(vertices[i], vertices[(i+1)%n]);
        if (!halfedges[i].is_valid()) {
            // 回滚已创建的半边
            for (size_t j = 0; j < i; ++j) {
                remove_edge(edge(halfedges[j]));
            }
            return Face_index();
        }
    }
    
    // 设置半边连接关系
    for (size_t i = 0; i < n; ++i) {
        set_next(halfedges[i], halfedges[(i+1)%n]);
        set_prev(halfedges[(i+1)%n], halfedges[i]);
    }
    
    // 创建面
    Face_index f = new_face();
    set_halfedge(f, halfedges[0]);
    for (auto h : halfedges) {
        set_face(h, f);
    }
    
    return f;
}
 
// 边分割（Catmull-Clark细分的基础操作）
template <class P>
typename Surface_mesh<P>::Vertex_index 
Surface_mesh<P>::split_edge(Edge_index e, const Point& p) {
    Halfedge_index h0 = halfedge(e, 0);
    Halfedge_index h1 = halfedge(e, 1);
    
    Vertex_index v0 = source(h0);
    Vertex_index v1 = target(h0);
    
    // 创建新顶点
    Vertex_index vm = add_vertex(p);
    
    // 创建新边
    Halfedge_index h_new = add_edge(vm, v1);
    
    // 更新原半边
    halfedge_to_target_vertex_[h0] = vm;
    
    // 更新连接关系
    // ... 详细实现
    
    return vm;
}
 
// 面分割（三角化）
template <class P>
typename Surface_mesh<P>::Vertex_index 
Surface_mesh<P>::split_face(Face_index f, const Point& p) {
    // 获取面的所有顶点
    std::vector<Vertex_index> face_vertices;
    Halfedge_index h = halfedge(f);
    Halfedge_index start = h;
    do {
        face_vertices.push_back(target(h));
        h = next(h);
    } while (h != start);
    
    // 删除原面
    remove_face(f);
    
    // 创建中心顶点
    Vertex_index center = add_vertex(p);
    
    // 创建三角形扇
    for (size_t i = 0; i < face_vertices.size(); ++i) {
        add_triangle(center, face_vertices[i], face_vertices[(i+1)%face_vertices.size()]);
    }
    
    return center;
}

垃圾回收机制

// 垃圾回收实现
template <class P>
void Surface_mesh<P>::collect_garbage() {
    // 第一步：重新索引顶点
    std::vector<Vertex_index> vertex_old_to_new(number_of_vertices());
    size_t n_vertices = 0;
    
    for (size_t i = 0; i < removed_vertices_.size(); ++i) {
        if (!removed_vertices_[i]) {
            vertex_old_to_new[i] = Vertex_index(n_vertices++);
        }
    }
    
    // 压缩顶点数组
    std::vector<Point> new_points(n_vertices);
    for (size_t i = 0, j = 0; i < removed_vertices_.size(); ++i) {
        if (!removed_vertices_[i]) {
            new_points[j++] = vpoint_[Vertex_index(i)];
        }
    }
    vpoint_.data().swap(new_points);
    
    // 更新所有引用顶点的索引
    for (auto& target : halfedge_to_target_vertex_) {
        target = vertex_old_to_new[target];
    }
    
    // 类似处理半边和面...
    
    // 清除删除标记
    removed_vertices_.clear();
    removed_vertices_.resize(n_vertices, false);
    
    // 调整属性数组大小
    vertex_properties_.resize(n_vertices);
}

使用示例

示例1：Surface_mesh基本操作

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <iostream>
#include <vector>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Surface_mesh;
 
int main() {
    Surface_mesh mesh;
    
    // 添加顶点
    Surface_mesh::Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
    Surface_mesh::Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
    Surface_mesh::Vertex_index v2 = mesh.add_vertex(Point_3(1, 1, 0));
    Surface_mesh::Vertex_index v3 = mesh.add_vertex(Point_3(0, 1, 0));
    Surface_mesh::Vertex_index v4 = mesh.add_vertex(Point_3(0.5, 0.5, 1));
    
    std::cout << "Added " << mesh.number_of_vertices() << " vertices" << std::endl;
    
    // 添加面（底面）
    mesh.add_face(v0, v1, v2, v3);
    
    // 添加侧面（三角形）
    mesh.add_face(v0, v1, v4);
    mesh.add_face(v1, v2, v4);
    mesh.add_face(v2, v3, v4);
    mesh.add_face(v3, v0, v4);
    
    std::cout << "Mesh has " << mesh.number_of_faces() << " faces" << std::endl;
    std::cout << "Mesh has " << mesh.number_of_edges() << " edges" << std::endl;
    
    // 遍历顶点
    std::cout << "\nVertices:" << std::endl;
    for (Surface_mesh::Vertex_index v : mesh.vertices()) {
        std::cout << "  " << v << ": " << mesh.point(v) << std::endl;
    }
    
    // 遍历面
    std::cout << "\nFaces (vertex indices):" << std::endl;
    for (Surface_mesh::Face_index f : mesh.faces()) {
        std::cout << "  Face " << f << ": ";
        for (Surface_mesh::Vertex_index v : mesh.vertices_around_face(mesh.halfedge(f))) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    }
    
    // 边界查询
    std::cout << "\nBoundary edges:" << std::endl;
    for (Surface_mesh::Edge_index e : mesh.edges()) {
        if (mesh.is_boundary(e)) {
            std::cout << "  Edge " << e << std::endl;
        }
    }
    
    return 0;
}

示例2：属性系统使用

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point_3;
typedef K::Vector_3 Vector_3;
typedef CGAL::Surface_mesh<Point_3> Surface_mesh;
 
int main() {
    Surface_mesh mesh;
    
    // 创建简单网格（四面体）
    Surface_mesh::Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
    Surface_mesh::Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
    Surface_mesh::Vertex_index v2 = mesh.add_vertex(Point_3(0, 1, 0));
    Surface_mesh::Vertex_index v3 = mesh.add_vertex(Point_3(0, 0, 1));
    
    mesh.add_face(v0, v2, v1);
    mesh.add_face(v0, v1, v3);
    mesh.add_face(v0, v3, v2);
    mesh.add_face(v1, v2, v3);
    
    // 添加顶点法向属性
    Surface_mesh::Property_map<Surface_mesh::Vertex_index, Vector_3> normals =
        mesh.add_property_map<Surface_mesh::Vertex_index, Vector_3>("v:normal").first;
    
    // 计算顶点法向（简单平均）
    for (Surface_mesh::Vertex_index v : mesh.vertices()) {
        Vector_3 n(0, 0, 0);
        int count = 0;
        
        // 遍历相邻面
        for (Surface_mesh::Face_index f : mesh.faces_around_target(mesh.halfedge(v))) {
            if (f != Surface_mesh::null_face()) {
                // 计算面法向（简化）
                auto vertices = mesh.vertices_around_face(mesh.halfedge(f));
                auto it = vertices.begin();
                Point_3 p0 = mesh.point(*it++);
                Point_3 p1 = mesh.point(*it++);
                Point_3 p2 = mesh.point(*it);
                
                Vector_3 fn = CGAL::cross_product(p1 - p0, p2 - p0);
                n = n + fn;
                ++count;
            }
        }
        
        if (count > 0) {
            normals[v] = n / std::sqrt(n.squared_length());
        }
    }
    
    // 输出法向
    std::cout << "Vertex normals:" << std::endl;
    for (Surface_mesh::Vertex_index v : mesh.vertices()) {
        std::cout << "  " << v << ": " << normals[v] << std::endl;
    }
    
    // 添加面颜色属性
    Surface_mesh::Property_map<Surface_mesh::Face_index, CGAL::Color> colors =
        mesh.add_property_map<Surface_mesh::Face_index, CGAL::Color>("f:color").first;
    
    // 设置随机颜色
    for (Surface_mesh::Face_index f : mesh.faces()) {
        colors[f] = CGAL::Color(rand() % 256, rand() % 256, rand() % 256);
    }
    
    // 移除属性
    mesh.remove_property_map(colors);
    
    return 0;
}

示例3：网格修改与欧拉运算

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Surface_mesh;
 
// 创建立方体
void create_cube(Surface_mesh& mesh) {
    // 8个顶点
    Surface_mesh::Vertex_index v[8];
    v[0] = mesh.add_vertex(Point_3(0, 0, 0));
    v[1] = mesh.add_vertex(Point_3(1, 0, 0));
    v[2] = mesh.add_vertex(Point_3(1, 1, 0));
    v[3] = mesh.add_vertex(Point_3(0, 1, 0));
    v[4] = mesh.add_vertex(Point_3(0, 0, 1));
    v[5] = mesh.add_vertex(Point_3(1, 0, 1));
    v[6] = mesh.add_vertex(Point_3(1, 1, 1));
    v[7] = mesh.add_vertex(Point_3(0, 1, 1));
    
    // 6个面（每个面两个三角形）
    // 底面
    mesh.add_face(v[0], v[2], v[1]);
    mesh.add_face(v[0], v[3], v[2]);
    // 顶面
    mesh.add_face(v[4], v[5], v[6]);
    mesh.add_face(v[4], v[6], v[7]);
    // 前面
    mesh.add_face(v[0], v[1], v[5]);
    mesh.add_face(v[0], v[5], v[4]);
    // 后面
    mesh.add_face(v[2], v[3], v[7]);
    mesh.add_face(v[2], v[7], v[6]);
    // 左面
    mesh.add_face(v[0], v[4], v[7]);
    mesh.add_face(v[0], v[7], v[3]);
    // 右面
    mesh.add_face(v[1], v[2], v[6]);
    mesh.add_face(v[1], v[6], v[5]);
}
 
// 细分所有边（Catmull-Clark风格）
void subdivide_edges(Surface_mesh& mesh) {
    std::vector<std::pair<Surface_mesh::Edge_index, Point_3>> edge_points;
    
    // 收集所有边和其中点
    for (Surface_mesh::Edge_index e : mesh.edges()) {
        Point_3 p0 = mesh.point(mesh.source(mesh.halfedge(e, 0)));
        Point_3 p1 = mesh.point(mesh.target(mesh.halfedge(e, 0)));
        Point_3 mid = CGAL::midpoint(p0, p1);
        edge_points.push_back({e, mid});
    }
    
    // 分割边
    for (const auto& ep : edge_points) {
        mesh.split_edge(ep.first, ep.second);
    }
}
 
int main() {
    Surface_mesh mesh;
    create_cube(mesh);
    
    std::cout << "Original cube:" << 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;
    
    // 验证欧拉公式：V - E + F = 2（对于球面）
    int euler = mesh.number_of_vertices() - mesh.number_of_edges() + mesh.number_of_faces();
    std::cout << "  Euler characteristic: " << euler << std::endl;
    
    // 细分边
    subdivide_edges(mesh);
    
    std::cout << "\nAfter edge subdivision:" << 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;
    
    return 0;
}

复杂度分析

时间复杂度

操作	Surface_mesh	Polyhedron_3	说明
添加顶点	O(1)	O(1)	均摊
添加面	O(d)	O(d)	d为面的度数
删除顶点	O(1)*	O(d)	*标记删除
删除面	O(1)*	O(d)	*标记删除
垃圾回收	O(n)	-	Surface_mesh需要
遍历顶点	O(n)	O(n)	所有顶点
遍历邻域	O(d)	O(d)	d为度数
点定位	O(1)	O(1)	索引访问

空间复杂度

组件	Surface_mesh	Polyhedron_3
顶点	O(n)	O(n)
半边	O(e)	O(e)
面	O(f)	O(f)
属性	O(n)	O(n)
总空间	O(n+e+f)	O(n+e+f)

具体存储（每个元素）：

Surface_mesh顶点：位置（3×double）+ 出射半边索引
Surface_mesh半边：目标顶点 + 下一个/前一个/相反半边 + 关联面
Polyhedron_3顶点：位置 + 出射半边指针
Polyhedron_3半边：目标顶点 + 下一个/前一个/相反半边 + 关联面

性能比较

场景	推荐选择	理由
频繁动态修改	Surface_mesh	高效的添加/删除
静态网格	Polyhedron_3	更稳定的迭代器
需要自定义属性	Surface_mesh	内置属性系统
经典算法实现	Polyhedron_3	成熟的半边结构
大网格处理	Surface_mesh	更好的内存局部性

关键文件位置

文件路径	说明
`CGAL/Surface_mesh.h`	Surface_mesh 主头文件
`CGAL/Surface_mesh/Surface_mesh.h`	完整实现
`CGAL/Surface_mesh/Properties.h`	属性系统
`CGAL/Polyhedron_3.h`	Polyhedron_3 主头文件
`CGAL/HalfedgeDS/`	半边数据结构
`CGAL/HalfedgeDS_default.h`	默认HDS配置
`CGAL/Polyhedron_items_3.h`	默认Items定义
`CGAL/Polyhedron_traits_with_normals_3.h`	带法向的Traits
`CGAL/boost/graph/graph_traits_Surface_mesh.h`	BGL适配器
`CGAL/boost/graph/graph_traits_Polyhedron_3.h`	BGL适配器

Chunibyo

Explorer

6.1 曲面网格

6.1 曲面网格

理论基础

半边数据结构（Halfedge Data Structure）

表面网格的数学定义

架构分析

Surface_mesh vs Polyhedron_3

Surface_mesh 实现

Polyhedron_3 实现

实现细节

属性系统实现

网格修改操作

垃圾回收机制

使用示例

示例1：Surface_mesh基本操作

示例2：属性系统使用

示例3：网格修改与欧拉运算

复杂度分析

时间复杂度

空间复杂度

性能比较

关键文件位置

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

6.1 曲面网格

6.1 曲面网格 §

理论基础 §

半边数据结构（Halfedge Data Structure） §

表面网格的数学定义 §

架构分析 §

Surface_mesh vs Polyhedron_3 §

Surface_mesh 实现 §

Polyhedron_3 实现 §

实现细节 §

属性系统实现 §

网格修改操作 §

垃圾回收机制 §

使用示例 §

示例1：Surface_mesh基本操作 §

示例2：属性系统使用 §

示例3：网格修改与欧拉运算 §

复杂度分析 §

时间复杂度 §

空间复杂度 §

性能比较 §

关键文件位置 §

Graph View

Table of Contents

Backlinks

6.1 曲面网格

理论基础

半边数据结构（Halfedge Data Structure）

表面网格的数学定义

架构分析

Surface_mesh vs Polyhedron_3

Surface_mesh 实现

Polyhedron_3 实现

实现细节

属性系统实现

网格修改操作

垃圾回收机制

使用示例

示例1：Surface_mesh基本操作

示例2：属性系统使用

示例3：网格修改与欧拉运算

复杂度分析

时间复杂度

空间复杂度

性能比较

关键文件位置