Chunibyo

Search

SearchSearch

8.1 三维三角剖分基础 (Triangulation_3)

Apr 04, 2026, 11 min read

8.1 三维三角剖分基础 (Triangulation_3)

上一节: 7.1 二维三角化基础 下一节: 8.2 三维Delaunay三角剖分

8.1.1 数学理论基础

三维三角剖分的定义

三维三角剖分（3D Triangulation）是将三维空间中的点集分解为一系列四面体（tetrahedra）的集合，满足以下条件：

  1. 覆盖性：所有四面体的并集等于这些点的凸包
  2. 无重叠性：任意两个四面体的交集要么为空，要么为一个公共面、公共边或公共顶点
  3. 顶点一致性：四面体的顶点恰好是给定点集中的点

组合结构

三维三角剖分的组合结构可以用**胞腔复形（Cell Complex）**描述：

  • 0-胞腔（顶点）：给定的三维点
  • 1-胞腔（边）：连接两个顶点的线段
  • 2-胞腔（面）：由三个顶点构成的三角形
  • 3-胞腔（四面体）：由四个顶点构成的三维单形

拓扑关系

在三维三角剖分中，每个四面体包含：

  • 4个顶点（vertices）
  • 6条边（edges）
  • 4个三角形面（facets）

相邻四面体共享一个公共面（facet adjacency）。这种邻接关系构成了三角剖分的拓扑结构。

欧拉示性数

对于球面拓扑的三维三角剖分，欧拉公式为：

其中：

  • ：顶点数
  • ：边数
  • ：面数
  • ：四面体数

几何与组合的分离

CGAL的Triangulation_3采用几何与拓扑分离的设计哲学：

  • 三角剖分类（Triangulation_3）：管理组合结构（拓扑）
  • 几何特征类（Geometric Traits）：提供几何谓词和构造
  • 顶点/胞腔类（Vertex/Cell）：存储关联数据

这种分离允许用户自定义几何内核（精确计算或近似计算）而不影响组合算法。

8.1.2 架构分析

类层次结构

Triangulation_3<GT, Tds>
├── GT: Geometric Traits（几何特征）
│   ├── Point_3: 三维点类型
│   ├── Segment_3: 线段类型
│   ├── Tetrahedron_3: 四面体类型
│   └── 几何谓词（orientation, side_of_sphere等）
│
└── Tds: Triangulation Data Structure（三角剖分数据结构）
    ├── Triangulation_ds_vertex_base_3: 顶点基类
    ├── Triangulation_ds_cell_base_3: 胞腔基类
    └── 邻接关系存储

核心组件

1. 几何特征（Geometric Traits）

几何特征类定义了三角剖分所需的所有几何对象和运算：

typename GT::Point_3          // 三维点
typename GT::Segment_3        // 线段
typename GT::Triangle_3       // 三角形
typename GT::Tetrahedron_3    // 四面体
 
// 几何谓词
GT::orientation(p, q, r, s)   // 四点定向（判断s在pqr平面的哪一侧）
GT::side_of_sphere(p, q, r, s, t)  // 判断t是否在p,q,r,s的外接球内

2. 数据结构（TDS）

三角剖分数据结构存储组合信息：

  • 顶点（Vertex）：存储几何点、关联的入射胞腔
  • 胞腔（Cell）：存储4个顶点句柄、4个邻接胞腔句柄

邻接关系通过胞腔的邻居指针实现：

Cell c;
c.vertex(0), c.vertex(1), c.vertex(2), c.vertex(3)  // 四个顶点
c.neighbor(0), c.neighbor(1), c.neighbor(2), c.neighbor(3)  // 四个邻接胞腔

3. 定位结构（Locate Structure）

为了高效地定位点所在的胞腔，CGAL使用分层定位结构（Hierarchy）：

  • 构建多级粗化三角剖分
  • 每级是上一级的随机子集
  • 定位时从顶层开始，逐级下降

期望时间复杂度：

内存布局

