1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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 is on Codidact now
    Commented Jan 20, 2017 at 14:12
  • $\begingroup$ Should be the later. $\endgroup$
    – Bla...
    Commented Jan 20, 2017 at 14:17

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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 is on Codidact now
    Commented Jan 21, 2017 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.