The title says it all, given two convex patches, how to find points/faces that have distance < x? Can I use GJK for this case?

Convex patches are obtained from convex decomposition, see here. If I read it correctly, I don't think methods used in that paper can give points/faces that satisfy above condition.

  • $\begingroup$ Are you looking for pairs of (point, face) that are separated by less than x, or a list of all points and faces that are less than x from some point/face on the other patch? $\endgroup$ – trichoplax Jan 20 '17 at 14:12
  • $\begingroup$ Should be the later. $\endgroup$ – Bla... Jan 20 '17 at 14:17

Yes GJK is appropriate for this.

The overall algorithm of GJK goes something like

simplex = empty
direction n = arbitrary

while(not finished){

    find furthest point p1 in mesh 1 in direction n
    find furthest point p2 in mesh 2 in direction -n

    supplement simplex with point p1-p2

    if(simplex is tetrahedron) simplify simplex

    direction n = pick direction perpendicular to simplex pointing to origin


you can then use the simplex at the end of the loop to calculate the distance from it to the origin and set finished to true and you will get a collection of points on each mesh which make up a pair of faces that are closer than x.

  • $\begingroup$ Can this be extended to give a list of all faces that are closer than x to the other mesh, or will it only work to give a single pair of faces? $\endgroup$ – trichoplax Jan 21 '17 at 11:20

Your Answer

