graphics - 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.