aka. Misadventures In Implementing a Real Time Tree of Life Graph. Note: this post is a logical sequel to the previous post, though it also doubles as a what-not-to-do tutorial of sorts when it comes to implementing real time graphs and render targets in XNA. Fair warning: It’ll probably be a bit incomprehensible if you’re not a programmer.
/tangential progress report: we’re about 40% of the way to the alpha release deadline and about 50% of the way through the “list of crap to do”. So we’re ahead of schedule, but not by much.
It’s probably worth noting that part of the reason I’m cutting it so fine is micro-feature-creep. A major advantage of programming on your own is the ability to indulge your inner ADHD-sufferer: getting distracted by something that sounds like fun and wandering off to code it. Some of my favorite features in Species have come about via ooh-shiney moments like this, but it slows down my progress on the stuff I’d planned out in advance.
Okay, back to the topic…
I not-so-briefly touched upon my very first tree of life graphing attempt in the previous post. This image…
… shows the end result.
Frankly, it’s ugly. It’s barely recognisable as what it’s supposed to represent, and it’s a performance hazard. Each one of those bars is a seperate sprite representing the life-time of a creature, which means I’m calling DrawSprite() a couple thousand times every frame. This would be manageable if I stopped drawing the simulation in the background (a tactic I’m may have to adopt when I get around to trying out the life-web I mentioned last post), but because I was rendering it as an overlay this wasn’t something I spent much time considering.
The idea behind this graph was that it would show the culmative effect of population changes by displaying all the creatures lives at an individual level. Admittedly, it manages this to some extent, but it does so extremely poorly. The rapid movement to the right, for example: that’s not natural selection, that’s just the logical result of measuring mutation from the starting location. If you start a value at 1, and your children are 0.9 and 1.1, it doesn’t matter that they are going in opposite directions: they will both appear at 0.1 on the graph.
But as far as first attempts go, it taught me quite a bit about what I was trying to achieve. That’s the whole point of prototyping: try something, learn, then try it again using the information you’ve learned. In this case what I learned was that showing individual creature lives was too microscopic to paint a good long term picture. I was going to have to summarize, and for that I’d need to use the species and speciation tranking system… which, despite post order, I hadn’t implemented at this stage. The above graph was generated entirely from random colour changes and the genetic distance algorithm.
So I went and I implemented species and speciation tracking while researching and considering my next move. Surprisingly, for such a simple concept, there are a whole variety of ways to implement a real-time graph. I’ll get to those in a moment, but first: what I decided I wanted to achieve was a population tracking graph that would show the relative size of each species and the effects of speciation, so you could see whether the splintering population was a single sterile creature, or a large segment. It would also need to be able to dynamically move and re-arrange population lines, to keep them from overlapping and under-representing the total population. This… turned out to be more ambitious than I expected.
I narrowed it down to a number of ways to do this:
1. Brute force sprites: draw a lot of sprites to form the shapes you want. This was the method I’d used for the previous version, and despite my complaints, for that version it was actually feasable: the number of sprites involved aren’t a negligable performance hit by any means, but they’re manageable and they’re easy. But to do this for a graph that shows changing population size on a per-frame/per-pixel basis? On a modern monitor we’re talking about 1080 sprites, multiplied by the number of species shown. Not viable.
2. Vertex List: dynamically changing geometry to represent the shapes you want. I didn’t spend much time looking into this option, but it has a number of things going for it: dynamically re-arranging Species Lines would be easy to do. The biggest problem with it is the bottleneck between the GPU and CPU: dropping that much vertex data on the GPU every frame can’t be a small performance hit.
3. Shader Trickery: sending the raw population data to the GPU and having it do all the work in the pixel shader by, essentially, drawing the graph on a transparent slide right in front of the camera. This is probably one of the best options here: it defers a lot of work to the GPU, is easy to implement, and allows the things I wanted to do, but… older shaders can only handle so many variables as parameters (255 for shader model 3.0), which is nowhere near enough. The CPU-GPU bottleneck issue still exists, but Shader Parameters are designed to be modified on the fly in a way that Vertices aren’t, so it’s not as bad. If I was targetting a later shader model this would probably be my preferred option, but as it stands… no.
4. Colour Arrays: generate an array of Color objects, modify it directly every frame, then save it to a texture and render that texture to the screen. Similar to option 3, except done entirely on the CPU rather than the GPU. I actually tried this one out: turns out that for full-screen textures it leaves a pretty massive footprint on your performance.
5. Render Targets: Oh god.
I hate render targets. I’ve had several dealings with them in the past, and every time they’ve given me a whole new bunch of reasons to hate them. Render targets are evil. /title drop
Don’t get me wrong, Render Targets are a vital and powerful aspect of the XNA framework, and there’s no doubt we’d miss them if they weren’t there. But they’re still evil. I still have nightmares about debugging Render Target issues. (okay I don’t really, that was hyperbole. My nightmares are more only have ordinary everyday things, like giant zombie demon spiders with flamethrowers held in their pincers. Also, the moth. Everybody has nightmares about the moth right?)
The basic concept behind this approach is to render only the ‘front’ pixels of the graph, then move the entire thing 1 pixel along next frame and render the next set of ‘front’ pixels. For a single line graph, this means you only have to draw 2 sprites: 1 for the line and another for the entire graph that was rendered last frame. This is a very efficient way of doing things, with the disadvantage is that what is drawn is drawn. I can’t modify the graph later if I want to move population lines to the left or right in response to population pressure.
But you can’t just do this straight onto the screen: I’m rendering everything else onto the screen, so I don’t want to be moving all that one pixel to the left every frame. Just the graph. And that means render targets, which are basically extra screens that you can activate, draw stuff on (without overwriting anything else) and return to later. Sounds easy, right?
A few points about render targets, for XNA users who are interested in avoiding the same horrible spiky pitfalls I fell into, climbed out of, then tripped and fell into again:
1. A render target has to be removed from the device before you can retrieve the texture from it. Failing to do so causes an exception. To remove it, call GraphicsDevice.SetRenderTarget(0, null);
2. Switching to a render target, then switching back, has an unfortionate tendency to clear your screen to a certain shade of purple. There are reasons for this (mostly because XNA is designed to work with the XBox, which has it’s share of quirks), but I didn’t know them at the time. All I knew was “suddenly purple WTF?”. To avoid this, it’s necessary to render to any Render Targets’s before you draw anything to the backbuffer.
3. A render target cannot render it’s own texture. In order to do what I said before (render a texture, then move it one pixel to the left and render again) you actually need to switch back and forth each frame between two render targets.
4. A render target cannot be used to render to multiple textures. You’d think you’d be able to render an object, then copy the result into a Texture2D and render a new object. This is what I wanted to do with the population lines so I could move them left and right: draw each one seperately and move their parent sprites. Turns out no: copying the result into a Texture2D only copies a reference to the Render Targets texture, so when you render the next thing in the list you overwrite the earlier Texture2D.
5. There is apparently a limit to the number of render targets you can have, so you’re not allowed to render multiple seperate objects that way, either. It’s nothing concrete, but somewhere between 40 and 60 targets the program will start to glitch out. For me, the sky went white, the game briefly lagged, and then it crashed out with an incomprehensible exception. I have no idea why these were the symptoms of too many rendertargets: I choose to believe I’d accidentally imported an identical anti-matter universe into the game and everything except the earth exploded at once. The few seconds of lag were just waiting for the shockwave to hit.
So how can you render an unknown number of seperate objects, like population lines, into seperate textures? There’s only one way: use a single render target, and perform a deep copy of the Texture2D before you move onto the next object so you copy all the information of the object and not just it’s reference. So how do you perform a deep copy? SetData() and GetData(), two of the slowest texture related functions in the framework! As it turns out, this performance hit for an almost-full-screen graph was almost as bad as option 1, way up there earlier in this post. So that’s out too.
(It’s probably worth noting that this method, can be possible for smaller images, like 256×256 thumbnails, where there’s less data to copy. I still don’t recommend doing it more than once per frame, however)
Eventually I gave up and left the population lines alone. The current system lets them stay where they are, overlapping.
I’ll leave the fancy visual stuff to the proper phylogenetic tree, which won’t display population histories and will be implemented later WITHOUT RENDERTARGETS. SCREW RENDER TARGETS. (okay, maybe with one render target).
Apparently he hates rendertargets almost as much as he hates multithreadin-“
NO. YOU DO NOT SPEAK THAT WORD IN THIS HOUSE.