biVector forum

Closest point to origin on tetrahedron

I implement finding the closest point to origin on tetrahedron. My current approach is getting planes perpendicular to faces through edges and checking signs of oriented distances from origin to these planes:

perpPlane = facePlane · edgeLine
orientedDist = originPoint ∨ perpPlane

Signs of the oriented distances are sufficient to find a closest vertex, edge or face.

Does anyone know, is there a better approach, simpler or with less computations?

@misanthrop Welcome to the bivector forum!

I think I follow your reasoning in introducing these perpendicular planes to the face along the edges. They form a right triangular prism, and the origin is closest to the face only if it lies within the prism, which can be tested by checking that all the signs of the distances to the three sides are the same (O \vee p gives the signed distance from the point O to the plane p. )

When that’s not the case, I see how to proceed if I also have the perpendicular planes to the edges at the endpoints of each edge (perpPlane = edgeLine . endPoint): they let me decide whether the origin is closer to an edge or a vertex. I don’t immediately see how to test this using only the original 12 perpendicular planes in your post.

It’s an interesting geometrical question, in any case.

Sorry, I think I’ve missed some details in the post. Planes perpendicular to faces are not sufficient. I also used signed distances to the planes of tetrahedron faces. Also, as you noted, after finding the edge, planes perpendicular to the edge should be used.

In the example below, I care only about 3 faces of tetrahedron, given that the origin is above the “base” face, in its prism.

I use this as a part of GJK algorithm. Do you know any existent implementations of GJK or similar algorithms using PGA?

There was a similar question regarding intersection of volumes in this post.