Line-Line intersection using matrices

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Line-Line intersection using matrices

Post by albinopapa » May 13th, 2019, 5:12 am

EDIT: The math is correct, but the process is not. The Px and Py parts is for infinite lines, the t and u parts are for line segments, they don't go together. So it is not as expensive as I thought.

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 |
First, cross multiply r00 with r11 and r10 with r01
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 |
Let's first start with the denominator and find the determinants. There are four 2x2 matrices and must find the determinants of all four, which will be another 2x2 matrix that we find the determinant of.

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
The same thing goes for the Px and Py. After you find Px and Py, divide both by denominator

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 ) )

In case it's not clear, the result of finding 'u' is negated.

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.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Line-Line intersection using matrices

Post by albinopapa » May 13th, 2019, 5:13 am

If you get lost with all the formulas, just compare the expanded formulas with the matrices and you should see how things are laid out, just refer back to how the determinant of a 2x2 matrix is found.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Line-Line intersection using matrices

Post by albinopapa » May 13th, 2019, 10:59 pm

Here's my implementation:

Code: Select all

#pragma once

#include "Ray.h"
#include <optional>

constexpr std::optional<std::pair<Vec2f,float>> IntersectsWith( Ray2d const& ray, Vec2f const& p1, Vec2f const& p2 )
{
	auto const p3 = ray.position;
	auto const p4 = Vec2f{ ray.position + ray.direction };

	auto const p1p2 = p1 - p2;
	auto const p3p4 = p3 - p4;
	auto const den = cross_product( p3p4, p1p2 );

	if( den == 0.f )
		return std::optional<std::pair<Vec2f, float>>();

	auto const p1p3 = p1 - p3;
	auto const t =  cross_product( p3p4, p1p3 ) / den;
	auto const u = -cross_product( p1p3, p1p2 ) / den;

	if( t >= 0.f && t <= 1.f && u >= 0.f )
		return std::optional<std::pair<Vec2f, float>>{std::pair{ p1 + ( ( p2 - p1 ) * t ), u }};

	return std::optional<std::pair<Vec2f, float>>{};
}
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
krautersuppe
Posts: 91
Joined: September 14th, 2015, 10:58 pm
Location: Istanbul

Re: Line-Line intersection using matrices

Post by krautersuppe » May 14th, 2019, 6:23 pm

My vector math material on intermediate problems is under way. It contains several intersection problems, use of determinants for cross product and linear mapping theory with detailed and illustrated solutions . I cannot promise certain release date though.. I might even add and cover this to that material but you will need to wait a bit
DSU
Discord: dsu1, GitHub: https://github.com/DSpUz

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Line-Line intersection using matrices

Post by albinopapa » May 14th, 2019, 7:07 pm

Um, can you dumb it down for someone like me? I haven't been able to understand or use any of the previous material you've uploaded ashamedly.

Actually, don't dumb it down, I just need to seek a path from start to finish. I don't have the foundation necessary to use any of these building blocks.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
krautersuppe
Posts: 91
Joined: September 14th, 2015, 10:58 pm
Location: Istanbul

Re: Line-Line intersection using matrices

Post by krautersuppe » May 14th, 2019, 7:50 pm

Stuff i posted is designed for dumbing it down. One should be able to somehow work through it after watching some introduction video on vectors. Is it arithmetics that you are struggling with or spatial imagination? At the end I intend this to be suitable for anyone to work through from beginning to end and that means that simple ones are not simple enough yet. I really tried to solve first part in great detail though :( - can you PM me about stuff that is not clear in that one?
DSU
Discord: dsu1, GitHub: https://github.com/DSpUz

Post Reply