Implementation:Google deepmind Mujoco Engine Collision GJK

Knowledge Sources	Google_deepmind_Mujoco
Domains	Physics Simulation, Collision Detection, Computational Geometry
Last Updated	2026-02-15 04:00 GMT

Overview

Implements the GJK (Gilbert-Johnson-Keerthi) distance algorithm and EPA (Expanding Polytope Algorithm) for computing distances and penetration depths between convex objects.

Description

This module provides MuJoCo's native implementation of the GJK algorithm for computing the minimum distance between two convex objects, and the EPA algorithm for computing penetration depth when objects are intersecting. The GJK algorithm iteratively builds a simplex in the Minkowski difference of the two objects, using the subdistance algorithm (adapted from Montanari et al., ToG 2017) to compute barycentric coordinates of the closest point to the origin. When intersection is detected, the EPA expands a polytope to find the minimum translation vector. The module also supports multi-contact generation via polygon clipping on the contact manifold.

Usage

Called by engine_collision_convex.c through the mjc_ccd function when convex geometry pairs need distance computation or penetration resolution. This is MuJoCo's native CCD implementation used when the mjDSBL_NATIVECCD flag is not set.

Code Reference

Source Location

Repository: Google_deepmind_Mujoco
File: src/engine/engine_collision_gjk.c
Lines: 1-2357

Key Functions

// Main entry point: compute distance (negative = penetration depth)
mjtNum mjc_ccd(const mjCCDConfig* config, mjCCDStatus* status,
               mjCCDObj* obj1, mjCCDObj* obj2);

// GJK algorithm: iteratively find closest point on Minkowski difference
static void gjk(mjCCDStatus* status, mjCCDObj* obj1, mjCCDObj* obj2);

// GJK intersection test: return 1 if in contact, 0 if not, -1 if inconclusive
static int gjkIntersect(mjCCDStatus* status, mjCCDObj* obj1, mjCCDObj* obj2);

// EPA: expand polytope to find penetration depth and witness points
static Face* epa(mjCCDStatus* status, Polytope* pt,
                 mjCCDObj* obj1, mjCCDObj* obj2);

// Subdistance: barycentric coordinates of closest point in simplex
static void subdistance(mjtNum lambda[4], int n, const Vertex simplex[4]);

// Simplex projection subroutines (3D, 2D, 1D)
static void S3D(mjtNum lambda[4], const mjtNum s1[3], const mjtNum s2[3],
                const mjtNum s3[3], const mjtNum s4[3]);
static void S2D(mjtNum lambda[3], const mjtNum s1[3], const mjtNum s2[3],
                const mjtNum s3[3]);
static void S1D(mjtNum lambda[2], const mjtNum s1[3], const mjtNum s2[3]);

// Multi-contact generation via polygon clipping
static void multicontact(Polytope* pt, Face* face, mjCCDStatus* status,
                         mjCCDObj* obj1, mjCCDObj* obj2);

Import

#include "engine/engine_collision_gjk.h"

I/O Contract

Inputs

Name	Type	Required	Description
config	const mjCCDConfig*	Yes	Configuration: max iterations, tolerance, max contacts, allocator callbacks
obj1	mjCCDObj*	Yes	First convex object with support function and geometry data
obj2	mjCCDObj*	Yes	Second convex object with support function and geometry data

Outputs

Name	Type	Description
status	mjCCDStatus*	Witness points (x1, x2), simplex data, and contact results
return value	mjtNum	Signed distance: positive = separated, negative = penetration depth

Related Pages

Page Connections

Double-click a node to navigate. Hold to expand connections.

Principle

Implementation

Heuristic

Environment