13.3 推进前沿曲面重建

推进前沿重建是曲面重建的重要方法，它直接从无向点云重建三角网格，无需法向信息。

0. 算法动机：为什么需要推进前沿重建？

现实问题引入

想象你是一位地质学家，在野外采集了岩石表面的采样点：

没有法向信息，只有点的位置
采样不均匀，某些区域密集，某些区域稀疏
需要重建岩石的真实表面，保留尖锐特征

或者你是一位游戏开发者：

从摄影测量获得了场景的点云
点云有噪声，有缺失
需要快速生成可用的网格模型

传统方法的局限

泊松重建：

需要法向信息
输出是隐式曲面，不经过原始点
可能过度平滑尖锐特征

Delaunay 方法：

对噪声敏感
计算复杂度高
需要额外的过滤步骤

推进前沿的优势

插值原始点：输出网格顶点就是输入点 无需法向：直接从点云重建 保留特征：能够重建尖锐边缘 开放表面：支持带边界的表面

如果不使用推进前沿

顶点偏移：重建结果不经过原始测量点
法向依赖：必须先估计法向，引入额外误差
特征丢失：尖锐边缘被圆滑
封闭强制：开放表面被错误封闭

1. 直观理解：吹气球与结冰

1.1 “球体生长就像吹气球”

想象你在点云上吹气球：

初始状态：

每个点是一个微小的气球
气球开始缓慢充气

   •       •       •
      •       •
   •       •       •
   
（微小气球，即将开始生长）

生长过程：

气球逐渐扩大
当三个气球刚好接触时，形成一个三角形

   ●───●
  / \\   \\
 ●   ●───●
  \\ /   /
   ●───●
   
（气球扩大，形成三角形网格）

停止条件：

气球碰到其他点停止
太大的空隙保持开放（边界）

1.2 “前沿推进就像结冰”

另一种类比：水面结冰

种子点：

某些点开始结冰（种子三角形）
冰面从这些点向外扩展

前沿扩展：

冰面边缘不断推进
遇到新点时连接形成新冰面
在尖锐处停止，保留特征

边界形成：

冰面前沿无法继续推进时形成边界
边界对应于数据缺失区域

1.3 “优先级队列就像智能队列”

算法使用优先级队列管理前沿：

优先级规则：

平坦区域优先（形成好三角形）
狭窄缝隙延后（避免错误连接）
尖锐特征特殊处理

前沿队列（按优先级排序）：
┌─────────────────────────────────┐
│ 1. 平坦边 (优先级: 0.2)         │ ← 先处理
├─────────────────────────────────┤
│ 2. 中等边 (优先级: 0.5)         │
├─────────────────────────────────┤
│ 3. 困难边 (优先级: 0.8)         │
├─────────────────────────────────┤
│ 4. 极难边 (优先级: 1.2)         │ ← 后处理（可能放弃）
└─────────────────────────────────┘

2. 数学基础

2.1 球体生长算法

AFSR 的核心思想是球体生长（ball-pivoting）的变体。算法想象一个球在点云上滚动，当球与三个点同时接触时，这三个点构成一个三角形。

形式化地，给定半径为 $r$ 的球，对于三个点 $p_{i}, p_{j}, p_{k}$ ，如果存在球同时与这三点相切，且球内不包含其他点，则这三点构成一个有效三角形。

2.2 Delaunay 三角剖分与 Voronoi 对偶

AFSR 基于三维 Delaunay 三角剖分，利用其对偶性质：

Delaunay 边：连接两点的边，存在空球（不含其他点）通过这两点
Delaunay 面：三角形面，存在空球通过三个顶点
Voronoi 边：到两个点等距的点的轨迹
Voronoi 面：到三个点等距的点的轨迹

AFSR 利用 Voronoi 边的长度作为面片优先级：较短的 Voronoi 边对应更”扁平”的三角形，更可能是表面的一部分。

2.3 优先级函数

算法使用优先级队列管理候选面片。默认优先级基于Delaunay 球的最小半径：

$priority (f) = min (radius (c_{1}), radius (c_{2}))$

其中 $c_{1}, c_{2}$ 是共享面 $f$ 的两个 Delaunay 四面体。

3. 算法流程详解

