Intersection of a line w/ a plane

#1 I have no idea what you are talking about but since I want to help out where I can I made you this diagram of the problem/needs. (Hopefully)


Is this the kinda thing you are looking to make/do?

// Clocks out

www.flashthunder.com

#2 Here is my shot, with all the real math left for someone else to do... :-)

Basically, what you want to do is find the 2 planes that are the distance you are looking for and are also parallel to your plane. Then all you need to do is find the line/plane intersection points.

Does that make sense?

Another way to do it would be to align the plane to, say, that x-z axis. Then find the equation for the line aligned on that axis and plug in the correct y value. That should give you the coordinate that is the correct distance away.

You also might be able to plug the distance formula into the line equation. 2D example:

Line eq: y = 5x + 2

"Plane" is the x-axis. We want the line point where it is 10 units above and below the axis.

distance: 10^2 = x^2 + y^2

100 = x^2 + y^2
x = sqrt(100 - y^2)

plug into line eq:
y = 5(sqrt(100 - y^2)) + 2

and lost of math left here that I don't really want to do this early in the morning... :-)

Anyway, you get the idea?

Josh

#3 Josh has the right idea

distance = sqrt[(x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2]

That's from the point of intersection.

Alc

#4 LINE-PLANE intersection is a very basic algo in Computer graphic. almost every single book about CG will have this.

The idea is very simple: given a plane (which decidec by 3 vectors in space). you can define a "plane equation" for this plane:

Ax+By+Cz+D=0
(x, y, z is any vector said to be on this plane. A,B,C,D are the constants describiing the spatial propertis of the plane. (A. B. C) is a vector paralla to the plane's normal)

given a line: you can define a line by its origin point and its direction vector:

line(x,y,z)=V_origin+V_dir*d
(line(x,y,z) is any vector on said to be on the line. V_origin is the origin point of the line. V_dir is the line's direction, d is the distance between V_origin and Line(x,y,z)

Put these 2 equations together. a intersection point between a line and a plane (V_int) should fulfill both equations:

V_facenormal dot (V_origin+d*v_dir)+D=0; (v_facenormal is (A, B, C)here, dot means dot_product of 2 vectors)

which lead us to d=-(D+V_facenormal dot V_origin)/V_facenormal dot v_dir)

once we got the d (distance betwee intersect point and line origine point), we can easily find out the actual intersect point (V_int) by putting the 'd' back to the line equation.

sample code:

//a helper function to do a line/plane intersetion test
//return -1.0f if fail
//return the actural collide distance if sucess.
float line_plane_test(float A, float B, float C, float D, D3DVECTOR* vo, D3DVECTOR* v_dir)
{
	float collision_distance;

	//plane is described as A*x+B*y+C*z+D=0
	//where (x, y, z) is any position on the given plane.

	//if the DOT product of v_dir and plane normal
        //(A, B, C) larger than zero, 
	//it means the ray and the plane normal are 
        //pointing to the similar direction 
         //(polygon is the backfacing from the ray point of view)
	//thus return fail;
	//if the DOT product is equal to zero, means the
        //v_dir is paralla with the plane, also return fail;

	float dir_dot_normal=v_dir->x*A+v_dir->y*B+v_dir->z*C;
	if (dir_dot_normal>=0.0f)
		return (-1.0f);

	//otherwise, the plane and the ray is gonna has one and 
        //only one intersert point, its distance s is said to be:
	//s=-(D+normal_dot_v_origin)/dir_dot_normal

	collision_distance=-(D+vo->x*A+vo->y*B+vo->z*C)/dir_dot_normal;
	return collision_distance;
}

#5 Ack. Nice range of answers there... :)

Clocks: Yes, more or less.

Josh: Erm, huh?

Greg: Ya, got that...

fred: Gah. See, my math totally sucks, 'cause you lost me in the first formula, other than a general understanding.

========

Hmmm. Mebbe I should have been more explicit.

There are two planes parallel to each other (plane A, plane B), x meters apart. I have three points on plane A (J, K, and L), and another point (M) somewhere on the other side of plane B (so that plane B is between point M and the plane A).

If you imagine drawing a line from point J in plane A, through plane B, to M... what are the coords of the point of intersection of plane B and line JM?

Mebbe I'll just have to go pay some math whiz to break it down and explain along the way - I'm not up to this, I guess. I know that programming is math intensive, but I've never had this much trouble before... of course I never did much 3D math either.

This problem and fred's answer are both right over my head when I try to break it down into an algorithm for a program. I apologize for my simplemindedness...

#6 Well, to solve a problem, you have to define the problem 1st. where you want to calc line(ray) intersect with plane, you need to define the plane and the line mathmatically. ie define the plane_B and line J_M

The 1st equation is called "Plane equation". A common mathmatical representation of a plane.
given 3 points (x1, y1, z1) (x2, y2, z2) (x3, y3, z3)on a plane, you can easily find out A, B, C, D of that plane

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);

obviousely, vector (A,B,C) is pointing to the same direction as the face normal.

From Ax+By+Cz+D=0; which will lead to (A, B,C)dot(x,y,z)+D=0;

since (x, y, z) also need to fit into the line equation (cuz its on both line and the plane). we replace (x,y, z) with the line equation. therefore we have
(A, B, C) dot (v_origin+v_dir*collision_distance)+D=0;

resolve this equation, we will have collision_distance.

#7 OK. Lemme see if I can wrap my head around this... but I think you may still be misunderstanding what I am after (Clocks' picture, on reflection, doesn't represent my problem as well as I thought).

I don't have any points on the plane I want to find the intersection with. I have 3 points on a parallel plane, say 1 meter away. Are you saying I can use that math to find three points on the plane for which I have no points, then find the intersection with the plane that is newly defined?

Mebbe I should make my own diagram...

#8 Here:


There are two planes: V and W. These planes are parallel and are assumed to extend infinitely (as they are planes, not faces), so don't read too much into the triangular representations here.

These planes do not have an 'up' or 'down' defined for them.

The two planes are a known distance apart (J units).

For plane V, I have three points on the plane: A, B, and C. I have no points on Plane W at all.

I do, however, have point M, which is on the other side of Plane W. Line (segment?) CM must pass through plane W at some point X. What are the coordinates of point X?

Is this the problem your solution is designed to solve?

BTW, thank you for your patience with my thick head...

#9 I think the best thing to do would be to state the things that are given and what you are looking for.

IE. you have two parallel planes and have a fomula for one of them. The other you know there is a point on the plane (A). Between these two planes there is a line intersecting each of them. The line intersects the first plane at point B and the second plane at point A. Find the point A.

Now in the above there is information missing to solve the problem. You have to know something else about the line and the distance from one plane to the other or something else on how plane 1 relates to plane 2.

Alc

#10

Quote:Now in the above there is information missing to solve the problem. You have to know something else about the line and the distance from one plane to the other or something else on how plane 1 relates to plane 2.

Er... I'm pretty sure I described those conditions in both my second and third trys at a description.

The plane for which I do not have points (plane W) is parallel to and a known distance (distance J) from the plane for which I do have points (plane V). The line that intersects has two defining points (C and M).

Isn't that enough, since I explicitly define plane V and line CM, and implicitly define plane W?

Sorry if my notation and terminology is not quite by the geometry standard - it's been about 17 years since I did this kind of math and I'm a bit fuzzy about how to even define the problem.

#11 It is a universial solution for testing line(ray)-plane intersection.

If you dont have enough data to define the plane_w, you will not be able to test the intersection point.

you can however, find 3 points (v1', v2' v3') on plane_w if you have 3 points (v1, v2, v3)on plane_v (which parallel with plane-w) already.

To do so, you have to find out the plane equation for plane_v. from there you got A,B,C, D for plane_v. (A,B,C) is indeed a vector parallel to the plane_v's face normal. Normalize(A,B,C) to obtain a unit vector V_plane_v_normal;

once you get plane_v's normalized vector. you will also need to know which side is plane_w at. depend on which side is the plane_w at, you can find out: v1'=v1+V_plane_v_normal*j or V1'=v1-V_plane_v_normal*j;
similar calc to get V2' and V3'

once you got V1', v2' and V3'. you can now find out the A,B,C,D for the plane_w.

so you have plane equation for Plane_w, you have 2 end points for your line, which you can easily convert them to line equation. problem solved!

ah. there is another easier way. once you got the normalized face_normal of plane_v, you can get the cos(angle) from the dot product of J_M and v_plane_v_normal (angle is the angle between 2 vectors)

cos(angle)=(J_M dot v_plane_v_normal)/(Magnitude(J_M)*Magnitude(v_plane_v_normal))

Magnitude(v_plane_v_normal=1.0f (cuz its a normalized vector)

Magnitude(x_c)=j/cos(angle)
==>>
Magnitude(x_c)=j*Magnitude(J_M)/(J_M dot v_plane_v_normal)

once you got magnitude(x_c) (the real distance between x and c) and you alread have line equation for line(J_M) so you can get x's coord by putting them together!

#12 Yeah sorry I must have been in the process of typing while you were because your diagram hadn't been posted yet :)

Alc

#13 Thanks. I'm still having trouble getting it all straight in my head, but I'm making progress as I go over that repeatedly. I appreciate the help.

#14 Ok, we know the formula for the first plane:
Ax + By + Cz = D
Since you are using the first plane as a frame of reference D = 0

Now you have three points along the first plane so you have 3 equations and 3 unknowns(A, B, C). Therefore you can solve for A, B, and C by substitution.

The normal (a vector 90 degrees from any vector along the plane) to this plane is (A, B, C). The magnitude of this vector can be expressed as the distance between the two parallel planes. That gives us our D for the formula for the second plane. Now since the normal for one vector can also be the normal to another vector which is parallel we can use the same A, B, and C values in the second equation. So the formula for the second plane will be:
Ax + By + Cz = distance between planes

So now you have a formula for the second plane.

From there use the formula for the line to find the point of intersection on the second plane.

You may want to get someone to confirm all of this, it's been a while since I've done this stuff too :)

Alc

#15 the vectors(A,B,C) on Plane_v and plane_w are not *necessary* the same, while they pointing to the same direction, but they are quite likely have different magnitude.

#16 I'm going to jump in here. Let's see if this helps. Using the information from the first post.

Three points that define the plane (p1, p2, and p3) to be intersected with.
Two points on the line l1 and l2.

First find out if the line is parallel to the plane, like you said Tim. To do this we need to find the vector, which gives the direction and orientation of the line, if this orientation is the same orientation as at least one vector within the plane then the plane and the line is parallel and we're done.

To find the vector of the line is simple just subtract one point on the line from any other point on the line (fortunately we have this info given), let's call our new vector that describes the line L (note: I'll describe points as lower-case letters, and vectors are described as upper-case letters),

L = l2 - l1 // i.e.: L.x = l2.x - l1.x; L.y = l2.y - l1.y; L.z = l2.z - l1.z

we're also going to need a couple of lines (that are non-paralell) within the plane to compare against, get them in the same way,

P1 = p2 - p1
P2 = p3 - p2

This is a somewhat tricky part. We need to find if the line vector (L1) is parallel to the plane. We have two handy tools to find relationships like this between vectors, one is called the dot product and another is called the cross product. The dot product of two vectors can tell us if the vectors are at right angles to each other (perpendicular, or otherwise called orthogonal). The cross product can give us a vector that is perpendicular to the two vectors. Using these two tools we can find if the line vector is parallel to the plane.

What we're going to do is find a line perpendicular to a vector in the plane and the vector of the line. Then we're going to see if this new line is perpendicular to another line in the plane. If this new line is perpendicular to this other line in the plane then the only way this could happen is if the original line is indeed perpendicular to the plane. Here's the steps (we're calling this new vector G), in pseudo-Torque Script

