@johnstanp: I may still have been posting / editing, since I only realised afterwards.

@BrotherBob: Ah, yeah. :)

I've solved something similar to this before, and yes, it is a 4th order polynomial. There are a number of ways to solve it, but all the ones I used involve some kind of iterative relaxation (like newtons method and other solutions).

However, a google search reveals the following:

http://en.wikipedia.org/wiki/Quartic_function#The_general_case.2C_along_Ferrari.27s_lines

So there's that. Good luck.

Quote:Original post by sprite_hound
Hmm. I get a second order polynomial, but I could well be going wrong somewhere:

Tp^2 - Bp^2 + t^2(Tv^2-Bs^2) + t^4(Ta^2 / 4) = 0t^2(Ta / 2) + t(Tv-Bs) + Tp - Bp = 0

I'm pretty sure this step is invalid. Unless I'm mistaken, there is no proof that the roots of (a^2 t^4+b^2 t^2+c^2) are the same as the roots of (a t^2 + b t + c)

Sorry to post so many times... One thing I wanted to mention: Guess and check is a pretty terrible "iterative solution." If you want to solve this, there's no reason an iterative solver has to be slow. Hell, most matrix decompositions are "iterative" and yet you can find a solution for a smallish matrix in very very short time because the algorithms are well understood and well optimized.

Now that you have the closed form, try implementing a real iterative root finder for a 4th order polynomial and I imagine the speed will be MUCH greater then whatever you are currently doing, despite the fact that its not a closed form solution.

Quote:
#2:
- A: (Tv-Bs). How does that work? Tv is a 3D vector and Bs is a single scalar. I could do a component-wise subtraction, but I want to verify—is this really what you meant? “Target Velocity” Tv and “Bullet Speed” Bs may have been cause for confusion; if you treat these both as 3D vectors I can see how you would reach this conclusion, but since one of them is actually scalar I want to be sure this is not a conclusion reached in confusion.

Yeah, I was assuming it was a 3d vector. I actually now think my whole working is very wrong due to forgetting how to multiply out brackets. [embarrass]

[Edited by - sprite_hound on November 15, 2010 1:35:51 PM]

Quote:Original post by YogurtEmperor
Is this the same as length²((Tp+Tvt+½×Tat²)-Bp)-(Bst*Bst) = 0, or did I miss a detail?

f²(x)-y²=0 is not equivalent to f²(x-y)=0
To prove it: simply take a counter example.

Let's f(x)=x;
x²-y²=0 is equivalent to (x-y)²=0?
The solutions of x²-y²=0 are x=y or x=-y
The unique solution of (x-y)²=0 is x=y.
So, the answer is "no".

It is not forbidden to do the following:
A := complex expression
B := another complex expression

A²-B²=0 <=> (A-B)(A+B)=0 <=> A=B OR A=-B
so lenth²(X) = Y² is equivalent to (length(X)-Y)(length(X)+Y)=0
But length(X) involves a square root. So it's easier working with length²(X)-Y²=0. But it introduces a solution that will have to be rejected when Y!=0 since length(X) cannot be negative.

As already said, you should have a 4th order polynomial at the left side (or whatever side you chose to put all the non zero terms) when developing your equation. There is an analytical solution to such a problem: actually there are analytical solutions up to the fourth order if I remember well.
A link:
Quartic_function

Good work! :-)

[Edited by - johnstanp on November 15, 2010 1:13:45 PM]

I found this link:

http://mathworld.wolfram.com/QuarticEquation.html

but currently I have no time to solve it, maybe tonight, if no one else has by then.

Length ^ 2 ( Tp + (Tv * t) + ((1 / 2) * Ta * (t ^ 2)) - Bp) - (Bs^2 * (t ^ 2)) = 0
-------------------------------
(Tpx + (Tvx * t) + ((1/2) * Tax * t^2) - Bpx) ^ 2 + (Tpy + (Tvy * t) + ((1/2) * Tay * t^2) - Bpy) ^ 2 + (Tpz + (Tvz * t) + ((1/2) * Taz * t^2) - Bpz) ^ 2 - (Bs^2 * t^2) = 0
-------------------------------
Tpx^2 + (Tvx^2 * t^2) + ((1/4) * Tax^2 * t^4) - Bpx^2 + (2 * Tpx * Tvx * t) + (Tpx * Tax * t^2) - (2 * Tpx * Bpx) + (Tvx * Tax * t^3) - (2 * Tvx * Bpx * t) - (Tax * Bpx * t^2) +
Tpy^2 + (Tvy^2 * t^2) + ((1/4) * Tay^2 * t^4) - Bpy^2 + (2 * Tpy * Tvy * t) + (Tpy * Tay * t^2) - (2 * Tpy * Bpy) + (Tvy * Tay * t^3) - (2 * Tvy * Bpy * t) - (Tay * Bpy * t^2) +
Tpz^2 + (Tvz^2 * t^2) + ((1/4) * Taz^2 * t^4) - Bpz^2 + (2 * Tpz * Tvz * t) + (Tpz * Taz * t^2) - (2 * Tpz * Bpz) + (Tvz * Taz * t^3) - (2 * Tvz * Bpz * t) - (Taz * Bpz * t^2)
- (Bs^2 * t^2) = 0

-------------------------------

((1/4) * (Tax^2 + Tay^2 + Taz^2) * t^4) +
(((Tvx * Tax) + (Tvy * Tay) + (Tvz * Taz)) * t^3) +
((Tvx^2 + Tvy^2 + Tvz^2 + (Tpx * Tax) + (Tpy * Tay) + (Tpz * Taz) - (Tax * Bpx) - (Tay * Bpy) - (Taz * Bpz) - Bs^2) * t^2) +
(2 * ((Tpx * Tvx) + (Tpy * Tvy) + (Tpz * Tvz) - (Tvx * Bpx) - (Tvy * Bpy) - (Tvz * Bpz)) * t) +
Tpx^2 + Tpy^2 + Tpz^2 - Bpx^2 - Bpy^2 - Bpz^2 - (2 * ((Tpx * Bpx) + (Tpy * Bpy) + (Tpz * Bpz)))
= 0
-------------------------------

Wich is of the form

A * t^4 + B * t^3 + C * t^2 + D * t + F = 0 (1)
(using F instead of E on porpuese just to avoid getting it confused with Euler's number)

Having:
A = (1/4) * (Tax^2 + Tay^2 + Taz^2)
B = (Tvx * Tax) + (Tvy * tay) + (Tvz * Taz)
C = Tvx^2 + Tvy^2 + Tvz^2 + (Tpx * Tax) + (Tpy * Tay) + (Tpz * Taz) - (Tax * Bpx) - (Tay * Bpy) - (Taz * Bpz) - Bs^2
D = 2 * ((Tpx * Tvx) + (Tpy * Tvy) + (Tpz * Tvz) - (Tvx * Bpx) - (Tvy * Bpy) - (Tvz * Bpz))
F = Tpx^2 + Tpy^2 + Tpz^2 - Bpx^2 - Bpy^2 - Bpz^2 - (2 * ((Tpx * Bpx) + (Tpy * Bpy) + (Tpz * Bpz)))

Now I put the equation (1) on an oline solver in:
http://www.quickmath.com/webMathematica3/quickmath/page.jsp?s1=equations&s2=solve&s3=basic

and solved it for t, but the results are just obscene. You'll have to replace and maybe simplify if possible. I have no time to that now. You'll have to take wathever result is real and positive, if none is then the bullet can't reach the target.