3.1 初始化阶段

构建输入点云的 Delaunay 三角剖分，识别初始种子面片：

对于每个 Delaunay 面 f:
    计算优先级 priority(f)
    如果 priority(f) 最小:
        选择 f 作为种子面
        将 f 的三条边加入前沿队列

可视化：

点云：                    Delaunay三角剖分：           种子选择：
  •       •                  /\\      /|               /\\      /|
    •   •        →          /  \\    / |    →         /  \\    / |
  •       •                /____\\  /  |             /____\\  /  |
    •   •                  \\    /  \\ /              \\ 1  /  \\ /
                            \\  /    \/                \\ /  2  \/
                             \\/     /                  \\/     /

3.2 前沿推进阶段

维护一个前沿（frontier）边集，迭代地扩展表面：

while 前沿队列非空:
    取出优先级最高的边 e
    找到 e 周围的最佳候选面 f
    
    如果 f 满足以下条件:
        - 不与其他前沿边冲突
        - 不创建非流形边
        - 不创建退化三角形
    then:
        将 f 加入表面
        更新前沿队列

逐步过程可视化：

步骤1: 种子三角形          步骤2: 扩展一条边
    •                      •───•
   /\\                     │  /|
  /  \\        →            │ / |
 •────•                    •/  •
                           
步骤3: 继续扩展            步骤4: 形成边界
•───•───•                 •───•───•
│  /│  /                  │  /│  /
│ / │ /        →          │ / │ /
•/  •/                    •/  •/
                          （开放边界）

3.3 边界处理

当算法无法继续推进时，可能形成边界。CGAL 的实现包括后处理步骤来优化边界。

3.4 多连通分量处理

算法可以处理多个不连通的表面分量，依次重建每个连通分量。

4. CGAL 架构分析

4.1 核心类层次

Advancing_front_surface_reconstruction<Dt, P>
    |
    +-- Delaunay_triangulation_3<Kernel, Tds> (用户传入)
            |
            +-- Advancing_front_surface_reconstruction_vertex_base_3<Kernel>
            |       +-- Triangulation_vertex_base_3<Kernel>
            |
            +-- Advancing_front_surface_reconstruction_cell_base_3<Kernel>
                    +-- Triangulation_cell_base_3<Kernel>

4.2 关键文件位置

文件	路径	功能
`Advancing_front_surface_reconstruction.h`	`Advancing_front_surface_reconstruction/include/CGAL/`	核心重建类
`Advancing_front_surface_reconstruction_vertex_base_3.h`	`Advancing_front_surface_reconstruction/include/CGAL/`	顶点基类
`Advancing_front_surface_reconstruction_cell_base_3.h`	`Advancing_front_surface_reconstruction/include/CGAL/`	单元基类

4.3 顶点状态管理

每个顶点维护以下状态信息：

class Advancing_front_surface_reconstruction_vertex_base_3 : public Vb
{
    // 边界边信息
    Intern_successors_type* m_incident_border;
    
    // 内部边列表
    std::list<Vertex_handle>::iterator m_ie_first, m_ie_last;
    
    // 入射请求列表
    std::list<Incidence_request_elt>::iterator m_ir_first, m_ir_last;
    
    // 标记信息
    int m_mark;           // 当前前沿标记
    int m_post_mark;      // 后处理标记
    
public:
    // 状态查询
    bool is_on_border() const;      // 是否在边界上
    bool is_exterior() const;       // 是否在外部
    bool not_interior() const;      // 是否非内部
    bool is_interior() const;       // 是否在内部
    
    // 标记操作
    void inc_mark();                // 增加标记计数
    void dec_mark();                // 减少标记计数
    int number_of_incident_border() const;
};

4.4 核心类定义

template <class Dt = Default, class P = Default>
class Advancing_front_surface_reconstruction
{
public:
    // 类型定义
    typedef typename Default::Get<Dt, ...>::type Triangulation_3;
    typedef typename Default::Get<P, AFSR::Default_priority>::type Priority;
    
    typedef typename Triangulation_3::Geom_traits Kernel;
    typedef typename Kernel::FT FT;
    typedef typename Kernel::Point_3 Point;
    typedef typename Kernel::Vector_3 Vector;
    
