00:00
00:00
Newgrounds Background Image Theme

Kiler91 just joined the crew!

We need you on the team, too.

Support Newgrounds and get tons of perks for just $2.99!

Create a Free Account and then..

Become a Supporter!

Intersection of two vectors

502 Views | 3 Replies
New Topic Respond to this Topic

Intersection of two vectors 2011-06-11 09:14:49


I am currently working my way through a book on Game Programming in Actionscript 3, and have gotten to a formula required for collision detection on finding the intersection point of two vectors.

Im not sure if the author uses vectors in the strictest definition, but the convention he uses is e.g for a vector V1 :

V1.a is the start point of the vector V1.b is the end point of the vector V1.ln is the vector perpendicular to V1 (its 'left normal') V1.vx is the difference between the x coordinate of V1.b and V1.a V1.vy similar to vx V1.dx is the same as vx , but for V1 scaled down to a unit vector (the direction vector)

Now,in the example we have V1 which is the motion vector of the ship, and V2, which is the target vector (i.e the line the ship is going to collide with at some point)

In order to calculate at what point on V2 the ship will collide travelling along motion vector V1, the book gives the following code using the "perpendicular dot product" (Which i have not come across before) and creating a third vector V3 between the start point of V1 and the start point of V2 (V1.a and V2.a):

perpProduct1 = v3.ln.vx * v2.dx + v3.ln.vy * v2.dy
perpProduct2 = v1.ln.vx * v2.dx + v1.ln.vy * v2.dy
t = perpProduct1 / perpProduct2
intersectionX = v1.a.x + v1.vx * t
intersectionY = v1.a.y + v1.vy * t

Now, i could easily just copy and paste that code wherever i need it and be done with it. But it bugs me that i dont really understand the mathematics of whats going on here. If someone could please give me a geometric explanation of how this algorithm finds the intersection point, or at least some sort of algebraic proof, it would help me sleep a little better tonight. Cheers.

Response to Intersection of two vectors 2011-06-11 09:23:05



If ya have something to say, PM me. I have a lot of time to spare.

Also never PM egg82.

BBS Signature

Response to Intersection of two vectors 2011-06-11 09:33:23


Cheers for the link, but i have already come across this page in my search. It appears to explain the more conventional method of finding the intersection of two lines (i.e by making the two line's equations equal to each other) Whereas i am interested in an explanation for why the method outlined above (e.g why are normals of the vectors used etc.?)

It is possible that you were saying that the explanation to my question is implied by the method outlined in the link, but if so i do not have the mathematical know how to make the connection.

Response to Intersection of two vectors 2011-06-11 10:05:48


I believe this code is from: Advanced Game Design with Flash by Rex van der Spuy. (page 117)
it is clear that if you don't have a solid understanding of vectors, you are not going to fully understand the example (as did I).
You see, finding the intersection point of 2 lines sounds really easy. We've all done it in high school where we would get something like:
l1 : y = 3x
l2 : y = 5x + 3
and you would do something like:
3x = 5x + 3
2x = -3
x= -1.5 (y = 3x) y = 3* -1.5 = -4.5
(x; y) = (-1.5 ; -4.5)
But doing this without concrete numbers can be quite difficult.
Especially since we can have a horizontal and vertical lines, which forces us into:
ax + by + c = 0
And vectors are made with 2 points. Converting 2 point into a line gives us:
y - y1 = [(y2 - y1) / (x2 - x1)]%u2022(x - x1) - line 1
Image another 1 of this (line 2) :
y - y3 = [(y4 - y3) / (x4 - x3)]%u2022(x - x3) - line 2

Now the story goes as we already know: isolate the x and y and you've got your intersection point!
but with 4 unknown variables this becomes rather complex. And as you can see we have some nice divisions in our formulas, and as we all know you can't divide by 0 so we have to work around that as well if you want it to work in all conditions (and you do).

Long story short: doing the math for this from the ground up takes time and is complex.
The main advantage of vectors is that they are nice and simple. Especailly in OOP where you can just make a vector object and don't have to worry much about hów it works, but just know thát it works.
Believe me you don't want to debug more than 10 lines of code that does all this math from the ground up.
The disadvantage of using vector objects is on the other hand that you are doing some unnecessary checks and taking a little more CPU. If you really want to see how to do the basic math of this you should see this link.
Especially when you go into more advanced math and physics you don't want to go over these fundamental vector things that you might not be entirely familiar with.
The whole idea of OOP is that once you've done something and it works, you don't want to spent any time rebuilding the same thing or even understand how it works exactly all the time. This is just one of these things you should say: 'ok: this works, it's easy, let's use it!' unless again you are a control freak and want to do all this from the ground up.
If this is the case, you need to calculate the normals of the vectors expressed in the x and y positions of the points that make up the vector, calculate the perpProducts, and eventually get the intersection points expressed in those x and y positions of the lines. The equations that you will eventually end up with will most likely be longer than a page but if you get it right, it should be identical to the result of the link. I think it is better for you to just get a solid understanding of vectors in general and eventually it will make sense to you.