shoot projectile (straight trajectory) at moving target in 3 dimensions

I already googled for the problem but only found either 2D solutions or formulas that didn't work for me (found this formula that looks nice: http://www.ogre3d.org/forums/viewtopic.php?f=10&t=55796 but seems not to be correct).

I have given:

Vec3 cannonPos;
Vec3 targetPos;
Vec3 targetVelocityVec;
float bulletSpeed;

what i'm looking for is time t such that

targetPos+t*targetVelocityVec

is the intersectionpoint where to aim the cannon to and shoot.

I'm looking for a simple, inexpens开发者_开发知识库ive formula for t (by simple i just mean not making many unnecessary vectorspace transformations and the like)

thanks!

---

The real problem is finding out where in space that the bullet can intersect the targets path. The bullet speed is constant, so in a certain amount of time it will travel the same distance regardless of the direction in which we fire it. This means that it's position after time t will always lie on a sphere. Here's an ugly illustration in 2d:

This sphere can be expressed mathematically as:

(x-x_b0)^2 + (y-y_b0)^2 + (z-z_b0)^2 = (bulletSpeed * t)^2      (eq 1)

x_b0, y_b0 and z_b0 denote the position of the cannon. You can find the time t by solving this equation for t using the equation provided in your question:

targetPos+t*targetVelocityVec                                   (eq 2)

(eq 2) is a vector equation and can be decomposed into three separate equations:

x = x_t0 + t * v_x
y = y_t0 + t * v_y
z = z_t0 + t * v_z

These three equations can be inserted into (eq 1):

(x_t0 + t * v_x - x_b0)^2 + (y_t0 + t * v_y - y_b0)^2 + (z_t0 + t * v_z - z_b0)^2 = (bulletSpeed * t)^2

This equation contains only known variables and can be solved for t. By assigning the constant part of the quadratic subexpressions to constants we can simplify the calculation:

c_1 = x_t0 - x_b0
c_2 = y_t0 - y_b0
c_3 = z_t0 - z_b0
(v_b = bulletSpeed)

(t * v_x + c_1)^2 + (t * v_y + c_2)^2 + (t * v_z + c_3)^2 = (v_b * t)^2

Rearrange it as a standard quadratic equation:

(v_x^2+v_y^2+v_z^2-v_b^2)t^2 + 2*(v_x*c_1+v_y*c_2+v_z*c_3)t + (c_1^2+c_2^2+c_3^2) = 0

This is easily solvable using the standard formula. It can result in zero, one or two solutions. Zero solutions (not counting complex solutions) means that there's no possible way for the bullet to reach the target. One solution will probably happen very rarely, when the target trajectory intersects with the very edge of the sphere. Two solutions will be the most common scenario. A negative solution means that you can't hit the target, since you would need to fire the bullet into the past. These are all conditions you'll have to check for.

When you've solved the equation you can find the position of t by putting it back into (eq 2). In pseudo code:

# setup all needed variables
c_1 = x_t0 - x_b0
c_2 = y_t0 - y_b0
c_3 = z_t0 - z_b0
v_b = bulletSpeed
# ... and so on

a = v_x^2+v_y^2+v_z^2-v_b^2
b = 2*(v_x*c_1+v_y*c_2+v_z*c_3)
c = c_1^2+c_2^2+c_3^2

if b^2 < 4*a*c:
    # no real solutions
    raise error

p = -b/(2*a)
q = sqrt(b^2 - 4*a*c)/(2*a)

t1 = p-q
t2 = p+q

if t1 < 0 and t2 < 0:
    # no positive solutions, all possible trajectories are in the past
    raise error

# we want to hit it at the earliest possible time
if t1 > t2: t = t2
else: t = t1

# calculate point of collision
x = x_t0 + t * v_x
y = y_t0 + t * v_y
z = z_t0 + t * v_z