Jump to content

  • Log In with Google      Sign In   
  • Create Account


3D line intersection


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
5 replies to this topic

#1 Assaf Muller   Members   -  Reputation: 124

Like
0Likes
Like

Posted 24 June 2006 - 08:55 AM

I got 2 lines, represented each by 2 3D vertexes. So for example the 1st line is represented as [0, 0, 0] -> [1, 1, 1] 2nd line: [1, 0, 1] -> [0, 1, 0] their intersection point should be [0.5, 0.5, 0.5] How would you accomplish this? I've thought of a more programmatical approach: and that is to fill in 10 or 100 vertexes in each line, then finding the minimal distance between a point on the first line, and a point on the 2nd line. If the minimal distance is 0 or close enough to 0 then the lines intersect. However this seems rather crude and inefficient. I thought of using y = ax + bz + c (line equation) but I'm having a little trouble... I got y, x, z. a = (y2 - y1) / (x2 - x1) b = (y2 - y1) / (z2 - z1) c = can be found by deducting the line's equations with two points on the same line. But then if I compare the two line's equations I got 2 variables with one equation (x and z intersection point is unkown, only 1 equation). So I'm stuck... Are my ideas and equations correct? Anyone got a better, fresh idea?

Sponsor:

#2 tendifo   Members   -  Reputation: 146

Like
0Likes
Like

Posted 24 June 2006 - 09:45 AM

You could set the two lines up in this format:

(x, y, z) = (x0, y0, z0) + t(u, v, w)

and then set the two equations equal to eachother and solve for t. Then replug t into one of the equations for the point.

But the problem here is that 3d lines sometimes do not intersect. For example:

(0, 0, 0) -> (1, 0, 0)
(0, 1, -1) -> (0, 1, 1)

Those completely miss eachother.

#3 Assaf Muller   Members   -  Reputation: 124

Like
0Likes
Like

Posted 24 June 2006 - 09:58 AM

Gotcha.

[u, v, w] are the components for a unit vector correct?

and the ranges for t are -infinite to +infinite?

#4 tendifo   Members   -  Reputation: 146

Like
0Likes
Like

Posted 24 June 2006 - 01:55 PM

Not the unit vector exactly. What I typically do, and I think this is the norm, is to have it go from t=0 to t=1, where t=0 is the first point and t=1 is the second point.

But the unit vector would work for what you're doing I guess.

#5 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 24 June 2006 - 03:40 PM

As tendifo alluded to, two lines in 3D will rarely intersect exactly. The common solution to this problem is instead to find the minimum distance between the lines (or rays or segments) and test it against some threshold. This is basically what you were suggesting with your multiple sample points approach, but fortunately it doesn't require that much work. There's a very simple algorithm for finding the minimum distance between two lines (it's a little more complex for rays and segments). Google for 'closest point of approach lines', 'closest point 3D lines', or similar phrases, and you should find a good article on the subject.

#6 bleb   Members   -  Reputation: 192

Like
0Likes
Like

Posted 26 June 2006 - 01:12 AM

Like this one!

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm




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