Sign in to follow this  
Followers 0
PfhorSlayer

Line segment plane intersection code issues...

9 posts in this topic

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

Share this post


Link to post
Share on other sites
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 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.
-1

Share this post


Link to post
Share on other sites
I didn't look at the whole function, but my first thought would be to replace:

Vector dir = p1 - p2;

With:

Vector dir = p2 - p1;

And see if that fixes it.

PfhorSlayer...that wouldn't be a Marathon reference, would it? If so, cool :-)
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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;
0

Share this post


Link to post
Share on other sites
I think the error lies in the line:
float dist = -((p.Normal() * p1) + p.Distance()) / denom;
It looks like you have the negative sign in the wrong place. I suggest trying:
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 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.


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 thatLX = tv. Since [LX] = tv then (X - L) = tv -> X = L + tv, our parametric equation for our line (since X, L and v are actually made up of 3 components i.e Xx, Xy Xz)

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+tv -> (L + tv) • n => L•n + tv n = d  -> tv•n = d - L • n
t = d - L•n  Note also that since d =  n•Q that 
vn

t =  n•Q - L•n  or n•(Q - L)
vn vn


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];
1

Share this post


Link to post
Share on other sites
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 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
1

Share this post


Link to post
Share on other sites
[quote name='Daerax' timestamp='1111380068' post='2965722']
float t = d - (p1 * p.Normal())/ denom;
Vector PoI = p1 + (t * v);
[/quote]

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

Anyways, I'm sorry to revive this old thread, @[url="../../user/34500-daerax/"]Daerax[/url] 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.
0

Share this post


Link to post
Share on other sites
[quote name='altare' timestamp='1328462145' post='4909861']
[quote name='Daerax' timestamp='1111380068' post='2965722']
float t = d - (p1 * p.Normal())/ denom;
Vector PoI = p1 + (t * v);
[/quote]

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.
[/quote]

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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0