// 顶点结构
class Vertex {
    Point_3 point;           // 几何位置
    Cell_handle cell;        // 一个入射胞腔（用于遍历）
    void* info;              // 可选用户数据
};
 
// 胞腔结构
class Cell {
    Vertex_handle vertices[4];    // 四个顶点
    Cell_handle neighbors[4];     // 四个邻接胞腔（对面邻居）
    void* info;                   // 可选用户数据
};

8.1.3 实现细节

点的定位算法

定位（Locate）操作是三角剖分的核心，用于找到包含给定点的胞腔。

线性定位

从已知胞腔开始，沿直线遍历：

// 伪代码
Cell_handle locate(Point p, Cell_handle start) {
    Cell_handle c = start;
    while (true) {
        // 检查p是否在c的每个面的外侧
        for (i = 0; i < 4; i++) {
            if (orientation(c->vertex((i+1)%4), 
                           c->vertex((i+2)%4), 
                           c->vertex((i+3)%4), p) == NEGATIVE) {
                c = c->neighbor(i);  // 移动到对面胞腔
                break;
            }
        }
        return c;  // p在c内部或边界上
    }
}

分层定位

// 期望O(log n)定位
Cell_handle locate_with_hierarchy(Point p) {
    // 从顶层开始
    int level = max_level;
    Cell_handle c = hierarchy[level]->infinite_cell();
    
    while (level >= 0) {
        c = locate_in_level(p, c);  // 在当前层定位
        if (level > 0) {
            c = hierarchy[level-1]->cell_corresponding_to(c);  // 下降
        }
        level--;
    }
    return c;
}

插入操作

Bowyer-Watson算法

插入新点会破坏局部Delaunay性质，需要重新三角剖分：

// 1. 定位包含新点的胞腔
Cell_handle c = locate(p);
 
// 2. 找到所有外接球包含p的胞腔（冲突区域）
std::vector<Cell_handle> conflict_cells;
find_conflict_cells(p, c, conflict_cells);
 
// 3. 删除冲突胞腔，形成空腔（cavity）
 
// 4. 将p与空腔边界连接，形成新胞腔
for (each facet on cavity boundary) {
    create_new_cell(p, facet);
}

遍历操作

CGAL提供多种遍历器（Iterator）用于访问三角剖分的元素：

// 遍历所有顶点
for (auto vit = T.finite_vertices_begin(); 
     vit != T.finite_vertices_end(); ++vit) {
    // 处理顶点
}
 
// 遍历所有胞腔
for (auto cit = T.finite_cells_begin(); 
     cit != T.finite_cells_end(); ++cit) {
    // 处理胞腔
}
 
// 遍历顶点的邻接胞腔
Vertex_handle v = ...;
auto vc = T.incident_cells(v);  // 返回cell_circulator
 
// 遍历胞腔的所有面
Cell_handle c = ...;
for (int i = 0; i < 4; i++) {
    Facet f(c, i);  // c的第i个面（与vertex(i)相对的面）
}

8.1.4 代码示例

基本用法

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <vector>
 
// 定义几何内核
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_3<K> Triangulation;
 
typedef Triangulation::Point Point;
typedef Triangulation::Vertex_handle Vertex_handle;
typedef Triangulation::Cell_handle Cell_handle;
typedef Triangulation::Facet Facet;
 