    typedef typename Triangulation_3::Vertex_handle Vertex_handle;
    typedef typename Triangulation_3::Cell_handle Cell_handle;
    typedef typename Triangulation_3::Facet Facet;
    typedef typename Triangulation_3::Edge Edge;
    
    // 2D 表面三角剖分
    typedef TDS_2 Triangulation_data_structure_2;
    
    // 构造函数
    Advancing_front_surface_reconstruction(Triangulation_3& dt, 
                                           Priority priority = Priority());
    
    // 运行重建
    void run(double radius_ratio_bound = 5, double beta = 0.52);
    
    // 结果访问
    const Triangulation_data_structure_2& triangulation_data_structure_2() const;
    Triangulation_3& triangulation_3() const;
    
    // 统计信息
    int number_of_facets() const;
    int number_of_vertices() const;
    int number_of_connected_components() const;
    bool has_boundaries() const;
    
    // 边界遍历
    Boundary_iterator boundaries_begin() const;
    Boundary_iterator boundaries_end() const;
    
    // 离群点访问
    const Outlier_range& outliers() const;
};

5. 实现细节

5.1 前沿边表示

前沿边使用复杂的数据结构维护：

typedef std::pair<Vertex_handle, Vertex_handle> Edge_like;
 
typedef std::pair<criteria, std::pair<IO_edge_type, int>> Border_elt;
// criteria: 优先级值
// IO_edge_type: 输入/输出边信息
// int: 连通分量编号
 
typedef std::set<Radius_ptr_type> Ordered_border_type;
// 按优先级排序的前沿边集合

5.2 候选面计算

对于每条前沿边，算法计算最佳候选面：

Radius_edge_type compute_value(const Edge_incident_facet& e)
{
    Cell_handle c = e.first.first;
    int i = e.second;
    int i1 = e.first.second, i2 = e.first.third;
    int i3 = 6 - e.second - i1 - i2;
    
    // 遍历边周围的所有面
    Edge_incident_facet e_it = e;
    coord_type min_valueA = infinity();
    Facet min_facetA;
    
    do {
        Cell_handle neigh = e_it.first.first;
        Facet facet_it(neigh, e_it.second);
        
        if (\!T.is_infinite(facet_it)) {
            // 计算优先级
            coord_type tmp = priority(*this, neigh, e_it.second);
            
            // 检查有效性
            if (tmp \!= infinity() && neigh->vertex(n_i3)->not_interior()
                && \!is_interior_edge(el1) && \!is_interior_edge(el2))
            {
                // 检查三角形质量（避免狭长三角形）
                Vector v1 = construct_cross_product(construct_vector(p2, pc), 
                                                     construct_vector(p2, p1));
                Vector v2 = construct_cross_product(construct_vector(p2, p1), 
                                                     construct_vector(p2, pn));
                FT norm = sqrt(norm1 * compute_scalar_product(v2, v2));
                FT pscal = v1 * v2;
                bool sliver_facet = (pscal <= COS_ALPHA_SLIVER * norm);
                
                if (\!sliver_facet && tmp < min_valueA) {
                    min_facetA = facet_it;
                    min_valueA = tmp;
                }
            }
        }
        e_it = next(e_it);
    } while (e_it.first.first \!= c);
    
    // 返回结果
    return Radius_edge_type(value, IO_edge_type(e, Edge_incident_facet(...)));
}

5.3 验证与合并

当选择候选面时，需要验证多种情况：

enum Validation_case { 
    NOT_VALID,              // 无效候选
    NOT_VALID_CONNECTING_CASE,  // 连接情况无效
    FINAL_CASE,             // 最终情况（形成封闭环）
    EAR_CASE,               // 耳朵情况（单边合并）
    EXTERIOR_CASE,          // 外部扩展
    CONNECTING_CASE         // 连接情况
};
 
