骨架分解与 Polycube 参数化

2026/05/20 14:00:00

课程等几何分析·12 min read

等几何分析骨架分解 Polycube 参数化课程笔记

# 第 5 讲：骨架分解与 Polycube 参数化

GAMES302 · 高级图形学与增强现实

授课教师：iGame Lab · 浙江大学

---

背景：从边界参数化到骨架分解

第 4 讲讨论了如何将给定的区域边界曲线转化为参数化曲面。核心挑战在于：复杂拓扑区域（多连通、带孔、任意拓扑）的参数化无法靠单块 Bézier 曲面完成。

本讲引入两条互补的技术路线：

骨架（Skeleton）分解：利用区域骨架将复杂区域先切分为若干子区域，再对每个子区域独立参数化。

Polycube / Polysquare 方法：将三维模型映射到轴对齐的立方体堆叠结构，从而生成 IGA 友好的块划分。

多立方体切片与块结构生成

闭合形式 Polysquare 结果

两条路线的共同目标是：减少内部奇异点、降低参数化畸变、生成 IGA 可用的多块结构。

---

骨架分解（Skeleton-based Domain Decomposition）

1 骨架的定义

定义（Skeleton）：给定二维区域 $$D$$ ，其骨架定义为满足下式的点集：

S(D) = \{ p \in D \mid \exists \text{ skeleton circle } C \subset D, \ p \in \text{center}(C), \ C \text{ 至少与边界 } B \text{ 相切于两点} \}

所谓 skeleton circle，是内含于区域 $$D$$ 且与边界 $$B$$ 至少切于两点的圆。骨架就是这些圆圆心的轨迹。骨架天然具有以下性质：

在分叉点（branch point）处，骨架为 Y 形或 T 形，对应区域的关键拓扑结构。

骨架的每条分支连接区域中两个边界点，天然适合作为分割曲线（segmentation curves）的候选路径。

骨架提取与域分解流程

2 基于骨架的四边形分割

骨架分解的核心步骤如下：

计算骨架：提取区域骨架，得到所有分支点和分割曲线候选路径。

确定分割点：对每个骨架分支点 $$P$$ ，取与其相切的两条边界曲线的切点 $$P_1, P_2$$ 作为边界上的分割点。

构造分割曲线：以骨架分支为引导线，连接边界分割点，形成区域内部的分割曲线。

子区域参数化：对分割后的每个子区域（现已成为单连通四边形块），使用第 4 讲方法独立参数化。

骨架方法的优势在于：骨架几何本身就编码了区域的拓扑信息，无需额外构造标架场；但其缺点是对复杂拓扑区域（如孔洞密集），骨架本身可能非常复杂，导致大量子区域。

---

复杂平面区域的全自动参数化框架

1 整体框架

课程给出了一套针对任意拓扑平面域的全自动参数化框架，流程分四步：

预处理（Pre-processing）：对输入的边界样条曲线做 Bézier 提取与细分，去除凹形不利于参数化的部分。

拓扑信息生成（Topology Generation）：将多连通区域转化为单连通区域，做近似凸分解，生成四边形网格拓扑。

全局优化分块（Global Optimization）：以四边形网格边为候选分割曲线，通过全局优化找到最优的曲线形状与块数。

高质量块参数化（Local Optimization）：对每个四边形块分别建立 Bézier 曲面参数化。

2 拓扑生成详解

离散边界：将提取的 Bézier 曲线端点相连，得到多边形离散边界。

多连通 → 单连通：对于带孔区域（multiply-connected），通过添加"虚拟桥接"将孔与外边界连通，转化为单连通区域。

四边形网格生成：基于 [Takayama et al., CGF 2015] 的方法，对单连通区域做准凸分解，再生成四边形网格 $$Q(V, E)$$ 。网格的顶点分为规则顶点（4 价）和奇异顶点（非 4 价）。

Laplacian 平滑：对四边形网格迭代 Laplacian 平滑以改进网格质量，收敛判据为相邻迭代间最大位移小于阈值 $\epsilon$ 。

3 全局优化目标函数

对分割曲线的优化，核心是同时最小化两项能量：

$F_{\text{shape}}$ ：控制曲线的形状（平滑性、曲率分布），使分割曲线尽量直且均匀分布。

$F_{\text{size}}$ ：控制各子区域面积尽量均匀（uniform patch size），避免出现过小或过大的块。

最终目标函数形如：

F = \alpha_1 F_{\text{shape}} + \alpha_2 F_{\text{size}}, \quad \alpha_i > 0

各能量项的加权系数通过实验调节，课程给出了典型算例的参数配置（ $\alpha_1, \alpha_2$ 在 1.0–2.0 范围）。

4 高质量块参数化（三步法）

Step 1：边界二层控制点构造

首先做正交性优化（orthogonality optimization），使得边界控制网与参数域边界尽量正交。

对规则区域施加 $$C^1$$ 连续性约束（Lagrange 乘子法）；对奇异点周围施加 $$G^1$$ 连续性约束（基于 [Mourrain et al., CAGD 2016] 的方法）。

对于奇异顶点 $$v$$ ， $$G^1$$ 连续性约束可描述为存在唯一解的线性方程组（当 $$M=3$$ 或 $$M=5$$ 时唯一可解）。

Step 2：内部控制点的局部 $$C^1$$ 能量最小化

设张量积 Bézier 曲面片 $$r(u,v)$$ 的阶数为 $$(n,m)$$ ，内部控制点 $$(n-3)(m-3)$$ 个。曲面片的最小能量条件为：

\frac{\partial E}{\partial P_{i,j}} = 0, \quad E(r) = \int_\Omega \| \Delta r \|^2 du dv

这是一个 $$(n-3)(m-3)$$ 元线性方程组，唯一可解后得到所有内部控制点。

