Google Answers Logo
View Question
 
Q: 3D ray intersection with a rectangle ( Answered 5 out of 5 stars,   3 Comments )
Question  
Subject: 3D ray intersection with a rectangle
Category: Science > Math
Asked by: toasty-ga
List Price: $5.00
Posted: 30 May 2002 16:16 PDT
Expires: 06 Jun 2002 16:16 PDT
Question ID: 18979
How do you determine if, and more importantly where, a ray (line
vector) intersects a rectangle in 3d given the four 3D cordinates
(x,y,z) of the rectangle, the origin 3D cordinate of the ray, and it's
direction vector.

The rectangle can be at any angle, so a simple solution where it's
idealy perpendicular to the ray will not work. I am a programmer,
rather than a mathematician, so speed is relevant too if possible, but
I'm more concerned with being able to solve the problem first. My trig
is rusty but I can solve most general steps, such as dot products, and
cross products of the vectors, I just need a forumla for solving where
the ray intersects the rectangle (if it does at all), preferably with
the intersection cordinates being relative to the rectangle and not
the entire 3d space.

Please feel free to ask for more information if needed.
Answer  
Subject: Re: 3D ray intersection with a rectangle
Answered By: smileywiley-ga on 30 May 2002 18:50 PDT
Rated:5 out of 5 stars
 
Hello,

Lets define some terminology first:  P1, P2, P3 and P4 are the
vertices defining the rectangle in clockwise fashion.  x1, y1 and z1
are the x, y and z coordinates of P1 and so on. Let V1 = P2 - P1 and
V2 = P4 - P1 be 2 adjacent vectors of the rectangle.  Let R0 = (x0,
y0, z0) be the origin point of the ray and let Rd = (xd, yd, zd) be
the ray vector.

There are several ways to find out if a ray intersects with a
rectangle or not.
The majority of the methods first find out where the ray intersects
the plane that the rectangle lies on.  (I'm assuming we're talking
about Euclidean spaces)

To do this we first derive the plane equation from the points of the
rectangle.

The general equation for a plane is Ax + By + Cz + D = 0 where A, B, C
and D are constants.  The values of A, B and C are the x, y and z
components of the vector normal to the rectangle.  The value of D is
the distance of the rectangle to the origin.

To find the normal vector you take the cross product of adjacent
vectors of the rectangle (for example V1xV2 [I'll skip the explanation
of cross product since you mentioned you can do that]).

Finding the distance from a point to the plane is a little long
(including slow functions like square root) so we'll sidestep that
plugging x4, y4 and z4, along with the x, y and z components of the
normal for A, B and C, into the general equation and solve for D.

That was the general method of getting the plane equation.  It works
but here's a faster more direct way of deriving it:

Manipulate the general plane equation into this form:
(A/D)x + (B/D)y + (C/D)z = -1
(hopefully, you know what I did to get there).  Then plug in P1, P2,
and P3 into that equation to get 3 different equations.  Apply
Cramer's Rule to solve for A/D, B/D and C/D.

You should get the following results:

A = y1(z2-z3) + y2(z3-z1) + y3(z1-z2)
B = z1(x2-x3) + z2(x3-x1) + z3(x1-x2)
C = x1(y2-y3) + x2(y3-y1) + x3(y1-y2)
D = -x1(y2*z3 - y3*z2) - x2(y3*z1 - y1*z3) - x3(y1*z2 - y2*z1)

Now we have the plane equation.  Lets find the intersection of the ray
with the plane.

We define the ray parametrically as R(t) = R0 + Rd*t.  

Then we plug in R(t) into the plane equation we derived earlier:
A(x0 + xd*t) + B(y0 + yd*t) + (z0 + zd*t) + D = 0

then solve for t:
t = -(A*x0 + B*y0 + C*z0 + D) / (A*xd + B*yd + C*zd)

After plugging t back into R(t), we finally have the point at which
the ray intersects with the plane.
R(t) = (x0 + xd*t, y0 + yd*t, z0 + zd*t).  Be sure to check if t is
not negative.  If t is negative, then the line that coincides with the
ray intersects with the plane but not the ray itself.

Now, all we have to do is a couple of checks to make sure that the
point is inside the rectangle.

Since the shape in question is a rectangle, I'll streamline the method
used for general convex polygons.

Let V3 = P4 - P3 be the vector opposite from V1.  Let V4 be the vector
from P1 to the point of intersection, and let V5 be the vector from P3
to the point of intersection.  Normalize vectors V1, V3, V4 and V5. 
Then find the dot products V1 dot V4 and V3 dot V5. If both are
non-negative, then the point is in the rectangle.  This works because
we use the fact that if the angle between V1 and V4 and the angle
between V3 and V5 are between 0 and 90 inclusive, the point is in the
rectangle.

Hope that helps.

Additional links:

Point-Plane Distance
( http://mathworld.wolfram.com/Point-PlaneDistance.html )

Ray-Polygon Intersection
( http://www.siggraph.org/education/materials/HyperGraph/raytrace/raypolygon_intersection.htm
)

Ray-Object Intersection
( http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter0.htm
)
toasty-ga rated this answer:5 out of 5 stars
Answer was direct and on the subject I was looking for, with helpful
reference links. Very pleased with the response!

Comments  
Subject: Re: 3D ray intersection with a rectangle
From: jackburton-ga on 31 May 2002 12:12 PDT
 
My immediate thought is to describe each side of the rectangle by a
vector equation.
For example, for side AB with position vectors  a and b, its equation
has the form
	r  =  a + l (b - a)				(1)
l is a constant.
If the ray has the equation 
	r  =  t s							(2)
where s is the direction vector, then if the ray intersects the side,
the coordinates of the intersection point must satisfy both (1) and
(2), ie
	a + l (b - a)  =  t s  				(3)

You would have to repeat for the other 3 sides of the rectangle.
There may be other ways of tackling this.

hope this helps :)
Subject: Re: 3D ray intersection with a rectangle
From: smileywiley-ga on 31 May 2002 14:54 PDT
 
In response to jackburton-ga's comment:

The l in r  =  a + l (b - a) is a variable between 0 and 1, not a
constant.

The equation for the ray should be r = v + t s, where t >= 0, v =
origin vector and s is the direction vector.

The algorithm described would find the intersection of the ray with
the segments that make up the rectangle and not the rectangle itself. 
(it would work if we were talking in 2d space though)
Subject: Re: 3D ray intersection with a rectangle
From: toasty-ga on 31 May 2002 17:30 PDT
 
Thanks for your responses. I've found them very helpful, I'm still
trying to digest all the information, and have been reviewing my
vector math in the meanwhile to regrasp all the terminology, it's been
some years. But your answer was quite informational and very helpful,
and thank you for providing the reference links.

I've rated the answer 5 stars with great pleasure and would like to
say thanks again. Also if it wouldn't be too bothersome, I would
really appreciate it if you could provide an example or two solving
the problem with some arbitrary rectangle and ray just to help me
visualize the steps and check my work.

Many thanks.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy