Intersecting a minkowski difference from the origin in a direction, how do i find the face im intersecting?

Question

Basically i have a set of vertices on the hull of a minkowski difference of two polyhedra. I want to find the distance from the origin to the hull in some arbitrary predetermined direction. Heres a quick 2D sketch:

So the issue is finding what triangular face/plane the ray is going to intersect. Once i have that plane i simply do a line/plane intersection test. My issue is finding the correct face/plane. Any ideas? Is there some set of dot product/cross product/triple product tests i can do to determine it? Or is it more complicated then that?

If your wondering what this is for im using a GJK algorithm to determine whether two objects are intersecting (which i've got working). If there is a collision i would like to find the penetration depth in a particular direction (which will be the direction of motion of the object).

Answer 1

Project the polyhedron in the direction of the ray, and your problem reduces to 2D, and finding which triangle encloses the origin. To test a single triangle, consider whether a given directed line segment (AB) is going clockwise or counterclockwise with respect to the origin. This is easy to determine with a simple cross-product test: it's counterclockwise iff A x (B-A) > 0.

If all three sides of a triangle have the same sense (clockwise or counterclockwise) then the triangle encloses the origin and that's the face you want.

EDIT:
Since your polyhedron is a hull it is convex, And since it is convex you can search the surface in an efficient way. You can traverse the edges in a very simple "walk uphill/downhill" way to find the two vertices farthest along the the ray in either direction. Then after you project the poyhedron you can start from these two points and do a similar climb toward the origin. This will be O(sqrt(n)).