Validation_case validate(const Edge_incident_facet& edge_Efacet,
                         const criteria& value)
{
    // 获取相关顶点和边
    Vertex_handle v1 = c->vertex(edge_Efacet.first.second);
    Vertex_handle v2 = c->vertex(edge_Efacet.first.third);
    Vertex_handle v3 = c->vertex(i);
    
    Edge_like ordered_el1(v3, v1);
    Edge_like ordered_el2(v3, v2);
    Edge_like ordered_key(v1, v2);
    
    // 检查边界状态
    bool is_border_el1 = is_border_elt(ordered_el1, result1);
    bool is_border_el2 = is_border_elt(ordered_el2, result2);
    bool is_border_key = is_border_elt(ordered_key, result12);
    
    // 情况 1: 两个相邻边都在边界上（形成三角形）
    if (is_border_el1 && is_border_el2) {
        // 移除三条边界边，添加面片
        remove_border_elt(ordered_key);
        force_merge(ordered_el1, result1);
        force_merge(ordered_el2, result2);
        select_facet(c, edge_Efacet.second);
        return FINAL_CASE;
    }
    
    // 情况 2: 只有一条相邻边在边界上（耳朵裁剪）
    if (is_border_el1) {
        merge_ear(ordered_el1, result1, ordered_key, v1, v2, ...);
        return EAR_CASE;
    }
    if (is_border_el2) {
        merge_ear(ordered_el2, result2, ordered_key, v2, v1, ...);
        return EAR_CASE;
    }
    
    // 情况 3: 外部扩展
    if (v3->is_exterior()) {
        border_extend(ordered_key, result12, v1, v2, v3, ...);
        return EXTERIOR_CASE;
    }
    
    // 情况 4: 连接情况（处理边界合并）
    // ...
    
    return NOT_VALID;
}

5.4 优先级计算

默认优先级基于 Delaunay 球半径：

FT smallest_radius_delaunay_sphere(const Cell_handle& c, const int& index) const
{
    Cell_handle n = c->neighbor(index);
    
    // 检查缓存
    coord_type value = c->smallest_radius(index);
    if (value >= 0 && n->smallest_radius(n->index(c)) == value)
        return value;
    
    // 计算 Voronoi 边长度
    const Point& cp0 = c->vertex(index)->point();
    const Point& cp1 = c->vertex((index+1) & 3)->point();
    const Point& cp2 = c->vertex((index+2) & 3)->point();
    const Point& cp3 = c->vertex((index+3) & 3)->point();
    
    // 处理退化情况
    if (c_is_plane || n_is_plane || my_collinear(cp1, cp2, cp3))
        value = infinity();
    else {
        // 计算外心距离
        Point cc = circumcenter(cp0, cp1, cp2, cp3);
        Point cn = circumcenter(np0, np1, np2, np3);
        
        // 计算到 Voronoi 边的距离
        Vector V = construct_vector(cn, cc);
        Vector Vc = construct_vector(cp1, cc);
        FT ac = compute_scalar_product(V, Vc);
        FT an = compute_scalar_product(V, construct_vector(cn, cp1));
        FT norm_V = compute_scalar_product(V, V);
        
        if (ac > 0 && an > 0)
            value = compute_scalar_product(Vc, Vc) - ac*ac/norm_V;
        else if (ac <= 0)
            value = compute_squared_distance(cc, cp1);
        else
            value = compute_squared_distance(cn, cp1);
    }
    
    // 缓存结果
    c->set_smallest_radius(index, value);
    n->set_smallest_radius(n->index(c), value);
    
    return value;
}

6. 使用示例

6.1 完整示例代码

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Advancing_front_surface_reconstruction.h>
#include <CGAL/Triangulation_data_structure_3.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/IO/read_points.h>
 
#include <vector>
#include <fstream>
#include <iostream>
 
// 类型定义
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Advancing_front_surface_reconstruction_vertex_base_3<Kernel> LVb;
typedef CGAL::Advancing_front_surface_reconstruction_cell_base_3<Kernel> LCb;
typedef CGAL::Triangulation_data_structure_3<LVb, LCb> Tds;
typedef CGAL::Delaunay_triangulation_3<Kernel, Tds> Triangulation_3;
typedef CGAL::Advancing_front_surface_reconstruction<Triangulation_3> Reconstruction;
 
