Surface Power Diagrams for Knit Singularity Placement

一句话总结

把”往针织物上摆放增/减针等奇异点”这件事，重新表述成曲面上的半离散最优传输问题，用推广到三角网格的测地功率图（geodesic power diagram）来量化编织时间函数梯度的旋度，从而一次性全局地、更快更均匀地放好所有奇异点，并生成机器可织的无螺旋（helix-free）针织图。

研究背景

• 领域现状：机器针织（whole-garment knitting）能一次成型复杂几何、少废料，近年在计算图形与制造领域很热。主流做法是”条纹（stripes）派”——在曲面上算两组正交、等间距的条纹，把它们相交得到 knit graph（针织图），再交给 Autoknit 编译器生成机器指令。条纹的奇异点就对应针织奇异点：wale 方向的增/减针、course 方向的短行端点（short row ends），它们是给曲面做几何塑形、保持线圈尺寸均匀的关键。
• 核心痛点：怎么”自动、聪明地”放这些奇异点一直是难题。早期方法要么手动配对奇异点、要么解庞大的混合整数规划；最近的工作（Mitra 等 2025）提出用时间函数归一化梯度的旋度作为启发信号，贪心地一个一个试放奇异点——每放一个都要解一次带约束的二次规划，随针织密度（奇异点数）增加而严重变慢，密集针织图基本做不动。而且贪心插入不保证旋度质量守恒，奇异点数目也无从控制。
• 本文 idea：不再逐个贪心，而是把”放置全部奇异点”整体表述为一个曲面上的半离散最优传输 / 测度量化问题：用一组离散奇异点去逼近（量化）连续的旋度测度。这个问题的解正是曲面上的一张功率图，用 Lloyd 型交替算法（解 OT 权重 + 更新奇异点位置）一次求出所有位置。

方法

整体框架：给定编织时间函数 \(h: M \to [0,1]\)（定义 course 行的先后顺序），先算它归一化梯度场的旋度 \(\mu_c = \nabla \times \overline{\nabla h}\)（course 方向）及其旋转版 \(\mu_w\)（wale 方向）作为”该放奇异点”的信号；把这个（带符号的）旋度测度拆成正负两部分分别做最优传输量化，得到正/负奇异点位置；配对并离散化到网格边上后，解条纹优化得到两组正交条纹，相交生成 helix-free 针织图，最后送 Autoknit 编译成机器指令。

flowchart LR
  A["时间函数 h"] --> B["旋度信号 ∇×∇h/(course, wale)"]
  B --> C["半离散 OT 量化/测地功率图 + Lloyd"]
  C --> D["奇异点位置/正 negative 配对"]
  D --> E["条纹优化/含排序约束"]
  E --> F["相交生成 helix-free 针织图"]
  F --> G["Autoknit 编译/机器编织"]

关键设计：

1. 把奇异点放置写成最优传输量化。 连续目标是找一个向量场 \(V\) 尽量贴近 \(\nabla h / P\)（\(P\) 是条纹周期），同时其旋度被量化成放在奇异点处的一串带 \(\pm 1\) 指标的 Dirac 测度之和。作者不去解对应的大规模混合整数问题，而是把它看成”用均匀离散测度去量化连续旋度测度、最小化 Wasserstein 距离”。奇异点个数由旋度总质量除以周期取整决定：\(N_{+} = \lceil \int_M \mu_{+} / P \rceil\)，\(N_{-} = \lceil \int_M \mu_{-} / P \rceil\)，这比贪心法多了对数目的原则性控制。由于旋度是带符号的，正负部分被分开量化（不做质量抵消），实现上很干净。作者还证明了一个平衡命题：在任意两条 \(h\) 等值线之间，正、负旋度质量相等（Stokes 定理的推论），这保证了 course 方向正负奇异点能好好配对、落在相近的等值线上。

2. 测地功率图：把平面 OT 机器搬上曲面。 平面上半离散 OT 的解是功率图（Voronoi 图的带权推广，每个 cell 由 power distance \(\lVert x - p_i \rVert^2 - \psi_i\) 最小决定）。要搬到三角网格上，需要曲面上快速的测地距离、功率距离、以及功率 cell 的质量加权重心。作者借助热核工具：用 Crane 等的”热方法”近似测地距离（Varadhan 公式 \(k_t(p,x) \propto e^{-d^2(p,x)/4t^2}\)），用 Sharp 等的向量热方法算对数映射 \(\log_p\) 来在切平面上做 Karcher 均值。功率 cell 用一组”功率距离核”以模糊（partition-of-unity）方式表示：

\[V_i(\boldsymbol{\psi})(x) = \dfrac{e^{-\psi_i/4t^2} k_t(p_i, x)}{\sum_j e^{-\psi_j/4t^2} k_t(p_j, x)}\]

这些量都归结为对预分解 Cholesky 的稀疏线性求解，复杂度近似随网格规模线性增长。