Step 3：保证单射的参数化（injective parameterization）

检测每个曲面片的 雅可比（Jacobian）： $J = \det(DF)$ ，若 $$J < 0$$ 则存在翻转。

对无效片（ $J \leq 0$ ）使用 对数障碍函数（logarithmic-barrier method）修正，将 Jacobian 约束纳入优化目标，最终得到可逆的单射参数化。

5 质量对比

以 Fig. 9–Fig. 11 三个复杂区域为例，与骨架方法 [Xu et al., 2015] 对比：

指标	本方法 Scaled Jacobian（均值）	对比方法	本方法条件数（均值）	对比方法
Fig. 9	0.884	0.517	2.76	5.36
Fig. 10	0.919	0.780	2.42	4.35
Fig. 11	0.902	0.789	2.57	4.23

不同方法参数化质量对比

本方法在所有指标上均显著优于骨架方法，尤其是在 最小 Scaled Jacobian（即最差片质量）上优势明显。

---

标架场方法（Frame Field）

与骨架分解并行，课程还介绍了另一套针对复杂区域参数化的技术：基于标架场的方法。

1 流程概述

边界转化：将多条 B 样条曲线边界检测特征点后分割，转化为多边形边界。

Delaunay 三角化：在区域内部生成背景三角网格，作为后续计算的离散基底。

建立拉普拉斯方程：根据边界标架场和矢量场信息，定义内部光滑矢量场方程 $\Delta u = 0$ 。

矢量场求解：使用 Meyer 提出的 Laplace-Beltrami 算子离散化求解，得到每个三角面片上的标架方向。

奇异点检测与流线构造：定位奇异点（3 价、5 价点等），根据其价（valence）确定流出方向，构造初始流线。

流线简化：按简化规则合并相邻流线，将区域划分为若干四边形子区域。

Coons 曲面参数化：对每个四边形子区域构造 Coons 映射，完成参数化。

2 标架场的核心思想

标架场（cross frame field）给区域中每一点赋予一个四元标架（4 个正交或近正交方向），奇异点的存在使得局部无法用统一方向场覆盖整个区域。通过流线（streamline）连接不同奇异点，流线即参数化的分割曲线，与骨架方法的思路本质上是一致的。

Cross frame field 与流线构造

---

Polycube / Polysquare 方法

1 Polycube 概念

Polycube（多立方体）是 3D 版的多边形（polyomino）——由若干大小相等的立方体面-面拼接而成的实体。其二维版本称为 Polysquare。

Polycube 方法的核心思想：将输入几何体（网格或曲面）映射到一个结构化的轴对齐多立方体表示，从而天然得到 IGA 所需的块结构（每个立方体对应一个 Bézier 块）。

2 主流方法（[Huang 2014]）

从输入模型提取 polycube structure（多立方体骨架）。

沿轴对齐的边界面对 polycube 做切片，每片即为一个 IGA 块。

问题：块数与切片次数正相关，复杂模型的块数可能爆炸性增长。

3 有向图简化

为减少块数，课程提出将多立方体结构抽象为有向图：图的每个节点代表一个轴对齐长方体，边代表相邻关系。每条边赋予高度差（height），代表沿某坐标轴的相对位置。

非退化约束：

边不能退化为一个点（否则该块在对应方向上厚度为零）。

不能合并两个相连的节点。

失真控制：用图边长度的拉伸量评估失真，寻找使失真最小的新高度：

\text{stretch}(e) = \frac{\text{new\_height}(e)}{\text{original\_length}(e)}

4 块优化（Block Optimization）

图简化后，对每个块独立做参数化优化。目标是在保持 IGA 分析精度的前提下，最小化块数（减少计算成本）与参数化失真（提升解精度）。

5 闭合形式 Polysquare

[Wang et al., CMAE 2022] 提出了 闭合形式多边形（closed-form polysquare）概念：结合标架场技术，将 polycube 结构推广为更一般的结构，既无内部奇异点，又比普通 polycube 拓扑更灵活。

这一灵活性使得对复杂模型可以生成更少的边界角点、更低失真的四边形网格，从而改善后续 IGA 仿真精度。

整体流程（Fig. 1）：裁剪输入网格为圆盘状 → 生成无内部奇异的 cross-frame field → 闭合形式 polysquare 参数化 → 块结构简化（Patch Simplification） → 得到最终简化的参数化。

---

开放性问题与小结

1 开放问题

如何高效处理超大规模复杂模型的参数化？

块数-精度-计算量三者之间的帕累托最优如何自动寻找？

从 2D 平面参数化推广到 3D 体参数化（trivariate parameterization）时，如何定义 $$G^1$$ 连续性？

2 本讲要点

主题	核心方法	关键目标
骨架分解	骨架引导的分割曲线 + 子区域独立参数化	减少内部奇异点
标架场	Cross frame field + 流线构造 + Coons 参数化	自动适应复杂拓扑
Polycube	多立方体切片 + 有向图简化	生成 IGA 友好的块结构
闭合形式 Polysquare	标架场 + 无内奇异性 + 块简化	更少角点、低失真

本讲的两条技术路线——骨架/标架场驱动的拓扑分解与 Polycube 驱动的结构化表示——代表了参数化研究的两个主流范式。前者更通用，后者更适合 IGA 分析场景，两者互相补充。

---

参考论文：

Xu et al., Skeleton-based domain decomposition for parameterization and IGA, CMAME 2015/2018

Takayama et al., Pattern-based quadrangulation for N-sided patches, CGF 2015

Mourrain et al., $$G^1$$ -continuity around irregular vertices, CAGD 2016

Wang et al., IGA-suitable planar parameterization with patch structure simplification, CMAME 2022