Wednesday, 30 June 2010

Keyframe madness

Behold, the promised post! It promises promising developments, developments which seek to fulfil the promise of a promising new keyframe system. There we go, now the word 'promise' looks strange to me. If it doesn't to you, try re-reading the last two sentences again. It's a pretty silly word, isn't it? But I digress.

You may recall from the last post that I've been working on a brand new keyframing system for PyIgnition. Indeed, the more astute amongst you may recall from the above paragraph that developments of a promising nature have occurred in the aforementioned area. Well, I'm glad to say that both observations are indeed in line with the most glorious reality about to unfold before you. That is, the new keyframe system is fully implemented and working rather well.

However, the coding process most certainly hasn't been without challenge. Indeed, it was rather horrific. Essentially, the new keyframe system introduced a somewhat more complicated InterpolateKeyFrames() function which took a little bit longer to complete. Shouldn't really be a problem, no? Well, when this function is running every frame on several hundred particles, each with several keyframes and variables to loop through, the slight difference becomes a seriously massive difference. As a result, even the simplest of scripts like the original fire demo would grind to a near-halt within seconds. And unfortunately no amount of ridiculous over-optimisation of the interpolation function yielded any real improvement.

But wait! All is not lost! For once all hope seemed to have dropped away (much like PyIgnition's frame rates), a guiding light of truth shone through the muck of malformed code and illuminated a speedy solution, bright and gleaming, the Excalibur of my code. Well, to be fair it wasn't quite as romanticised as that. In reality I spent many an age trawling the web for better ways to interpolate between frames, whilst simultaneously trying every optimisation technique I could find on the existing code - literally to the point of trying to use local variables over global variables because they're apparently faster, and avoiding using object.function() (preferring a simple function() ) because it's supposedly slower. The latter saw no avail, regrettably, but the former took me on a most interesting tour of the interwebs. And, I'm pleased to say, I came upon a solution!

You see, the particles belonging to one source are all spawned with exactly the same keyframes - so the same interpolation calculations are being done for every particle, just at different times. This is obviously wasteful. So instead of doing these same calculations, every single time, the program now pre-calculates what the variables of a particle should be for every frame of its life and saves them all to a big old lookup-table-esque array thing. This is stored in the particle source object, and is accessed from created particles through a reference to their parent source. When a particle keyframe is created with the source via the CreateParticleKeyframe() method, the source immediately updates this lookup-table-esque array using its PreCalculateParticles() function.

You'll probably have noticed that there's a definite space-time tradeoff here. Obviously the particle keyframes no longer pose any problems whatsoever, as the particle update method now simply sets each of the particle's variables to the ones stored by the parent source for the current frame. This means that the program is now actually slightly faster than it was before the new system was implemented. However, the thought of storing every variable for every frame of a particle's life is slightly unnerving, as one would assume that it would mean massive memory consumption. However, this is actually not as significant as you might think.

Here's an example. We have a fairly typical particle effect with keyframed particles, which emits 20 particles per frame with a particle lifespan of 600 (both of these are probably larger than you'd ever need to use in practice, but I'm using exceptionally large values just to show how little memory the particle caching actually requires). Now, at present, a particle object can keyframe the following variables:

  • colour - 3*int = 12 bytes
  • radius - 1*float = 8 bytes
  • length - 1*float = 8 bytes

This gives us a total size of 28 bytes for a single set of stored variables. Now, I haven't the foggiest idea how Python stores dictionary objects (which is how these variables are stored in the lookup-table-esque array thing), so just for laughs we'll double this value to 56 bytes, a size it will probably not come close to reaching in reality. Again, this is just to show how little space it actually requires. So, to store keyframed values for every frame of a particle's life, we would need to store 600 of these variable sets. That gives us a final memory usage of 33, 600 bytes or 33.6 kilobytes. Not bad for an overly large value you're unlikely to ever reach in practice, eh? So really, all things considered, this business of pre-calculating keyframed particles is almost certainly the way forward. It's definitely made things run faster anyway.

And that's where I am now. Well, actually, I also added setter methods for keyframeable variables - simply setting them in the 'object.variable = newvalue' fashion simply won't work now as it would be overridden by keyframe interpolation, so you would now use 'object.SetVariable(newvalue)', which creates a keyframe for 'variable' at the supplied value on the current frame. Next up is giving the user the opportunity to select interpolation modes (followed by a bit of bugfixing of course), and the next release - which has been upgraded to Beta 1, incidentally - will be ready!

No comments:

Post a Comment