IEEE Transactions on Robotics

Collision Detection Between Convex Objects Using Pseudodistance and Unconstrained Optimization

作者：Rilun Xia, Dongming Wang, Chenqi Mou · 机构：LMIB-School of Mathematical Sciences, Beihang University, Beijing, China; LMIB-School of Artificial Intelligence, Beihang University, Beijing, China; LIP6–CNRS–Sorbonne Université, Paris, France; Sino-French Laboratory for Mathematics, Hangzhou International Innovation Institute of Beihang University, Hangzhou, China

会议/期刊：IEEE Transactions on Robotics · 发布日期：2025 · 页码：253-268

路径规划运动规划优化安全

精读笔记

Problem Setting

【Collision Detection Between Convex Objects Using Pseudodistance and Unconstrained Optimization，IEEE Transactions on Robotics / 2025】

这篇论文解决的不是通用 collision detection，而是一个更具体但很有价值的子问题：凸对象、隐式曲面片段边界、可包含非严格凸和非光滑结构、目标主要是布尔碰撞判定而非精确欧氏距离。真正困难点在于，隐式曲面对象的欧氏距离通常要解 constrained optimization；而如果边界是高阶曲面、piecewise implicit surfaces 或非光滑拼接，common-normal / closest point iteration 容易依赖初始化、光滑性和严格凸性。

关键矛盾是：碰撞判定只需要“两个零集是否有交”，但传统方法经常先求比这个问题更强的量——最近点、最小距离或接触法线。作者的切入点是把问题降格：不再坚持真实欧氏距离，只保留足以判定交集的伪距离性质，并让这个伪距离天然适合无约束凸优化。

Motivation

已有方法的不足不是单一维度的速度问题，而是适用性和优化形式之间的错配。多面体方法快但需要离散化，曲面几何被网格近似后会引入精度和预处理成本；ellipsoid 专用方法利用代数结构，泛化性弱；common-normal 方法本质在边界上找接触点，对初值和光滑性敏感；更 general 的 convex implicit proximity query 又会回到带约束距离优化。

作者的核心观察是：如果任务只是判断碰撞，真实距离不是必要信息。缺的是一种“几何上足够正确、优化上足够好”的替代距离：它的零集要严格等于物体内部，它要凸以避免局部极小，它的平方要可微以允许 Newton 类方法。这就是 δ-distance 的动机。

Core Idea

论文真正改变的是建模方式：不再在两个对象表面之间寻找最近点，也不再求两个集合间的真实距离，而是在整个空间中构造两个以物体为零势能区的虚拟势场。两个物体碰撞，当且仅当这两个势场的叠加存在零能量点；否则最小点是两者势场拉力平衡的位置。

这个思路的本质区别在于，它把 collision detection 变成了 unconstrained convex minimization。δ-distance 不是为了逼近欧氏距离，而是为了构造一个“可优化的可行性违反度”。这种 formulation 的优势来自信息重组：物体边界的多个隐式约束通过 ReLU-violation norm 聚合为一个全空间函数，优化变量只剩一个空间点 x，而不是两个表面点、Lagrange multipliers 或多约束内部点。

Method

1. δ-distance：解决“inside-outside 函数便宜但不一定适合作为距离”的问题。它要求非负、零集正确、凸、平方可微。核心变化是把碰撞所需的集合信息编码为一个全局凸函数，而不是几何最近点问题。

2. 势能平方 V=p^2：解决边界不可微问题。ReLU(F) 在 F=0 处不可微，但 ReLU(F)^2 在边界可微；这一步是方法能用 Newton-Raphson 的关键，不是装饰性选择。

3. 多隐式片段组合：对于 Δ=∩_i {F_i≤0}，用 sqrt(sum_i ReLU(\hat F_i)^2) 作为整体 δ-distance。它本质上是一个 convex constraint violation norm。这样 piecewise implicit boundary 不需要显式拼接成光滑边界，也不需要枚举 active surface。

4. 无约束凸优化判碰：最小化 V_1(x)+V_2(x)。若最小值为 0，则 x 同时在两个物体内；否则无交。这里正确性来自零集等价，优化可解性来自凸性和可微性。

5. 线性平移扩展：把 x 扩展为 (x,t)，物体运动对应仿射变换；凸函数与仿射映射复合仍凸。因此可以在时空中判定是否存在某时刻交叠。注意这不是完整 CCD，因为不返回首次碰撞时间。

Key Insight / Why It Works

最核心贡献是把碰撞判定看成“两个凸零集的共同可行性检测”，并用平方化的 convex violation measure 做无约束化。这比“求距离再判零”更贴近布尔碰撞的最低信息需求。因此它有效的原因不是更好的数值微分，也不是 Newton 方法本身，而是把问题从 constrained geometric optimization 转换为 unconstrained convex feasibility minimization。