G = vectorCross(L, P1);		
/* i.e: G.x = L.y * P1.z - L.z * P1.y; 
        G.y = L.z * P1.x - L.x * P1.z; 
        G.z = L.x * P1.y - L.y * P1.x */
	det = vectorDot(G, P2);		
/* i.e: det = G.x * P2.x + G.y * P2.y + G.z * P2.z
	if (  det == 0 )     /* in practice this should really be something like:  
if ( (det >= -0.0001) && (det <= 0.0001) )  because 
of precision issues */
	{
		/* the line is parallel, 
we're done, no intersection */
		return 0;
	}

but if the line is not parallel then we know there is an intersection with the plane, the only question that remains is where. This is the really tricky part. I'm not going to explain this here. This is taken from a well known and fast triangle-ray intersection algorithm (Moller-Trumbore). See here for their explanation of how it works and the full C code behind it.

// get distance vector from l1 to p1, called T
	T = l1 - p1;
	
	/* get unscaled u, (u,v) is the point on the 
plane in respect to p1. so in (u,v) coordinates p1 is 
(0,0) -- I may be wrong on this part I'm not too sure if 
this is in respect to p1, but the math looks like it is 
so, you'd have to play around with it to be sure. it 
might be in respect to another of the three points in 
the plane.)  */
	u = vectorDot(T, G);

	// get unscaled v
	Q = vectorCross(T, P1);
	v = vectorDot(L,Q);

	// scale u and v
	scale = 1 / det;
	u *= scale;
	v *= scale;

Also note if you are doing this in Torque script you can use the ContainerRayCast function to do all of this, but this will give you the hit point in 3D space rather than in the (u, v) in the plane. Which may be what you're looking for.

Hope this helps.

Mike

#17 AAAAaaahhhh I hate collision detection!! AAAHHHHHHHHH