<p>Yes GJK is appropriate for this. </p>

<p>The overall algorithm of GJK goes something like </p>

<pre><code>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

}
</code></pre>

<p>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.</p>

CC BY-SA 3.0
2017-01-21T11:20:42.250Z
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?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-01-20T17:00:29.737Z
2017-01-21T11:18:33.813Z
2017-01-21T11:18:33.813Z
ratchet freak
<p>The title says it all, given two convex patches, how to find points/faces that have distance &lt; x?  Can I use GJK for this case?</p>

<p>Convex patches are obtained from convex decomposition, see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.3141&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">here</a>. If I read it correctly, I don't think methods used in that paper can give points/faces that satisfy above condition.</p>

CC BY-SA 3.0
2017-01-20T14:12:59.767Z
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?
trichoplax is on Codidact now
CC BY-SA 3.0
2017-01-20T14:17:09.473Z
Should be the later.
Bla...
<computational-geometry>
Given two convex patches, how to find points/faces that have distance < x?
Bla...
# Given two convex patches, how to find points/faces that have distance < x?

(Asked by: username_0 on 2017-01-20)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.3141&rep=rep1&type=pdf). If I read it correctly, I don't think methods used in that paper can give points/faces that satisfy above condition.

**Tags:** computational-geometry

> **Comments:**
> **username_1**: 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?  
> **username_0**: Should be the later.  

---

## 1 answers

### Answer by username_2 on 2017-01-20. Score: 2

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.

> **Comments:**
> **username_1**: 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?  

---

