Dirty Rectangles

Question

Where may one find references on implementing an algorithm for calculating a "dirty rectangle" for minimizing frame buffer updates? A display model that permits arbitrary edits and computes the minimal set of "bit blit" operations required to update the display.

Answer 1

To build the smallest rectangle that contains all the areas that need to be repainted:

• Start with a blank area (perhaps a rectangle set to 0,0,0,0 - something you can detect as 'no update required')

For each dirty area added:

• Normalize the new area (i.e. ensure that left is less than right, top less than bottom)
• If the dirty rectangle is currently empty, set it to the supplied area
• Otherwise, set the left and top co-ordinates of the dirty rectangle to the smallest of {dirty,new}, and the right and bottom co-ordinates to the largest of {dirty,new}.

Windows, at least, maintains an update region of the changes that it's been informed of, and any repainting that needs to be done due to the window being obscured and revealed. A region is an object that is made up of many possibly discontinuous rectangles, polygons and ellipses. You tell Windows about a part of the screen that needs to be repainted by calling InvalidateRect - there is also an InvalidateRgn function for more complicated areas. If you choose to do some painting before the next WM_PAINT message arrives, and you want to exclude that from the dirty area, there are ValidateRect and ValidateRgn functions.

When you start painting with BeginPaint, you supply a PAINTSTRUCT that Windows fills with information about what needs to be painted. One of the members is the smallest rectangle that contains the invalid region. You can get the region itself using GetUpdateRgn (you must call this before BeginPaint, because BeginPaint marks the whole window as valid) if you want to minimize drawing when there are multiple small invalid areas.

I would assume that, as minimizing drawing was important on the Mac and on X when those environments were originally written, there are equivalent mechanisms for maintaining an update region.

Answer 2

What language are you using? In Python, Pygame can do this for you. Use the RenderUpdates Group and some Sprite objects with image and rect attributes.

For example:

#!/usr/bin/env python
import pygame

class DirtyRectSprite(pygame.sprite.Sprite):
    """Sprite with image and rect attributes."""
    def __init__(self, some_image, *groups):
        pygame.sprite.Sprite.__init__(self, *groups)
        self.image = pygame.image.load(some_image).convert()
        self.rect = self.image.get_rect()
    def update(self):
        pass #do something here

def main():
    screen = pygame.display.set_mode((640, 480))
    background = pygame.image.load(open("some_bg_image.png")).convert()
    render_group = pygame.sprite.RenderUpdates()
    dirty_rect_sprite = DirtyRectSprite(open("some_image.png"))
    render_group.add(dirty_rect_sprite)

    while True:
        dirty_rect_sprite.update()
        render_group.clear(screen, background)
        pygame.display.update(render_group.draw(screen))

If you're not using Python+Pygame, here's what I would do:

• Make a Sprite class that's update(), move() etc. method sets a "dirty" flag.
• Keep a rect for each sprite
• If your API supports updating a list of rects, use that on the list of rects whose sprites are dirty. In SDL, this is SDL_UpdateRects.
• If your API doesn't support updating a list of rects (I've never had the chance to use anything besides SDL so I wouldn't know), test to see if it's quicker to call the blit function multiple times or once with a big rect. I doubt that any API would be faster using one big rect, but again, I haven't used anything besides SDL.

Answer 3

It sounds like what you need is a bounding box for each shape that you're rendering to the screen. Remember that a bounding box of a polygon can be defined as a "lower left" (the minimum point) and an "upper right" (the maximum point). That is, the x-component of the minimum point is defined as the minimum of all the x-components of each point in a polygon. Use the same methodology for the y-component (in the case of 2D) and the maximal point of the bounding box.

If it's sufficient to have a bounding box (aka "dirty rectangle") per polygon, you're done. If you need an overall composite bounding box, the same algorithm applies, except you can just populate a single box with minimal and maximal points.

Now, if you're doing all this in Java, you can get your bounding box for an Area (which you can construct from any Shape) directly by using the getBound2D() method.

Answer 4

I just recently wrote a Delphi class to calculate the difference rectangles of two images and was quite suprised by how fast it ran - fast enough to run in a short timer and after mouse/keyboard messages for recording screen activity.

The step by step gist of how it works is by:

1. Sub-dividing the image into logical 12x12 by rectangles.

2. Looping through each pixel and if there's a difference then I tell the sub-rectangle which the pixel belongs to that there's a difference in one of it's pixels and where.

3. Each sub-rectangle remembers the co-ordinates of it's own left-most, top-most, right-most and bottom-most difference.

4. Once all the differences have been found, I loop through all the sub-rectangles that have differences and form bigger rectangles out of them if they are next to each other and use the left-most, top-most, right-most and bottom-most differences of those sub-rectangles to make actual difference rectangles I use.

This seems to work quite well for me. If you haven't already implemented your own solution, let me know and I'll email you my code if you like. Also as of now, I'm a new user of StackOverflow so if you appreciate my answer then please vote it up. :)