Errol_Summerlin wrote:But you're only thinking about the fastest simulation bin; or are you saying that a unit simulated every 8 seconds would compute frames 8 seconds ahead?
(This might be okay, as long as collisions are computed as often and as interpolated as necessary... just asking.)
That is the idea. When a collision occurs, you would need to stop both objects along their interpolated path and compute the effects of the collision.
Gottcha.
Same goes for any changes by the AI: If the AI was turning to the right, and it now decides to nose-up instead, it will have to notify the physics to please reschedule the unit as to simulate the next frame ASAP.
And I haven't delved into the multiplayer code; but probably the server is trying to predict players' positions, to compensate for internet lag, and to reduce bandwidth; and probably the same applies when user input changes (--i.e.: probably clients only send packets to the server about user input, and only when it changes; and the server would simulate their trajectories, and should switch to fast stepping after it receives a packet for a unit, then slow down the simulation steps; but I'm just guessing).
So, we're back to interpolating two data points, with the benefit of knowing position, speed and acceleration for each; not sure what's a good algorithm to use.
You have 3 options. I tried to explain them in this thread, but I get the feeling everybody skimmed over the math
, so here is the summary:
x0, v0, and a0 are position, velocity, and acceleration at the "previous" state(I heartily approve of the renaming. I was thinking exactly the same thing), and x1, v1, and a1 are position, velocity, and acceleration in the previous state. dt=t1-t0 where t1 is time at the "next" state and t0 is the time associated with the "previous" state. The time elapsed since t0 is given by t
Option 1: Linear interpolation
x=x0+t*(-x0 + x1)/dt
v will appear to be constant over the interval
a will appear to be zero over the interval
Note that when t=dt, the object should be at the "next" position, and if you plug it in in the above equation, you will see that this is the case.
Option 2: Cubic interpolation
C1=(-2*(2*dt*v0 + dt*v1 + 3*x0 - 3*x1))/Power(dt,2)
C2=(6*(dt*v0 + dt*v1 + 2*x0 - 2*x1))/Power(dt,3)
x=x0+v0*t+C1*t^2+C2*t^3
v=v0+2*C1*t+3*C2*t^2
a=2*C1+6*C2*t
Note that when t=dt, x=x1 and v=v1, but a!=a1
Option 3: 5th order interpolation
C1=(-3*(3*a0*Power(dt,2) - a1*Power(dt,2) + 12*dt*v0 + 8*dt*v1 + 20*x0 -
20*x1))/Power(dt,3)
C2=(12*(3*a0*Power(dt,2) - 2*a1*Power(dt,2) + 16*dt*v0 + 14*dt*v1 + 30*x0 -
30*x1))/Power(dt,4)
C3=(-60*(a0*Power(dt,2) - a1*Power(dt,2) + 6*dt*v0 + 6*dt*v1 + 12*x0 -
12*x1))/Power(dt,5)
x=x0+v0*t+.5*a0*t^2+C1*t^3+C2*t^4+C3*t^5
v=v0+a0*t+3*C1*t^2+4*C2*t^3+5*C3*t^4
a=a0+6*C1*t+12*C2*t^2+20*C2*t^3
Note that when t=dt, x=x1,v=v1, and a=a1
You CAN get quadratic and quartic solutions, but you have to give up one of your endpoint matching requirements from the cubic and 5th order interpolations respectively.
EDIT: For what its worth, I strongly recommend having all three interpolation routines available, but I think that cubic interpolation gives you a good mix of smoothness with small computational expense. Remember the constants C1, C2, and C3 need only be calculated once per physics step. Things with small physics step will probably be better off with linear interpolation since computing C1 and C2 for the cubic could get computationally expensive with a small physics step. However, things with big physics steps will probably want a better interpolation to keep their trajectory looking smooth.
Great stuff!
Yeah, at first glance, the cubic stepping looks the most tempting.
By the way, for interpolation purposes, we only need to interpolate position, so it boils down to,
C1=(-2*(2*dt*v0 + dt*v1 + 3*x0 - 3*x1))/Power(dt,2)
C2=(6*(dt*v0 + dt*v1 + 2*x0 - 2*x1))/Power(dt,3)
x=x0+v0*t+C1*t^2+C2*t^3
<finito>
Well, we'll need to interpolate velocity when a collision occurs.
And as you say, C1 and C2 are per-physics-step, so the only interpolation code is,
x=x0+v0*t+C1*t^2+C2*t^3
EUREKA!
We don't need to keep around the previous physics frame, then; what we need is a new struct to which we only copy X0 and V0, and compute C1 and C2.
In fact, we may not even need the two frames we got now, if we use a different structure for output... (I need to check the rk4 code to see if there would be any aliasing problems reading from, and writing to, the same state) ...though we will need two ouput structures and a flipper flag, for concurrent update/use from separate threads (namely the graphics thread, as I think collisions will be in the same thread as physics). ((On the other hand, if we unify interpolations for collisions AND graphics, then we have no concurrency requirements for this structure. The way this would work is, we get a display list from the graphics thread, periodically updated. Then, whenever we compute interpolations for collisions, we add to our list of units to interpolate the list from the graphics thread, IF the time to the next graphics frame is near. If we do this, then it is the list of final, interpolated positions that would have concurrency requirements.))
..........
Anyway, both algorithms are in EJphysics.h. I would use rk4 for most objects and just make their physics time step bigger if you don't need that much accuracy or their acceleration vectors are slowly varying. I have not tested it to be sure, but if my ballpark calculations are correct, rk4 should be able to do track the trajectory of a planet like earth with a 1 day time step without any noticeable decay over at least 100 orbits (years).
I'm beginning to think I'd better change my scheduler code to have 16 simulation frequency bins, then, instead of 8. With 8 bins I only have steps from 1/16th of a second to 8 seconds. With another 8 we could have up to a little over one hour per step.
I don't think having steps longer than an hour would make any difference in terms of computational load, but I could be wrong... If we do want to have younger stars with proto-planetary disks, with all planetessimals simulated, as I think Klauss hinted at, then for sure; but then I'm not sure where the initial conditions for such a vast and chaotic set of objects would come from.
Hmmm, I just thought of something. It may be a good idea to have the interpolated position of an object handy in addition to its "previous" and "next" positions. The reason is as follows. Imagine a planet going on a 1-day physics time step and using cubic interpolation. It is near the end of the planet's physics step when a player flies nearby where the planet used to be nearly 1 day ago. Earth's orbital speed is 30 km/s. Even 1 hour ago, that is 108000 km away from where the planet currently sits. However, when the player's ship calculates the force on it due to nearby gravitational objects, it needs to make sure it grabs the most recently interpolated position of the planet rather than its previous or next state. Otherwise, the player's ship will experience gravity due to an object that is not there anymore.
WOW. power( Indeed!, 77.7 )...
(Another factor probably we all tend to forget is that in vegastrike, all speed vectors are "absolute" (relative to the local star), so even for two units of low speeds relative to each other, simulation steps may involve very long travel distances for both. We'll eventually going to have to bite the bullet and implement local, moving frames of reference; but that's going to be a real code challenge.)
Ouch...
You know what this implies?
I'm thinking it implies interpolations for *everything* all the time.
You see, in my mind, we were only going to interpolate units we needed to interpolate, at any given time.
That would have included,
- a) Units that need interpolation for collisions, which is a small subset, at each basic step, because the first layer or two of the collisions filter are predictive eliminators: Namely, if something is too far from any other units, it says "I won't be colliding with anything for at least 6 seconds, so check with me again then."
- b) Units that need interpolation for display, which is also a small subset because it ignores firstly all units outside the visual frustrum, and secondly it elliminates possibly all units whose | velocity - player_velocity | * physics_dt / distance < ~ 0.5 * sin( 1 pixel width view angle ).
Well, no big deal; what it implies is adding all gravitational attractors (units of mass > some_mass_TBD), which will probably add maybe a a couple of dozen units to the interpolation list, unconditionally; but that's nothing to write home about. What IS worth writing home about is the fact that physics will have to check this "current" interpolation data, which I'm not sure if it's synchronous or asynchronous...
Well, I think this settles the question, and interpolations will HAVE TO be in the same thread as physics and collisions.
I'm a bit worried that, in time, we're going to keep discovering other cases needing interpolations...
Once we implement more sophisticated sensors, for instance, a small ship 100,000 km away would, according to physics and graphics requirements, only need one physics step every 8-seconds, and no interpolations at all, ever; BUT, if we have a very sensitive heat sensor, that same ship, when it turns such that its engines are pointed towards us, should cause a momentary blip on our screens. But we wouldn't know its rotational position without interpolations.
Another example: Ships behind us may not need graphical interpolations as far as drawing them on the screen, but may need them as far as their blips on our sensors are concerned.
@errol: oh... now I get it. I indeed was thinking you were going to use <axis,angle> for state as well, hence the misunderstanding.
I hadn't even thought of the problem until chuck mentioned it to me, so I was just keeping the quaternions around. But that is how I "think" chuck intended to handle it as well. We don't exactly speak the same language all the time. I speak physicsease and he speaks computerease
I'm not sure what I was thinking, either; or IF I was thinking; can't remember.
I think I'm thinking now, though: Angle and axis is what we need for rotational position, IF we want to interpolate. But for
rotational speed and acceleration we could continue to use quaternions, I suppose; though I'm not sure I understand how the math for expressing rotational speed with quaternions works... Do we have the same problem with having a rotational speed limit beyond which it would have to become a non-unit quaternion or something?
Furthermore, if we're going to do cubic interpolation, and for that we only need rotational X0, V0, C1 and C2, then might as well add these to the output struct; so,
Code: Select all
struct sim_output
{
vec3<double> X0, V0, C1, C2;
quat<double> rX0, rV0, rC1, rC2;
};
So, now the problem boils down to making sure that the formula,
rx=rx0+rv0*t+rC1*t^2+rC2*t^3
is implemented in such a way that it works when interpolated angles >> 360 deg.
EDIT:
Well, I guess with quaternions it would go something like,
t/=dt;
rx=rx0+rv0^t+rC1^(t^2)+rC2^(t^3)
If that's not possible, then maybe we'd have to,
Code: Select all
struct sim_output
{
vec3<double> X0, V0, C1, C2;
angle_n_axis rX0, rV0, rC1, rC2;
};