int main(int argc, char* argv[])
{
    // 1. 读取点云
    std::vector<Point> points;
    const char* input_file = (argc > 1) ? argv[1] : "input.xyz";
    
    if (\!CGAL::IO::read_points(input_file, std::back_inserter(points)))
    {
        std::cerr << "Error: cannot read file " << input_file << std::endl;
        return EXIT_FAILURE;
    }
    
    std::cout << "Loaded " << points.size() << " points" << std::endl;
    
    // 2. 构建 Delaunay 三角剖分
    Triangulation_3 dt(points.begin(), points.end());
    std::cout << "Delaunay triangulation: " << dt.number_of_vertices() << " vertices"
              << std::endl;
    
    // 3. 创建并运行重建
    Reconstruction reconstruction(dt);
    
    // 参数设置
    double radius_ratio_bound = 5.0;  // 半径比上界
    double beta = 0.52;               // 角度参数（约 30 度）
    
    reconstruction.run(radius_ratio_bound, beta);
    
    // 4. 输出统计信息
    std::cout << "Reconstruction completed:" << std::endl;
    std::cout << "  Facets: " << reconstruction.number_of_facets() << std::endl;
    std::cout << "  Vertices: " << reconstruction.number_of_vertices() << std::endl;
    std::cout << "  Components: " << reconstruction.number_of_connected_components() << std::endl;
    std::cout << "  Has boundaries: " << (reconstruction.has_boundaries() ? "yes" : "no") << std::endl;
    std::cout << "  Outliers: " << reconstruction.number_of_outliers() << std::endl;
    
    // 5. 提取结果并保存
    std::ofstream out("output.off");
    out << "OFF\n";
    out << points.size() << " " << reconstruction.number_of_facets() << " 0\n";
    
    // 输出顶点
    for (const auto& p : points)
        out << p << "\n";
    
    // 输出面片（需要访问 TDS_2）
    const auto& tds2 = reconstruction.triangulation_data_structure_2();
    for (auto fit = tds2.faces_begin(); fit \!= tds2.faces_end(); ++fit)
    {
        if (fit->is_on_surface())
        {
            auto v0 = fit->vertex(0)->vertex_3();
            auto v1 = fit->vertex(1)->vertex_3();
            auto v2 = fit->vertex(2)->vertex_3();
            
            out << "3 " << v0->index() << " " 
                << v1->index() << " " 
                << v2->index() << "\n";
        }
    }
    out.close();
    
    return EXIT_SUCCESS;
}

6.2 使用自定义优先级

用户可以定义自己的优先级函数：

// 自定义优先级：基于周长约束
struct Perimeter {
    double bound;
    
    Perimeter(double bound) : bound(bound) {}
    
    template <typename AdvancingFront, typename Cell_handle>
    double operator()(const AdvancingFront& adv, Cell_handle& c, 
                      const int& index) const
    {
        // 如果周长约束为 0，使用默认优先级
        if (bound == 0) {
            return adv.smallest_radius_delaunay_sphere(c, index);
        }
        
        // 计算三角形周长
        double d = sqrt(squared_distance(c->vertex((index+1)%4)->point(),
                                         c->vertex((index+2)%4)->point()));
        if (d > bound) return adv.infinity();
        
        d += sqrt(squared_distance(c->vertex((index+2)%4)->point(),
                                   c->vertex((index+3)%4)->point()));
        if (d > bound) return adv.infinity();
        
        d += sqrt(squared_distance(c->vertex((index+1)%4)->point(),
                                   c->vertex((index+3)%4)->point()));
        if (d > bound) return adv.infinity();
        
        // 周长满足约束，使用默认优先级
        return adv.smallest_radius_delaunay_sphere(c, index);
    }
};
 
// 使用自定义优先级
Perimeter perimeter(0.5);  // 周长上界为 0.5
Triangulation_3 dt(points.begin(), points.end());
Reconstruction<Triangulation_3, Perimeter> reconstruction(dt, perimeter);
reconstruction.run(5.0, 0.52);

6.3 便捷函数接口

CGAL 提供了更简单的函数接口：

#include <CGAL/Advancing_front_surface_reconstruction.h>
 
// 定义输出类型
typedef std::array<std::size_t, 3> Facet;
 
// 使用便捷函数
std::vector<Facet> facets;
CGAL::advancing_front_surface_reconstruction(
    points.begin(), points.end(),
    std::back_inserter(facets),
    radius_ratio_bound,  // 默认 5.0
    beta                 // 默认 0.52
);
 
