Calculating interception vector and time scalar

The position of the target dependent on the time t:
P_T(t) := O_T + t * v_T * d_T
where O_T is its initial position (i.e. when t==0), v_T is its velocity (notice that this is a scalar!), and d_T is its moving direction (normalized to a length of 1). This formula assumes a linear straight movement of the target. It also reduces the target to a point.

Similarly,
P_P(t) := O_P + t * v_P * d_P
expresses the same for the projectile, obviously with other parameters. This formula also assumes a linear straight movement of the projectile, of course.

Now, if
P_T(t) = P_P(t)
is given for any t>=0, then the both positions are identical. Notice that if you set in the terms
O_T + t * v_T * d_T = O_P + t * v_P * d_P
and re-orders them like so
O_T - O_P = t * ( v_P * d_P - v_T * d_T )
you'll see a term that is missed in the formula of the OP.

Now in principle there is only 1 real unknown variable, namely t, for which the equation has to be solved. To be able to do so you have to know especially the parameters v_T and d_T. Perhaps v_P is much greater than v_T (e.g. a bullet is fired at a human), then the simplification
v_P * d_P - v_T * d_T is approx. v_P * d_P
can be made. Else the parameters have to be estimated by measuring the movement of the target for a small period of time (perhaps it is eplicitely known by the engine, of course; depends on how the target is controlled).

Thank you for the reply.

The problem is that there are 2 unknown variables, time and the D_T and because of that all i could think of was to start time at almost 0 and increment it and checking how long the D_P vector is. If it's less than 1 then i know we've overshot and should decrement the time with more accuracy and while it's longer than 1 continue to increment it until it's as close to 1 as we will accept.

Sometimes there won't be a solution of course, depending on where the objects are and what velocities are chosen.

Seeing as you seem to have a better grasp of math, did you read the other thread?

Maybe we could somehow calculate the time variable if we assume that there exists a solution seeing as the ratio between the distances needed to travel is the same as the ratio between the two objects' speed.

Quote:

Original post by Cybrosys The problem is that there are 2 unknown variables, time and the DT and because of that all i could think of was to start time at almost 0 and increment it and checking how long the DP vector is. If it's less than 1 then i know we've overshot and should decrement the time with more accuracy and while it's longer than 1 continue to increment it until it's as close to 1 as we will accept.

Oh, now I see your point. Sorry for my misunderstanding.

Okay. This equation
O_T - O_P = t * ( v_P * d_P - v_T * d_T )
contains actually 4 unknown values since d_P is a 3D vector. With its 3 dimensions it also provides 3 scalar equations. That is still 1 equation too less. But luckily there is another implicit equation that helps. Let's see:

Lets define a distance vector to save some writing
s := O_T - O_P
and
v_T := v_T * d_T
v_P := v_P * d_P
what means nothing more than that the direction of motion (with a length of 1) is scaled by the speed, so that a velocity vector is resulting.

Setting in leads to
s = t * ( v_P - v_T )
what can be decomposed into 3 scalar equations
s_x = t * ( v_Px - v_Tx )
s_y = t * ( v_Py - v_Ty )
s_z = t * ( v_Pz - v_Tz )

Next we know that
|v_P| = sqrt( v_Px² + v_Py² + v_Pz² ) == v_P
i.e. the length of the velocity vector of the projectile is just given. Using a square to hide the nasty sqrt leads to
v_Px² + v_Py² + v_Pz² == v_P²
what is just the 4-th equation mentioned above.

Now isolate v_Px, v_Py, v_Pz from the first 3 equations
v_Px = ( s_x + t * v_Tx ) / t
v_Py = ( s_y + t * v_Ty ) / t
v_Pz = ( s_z + t * v_Tz ) / t
and setting this into the 4-th equation, and calculating the squares, so that (if I made no mistake)
( s_x² + s_y² + s_z²) + 2 * t * ( s_x * v_Tx + s_y * v_Ty + s_z * v_Tz ) + t² * ( v_Tx² + v_Ty² + v_Tz² ) = t² * v_P²
or in vector form (if you have a nice vector math lib at hand
|s|² + 2 * t * s * v_T + t² * |v_T|² = t² * v_P²

Herein only t is unknown, and the whole formula is a quadratic equation in t. One can solve any quadratic equation of the form
f(t) := t² + c₁ * t + c₀ = 0
by the so-called "pq-formula" (well, it is called so in Germany), yielding in
t_a = - c₁ / 2 + sqrt( c₁² / 4 - c₀ )
t_b = - c₁ / 2 - sqrt( c₁² / 4 - c₀ )

If the argument of the sqrt is negative then there is no (real) solution since both motions are parallel; if it is 0 then there is 1 solution, and if it is greater than 0 then it has 2 solutions. A negative t will be nonsense in your case, of course.

However, the terms a, b, c, and d in the cited thread are just intermediate results of solving the pq-fomula above. But notice that I have written down the 3-dimensional case, while the cited thread shows it for 2 dimensions.

With the (senseful) t you can compute P_T(t) and from that d_P (see my first post above).

Hopefully that helps you a bit. Please excuse me if I have made the one or other mistake in the math above. I will correct it if I recognize one.

[EDIT: 4 mistakes corrected by now]

[Edited by - haegarr on June 30, 2007 1:18:37 PM]

Thank you, you've been very helpful :) (Rate++)

I'm reading through your post and checking the math, the only thing that caught my eye so far was that you stated that:

V_Px = (S_x + t * V_Tx) / t

when a simpler one is:
V_Px = V_Tx + S_x / t

Was there a reason for doing so?

Quote:

Original post by Cybrosys I'm reading through your post and checking the math, the only thing that caught my eye so far was that you stated that: VPx = (Sx + t * VTx) / t when a simpler one is: VPx = VTx + Sx / t Was there a reason for doing so?

Not really. I've just solved the brace, added the one term and divided by t, while you've gone a step furthur. Later when eliminating the division after setting into the 4-th equation both ways yield in the same, so its just a matter of taste and how many steps one skips during explanation.

Well, thank you again. I was going insane over the problem :)