13.5 其他曲面重建方法

除了泊松重建、推进前沿和尺度空间重建外，CGAL还提供了多边形曲面重建和动力学曲面重建两种方法。

除了泊松重建、推进前沿和尺度空间重建外，CGAL 还提供了多边形曲面重建和动力学曲面重建两种方法。这些方法针对特定应用场景设计，具有独特的优势。

13.5.1 多边形曲面重建

多边形曲面重建（Polygonal Surface Reconstruction）由 Nan 和 Wonka 提出，专门用于从分段平面点云重建多边形网格模型。该方法假设输入点云已被分割为平面区域。

数学基础

问题定义

给定：

点云 $P = {p_{1}, ..., p_{n}}$
法向 $N = {n_{1}, ..., n_{n}}$
平面标签 $L = {l_{1}, ..., l_{n}}$ ，其中 $l_{i} \in {0, 1, ..., k}$ 表示点 $p_{i}$ 所属的平面（ $l_{i} = - 1$ 表示未分配）

目标：找到一个水密的多边形网格 $M$ ，使得：

$M$ 的面片是平面多边形
$M$ 插值输入点云
$M$ 是流形且水密的

候选面生成

算法首先通过平面相交生成候选面：

对于每对平面 $(π_{i}, π_{j})$ ，计算交线 $l_{ij}$
对于每三个平面 $(π_{i}, π_{j}, π_{k})$ ，计算交点 $v_{ijk}$
构建平面排列（plane arrangement），提取有界面作为候选面

混合整数优化

候选面选择被建模为混合整数规划（MIP）问题：

$min \sum_{f \in F} (w_{fitting} \cdot E_{fit} (f) + w_{coverage} \cdot E_{cov} (f)) + w_{complexity} \cdot E_{comp}$

约束条件：

每条边关联 0 或 2 个面（水密性）
每个顶点的邻接面形成有效流形

架构分析

核心类

template <class GeomTraits>
class Polygonal_surface_reconstruction
{
public:
    typedef typename GeomTraits::FT FT;
    typedef typename GeomTraits::Point_3 Point;
    typedef typename GeomTraits::Vector_3 Vector;
    typedef typename GeomTraits::Plane_3 Plane;
    
    // 构造函数
    template <typename PointRange, typename PointMap, typename NormalMap, typename IndexMap>
    Polygonal_surface_reconstruction(
        const PointRange& points,
        PointMap point_map,
        NormalMap normal_map,
        IndexMap index_map
    );
    
    // 重建
    template <typename MixedIntegerProgramTraits, typename PolygonMesh>
    bool reconstruct(
        PolygonMesh& output_mesh,
        double wt_fitting = 0.43,
        double wt_coverage = 0.27,
        double wt_complexity = 0.30
    );
    
    // 访问候选面
    template <typename PolygonMesh>
    void output_candidate_faces(PolygonMesh& candidate_faces) const;
    
    // 错误信息
    const std::string& error_message() const;
};

内部组件

Polygonal_surface_reconstruction
    |
    +-- internal::Point_set_with_planes<GeomTraits>
    |       +-- 点云和平面信息存储
    |
    +-- internal::Hypothesis<GeomTraits>
    |       +-- 候选面生成
    |       +-- 平面相交计算
    |
    +-- internal::Candidate_confidences<GeomTraits>
            +-- 置信度计算

使用示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygonal_surface_reconstruction.h>
#include <CGAL/Shape_detection/Region_growing/Region_growing.h>
#include <CGAL/Shape_detection/Region_growing/Point_set.h>
#include <CGAL/SCIP_mixed_integer_program_traits.h>  // 或 GLPK
 
#include <vector>
#include <fstream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef boost::tuple<Point, Vector, int> PNI;  // Point, Normal, Index
typedef std::vector<PNI> Point_vector;
 
typedef CGAL::Nth_of_tuple_property_map<0, PNI> Point_map;
typedef CGAL::Nth_of_tuple_property_map<1, PNI> Normal_map;
typedef CGAL::Nth_of_tuple_property_map<2, PNI> Plane_index_map;
 
typedef CGAL::Polygonal_surface_reconstruction<Kernel> Polygonal_reconstruction;
typedef CGAL::Surface_mesh<Point> Surface_mesh;
typedef CGAL::SCIP_mixed_integer_program_traits<double> MIP_Solver;
 
int main(int argc, char* argv[])
{
    // 1. 读取点云（带法向）
    Point_vector points;
    // ... 读取代码 ...
    
    // 2. 平面检测（使用区域生长）
    // ... 区域生长代码，为每个点分配平面索引 ...
    
    // 3. 设置平面索引到点云
    for (std::size_t i = 0; i < points.size(); ++i)
        points[i].get<2>() = plane_index[i];
    
    // 4. 创建重建对象
    Polygonal_reconstruction algo(points, Point_map(), Normal_map(), Plane_index_map());
    
    // 5. 执行重建
    Surface_mesh model;
    if (\!algo.reconstruct<MIP_Solver>(model, 0.43, 0.27, 0.30)) {
        std::cerr << "Failed: " << algo.error_message() << std::endl;
        return EXIT_FAILURE;
    }
    
    // 6. 保存结果
    std::ofstream out("result.off");
    CGAL::IO::write_OFF(out, model);
    out.close();
    
    return EXIT_SUCCESS;
}

