Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a quick way to estimate the distance between a point and a triangle in 3d space? Preferably one which never returns higher than the actual distance.

I know I could form a pyramid then use the height equation to get the exact value but I'm just looking for a decent estimate.

share|improve this question
add comment

3 Answers

If you cannot afford to overestimate I suspect you are stuck with finding the exact figure, which is not difficult. Call the triangle $T.$ It lies in a plane. You have a point of interest, call it $P.$ Find the orthogonal projection of $P$ in the plane containing $T,$ call that point $Q.$

If $Q$ lies within, or on an edge or vertex of the triangle, then the distance from $Q$ to $P$ is the answer.

If not: from each edge of the triangle, extend a constant-width strip outwards forever, within the plane containing $T.$. If $Q$ lies in or on an edge of one of these strips, then the projection of $Q$ to the appropriate edge is the closest point to $P$ in $T.$

If that fails, it is one of the three vertices that is closest.

share|improve this answer
    
Thanks for the answer. The actual problem is I need an object distance estimate for a ray tracer. I was hoping there would be some magical formula I hadn't though of but I suspect it would be quicker just to test each triangle rather than this method. –  aaa May 3 '12 at 2:55
add comment

There are lots of easy ways to get a good conservative estimate of the distance. The general idea is, you put a bounding volume around your primitive and compute the shortest distance from the original point to the bounding volume. Every point on the primitive is guaranteed to be at least as far from the point as this distance.

The simplest approach is probably to use an axis-aligned bounding box. Say your triangle has vertices $\mathbf a$, $\mathbf b$, $\mathbf c$, and your point outside the triangle is $\mathbf p$. The extent of the bounding box along the $x$-axis is $[x_\min = \min(a_x,b_x,c_x), x_\max = \max(a_x,b_x,c_x)]$, and similarly for $y$ and $z$. The point $\mathbf q$ in the box $[x_\min, x_\max] \times [y_\min, y_\max] \times [z_\min, z_\max]$ closest to $\mathbf p$ has $x$-coordinate $q_x = \operatorname{clamp}(p_x, [x_\min, x_\max]) = \min(\max(p_x, x_\min), x_\max)$, and similarly for $y$ and $z$. The distance between the point and the box, then, is the distance between the points $\mathbf p$ and $\mathbf q$.

Actually, if you're going to be using this to ray-trace meshes consisting of lots of triangles, then you should really be looking into building a bounding volume hierarchy over the whole mesh as well.

share|improve this answer
add comment

This document tells you how to do it, and the same site has high quality C++ code to do the job quickly and efficiently.

But, I agree with the first answer -- if you want your ray tracer to be fast, then the key is not how fast you can process each triangle. What matters more is your ability to ignore large collections of triangles very quickly, all in one step. This requires some sort of hierarchical data structure.

Alternatively, the modern approach is to write some massively parallel brain-dead code that runs on your GPU (not on your CPU). The code given on the site mentioned above is fairly simple, so you might be able to turn it into a GPU kernel.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.