// 输出结果
std::cout << "OFF\n";
std::cout << points.size() << " " << facets.size() << " 0\n";
for (const auto& p : points)
    std::cout << p << "\n";
for (const auto& f : facets)
    std::cout << "3 " << f[0] << " " << f[1] << " " << f[2] << "\n";

6.4 实际应用：快速原型制作

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Advancing_front_surface_reconstruction.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/IO/read_points.h>
#include <CGAL/IO/OBJ.h>
#include <CGAL/grid_simplify_point_set.h>
#include <CGAL/jet_estimate_normals.h>
#include <CGAL/mst_orient_normals.h>
#include <iostream>
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef CGAL::Surface_mesh<Point> Mesh;
 
// 快速原型制作流程
void rapid_prototyping_pipeline(const std::string& input_file,
                                const std::string& output_file)
{
    // 1. 读取点云
    std::vector<Point> points;
    if (\!CGAL::IO::read_points(input_file, std::back_inserter(points))) {
        std::cerr << "Failed to read input" << std::endl;
        return;
    }
    
    std::cout << "Loaded " << points.size() << " points" << std::endl;
    
    // 2. 预处理：简化（如果点云过于密集）
    if (points.size() > 100000) {
        double cell_size = 0.01;  // 1cm 网格
        auto iterator_to_first_to_remove = CGAL::grid_simplify_point_set(
            points, cell_size);
        points.erase(iterator_to_first_to_remove, points.end());
        std::cout << "Simplified to " << points.size() << " points" << std::endl;
    }
    
    // 3. 构建 Delaunay 三角剖分
    typedef CGAL::Advancing_front_surface_reconstruction_vertex_base_3<Kernel> LVb;
    typedef CGAL::Advancing_front_surface_reconstruction_cell_base_3<Kernel> LCb;
    typedef CGAL::Triangulation_data_structure_3<LVb, LCb> Tds;
    typedef CGAL::Delaunay_triangulation_3<Kernel, Tds> Dt;
    
    Dt dt(points.begin(), points.end());
    std::cout << "Delaunay triangulation created" << std::endl;
    
    // 4. 推进前沿重建
    typedef CGAL::Advancing_front_surface_reconstruction<Dt> Reconstruction;
    Reconstruction reconstruction(dt);
    
    // 根据数据质量调整参数
    double radius_ratio_bound = 5.0;  // 标准值
    double beta = 0.52;               // 约30度
    
    // 如果数据噪声较大，可以放宽参数
    if (points.size() < 5000) {
        radius_ratio_bound = 6.0;  // 更宽松
        beta = 0.45;               // 更小角度
    }
    
    reconstruction.run(radius_ratio_bound, beta);
    
    std::cout << "Reconstruction completed:" << std::endl;
    std::cout << "  Facets: " << reconstruction.number_of_facets() << std::endl;
    std::cout << "  Components: " << reconstruction.number_of_connected_components() << std::endl;
    std::cout << "  Boundaries: " << (reconstruction.has_boundaries() ? "yes" : "no") << std::endl;
    
    // 5. 转换为 Surface_mesh
    Mesh mesh;
    // 添加顶点
    for (const auto& p : points) {
        mesh.add_vertex(p);
    }
    
    // 添加面
    const auto& tds2 = reconstruction.triangulation_data_structure_2();
    for (auto fit = tds2.faces_begin(); fit \!= tds2.faces_end(); ++fit) {
        if (fit->is_on_surface()) {
            auto v0 = fit->vertex(0)->vertex_3();
            auto v1 = fit->vertex(1)->vertex_3();
            auto v2 = fit->vertex(2)->vertex_3();
            
            mesh.add_face(
                Mesh::Vertex_index(v0->index()),
                Mesh::Vertex_index(v1->index()),
                Mesh::Vertex_index(v2->index())
            );
        }
    }
    
    // 6. 保存结果
    CGAL::IO::write_OBJ(output_file, mesh);
    std::cout << "Saved to " << output_file << std::endl;
}
 
int main(int argc, char* argv[])
{
    std::string input = (argc > 1) ? argv[1] : "scan.xyz";
    std::string output = (argc > 2) ? argv[2] : "model.obj";
    
    rapid_prototyping_pipeline(input, output);
    
    return 0;
}

