Interactive generalized penetration depth computation for rigid and articulated models using object norm

Min Tang, Young J. KimACM Trans. Graphics 2014 · DOI

TL;DR

This paper introduces a novel, real-time algorithm for accurately computing "generalized penetration depth" (PDg) for both rigid and articulated objects. By defining a new "object norm" metric and using iterative optimization on the contact space, their method significantly speeds up this complex calculation, making it practical for interactive applications.

What Problem Does This Paper Address?

In computer graphics and robotics, accurately determining how much objects overlap (penetration depth or PD) is crucial for simulations, motion planning, and haptic feedback. Traditional "translational PD" (PDt) often overestimates overlap, especially for articulated objects (like robots with joints), because it only considers simple sliding motions. "Generalized PD" (PDg) aims to find the minimal rigid motion to separate objects, which is a more accurate and physically meaningful measure. However, calculating PDg is computationally very expensive, often requiring complex arrangements of high-dimensional contact surfaces, making existing methods too slow for interactive use. Furthermore, no efficient PDg algorithms existed for articulated models.

Methods

The core of this paper is the introduction of a generalized "object norm" metric for articulated models. This norm quantifies the "effort" or "energy" required to move an object or a link within an articulated chain. The algorithm then approximates PDg through an iterative, constrained optimization process on the "contact space" (the space of configurations where objects are touching).

Key steps include:

  • Object Norm Formulation: Generalizing the object norm from rigid bodies to articulated models, considering different joint types (prismatic, revolute, spherical).
  • Iterative Constrained Optimization:
    • Free-configuration Selection: Finding an initial collision-free pose.
  • Contact-space Projection (CSP): Projecting the initial pose onto the contact space using generalized continuous collision detection (CCDg) and greedy optimization. This step aims to find a contact configuration that minimizes the object norm.
  • Constrained Optimization: Linearizing the contact constraint to create a "linearized local contact space" (LLCS) and solving an LCP (Linear Complementarity Problem) to find a locally optimal configuration that minimizes the object norm.
  • Re-projection: Ensuring the resulting configuration remains on the contact space.
  • Handling Articulated Models: Extending the object norm and optimization process to handle the complex kinematics of articulated bodies with multiple joints.

Datasets

The paper does not introduce new datasets. Instead, it uses standard 3D models for benchmarking, including:

  • Rigid Models: Bunny, Dragon, Spoon, Cup, Placement, Robot under the Bridge, Grasping, Pawn/CAD, Hammer/Bumpy-Sphere, L-shape/Torusknot.
  • Articulated Models: Puma robot (with different configurations), Hand model.

These models are used to test the algorithm's performance and accuracy against existing methods and analytical solutions where possible.

Key Insights and Ideas

  • Object Norm for Articulated Models: The generalization of the object norm to articulated models is a crucial contribution, providing a unified metric for measuring motion effort across different joint types.
  • Linearized Contact Space: Linearizing the complex, high-dimensional contact space is a key practical simplification that enables efficient optimization.
  • Iterative CSP and Optimization: The multi-step approach of CSP followed by constrained optimization effectively navigates the complex search space to find a good approximation of PDg.
  • Real-time Performance: The algorithm achieves interactive rates (tens of milliseconds) for complex models, which was a significant bottleneck for previous PDg methods.
  • PDg for Articulated Models: This paper is the first to present a practical algorithm for computing PDg for articulated models, opening up new possibilities for their simulation and control.

Key Results

  • Speed: The algorithm can compute locally optimal PDg for rigid and articulated models with tens of thousands of triangles in tens of milliseconds.
  • Accuracy: For rigid models, the algorithm shows competitive or better results compared to prior state-of-the-art methods like [Zhang et al. 2007a], with small relative errors. For a specific analytical case of articulated models, the results are very close to the optimum (mean squared error of 0.0027).
  • Applications: The paper demonstrates successful applications in:
  • Motion Planning: Improving retraction-based planners by generating more relevant contact samples.
  • Physically-based Animation: Helping to find collision-free initial poses for complex articulated characters.
  • Grasping: Assisting in finding valid, collision-free grasp poses for novel objects.

Limitations and Future Work

  • Local Optima: The algorithm guarantees only locally optimal PDg solutions and can get stuck in local minima.
  • Initial Configuration Dependence: The quality of the result depends on the initial collision-free configuration selection.
  • Complexity for High DoFs/Contacts: For models with very high degrees of freedom or a large number of contacts, the algorithm might require many iterations.
  • No Closed Loops: The current algorithm does not handle articulated models with closed kinematic loops.
  • Future Work: The authors suggest extending the work to:
  • Multi-body and deformable body simulations.
  • Integrating PDg into constraint-based dynamics for better convergence.
  • GPU-based or parallel implementations.
  • Computing PDg for multiple moving, overlapping bodies simultaneously.

Summary updated

Abstract

We present a novel, real-time algorithm to accurately approximate the generalized penetration depth ( PD g ) between two overlapping rigid or articulated models. Given the high complexity of computing PD g , our algorithm approximates PD g based on iterative, constrained optimization on the contact space, defined by the overlapping objects. The main ingredient of our algorithm is a novel and general formulation of distance metric, the object norm , in a configuration space for articulated models, and a compact closed-form solution for it. Then, we perform constrained optimization, by linearizing the contact constraint, and minimizing the object norm under such a constraint. In practice, our algorithm can compute locally optimal PD g for rigid or articulated models consisting of tens of thousands of triangles in tens of milliseconds. We also suggest three applications using PD g computation: retraction-based motion planning, physically-based animation, and data-driven grasping.
BibTeX
@article{tang2014interactive,
  author = {Min Tang and Young J. Kim},
  title = {{Interactive generalized penetration depth computation for rigid and articulated models using object norm}},
  journal = {ACM Transactions on Graphics},
  year = {2014},
  doi = {10.1145/2517108},
}
Figure