Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

ISOPimp

Intersect between 2 lines in 3D space

This topic is 5589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here is the problem: I have 2 lines in 3D space (represented by a pair of points) and need to find the intersect point of these two lines. They WILL intersect, i know that, I just need some c++ code that I can use to find the point of intersection. I need this to find the centroid of a triangle. With this centroid point I will be drawing a line representing the triangle''s normal. Thank you

Share this post


Link to post
Share on other sites
Advertisement
parametric equations use u must!

first Line:
p = first pt
q = second pt
second Line:
r = first pt
s = second pt

first Line parametric equation:
x = (1-t)p + tq , where t is from 0 to 1

second Line parametric equation:
y = (1-t)r + ts , where t is from 0 to 1

then:
x = y must! find t u will, only then will you feel the force!

edit i must!

...................................................



[edited by - kuladus on June 2, 2003 12:39:56 AM]

Share this post


Link to post
Share on other sites
Sorry, I think you misunderstood the question. I understand the math behind getting the intersect point, but I am confused as to how I can solve the equation in c++. Well, I dont understand all the math, for instance when I multiply a point by t is it like this: t(x, y, z) = (tx, ty, tz)?

This is what I have as of right now:

x1 = line 1 point 1 = (-1.00, 0.00, 0.00)
x2 = line 1 point 2 = ( 0.00, 0.50,-0.25);
x3 = line 2 point 1 = ( 0.00, 1.00, 0.00);
x4 = line 2 point 2 = (-0.50, 0.00,-0.25);
(these are actual points taken from my simple app)

t = t
s = 1 - t

x = s(x1.x, x1.y, x1.z) + t(x2.x, x2.y, x2.z)
y = s(x3.x, x3.y, x3.z) + t(x4.x, x4.y, x4.z)

(s(x1.x), s(x1.y), s(x1.z)) + (t(x2.x), t(x2.y), t(x2.z)) = (s(x3.x), s(x3.y), s(x3.z)) + (t(x4.x), t(x4.y), t(x4.z))

(s(x1.x) + t(x2.x), s(x1.y) + t(x2.y), s(x1.z) + t(x2.z)) = (s(x3.x) + t(x4.x), s(x3.y) + t(x4.y), s(x3.z) + t(x4.z))

((t-1), t(.5), t(-.25)) = (t(-.5), (1-t), t(-.25))


At this point my brain hurts, plus I dont know how I would adapt this to c++ code. Im gunna get some more coffee and see if that helps me...

Share this post


Link to post
Share on other sites
code for u i must hmmm?



#include <stdio.h>
#include <math.h>

typedef struct{
float x;
float y;
float z;
} Point;

typedef struct{
Point pt1;
Point pt2;
} Line;

void Intersect(Line line1, Line line2);

int main()
{
Line L1, L2;

L1.pt1.x = -1; L1.pt2.x = 0;
L1.pt1.y = 0; L1.pt2.y = 0.5;
L1.pt1.z = 0; L1.pt2.z = -0.25;

L2.pt1.x = 0; L2.pt2.x = -0.5;
L2.pt1.y = 1; L2.pt2.y = 0;
L2.pt1.z = 0; L2.pt2.z = -0.25;


Intersect(L1, L2);

return 0;
}

