Divide and Truncate: A Penetration and Inversion Free Framework for Coupled Multi-physics System

一句话总结

提出 Divide and Truncate（DAT）——把碰撞处理抽象成”给每个几何面划一块专属空间，再把位移截断到这块空间内”的统一框架，其方向感知的 Planar-DAT 变体在保证无穿透、无翻转的同时，消除了传统方法的人为阻尼与卡死，且与材料、求解器无关，可作为后处理步骤接入任意迭代优化器。

研究背景

• 领域现状：无穿透（penetration-free）已是稳健物理仿真的基石。主流做法有两条路线：一是把连续碰撞检测（CCD）嵌进线搜索的 IPC 类方法，二是用离散碰撞检测给每个顶点设”信赖域”边界的保守推进（conservative advancement）类方法。
• 核心痛点：两条路线都在”防最坏情况”。线搜索用全局最早的一次碰撞去卡住整个网格的步长；信赖域方法则假设任何方向的运动都危险，于是施加各向同性（各方向一视同仁）的球形约束。前者昂贵、后者带来人为阻尼，在密集接触下还会卡死（deadlock）。此外多物理耦合时，每种材料/模型往往要各自定制 CCD 公式，集成困难。
• 本文 idea：位移方向其实在施加约束前通常是已知的，而且大多数位移是切向或远离邻近表面的，本不该被截断。于是把信赖域重构成”方向感知的半空间划分”，只约束朝向表面的那部分运动。

方法

整体思路分两步：先把周围空间划分成互不重叠的专属区域，每个几何面分到一块；再把优化器给出的位移 \(\Delta X\) 截断，使每个面变形后仍留在自己的区域内。因为区域互斥，只要各自不越界，整体就必然无穿透。作者把这套思路叫 Divide and Truncate（DAT），并对顶点-三角形对与边-边对分别施加。

flowchart LR
  A["优化器给出位移 ΔX"] --> B["BVH 查询邻近面 (半径 rq)"]
  B --> C["按方向构造划分平面 (计算 λ)"]
  C --> D["求 ΔX 与平面交点，逐顶点截断 t_v"]
  D --> E["atomic_min 汇聚每个顶点的 t_v"]
  E --> F["无穿透 / 无翻转的 ΔX，累加进状态"]

关键设计分为四点：

1. 各向同性划分（Isotropic-DAT）作为对照。 让每个面移动量不超过到最近面距离的一半，用以顶点为心的球、以三角形/边为心的偏置区域来界定专属区。这正是此前工作与 OGC 所用的方案，但它对所有方向一视同仁，天然保守。

2. 方向感知的平面划分（Planar-DAT）是核心贡献。 对一个无交的顶点-三角形对，取顶点到三角形最近点连线为法向 \(\boldsymbol{n}_{v,t}\)，在两者之间放一张分隔平面，顶点与三角形各占一个开半空间。所有配对的半空间取交，得到每个面的专属区域，其并集铺满整个空间——空间利用率远高于各向同性的有限小球。平面位置由参数 \(\lambda_{v,t}\) 决定，并按两侧位移的法向分量自适应：定义 \(\delta_v = \max(-\Delta \boldsymbol{x}_v \cdot \boldsymbol{n}_{v,t}, 0)\) 与三角形侧的 \(\delta_t\)，当两侧都朝平面靠近时按 \(\lambda_{v,t} = \delta_t / (\delta_t + \delta_v)\) 分配空间；一旦某侧在远离或平行移动，就不对该侧截断。这正是消除阻尼与卡死的关键。截断时对每个划分平面求位移射线的交点，用松弛比 \(\gamma_r \in (0,1)\) 保证停在平面前。

3. 无翻转约束天然融入同一框架。 四面体翻转发生在某顶点越过对面三个顶点所定义的平面，这同样是一个半空间排除条件，其划分平面的构造方式与顶点-三角形接触完全一致，于是无穿透与无翻转用同一套 Planar-DAT 流程一并解决，无需额外处理。

