Author Topic: Problem with 3D Intersecting Lines  (Read 19968 times)

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Problem with 3D Intersecting Lines
« on: August 05, 2012, 01:14:12 PM »
Hello,

I need to calculate the intersection point of two 3D lines.
I know that they intersect, as unlikely as this is with lines in 3D.

I need to calculate the point at which they intersect.


I start with 2 points on each line, so 4 points in total.  Like this:


Code: [Select]
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

end


How can I calculate the intersection point?
« Last Edit: August 05, 2012, 02:11:48 PM by annikk.exe »

Lost Seedling

  • Shrub
  • ***
  • Thank You
  • -Given: 9
  • -Receive: 30
  • Posts: 205
Re: Problem with 3D Intersecting Lines
« Reply #1 on: August 05, 2012, 02:14:32 PM »
Without giving this too much thought (I'm busy with another Eufloria-related project):

Can you determine the slope of each line in each plane of reference (X, Y, and Z)...

http://www.mathopenref.com/coordequation.html

and then solve for the intersection of the two lines in each plane...

http://www.mathopenref.com/coordintersection.html

to arrive at your final solution?

I can hardly wait for your finished product if it will be anything like my imagination.

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #2 on: August 05, 2012, 05:29:13 PM »
Didn't this work?

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #3 on: August 06, 2012, 12:32:09 AM »
I'll be honest and say that I had trouble converting your maths into code. :<  Could you try explaining it again?  It's a real stumbling block for me.


I can hardly wait for your finished product if it will be anything like my imagination.

Did you see this?
Hurray for eyecandy. :>
« Last Edit: August 06, 2012, 12:43:59 AM by annikk.exe »

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #4 on: August 06, 2012, 01:00:25 AM »
Nah, s'okay. I kinda rushed that explanation and it wasn't the best I've done. I don't have my textbooks any more because I had to give them back, but I'll try my best to remember how it all works. This post will be updated as I write more of it.



A vector is a quantity with both magnitude (size) and direction. They are sometimes written as columns of numbers like vertical co-ordinates, but since I cant do that easily on here, I'll write co-ordinates in standard text and vectors in bold text. Therefore, (1,2,3) is a co-ordinate, (1,2,3) is a vector for the purposes of this explanation.

A point has a position vector which is equal to its co-ordinates. So, the point (2,6,4) has position vector (2,6,4) relative to (0,0,0). That is to say, to get from (0,0,0) to (2,6,4) one must travel 2 units in the X direction, 6 units in the Y direction and 4 units in the Z direction. More generally, the point (a,b,c) has position vector (a,b,c) and is reached by travelling a units in X, b units in Y and c units in Z.



To find the vector that moves FROM the point (1,2,3) TO the point (4,5,6), one must calculate (4,5,6)-(1,2,3). This is simple: treat each part of the vector separately to the rest. So, (4,5,6)-(1,2,3) = (4-1, 5-2, 6-3) = (3,3,3). To move in the other direction, calculate (1,2,3)-(4,5,6) =(-3, -3, -3).

In general, the vector PQ that moves FROM P(a,b,c) TO Q(d,e,f) is (d-a, e-b, f-c). The vector that moves FROM Q to P is equal to -PQ.




Now consider the line going through points with position vectors (a, b, c) and (d, e, f). Obviously P(a, b, c) and Q(d, e, f) are on that line. So, a general point R(x, y, z) on that line will have a position vector equal to the position vector of either P or Q plus some other quantity.

Now imagine the line in 3D space: To reach any point on the line, you first move to a point on it, then either toward or away from another point on it. Think of it like a ring on a bar - first you put the ring on the bar, then you can slide it along the bar, but not away from the bar. A convenient movement along the line is a multiple of the vector that goes from P to Q. Therefore, the point R has position vector OP + mPQ. Make sense, or do you want me to explain better?



More later.
« Last Edit: August 08, 2012, 04:16:51 AM by Pilchard123 »

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #5 on: August 06, 2012, 01:46:28 AM »
Thanks for this Pilchard.  I'm having trouble converting the equations in your previous explanation into code.

For example, consider that I start with this:

Code: [Select]
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

end

How do I go about calculating the values m and n?



To begin with the calculation for m, looking at the numerator, it begins "bx ay".  Bx, I guess that is the x-component of the direction vector on the second line... or..
Um, so let's start... I guess that vector would be like this?

Code: [Select]
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

m = (Bx2 - Bx1)

end

Then what's next?  I guess it would be Ay.  So I guess that must be the y-component of the direction vector for the first line.  So that would be (Ay2 - Ay1) ?


Code: [Select]
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

m = ((Bx2 - Bx1) * (Ay2 - Ay1))

end


That's just the very start of the numerator filled out.
Am I doing it right..?

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #6 on: August 06, 2012, 01:56:11 AM »
I...think so. You could probably get tables to act like vectors with a bit of Lua-foo. I might have a go in a minute.

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #7 on: August 06, 2012, 02:08:43 AM »
It needs to reduce to simple arithmetic, adding, multiplying, subtracting, etc.  Otherwise I can't turn it into code.. :>

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #8 on: August 06, 2012, 02:14:01 AM »
Yea, I know. I'm working on a bunch of methods that will mess with vectors and puke out a number.

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #9 on: August 06, 2012, 09:43:56 PM »
I've had another go, and produced this:


Code: [Select]
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)

t = (Ax1 - Bx1) / (Ax1 - Ax2 - Bx1 + Bx2) )

intersectX3d =  Ax1 + ((Ax2 - Ax1) * t)
intersectY3d =  Ay1 + ((Ay2 - Ay1) * t)
intersectZ3d =  Az1 + ((Az2 - Az1) * t)

end

I based it off an excel spreadsheet I found here: http://www.eng-tips.com/viewthread.cfm?qid=293756


Wonder if this will work?
« Last Edit: August 06, 2012, 10:19:19 PM by annikk.exe »

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #10 on: August 08, 2012, 04:18:41 AM »
Oop, bX is the x-component of the direction vector of the FIRST line, not the second. Sorry.

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #11 on: August 09, 2012, 11:48:40 AM »
It works some of the time, but also frequently produces ridiculous output.


I think the problem is that although the lines _ought_ to intersect, rounding errors and maximum number of decimal places means it isn't always exact, and this throws the calculation randomly off at times.


The solution is to find the point of closest approach on each edge, rather than looking for the point of intersection.  That should produce much more reliable coordinates, without occcasionally shooting off into erroneous values.
http://paulbourke.net/geometry/lineline3d/
« Last Edit: August 09, 2012, 11:53:03 AM by annikk.exe »

Pilchard123

  • Tester
  • Old Oak
  • ****
  • Thank You
  • -Given: 4
  • -Receive: 24
  • Posts: 932
  • Eufloria: Yes
Re: Problem with 3D Intersecting Lines
« Reply #12 on: August 09, 2012, 05:58:27 PM »
Want me to try to bash out an explanation of vector products, or have you got that okay?

annikk.exe

  • Achiever
  • Ent
  • ****
  • Thank You
  • -Given: 0
  • -Receive: 4
  • Posts: 1,809
Re: Problem with 3D Intersecting Lines
« Reply #13 on: August 09, 2012, 09:24:55 PM »
I need some time to digest the new maths involved in this strategy, may as well save your energy for now. :>  I'm sure I'll have lots of questions in due course..