Continuous penalty forces

Min Tang, Dinesh Manocha, Miguel A. Otaduy, Ruofeng TongACM Trans. Graphics 2012 · DOI

TL;DR

This paper introduces a novel "Continuous Penalty Force" (CPF) formulation for simulating contact between rigid and deformable objects. By tracing contact features along their trajectories and integrating forces over time, CPF significantly improves simulation stability and robustness, reducing issues like jitter and inter-penetration that plague traditional discrete penalty methods.

What Problem Does This Paper Address?

Simulating realistic physical interactions in computer graphics, robotics, and virtual environments relies heavily on accurate contact and collision handling. Traditional "penalty-based" methods are computationally efficient but suffer from significant robustness and stability problems. These issues arise from discontinuities in force calculations, especially when objects penetrate. This can lead to undesirable artifacts like jitter (high-frequency oscillations), instability (unbounded growth of physical quantities), and "pop-through" (objects passing through each other). The core challenge is to maintain stable, smooth, and accurate contact responses, especially for deformable objects and under large time steps, without incurring prohibitive computational costs.

Methods

The authors propose a "Continuous Penalty Force" (CPF) formulation that addresses the limitations of discrete methods. The key innovations are:

  • Continuous Collision Detection (CCD): Instead of checking for collisions only at discrete time steps, CPF uses CCD to identify the first time of contact between features (vertices, edges, triangles) and traces their trajectories. This allows for a more accurate understanding of how features interact over time.
  • Penetration Time Intervals: Based on CCD, the algorithm identifies intervals of time during which features are inter-penetrating.
  • Continuous Force Integration: Rather than calculating a force based on penetration depth at a single point in time, CPF integrates the penalty force over these identified penetration time intervals. This effectively "averages" the force along the trajectory, smoothing out discontinuities.
  • Analytic Expressions: The paper derives closed-form, polynomial expressions for the continuous penalty forces for both vertex-face (VF) and edge-edge (EE) contact pairs. This allows for efficient computation of the accumulated impulse.
  • Feature Tracing: Contact features (points of contact and normals) are traced along their deforming trajectories, ensuring continuity and smoothness in the force calculation.

Datasets

The paper evaluates its method on several benchmarks, including:

  • Chain Benchmark: A swinging chain colliding with a rigid box.
  • Stick Benchmark: A ball bouncing off a stick.
  • Octopus Benchmark: A soft, deforming octopus in a rigid bowl.
  • Cloth Benchmark: Multiple deforming tori falling onto a cloth.
  • Dragons Benchmark: Deforming dragons falling into a rigid bucket.
  • Rings Benchmark: Falling rings colliding with a base.

No new datasets were introduced; existing scenarios were used to demonstrate the method's effectiveness.

Key Insights and Ideas

  • Trajectory Matters: The paper strongly emphasizes that the path an object takes between discrete time steps is crucial for accurate contact force calculation, a factor often ignored by discrete methods.
  • Averaging Smooths Discontinuities: By integrating forces over time intervals, CPF acts as a low-pass filter, smoothing out the noisy and discontinuous forces characteristic of discrete methods.
  • Analytic Solutions for Efficiency: Deriving polynomial expressions for the continuous forces allows for efficient impulse computation, keeping the overhead manageable.
  • Improved Robustness with Minimal Cost: The CPF method offers significant improvements in stability and robustness with only a modest increase in computational cost compared to discrete methods.

Key Results

  • Reduced Jitter and Instability: Benchmarks like the Chain and Cloth simulations show significantly smoother force profiles and more stable behavior with CPF compared to discrete methods, especially under large time steps.
  • Alleviated Inter-Penetration: CPF successfully resolves inter-penetration issues in scenarios like the Octopus and Rings benchmarks, where discrete methods fail.
  • Accurate Trajectories: The Stick Benchmark demonstrates that CPF produces more physically accurate bounce trajectories compared to discrete methods.
  • Computational Cost: CCD and CPF computation take approximately 3 µsec per feature pair. While this is 3-4 times slower than discrete collision detection and force computation, the authors argue the stability gains justify the overhead.

Limitations and Future Work

  • Degenerate Scenarios: The method may require special treatment for degenerate collision scenarios, such as parallel edges in edge-edge collisions.
  • Linear Trajectory Approximation: For objects with large rotational motions, approximating trajectories as linear between discrete time steps might reduce accuracy.
  • Local Penetration Depth: The current formulation uses local penetration depth, which doesn't guarantee global resolution of inter-penetrations.
  • Explicit Integration: The current implementation uses explicit integration, which could still lead to instability with very large time steps or contact stiffness.
  • Future Work: The authors suggest extending the approach to handle higher-order trajectories, improving robustness against all types of inter-penetrations, and exploring implicit integration methods for enhanced stability. They also propose combining CPF with constraint-based methods for more complex scenarios.

Summary updated

BibTeX
@article{tang2012continuous,
  author = {Min Tang and Dinesh Manocha and Miguel A. Otaduy and Ruofeng Tong},
  title = {{Continuous penalty forces}},
  journal = {ACM Trans. Graphics},
  year = {2012},
  doi = {10.1145/2185520.2185603},
}
Figure