Microtile Arrays

An important requirement for the canvas is to have an efficient representation of the area that needs to be redrawn. This area can be disjoint and potentially very complex, since items can be scattered across the canvas area and one would wish to avoid painting a single large bounding box for all of them.

Microtile arrays are a simple data structure for representing 2D regions, suited to representing redraw areas.

The array divides the area into a grid aligned on 32-pixel boundaries. Within each grid square is a bounding rectangle, the microtile. Since all coordinates in the microtile are in the range $[0, 32]$, 8 bits are more than sufficient for each coordinate. Since each microtile requires four coordinates to represent its bounding rectangle, each microtile can be conveniently represented with a 32-bit value.

Figure 2 presents the microtile representation of a complex area. The polygon defines the covered area. The shaded region represents the individual microtiles; each microtile is the bounding box within a grid square that surrounds the covered area. For the final redrawing operation, adjacent microtiles are combined together into bigger rectangles, shown as thicker outlines in the diagram. Each of these rectangles is then calculated and drawn to the screen.

Figure 2: Microtile array that represents the area occupied by a complex polygon. Each little bounding box, or microtile, fits within a grid square. Microtiles are later coalesced into bigger rectangles suitable for redrawing.

Microtile arrays have many advantages which make them ideal for the canvas widget. First, the data structure is compact; a microtile array for a $640 \times 480$ window requires only 1200 bytes. Second, it can be manipulated very quickly; the sample polygon in Figure 2 is calculated in about 1.2 ms on a 233 MHz PII. Third, the resulting microtile array is easily decomposed into rectangles.

Rectangle decomposition has several desirable properties, including a bounded number of rectangles -- no more than 300 for that $640 \times 480$ image, no matter the complexity of the area. Also, rectangles tend to align on 32-pixel boundaries, which can speed things down the rendering pipeline.

In the context of the GNOME canvas, items can queue their redraw areas in any of three ways: they can specify an explicit microtile array, in which case it is added to the canvas' current redraw area; they can request that a rectangular area be redrawn, and so the canvas converts that rectangle to a microtile array; or they can specify a sorted vector path as the redraw area, which is again converted to a microtile array.