13.1 曲面重建技术概述 §

曲面重建算法通常以 三维Delaunay三角剖分 为基础结构。本章概述CGAL提供的五种主要曲面重建方法。

曲面重建是计算几何中的核心问题之一，其目标是从离散的三维点云数据中恢复出连续的表面几何。CGAL 提供了多种曲面重建算法，每种算法基于不同的数学原理，适用于不同的应用场景。

13.1.1 问题定义 §

给定一个三维点集 $P=\{p_1,p_2,...,p_n\}$，其中每个点 $p_i\in {\mathbb{R}}^3$，曲面重建的目标是找到一个二维流形 $S\subset {\mathbb{R}}^3$，使得 $P$ 是 $S$ 的采样。根据输入数据的不同，问题可以分为：

• 无向点云重建：仅知道点的位置
• 有向点云重建：知道点的位置和法向量方向
• 平面分割重建：知道点属于哪个平面区域

13.1.2 CGAL 曲面重建算法概览 §

CGAL 提供了五种主要的曲面重建算法：

算法	输入要求	输出类型	适用场景
泊松重建	有向点云	水密三角网格	封闭物体扫描
推进前沿重建	无向点云	三角网格（可能有边界）	开放表面重建
尺度空间重建	无向点云	插值三角网格	噪声点云处理
多边形曲面重建	平面分割点云	多边形网格	CAD 模型重建
动力学重建	有向点云	多边形网格	建筑场景重建

13.1.3 算法选择指南 §

选择合适的重建算法需要考虑以下因素：

数据特性 §

• 点云密度：均匀采样 vs 非均匀采样
• 噪声水平：低噪声可直接重建，高噪声需要预处理
• 数据完整性：封闭物体 vs 开放表面
• 特征保留：是否需要保留尖锐特征

输出要求 §

• 水密性：是否需要封闭的表面
• 网格质量：三角形质量要求
• 插值性：输出是否必须经过输入点
• 多边形支持：是否需要多边形面片

计算资源 §

• 时间复杂度：从 $O(n\log n)$ 到 $O(n^2)$ 不等
• 内存需求：与点云规模和重建精度相关
• 并行支持：部分算法支持多线程

13.1.4 重建流程 pipeline §

典型的曲面重建流程包括以下步骤：

输入点云
    |
    v
预处理（去噪、采样、法向估计）
    |
    v
选择并运行重建算法
    |
    v
后处理（平滑、修复、简化）
    |
    v
输出网格

CGAL 的 Point_set_processing_3 包提供了丰富的预处理和后处理工具，包括：

• 法向估计：基于 PCA 或 jet 拟合
• 去噪：基于双边滤波或统计离群点移除
• 采样：网格简化或均匀采样
• 配准：多视角点云对齐

13.1.5 理论基础 §

曲面重建算法的数学基础主要包括：

隐式表面 §

许多重建算法（如泊松重建）将表面表示为隐式函数 $f:{\mathbb{R}}^3\to \mathbb{R}$ 的零等值面： $S=\{x\in {\mathbb{R}}^3\mid f(x)=0\}$

隐式表示的优点包括：

• 自然处理拓扑变化
• 易于判断点是否在表面内部
• 支持布尔运算

Delaunay 三角剖分 §

推进前沿和尺度空间重建基于三维 Delaunay 三角剖分。Delaunay 三角剖分具有以下性质：

• 最大化最小角
• 空球性质：每个三角形的外接球不包含其他点
• 对偶于 Voronoi 图

变分方法 §

泊松重建和多边形重建使用变分框架，通过最小化能量泛函来求解： $E(f)={\int }_{\Omega }\Vert \nabla f-\mathbf{V}{\Vert }^{2}dV+\lambda R(f)$

其中 $\mathbf{V}$ 是向量场，$R(f)$ 是正则化项。

13.1.6 本章组织 §

本章后续内容组织如下：

• 13.2 节：详细介绍泊松曲面重建的数学原理和实现
• 13.3 节：分析推进前沿重建的球体生长算法
• 13.4 节：探讨尺度空间重建的多尺度处理框架
• 13.5 节：介绍多边形重建和动力学重建等其他方法

每节都包含理论基础、架构分析、实现细节、使用示例和复杂度分析。

参考文献 §

1. Kazhdan, M., Bolitho, M., & Hoppe, H. (2006). Poisson surface reconstruction. In Proceedings of the fourth Eurographics symposium on Geometry processing (Vol. 7, No. 4).

2. Boissonnat, J. D., & Oudot, S. (2005). Provably good sampling and meshing of surfaces. Graphical Models, 67(5), 405-451.

3. Digne, J., Morel, J. M., Souzani, C. M., & Lartigue, C. (2011). Scale space meshing of raw data point sets. Computer Graphics Forum, 30(6), 1630-1642.

4. Nan, L., & Wonka, P. (2017). Polyfit: Polygonal surface reconstruction from point clouds. In Proceedings of the IEEE International Conference on Computer Vision (pp. 2353-2361).

5. Oesau, S., Lafarge, F., & Alliez, P. (2023). Kinetic shape reconstruction. ACM Transactions on Graphics, 42(4), 1-15.