复杂度分析

步骤	复杂度	说明
候选面生成	$O (k^{3})$	$k$ 为平面数，三平面求交
邻接关系提取	$O (f \cdot k)$	$f$ 为候选面数
MIP 求解	指数级（最坏情况）	实际通常可接受

适用场景

建筑场景重建（墙面、屋顶等平面结构）
CAD 模型逆向工程
室内环境扫描
任何具有明显平面特征的对象

13.5.2 动力学曲面重建

动力学曲面重建（Kinetic Surface Reconstruction, KSR）是 CGAL 较新添加的重建方法，结合了形状检测、动力学空间划分和图割优化。

数学基础

动力学空间划分

KSR 使用动力学空间划分（Kinetic Space Partition）将空间划分为凸多面体单元：

从检测到的平面创建初始多边形
多边形沿法向”扩展”（kinetic 行为）
当多边形相交时，创建新的边和顶点
最终形成空间划分

内外标记优化

重建问题被转化为体积标记问题：

$min_{L} \sum_{v} E_{data} (v, L (v)) + λ \sum_{(u, v)} E_{smooth} (u, v) \cdot [L (u) \neq = L (v)]$

其中：

$L (v) \in {inside, outside}$ 是体积标签
$E_{data}$ 是数据项（基于点云可见性投票）
$E_{smooth}$ 是平滑项（基于面片面积）
$λ$ 平衡数据保真度和模型复杂度

使用图割（Graph Cut）算法高效求解。

架构分析

核心类

template <typename GeomTraits, typename PointRange, 
          typename PointMap, typename NormalMap, 
          typename IntersectionKernel = CGAL::Exact_predicates_exact_constructions_kernel>
class Kinetic_surface_reconstruction_3
{
public:
    using Kernel = GeomTraits;
    using Intersection_kernel = IntersectionKernel;
    using FT = typename Kernel::FT;
    using Point_3 = typename Kernel::Point_3;
    using Plane_3 = typename Kernel::Plane_3;
    using KSP = Kinetic_space_partition_3<Kernel, Intersection_kernel>;
    
    // 构造函数
    template <typename NamedParameters>
    Kinetic_surface_reconstruction_3(Point_range& points, 
                                      const NamedParameters& np = parameters::default_values());
    
    // 形状检测
    template <typename NamedParameters>
    std::size_t detect_planar_shapes(const NamedParameters& np = parameters::default_values());
    
    // 初始化划分
    template <typename NamedParameters>
    void initialize_partition(const NamedParameters& np = parameters::default_values());
    
    // 执行划分
    void partition(std::size_t k);
    
    // 联合检测和划分
    template <typename NamedParameters>
    void detection_and_partition(std::size_t k, const NamedParameters& np);
    
    // 重建（带地面检测）
    template <class OutputPointIterator, class OutputPolygonIterator>
    void reconstruct_with_ground(FT lambda, OutputPointIterator pit, OutputPolygonIterator polyit);
    
    // 重建（自定义外部节点）
    template <class OutputPointIterator, class OutputPolygonIterator>
    void reconstruct(FT lambda, std::map<typename KSP::Face_support, bool> external_nodes,
                     OutputPointIterator pit, OutputPolygonIterator polyit);
    
    // 访问检测到的形状
    const std::vector<Plane_3>& detected_planar_shapes();
    const std::vector<std::vector<std::size_t>>& detected_planar_shape_indices();
    
    // 访问划分
    const KSP& kinetic_partition() const;
};

处理流程

输入点云
    |
    v
平面形状检测（区域生长）
    |
    v
形状正则化（可选：平行、正交、共面）
    |
    v
动力学空间划分初始化
    |
    v
多边形扩展与相交处理
    |
    v
能量项设置（数据项 + 平滑项）
    |
    v
图割优化（内外标记）
    |
    v
提取标记边界作为表面
    |
    v
多边形化与输出

使用示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Kinetic_surface_reconstruction_3.h>
#include <CGAL/Point_set_3.h>
#include <CGAL/IO/read_points.h>
 
#include <vector>
#include <fstream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
typedef CGAL::Point_set_3<Point, Vector> Point_set;
 
typedef CGAL::Kinetic_surface_reconstruction_3<Kernel, 
                                                    Point_set,
                                                    Point_set::Point_map,
                                                    Point_set::Vector_map> KSR;
 
