Invalidation/Redraw -- A Graphical Interface Pattern

Category: Graphical Interface

Intent

Used to optimize redraws in a graphical system where there tend to be a large number of visual changes, each involving only a small part of the graphic.

Motivation

A naive implementation of a graphical system redraws an entire graphic immediately every time any part of that graphic changes. This is acceptable for some purposes, but becomes unacceptably in situations like graphical user interfaces, where it can result in large numbers of redraws and poor performance. For instance, suppose the user drags a window in front of another complex window. To redraw the back window for every pixel of mouse movement is unnecessary and extremely slow. Instead, it is better to store a series of events indicating which parts of the back window were blocked, and redraw the window only once after all the user releases the front window. If greater update responsiveness is called for, the back window can be redrawn at regular intervals, at each interval redrawing all changes since the previous redraw.

Applicability

Invalidation/Redraw is useful in graphical systems where

Changes to the graphic occur frequently.
Instantaneous graphical updates are not required.

If changes are infrequent, Invalidation/Redraw complicates the system with little performance gain. If instantaneous updates are required, Invalidation/Redraw may be too slow due to the delay between the redraw request and the redraw.

Consequences

Invalidation/Redraw introduces some additional memory usage to store the collected union of the update request regions.

In systems where updates are frequent, drawing time is significantly reduced. The amount of reduction depends on the time between redraws-- more frequent redraws require more time but improve responsiveness.

Implementation

Consider the following issues when implementing the Invalidation/Redraw pattern:

Invalidation/Redraw may be most easily implemented using rectangular regions for invalidation. However, providing more general geometric shapes should improve performance, as it will limit the number of pixels which will actually have to be drawn in some cases. For instance, a circular dial object can be invalidated as a circle, rather than a rectangle, eliminating the need to redraw the pixels at the rectangle corners.
Generally a system which supports "rectangles only" for individual invalidation events will support an arbitrary union of rectangles as the accumulated invalid area-- this is easily implemented by storing a list of invalid rectangles internally and iterating over them at redraw time. However, an even simpler approach is to use a single rectangle as the collected invalid region; new rectangles are added by expanding the invalid rectangle to cover them. This may result in drawing a much larger area than necessary, but in some applications (like user interfaces) where updates tend to be localized, it may be a reasonably approximation.
Support for general shapes also allows all invalid regions to be unified into a single region, which is then redrawn in a single step. This approach significantly reduces the number of redraws required and is usually faster than the alternative (redrawing each invalid region separately), but can also significantly increase the complexity of the system, especially if there is no low-level support for general geometric regions.
On systems supporting multithreading, it may be possible to perform the redraws in a separate thread. In many existing systems, however, the redraws are performed by calling a Redraw procedure from the main event loop.
Shorter time intervals between redraw cycles will require more time, but will improve apparent responsiveness. However, intervals too small can require so much drawing time that the entire program slows down. In user interface applications, this is generally not a problem, because invalidate events tend to happen in small clumps. But it could become a problem in an application which generates long and steady streams of invalidate events.
It is often possible to improve performance by doing some simple optimizations. For instance, if any of the requested invalid regions is entirely enclosed by any other, the inner one can be discarded. Also, if there is a clipping region associated with drawing, any invalid regions outside the clipping region can be discarded.

Known Uses

Invalidation/Redraw is found in most graphical user interface packages. Examples include ET++, the Think Class Library, VisualWorks Smalltalk, and the MacOS Toolbox. The pattern is well suited to some kinds of animation packages, but I know of no examples of its use for such applications. Please send any additional examples to Greg Ferrar.

Back to the ET++ pages