Lifted Surfacing of Generalized Sweep Volumes
问题背景
给定一个随时间移动、可以变形甚至改变拓扑的实体（称为 brush，笔刷），它在运动过程中扫过的三维空间称为扫掠体（sweep volume），其边界称为扫掠边界（sweep boundary）。计算扫掠边界是几何建模中的经典难题，在实体造型、机加工仿真、机器人工作空间计算、连续碰撞检测等场景都有应用。
难点在于扫掠边界同时具有复杂的几何与拓扑特征：
- 不同时刻的笔刷实例相互碰撞时会产生尖锐折痕（sharp creases），边界因此不是光滑曲面。
- 边界的不同部分可能彼此非常接近，形成狭窄缝隙（narrow gaps）。
- 边界可能由多个连通分量组成，其中一些包围着与外部不连通的内部空腔（interior voids），这对碰撞检测和工作空间计算尤为关键。
现有方法各有局限。体素类（volumetric）方法适用面广、能保证闭合曲面，但受网格分辨率限制，难以表达精细几何特征，会把折痕磨圆、在狭窄区域产生伪影，提高分辨率只能缓解而无法根除，且代价高昂。网格类（mesh-based）方法几何精度更好，但通常只能处理简单（如仿射）运动，容易产生缝隙和自交，并且往往丢失内部空腔。
核心贡献
本文提出一种通用的扫掠边界求解方法，在通用性、鲁棒性和特征保真度上均有改进。方法适用于任何由光滑（至少 \(C^2\)）四维隐式扫掠函数表示的广义扫掠，容许笔刷在扫掠中发生形态乃至拓扑变化。
三点主要贡献：
- 提出一种基于水平集相交与缠绕数（winding number）的扫掠边界新刻画，适用于任意维度的广义扫掠。
- 给出一个在 \(\mathbb{R}^3\) 中计算扫掠边界的算法，比网格类方法更鲁棒，比体素类方法更能刻画尖锐与狭窄特征，并保证输出闭合、无自交。
- 提出一种在 \(\mathbb{R}^4\) 中计算提升包络（lifted envelope）的算法，改进了现有高维向量值水平集离散化方法的网格质量。
预备定义
广义扫掠由光滑的 \((n+1)\) 维扫掠函数 \(f(x,t)\) 隐式定义，\(x \in \mathbb{R}^n\)，\(t \in [0,1]\)。时刻 \(t\) 的笔刷是满足 \(f(x,t) < 0\) 的所有点。扫掠体是所有存在某个 \(t\) 使其落在笔刷内的点的集合。
作为特例，刚体扫掠（笔刷仅平移旋转）可写成：
\[f(x,t) = b(R^{-1}(t) \cdot (x - T(t)))\]
其中 \(b\) 是初始笔刷隐函数，\(T(t)\)、\(R(t)\) 为平移向量和旋转矩阵。
扫掠边界可以隐式地定义为下述函数的零水平集：
\[f^*(x) = \min_{t \in [0,1]} f(x,t)\]
因为 \(x\) 在扫掠体内当且仅当存在某个 \(t\) 使 \(f(x,t) < 0\)，即 \(\min_t f(x,t) < 0\)。注意 \(f^*\) 连续但不光滑，在最小值由多个 \(t\) 达到处出现尖锐特征（二维为角点，三维为折痕曲线）。
另一种视角是提升的（lifted）结构。定义提升扫掠体为 \(\mathbb{R}^{n+1}\) 中满足 \(f(x,t) < 0\) 的点集，其边界称为扫掠集（sweep set）。扫掠边界是扫掠集”轮廓（silhouette）”沿时间方向投影的结果。轮廓上的点 \(\{x,t\}\) 满足 \(f(x,t)=0\)，并根据时间取值满足关于时间导数 \(f'(x,t) = \partial f(x,t)/\partial t\) 的条件：
- \(0 < t < 1\) 且 \(f'(x,t) = 0\)（contour，轮廓）；
- \(t = 0\) 且 \(f'(x,0) > 0\)（bottom cap，底盖）；
- \(t = 1\) 且 \(f'(x,1) < 0\)（top cap，顶盖）。
三者之并称为提升包络（lifted envelope）。它在 \(\mathbb{R}^n\) 中的投影称为包络（envelope），是一个可能自交的结构，其中每个点都在某时刻与笔刷相切。扫掠边界是包络中不位于扫掠体内部的子集。
奇异性
包络除自交外还可能含奇异点，它们是提升包络上高阶导数消失点的投影。若某个 \(t \in (0,1)\) 使 \(f(x,t)=f'(x,t)=0\) 且 \(f''(x,t)=0\)，则 \(x\) 为奇异点。进一步分类：
- 尖点（cusp）：\(f=f'=f''=0\) 但 \(f''' \neq 0\)；一般具有 \(n-2\) 维。此时 \(f_x(s)=f(x,s)\) 在 \(s=t\) 处是拐点式的驻点而非极值，因此 \(x\) 落在扫掠体内部，尖点不在扫掠边界上。
- 夹点（pinch）：\(f=f'=f''=f'''=0\) 但 \(f'''' \neq 0\)；一般具有 \(n-3\) 维。此时是波状极值点（point of undulation），因此夹点可能落在扫掠边界上。
理论基础
方法建立在两个观察之上，二者对任意维度的广义扫掠都成立。
提升包络是两个隐式曲面的交
轮廓、底盖、顶盖分别落在 \(f'(x,t)\) 的零水平集（\(0 \[g(x,t) = \begin{cases} f'(x,t), & 0 \le t \le 1 \\ 1, & t > 1 \\ -1, & t < 0 \end{cases}\] 将 \(g\) 的零水平集定义为其零上水平集闭包的边界，可验证它恰与 silhouette set 重合，且可定向。于是提升包络就是两个隐式曲面的交：扫掠函数 \(f\) 的零水平集（扫掠集）与轮廓函数 \(g\) 的零水平集（silhouette set）。这个观察使得提升包络（进而包络）可以通过等值面提取稳健地离散化。 方法给出了扫掠边界的组合刻画，依赖于对包络的一个精心选择的定向。 在提升包络光滑处的点 \(p\)，其定向由 \(n-1\) 个切向量基 \(\Sigma\) 表示，\(\Sigma\) 同时正交于 \(\nabla f\) 和 \(\nabla g\)。若 \(\{\Sigma, \nabla f, \nabla g\}\) 构成正定向基，即 \[\det(\{\Sigma, \nabla f, \nabla g\}) > 0\] 则称 \(\Sigma\) 为向外（outward）。把提升包络的向外切基投影到 \(\mathbb{R}^n\) 即得向外定向的包络。核心定理： 定理：扫掠边界是向外定向包络中，界定缠绕数为 0 的空间的那部分子集。 证明思路是引入”层数（layer count）”概念：点 \(x\) 处的层是使 \(f(x,t)<0\) 的连续时间区间。层数与缠绕数一样都是整数、在远离包络的连通区域内为常数、点越过包络时按 \(\pm 1\) 变化且符号由相对向外定向的运动方向决定、在扫掠体外均为零。据此二者绝对值处处相等，层数为零的点正是缠绕数为零的点。向外定向对该刻画至关重要——它能正确区分带空腔与不带空腔的情形。 由上述观察导出两阶段方法： 对 \(n=3\)，阶段二可直接借助已有的网格排布与缠绕数工具（Zhou 等 2016）实现，辅以简单后处理。由于这类工具在包络奇异点附近（相交三角形近乎相切）会产生大量伪单元，方法对体积小于阈值的单元进行剪除，并提取多个排布面片交汇处的折痕曲线和折痕点。核心创新在阶段一。方法适用于任何”黑箱”扫掠函数 \(f(x,t)\)，只要能查询给定位置与时刻的值和梯度，并满足通用性假设。 提升包络是扫掠集与 silhouette set 之交。常见做法是先算一个函数的水平集得到余维 1 流形 \(M\)，再在 \(M\) 上采样另一函数求水平集得到余维 2 流形。本方法沿用两步框架，但有两点关键差异。 顺序（\(f \to g\) 还是 \(g \to f\)）会影响结果。离散曲面常产生锯齿状轮廓，若先取扫掠集再求其轮廓，得到的包络很不光滑。而提升包络上的点倾向于避开 silhouette set 自身的轮廓（这类点需 \(f''(x,t)=0\)，对应包络奇异点，维度更低，其中唯一可能落在扫掠边界上的夹点更稀有）。因此方法选择先计算 \(M\) 为 silhouette set，再在其上求 \(f\) 的水平集，得到更光滑的离散化，尤其是投影到扫掠边界的那部分。 在 \(\mathbb{R}^4\) 中用四维单纯形做等值面提取，容易产生形状很差的四面体（短边、小二面角），进而在三维等值面提取后得到大量近退化三角形，给下游排布计算带来数值问题。仅靠把网格顶点”吸附（snapping）”到等值面在四维单纯形网格上效果有限。 方法改用四维柱体（columns）分解 \(\mathbb{R}^4\)：每个柱体由给定三维四面体网格中的一个四面体沿时间方向拉伸而成。由于提升包络倾向于避开 silhouette set 在时间上”折叠”的地方，含提升包络的那部分更可能与柱体”横截”相交，交出来的三维四面体截面投影正是拉伸它的四面体，从而在网格良好时得到大多形状良好的四面体。 算法接受一个”3.5D”网格表示：一个三维四面体网格，加上每个网格顶点上的一串时间戳。分两步： 为保证向外定向，每个多面体（三角形）朝 \(g\)（\(f\)）为正的一侧定向。 行进柱体按维度递增处理四面体的顶点、边、面：在每条时间线（timeline）上按时间戳求 \(g\) 的零交点生成 p-vertex（利用 \(g\) 在 \(t<0\)、\(t>1\) 的延拓，保证零交点数为奇数）；在时间四边形（time-quad）上把相邻 p-vertex 连成有向 p-edge；在时间棱柱（time-prism）上把有向 p-edge 组成有向环形成 p-face；最后把连通的 p-face 组成多面体。该过程保证输出多面体网格在 p-face 处拓扑流形（每个内部 p-face 恰与两个多面体相邻）。即便某些多面体几何自交，也会在后续排布计算中解决。 行进多面体沿标准追踪法在每个多面体的边上求 \(f\) 的零交点：沿 p-edge 用值和梯度的三次 Hermite 插值近似 \(f\)，再用 Halley 法求根以提升光滑度；把零交点按符号方向连成有向段、组成有向环并三角化，最后丢弃第四坐标投影到三维。行进柱体产生的多面体（尤其是提升包络附近的）大多是与输入网格相同的四面体，此时行进多面体退化为标准 Marching Tetrahedra，并用吸附阈值 0.1 倍边长的 grid-snapping 去除近退化三角形。 高维均匀采样会导致网格规模爆炸，因此需要仅在提升包络附近（尤其其投影到扫掠边界的子集）加密采样，同时保持四面体形状良好。方法借鉴 Ju 等 2024 的迭代细化思想，适配到 3.5D 网格与两步曲面算法。 网格自粗到细生成，从均匀四面体网格加均匀时间戳出发，交替进行空间与时间细化。空间细化用最长边二分法（在最长边中点插入新顶点，把相邻四面体各一分为二，新顶点时间戳取两端点之并）；时间细化在时间戳区间中点插入新时间戳。优先时间细化（存储小、不改动网格结构）。空间队列的四面体按最长边降序排序，时间队列的区间按长度降序排序。 细化准则是一个有序检查列表： 前两个检查判断四面体是否含扫掠边界，后两个保证输出精度。这些检查通过 Ju 等 2024 为单纯形开发的零交点测试和误差界实现，需将柱体分解为四维单纯形。消融实验显示：去掉包络近似误差检查会导致包络处欠细化、曲面不光滑；去掉内部性检查会在不属于扫掠边界的内部包络处过度细化；均匀网格在相近四面体数下给出更粗糙的近似。 方法用 C++ 实现，唯一外部依赖是 Zhou 等 2016 的网格排布程序，实验在 M4 Pro 芯片、48GB 内存的 MacBook Pro 上进行。初始网格用 \(4^3\) 立方格经 Kuhn 剖分得到的均匀四面体网格，每个网格点起始有 5 个均匀时间样本；固定 \(\epsilon_{time} = 2^{-7}\)，令 \(\epsilon_{space} = 0.05 \cdot \epsilon_{env}\)。这样一个粗糙初始网格对所有示例都足够。质量主要由 \(\epsilon_{sil}\) 和 \(\epsilon_{env}\) 控制，文中取 \(\epsilon_{sil} \in [0.001, 0.005]\)、\(\epsilon_{env} \in [0.0001, 0.0005]\)。 与 Sellán 等 2021（一种基于时空数值延拓的体素方法，仅适用于网格 SDF 定义的刚体扫掠）的对比表明：作为体素方法它会产生磨圆的折痕和贴近曲面处的伪影，提高分辨率只能减轻而不能消除，且显著增大输出规模与运行时间；本方法在相近网格复杂度下产生尖锐折痕并能分辨极近曲面。 方法的关键优势是通用性，可处理笔刷发生形态乃至拓扑变化的扫掠：环面与球之间的形变、一球分裂为两球再合并、五亏格立方体形变为三亏格四面体（均以四次多项式表示）、Fertility 模型沿螺旋下降同时向内偏移（亏格从 4 减到 0）、线框球滚动并膨胀（亏格从 41 变到 29，含 110 个空腔）。方法还支持用 soft-min/soft-max 复合多个扫掠函数以实现布尔运算，并在两个刚体扫掠的交界处产生尖锐折痕。 运行时间从数秒到数分钟不等，主要耗在网格生成上，主导因素是每次扫掠函数（及其梯度）求值的耗时与扫掠边界的几何复杂度。随 \(\epsilon_{env}\) 减小，各步耗时呈多项式增长，与几何元素数量的增长相关。从缠绕数得到扫掠边界
方法总览
计算提升包络
函数顺序
网格单元质量
自适应网格生成
实验与评估
局限与展望