1. Lloyd 型交替优化。 一步 Lloyd 迭代 = 先用 L-BFGS 优化功率权重 \(\psi_i\)（让每个 cell 覆盖相等的旋度质量，梯度是质量差 \(\partial G / \partial \psi_i = P - \int_M V_i \, d\mu\)），再把每个奇异点沿指数映射挪到其功率 cell 的质量加权重心（用 0.8 的步长抑制振荡）。交替到 OT 目标相对改善低于 \(\varepsilon_{\text{Lloyd}} = 10^{-4}\) 收敛，通常 50–100 次迭代即可。整个量化对随机初始化相当鲁棒，不同初值得到的奇异点配置质量相近。

2. 稠密设置下保证无螺旋的新约束。 密集针织（低周期、奇异点多）时，要保证所有 course 轨迹 helix-free 更难。作者在条纹优化里加了三项局部约束：对称短行端点约束（让配对短行两端结构对称）、分隔线路由规则（在近邻等值线间按平均时间值绕开其他奇异边来铺设配对边链）、以及排序不等式约束（要求相邻 course 奇异点按时间函数 \(h\) 有序，防止 Type II cell 出现螺旋）。这些约束基本是局部的，与全局量化解耦。此外，knit graph 抽取时通过匹配虚拟顶点并微调位置，使得可以生成比网格边长更细的针织图。

用户可控性也做了扩展：旋度遮罩（在指定区域清零旋度、不插奇异点，用于放 logo/纹理而无失真）、等值线约束（让时间函数在特征边上取常值，使 course 行对齐锐利特征/接缝）、以及boosting 参数 \(c\)（把旋度质量按 \(\mu' = (1-c)\mu + c \left(\int_M d\mu / \int_M d\mu_B\right)\mu_B\) 转移到用户指定曲线上形成”表观接缝”，且保持总旋度质量、奇异点数不变）。

实验结果

实现为 C++（Gurobi 解优化、Geometry-Central 提供热方法/log-map、Polyscope 可视化），在 M3 MacBook Pro 上计时，并用 Shima Seiki 15 针 V 型床机实际编织验证。核心对比是相对前作 Mitra 等 2025 的运行时间——在相同奇异点数下衡量（表为总运行时间，m:ss）：

模型	Mitra’25 奇异点数	Mitra’25 用时	本文用时	加速
Sock	31	0:29	0:19	1.6x
Dress	14	0:21	0:03	8.3x
Cactus	22	0:29	0:06	4.9x
Elbow Sleeve	22	0:06	0:01	11.8x
Pipes	62	1:15	0:12	6.0x
Heart	189	5:30	0:16	20.6x

加速一般落在 5x–10x，奇异点越多优势越明显。在稠密（低周期）设置下，前作常在 10 分钟超时或做不出 helix-free 图（Duck / Moai / Bunny 前作超时，本文分别 1:10 / 2:34 / 0:58 完成），完成的模型平均约 3x 加速。质量上，本文在较粗设置里中位边长误差 7.4%、中位角度偏差 3.1%，优于前作的 8.6% 与 5.0%；相比 Autoknit 的原生图，本文图更平滑、四边形角度误差更低，更适合渲染。运行时间近似随网格顶点数线性、随周期减小（奇异点增多）而上升。

亮点与局限

• 亮点：
  • 把针织奇异点放置这一离散组合难题，优雅地统一到”曲面上半离散最优传输 / 测度量化”框架，用一次全局求解替代逐点贪心，通常 5–10x 加速，密集图上更可行。
  • 提出并落地了三角曲面上的测地功率图（Voronoi 的带权推广），全部基于预分解的稀疏热核求解，工程上高效、复杂度近线性；这一工具本身有超出针织的潜在用途。
  • 有原则地决定奇异点数目、保证旋度质量守恒，配合新的排序/路由约束更鲁棒地生成 helix-free 图，并保留丰富的用户编辑能力（遮罩、等值线对齐、表观接缝）。用大量实物编织与虚拟画廊验证。
• 局限：
  • 支撑点目前随机初始化，更聪明的初始化（或多尺度/周期调度）可望更快收敛，作者列为未来工作。
  • 网格分辨率与周期不完全独立：给定周期 \(P\) 建议平均边长 \(\le 2P\)，否则可能出现绝对指标大于 1 的离散奇异点，导致条纹与针织图次优。
  • 下游依赖 Autoknit 调度器，其在高拓扑复杂度或强局部塑形的模型上偶有跑不通（部分结果只能放进虚拟画廊）。
  • 仅限最基础的单面平针（single jersey）结构。

延伸思考

• 这条工作是 Boston University Ed Chien 组”条纹—叶状结构—曲率/旋度”针织规划路线的延续（Mitra 等 2023/2024/2025 的自然升级），把逐点贪心换成 OT 全局量化是关键转折——这类”用最优传输做均匀采样/量化”的思路，与蓝噪声采样、曲面重网格化本是同源，作者也点明了向这些方向迁移的可能。
• 曲面测地功率图作为独立工具值得关注：凡是需要在网格上做带权、质量约束的均匀布点（如各向异性采样、3D 打印量化伪影处理）都可能复用这套热核 + Lloyd 机器。
• 值得追问的是可扩展性与结构表达力：从单面平针推广到罗纹、提花等更复杂针织结构后，旋度信号与 helix-free 约束是否仍成立；以及更智能的初始化能否把交互速度进一步推到实时。