4. 旋转与动画自由度的扩展。 刚体顶点走的是曲线轨迹，作者证明只要每个顶点不越过其划分平面即可（面轨迹穿越平面当且仅当某顶点穿越），用”均匀采样找符号变化 + 二分 + 区间算术验证包围盒”的两阶段算法找最晚安全时刻。动画物体则被当作”无限刚”的目标位姿，分多次迭代增量施加，同样接受截断与安全检查，实现动画与仿真物体的无缝、无穿透耦合。此外还给出能量最优的 Divide and Project（DAP）变体（用 Dykstra 投影到半空间交集），但其迭代投影比截断慢约 50 倍，实时场景仍首选截断。

工程上，为避免朴素 \(O(N^2)\)，只在查询半径 \(r_q\) 内找邻近面，超出的退化为各向同性截断。GPU 实现按碰撞对并行，每线程算一个划分平面并用 atomic min 更新四个相关顶点的截断标量——比按顶点并行快约 20 倍。碰撞检测无需每次迭代都跑，可按固定频率执行，从而把整帧计算捕获进单个 CUDA graph。

实验结果

作者在 10 个各含 3000 个离散三角形的随机网格上、每个施加 100 组随机变形（纯线性位移、以及带随机旋转的刚体运动），共 900 万次位移，度量”每顶点位移幅度保留比”，对比 Isotropic-DAT 与全局 CCD 截断。核心结论是 Planar-DAT 平均能多保留 2 倍以上的意图运动，在接触最密集、最该保运动的顶点上优势可达数十到上百倍；相较全局 CCD 更是平均多保留 100 倍以上位移（CCD 因一处早碰撞就锁死整个系统而极度保守）。

统计量	vs Isotropic-DAT（线性）	vs Isotropic-DAT（旋转+线性）	vs 全局 CCD（线性）	vs 全局 CCD（旋转+线性）
均值	2.22×	2.34×	265×	289×
中位数	1.42×	1.65×	265×	282×
90 分位	4.03×	4.72×	411×	448×
最大	157.6×	178.2×	460×	512×

真实场景上，200 层布料落到圆柱、持续产生 2000 多万接触对，Isotropic-DAT 因过度截断锁死失败，Planar-DAT 用两倍时间步、一半迭代仍稳定，平均每步不到 12.6 ms。另有 369 m/s 铅弹穿膛线、齿轮碾压软体 Armadillo（保无翻转）、软体/布料/刚体混合下落等多物理场景。收敛性上 Planar-DAT 每迭代仅比 Isotropic-DAT 贵约 10%，却因方向约束能迈更大步、更快降残差；而 CCD 每迭代约 16 ms、慢 10 倍以上，DAP 则慢约 50 倍。整体在密集接触场景比 Isotropic-DAT 至少快 2 倍，仿真每步中碰撞检测占 63.5%、平面截断仅占 12.8%。

亮点与局限

• 亮点：
  • 用”划分空间 + 截断位移”把碰撞处理统一成一个几何框架，无穿透与无翻转共用同一套公式。
  • 方向感知的半空间约束只挡朝向表面的运动，切向与远离运动完全放行，从根上解决了保守信赖域的人为阻尼与卡死。
  • 材料无关、求解器无关：作为后处理步骤即可接入任意迭代优化器，异质多物理耦合变得直接。
  • GPU 上按碰撞对 + atomic min 的实现高效，可整帧塞进单个 CUDA graph，达到交互乃至实时帧率。
• 局限：
  • 依赖查询半径 \(r_q\)，超出半径的接触退化为各向同性截断，大位移场景仍可能重新引入阻尼。
  • 截断保证无穿透，但若求解器未收敛就被切断，不保证动量/能量守恒，高精度应用下可能影响物理准确性。
  • 刚体旋转靠采样与区间算术界定曲线轨迹，带来额外开销，极快旋转下需调参。
  • 以 OGC 为底层接触模型，因而继承了它在非凸边界处接触能量不连续的问题。

延伸思考

DAT 与 VBD（Vertex Block Descent）这类 Gauss-Seidel 求解器结合得很自然——每处理一个颜色就立刻做一次截断，说明”截断作为后处理”的设计对现代并行求解器友好，值得思考它能否同样干净地接入 XPBD、投影动力学等其它管线。其”方向感知半空间”的思想本质是把信赖域从各向同性球升级为自适应超平面，这类”用已知搜索方向放宽保守边界”的做法或许能迁移到其它带硬约束的优化问题。另一个值得追问的点是查询半径退化行为：能否用分层或多分辨率的划分，让大位移场景也不必回退到各向同性，从而彻底摆脱残余阻尼。