Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

(Note: I realise this would perhaps fit on the gamedev stackexchange also, but i felt that since the crux of the question is asking for the explanation of a geometric formula, it perhaps fitted better here).

share|improve this question
    
This is really badly readable. Would it be difficult to translate the obscure object-oriented code into normal mathematical language? –  Luboš Motl Jun 11 '11 at 13:33
    
Apologies, to be honest i just sort of copied a part of the page in the book i was referring to almost ad verbatim. I do not have a great amount of experience with mathematical notation, and was unsure of my ability to translate this into general mathematical formula (particularly the fact that the author of the book keeps referring to things like v1 and v2 as "vectors" when i think they are closer to something like a partial line segment, since they have a very specific start and end point) –  Craig Innes Jun 11 '11 at 17:40
add comment

1 Answer 1

up vote 1 down vote accepted

You write "the book gives the following code [...] creating a third vector V3 between the start point of V1 and the start point of V2 (V1.a and V2.a)", but the code doesn't actually create V3, it just uses it. I'm going to make some assumptions to make sense of the code; you're going to have to judge for yourself whether they're correct.

It seems that by "vector" you're referring to an object which is defined by a start point $\vec a$ and an end point $\vec b$ and which contains the following information:

  • The difference $\vec v=\vec b-\vec a$, i.e. the vector pointing from $\vec a$ to $\vec b$
  • The normalized difference $\vec d = \vec v/|\vec v|$, i.e. the unit vector corresponding to $\vec v$
  • A "left normal" $\vec n$, which is orthogonal to $\vec v$ and has the same length as $\vec v$, i.e. $\vec n\cdot\vec v=0$ and $|\vec n|=|\vec v|$.

Note that "V1.ln is the vector perpendicular to V1" makes no sense, since there are infinitely many vectors perpendicular to V1, and even two different vectors perpendicular to V1 with the same length as V1; presumably "left normal" refers to an orientation convention that picks out one of these two vectors. Note also that in "V1.ln is the vector perpendicular to V1", you're using "vector" in the usual mathematical sense, not in these sense of an object representing a directed segment as defined above (else there would be an infinite regress and V1.ln would itself have a start point, an end point, and a member ln, etc.).

Given all this, I assume that in "creating a third vector V3 between the start point of V1 and the start point of V2 (V1.a and V2.a)", you're using "between" not in a geometric sense of the vector somehow lying between these two points, but you mean that the "vector" V3 has as its start point the start point of V1 and as its end point the start point of V2.

Another assumption is that the vector "V1", which you call the "motion vector" of the ship, has as its start point the current position of the ship and as its end point the position of the ship at time $t=1$, and the ship is modeled to travel along the line segment connecting the two.

Assuming all this, the code makes sense as follows. The trajectory of the ship is

$$\vec{x}(t)=\vec a_1+t(\vec b_1 - \vec a_1)\;,$$

where $\vec a_1$ and $\vec b_1$ are the start point and end point, respectively, of the "motion vector" V1.

The equation of the line with which this trajectory is being intersected is

$$\vec{x}(\lambda)=\vec a_2+\lambda(\vec b_2 - \vec a_2)\;,$$

where $\vec a_2$ and $\vec b_2$ are the start point and end point, respectively, of the "target vector" V2.

To find the intersection, we need to equate the two:

$$\vec a_1+t(\vec b_1 - \vec a_1)=\vec a_2+\lambda(\vec b_2 - \vec a_2)\;.$$

To solve this for $t$, we can multiply it by the "left normal" of V2, since this is orthogonal to $\vec b_2 - \vec a_2$ and will thus get rid of $\lambda$:

$$(\vec a_1+t(\vec b_1 - \vec a_1))\cdot \vec n_2=(\vec a_2+\lambda(\vec b_2 - \vec a_2))\cdot \vec n_2\;,$$

$$t(\vec b_1 - \vec a_1)\cdot \vec n_2=(\vec a_2-\vec a_1)\cdot \vec n_2\;,$$

$$t=\frac{(\vec a_2 - \vec a_1)\cdot \vec n_2}{(\vec b_1-\vec a_1)\cdot \vec n_2}\;.$$

Since $a_1$ and $a_2$ are start point and end point, respectively, of V3, we're almost there; the only difference to the computation in the code is that the normals and the differences are interchanged, and that the normalized difference of V2 is used in the code. But swapping normals and differences only introduces a minus sign in the dot products (turning one vector by $\pi/2$ instead of the other changes the angle by $\pi$), and this minus sign drops out of the fraction, as does the length of V2, so the formulas are actually equivalent. The last two lines of the code then just substitute this value of $t$ into the ship's trajectory.

share|improve this answer
    
Thanks, this goes a good way to clearing things up a bit :) And yes apologies for the rather slapdash explanation of my predicament. I was struggling with both my own inexperience with mathematical definitions and the author's idiosyncratic use of certain mathematical words like 'vector' –  Craig Innes Jun 11 '11 at 17:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.