# Given two convex patches, how to find points/faces that have distance < x?

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.

• 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? Jan 20 '17 at 14:12
• Should be the later. 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.

• 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? Jan 21 '17 at 11:20