- Home /
How to check for an intersection between two lines in 3d space with floats´lack of precision in mind?
In 2d, getting the point of intersection between two lines is easy. You basically solve for a variable that works like a magnitude multiplier for the direction vector. You have your lines like this, for example: (1 + 2s, 3 - 3s) and (0.5 + 4t, 1 - 2t). Then you set them equal to solve for s, then use substitution to get one variable in terms of the other and you´ve got the s (or t) that gives you the point of intersection. And because s or t can be any value from positive infinity to negative infinity, they will collide as long as they aren´t parallel, since the equation assumes both are infinite lines. But in 3d space, this doesn´t really work. Most lines won´t ever intersect, even if they are infinite. Now, if they should, you would basically do the same but then check that also (z direction)s = (z direction)t. The problem is... well, float´s lack of precision. It might look like they are not intersecting when they really are. In my case, I´ve got two aligned lines. You could visualize them as part of the same plane (they aren´t, but it helps to understand their placement). Again, as long as they aren´t parallel they should intersect. I don´t know if that helps or not, but then, how can I code in a way that floats don´t matter?
Answer by Captain_Pineapple · Feb 20, 2020 at 09:38 AM
Calculate the minimum distance between the 2 lines and check the magnitude. If that is below a certain threshold then there is an intersection. Should get rid of the problem since you are then able to define the threshold as you like.
The math you need can be found here in case you need it.
just to be sure: this will ofc not solve the issue of floating point imprecision so the threshold you set must of not be too small or you might be stuck at the same problem again. But i guess this solution should be sufficient for the most use-cases.
Answer by Bunny83 · Feb 20, 2020 at 06:49 PM
I just like to mention that if you want to go for a linear system of equations, this still works exactly the same way. However instead of having 2 equations and 2 unknowns we have 3 equations and 3 unknowns. The actual question we have to answer here is how do we get from the start point of line A to the start point of line B by a linear combination of the direction vector of line A, the direction vector of line B and the perpendicular vector of the two direction vectors. Those 3 vectors span the full 3d space. We are looking for the 3 parameters of our 3 axis how to connect the two points using those 3 axis.
Since all is just a matter of relativity, of course we would just move our whole construct in such a way so one line starts at the origin. All we have to do is subtract the starting point of line A from both starting points of our lines. This will make line A start at the origin and line B is moved accordingly. So we start with those two lines:
P(a) = Astart + a*Adir;
P(b) = Bstart + b*Bdir;
We get the third axis (Cdir) through the cross product between Adir and Bdir.
Cdir = Vector3.Cross(Adir, Bdir);
Our final equation we are looking for is
a*Adir - b*Bdir + c*Cdir = Bstart - Astart;
If we write out each component equation we get
a*Adir.x - b*Bdirx. + c*Cdir.x = Bstart.x - Astart.x;
a*Adir.y - b*Bdiry. + c*Cdir.y = Bstart.y - Astart.y;
a*Adir.z - b*Bdirz. + c*Cdir.z = Bstart.z - Astart.z;
Here we have 3 equations and 3 unknows (a, b and c). When solving this system "a" will be the required parameter for line A to get the closest point to line B. Likewise "b" is the point on line B that is closest to line A. And finally "c" represents the distance between those two points. In case the lines truely intersect this would ideally be 0. However that's never the case due to inaccuracies. In the real world you could never have two lines in 3d space to actually cross each other. Keep in mind we talk about mathematical lines. They have no thickness. Yes, mathematically when having infinite precision you can choose a certain configuration which gives you a perfect crossing. In any case or reality the lines always just get close to each other and "c" will tell you how close.
Note that the value of "c" can also be determined by just calculating the distance between the two parallel planes. Plane A would be the plane where lineA is in and has a normal vector of Cdir and plane B would be the plane where lineB is in. Since both planes are parallel they have the same normal vector (Cdir). The distance between the two planes is just the difference between the "D" term of the plane equations.
Plane planeA = new Plane(Cdir, Astart);
Plane planeB = new Plane(Cdir, Bstart);
float c = planeA.distance - planeB.distance;
Note that I haven't paid much attention to the signs here. So "c" might be inverted. Anyways c will tell you how close the two lines actually get.
If you have trouble understanding any of this I would recommend to refresh your linear algebra skills (3b1b for rescue) ;)
$$anonymous$$an i wish i had your time and patience to put so much effort in your answers... once again well done mate.
:) I just like math and geometry. I've just got home and have thrown this system onto an online solver. Of course it spit out an endless convoluted solution for a, b and c. However I recognised a pattern. In pseudo code it's essentially this if I didn't make a mistake :D:
D = -det([Adir, Bdir, Cdir]);
a = (Bdir x Cdir) * dif / D;
b = (Adir x Cdir) * dif / D;
c = (Adir x Bdir) * dif / D;
To make it a bit more clear "x" is the cross product "*" is the dot product. So it's essentially the tripple product. D is just the deter$$anonymous$$ant of the 3x3 matrix of our 3 direction vectors (Adir, Bdir and Cdir). "dif" is just Bstart - Astart
So something like that:
D = -( Adir.x*Bdir.y*Cdir.z + Adir.y*Bdir.z*Cdir.x + Adir.z*Bdir.x*Cdir.y
-Cdir.x*Bdir.y*Adir.z - Cdir.y*Bdir.z*Adir.x - Cdir.z*Bdir.x*Adir.y );
This is of course untested ^^