Fastest way to compute point to triangle distance in 3D?

Question

One obvious method for computing the minimum distance from a point to a 3D triangle is to project the point onto the plane of the triangle, determine the barycentric coordinates of the resulting point, and use them to determine whether the projected point lies within the triangle. If not, clamp its the barycentric coordinates to be in the range [0,1], and that gives you the closest point that lies inside the triangle.

Is there a way to speed this up or simplify it somehow?

Answer 1

Assuming you're using one of the known fast algorithms, the only way to speed it up is when you are doing a lot of measurements on a lot of triangles. In that case, you can keep a lot of quantities precomputed in "edge" or "winding" structures. Instead of storing the 3 points, you store meshes comprised of edge structures. Projection then becomes very quick and barycentric tests can be coded so that they are branch-predictable.

The real key is to just keep everything in cache. Processors can do MUL and DIV in nearly 1 clock cycle so memory is usually the bottleneck.

Also, consider writing the algo in SSE3 or something similar (such as Mono's SIMD support). It's work, but you can usually do a couple triangles at a time if you think hard enough about it.

I'll try to find some papers on the topic, but you might want to Google for "Ray Mesh Intersection". That will bring up all the great work from the 80s and 90s when people worked hard on optimizing this stuff.

Answer 2

There are different approaches to finding the distance from a point P0 to a triangle P1,P2,P3.

1. The 3D method. Project the point onto the plane of the triangle and use barycentric coordinates or some other means of finding the closest point in the triangle. The distance is found in the usual way.

2. The 2D method. Apply a translation/rotation to the points so that P1 is on the origin, P2 is on the z-axis, P3 in the yz plane. Projection is of the point P0 is trivial (neglect the x coordinate). This results in a 2D problem. Using the edge equation its possible to determine the closest vertex or edge of the triangle. Calculating distance is then easy-peasy.

This paper compares the performance of both with the 2D method winning.