int main() {
    // 创建三角剖分
    Triangulation T;
    
    // 插入点
    std::vector<Point> points;
    points.push_back(Point(0, 0, 0));
    points.push_back(Point(1, 0, 0));
    points.push_back(Point(0, 1, 0));
    points.push_back(Point(0, 0, 1));
    points.push_back(Point(0.5, 0.5, 0.5));
    points.push_back(Point(1, 1, 1));
    
    // 批量插入（更高效）
    T.insert(points.begin(), points.end());
    
    // 查询基本信息
    std::cout << "顶点数: " << T.number_of_vertices() << std::endl;
    std::cout << "胞腔数: " << T.number_of_cells() << std::endl;
    std::cout << "有限胞腔数: " << T.number_of_finite_cells() << std::endl;
    
    // 定位点
    Point query(0.1, 0.1, 0.1);
    Cell_handle c = T.locate(query);
    
    if (T.is_infinite(c)) {
        std::cout << "查询点在凸包外" << std::endl;
    } else {
        std::cout << "查询点在胞腔内" << std::endl;
    }
    
    // 遍历有限胞腔
    int cell_count = 0;
    for (auto cit = T.finite_cells_begin(); 
         cit != T.finite_cells_end(); ++cit) {
        Cell_handle cell = cit;
        // 访问四个顶点
        for (int i = 0; i < 4; i++) {
            Point p = cell->vertex(i)->point();
            std::cout << "顶点 " << i << ": (" 
                      << p.x() << ", " << p.y() << ", " << p.z() << ")" 
                      << std::endl;
        }
        cell_count++;
    }
    
    return 0;
}

带信息的顶点

#include <CGAL/Triangulation_vertex_base_with_info_3.h>
 
// 定义带信息的顶点基类
typedef CGAL::Triangulation_vertex_base_with_info_3<int, K> Vb;
typedef CGAL::Triangulation_data_structure_3<Vb> Tds;
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
 
typedef Triangulation::Vertex_handle Vertex_handle;
 
int main() {
    Triangulation T;
    
    // 插入带信息的点
    Vertex_handle v0 = T.insert(Point(0, 0, 0));
    v0->info() = 0;  // 设置顶点信息
    
    Vertex_handle v1 = T.insert(Point(1, 0, 0));
    v1->info() = 1;
    
    // 访问信息
    for (auto vit = T.finite_vertices_begin(); 
         vit != T.finite_vertices_end(); ++vit) {
        std::cout << "顶点ID: " << vit->info() << std::endl;
    }
    
    return 0;
}

几何谓词的使用

#include <CGAL/predicates_on_points_3.h>
 
void test_orientation(const Triangulation& T) {
    // 获取四个点
    Point p(0, 0, 0), q(1, 0, 0), r(0, 1, 0), s(0, 0, 1);
    
    // 定向测试：判断s在pqr平面的哪一侧
    CGAL::Orientation orient = CGAL::orientation(p, q, r, s);
    
    switch (orient) {
        case CGAL::POSITIVE:
            std::cout << "s在pqr平面的正侧" << std::endl;
            break;
        case CGAL::NEGATIVE:
            std::cout << "s在pqr平面的负侧" << std::endl;
            break;
        case CGAL::COPLANAR:
            std::cout << "s在pqr平面上" << std::endl;
            break;
    }
}

8.1.5 复杂度分析

时间复杂度

操作平均复杂度最坏复杂度说明
构造空三角剖分初始化
插入单个点分层定位期望
插入n个点批量插入优化
定位点分层结构
删除点d为度数
遍历所有胞腔线性遍历
最近邻查询使用Delaunay性质

空间复杂度

  • 顶点存储：，每个顶点存储几何点和一个入射胞腔指针
  • 胞腔存储：，m为胞腔数，每个胞腔存储4个顶点指针和4个邻居指针
  • 定位结构：，分层结构的额外开销

对于一般位置的三维点集，胞腔数 ，因此总空间复杂度为 。

理论界限

三维三角剖分的组合复杂度：

  • 下界： 个胞腔
  • 上界： 个胞腔（凸位置达到上界）

对于随机分布的点集，期望胞腔数为 。

8.1.6 与其他组件的关系

Triangulation_3
├── 继承/特化
│   ├── Delaunay_triangulation_3（Delaunay三角剖分）
│   ├── Regular_triangulation_3（正则三角剖分）
│   └── Periodic_3_triangulation_3（周期性三角剖分）
│
├── 用于
│   ├── Mesh_3（三维网格生成）
│   ├── Alpha_shapes_3（Alpha形状）
│   └── Skin_surface_3（皮肤曲面）
│
└── 依赖
    ├── Kernel（几何内核）
    └── Triangulation_data_structure_3（数据结构）

Graph View

Backlinks