[Math] Closest point on a 3D triangle, is this algorithm correct

convex optimizationgeometrylinear algebratriangles

Given a point $P$ and three triangle vertices $U$, $V$, $W$, all in $\mathbb{R}^3$, I need to find the point in the triangle $UVW$closest to $P$. Does the following algorithm work, or have I missed any case?

  1. Project $P$ onto the plane spanned by $UVW$. If the projected point lies inside the triangle, this is the closest point. Otherwise:

  2. Project $P$ onto the three lines $UV$, $VW$, $WU$. If any of the projections lies on the edge, add these points to a list of candidates.

  3. Add the three vertices to the list of candidates. Now we have 3-6 solution candidates, and one of these must be the closest point on the triangle.

Have I missed anything? For instance, could the solution lie on the edge of the triangle even if that edge was discarded in step 2? I couldn't find a counter-example, but I don't trust my skills that much.

Best Answer

That algorithm is fine. But it's easier, once you've projected to a point $Q$ in the plane, to search in the plane. If $Q$ is interior to the triangle, you're done, as you observed.

Now you can test, for each edge, say $UV$, whether the projection $Q$ and the remaining point $W$ are on opposite sides of the line $UV$. If so, $W$ is not the closest point, and you can find the closest point by projecting onto $UV$: if the projection lies between $U$ and $V$, it's the closest point; if not, then one of $U$ or $V$ is.

Thomas Akenine-Moller has done a LOT of work on this kind of thing, and has many very clever algorithms for doing it with the smallest possible number of computations. To be more precise, he's studied ray-triangle interserction algorithms, but many of the ideas there apply here as well. Sample paper: Tomas Möller and Ben Trumbore. Fast, minimum storage ray-triangle intersection. J. Graph. Tools, 2(1):21–28, October 1997.

As for "have I missed anything", one way to think of it is that you start at the point $Q$ and draw ever-expanding disks until one touches the triangle. When you view it that way, it's pretty clear that the choices you described are exhaustive.

(Apologies for my earlier answer: I was just being too glib, and should have paused and thought for just a moment longer...)

Related Question