   Numerical integration and dense output for motion
  I'm playing with an idea that would let the physics engine I'm building use an adaptive time step, and I'm looking for some advice.Consider the picture below:The curve at the top represents some unknown function (ie: the position of a particle over time) during an epoch, which is a term I'm using to represent continuous motion (ie: before a collision would be one epoch, and after a collision is a new epoch).Using an adaptive time step algorithm and a numerical integrator (velocity verlet or Beeman's algorithm probably), I get discrete points at discrete times (the points in the middle of the picture).  At each point I have information on the position, velocity, and acceleration of the body at that point.Now I want to interpolate between the known states so I can find the state of the body at any arbitrary time.  That's the bottom row in the picture (linear interpolation in this case, but I'm aiming for higher).The trick here is that I no longer care about the actual "unknown" curve.  Whatever the interpolation I use becomes the actual motion of the body.  So choosing a good interpolation scheme is going to be very important.I'll use the interpolation to draw the bodies at specific frame times, and to check for collision times between bodies.  And I'll need the velocity too, so during a collision I can calculate resolution impulses.The first idea I had is rather naive.  Basically use the start and end position, velocity, and acceleration to form a 5th order spline between every point.  The upside is that I can be sure that not only are the positions and first and second derivatives continuous, but they actually agree with the integration.  The downside is that it's a higher order polynomial, and I hear they're bad for interpolation.Plus a 5th order polynomial is probably way more accurate than I really need.Linear is too coarse (the linearity would be evident as you watched the bodies move), so my current thinking is a quadratic curve for position, and a separate one for velocity.  The end point conditions are easy (position spline should start and end at the correct calculated values.  Likewise for velocity), but I'm having a hard time deciding on a third condition to form the full spline with.I could go up to a full cubic spline, and use the first derivative at either end point as the other two conditions, but quadratic splines have some nice properties for collision detection that I don't want to give up.So any thoughts anyone has would be appreciated.   
Quote:Original post by NumsgilLinear is too coarse (the linearity would be evident as you watched the bodies move), so my current thinking is a quadratic curve for position, and a separate one for velocity.Is this a problem that you anticipate, or one that you have really encountered? I've never been able to see any artifacts due to linearly interpolating between states in the Physics simulation. What is the largest time that you allow? Perhaps it's too large?   ;  One reason to choose a cubic spline comes from the principle of minimizing work in physics. If you do linear interpolation, that is equivalent to a series of impulses applied to the particle. A natural question is, if you apply a continuous force, can you get a particle to travel through the same points while doing less physical work (ie: use less energy), and if so, what path will it take?In other words, what function minimizes the path integral of the acceleration? The answer is actually a cubic spline, which can be seen using Lagrange multipliers. If you are interested in the math of it, you can read the paper here:http://www.springerlink.com/content/k37198281q833wl4/I'm not sure if anyone has applied the same sort of analysis to a function with known positions and velocities.   ;Quote:Original post by alvaroQuote:Original post by NumsgilLinear is too coarse (the linearity would be evident as you watched the bodies move), so my current thinking is a quadratic curve for position, and a separate one for velocity.Is this a problem that you anticipate, or one that you have really encountered? I've never been able to see any artifacts due to linearly interpolating between states in the Physics simulation. What is the largest time that you allow? Perhaps it's too large?The timestep can be quite large.  That's the whole point really.  It could be in the range of several seconds even.  If the acceleration is uniform (ie: ballistic motion), you can even take an arbitrarily large time step, since most integration schemes can calculate the exact motion of a particle under uniform acceleration (it's just the Taylor quadratic expansion).Speaking of constant acceleration, that's another reason why you need at least a quadratic.  Ballistic motion is common enough in physics engines that you really need an interpolation scheme which can handle it in a single piece.Quote:Original post by Maze MasterOne reason to choose a cubic spline comes from the principle of minimizing work in physics. If you do linear interpolation, that is equivalent to a series of impulses applied to the particle. A natural question is, if you apply a continuous force, can you get a particle to travel through the same points while doing less physical work (ie: use less energy), and if so, what path will it take?In other words, what function minimizes the path integral of the acceleration? The answer is actually a cubic spline, which can be seen using Lagrange multipliers. If you are interested in the math of it, you can read the paper here:http://www.springerlink.com/content/k37198281q833wl4/I'm not sure if anyone has applied the same sort of analysis to a function with known positions and velocities.Ah, that's very interesting, thanks for the link.   