Vector p1 = this->points[y]; Vector p2 = this->points[x]; Vector dir = p1 - p2; dir.Normalize(); float denom = p.Normal() * dir; if (denom == 0) continue; float dist = -((p.Normal() * p1) + p.Distance()) / denom; Vector v = p1 + (dist * dir);Anyone see something wrong with my code?

**1**

# Line segment plane intersection code issues...

Started by PfhorSlayer, Mar 20 2005 10:51 AM

9 replies to this topic

###
#1
Members - Reputation: **316**

Posted 20 March 2005 - 10:51 AM

I'm trying to find the intersection point of a line segment and a plane, but I'm having trouble.
The two points that make up my line segment are:
p1 = (0, -64, -64)
p2 = (0, -64, 0)
The plane is n(0, 0, 1) d = -24
The split point SHOULD be (0, -64, -24), but for some reason, my code is giving me (0, -64, 24)!

###
#2
Crossbones+ - Reputation: **1709**

Posted 20 March 2005 - 11:23 AM

I don't understand this line:

Or any of the other lines where you "multiply" two vectors and get a scalar. Dot product I presume?

At any rate, what I would do is find the absolute distance of

float denom = p.Normal() * dir;

Or any of the other lines where you "multiply" two vectors and get a scalar. Dot product I presume?

At any rate, what I would do is find the absolute distance of

`p1`and`p2`from the plane, call them`p1dist`and`p2dist`. Then you have the normalized direction vector from`p1`to`p2`, call it`dir`. Then, the intersection point is`dir * (p1dist / (p1dist + p2dist))`which works because of triangle congruency. This is what I think you're doing, however maybe it isn't as clear because of how you do it. Maybe the problem is because you have`p1 - p2`as your direction instead of`p2 - p1`but I haven't examined it that closely enough.###
#4
Members - Reputation: **316**

Posted 20 March 2005 - 12:01 PM

Doing dir = p2 - p1 instead of the other way around has zero effect, and the * operator is overloaded for two Vectors to be the dot product.

And yes, it is a Marathon reference. :)

I'm going to try Zipster's suggestion now, and see if that doesn't work out.

And yes, it is a Marathon reference. :)

I'm going to try Zipster's suggestion now, and see if that doesn't work out.

###
#5
Members - Reputation: **2075**

Posted 20 March 2005 - 01:28 PM

You're right, my mistake - negating the direction vector shouldn't affect the outcome.

Here's another thought. If your plane distance is the distance of the plane along the plane normal, than maybe this line:

float dist = -((p.Normal() * p1) + p.Distance()) / denom;

Should be:

float dist = -((p.Normal() * p1) - p.Distance()) / denom;

Here's another thought. If your plane distance is the distance of the plane along the plane normal, than maybe this line:

float dist = -((p.Normal() * p1) + p.Distance()) / denom;

Should be:

float dist = -((p.Normal() * p1) - p.Distance()) / denom;

###
#6
Members - Reputation: **1207**

Posted 20 March 2005 - 10:41 PM

I think the error lies in the line:

You offer me a perfect excuse to post my original reply, I went and wrote a lengthy reply without really looking at the code, when I finally did I smacked myself with a shoe and was like, arghh all that typing and he just had to move the sign!! Anyway Im sure it'll be useful to someone, there is not many satisfactory explanations on Intersection of stuffs.

Your notation is a bit confusing to me as it clashes a bit with what I am used to. You have n(0,0,1)d = -24 and I thought you were defining the plane such that n was the normal and d was a scalar value..It took a while for me to recognize that d was a point which created a vector with the point through which the plane passed through..

Anyway I think your method is a bit acrobatic and the need for normals is unnecessary if one utilizes the definition of a line in 3 space. In planar geometry a line can be defined with a member point and its slope, similarly so is a plane defined in 3 space. The plane can be define by an inclination and point on the plane. If we ascribe a vector n orthogonal to our plane the task of defining our inclination it then follows that for any point P which lies in our plane going through some point Q, if we create a vector

If we have a line in 3-Space going through some point L then any any point X on the line creates a vector

Since the we know the line intersects with our plane then we know that some point X on our line is also part of our plane. You have your plane defined as n•d = c ( a variant of ax + by + cz = d), so we need to rewrite our original plane equation to reflect this form.

We have from earlier that

That equation is for the general case when Q is known and no constant is given. Also note that the denominator of the equation for t will be equal to zero when the line is parrallel to the plane. Using your code as a template the PoI can be found thus:

Oh, I still dont know why you are normalizing and what this line means:

Vector p1 = this->points[y];

Vector p2 = this->points[x];

float dist =It looks like you have the negative sign in the wrong place. I suggest trying:-((p.Normal() * p1) + p.Distance()) / denom;

float dist = (-(p.Normal() * p1) + p.Distance()) / denom;

Quote:

Original post by Zipster

I don't understand this line:float denom = p.Normal() * dir;

Or any of the other lines where you "multiply" two vectors and get a scalar. Dot product I presume?

At any rate, what I would do is find the absolute distance ofp1andp2from the plane, call themp1distandp2dist. Then you have the normalized direction vector fromp1top2, call itdir. Then, the intersection point isdir * (p1dist / (p1dist + p2dist))which works because of triangle congruency. This is what I think you're doing, however maybe it isn't as clear because of how you do it. Maybe the problem is because you havep1 - p2as your direction instead ofp2 - p1but I haven't examined it that closely enough.

You offer me a perfect excuse to post my original reply, I went and wrote a lengthy reply without really looking at the code, when I finally did I smacked myself with a shoe and was like, arghh all that typing and he just had to move the sign!! Anyway Im sure it'll be useful to someone, there is not many satisfactory explanations on Intersection of stuffs.

