Enhanced Crowd Rendering

A fundamental challenge when designing a game centered around hordes of zombies is how to render a large quantity of animated characters.  A number of solutions exist, but none of them were quite suitable for Dead Shift.  In this post I will introduce a new(?) technique I’ve developed for skinned mesh instancing (aka. crowd rendering) that addresses many of the issues with the one proposed in GPU Gems 3 (and adapted for XNA), making it better suited for crowds of important characters who may require animation techniques such as motion blending.

To start, here is a quick overview of both techniques.

Original Technique:

• Bones are stored in absolute positions, so no blending is possible.
• Animations must be pre-baked at 30fps or 60fps resulting in large memory/storage requirements.
• Not suitable for rendering main characters, requiring a completely separate animation system for them!

My Enhanced Technique:

• Bones are stored in relative positions, along with skeletal hierarchy and bind-pos data needed to blend multiple frames/animations together at run-time.
• Animations can be pre-baked at lower framerates (15fps works nicely) which drastically lowers memory/storage requirements.
• Animation Processing is decoupled from Rendering, allowing arbitrarily complex blending/tweening routines on the GPU and re-use of processed frames between passes (ie. shadow-depth)
• Suitable for all characters in a game, unifying all animation into a single system.

The process for my technique is as follows:

• Pre-bake animations as usual with the GPU Gems 3 technique; output Relative Matrices, NOT Absolute Matrices.  We’ll refer to this as the “AnimationTexture”.
• Store the Inverse BindPos as a frame in AnimationTexture, you’ll need this at runtime.  I find it’s easy to place this at Frame 0.
• Store the Skeletal Hierarchy in a Texture for run-time access… This can be a separate texture, or simply packed into another dummy animation frame.  The important thing here is that we’ll need our shaders to be able to look up the Parent BoneIndex for any given BoneIndex…
• Write an “Animation Processor” shader that reads frames from AnimationTexture for each character instance and generates a new texture, we’ll call this “FinalAnimationTexture”, in the format of the original GPU Gems 3 technique. Each character will need to be assigned a RowID within this new FinalAnimationTexture to read their processed frame.  Hint: If you use Multiple Render Targets, you can spit out all 3 pixels of a bone matrix at once… This eliminates the need to process bones 3x.
• Render Characters as usual, the only difference being that characters reference RowID in FinalAnimationTexture, instead of FrameID in AnimationTexture…
• If bone data is required on the CPU, wait a frame and read it back.  I’ve found it far more efficient to first process all bone data we want to read back into a single texture to avoid multiple GPU to CPU transfers.

The beauty of this technique lies in the “Animation Processor” shader.  Because we don’t need a World Matrix at this stage, we can easily process over 200 character animations in a single draw call.  Also, nobody says you have to use a single “Animation Processor” shader, you could write any number of shaders for different types of animation such as Inverse Kinematics.  All animation frame data simply needs to be written to FinalAnimationTexture, so perform this step however you please.

Now, I’m far too lazy to draw diagrams, write sample code, and go into extreme detail… Sorry!… Feel free to ask questions if you’re interested, and I’ll do my best to answer!  I just wanted to put this idea out there for anyone struggling with a similar problem.

Some useful nuggets of information:

• In order to perfectly sync bones between the CPU and GPU without horribly stalling the GPU, you may have to use the processed animation data from 2-3 frames back (depending on your architecture).  This means double/triple/quadruple buffering FinalAnimationTexture and using outdated animation info to ensure, for example, that a weapon stays perfectly in a character’s hand.
• If you store your original AnimationTexture as Dual Quaternions (2 pixels per bone), it’s very easy to blend between frames/animations, and you use less memory.  The trick to interpolating dual quaternions is to compare them w/ a dot product and conditionally negate the second DualQuat to ensure blending moves in the right direction…  Interestingly, this step can be pre-computed at build time in the AnimationTexture so that any frame can be blindly lerp()’d with the following frame. *devious*