Determining if and where a photon will collide with a polygon in 3D space.

Question

The problem is straight forward:

1) We have a photon traveling from Point 1 (x,y,z) to Point 2 (x,y,z), both of which could be located anywhere in 3D space.

2) We have a polygon that is both rotated randomly on the x-axis and/or y-axis and also located anywhere in 3D space.

3) We want to find: a) if the photon will collide with the polygon at all and b) if it does where will that be (x,y,z)?

An image of the problem: http://dl.dropbox.com/u/3150177/Programming/3D/Math/Photon%20Path/Photon%20Path.png

The aim of this is to calculate how the photon's path should be altered from an interaction(s) with the polygon(s).

I am reading up on this subject now but I was wondering if anyone could give me a head start. Thanks in advance.

Answer 1

Sounds like you are looking for a ray/polygon intersection test.

I can't remember the details but I imagine you split it into two parts. First you find the point on the polygon's plane that the ray intersects at. This can be got from a simple ray/plane intersection test. Secondly use a co-ordinate system on the polygon's plane to test whether the intersection point lies within the polygon. This can be got from a point-in-polygon test.

Answer 2

The photon is traveling with vector v = p2 - p1 starting at p1, creating this line:

p1 + v * a 

To find out if the photon collides with the polygon you have to find a value for a for:

p1 + v * a = polygon

For example:

p1 is (15, 4, 5)
p2 is (10, 1, 3) 
and polygon is a 10x10 square: (-5...5, -5...5, 0)

v = p2 - p1 = (-5, -3, -2)

p1 + v * a = pol makes:

p1.x + v.x * a = pol.x
p1.y + v.y * a = pol.y
p1.z + v.z * a = pol.z

a = (pol.z - p1.z) / v.z = (0 - 15) / -2 = 7.5
pol.x = p1.x + v.x * a = 15 + -5 * 7.5 = -22.5
pol.y = p1.y + v.y * a = 10 + -3 * 7.5 = -12.5

The -22.5 is not between -5 and 5 and -12.5 is not between -5 and 5, so the photon does not collide with the polygon.

It's been a while since I've done this so I may have made some mistakes. I used the fact that pol.z = 0 to calculate a. You may have to rotate the polygon to line up with one axis, as long as you rotate p1 around the polygon's center as well.

Answer 3

General overview:

1) Segment-Plane Intersection: Determine if the line segment connecting points 1 and 2 intersects the plane containing the polygon. If it doesn't, then it will never intersect the polygon, and you're done.

2) Find Point of Intersection: Determine the point at which the line segment and plane intersect. This will provide the information you want in 3-b in your question. Call this point Q

3) Determine if Q is interior to the polygon: One method of determining this is here, but a well crafted Google search will likely result in others. You can optimize for different types of polygons you expect (i.e. convex) or if the plane containing the polygon is axially aligned (i.e. one of the axes for your coordinate system is normal to the plane containing the polygon).

Assumption: All of the polygon's points are co-planar.

Answer 4

You're doing ray tracing. Most efficient is to break the polygon into triangles and use the Moeller ray-triangle test. Or perhaps the Wald test. There are also variants that use extra stored data beyond just the vertex information which can be even faster if you're doing multiple rays against the same triangle. Google provides so many results, I haven't selected a "best" one to put here.

Answer 5

Ray / triangle intersections are well understood and quite easy. The rotations are harder, though.

Perhaps you could transform the triangle's vertices using a rotation matrix and then use a simple ray / triangle intersection?