Jump to content

  • Log In with Google      Sign In   
  • Create Account


Line segment plane intersection code issues...


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 PfhorSlayer   Members   -  Reputation: 316

Like
1Likes
Like

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

Sponsor:

#2 Zipster   Crossbones+   -  Reputation: 549

Like
-1Likes
Like

Posted 20 March 2005 - 11:23 AM

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.

#3 scgames   Members   -  Reputation: 1969

Like
0Likes
Like

Posted 20 March 2005 - 11:36 AM

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

#4 PfhorSlayer   Members   -  Reputation: 316

Like
0Likes
Like

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.

#5 scgames   Members   -  Reputation: 1969

Like
0Likes
Like

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;

#6 Daerax   Members   -  Reputation: 1207

Like
1Likes
Like

Posted 20 March 2005 - 10:41 PM

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


#7 Dmytry   Members   -  Reputation: 1147

Like
1Likes
Like

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 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
My game The Polynomial is now available on Steam. | The Polynomial homepage | Cloud and terrain rendering |Everything i said in that post is obviously ABSOLUTE TRUTH my unhumble opinion.

#8 PfhorSlayer   Members   -  Reputation: 316

Like
0Likes
Like

Posted 21 March 2005 - 10:59 AM

Thanks for the help, all. Daerax was right, I had the negative sign in the wrong place. D'oh!

#9 altare   Members   -  Reputation: 100

Like
0Likes
Like

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 jjd   Crossbones+   -  Reputation: 2066

Like
0Likes
Like

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





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS