Dirty Rectangles

Most frames look almost exactly like the one before. A character takes a step, a score ticks over, a window is dragged aside, and everything else stays where it was. On a machine whose screen is a block of memory that the processor has to write itself, redrawing all of it every frame wastes most of the work. A 320 × 200 screen with one byte per pixel is 64,000 bytes; a sprite 16 pixels square is 256 bytes. The dirty-rectangle technique keeps a list of the areas that have changed, which are “dirty”, and redraws and copies only those.

The clearest period descriptions come from the people who built windowing systems, because a window that is uncovered has to be repaired without redrawing the whole screen. Apple’s Window Manager documentation of 1984 calls the area the “update region”; Digital Research’s GEM hands the program a “rectangle list”; the Amiga’s Layers library keeps a “DamageList”; Windows keeps an “invalid rectangle”. Games used the same trick wherever most of the picture stood still, and id Software’s Doom (1993) still kept a single “dirtybox” for the parts of the screen it had touched.

Fast facts

• What it saves: drawing and copying time, roughly in proportion to how little of the screen changes.
• What it costs: bookkeeping. Every change has to be recorded as a rectangle, and the rectangles have to be merged, clipped and redrawn in the right order.
• Pays off when: most of the screen is still. Adventure games, strategy and board games, status bars, desktop windows.
• Does not pay off when: everything moves. In a game that scrolls the whole screen, nearly every pixel changes every frame, so the whole screen is dirty anyway.
• Not needed for: hardware sprites, which the video chip draws over the background without changing screen memory.
• Usually paired with: a back buffer, as in double buffering, so that the repairs are made off screen and only finished areas are copied to the display.

How it works

Each frame runs through four steps.

1. Collect. For every object that moved, changed its animation frame, appeared or disappeared, add the box where it was last frame and the box where it is now. Add the box of anything in the background that changed, such as a door that opened or a digit of the score.
2. Tidy. Clip each rectangle to the screen and drop any that are now empty. Merge rectangles that overlap, and neighbours whose combined box costs less to redraw than the two apart.
3. Rebuild. For each rectangle, redraw the background inside it, then every object that overlaps it, back to front, clipped to the rectangle.
4. Show. Copy each rectangle from the back buffer to the screen.

Then empty the list and start again.

each frame:
    dirty = []                                  # a fresh list every frame

    # 1. Collect what changed since the last frame
    for obj in objects:
        if obj moved, changed frame, appeared or vanished:
            if obj.was_drawn: dirty.append(obj.old_box)
            if obj.visible:   dirty.append(obj.box)
            obj.old_box = obj.box
            obj.was_drawn = obj.visible
    for tile in changed_background_tiles:
        dirty.append(tile.box)

    # 2. Tidy the list
    dirty = [clip_to_screen(r) for r in dirty]
    dirty = [r for r in dirty if not r.empty]
    dirty = merge(dirty)

    # 3. Rebuild those areas in the back buffer
    for r in dirty:
        draw_background(back, r)
        for obj in objects, back to front:
            if obj.visible and overlaps(obj.box, r):
                draw_clipped(back, obj, r)

    # 4. Show them
    for r in dirty:
        copy(back, screen, r)

This is pseudocode, so trace it rather than run it. The expected result is that after step 4 the screen holds exactly what a full redraw of every pixel would have produced.

The mistakes it guards against

• Forgetting where something was. If only the new box is marked, the old position is never repainted and the object leaves a trail.
• Forgetting things that vanish. A sprite that is destroyed has no new box, but its old one still has to be repaired, or a ghost of it stays on screen.
• Redrawing only the objects that moved. Step 3 repaints the background over the whole rectangle, which wipes out any still object that overlaps it. Every visible object that touches the rectangle has to be drawn again, in depth order.
• Never emptying the list. The picture stays correct, but the list grows every frame until the program is redrawing everything and paying for the bookkeeping as well.

Merging rectangles

How far to merge is a judgement. Two overlapping boxes are always worth combining, because the overlap would otherwise be drawn twice. Two boxes far apart are cheaper to draw separately than as one big box that covers the empty space between them. A common rule is to merge when the bounding box is no larger than the two areas added together, plus an allowance for the cost of handling an extra rectangle.

The simplest scheme keeps just one box and stretches it to take in every change. Doom’s source code does this: its V_MarkRect routine grows a single dirtybox to include each rectangle the engine draws into. Windows does the same for each window. Charles Petzold’s Programming Windows explains that Windows keeps “the coordinates of the smallest rectangle that encompasses the invalid region”, and if another area becomes invalid before the program has repainted, “Windows calculates a new invalid region that encompasses both areas”.

Page flipping

With two screens that take turns, as in double buffering by page flipping, the bookkeeping changes. The page about to be drawn was last brought up to date two frames ago, so it needs this frame’s rectangles and the previous frame’s too. Fabien Sanglard’s account of Doom describes how its DOS version, which cycled through three pages of VGA memory, kept a separate update box for each page.

Copying a rectangle straight to the visible screen can still be caught half done by the display’s beam, which shows as tearing. Small copies finish sooner, which narrows that window without closing it; the usual cure is to copy during the vertical blank, or to flip pages.

In the windowing systems

Overlapping windows made partial redrawing a job for the operating system. When one window moves, the part of the window behind it that comes into view is damaged, and only that part needs repainting. Each system recorded the damage in its own way and handed it to the program.

Macintosh (1984). Apple’s Window Manager documentation describes the update region as “dynamic rather than fixed: the Window Manager keeps track of all areas of the content region that have to be redrawn and accumulates them into the update region”. The Toolbox Event Manager “periodically checks to see if there’s any window whose update region is not empty” and reports an update event. The program then calls BeginUpdate, which limits drawing to the damaged area, draws the window, and calls EndUpdate. The program can draw the whole window if that is simpler, because “only the parts of the window that require updating will actually be drawn on the screen”. The update region is a QuickDraw region, which, the QuickDraw documentation explains, “can be any arbitrary area or set of areas”, including ones with holes, so it is not limited to rectangles.

Amiga. The Layers library does the same for its “simple refresh” layers, which keep no copy of their hidden parts. “The system keeps track of these areas by using a DamageList,” the ROM Kernel Reference Manual explains. BeginUpdate() installs a set of clipping rectangles made from the DamageList, so “use the graphics rendering routines as if to redraw the entire layer … only the damaged areas are actually rendered into, saving time”.

Atari ST (GEM). GEM gives the program a list of rectangles instead of a clipping region, and the program walks through it. James Luczak’s 1987 tutorial in ST-Log sets out the loop: call WIND_GET for “the first rectangle of the rectangle list”, work out which part of the window it covers, draw, then call WIND_GET again “to get the next rectangle to update from the rectangle list”, until the list is empty. In 1993 ST Format’s assembly-language column described the same process, setting the VDI clipping rectangle with vs_clip for each one, and called the area to repair “the dirty rectangle”.

Windows. A program marks an area for repainting with InvalidateRect, and Windows sends a single WM_PAINT message however many areas have been invalidated. Petzold advised that although a program “can simply repaint the entire client area”, “repainting only the area of the window defined by that rectangle saves time”.

Two styles run through these systems. The Macintosh and Amiga manuals let the program redraw everything and rely on clipping to keep the output inside the damage, which is simple to write. GEM’s loop, and careful Windows programs, draw only inside each rectangle. Petzold explained why the extra code was worth it: when a program draws outside the invalid rectangle, Windows has to work out that there is nothing to do, and “this determination takes time”.

In games

A game uses the technique when its picture is mostly still: a room in an adventure game, a board or a map, or the status panel around a 3D view. Doom rendered its 3D view in full every frame, but kept its dirty box so that only the parts of the screen it had drawn into were sent to the video card. In a game that scrolls the whole screen, every rectangle is dirty every frame, and the bookkeeping is wasted.

Later use

The same idea now goes by “damage” or “invalidation”. In the Wayland display protocol used on Linux, for example, a program tells the compositor “the regions where the pending buffer is different from the current surface contents, and where the surface therefore needs to be repainted”.

See also

• Double Buffering
• Sprites
• Blitter
• Game Loop
• Doom