gpdmink

A Python implementation for GPDMink: gradient-parameterized deformable Minkowski sums between convex bodies with smooth bounding surface.

Article

"Gradient-parameterized deformable Minkowski sum with applications on contact detection" Article link, Supplimentary Video

Usage

Demonstration scripts

Scripts for demonstrating the usage of this package. The plots correspond to the illustrative figures in the article.

• demo_minkowski_sum.py: Demonstrate GPDMink algorithm for: (1) bodies with linear transformations; (2) only one body has nonlinear deformation (e.g., tapering and bending); (3) both bodies have nonlinear deformations. Corresponding figures in the article: Figs. 1, 3, 4, 5.
• demo_superquadrics.py: Demonstrate superquadrics with linear and nonlinear deformations. Corresponding figures in the article: Fig. 2.
• demo_collision_detection.py: Demonstrate CFC collision detection between two convex bodies with smooth bounding surface, one of which has nonlinear deformation. Also includes cost values at each iteration. Corresponding figures in the article: Fig. 6.

Test scripts

Unit test files are located in /test folder

• test_minkowski_sum.py: Unit test for GPDMinkowskiSum function. Compute gradient-parameterized deformable Minkowski sums between two convex bodies with smooth surface: (1) in canonical form, (2) with linear transformations, (3) when at most one body has nonlinear deformation (e.g., tapering) and (4) when both bodies have nonlinear deformations (using nonlinear least-squares, takes longer time).
• test_collision_detection.py: Unit test for CollisionDetection functions.
• test_ellipsoid.py: Unit test for Ellipsoid class. Compute closest points between two ellipsoids and plot them.
• test_superquadrics.py: Unit test for SuperQuadrics class. Generate points on superquadric surface and plot two superquadrics.

Class

• GeometryModel: Superclass for defining geometric models
• SuperQuadrics: Implementations of methods for superquadric model
• Ellipsoid: Implementations of methods for ellipsoidal model

Function

• GPDMinkowskiSum: Functions to compute Minkowski sums using the proposed methods (exact closed-form and approximated).
• NonlinearDeformation: Functions to compute surface points and gradients after nonlinear deformations (e.g., tapering, bending, twisting).
• CollisionDetection: Functions for CFC collision detection.
• Utilities: Utility functions.

Citation

If you find our work useful, please consider citing:

@article{ruan2025gradient,
  title={Gradient-parameterized deformable Minkowski sum with applications on contact detection},
  author={Ruan, Sipu and Mei, Jundong},
  journal={Multibody System Dynamics},
  year={2025},
  publisher={Springer}
}

Reference

• Compute closed-form Minkowski sums (canonical and with linear transformation): Ruan, S. and Chirikjian, G. S.. Closed-form Minkowski sums of convex bodies with smooth positively curved boundaries. Computer-Aided Design, 143, 103133.