Enhanced Crowd Rendering
January 26, 2010Designing a new technique for Skinned Mesh Instancing that supports complex animation and uses less memory.
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*
Looks amazing and looks like the gameplay is, well present
looks like its gonna be incredible fun to pick up any item and just bludgeon the crap out of huge amounts of zombies.
Looking forward to the progress vids and updates in the coming months
Also as an afternote
the animations are fuckin awesome
Hehe, thanks Tim.
The characters and animations are just placeholders at this point, but I do really like how some of the zombie deaths turned out.
This is really just a basic hacked-together gameplay demo… There’s a lot of glitches to work out, physics to improve, and AI to add.
You are definitely making great progress. I visit this blog frequently because you always motivate me to push harder. I read an article “http://bphelpsdev.spaces.live.com/blog/cns!602815048C7B5C20!302.entry” that uses a very similar approach to crowd rendering. It has a nice sample too, if you haven’t already seen it.
Honestly, I think it would be hard for me to make a game like yours, because I would probably being playing it more than working on it.
Man, I can’t barely wait to playtest this.
Thank you Nelxon, I’m glad the blog is motivational; my dream would be to create something inspiring like “Shadow of the Colossus”, or “Out of this World” (AKA “Another World”).
Yeah, I do find myself wasting hours just chopping up zombies, my gf is always making fun of me for that
… it makes it hard to work, but is probably a sign I’m on the right track. 
That article you linked to is an XNA adaptation of the GPU Gems 3 technique I was referring to. It’s good for some things, but it has many limitations. I originally based my implementation on the exact sample you linked to, although at this point it’s been rewritten and redesigned.
Impressive and nice commentary on the tech behind the crowd rendering. Glad I stopped by to check the site. Looking forward to see how your project turns out and how it effect XBL Indie.
Hiah, i was looking at the new dock which seemed to update its self to the new uber cool version, and I noticed ‘Punk Software’ and was led here by curiosity
. Anyway, totally love the game and I will be passing the links, I live in the UK so excuse the pounds but, if you release this to steam or something or have a donation area for the game, when its released i will be buying it for £20, this game totally rocks! (I will be getting it for my 360 too 
) I cant wait for a release! 
Thanks Dany,
The price will be either $3 or $5 USD on Xbox Live Indie Games, not sure how the MS points translate into BP though. Those are the only two prices we can charge.
I was reading this article showing the statistics of sales on XBL indie. Made me wonder how well dead shift will do. I was really surprise by some of the numbers. Anyway, I thought it was interesting and that you would find it informative if you hadn’t already seen it.
http://www.gamerbytes.com/2010/01/indepth_xbox_live_indie_games.php
Jazz,
I haven’t seen that particular article, but I did read the original data. It’s quite exciting to know that it is possible to do very well on the Indie Games channel, but on the other hand a top 10/20 list isn’t going to tell you anything about the average game that may only sell 50 copies.
That said, I think we have a better-than-average chance at doing well w/ Dead Shift… that is of course if I can actually finish the game w/ decent play control and a fair amount of polish.
Well I will definitely be buying this and telling everyone I know to get it when it comes out cause we’ve gotta fuel games like yours so we can set the standards for indie games higher.
And I like your reference to shadow of the colossus, the best game I never played. The first game I read the tech documentation for. Their “inverse kinetics” for the colossi seems similar to what you’ve done for the zombies. The death at the end is awesome how he goes for support on each leg and eventually drops like a sack of bricks. The tech behind that game is so amazing
Thanks Tim!
It really makes my day to hear people are excited about the game!
I actually don’t have any Inverse Kinematics yet, but I plan on using a really nice faked IK trick that will take full advantage of this new crowd rendering technique. It works by blending multiple animations like WalkingForward with WalkingDowhill based on the slope of terrain. That would be efficient enough to have zombies using it. But we’ll see if it’s even needed
Oh, okay but i do recommend a way to donate, and GBP and USD are roughly the same at the minute and I like the idea, you have some good physics and the sandbox style is extremely appealing. I’m quite amazed at what you’ve done already, keep up the good work, when this is done it will be epic!
Thanks Dany007!
Maybe I’ll make the PC port donationware, and that way anyone can donate if they wish.
Writing a physics engine was a real nightmare, and it still needs lots of work! *uggg*… It’s a huge relief to hear you like the style; I scrapped months of previous work to redo the physics to allow for the whole open world thing… Just wait until you see the vehicles!
I really hope I can finish some kind of demo in time for Dream-Build-Play, but March is coming up really fast.
Hi! I have been thinking that the indie games channel would be a great distribution platform for episodic content. If you can create 3 decent levels, then you could release them all for 80 points each, spaced a few weeks apart. I think you might get more sales this way since 80 points is an easier buy than 240.
WooooW!! It really looks great :O
AMAZING
Ill buy it
@Ben
That could work except that it’s going to be a struggle to even fit the game under the 150mb limit, and your game must be under just 50mb in order to charge 80 points.
I’m just hoping I can make something fun/quality enough that people compare it to higher priced XBLA games, instead of $1 massage apps.
@BARKtothePEOPLE
Thank you.
lol, come on now. There hasn’t been a massage app released for months!! I forgot about that 50mb for 80 points limit though. How about this though, adding in a sandbox/arena for two people to hack some zombies over Xbox live?
I was only kidding about the massage app, but it’s still a valid point. Sometimes if you completely devalue your software, it can work against you.
I want the game, or at least a sequel, to have coop and multiplayer modes… but I’ve already taken on a bit more than one person probably should. So we’ll see.
I think massage app is a bit of metonymy,
when you say something is a massage app your saying its a piece of crap
or more elegantly put, its shovelware programmed in a presumably short amount of time, thrown onto the indie games section to see if they cant pull in a couple bucks.
Im working on my own 3d physics engine now as well
Ive just about finished implementing separating plane theorem for mesh collision
Its the only idea I can really grasp in 3d collision
@Tim
‘Shovelware’, that’s the word I was looking for!
Good luck with the physics engine, I had an impossible time w/ OBB->OBB and OBB->Poly collision. *uggg*
I got only one word…
WOW!
Hey poly. Well march is finally here. Was wondering how your project was comin along.
@Jazz
Well I’ve done some work improving the SSAO and other random things… I’m considering switching to a Light Pre-Pass Renderer instead of the purely Deferred Renderer I have now… If I can’t cut down on video bandwidth, I might have to lower the resolution to 480p which I’d rather not do…
I wish I could say I’ve gotten much more work done, but real life has been getting in the way lately.
Edit: The “Light Pre-Pass” technique doesn’t look like it’s going to help my situation… time to do some research, fun fun.
Have you thought about throwing anything up onto the channel and asking people to donate to a future project, seems to be in vogue currently.
@Ben
You mean like Overgrowth by Wolfire Games? I do think that’s a brilliant idea, but I’m set for funding at the moment… My problem is really lack of game development experience and brainpower.
Things have been a little hectic this month, but development is going to pick up steam soon… No worries
Hey PolyVector,
Just wanted to let you I added you to my XDSK, XNA Developer’s Survival Kit.
http://www.nelxon.com/journal/entry-1002/xdsk/
It basically a list of resources, articles and blogs to help developers produce better games.
You may find something there you can use as well. Looking forward to your next update.
@Nelxon
Thank you for including me, that looks like an amazing resource! *Bookmarking*
Good luck ! (and don’t forget rocket dock)
Hey, i got an awesome idea for you!
What about adding an ability to combine items how you like, as it should not be that hard to do!
lets take this as an example…
-You have Hammer, plank and nails in your inventory, craft them into nail board! (This is how many games crafting mechanic works!)
But why not to take it to the next level?
EXAMPLE!
-You have Golf club, Duct tape and chainsaw in your inventory, when in crafting mode small window would appear where you could place the chainsaw golf club anywhere you want and press (BUTTON HERE!) to attach the 2 weapons.
It wouldnt be too hard to create, as it would be only combining 2 or 3 weapons into one, and all the parts would have their own places, that touch the zombie with enough force = Death, decap etc…
This is just my idea, but would love to see this in the game, as i havent seen any game (Other than gmod [Duhh!]) have the weapon attaching!
I hope this helps you to bring new idea to the game, and i hope this gets implented somehow atleast to the game!
Keep the steady update flow coming!
@Jesse
My original plan for the game involved crazier weapon combining than that! I actually planned on having weapons attachable to things like vehicles/shopping carts/etc… But then it was announced that Dead Rising 2 would have this type of functionality… so…
I may still attempt it, but it’s no longer an original idea unfortunately… :/
But don’t worry, I have plenty of original play mechanic ideas I’m brewing up… My bigger problem is getting the engine/artwork/game to a playable point first!
Sorry the updates have slowed down, real life has been intervening. Maybe I’ll post an update so everyone knows we’re still alive/undead and working on the game.
Actually, I was thinking more along the lines of creating some type of stunt race course where you drive around and run over zombies. If you could get that up under 50 megs I would definitely pay 80 MS points for it!!
@Ben
Oh, you meant actually create a mini game to fund the larger game’s dev. That could work, I do plan on releasing mini games eventually… We’ll have to see how long it takes me to even get a fully playable demo of anything. There’s too many collision/physics/art/performance issues at the moment to just rush something out. I want to release games I’m proud of.
Sounds good, I’m all for taking the time to release quality. Please do consider uploading test builds to,
http://www.xblig.co.uk/forums/index.php
I think your game could be the one that draws more people to the press A forums. With a playable demo, I think you could even ask for donations. Bypassing the marketplace if you wish. I don’t know if you’re down for that sort of thing but it is a possibility.
@Ben
It’s worth considering, there’s also this site and the playtest area of CCO.
Really cool, I’m trying to implement the same kind of thing based on the Gems 3, however implementing shader instancing is a pain. The InstanceSkinnedModelMesh.cs is killing me, would you mind posting the ReplicateVertexData method
?
@David
My version is mixed up in a ShapeBuilder class, but I actually learned from this sample: (if I remember correctly)
http://creators.xna.com/en-US/sample/meshinstancing
I’ll have a look at that, looks promising Thank you
Firstly, you’re awesome (and inspiring). Secondly, dual quaternions?! Really?! That’s hardcore. Why didn’t you go with quaternion(rotation)/vector(translation) out of curiosity? Is it slower or less accurate? It’s certainly less confounding. This is a really clever technique to leverage the strength of the Xbox’s GPU and I’d like to say thanks for sharing. I think I understand it except for the Animation Processor Shader (most important part). My understanding: In its most basic form you read the relative bone position for current bone for the current frame and read that bone’s parent index so you can read the parent bones relative position. You multiply this bone matrix and its parent bone’s matrix to get it’s absolute transform.
How do you ensure that the tree is traversed appropriately (ie root, child of root, child of child of root)?
Then you read the bone’s inverse bind pose matrix and multiply it by it’s absolute transform. Then spit out this matrix to three rendertargets.
How are you calculating over 200 animations in one draw call. Is the current frame index for each instance being written to a dynamic vertex buffer or shader contant array? I’m soo confused. Help me (so I can ask you more questions).
PS I love you.
@T
Thank you.
You actually have me second guessing the Dual Quaternion thing… I believe I was using them because they’re easy to lerp, but I switched to them from matrices quite a while back when I was much newer to 3d programming (not that I’m an expert now)… So perhaps their use is unfounded… They are quite expensive to convert back into a matrix, but that only happens once per processed bone…, hrmmmmm….. Now I’m going to have to rethink them.
It sounds like you understand what I’m doing, except I’m traversing the tree in the reverse order CurrentBone->Parent->Parent->Parent until I hit root, this makes it much simpler.
I’m using a shader constant array and a modified “Fullscreen Quad” that’s now more of a “Partial-screen Quad” The instance is determined by Texel.Y, and the bone by the Texel.X.
Correction: The DualQuat gets converted to a Matrix once for each recursion through to the Parent… The DualQuats are used to tween/blend animations, then the final matrix is used to adjust for the parent… Since there’s so much math, I decided to have a hand at optimizing the conversion function and managed to eliminate 23 multiplications on top of my old optimizations that cut out 11!… So the function now uses 34 less multiplication instructions than the example I based it on. Here’s the crazy-optimized code, maybe someone has a clever way of optimizing it further?
float4x4 DualQuatToMatrix(float2x4 dQ)
{
float4 Qn = dQ[0];
float4 Qd = dQ[1];
Matrix M = 0;
//Qn Squared…
float4 Qn2 = Qn * Qn;
M[0][0] = Qn2.w + Qn2.x – Qn2.y – Qn2.z;
M[1][1] = Qn2.w + Qn2.y – Qn2.x – Qn2.z;
M[2][2] = Qn2.w + Qn2.z – Qn2.x – Qn2.y;
//x*y, y*z, z*w, w*x…
float4 Qn2_1 = Qn * Qn.yzwx;
M[0][1] = Qn2_1.x + Qn2_1.z;
M[1][0] = Qn2_1.x – Qn2_1.z;
M[1][2] = Qn2_1.y + Qn2_1.w;
M[2][1] = Qn2_1.y – Qn2_1.w;
//x*z, y*w, z*x, w*y…
float4 Qn2_2 = Qn * Qn.zwxy;
M[0][2] = Qn2_2.x – Qn2_2.y;
M[2][0] = Qn2_2.x + Qn2_2.y;
float4 Qdx_X_Qn = Qn * Qd.x;
float4 Qdy_X_Qn = Qn * Qd.y;
float4 Qdz_X_Qn = Qn * Qd.z;
float4 Qdw_X_Qn = Qn * Qd.w;
M[3][0] = Qdx_X_Qn.w – Qdy_X_Qn.z + Qdz_X_Qn.y – Qdw_X_Qn.x;
M[3][1] = Qdx_X_Qn.z – Qdz_X_Qn.x + Qdy_X_Qn.w – Qdw_X_Qn.y;
M[3][2] = Qdy_X_Qn.x + Qdz_X_Qn.w – Qdx_X_Qn.y – Qdw_X_Qn.z;
//Batch all the various 2x’s here to save instructions
M[0] *= float4(1, 2, 2, 1);
M[1] *= float4(2, 1, 2, 1);
M[2] *= float4(2, 2, 1, 1);
M[3] *= float4(2, 2, 2, 1);
float len2 = dot(Qn, Qn);
M[3][3] = len2;
M /= len2;
return M;
}
the MS points to US currency is simple
80 Points = $1