So I was watching a video on 2D ray casting as I want to add in some lighting effects into my game. Now, I believe that chili has covered line-line intersection in one video or another, but for some reason I or another I didn't catch on to what was going on and while watching this other video something clicked. The video author used the wikipedia explanation and one of the audience of the stream asked about some notation that was being used. He said that was signifying a determinant and that's what set things off.
I recently had been looking through matrix operations and wanted to know how to calculate the determinant. Once I understood that, I was able to understand the formulas on the wikipedia page.
So first off, finding the determinant of a 2x2 matrix:
Code: Select all
M = | r00 r01 |
| r10 r11 |
left = r00 * r11;
right = r10 * r01;
Then subtract right from left
determinant = left - right;
Now, how does this apply to line-line intersection? Well, I don't know lol. I do know that this is how the formulas work, so here's the formulas from wikipedia.
L1 and L2 are lines
p1 and p2 are points defining the start and end points
Px and Py are the x and y or the intersecting point
Code: Select all
Px = | L1.p1.x L1.p1.y | | L1.p1.x 1 |
| L1.p2.x L1.p2.y | | L1.p2.x 1 |
| L2.p1.x L2.p1.y | | L2.p1.x 1 |
| L2.p2.x L2.p2.y | | L2.p2.x 1 |
-------------------------------------------------- // divided by
| L1.p1.x 1 | | L1.p1.y 1 |
| L1.p2.x 1 | | L1.p2.y 1 |
| L2.p1.x 1 | | L2.p1.y 1 |
| L2.p2.x 1 | | L2.p2.y 1 |
Py = | L1.p1.x L1.p1.y | | L1.p1.y 1 |
| L1.p2.x L1.p2.y | | L1.p2.y 1 |
| L2.p1.x L2.p1.y | | L2.p1.y 1 |
| L2.p2.x L2.p2.y | | L2.p2.y 1 |
-------------------------------------------------- // divided by
| L1.p1.x 1 | | L1.p1.y 1 |
| L1.p2.x 1 | | L1.p2.y 1 |
| L2.p1.x 1 | | L2.p1.y 1 |
| L2.p2.x 1 | | L2.p2.y 1 |
Code: Select all
det0 = L1.p1.x * 1 - L1.p2.x * 1 -> L1.p1.x - L1.p2.x
det1 = L1.p1.y * 1 - L1.p2.y * 1 -> L1.p1.y - L1.p2.y
det2 = L2.p1.x * 1 - L2.p2.x * 1 -> L2.p1.x - L2.p2.x
det3 = L2.p1.y * 1 - L2.p2.y * 1 -> L2.p1.y - L2.p2.y
Now, calculate the determinant of the results from above
D = | L1.p1.x - L1.p2.x L1.p1.y - L1.p2.y |
| L2.p1.x - L2.p2.x L2.p1.y - L2.p2.y |
denominator =
( ( L1.p1.x - L1.p2.x ) * ( L2.p1.y - L2.p2.y ) )
-( ( L2.p1.x - L2.p2.x ) * ( L1.p1.y - L1.p2.y ) )
or
D = | det0 det1 |
| det2 det3 |
denominator = det0 * det1 - det2 * det3
Once you have found the denominator, you can have an early out if the determinant is equal to 0 as this means that the lines are parallel with each other and there will never be a collision.
As noted in the wikipedia article, if there is a point of intersection, it might be on the line and not the segments in your code, so you must calculate a few more determinants to determine that.
t and u are going to be percentages of how far on the line segment the point is between the start and end. If the value of either is below 0, then the POI is somewhere before the start point and if greater than 1 it's somewhere after the end point, and any value between 0 and 1 for t means it's within the first line segment and 0 to 1 for u means it's within the second line segment.
Code: Select all
t = | L1.p1.x - L2.p1.x | | L2.p1.x - L2.p2.x |
| L1.p1.y - L2.p1.y | | L2.p1.y - L2.p2.y |
--------------------------------------------------------// divided by
| L1.p1.x - L1.p2.x | | L2.p1.x - L2.p2.x |
| L1.p1.y - L1.p2.y | | L2.p1.y - L2.p2.y |
u = | L1.p1.x - L1.p2.x | | L1.p1.x - L2.p1.x |
| L1.p1.y - L1.p2.y | | L1.p1.y - L2.p1.y |
-------------------------------------------------------// divided by
| L1.p1.x - L1.p2.x | | L2.p1.x - L2.p2.x |
| L1.p1.y - L1.p2.y | | L2.p1.y - L2.p2.y |
denominator = |
( L1.p1.x - L1.p2.x ) * ( L2.p1.y - L2.p2.y )
- ( L1.p1.y - L1.p2.y ) * ( L2.p1.x - L2.p2.x )
t =
( L1.p1.x - L2.p1.x ) * ( L2.p1.y - L2.p2.y )
- ( L1.p1.y - L2.p1.y ) * ( L2.p1.x - L2.p2.x )
-------------------------------------------------------
( L1.p1.x - L1.p2.x ) * ( L2.p1.y - L2.p2.y )
- ( L1.p1.y - L1.p2.y ) * ( L2.p1.x - L2.p2.x )
u =
-( ( L1.p1.x - L1.p2.x ) * ( L1.p1.y - L2.p1.y )
-( L1.p1.y - L1.p2.y ) * ( L1.p1.x - L2.p1.x )
------------------------------------------------------
( L1.p1.x - L1.p2.x ) * ( L2.p1.y - L2.p2.y )
- ( L1.p1.y - L1.p2.y ) * ( L2.p1.x - L2.p2.x ) )
Ok, so while I'm not sure why this works, I now understand how it works.
I mostly just put this here in case I forget, also it's bound to be useful at some point. Apparently, you can use the cross product to find the POI, but I'm having troubles following the formulas for that right now, if I figure it out I"ll probably post that here as that seems less computationally expensive than finding the determinant of 17 2x2 matrices. There is a lot of redundant operations, so I'm sure it's not as expensive as it looks.