You''ve given me the perfect opportunity for self promotion! You should definitely see my chapter in "Game Programming Gems 2," which is titled: "Fast, Robust Intersection of 3D Line Segments." The 100% complete answer to your problem is there, along with all the math worked out from start to end + working code and a demo program! Well worth the $50+ just for that chapter alone! (Well, maybe not, but for $50+ you get maybe 70 chapters of good stuff.)

By the way, what are you needing this for?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

line A (0, 0) - (5, 5)
line B (5, 0) - (0, 5)

m = y2 - y1 / x2 - x1

slope calculated A 1
slope calculated B -1

visually view the pairs, or graph them to find the y
intercept.

y intercept for A 0
y intercept for B 5

y = mx + b

equation A y = 1x + 0
equation B y = -1x + 5

x + y = b

standard form A -1x + y = 0
standard form B 1x + y = 5

y = b - x

solve for y: 0x + 2y = 5
solve for y: 2y = 5
solve for y: y = 5/2

x = b - y

solve for x: 1x + 5/2 = 5
solve for x: 2x + 5 = 10
solve for x: 2x = 5
solve for x: x = 5/2

intersection at: (5/2, 5/2)

if you graph this problem on paper you can verify that
the solution is indeed correct. all you have to do is
isolate this into a function taking four sets of points
that define two line segments, and return a struct of
two points. good luck, and i hope this helps.

Yes, the naive solutions often cause the troubles you mention. And usually people don''t treat line *segments*---only infinite lines. So, while I can''t give the solution here---my answer is now copyrighted through Charles River---the chapter does cover the most general problem in detail, including how to deal with finite-length segments.

I wonder if libraries will be stocking the second Gems book?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Just because they are in the same plane doesn't mean they intersect since they might be parallel.

This most likely is not how you should calculate it, but it seems the easiest way to explain it.

      pa.1 = (a1.x, a1.y, a1.z)pa.2 = (a2.x, a2.y, a2.z)va   = pa.2 - pa.1pb.1 = (b1.x, b1.y, b1.z)pb.2 = (b2.x, b2.y, b2.z)vb   = pb.2 - pb.1ab   = pa.1 - pb.1cp   = va x vbvaab = va x abvbab = vb x abif (cp.x != 0)   s    = vbab.x / cp.x   t    = vaab.x / cp.xelse if (cp.y != 0)   s    = vbab.y / cp.y   t    = vaab.y / cp.yelse if (cp.z !=0)   s    = vbab.z / cp.z   t    = vaab.z / cp.zelse lines are parallel   s = -1   t = -1if (((s >= 0) && (s <= 1)) && ((t >= 0) && (t <= 1)))   intersection = pa.1 + va*s      

The reason you most likely don't want to calculate it that way is that the cross products are excessive since most often you use just one component of each. Since you have to test if they are in the same plane, which this assumes they are, you should have already calculated cp and either vaab or vbab since cp x vaab and cp x vbab will be the zero vector if they are in the same plane. Since you should already have cp you can skip the cross product since you can already tell which component of the other vector you need.

Edited by - LilBudyWizer on September 5, 2001 12:27:02 AM

Dang typos and I guess it would make more sense to check if they are in the same plane with the scalar triple product ab*(va x vb) rather than (va x ab) x (va x vb) or (vb x ab) x (va x vb). So anyway you should already have va, vb, ab and cp and you only need one component of vaab and vbab. So that should only be six multiplies, two divisions and two subtractions to calculate s and t plus three multiplies and three additions to calculate the point of intersection in addition to what you should or at least could already have.

Edited by - LilBudyWizer on September 6, 2001 3:50:44 PM