Euflorium: The Eufloria Community
Eufloria => Eufloria Classic => Eufloria Classic Mods => Topic started by: annikk.exe 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:
function Calculate3DIntersectionPoint(Ax1, Ay1, Az1, Ax2, Ay2, Az2, Bx1, By1, Bz1, Bx2, By2, Bz2)
end
How can I calculate the intersection point?
-
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 (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 (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.
-
Didn't this (http://www.dyson-game.com/smf/index.php?topic=1562.msg12137#msg12137) work?
-
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 (http://www.dyson-game.com/smf/index.php?topic=1494.msg12327#msg12327)?
Hurray for eyecandy. :>
-
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.
-
Thanks for this Pilchard. I'm having trouble converting the equations in your previous explanation (http://www.dyson-game.com/smf/index.php?topic=1562.msg12137#msg12137) into code.
For example, consider that I start with this:
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?
(http://www.dyson-game.com/smf/index.php?action=dlattach;topic=1562.0;attach=996;image)
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?
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) ?
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..?
-
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.
-
It needs to reduce to simple arithmetic, adding, multiplying, subtracting, etc. Otherwise I can't turn it into code.. :>
-
Yea, I know. I'm working on a bunch of methods that will mess with vectors and puke out a number.
-
I've had another go, and produced this:
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?
-
Oop, bX is the x-component of the direction vector of the FIRST line, not the second. Sorry.
-
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/
-
Want me to try to bash out an explanation of vector products, or have you got that okay?
-
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..