What is the fastest way to find the point of intersection between a ray and a polygon?

Question

Pretty much as the question asks. Answers preferably in pseudo code and referenced. The correct answer should value speed over simplicity.

Answer 1

See Intersections of Rays, Segments, Planes and Triangles in 3D. You can find ways to triangulate polygons.

If you really need ray/polygon intersection, it's on 16.9 of Real-Time Rendering (13.8 for 2nd ed).

We first compute the intersection between the ray and [the plane of the ploygon] pie_p, which is easily done by replacing x by the ray.

 n_p DOT (o + td) + d_p = 0 <=> t = (-d_p - n_p DOT o) / (n_p DOT d)

If the denominator |n_p DOT d| < epsilon, where epsilon is very small number, then the ray is considered parallel to the polygon plane and no intersection occurs. Otherwise, the intersection point, p, of the ray and the polygon plane is computed: p = o + td. Thereafter, the problem of deciding whether p is inside the polygon is reduced from three to two dimentions...

See the book for more details.

Answer 2

Whole book chapters have been devoted to this particular requirement - it's too long to describe a suitable algorithm here. I'd suggest reading any number of reference works in computer graphics, in particular:

• Introduction to Ray Tracing, ed. Andrew S. Glassner, ISBN 0122861604

Answer 3

For ray-triangle/square here's a very good explanation
http://www.blackpawn.com/texts/pointinpoly/default.html