Robust Differentiable Collision Detection for General Objects

1. Problem Statement

Collision detection is fundamental to robotics (simulation, control, planning), producing witness points (closest points for separated objects or deepest penetration points for overlapping objects). These points define contact positions and directions, which are essential for contact modeling.

However, traditional algorithms like GJK (Gilbert-Johnson-Keerthi) and EPA (Expanding Polytope Algorithm) are non-differentiable. This prevents gradients from flowing through the collision detection process, hindering gradient-based optimization in contact-rich tasks like grasping and manipulation. While recent work introduced randomized smoothing to make witness points differentiable, existing methods suffer from two major limitations:

1. Convexity Restriction: Direction-based smoothing (e.g., Montaut et al.) relies on GJK optimality conditions, limiting it to strictly convex objects.
2. Lack of Robustness: These methods struggle with complex geometries (concave objects), mesh sensitivity, and numerical instability when objects are very close or penetrating.

2. Methodology

The authors propose a robust and efficient differentiable collision detection framework applicable to both convex and concave objects. The method belongs to the family of first-order randomized smoothing but introduces three key innovations:

A. Distance-Based Softmax Smoothing

Instead of the direction-based score used in prior work (which fails for concave shapes), the authors reformulate the witness point $x_1$ as an optimization problem based on distance:
$$x_1 = \arg\max_{v \in \partial O_1} (-\|v - x_2\|^2)$$
They replace the non-smooth $\arg\max$ with a softmax relaxation using a temperature parameter $\tau$:
$$x_1 \approx x_1^* = \sum_{j=1}^N w_j v_{1,j}, \quad w_j = \frac{\exp(-\|v_{1,j} - x_2\|^2 / \tau)}{\sum \exp(\dots)}$$

• Advantage: This distance-based formulation naturally generalizes to concave objects and avoids numerical instability caused by vanishing direction vectors when objects are nearly touching.

B. Adaptive Sampling Strategy

To approximate the object surface, the method samples points $\{v_{1,j}\}$.

• Preprocessing: A large candidate set of vertices and random surface samples is generated.
• Adaptive Selection: In each iteration, a local subset is selected based on the Euclidean distance to the current witness point. The radius $\alpha$ is dynamically updated: $\alpha = \max(\|t_1 - x_1\|, \epsilon)$, where $t_1$ is the target contact point.
• Advantage: Unlike fixed-neighbor sampling (which is sensitive to mesh quality), adaptive sampling ensures robustness across diverse object scales and complex concave geometries.

C. Equivalent Gradient Transport (EGT)

In many robotic tasks (e.g., grasping), the object pose is fixed, and only the robot's pose is optimized. Directly optimizing one pose can be inefficient due to broken symmetry.

• Mechanism: The method uses Lie algebra and the Adjoint operator to transport the gradient that would nominally apply to the fixed object ($T_1$) to the moving object ($T_2$).
• Formula: Updating $T_1$ with $-\lambda \xi_1$ is equivalent to updating $T_2$ with $-\lambda \tilde{\xi}_2$, where $\tilde{\xi}_2 = -\text{Ad}_{T_2^{-1}T_1} \xi_1$.
• Advantage: This allows efficient optimization even when only one object's pose is a decision variable, recovering the performance of joint optimization.

3. Key Contributions

1. General Framework: An open-source, differentiable collision detection framework supporting both convex and concave objects (arbitrary meshes), overcoming the convexity limitation of previous methods.
2. Algorithmic Innovations: Introduction of distance-based smoothing, adaptive sampling, and equivalent gradient transport to ensure robustness and gradient quality.
3. Performance: Significant improvements in accuracy and efficiency over existing baselines (Analytical, Finite Difference, and Direction-based Random Smoothing).
4. Application: Demonstration of the method in dexterous grasp synthesis, successfully refining grasp poses to match target contact points.

4. Experimental Results

The method was evaluated on large-scale datasets (DexGraspNet and Objaverse) containing 10,000 objects (both convex and concave).

• Accuracy: The method achieved a median error below 0.1 mm across 400 random object pairs with 1,024 tasks each.
• Comparison: It outperformed baselines by >40% in terms of mm-level accuracy (Acc@1e-6).
  • Analytical methods often got stuck at vertices (zero derivatives).
  • Direction-based smoothing (RS-1-Dir) failed dramatically on concave objects.
  • Finite Difference/RS-0 were computationally prohibitive and struggled with initial penetrations.
• Efficiency: The method is highly parallelizable on GPUs. The backward pass is significantly faster than zero-order methods (RS-0) and comparable to first-order methods, with a runtime of ~10–20 $\mu$s for complex concave objects.
• Ablation Studies: Confirmed that distance-based smoothing and adaptive sampling are critical for concave objects, and Equivalent Gradient Transport is essential for single-object optimization.

5. Significance

This work bridges a critical gap in robotic learning and control by enabling gradient-based optimization for tasks involving complex, non-convex geometries.

• Enables End-to-End Learning: It allows gradients to flow from contact constraints through collision detection to robot poses and joint angles, facilitating differentiable simulation and planning.
• Robustness: By handling concave objects and varying scales without manual tuning, it makes differentiable collision detection viable for real-world "in-the-wild" robotic applications.
• Future Impact: The authors demonstrate its utility in grasp refinement and suggest future integration into planning and control frameworks for dexterous manipulation.

Code Availability: The implementation is open-source at https://github.com/JYChen18/DiffCollision.