Dirty Rectangles Help?

[BantamCityGames]

Hi, my second game has alot of rendering and quite a bit of alpha-blending. The frame rate is starting to drop and I would like to implement dirty rectangle optimization. Does anyone have conceptual/technical articles on implementing this for a DirectDraw (2D/non-isometric/side-view) rendering system. I guess I understand the basics (only draw what has changed), but how do you detect what has changed? Can you do it at the renderer level and keep track of all the regions that have changed as you blit to them, or do you have to keep track of it in the sprite movement code? There are subtleties to this that I just haven't grasped yet, so any help would be great.

Also, are there any simple optimizations that have a greater bang-for-the-buck so to speak (something obvious I may have overlooked even)?

[ggambett]

If everything in your engine is sprite based, you do as follows :

- When you add a sprite, invalidate ("queue for redraw") the area occupied by the sprite
- When you delete a sprite, invalidate the area that was occupied by the sprite
- When you move a sprite, invalidate the old and new rectangles.

There are lots of possible optimizations. You may want to grab the background of the sprite before drawing it and restoring it when you delete it, instead of compositing the backround again. May be useful if you have lots of sprite layers and the moving sprites are usually the higher layer, for example.

Also look into micro tile arrays.

[Rod Hyde]

- When you add a sprite, invalidate ("queue for redraw") the area occupied by the sprite
- When you delete a sprite, invalidate the area that was occupied by the sprite
- When you move a sprite, invalidate the old and new rectangles.

- If you're double- or triple- buffering then you need to keep track of where the sprite was drawn when the frame was last active, as you'll need to invalidate that area if the sprite moved away from it.

--- Rod

[Mark Fassett]

The biggest optimization I made in my game, which used DDraw at the time and was only getting about 30fps, was to move away from DDraw and start using PTK. Gained 25-30fps just by switching.

[Diodor Bitan]

Original post by BantamCityGames
Can you do it at the renderer level and keep track of all the regions that have changed as you blit to them, or do you have to keep track of it in the sprite movement code? There are subtleties to this that I just haven't grasped yet, so any help would be great.

I have found I need two passes through the list of objects (one for calculating the dirty rectangles and one for the actual blitting). If a transparent sprite changes (because of movement or because it is an animated sprite), not only it must be redrawn, but the objects below it too. Because redrawing those could in turn cause other objects to be redrawn (and so forth) my system must support partial drawing for every graphical object. Also, I must make sure that no two dirty rectangles overlap, lest I end up drawing the same portion of one object twice (causing an annoying artifact if the object is transparent). This leads to a lot of troublesome rectangle intersection calculations, to ensure that all new dirty rectangles are broken up if they overlap old ones.

[BantamCityGames]

The biggest optimization I made in my game, which used DDraw at the time and was only getting about 30fps, was to move away from DDraw and start using PTK. Gained 25-30fps just by switching.

I thought about it early in my project, but decided not to for certain reasons. I almost wish I had though as it seems everyone's fps have gotten better.

[BantamCityGames]

- If you're double- or triple- buffering then you need to keep track of where the sprite was drawn when the frame was last active, as you'll need to invalidate that area if the sprite moved away from it.

--- Rod

Is there a standard technique to solve this problem or can you just keep a variable to tell you what frame you are drawing to?

This is even more complicated than I thought.

[Air]