int main(int argc, char* argv[])
{
    // 1. 读取点云
    Point_set points;
    std::ifstream input((argc > 1) ? argv[1] : "input.ply");
    input >> points;
    input.close();
    
    std::cout << "Loaded " << points.size() << " points" << std::endl;
    
    // 2. 创建 KSR 对象
    KSR ksr(points,
            CGAL::parameters::point_map(points.point_map())
                             .normal_map(points.normal_map()));
    
    // 3. 检测平面形状并创建划分
    // k: 每个多边形允许的最大交点数
    std::size_t k = 10;
    ksr.detection_and_partition(k,
        CGAL::parameters::maximum_distance(0.1)
                         .maximum_angle(15.0)
                         .minimum_region_size(100)
                         .regularize_parallelism(true)
                         .regularize_orthogonality(true)
                         .regularize_coplanarity(true));
    
    std::cout << "Detected " << ksr.detected_planar_shapes().size() << " planes" << std::endl;
    std::cout << "Partition has " << ksr.kinetic_partition().number_of_volumes() << " volumes" << std::endl;
    
    // 4. 重建（带地面检测）
    FT lambda = 0.5;  // 平衡参数 [0, 1)
    std::vector<Point> output_points;
    std::vector<std::vector<std::size_t>> output_polygons;
    
    ksr.reconstruct_with_ground(lambda,
                                std::back_inserter(output_points),
                                std::back_inserter(output_polygons));
    
    // 5. 保存结果
    std::ofstream out("result.ply");
    CGAL::IO::write_PLY(out, output_points, output_polygons);
    out.close();
    
    return EXIT_SUCCESS;
}

复杂度分析

步骤	复杂度	说明
形状检测	$O (n lo g n)$	基于 k-d 树的区域生长
形状正则化	$O (k^{2})$	$k$ 为形状数
动力学划分	$O (p \cdot k)$	$p$ 为多边形数
图割优化	$O (V^{2} \cdot E)$	$V$ 为体积数， $E$ 为面片数

适用场景

大规模建筑场景重建
城市模型生成
室内环境重建
需要多边形输出的 CAD 应用

13.5.3 方法比较

特性	多边形重建	动力学重建
输入要求	平面分割 + 法向	有向点云
输出类型	多边形网格	多边形网格
水密性	是（优化保证）	是（体积标记）
平面检测	外部提供	内置
形状正则化	无	支持
地面检测	无	支持
典型应用	CAD 逆向工程	建筑/城市场景

13.5.4 选择建议

何时选择多边形重建

已有高质量的平面分割结果
需要精确控制重建权重
处理相对简单的分段平面对象
需要与特定 MIP 求解器集成

何时选择动力学重建

处理大规模建筑场景
需要自动平面检测和正则化
需要地面检测功能
希望端到端的重建流程

参考文献

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).
Oesau, S., Lafarge, F., & Alliez, P. (2023). Kinetic shape reconstruction. ACM Transactions on Graphics, 42(4), 1-15.
Chauve, A. L., Labatut, P., & Pons, J. P. (2010). Robust piecewise-planar 3D reconstruction and completion from large-scale unstructured point data. In CVPR (pp. 1261-1268).
CGAL Documentation: Polygonal Surface Reconstruction. https://doc.cgal.org/latest/Polygonal_surface_reconstruction/
CGAL Documentation: Kinetic Surface Reconstruction. https://doc.cgal.org/latest/Kinetic_surface_reconstruction/

Chunibyo

Explorer

13.5 其他曲面重建方法

13.5 其他曲面重建方法

13.5.1 多边形曲面重建

数学基础

问题定义

候选面生成

混合整数优化

架构分析

核心类

内部组件

使用示例

复杂度分析

适用场景

13.5.2 动力学曲面重建

数学基础

动力学空间划分

内外标记优化

架构分析

核心类

处理流程

使用示例

复杂度分析

适用场景

13.5.3 方法比较

13.5.4 选择建议

何时选择多边形重建

何时选择动力学重建

参考文献

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

13.5 其他曲面重建方法

13.5 其他曲面重建方法 §

13.5.1 多边形曲面重建 §

数学基础 §

问题定义 §

候选面生成 §

混合整数优化 §

架构分析 §

核心类 §

内部组件 §

使用示例 §

复杂度分析 §

适用场景 §

13.5.2 动力学曲面重建 §

数学基础 §

动力学空间划分 §

内外标记优化 §

架构分析 §

核心类 §

处理流程 §

使用示例 §

复杂度分析 §

适用场景 §

13.5.3 方法比较 §

13.5.4 选择建议 §

何时选择多边形重建 §

何时选择动力学重建 §

参考文献 §

Graph View

Table of Contents

Backlinks

13.5 其他曲面重建方法

13.5.1 多边形曲面重建

数学基础

问题定义

候选面生成

混合整数优化

架构分析

核心类

内部组件

使用示例

复杂度分析

适用场景

13.5.2 动力学曲面重建

数学基础

动力学空间划分

内外标记优化

架构分析

核心类

处理流程

使用示例

复杂度分析

适用场景

13.5.3 方法比较

13.5.4 选择建议

何时选择多边形重建

何时选择动力学重建

参考文献