Archived

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

Intersect between 2 lines in 3D space

This topic is 5307 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
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