This is even more complicated than I thought.Indeed. In my experience Dirty Rectangles are a complete waste of time except on the simplest of games. If your game is a side scroller (ie full updates to the background because it's moving) then forget it. If you use a lot of particle effects, then don't bother either. If you plan on using double or triple-buffering then don't bother.

I spent quite a lot of work impementing Dirty Rects for my game Chicken Little (a falling-blocks puzzle game) because I figured it would be a good thing. Even before I added any sort of particle effects or text overlays ("Good Job!" "Combo!" things like that), the speed increase was negligable. Once I factored in the option of double buffering and particle effects I realized that I was going to have to re-render 70-80% of the screen anyways-- in addition to a whole load of extra work required in maintaining the dirty rect lists.

So yeah. I sincerely think your efforts in optimizing your game could be put forth elsewhere with a lot more success. If your alpha blending is significantly slower than your regular blits (by more than 30-40%) then it sounds like to me you're doing most of your "work" in the primary ddraw surface (the one stored in video memory). The very best thing you can do to speed up your game is to create a secondary buffer in system ram and do all your game blitting to that, then copy the whole shabang over into video ram upon the completion of rendering each frame. Hope this helps.

- Air

[Rod Hyde]

Is there a standard technique to solve this problem or can you just keep a variable to tell you what frame you are drawing to?

This is even more complicated than I thought.
It is a very long time since I used the technique, so my memory is hazy and I don't have the code on the machine I'm using right now, but I only went as far as double-buffering. I basically kept track of the current frame. Each sprite stored two rectangles, one for where it was when frame 0 was last active and one for where it was when frame 1 was last active. Beyond that, my memory gets even hazier, but from what I recall I always cleared each sprite's old rectangle to background then re-drew each sprite regardless of whether it had changed or not, because doing anything cleverer than that became very complicated.

Rendering a frame looked something like this:
for each sprite:
clear its old rectangle to background
for each sprite:
draw it in its new positionWith a relatively small number of sprites compared to the size of the screen, this worked well. It didn't scale wonderfully, as there would be a point at which it became easier just to clear the buffer and draw all the sprites. With the advent of hardware acceleration, that became even more attractive ... and that's what I do now. PTK does an excellent job of making it easy.

--- Rod

[MiCo Games]

then copy the whole shabang over into video ram upon the completion of rendering each frame.

I've found that on fast CPUs, this step can take a long time compared to the rendering, because of the transfer speed from system to video memory.

A nice way to speed it up, if you're not redrawing the whole screen every frame, is to divide the screen into "dirty tiles" of suitable size. When a sprite change, it flags the affected tiles as dirty, but all the sprites are drawn. Then, instead of copy the whole buffer to video ram, you just copy all tiles that are flagged as dirty. Obviously, if you change so much stuff every frame that all tiles are flagged as dirty, then this technique will actually slow things down rather than speeding it up. And I would only recommend it if copying from system ram to videoram have definitely been identified as the bottleneck.

As always: never ever optimize without having run it through a profiler.

[Diodor Bitan]

Original post by Air
The very best thing you can do to speed up your game is to create a secondary buffer in system ram and do all your game blitting to that, then copy the whole shabang over into video ram upon the completion of rendering each frame.

Yeah, that's what I do, except I don't copy the whole shebang, just the dirty regions (SDL function SDL_UpdateRects). Basically, all I do is software rendering.

[BantamCityGames]

Currently I am drawing everything in system ram and copying to video ram only when done.

I am getting the feeling there are different views on Dirty Rectangles.
Some people say that if you have alot of things moving on the screen it will not save you much rendering time, but I remember a post on Dexterity by the programmer of Ricochet Lost Worlds (James C. [Something]) and he said that one of the most effective optimizations that he did was to implement dirty rectangles. Anyone that has played Ricochet Lost Worlds knows that there is ALOT of things moving around (foreground, background, effects). If what James says is true, than I have to imagine dirty rectangles would be helpful in quite a few circumstances.

Now that I hear all of your suggestions, I think the only part of dirty rects that would be difficult would be the problem of double buffering. Can someone explain in more detail how to make sure you are referencing the correct frame?

[Night Elf]

I remember a post on Dexterity by the programmer of Ricochet Lost Worlds (James C. [Something]) and he said that one of the most effective optimizations that he did was to implement dirty rectangles.

IIRC, he was talking about a software renderer they developed for Ricochet Lost Worlds. I think that dirty rects won't speed your DirectDraw game much. I guess there must be better optimizations you can implement before.

What is the number of sprites you're rendering? How many have alpha blending? What are your test system specs? What FPS count are you getting?

[BantamCityGames]

IIRC, he was talking about a software renderer they developed for Ricochet Lost Worlds. I think that dirty rects won't speed your DirectDraw game much. I guess there must be better optimizations you can implement before.

What is the number of sprites you're rendering? How many have alpha blending? What are your test system specs? What FPS count are you getting?

-The 800x600 background.
-The HUD. (not too big)
-About 65 sprites (not counting effects) with zero alpha blending.
-I also have particle effects which consists of a total of a couple hundred particles (tiny individual alpha rendered sprites). I realize this is part of the problem, but how else do you get convincing particle effects?

[MiCo Games]

Where is the most time spent? In drawing the effects, the sprites, or the background?

[BantamCityGames]

Where is the most time spent? In drawing the effects, the sprites, or the background?

I'm leaving for CT right now so I didn't have time to fully profile it, but I just ran a few quick fps tests and it looks like this (all performed independantly):

not rendering the background gave me about 25% increase in fps
not rendering the effects gave me about 20% increase in fps
not rendering the sprites gave me about 10% increase in fps
not rendering the HUD gave me less than 10% increase in fps

[DDustin]

It looks to me as if a dirty rectangle system would be wonderful for your project then, as it would avoid a complete redraw of the background each frame. Also I dont quite understand what you mean by double buffering being the hard part...

You need two bitmaps here, a 'buffer' and a 'background' bitmap. The drawing code for the program will draw to the 'buffer' and call a function to mark the modified dimensions. This function must store these coordinates in some type of vector / list, spliting the rectangle up into non-overlapping rectangles. The function to update the screen, needs two lists to share with the marking function, one list containing all the modified areas, and one list holding all the modified areas from last frame. The screen updating function must then combine the two lists (again checking for overlapping) and then draw those rectangles from the buffer to the screen. Then draw those same rectangles from the background to the buffer.

Sound complicated? It is. The hard part is not the double buffer though, the hard part is somehow dividing up the new rectangle into smaller ones so it doesnt overlap with other rectangles. If you dont do this part correctly, theres really no point and you should just go back to using a plain double buffer... (but dont go back that far, stick with page flipping, trible buffering or hardware scrolling. They perform much better)

As to the argument about the calculations required for dirty rectangles taking too long, its faster then sending big bitmaps to the video card. Thats the bottleneck dirty rectangles tries to beat.

[Nemesis]

I think that with all the present medium-to-highend graphics hardware designed to render 3d, it is no longer worth-while using dirty rectangles to render in 2D, in particular when using 3D cards for such purpose.

[James C. Smith]

For what it’s worth, Ricochet Lost Worlds is triple buffered (hardware page flipping with two back buffers and a front buffer) but does all drawing using software 2D blits. It uses direct rect to dramatically improve performance. You could also get performance from using 3D hardware blitting. But if you use software, and even if you are triply buffered, dirty rects help a lot. The most important factor is to limit how much is written across the AGP buss. You don’t want to copy the pixels that didn’t change and you never want to copy the same pixel twice. Some simplistic dirty rect approaches make the copy to screen slower because the do not properly handle overlapping sprites. You also never want to read from the back buffer. Therefore, if you are doing alpha blending, you should draw all your stuff into a system memory frame buffer first so all blending is done in system memory. Then copy the parts that change to the video back buffer. If you have multiple back buffers you will have to separately track what changed on each buffer.