15.1 网格参数化

网格参数化以 Surface_mesh 为输入数据结构，与网格处理流程紧密配合，用于生成纹理坐标和UV展开。

15.1.1 参数化是什么？

网格参数化（Surface Mesh Parameterization）是计算几何中的核心问题之一，其目标是将三维曲面映射到二维平面域上。这一过程在计算机图形学中有着广泛的应用，包括纹理映射、重新网格化、曲面拟合、细节传输等。

直观理解

想象你有一个由三角形组成的3D模型（如一个球体或一个动物模型），你希望给它”剥皮”并平铺到平面上，就像制作地图时将地球表面投影到平面上一样。这个过程就是参数化。

在数学上，参数化是一个映射函数：

$ϕ : S \subset R^{3} \to Ω \subset R^{2}$

其中 $S$ 是三维曲面， $Ω$ 是二维参数域。对于网格上的每个顶点 $v_{i}$ ，我们计算其对应的参数坐标 $(u_{i}, v_{i})$ 。

拓扑要求

CGAL中的参数化方法主要处理具有以下特性的三角网格：

2-流形（2-manifold）：网格 locally 类似于平面
可定向（Oriented）：每个面都有明确的朝向
拓扑圆盘（Homeomorphic to a disk）：网格在拓扑上等价于一个圆盘

对于不满足拓扑圆盘条件的网格（如球体或有多个边界的网格），需要先进行切割（cutting）处理，这可以通过 Seam_mesh 类来实现。

参数化的质量度量

一个好的参数化应该最小化某些失真（distortion）。主要的失真类型包括：

角度失真：参数域中的角度与原始曲面上的角度差异
面积失真：参数域中的三角形面积与原始面积的比例变化
长度失真：边长在参数化前后的变化

15.1.2 数学基础：失真度量

从3D到2D的映射