*Other post begins Here:*Your notation is a bit confusing to me as it clashes a bit with what I am used to. You have n(0,0,1)d = -24 and I thought you were defining the plane such that n was the normal and d was a scalar value..It took a while for me to recognize that d was a point which created a vector with the point through which the plane passed through..

Anyway I think your method is a bit acrobatic and the need for normals is unnecessary if one utilizes the definition of a line in 3 space. In planar geometry a line can be defined with a member point and its slope, similarly so is a plane defined in 3 space. The plane can be define by an inclination and point on the plane. If we ascribe a vector n orthogonal to our plane the task of defining our inclination it then follows that for any point P which lies in our plane going through some point Q, if we create a vector

**[QP]**then the dot product with n will be zero since n is orthogonal to our plane. Thus a plane is defined as n•(**P-Q**) = 0.If we have a line in 3-Space going through some point L then any any point X on the line creates a vector

**[LX]**parallel to some vector**v**which directs the line. Since**[LX] || v**it follows that there exists a scalar t describing our line progression such that**LX**= t**v**. Since**[LX]**= t**v**then (X - L) = tv -> X = L + t**v**, our parametric equation for our line (since X, L and v are actually made up of 3 components i.e X_{x}, X_{y}X_{z})Since the we know the line intersects with our plane then we know that some point X on our line is also part of our plane. You have your plane defined as n•d = c ( a variant of ax + by + cz = d), so we need to rewrite our original plane equation to reflect this form.

We have from earlier that

**n**•(**P-Q**) = 0 thus**n**•P -**n**•Q = 0 ->**n**•P =**n**•Q,**n**•Q = d. =>**n**•P = d, Since X from our line is also a part of the plane then X = P so:**n**•X = d, X= L+t**v**-> (L + t**v**) •**n**=> L•**n**+ t**v**•**n**= d -> t**v**•n = d - L •**n**t =d - L•nNote also that since d =n•Qthat

v•n

t =orn•Q - L•nn•(Q - L)

v•n v•n

That equation is for the general case when Q is known and no constant is given. Also note that the denominator of the equation for t will be equal to zero when the line is parrallel to the plane. Using your code as a template the PoI can be found thus:

Vector p1 (0, -64, -64);

Vector p2 (0, -64, 0);

Vector v = p2 - p1;

float denom = p.Normal() * v;

if (denom == 0)

continue; // n _|_ p

float t = d - (p1 * p.Normal())/ denom;

Vector PoI = p1 + (t * v);

*End It! Damn it, I want my 15~20mins back!![sad]*Oh, I still dont know why you are normalizing and what this line means:

Vector p1 = this->points[y];

Vector p2 = this->points[x];

###
#7
Members - Reputation: **1150**

Posted 21 March 2005 - 01:08 AM

haven't readed long post above mine, but note that result you get is same as you should if your d = 24 (not -24) and it looks rather like you have incorrect sign for d.

Other than that, your code looks *quite* unreadable/obfuscated.

Let we have plane normal = N , plane distance = d , and line segment A,B

Line segment have equation A+t*(B-A)

So, we need to find t that

(A+t*(B-A)).N=d

that is,

A.N+t*(B-A).N=d

t=(d-A.N)/((B-A).N)

That is, code becomes just

where * stands for dot product. (actually it is valid as there's aint no other meaningful overload for vector*vector, and definately overloading "%" or "&" to do that is lot wors

Other than that, your code looks *quite* unreadable/obfuscated.

Let we have plane normal = N , plane distance = d , and line segment A,B

Line segment have equation A+t*(B-A)

So, we need to find t that

(A+t*(B-A)).N=d

that is,

A.N+t*(B-A).N=d

t=(d-A.N)/((B-A).N)

That is, code becomes just

**two lines**:

// of course you can better test your denom for 0, but anyway, that quite well gives you basic idea:

double t=(plane_distance-P1*plane_Normal)/((P2-P1)*plane_Normal);

intersection_point=t*(P2-P1);

where * stands for dot product. (actually it is valid as there's aint no other meaningful overload for vector*vector, and definately overloading "%" or "&" to do that is lot wors

###
#9
Members - Reputation: **100**

Posted 05 February 2012 - 11:15 AM

float t = d - (p1 * p.Normal())/ denom;

Vector PoI = p1 + (t * v);

For a start, thanks all for the precious information this thread contains.

Anyways, I'm sorry to revive this old thread, @Daerax but I'm here hoping that somebody can help me solve this same problem with a slightly different approach: my plane is certainly a 'standard' plane, but it's actually defined by

position

and

normal

In simple words, the formulas and ideas proposed here give me results that I can't understand how to adapt to my solution, since I'm not competent enough.

My problem is basically that I don't have a 'd' value, or rather, I can't understand how to calculate 'd' from my plane 3d vector position and 3d vector normal.

###
#10
Crossbones+ - Reputation: **2140**

Posted 05 February 2012 - 12:30 PM

float t = d - (p1 * p.Normal())/ denom;

Vector PoI = p1 + (t * v);

For a start, thanks all for the precious information this thread contains.

Anyways, I'm sorry to revive this old thread, @Daerax but I'm here hoping that somebody can help me solve this same problem with a slightly different approach: my plane is certainly a 'standard' plane, but it's actually defined by

position

and

normal

In simple words, the formulas and ideas proposed here give me results that I can't understand how to adapt to my solution, since I'm not competent enough.

My problem is basically that I don't have a 'd' value, or rather, I can't understand how to calculate 'd' from my plane 3d vector position and 3d vector normal.

In your case you can get 'd' by taking the dot product of the normal of the plane and any point on the plane.

-Josh

--www.physicaluncertainty.com

--linkedin

--irc.freenode.net#gdnet