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

Look into R-tree and quadtree data structures.

Answer 2

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 3

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 4

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 5

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. :)

Answer 6

Vexi is a reference implementation of this. The class is org.vexi.util.DirtyList (Apache License), and is used as part of production systems i.e. thoroughly tested, and is well commented.

A caveat, the currently class description is a bit inaccurate, "A general-purpose data structure for holding a list of rectangular regions that need to be repainted, with intelligent coalescing." Actually it does not currently do the coalescing. Therefore you can consider this a basic DirtyList implementation in that it only intersects dirty() requests to make sure there are no overlapping dirty regions.

The one nuance to this implementation is that, instead of using Rect or another similar region object, the regions are stored in an array of ints i.e. in blocks of 4 ints in a 1-dimensional array. This is done for run time efficiency although in retrospect I'm not sure whether there's much merit to this. (Yes, I implemented it.) It should be simple enough to substitute Rect for the array blocks in use.

The purpose of the class is to be fast. With Vexi, dirty may be called thousands of times per frame, so intersections of the dirty regions with the dirty request has to be as quick as possible. No more than 4 number comparisons are used to determine the relative position of two regions.

It is not entirely optimal due to the missing coalescing. Whilst it does ensure no overlaps between dirty/painted regions, you might end up with regions that line up and could be merged into a larger region - and therefore reducing the number of paint calls.

Code snippet. Full code online here.

public class DirtyList {

    /** The dirty regions (each one is an int[4]). */
    private int[] dirties = new int[10 * 4]; // gets grown dynamically

    /** The number of dirty regions */
    private int numdirties = 0;

    ...

    /** 
     *  Pseudonym for running a new dirty() request against the entire dirties list
     *  (x,y) represents the topleft coordinate and (w,h) the bottomright coordinate 
     */
    public final void dirty(int x, int y, int w, int h) { dirty(x, y, w, h, 0); }

    /** 
     *  Add a new rectangle to the dirty list; returns false if the
     *  region fell completely within an existing rectangle or set of
     *  rectangles (i.e. did not expand the dirty area)
     */
    private void dirty(int x, int y, int w, int h, int ind) {
        int _n;
        if (w<x || h<y) {
            return;
        }
        for (int i=ind; i<numdirties; i++) {
            _n = 4*i;
            // invalid dirties are marked with x=-1
            if (dirties[_n]<0) {
                continue;
            }

            int _x = dirties[_n];
            int _y = dirties[_n+1];
            int _w = dirties[_n+2];
            int _h = dirties[_n+3];

            if (x >= _w || y >= _h || w <= _x || h <= _y) {
                // new region is outside of existing region
                continue;
            }

            if (x < _x) {
                // new region starts to the left of existing region

                if (y < _y) {
                    // new region overlaps at least the top-left corner of existing region

                    if (w > _w) {
                        // new region overlaps entire width of existing region

                        if (h > _h) {
                            // new region contains existing region
                            dirties[_n] = -1;
                            continue;
                        }// else {
                        // new region contains top of existing region
                        dirties[_n+1] = h;
                        continue;

                    } else {
                        // new region overlaps to the left of existing region

                        if (h > _h) {
                            // new region contains left of existing region
                            dirties[_n] = w;
                            continue;
                        }// else {
                        // new region overlaps top-left corner of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(x, _y, _x, h, i+1);
                        return;

                    }
                } else {
                    // new region starts within the vertical range of existing region

                    if (w > _w) {
                        // new region horizontally overlaps existing region

                        if (h > _h) {
                            // new region contains bottom of existing region
                            dirties[_n+3] = y;
                            continue;
                        }// else {
                        // new region overlaps to the left and right of existing region
                        dirty(x, y, _x, h, i+1);
                        dirty(_w, y, w, h, i+1);
                        return;

                    } else {
                        // new region ends within horizontal range of existing region

                        if (h > _h) {
                            // new region overlaps bottom-left corner of existing region
                            dirty(x, y, _x, h, i+1);
                            dirty(_x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains right part of new region
                        w = _x;
                        continue;
                    }
                }
            } else {
                // new region starts within the horizontal range of existing region

                if (y < _y) {
                    // new region starts above existing region

                    if (w > _w) {
                        // new region overlaps at least top-right of existing region

                        if (h > _h) {
                            // new region contains the right of existing region
                            dirties[_n+2] = x;
                            continue;
                        }// else {
                        // new region overlaps top-right of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(_w, _y, w, h, i+1);
                        return;

                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // new region overlaps to the above and below of existing region
                            dirty(x, y, w, _y, i+1);
                            dirty(x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains bottom part of new region
                        h = _y;
                        continue;
                    }
                } else {
                    // new region starts within existing region

                    if (w > _w) {
                        // new region overlaps at least to the right of existing region

                        if (h > _h) {
                            // new region overlaps bottom-right corner of existing region
                            dirty(x, _h, w, h, i+1);
                            dirty(_w, y, w, _h, i+1);
                            return;
                        }// else {
                        // existing region contains left part of new region
                        x = _w;
                        continue;
                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // existing region contains top part of new region
                            y = _h;
                            continue;
                        }// else {
                        // new region is contained within existing region
                        return;
                    }
                }
            }
        }

        // region is valid; store it for rendering
        _n = numdirties*4;
        size(_n);
        dirties[_n] = x;
        dirties[_n+1] = y;
        dirties[_n+2] = w;
        dirties[_n+3] = h;
        numdirties++;
    }

    ...
}