7. 复杂度分析

7.1 时间复杂度

步骤	复杂度	说明
Delaunay 三角剖分	$O (n lo g n)$	$n$ 为输入点数
初始化	$O (n)$	寻找种子面
前沿推进	$O (m lo g m)$	$m$ 为输出面片数，优先队列操作
后处理	$O (m)$	边界优化

总体复杂度为 $O (n lo g n + m lo g m)$ 。

7.2 空间复杂度

Delaunay 三角剖分： $O (n)$
前沿队列： $O (m)$ （前沿边数）
表面存储： $O (m)$

总体空间复杂度为 $O (n + m)$ 。

7.3 参数影响

radius_ratio_bound：控制候选面片的半径比阈值。较大的值允许更多面片，但可能包含噪声。
beta：控制楔形区域的角度。较大的值更严格，可能产生更多边界。

8. 应用建议

8.1 适用场景

AFSR 最适合以下场景：

无向点云（没有法向信息）
开放表面重建（允许边界）
需要插值输入点的应用
点云密度较均匀的情况

8.2 预处理建议

离群点移除：AFSR 对离群点敏感，建议先进行统计过滤
采样均匀化：如果点云密度变化大，可考虑重采样
边界检测：对于已知开放边界的扫描数据，可利用边界信息

8.3 常见问题

问题 1：重建结果有过多孔洞

原因：beta 参数过大或点云密度不足
解决：减小 beta 值，或增加 radius_ratio_bound

问题 2：重建结果包含噪声面片

原因：radius_ratio_bound 过大或输入有离群点
解决：减小 radius_ratio_bound，或预处理移除离群点

问题 3：多个连通分量被合并

原因：组件间距过小
解决：使用自定义优先级添加距离约束

9. 参数调优指南

9.1 参数选择流程图

开始
  │
  ▼
数据质量评估
  │
  ├─ 高质量扫描（噪声低，密度均匀）
  │     └─ radius_ratio_bound = 5.0, beta = 0.52
  │
  ├─ 中等质量（有噪声，密度变化）
  │     └─ radius_ratio_bound = 6.0, beta = 0.45
  │
  └─ 低质量（噪声大，缺失多）
        └─ radius_ratio_bound = 7.0, beta = 0.40
  │
  ▼
检查重建结果
  │
  ├─ 孔洞过多？→ 增大 radius_ratio_bound 或减小 beta
  │
  ├─ 噪声面片？→ 减小 radius_ratio_bound
  │
  └─ 组件合并？→ 使用自定义优先级
  │
  ▼
结束

9.2 自定义优先级示例

// 距离约束优先级（防止远距离连接）
struct DistanceConstraint {
    double max_distance;
    
    DistanceConstraint(double d) : max_distance(d) {}
    
    template <typename AdvancingFront, typename Cell_handle>
    double operator()(const AdvancingFront& adv, Cell_handle& c, 
                      const int& index) const {
        // 计算三角形最大边长
        const Point& p1 = c->vertex((index+1)%4)->point();
        const Point& p2 = c->vertex((index+2)%4)->point();
        const Point& p3 = c->vertex((index+3)%4)->point();
        
        double d12 = sqrt(squared_distance(p1, p2));
        double d23 = sqrt(squared_distance(p2, p3));
        double d31 = sqrt(squared_distance(p3, p1));
        
        double max_d = std::max({d12, d23, d31});
        
        if (max_d > max_distance)
            return adv.infinity();  // 拒绝这个大三角形
        
        return adv.smallest_radius_delaunay_sphere(c, index);
    }
};

10. 实际应用案例

10.1 案例一：考古文物数字化

场景：从摄影测量获得破碎陶片的点云。

挑战：

点云密度不均匀
有缺失区域（边界）
需要保留尖锐边缘

解决方案：

// 使用较小的 beta 保留特征
reconstruction.run(5.0, 0.45);  // 更严格的角度控制
 
// 后处理：检测并标记边界
if (reconstruction.has_boundaries()) {
    std::cout << "Detected boundaries:" << std::endl;
    for (auto bit = reconstruction.boundaries_begin();
         bit \!= reconstruction.boundaries_end(); ++bit) {
        std::cout << "  Boundary with " << bit->size() << " edges" << std::endl;
    }
}

