Sunday, August 29, 2010

Animating the Canvas Part 2: Layers of Dirty Rectangles

Today I am going to look at layers and dirty rectangles. These techniques work really well together, though it is certainly possible to use layers without using dirty rectangles. Next week I will start implementing the animation system by getting some of the primitives out of the way and we will continue the implementation in the weeks following that.

Layers, when used in an animation system, can be thought of as cells as used by traditional film-based animation. Cell animation was developed as a way of drastically reducing the workload required to produce an animated sequence. The best way of explaining how, is to start with an example. Lets say we wanted a simple animated sequence consisting of two cars driving past each other on a street. If you had to draw each frame fully, then you would have to draw the background street, as well as both cars for every frame. If the background is not changing, then this is obviously a bit of a waste. In Cell animation, each element of the animation is drawn on it's own transparent sheet of celluloid and each of these sheets are then combined to form the frame which is then photographed.  Because the background doesn't change, it would only need to be drawn one time. If the celluloid sheets that the cars are on are large enough, even the number of car images can be reduced as the only thing changing are the tires.

Layers work the same way as cells. Each layer that makes up the frame is it's own separate image. The frame is created by simply drawing the layers from the background layer up. This is essentially the same thing as the painter's algorithm with the exception that the layers can change over time. Where this technique can become extremely powerful is when you add the concept of having layers being able to have their own sub-layers and sub-layers being able to have sub-sub-layers and so on. In our previous example, each car could have two layers with the tires being separate from the body of the car.

Looking at the above layering system for animating, we can see that layers do not help with the primary problem that was discussed in part 1. The layer system above would essentially require that we redraw the entire image for every frame. This is where dirty rectangles come into play.

What is this magical dirty rectangle? It is simply a rectangular section of the frame that has been marked as being dirty. In other words, it is a rectangle indicating a part of the frame that has changed and needs to be redrawn.  This very simple concept can save a vast amount of redrawing as the only thing that you need to draw each frame is the contents that make up the dirty rectangle(s).

There are a number of ways of implementing dirty rectangles. The easiest is to have a single dirty rectangle which scales itself to fit the entire dirty area of the image. This is very simple to implement but unless the changes to a display are constrained may result in having to redraw large chunks of the image. The approach I will be using will be a list of rectangles with subdivisions to remove any overlapping areas. This means that when something changes on the screen, that area gets marked as dirty. This gets added to the list of dirty rectangles. An object moving results in two dirty rectangles. One for the area where the object use to be and one for where the object is now.  When the display refreshes itself, each of these multiple small regions get redrawn. To prevent redrawing the same portion of the screen multiple times, dirty rectangles that overlap other dirty rectangles will be broken into smaller rectangles so that each dirty rectangle in the list covers a unique portion of the display reducing overdrawing.

That is all there is to it, at least concept wise. Implementing this system may be more complicated then the above makes it sound but then that is why programming is so much fun.


ejb said...

I'll be very interested in how your planning on implementing the 'dirty rect' technique. I'm creating a game/animation engine, and think this could greatly improve my fps. If you ever have some links to sources, your own or others, I would be interested in seeing them. I'm interested to see how things turn out.

Billy D. Spelchan said...

I am planning on posting the code as it is covered in the series. I am only posting once a week and there is a lot to cover so it will probably be 3 or 4 weeks until I get to the dirty rectangle handling part.