void Intersect(Line line1, Line line2)
{

/*
Line1Param = (1-t)*line1.pt1 + t*line2.pt2 , where t is from 0 to 1
Line2Param = (1-t)*line2.pt1 + t*line2.pt2 , where t is from 0 to 1

Therefore Line1Param.x = (1-t1)*line1.pt1.x + t1*line1.pt2.x = line1.pt1.x - t1*(line1.pt1.x - line1.pt2.x)
And also Line2Param.x = (1-t2)*line2.pt1.x + t2*line2.pt2.x = line2.pt1.x - t2*(line2.pt1.x - line2.pt2.x)

These have to equal hmm?
line1.pt1.x - t1*(line1.pt1.x - line1.pt2.x) == line2.pt1.x - t2*(line2.pt1.x - line2.pt2.x)

(1) therefore t1 = (line1.pt1.x - line2.pt1.x + t2*(line2.pt1.x - line2.pt2.x))/(line1.pt1.x - line1.pt2.x)

still following me? =)

Now...Line1Param.y = (1-t1)*line1.pt1.y + t1*line1.pt2.y = line1.pt1.y - t1*(line1.pt1.y - line1.pt2.y)
And also Line2Param.y = (1-t2)*line2.pt1.y + t2*line2.pt2.y = line2.pt1.y - t2*(line2.pt1.y - line2.pt2.y)

line1.pt1.y - t1*(line1.pt1.y - line1.pt2.y) == line2.pt1.y - t2*(line2.pt1.y - line2.pt2.y)

(2) therefore t1 = (line1.pt1.y - line2.pt1.y + t2*(line2.pt1.y - line2.pt2.y))/(line1.pt1.y - line1.pt2.y)


(1) == (2) // == (3)

(line1.pt1.x - line2.pt1.x + t2*(line2.pt1.x - line2.pt2.x))*(line1.pt1.y - line1.pt2.y) =
(line1.pt1.y - line2.pt1.y + t2*(line2.pt1.y - line2.pt2.y))*(line1.pt1.x - line1.pt2.x)


float d1y = line1.pt1.y - line2.pt1.y; //diff between y @ pt1
float d1x = line1.pt1.x - line2.pt1.x; //diff between x @ pt1

float s2y = line2.pt1.y - line2.pt2.y;
float s1y = line1.pt1.y - line1.pt2.y;
float s2x = line2.pt1.x - line2.pt2.x;
float s1x = line1.pt1.x - line1.pt2.x;


(d1x + t2*(s2x))*s1y = (d1y + t2*(s2y))*s1x

d1x*s1y + t2*s2x*s1y = d1y*s1x + t2*s2y*s1x

t2*(s2x*s1y-s2y*s1x) = d1y*s1x - d1x*s1y;

t2 = (d1y*s1x - d1x*s1y)/(s2x*s1y-s2y*s1x);

*/


float d1y = line1.pt1.y - line2.pt1.y; //diff between y @ pt1

float d1x = line1.pt1.x - line2.pt1.x; //diff between x @ pt1


float s2y = line2.pt1.y - line2.pt2.y;
float s1y = line1.pt1.y - line1.pt2.y;
float s2x = line2.pt1.x - line2.pt2.x;
float s1x = line1.pt1.x - line1.pt2.x;

float t2 = (d1y*s1x - d1x*s1y)/(s2x*s1y-s2y*s1x); printf("T2: %f\n", t2);
float t1 = (-d1y*s2x - -d1x*s2y)/(s1x*s2y-s1y*s2x); printf("T1: %f\n", t1);

Point intersectPt;

if ( (fabs(((1-t1)*line1.pt1.x + t1*line1.pt2.x)-((1-t2)*line2.pt1.x + t2*line2.pt2.x))<0.1)&&
(fabs(((1-t1)*line1.pt1.y + t1*line1.pt2.y)-((1-t2)*line2.pt1.y + t2*line2.pt2.y))<0.1)&&
(fabs(((1-t1)*line1.pt1.z + t1*line1.pt2.z)-((1-t2)*line2.pt1.z + t2*line2.pt2.z))<0.1))
{
intersectPt.x = (1-t1)*line1.pt1.x + t1*line1.pt2.x;
intersectPt.y = (1-t1)*line1.pt1.y + t1*line1.pt2.y;
intersectPt.z = (1-t1)*line1.pt1.z + t1*line1.pt2.z;

printf("Lines intersect at (%f, %f, %f)\n", intersectPt.x, intersectPt.y, intersectPt.z);
}
else printf("No intersection.\n");

}



note: haven''t tested it fully yet, but it should work for most/all cases

...................................................

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!