考虑一个三角形面片 $T = (p_{0}, p_{1}, p_{2})$ ，其中 $p_{i} \in R^{3}$ 。参数化将这个三角形映射到参数域中的三角形 $T^{'} = (q_{0}, q_{1}, q_{2})$ ，其中 $q_{i} = (u_{i}, v_{i}) \in R^{2}$ 。

在这个三角形内部，映射是线性的，可以用仿射变换表示：

$ϕ (x) = A x + b$

其中 $A$ 是一个 $2 \times 2$ 的雅可比矩阵（Jacobian），描述了局部变形。

奇异值分解与失真分析

对雅可比矩阵 $A$ 进行奇异值分解（SVD）：

$A = U Σ V^{T} = U (σ_{1} 0 0 σ_{2}) V^{T}$

其中 $σ_{1} \geq σ_{2} > 0$ 是奇异值。基于奇异值，我们可以定义以下失真度量：

等距失真（Isometric Distortion）：

$E_{i so} = (σ_{1} - 1)^{2} + (σ_{2} - 1)^{2}$

当 $σ_{1} = σ_{2} = 1$ 时，映射是等距的（长度保持）。

保角失真（Conformal Distortion）：

$E_{co n f} = (\frac{σ _{1}}{σ _{2}} - 1)^{2}$

当 $σ_{1} = σ_{2}$ 时，映射是保角的（角度保持）。

等积失真（Authalic Distortion）：

$E_{a u t h} = (σ_{1} σ_{2} - 1)^{2}$

当 $σ_{1} \cdot σ_{2} = 1$ 时，映射是等积的（面积保持）。

L2 Stretch 度量

Sander等人提出的L2 stretch是衡量面积失真的常用指标：

$L^{2} (S) = \sum_{T \in S} A_{T} ((\frac{σ _{1}^{2} + σ _{2}^{2}}{2}) - 1)$

其中 $A_{T}$ 是三角形 $T$ 在参数域中的归一化面积。

CGAL提供了计算L2 stretch的函数：

#include <CGAL/Surface_mesh_parameterization/measure_distortion.h>
 
double stretch = SMP::compute_L2_stretch(mesh, uv_map);

保角映射的数学基础

保角映射（Conformal Mapping）是局部保持角度的映射。在复分析框架下，可以将参数坐标表示为复数 $z = u + i v$ 。

对于三角形网格，保角条件可以表达为Cauchy-Riemann方程的离散形式。考虑一个三角形，设其在局部正交坐标系中的顶点为 $(x_{0}, y_{0}), (x_{1}, y_{1}), (x_{2}, y_{2})$ ，参数坐标为 $(u_{0}, v_{0}), (u_{1}, v_{1}), (u_{2}, v_{2})$ 。

保角条件要求：

$(z_{1} - z_{0}) (w_{2} - w_{0}) = (z_{2} - z_{0}) (w_{1} - w_{0})$

其中 $z_{k} = x_{k} + i y_{k}$ ， $w_{k} = u_{k} + i v_{k}$ 。这个方程正是LSCM方法的核心。

15.1.3 LSCM：最小二乘保形映射

算法原理

Least Squares Conformal Maps（LSCM）由Levy等人于2002年提出，是一种自由边界的保角参数化方法。与固定边界方法不同，LSCM允许边界顶点自由移动，仅通过固定至少两个顶点来消除全局自由度。

核心思想：

LSCM最小化每个三角形上的保角能量。对于每个三角形，定义能量为Cauchy-Riemann方程残差的平方：

$E_{T} = ∣ (z_{1} - z_{0}) (w_{2} - w_{0}) - (z_{2} - z_{0}) (w_{1} - w_{0}) ∣^{2}$

总能量是所有三角形能量的和：

$E_{t o t a l} = \sum_{T} E_{T}$

数学推导

将复数方程展开为实数形式。设 $z = x + i y$ ， $w = u + i v$ ，则：

$(z_{1} - z_{0}) (w_{2} - w_{0}) = [(x_{1} - x_{0}) + i (y_{1} - y_{0})] [(u_{2} - u_{0}) + i (v_{2} - v_{0})]$

展开后分离实部和虚部，得到两个实数方程：

实部方程： $(x_{1} - x_{0}) (u_{2} - u_{0}) - (y_{1} - y_{0}) (v_{2} - v_{0}) = (x_{2} - x_{0}) (u_{1} - u_{0}) - (y_{2} - y_{0}) (v_{1} - v_{0})$

虚部方程： $(x_{1} - x_{0}) (v_{2} - v_{0}) + (y_{1} - y_{0}) (u_{2} - u_{0}) = (x_{2} - x_{0}) (v_{1} - v_{0}) + (y_{2} - y_{0}) (u_{1} - u_{0})$

这些方程对每个三角形产生两个线性约束，形成最小二乘问题。

线性系统构建

LSCM构建的线性系统具有以下形式：

$A X = B$

其中：

$A$ 是一个 $(2 \times # t r ian g l es) \times (2 \times # v er t i ces)$ 的稀疏矩阵
$X$ 是未知向量，包含所有顶点的 $(u, v)$ 坐标
$B$ 是右端项，由固定顶点的约束决定

由于系统超定（方程数多于未知数），使用最小二乘法求解，等价于求解正规方程：

$A^{T} A X = A^{T} B$

矩阵 $A^{T} A$ 是对称正定的，可以使用Cholesky分解或共轭梯度法高效求解。

CGAL实现

CGAL中的 LSCM_parameterizer_3 类实现了这一算法：

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Surface_mesh_parameterization/LSCM_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Two_vertices_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/parameterize.h>
 
typedef CGAL::Simple_cartesian<double>      Kernel;
typedef Kernel::Point_2                     Point_2;
typedef Kernel::Point_3                     Point_3;
typedef CGAL::Surface_mesh<Kernel::Point_3> SurfaceMesh;
 
typedef boost::graph_traits<SurfaceMesh>::vertex_descriptor     vertex_descriptor;
typedef boost::graph_traits<SurfaceMesh>::halfedge_descriptor   halfedge_descriptor;
 
namespace SMP = CGAL::Surface_mesh_parameterization;
 
int main(int argc, char** argv)
{
  // 读取网格
  SurfaceMesh mesh;
  CGAL::IO::read_polygon_mesh(argv[1], mesh);
 
  // 获取最长边界
  halfedge_descriptor bhd = CGAL::Polygon_mesh_processing::longest_border(mesh).first;
 
  // 创建UV属性映射
  typedef SurfaceMesh::Property_map<vertex_descriptor, Point_2> UV_pmap;
  UV_pmap uv_map = mesh.add_property_map<vertex_descriptor, Point_2>("v:uv").first;
 
  // 定义边界参数化器（固定两个顶点）
  typedef SMP::Two_vertices_parameterizer_3<SurfaceMesh> Border_parameterizer;
  
  // 定义LSCM参数化器
  typedef SMP::LSCM_parameterizer_3<SurfaceMesh, Border_parameterizer> Parameterizer;
 
  // 执行参数化
  SMP::Error_code err = SMP::parameterize(mesh, Parameterizer(), bhd, uv_map);
 
  if (err != SMP::OK) {
    std::cerr << "Error: " << SMP::get_error_message(err) << std::endl;
    return EXIT_FAILURE;
  }
 
  // 输出结果
  std::ofstream out("lscm_result.off");
  SMP::IO::output_uvmap_to_off(mesh, bhd, uv_map, out);
 
  return EXIT_SUCCESS;
}

完整示例：带接缝的LSCM参数化

对于复杂拓扑（如球体），需要先切割网格：

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/Seam_mesh.h>
#include <CGAL/Surface_mesh_parameterization/LSCM_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Two_vertices_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/parameterize.h>
#include <CGAL/Surface_mesh_parameterization/IO/File_off.h>
 
typedef CGAL::Simple_cartesian<double>      Kernel;
typedef Kernel::Point_2                     Point_2;
typedef Kernel::Point_3                     Point_3;
typedef CGAL::Surface_mesh<Kernel::Point_3> SurfaceMesh;
 
typedef boost::graph_traits<SurfaceMesh>::edge_descriptor       SM_edge_descriptor;
typedef boost::graph_traits<SurfaceMesh>::halfedge_descriptor   SM_halfedge_descriptor;
typedef boost::graph_traits<SurfaceMesh>::vertex_descriptor     SM_vertex_descriptor;
 
typedef SurfaceMesh::Property_map<SM_halfedge_descriptor, Point_2> UV_pmap;
typedef SurfaceMesh::Property_map<SM_edge_descriptor, bool>       Seam_edge_pmap;
typedef SurfaceMesh::Property_map<SM_vertex_descriptor, bool>     Seam_vertex_pmap;
 
typedef CGAL::Seam_mesh<SurfaceMesh, Seam_edge_pmap, Seam_vertex_pmap> Mesh;
typedef boost::graph_traits<Mesh>::halfedge_descriptor            halfedge_descriptor;
typedef boost::graph_traits<Mesh>::vertex_descriptor              vertex_descriptor;
 
namespace SMP = CGAL::Surface_mesh_parameterization;
 
int main(int argc, char** argv)
{
  const std::string filename = (argc > 1) ? argv[1] : "data/lion.off";
  const char* selection_file = (argc > 2) ? argv[2] : "data/lion.selection.txt";
 
  SurfaceMesh sm;
  if (!CGAL::IO::read_polygon_mesh(filename, sm)) {
    std::cerr << "Invalid input file." << std::endl;
    return EXIT_FAILURE;
  }
 
  // 创建接缝属性映射
  Seam_edge_pmap seam_edge_pm = sm.add_property_map<SM_edge_descriptor, bool>("e:on_seam", false).first;
  Seam_vertex_pmap seam_vertex_pm = sm.add_property_map<SM_vertex_descriptor, bool>("v:on_seam", false).first;
 
  // 创建Seam_mesh并添加接缝
  Mesh mesh(sm, seam_edge_pm, seam_vertex_pm);
  SM_halfedge_descriptor smhd = mesh.add_seams(selection_file);
  
  if (smhd == SM_halfedge_descriptor()) {
    std::cerr << "Warning: No seams in input" << std::endl;
  }
 
  // UV属性映射（存储在原始网格的半边）
  UV_pmap uv_pm = sm.add_property_map<SM_halfedge_descriptor, Point_2>("h:uv").first;
 
  // 获取边界半边
  halfedge_descriptor bhd = CGAL::Polygon_mesh_processing::longest_border(mesh).first;
 
  // 配置参数化器
  typedef SMP::Two_vertices_parameterizer_3<Mesh>               Border_parameterizer;
  typedef SMP::LSCM_parameterizer_3<Mesh, Border_parameterizer> Parameterizer;
 
  // 执行参数化
  SMP::Error_code err = SMP::parameterize(mesh, Parameterizer(), bhd, uv_pm);
 
  if (err != SMP::OK) {
    std::cerr << "Error: " << SMP::get_error_message(err) << std::endl;
    return EXIT_FAILURE;
  }
 
  // 输出结果
  std::ofstream out("lscm_seam_result.off");
  SMP::IO::output_uvmap_to_off(mesh, bhd, uv_pm, out);
 
  return EXIT_SUCCESS;
}

LSCM的特点

优点：

自由边界，允许边界自然演化以获得更低的角度失真
求解对称正定系统，数值稳定
计算效率高，只需解一个线性系统

缺点：

不保证双射（可能出现三角形翻转）
需要固定至少两个顶点
对于复杂模型可能需要切割

15.1.4 ARAP：尽可能刚性

算法原理

As-Rigid-As-Possible（ARAP）参数化由Liu等人于2008年提出，是一种基于能量最小化的形状保持方法。ARAP试图在保持局部刚性的同时，将曲面展平到平面上。

核心思想：

对于每个三角形，定义一个局部最优的刚性变换（旋转+平移），然后全局缝合这些局部变换以获得一致的参数化。这是一个交替优化过程：

局部阶段：固定参数坐标，为每个三角形计算最优刚性变换
全局阶段：固定刚性变换，求解全局一致的参数坐标

数学推导

能量函数：

ARAP最小化以下能量：

$E = \sum_{t} A_{t} ∥ J_{t} - R_{t} ∥_{F}^{2}$

其中：

$A_{t}$ 是三角形 $t$ 的面积
$J_{t}$ 是三角形 $t$ 的雅可比矩阵
$R_{t}$ 是旋转矩阵（ $R_{t}^{T} R_{t} = I$ ， $det (R_{t}) = 1$ ）
$∥ \cdot ∥_{F}$ 是Frobenius范数

广义能量：

ARAP引入参数 $λ$ 来平衡角度和形状保持：

$E = \sum_{t} A_{t} [(1 - λ) J_{t}^{i so} - R_{t}_{F}^{2} + λ ∥ J_{t} - R_{t} ∥_{F}^{2}]$

其中 $J_{t}^{i so}$ 是 $J_{t}$ 的等距部分（缩放被归一化）。

当 $λ = 0$ ：ASAP（As-Similar-As-Possible），等价于LSCM
当 $λ \to \infty$ ：ARAP（As-Rigid-As-Possible）

局部优化

对于每个三角形，给定当前参数坐标，最优旋转 $R_{t}$ 可以通过极分解（Polar Decomposition）计算：

$J_{t} = U Σ V^{T} \Rightarrow R_{t} = U V^{T}$

在CGAL实现中，这转化为求解一个三次方程来确定变换矩阵的元素。

全局优化

固定所有局部旋转后，全局阶段求解一个稀疏线性系统。使用余切权重（cotangent weights）：

$w_{ij} = cot α_{ij} + cot β_{ij}$

其中 $α_{ij}$ 和 $β_{ij}$ 是边 $(i, j)$ 对面的两个角。

全局系统形式为：

$\sum_{j \in N (i)} w_{ij} (q_{i} - q_{j}) = \sum_{j \in N (i)} w_{ij} R_{t_{ij}} (p_{i} - p_{j})$

其中 $p$ 是3D位置， $q$ 是2D参数坐标， $R_{t_{ij}}$ 是包含边 $(i, j)$ 的三角形的旋转。

CGAL实现

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Surface_mesh_parameterization/ARAP_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/parameterize.h>
#include <CGAL/Surface_mesh_parameterization/IO/File_off.h>
 
typedef CGAL::Simple_cartesian<double>       Kernel;
typedef Kernel::Point_2                      Point_2;
typedef Kernel::Point_3                      Point_3;
typedef CGAL::Surface_mesh<Kernel::Point_3>  SurfaceMesh;
 
typedef boost::graph_traits<SurfaceMesh>::vertex_descriptor     vertex_descriptor;
typedef boost::graph_traits<SurfaceMesh>::halfedge_descriptor   halfedge_descriptor;
 
namespace SMP = CGAL::Surface_mesh_parameterization;
 
int main(int argc, char** argv)
{
  const std::string filename = (argc > 1) ? argv[1] : "data/head.off";
 
  SurfaceMesh mesh;
  if (!CGAL::IO::read_polygon_mesh(filename, mesh)) {
    std::cerr << "Invalid input file." << std::endl;
    return EXIT_FAILURE;
  }
 
  // 获取最长边界
  halfedge_descriptor bhd = CGAL::Polygon_mesh_processing::longest_border(mesh).first;
 
  // 创建UV属性映射
  typedef SurfaceMesh::Property_map<vertex_descriptor, Point_2> UV_pmap;
  UV_pmap uv_map = mesh.add_property_map<vertex_descriptor, Point_2>("v:uv").first;
 
  // 创建ARAP参数化器
  // lambda = 1000.0 表示强调形状保持
  // iterations = 50 表示最大迭代次数
  // tolerance = 1e-6 表示能量收敛阈值
  SMP::ARAP_parameterizer_3<SurfaceMesh> parameterizer(
    SMP::Two_vertices_parameterizer_3<SurfaceMesh>(),  // 边界参数化器
    CGAL::Default(),                                   // 求解器（默认Eigen）
    1000.0,                                            // lambda
    50,                                                // 最大迭代次数
    1e-6                                               // 收敛容差
  );
 
  // 执行参数化
  SMP::Error_code err = SMP::parameterize(mesh, parameterizer, bhd, uv_map);
 
  if (err != SMP::OK) {
    std::cerr << "Error: " << SMP::get_error_message(err) << std::endl;
    return EXIT_FAILURE;
  }
 
  // 输出结果
  std::ofstream out("arap_result.off");
  SMP::IO::output_uvmap_to_off(mesh, bhd, uv_map, out);
 
  return EXIT_SUCCESS;
}

迭代过程可视化

ARAP的迭代特性允许我们观察参数化的渐进改善：

// 启用调试输出
#define CGAL_SMP_ARAP_DEBUG
#define CGAL_PARAMETERIZATION_ARAP_VERBOSE
 
// 在迭代过程中，ARAP会输出中间结果
// ARAP_initial_param.off - 初始参数化（MVC或LSCM）
// ARAP_iteration_1.off, ARAP_iteration_2.off, ... - 中间结果
// ARAP_final_pre_processing.off - 最终迭代结果
// ARAP_final_post_processing.off - 后处理结果（如果有翻转）

ARAP的特点

优点：

平衡角度和形状保持，视觉效果更好
通过迭代优化，结果质量高于单次求解方法
包含后处理步骤处理翻转

缺点：

计算成本较高（需要多次求解线性系统）
不保证双射
参数选择（lambda、迭代次数）需要经验

15.1.5 边界条件处理

固定边界 vs 自由边界

参数化方法根据边界处理方式可分为两类：

固定边界（Fixed Border）：

边界顶点被约束到预定义的凸多边形（圆、正方形）
保证双射（当权重为正时）
示例：Tutte重心映射、Floater均值坐标、离散保角映射

自由边界（Free Border）：

边界顶点自由移动
需要固定至少两个顶点消除全局自由度
不保证双射，但通常失真更低
示例：LSCM、ARAP

边界参数化器

CGAL提供了多种边界参数化策略：

圆形边界：

// 弧长参数化（默认）
typedef SMP::Circular_border_arc_length_parameterizer_3<SurfaceMesh> Border_param;
 
// 均匀参数化
typedef SMP::Circular_border_uniform_parameterizer_3<SurfaceMesh> Border_param;

正方形边界：

// 弧长参数化
typedef SMP::Square_border_arc_length_parameterizer_3<SurfaceMesh> Border_param;
 
// 均匀参数化
typedef SMP::Square_border_uniform_parameterizer_3<SurfaceMesh> Border_param;

两点参数化（自由边界）：

typedef SMP::Two_vertices_parameterizer_3<SurfaceMesh> Border_param;

凸组合条件

Tutte定理指出：如果边界映射到凸多边形，且每个内部顶点是其邻居的凸组合，则参数化是双射的。

数学上，对于内部顶点 $v_{i}$ ：

$q_{i} = \sum_{j \in N (i)} w_{ij} q_{j}, \sum_{j} w_{ij} = 1, w_{ij} > 0$

满足这一条件的方法包括：

Tutte重心映射（均匀权重）
Floater均值坐标（正权重）

不满足的方法（可能产生翻转）：

离散保角映射（余切权重可能为负）
离散等积映射
LSCM、ARAP（自由边界）

切割与接缝处理

对于非拓扑圆盘网格，需要先切割：

Seam_mesh 的使用：

#include <CGAL/boost/graph/Seam_mesh.h>
 
// 定义属性映射
typedef SurfaceMesh::Property_map<SM_edge_descriptor, bool> Seam_edge_pmap;
typedef SurfaceMesh::Property_map<SM_vertex_descriptor, bool> Seam_vertex_pmap;
 
Seam_edge_pmap seam_edge_pm = sm.add_property_map<SM_edge_descriptor, bool>("e:on_seam", false).first;
Seam_vertex_pmap seam_vertex_pm = sm.add_property_map<SM_vertex_descriptor, bool>("v:on_seam", false).first;
 
// 创建Seam_mesh
typedef CGAL::Seam_mesh<SurfaceMesh, Seam_edge_pmap, Seam_vertex_pmap> Mesh;
Mesh mesh(sm, seam_edge_pm, seam_vertex_pm);
 
// 从文件加载接缝
SM_halfedge_descriptor smhd = mesh.add_seams("selection.txt");

接缝文件格式：

接缝文件是一个文本文件，每行包含两个顶点索引，表示一条接缝边：

切割策略：

最长边界扩展：从最长边界开始，延伸到覆盖整个网格
最短路径切割：在锥形（cones）之间寻找最短路径
用户指定：手动选择切割线

Orbifold Tutte嵌入

对于球面拓扑，Orbifold Tutte嵌入提供了一种无需显式切割的参数化方法：

#include <CGAL/Surface_mesh_parameterization/Orbifold_Tutte_parameterizer_3.h>
 
// 定义锥形类型
typedef SMP::Orbifold_Tutte_parameterizer_3<Mesh> Parameterizer;
 
// 选择4个锥形并指定类型IV orbifold
SMP::Error_code err = SMP::parameterize(mesh, 
  Parameterizer(SMP::Orbifold_type::IV, cone_vertices), bhd, uv_map);

Orbifold Tutte保证全局双射，适用于球面参数化。

15.1.6 完整代码实现

综合示例：比较不同参数化方法

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Timer.h>
 
// 参数化方法
#include <CGAL/Surface_mesh_parameterization/Barycentric_mapping_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Discrete_conformal_map_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Mean_value_coordinates_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Discrete_authalic_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/LSCM_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/ARAP_parameterizer_3.h>
 
// 边界参数化器
#include <CGAL/Surface_mesh_parameterization/Circular_border_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Square_border_parameterizer_3.h>
#include <CGAL/Surface_mesh_parameterization/Two_vertices_parameterizer_3.h>
 
#include <CGAL/Surface_mesh_parameterization/parameterize.h>
#include <CGAL/Surface_mesh_parameterization/measure_distortion.h>
#include <CGAL/Surface_mesh_parameterization/IO/File_off.h>
 
#include <iostream>
#include <fstream>
#include <string>
 
typedef CGAL::Simple_cartesian<double>       Kernel;
typedef Kernel::Point_2                      Point_2;
typedef Kernel::Point_3                      Point_3;
typedef CGAL::Surface_mesh<Kernel::Point_3>  SurfaceMesh;
 
typedef boost::graph_traits<SurfaceMesh>::vertex_descriptor     vertex_descriptor;
typedef boost::graph_traits<SurfaceMesh>::halfedge_descriptor   halfedge_descriptor;
 
namespace SMP = CGAL::Surface_mesh_parameterization;
 
// 模板函数：应用参数化并测量
template <typename Parameterizer>
void apply_parameterization(SurfaceMesh& mesh, 
                           halfedge_descriptor bhd,
                           Parameterizer& parameterizer,
                           const std::string& name)
{
  // 创建UV映射
  typedef SurfaceMesh::Property_map<vertex_descriptor, Point_2> UV_pmap;
  UV_pmap uv_map = mesh.add_property_map<vertex_descriptor, Point_2>("v:uv").first;
 
  CGAL::Timer timer;
  timer.start();
 
  // 执行参数化
  SMP::Error_code err = SMP::parameterize(mesh, parameterizer, bhd, uv_map);
 
  timer.stop();
 
  if (err != SMP::OK) {
    std::cerr << name << " failed: " << SMP::get_error_message(err) << std::endl;
    return;
  }
 
  // 计算失真
  double stretch = SMP::compute_L2_stretch(mesh, uv_map);
 
  std::cout << name << ":" << std::endl;
  std::cout << "  Time: " << timer.time() << " seconds" << std::endl;
  std::cout << "  L2 Stretch: " << stretch << std::endl;
 
  // 保存结果
  std::ofstream out(name + "_result.off");
  SMP::IO::output_uvmap_to_off(mesh, bhd, uv_map, out);
}
 
int main(int argc, char** argv)
{
  const std::string filename = (argc > 1) ? argv[1] : "data/nefertiti.off";
 
  // 读取网格
  SurfaceMesh mesh;
  if (!CGAL::IO::read_polygon_mesh(filename, mesh)) {
    std::cerr << "Cannot read: " << filename << std::endl;
    return EXIT_FAILURE;
  }
 
  std::cout << "Mesh: " << num_vertices(mesh) << " vertices, "
            << num_faces(mesh) << " faces" << std::endl;
 
  // 获取边界
  halfedge_descriptor bhd = CGAL::Polygon_mesh_processing::longest_border(mesh).first;
 
  // 1. Tutte Barycentric Mapping（圆形边界）
  {
    SurfaceMesh mesh_copy = mesh;
    typedef SMP::Circular_border_arc_length_parameterizer_3<SurfaceMesh> Border;
    typedef SMP::Barycentric_mapping_parameterizer_3<SurfaceMesh, Border> Param;
    Param parameterizer;
    apply_parameterization(mesh_copy, bhd, parameterizer, "Tutte");
  }
 
  // 2. Floater Mean Value Coordinates（圆形边界）
  {
    SurfaceMesh mesh_copy = mesh;
    typedef SMP::Circular_border_arc_length_parameterizer_3<SurfaceMesh> Border;
    typedef SMP::Mean_value_coordinates_parameterizer_3<SurfaceMesh, Border> Param;
    Param parameterizer;
    apply_parameterization(mesh_copy, bhd, parameterizer, "Floater_MVC");
  }
 
  // 3. Discrete Conformal Map（圆形边界）
  {
    SurfaceMesh mesh_copy = mesh;
    typedef SMP::Circular_border_arc_length_parameterizer_3<SurfaceMesh> Border;
    typedef SMP::Discrete_conformal_map_parameterizer_3<SurfaceMesh, Border> Param;
    Param parameterizer;
    apply_parameterization(mesh_copy, bhd, parameterizer, "Discrete_Conformal");
  }
 
  // 4. Discrete Authalic（圆形边界）
  {
    SurfaceMesh mesh_copy = mesh;
    typedef SMP::Circular_border_arc_length_parameterizer_3<SurfaceMesh> Border;
    typedef SMP::Discrete_authalic_parameterizer_3<SurfaceMesh, Border> Param;
    Param parameterizer;
    apply_parameterization(mesh_copy, bhd, parameterizer, "Discrete_Authalic");
  }
 
  // 5. LSCM（自由边界）
  {
    SurfaceMesh mesh_copy = mesh;
    typedef SMP::Two_vertices_parameterizer_3<SurfaceMesh> Border;
    typedef SMP::LSCM_parameterizer_3<SurfaceMesh, Border> Param;
    Param parameterizer;
    apply_parameterization(mesh_copy, bhd, parameterizer, "LSCM");
  }
 
  // 6. ARAP（自由边界）
  {
    SurfaceMesh mesh_copy = mesh;
    SMP::ARAP_parameterizer_3<SurfaceMesh> parameterizer(
      SMP::Two_vertices_parameterizer_3<SurfaceMesh>(),
      CGAL::Default(),
      1000.0,    // lambda
      50,        // iterations
      1e-6       // tolerance
    );
    apply_parameterization(mesh_copy, bhd, parameterizer, "ARAP");
  }
 
  return EXIT_SUCCESS;
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.12...3.31)
project(Mesh_Parameterization_Examples)
 
find_package(CGAL REQUIRED OPTIONAL_COMPONENTS Core)
 
if(NOT CGAL_FOUND)
  message(FATAL_ERROR "CGAL is required")
endif()
 
# 查找Eigen（用于求解线性系统）
find_package(Eigen3 3.1.0 QUIET)
if(EIGEN3_FOUND)
  include(CGAL_Eigen3_support)
else()
  message(WARNING "Eigen3 not found. Some examples will not compile.")
endif()
 
if(TARGET CGAL::Eigen3_support)
  # 简单参数化示例
  create_single_source_cgal_program("simple_parameterization.cpp")
  target_link_libraries(simple_parameterization PRIVATE CGAL::Eigen3_support)
 
  # LSCM示例
  create_single_source_cgal_program("lscm_example.cpp")
  target_link_libraries(lscm_example PRIVATE CGAL::Eigen3_support)
 
  # ARAP示例
  create_single_source_cgal_program("arap_example.cpp")
  target_link_libraries(arap_example PRIVATE CGAL::Eigen3_support)
 
  # 比较示例
  create_single_source_cgal_program("compare_methods.cpp")
  target_link_libraries(compare_methods PRIVATE CGAL::Eigen3_support)
endif()

15.1.7 纹理映射应用

UV坐标的生成与使用

参数化的主要应用之一是纹理映射。生成的UV坐标可以用于：

2D纹理采样：从图像中采样颜色
法线贴图：添加表面细节
环境光遮蔽：预计算光照信息
位移贴图：几何细节增强

纹理坐标归一化

参数化结果通常需要归一化到 $[0, 1]$ 范围：

// 计算边界框
Point_2 min_uv(CGAL::ORIGIN), max_uv(CGAL::ORIGIN);
bool first = true;
for (vertex_descriptor v : vertices(mesh)) {
  Point_2 uv = get(uv_map, v);
  if (first) {
    min_uv = max_uv = uv;
    first = false;
  } else {
    min_uv = Point_2(std::min(min_uv.x(), uv.x()), std::min(min_uv.y(), uv.y()));
    max_uv = Point_2(std::max(max_uv.x(), uv.x()), std::max(max_uv.y(), uv.y()));
  }
}
 
// 归一化
for (vertex_descriptor v : vertices(mesh)) {
  Point_2 uv = get(uv_map, v);
  double u = (uv.x() - min_uv.x()) / (max_uv.x() - min_uv.x());
  double v_coord = (uv.y() - min_uv.y()) / (max_uv.y() - min_uv.y());
  put(uv_map, v, Point_2(u, v_coord));
}

纹理Atlas打包

对于复杂模型，通常需要将其分割为多个图表（charts），每个图表单独参数化，然后打包到纹理atlas中：

// 伪代码：纹理atlas打包
void pack_atlas(const std::vector<SurfaceMesh>& charts, 
                std::vector<UV_pmap>& uv_maps,
                int texture_size)
{
  // 1. 对每个chart进行参数化
  // 2. 归一化UV坐标到[0,1]
  // 3. 计算每个chart的包围盒
  // 4. 使用矩形打包算法（如MAXRECTS）排列charts
  // 5. 更新UV坐标到最终atlas位置
}

实际渲染示例

以下是将CGAL参数化结果导出为OBJ格式（包含纹理坐标）的代码：

#include <CGAL/Surface_mesh.h>
#include <fstream>
 
void export_obj_with_uv(const SurfaceMesh& mesh,
                       const UV_pmap& uv_map,
                       const std::string& filename)
{
  std::ofstream out(filename);
  
  // 写入顶点
  for (vertex_descriptor v : vertices(mesh)) {
    Point_3 p = get(get(CGAL::vertex_point, mesh), v);
    out << "v " << p.x() << " " << p.y() << " " << p.z() << "\n";
  }
  
  // 写入纹理坐标
  for (vertex_descriptor v : vertices(mesh)) {
    Point_2 uv = get(uv_map, v);
    out << "vt " << uv.x() << " " << uv.y() << "\n";
  }
  
  // 写入面（使用顶点索引和纹理坐标索引）
  for (face_descriptor f : faces(mesh)) {
    out << "f";
    for (vertex_descriptor v : vertices_around_face(halfedge(f, mesh), mesh)) {
      int idx = get(get(boost::vertex_index, mesh), v) + 1;  // OBJ使用1-based索引
      out << " " << idx << "/" << idx;
    }
    out << "\n";
  }
}

可视化纹理映射结果

参数化质量可以通过棋盘格纹理可视化：

// 生成棋盘格纹理图像
void generate_checkerboard(const std::string& filename, int size = 512)
{
  std::ofstream out(filename, std::ios::binary);
  
  // BMP文件头（简化版本）
  // ...
  
  for (int y = 0; y < size; ++y) {
    for (int x = 0; x < size; ++x) {
      int check = ((x / 32) + (y / 32)) % 2;
      unsigned char color = check ? 255 : 0;
      out << color << color << color;
    }
  }
}

当纹理映射正确时，棋盘格应该均匀分布，没有明显扭曲；如果存在拉伸，格子会变得不均匀；如果出现翻转，纹理会显示为镜像。

15.1.8 方法对比与选择

参数化方法对比表

方法	边界类型	双射保证	最小化目标	求解器类型	适用场景
Tutte重心映射	固定凸边界	是（正权重）	无特定目标	稀疏线性系统	需要保证双射的基础参数化
Floater均值坐标	固定凸边界	是	角度失真（近似）	稀疏线性系统	质量优于Tutte，仍保证双射
离散保角映射	固定凸边界	否（余切可能负）	角度失真	稀疏线性系统	角度保持优先
离散等积映射	固定凸边界	否	面积失真	稀疏线性系统	面积保持优先
迭代等积映射	固定凸边界	否	L2 stretch	迭代优化	高质量面积保持
LSCM	自由	否	角度失真	最小二乘	角度保持，允许自由边界
ARAP	自由	否	角度+形状	交替优化	高质量形状保持
Orbifold Tutte	无（球面）	是	无特定目标	稀疏线性系统	球面拓扑，无缝参数化

选择指南

需要保证双射时：

简单应用：Tutte重心映射
更好质量：Floater均值坐标
球面拓扑：Orbifold Tutte

角度保持优先：

快速：离散保角映射（固定边界）
更好质量：LSCM（自由边界）

形状保持优先：

使用ARAP，调整lambda参数

面积保持优先：

离散等积映射
迭代等积映射（更高质量）

性能对比

方法	时间复杂度	内存使用	预处理要求
Tutte	$O (n^{1.5})$	低	无
Floater	$O (n^{1.5})$	低	无
离散保角	$O (n^{1.5})$	中	无
LSCM	$O (n^{1.5})$	中	无
ARAP	$O (k \cdot n^{1.5})$	高	需要初始参数化
Orbifold	$O (n^{1.5})$	中	需要选择锥形

其中 $n$ 是顶点数， $k$ 是ARAP迭代次数。

常见问题与解决方案

问题1：参数化失败（ERROR_CANNOT_SOLVE_LINEAR_SYSTEM）

可能原因：

网格有孔洞或拓扑问题
矩阵奇异（边界条件不足）

解决方案：

检查网格拓扑
使用不同的边界参数化器
添加更多约束

问题2：结果有翻转（三角形方向反转）

可能原因：

自由边界方法不保证双射
输入网格有复杂几何

解决方案：

使用固定边界方法
启用ARAP的后处理
手动切割网格

问题3：边界扭曲严重

解决方案：

使用自由边界方法（LSCM、ARAP）
调整边界形状（正方形vs圆形）
使用迭代等积映射重新分布stretch

15.1.9 本章小结

网格参数化是将三维曲面映射到二维平面的核心技术。本章介绍了CGAL中实现的主要参数化方法：

数学基础：理解了失真度量（角度、面积、长度）和保角映射的数学原理。
LSCM：一种自由边界的保角参数化方法，通过最小二乘求解Cauchy-Riemann方程，适合角度保持应用。
ARAP：一种交替优化方法，平衡角度和形状保持，通过局部-全局迭代获得高质量参数化。
边界处理：了解了固定边界vs自由边界的区别，以及如何使用Seam_mesh处理复杂拓扑。
实际应用：学习了如何将参数化结果用于纹理映射，包括UV坐标归一化和纹理atlas打包。

CGAL的Surface_mesh_parameterization包提供了丰富的参数化方法，通过统一的接口可以方便地切换不同算法。选择合适的方法需要根据应用需求（双射保证、失真类型、计算效率）进行权衡。

15.1.10 练习

练习1：基础参数化

编写程序加载一个OFF格式的三角网格，分别使用Tutte重心映射和LSCM进行参数化，比较两者的运行时间和视觉结果。

提示：

使用 CGAL::Polygon_mesh_processing::longest_border 获取边界
使用 SMP::IO::output_uvmap_to_off 输出结果

练习2：失真分析

实现一个程序，计算并比较不同参数化方法的以下指标：

L2 stretch
最大角度失真
面积失真比例

提示：使用 SMP::compute_L2_stretch 和自定义函数计算其他指标。

练习3：ARAP参数调优

实验ARAP的lambda参数对结果的影响：

使用lambda = 0（ASAP）
使用lambda = 1, 10, 100, 1000, 10000
记录每种情况下的能量收敛曲线和最终失真

问题：对于你的测试模型，哪个lambda值给出了最佳视觉效果？

练习4：纹理映射

创建一个完整的纹理映射管线：

加载3D模型并参数化
生成棋盘格纹理
导出带UV坐标的OBJ文件
在3D查看器（如Blender或MeshLab）中验证结果

扩展：尝试使用真实纹理图像，观察不同参数化方法对纹理质量的影响。

练习5：球面参数化

使用Orbifold Tutte嵌入对一个封闭球面模型（如ico sphere）进行参数化：

选择4个锥形顶点（尽量均匀分布）
使用 Orbifold_Tutte_parameterizer_3 进行参数化
比较Orbifold结果与切割后使用LSCM的结果

问题：Orbifold Tutte的主要优势是什么？

练习6：接缝优化

实现一个自动切割算法：

找到模型的最长边界（如果存在）
如果没有边界，找到一对距离最远的顶点
计算它们之间的最短路径作为切割线
使用Seam_mesh应用切割并参数化

提示：使用 CGAL::Polygon_mesh_processing::shortest_path 计算最短路径。

参考文献：

Levy, B., Petitjean, S., Ray, N., & Maillot, J. (2002). Least squares conformal maps for automatic texture atlas generation. ACM SIGGRAPH.
Liu, L., Zhang, L., Xu, Y., Gotsman, C., & Gortler, S. J. (2008). A local/global approach to mesh parameterization. Computer Graphics Forum.
Floater, M. S. (2003). Mean value coordinates. Computer Aided Geometric Design.
Tutte, W. T. (1963). How to draw a graph. Proceedings of the London Mathematical Society.
Desbrun, M., Meyer, M., & Alliez, P. (2002). Intrinsic parameterizations of surface meshes. Computer Graphics Forum.
Sander, P. V., Snyder, J., Gortler, S. J., & Hoppe, H. (2001). Texture mapping progressive meshes. ACM SIGGRAPH.
Aigerman, N., & Lipman, Y. (2015). Orbifold Tutte embeddings. ACM Transactions on Graphics.

Chunibyo

Explorer

15.1 网格参数化

15.1 网格参数化 §

15.1.1 参数化是什么？ §

直观理解 §

拓扑要求 §

参数化的质量度量 §

15.1.2 数学基础：失真度量 §

从3D到2D的映射 §

奇异值分解与失真分析 §

L2 Stretch 度量 §

保角映射的数学基础 §

15.1.3 LSCM：最小二乘保形映射 §

算法原理 §

数学推导 §

线性系统构建 §

CGAL实现 §

完整示例：带接缝的LSCM参数化 §

LSCM的特点 §

15.1.4 ARAP：尽可能刚性 §

算法原理 §

数学推导 §

局部优化 §

全局优化 §

CGAL实现 §

迭代过程可视化 §

ARAP的特点 §

15.1.5 边界条件处理 §

固定边界 vs 自由边界 §

边界参数化器 §

凸组合条件 §

切割与接缝处理 §

Orbifold Tutte嵌入 §

15.1.6 完整代码实现 §

综合示例：比较不同参数化方法 §

CMakeLists.txt §

15.1.7 纹理映射应用 §

UV坐标的生成与使用 §

纹理坐标归一化 §

纹理Atlas打包 §

实际渲染示例 §

可视化纹理映射结果 §

15.1.8 方法对比与选择 §

参数化方法对比表 §

选择指南 §

性能对比 §

常见问题与解决方案 §

15.1.9 本章小结 §

15.1.10 练习 §

练习1：基础参数化 §

练习2：失真分析 §

练习3：ARAP参数调优 §

练习4：纹理映射 §

练习5：球面参数化 §

练习6：接缝优化 §

Graph View

Table of Contents

Backlinks

15.1 网格参数化

15.1.1 参数化是什么？

直观理解

拓扑要求

参数化的质量度量

15.1.2 数学基础：失真度量

从3D到2D的映射

奇异值分解与失真分析

L2 Stretch 度量

保角映射的数学基础

15.1.3 LSCM：最小二乘保形映射

算法原理

数学推导

线性系统构建

CGAL实现

完整示例：带接缝的LSCM参数化

LSCM的特点

15.1.4 ARAP：尽可能刚性

算法原理

数学推导

局部优化

全局优化

CGAL实现

迭代过程可视化

ARAP的特点

15.1.5 边界条件处理

固定边界 vs 自由边界

边界参数化器

凸组合条件

切割与接缝处理

Orbifold Tutte嵌入

15.1.6 完整代码实现

综合示例：比较不同参数化方法

CMakeLists.txt

15.1.7 纹理映射应用

UV坐标的生成与使用

纹理坐标归一化

纹理Atlas打包

实际渲染示例

可视化纹理映射结果

15.1.8 方法对比与选择

参数化方法对比表

选择指南

性能对比

常见问题与解决方案

15.1.9 本章小结

15.1.10 练习

练习1：基础参数化

练习2：失真分析

练习3：ARAP参数调优

练习4：纹理映射

练习5：球面参数化

练习6：接缝优化