10.2 案例二：工业零件检测

场景：检测机械零件的表面缺陷。

方法：

使用 AFSR 重建标称表面
将重建结果与CAD模型对比
偏差区域即为缺陷

10.3 案例三：地形建模

场景：从无人机摄影测量获得地形点云。

优势：

自然处理开放边界（地形边缘）
保留地形特征（山脊、沟壑）
无需法向估计

参考文献

Boissonnat, J. D., & Oudot, S. (2005). Provably good sampling and meshing of surfaces. Graphical Models, 67(5), 405-451.
Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., & Taubin, G. (1999). The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 5(4), 349-359.
CGAL Documentation: Advancing Front Surface Reconstruction. https://doc.cgal.org/latest/Advancing_front_surface_reconstruction/

Chunibyo

Explorer

13.3 推进前沿曲面重建

13.3 推进前沿曲面重建 §

0. 算法动机：为什么需要推进前沿重建？ §

现实问题引入 §

传统方法的局限 §

如果不使用推进前沿 §

1. 直观理解：吹气球与结冰 §

1.1 “球体生长就像吹气球” §

1.2 “前沿推进就像结冰” §

1.3 “优先级队列就像智能队列” §

2. 数学基础 §

2.1 球体生长算法 §

2.2 Delaunay 三角剖分与 Voronoi 对偶 §

2.3 优先级函数 §

3. 算法流程详解 §

3.1 初始化阶段 §

3.2 前沿推进阶段 §

3.3 边界处理 §

3.4 多连通分量处理 §

4. CGAL 架构分析 §

4.1 核心类层次 §

4.2 关键文件位置 §

4.3 顶点状态管理 §

4.4 核心类定义 §

5. 实现细节 §

5.1 前沿边表示 §

5.2 候选面计算 §

5.3 验证与合并 §

5.4 优先级计算 §

6. 使用示例 §

6.1 完整示例代码 §

6.2 使用自定义优先级 §

6.3 便捷函数接口 §

6.4 实际应用：快速原型制作 §

7. 复杂度分析 §

7.1 时间复杂度 §

7.2 空间复杂度 §

7.3 参数影响 §

8. 应用建议 §

8.1 适用场景 §

8.2 预处理建议 §

8.3 常见问题 §

9. 参数调优指南 §

9.1 参数选择流程图 §

9.2 自定义优先级示例 §

10. 实际应用案例 §

10.1 案例一：考古文物数字化 §

10.2 案例二：工业零件检测 §

10.3 案例三：地形建模 §

参考文献 §

Graph View

Table of Contents

Backlinks

13.3 推进前沿曲面重建

0. 算法动机：为什么需要推进前沿重建？

现实问题引入

传统方法的局限

如果不使用推进前沿

1. 直观理解：吹气球与结冰

1.1 “球体生长就像吹气球”

1.2 “前沿推进就像结冰”

1.3 “优先级队列就像智能队列”

2. 数学基础

2.1 球体生长算法

2.2 Delaunay 三角剖分与 Voronoi 对偶

2.3 优先级函数

3. 算法流程详解

3.1 初始化阶段

3.2 前沿推进阶段

3.3 边界处理

3.4 多连通分量处理

4. CGAL 架构分析

4.1 核心类层次

4.2 关键文件位置

4.3 顶点状态管理

4.4 核心类定义

5. 实现细节

5.1 前沿边表示

5.2 候选面计算

5.3 验证与合并

5.4 优先级计算

6. 使用示例

6.1 完整示例代码

6.2 使用自定义优先级

6.3 便捷函数接口

6.4 实际应用：快速原型制作

7. 复杂度分析

7.1 时间复杂度

7.2 空间复杂度

7.3 参数影响

8. 应用建议

8.1 适用场景

8.2 预处理建议

8.3 常见问题

9. 参数调优指南

9.1 参数选择流程图

9.2 自定义优先级示例

10. 实际应用案例

10.1 案例一：考古文物数字化

10.2 案例二：工业零件检测

10.3 案例三：地形建模

参考文献