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 5676 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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!