CODEWITHSUNDEEP
geometrycollision-detection
I J
I J

Reputation: 825

closest distance between hull and box

What would be the best way to find the closest distance between a convex hull and an axis aligned box ? By closest distance I mean the pair of points on the hull and box that are closest to each other. We can assume that we know that we know that the hull and box do not intersect.

The hull is given by faces, vertices and I can triangulate the faces if necessary.

Upvotes: 3

Views: 867

Answers (2)

I J
I J

Reputation: 825

The paper here gives an algorithm to find closest pair between two convex hulls. http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf

For some time, I thought that may be one of the hulls being AABB would make this algorithm unnecessary. Unfortunately, I didn't find that to be true.

The idea behind this algorithm is that you take Minkowski difference of two hulls. The closest pair would be a point in this Minkowski difference closest to the origin. Cartheodory's theorem says that in a d dimensional space, you need only d+1 points to represent a point in the hull. So basically you choose d+1 sized sets of the minkowski difference and find their closest distance to the origin. The closest point to the origin is found through an iterative algorithm.

Upvotes: 5

Alexei Levenkov
Alexei Levenkov

Reputation: 100537

For case of hull inside a box (or any other convex object):

If they don't intersect than the closest point in the hull would be a vertex of the hull, never middle of a face.

Simply iterating trough all vertices of the hull and computing distance to each side of the box will let you find pair of points (vertex of the hull + point on a face of the box). Note that is a face of the hull is parallel to one of the box's faces you'll get more than one pair at the same distance.

Hull outside the box:

Pair contains point of an edge of the hull or box and point on the second object. Iterating through all edges of the hull and box and compute distance to all faces of the other object looks like an approach, but better one should exist.

Upvotes: 0

Related Questions