What is the best method for finding the closest point on a tetrahedron to a point? I've implemented a method for finding the closest point on a triangle to point using voronoi regions, should i just find the closest point on each of the triangles and return the point on the triangle that has the shortest distance to my test point? Seems like there should be a better way.

Well, let's see. The closest point on a tetrahedron would be one of the following things: One of the vertices of the tetrahedron, along one of the edges of the tetrahedron, on a face of the tetrahedron, or the point itself (if the point is in the tetrahedron). I suggest you try to identify the circumstances under which each of these is the case.

oliii, I decided to go ahead and implement it the way i described it, but are you speaking about barycentric coords as an alternative method?

Quote: Original post by oliii
Also, Dave Eberly has implemented a similar solution for finding the closest point on a triangle to a point. Using voronoi diagram of a triangle would probably be as efficient, but the barycentric coordinates is more elegant in my opinion.

My distance page at my web site also has code for computing distance from a point to a tetrahedron, including producing the closest point. The point-triangle distance uses the method of minimizing a quadratic equation on a triangular domain. The point-tetrahedron code does not do this, but just determines if the point is inside the tetrahedron (considered as a solid, the distance is zero) or computes distance from point to triangle facets and chooses the minimum. The minimization approach is not that complicated, so perhaps I will implement that soon and compare.

Currently I'm using voronoi regions to find where the point lies in relation tp the triangle features and then finding the closest point on the triangle based on which region it lies in.

For my closest point on a Tetrahedron, I just calculate the distance to each facet and take the point with the smallest distance, Would it be beneficial for me to break the tetrahedron up into Voronoi regions?

Also, a quick question about GJK, say if I have two intersecting objects, the minkowski difference contains the origin. In order to find the penetration distance would I calculate the closest point on the minkowski difference to the origin?

Quote: Original post by Christer Ericson
Dave's solution for finding the closest point on a triangle to a point is based on vector calculus: he solves the quadratic minimization problem. The solution I present is based on determining which Voronoi region the query point lies in, and then projecting the query point onto the corresponding feature and thus obtaining the closest point. These two approaches are roughly equally efficient. Off the top of my head I think my approach has a slight efficiency advantage, but don't quote me on that. You really don't want to use an approach based on barycentric coordinates for this problem, because barycentric coordinates are unrelated to orthogonal distances and therefore cannot be directly used in the determination of the boundary cases (i.e on which edge to find the closest point). Therefore a barycentric coordinate approach would have to perform additional computations that the former two approaches would not have to do.

The quadratic minimization leads to computing barycentric coordinates for the query point so that you know which features to test. The triangle decomposes the parametric plane into seven regions, labeled say by a triple of signs of the barycentric coordinates. If inside the triangle, the distance is zero (triangle treated as a solid). If outside, three regions require you to test one edge for closeness. The other three regions require you test two edges for closeness. This last fact is why I believe you say "have to perform additional computations". It is quite possible that the Voronoi approach is faster than the minimization/barycentric approach, but I would want to test this hypothesis with actual implementations. Your Voronoi approach has the cost of determining in which Voronoi region the query point is in. Once in that region, you have only one feature to compute distance to. The comparison in performance is clear: How much does it cost you to determine the Voronoi region and distance-to-feature calculation versus how much does it cost to find barycenteri region and do one or two distance-to-feature calculations? In the minimization approach, the location of the minimum on a feature is found with very small cost. <br><br>At any rate, always an interesting debate for point-triangle distance (or point-simplex distance in general). Another approach that might be feasible is a conjugate gradient search, which is specialized to handle projections.<br>