最可能真正有贡献的是 δ-distance 的条件设计：零集正确保证判碰语义，凸性保证无 spurious local minima，平方可微保证可以用二阶优化穿过 ReLU 边界。这里的 ReLU-square trick 很关键：它允许非光滑几何边界对应光滑势能，而不是要求物体本身光滑。

部分增益来自 engineering / representation choice。比如为 superquadric 选择低阶 \hat F 而不是原始高幂 inside-outside function，确实改善 conditioning，但这是数值工程层面的关键细节，不是新的几何理论。文中也承认选择低幂形式能减少 Newton 步数和浮点数值问题；这部分增益来源比较清楚，但缺少统一最优性理论。

它不是 scaling、retrieval 或 data-driven 方法；核心是 better inductive bias：用凸 violation landscape 代替真实距离 landscape。测试时计算量主要来自 Newton 迭代和解析梯度/Hessian，因此更像 test-time convex optimization，而不是预计算或数据覆盖带来的泛化。

Relation To Prior Work

与 GJK/多面体路线相比，它不依赖离散顶点支撑函数，而是直接在隐式表示上工作；代价是只适用于能构造凸 δ-distance 的对象，且通常不给真实距离。与 ellipsoid/quartic-root 等代数专用方法相比，它牺牲特例速度和闭式判定，换取曲面类型 generality。

与 common-normal 方法最本质的差异是：后者在边界上找一对满足法线反向的候选接触点，本质是 closest-point stationarity；本文在全空间找叠加势能最低点，不要求边界光滑，也不需要先知道 active surfaces。与 Chakraborty 等 constrained proximity query 相比，本文不求欧氏距离，不引入约束优化，而是用伪距离把约束吸收到目标函数。

看似新的“虚拟势场”本身并不新，势场思想在机器人中很常见；实质创新在于这个势场被设计成全局凸且零集精确对应凸体，从而不是传统 potential field 那种容易局部极小的 heuristic。

Dataset / Evaluation

实验主要是作者构造的六类隐式凸体及其随机位姿/随机线性速度组合，覆盖平面、二次曲面、高阶 hyperquadric、superellipsoid 以及 piecewise intersections。这个覆盖能验证方法在“解析凸隐式对象族”上的适用性，也展示了非光滑/非严格凸拼接对象可处理。

与 FCL/GJK 的比较有一定参考价值，但不是完全公平的范式对比：GJK 使用的是多面体近似，精度、顶点数、预处理和内存开销都影响结论；本文方法直接用解析隐式式子，天然避免网格化。实验支持“在这些对象上速度可达到实时、与多面体近似同量级”的 claim，但没有充分支持“广泛工业场景鲁棒可用”的 claim。

连续运动实验只覆盖线性平移，并且只判断是否存在碰撞，不求 TOI。对于 robotics 中常见的旋转、关节运动、多体链、复杂 scene broadphase/narrowphase 集成，文中未充分说明。

Limitation

最大的前提是凸性。对象必须能表示为凸隐式不等式的交，且每个约束要能找到合适的凸 \hat F。非凸对象只能通过凸分解间接处理，论文没有讨论分解误差、组合数量或 broadphase 成本。

第二个限制是 δ-distance 的选择并非自动。理论上很多函数满足定义，但实际性能高度依赖 conditioning；高阶曲面可能造成 Hessian 病态，非严格凸会导致 Hessian 奇异，需要伪逆。文中给出经验规则如降低幂次，但没有充分说明如何系统选择最优伪距离，也没有给出坏例子的鲁棒性分析。

第三，方法不输出真实欧氏距离，除非 δ-distance 选择为欧氏距离；而对一般隐式对象这正是难算的情况。作者提出 sqrt(2V_min) 可作为对象间 δ-distance，但它是否能替代 Euclidean distance 用于规划、控制或动力学接触，文中未充分说明。尤其 penetration depth、contact manifold、稳定接触约束都不是直接解决的。

第四，CCD 扩展相当有限。线性平移保持仿射复合下的凸性；一旦有旋转，时空函数通常不再凸。first time of contact 也未解决。因此它更像一个特殊 swept-intersection feasibility test，而不是完整连续碰撞检测框架。

Takeaway

  • 1. 最值得记住的是：碰撞判定不必绑定真实距离。
  • 只要零集、凸性、平方可微三者成立，伪距离就足以给出全局可解的判碰证书。
  • 2. ReLU violation norm + square smoothing 是一个可迁移 pattern：把多隐式约束的可行性检测转成无约束凸优化，这个思想可用于 collision cost、trajectory optimization、接触候选筛选。
  • 3. 未来真正有价值的方向不是再堆更多曲面例子，而是系统化 δ-distance 设计：conditioning-aware、scale-aware、可给距离上下界、可推 penetration/contact 信息。

一句话总结

这篇论文的定位是：用凸伪距离和平方势场把隐式凸体碰撞判定从距离/接触点求解重构为无约束凸可行性优化，是一种以牺牲真实距离语义换取适用性和全局优化结构的方法演化。