Question: EPA Position Computation

[psclklnk]

Hi everyone,

first of all thanks for this brilliant library! I am looking into the problem of collision detection for a project I am working on, specifically focusing on EPA. After looking up the original papers in which EPA was proposed, I still am a bit puzzled about the computation of the contact position, as it was not described in the seminal paper [1] and I also couldn't find any precise description of what is the principle behind this computation.

Looking into the code, it seems like an average over the support points from both objects is computed for the half of the vertices in the polytope closest to the origin:

libccd/src/ccd.c

Lines 156 to 168 in 63d3a91

	qsort(vs, len, sizeof(ccd_pt_vertex_t *), penEPAPosCmp);
	ccdVec3Set(pos, CCD_ZERO, CCD_ZERO, CCD_ZERO);
	scale = CCD_ZERO;
	if (len % 2 == 1)
	len++;
	for (i = 0; i < len / 2; i++){
	ccdVec3Add(pos, &vs[i]->v.v1);
	ccdVec3Add(pos, &vs[i]->v.v2);
	scale += CCD_REAL(2.);
	}
	ccdVec3Scale(pos, CCD_ONE / scale);

Without explicitly knowing what's going on, this sounds like it computes some average between the two object boundaries. For what I have in mind it would be interesting to compute two individual points where each point is on the boundary of one object. If I understand the EPA algorithm correctly, these two points should then be joined by the direction return by EPA times the computed penetration depth (obviously with some approximation error).

My gut feeling (and one plot I investigated for some simple shapes) told me that I would need to compute

p_1 = pos + 0.5 * depth * dir
p_2 = pos - 0.5 * depth * dir

where pos, depth and dir are the values returned by ccdGJKPenetration.

Is this gut feeling correct? If so, can you enlighten me what's going on in the computation of the contact position in EPA? If there is some mathematical formulation of the idea I would be more than happy to read it.

Best regards
Pascal

[1] Van Den Bergen, Gino. "Proximity queries and penetration depth computation on 3d game objects." Game developers conference. Vol. 170. 2001.