MicroTile Arrays

typedef struct _ArtUta ArtUta;
typedef art_u32 ArtUtaBbox;

#define ART_UTA_BBOX_CONS(x0, y0, x1, y1) (((x0) << 24) | ((y0) << 16) | \
				       ((x1) << 8) | (y1))

#define ART_UTA_BBOX_X0(ub) ((ub) >> 24)
#define ART_UTA_BBOX_Y0(ub) (((ub) >> 16) & 0xff)
#define ART_UTA_BBOX_X1(ub) (((ub) >> 8) & 0xff)
#define ART_UTA_BBOX_Y1(ub) ((ub) & 0xff)

#define ART_UTILE_SHIFT 5
#define ART_UTILE_SIZE (1 << ART_UTILE_SHIFT)

/* Coordinates are shifted right by ART_UTILE_SHIFT wrt the real
   coordinates. */
struct _ArtUta {
  int x0;
  int y0;
  int width;
  int height;
  ArtUtaBbox *utiles;
};

ArtUta is a specialized libart data structure for representing approximate regions, i.e. regions of interest. A very typical application for microtile arrays is to represent the region needing repaint in the Gnome Canvas display. As individual canvas items undergo state change, they add the area changed to the repaint region. Finally, the canvas repaints this region. Even when the same area is added to the repaint region more than once, it is only painted once.

The uta data structure has numerous advantages. It is compact in size, has simple structure, and is bounded in growth. An uta for a 640 x 480 window will never grow above 1200 bytes, no matter how complex the region becomes. In spite of the excellent space and speed characteristics, uta's are fairly precise. For any rectangle, there is a corresponding uta that covers exactly the same region. Uta's are also excellent at representing L-shapes and other cases likely to occur in practice. When imprecision does occur, the resulting squares are likely to align on 32-pixel boundaries, which can speed things significantly downstream.

The data structure itself is fairly simple. There is one ArtUtaBbox for each 32 x 32 pixel square (i.e. MicroTile) of the region. Each ArtUtaBbox contains a bounding box, with the coordinates packed one-per-byte into a single 32-bit word. An ArtUtaBbox of zero is empty. Conversely, an ArtUtaBbox of 0x00002020 is full; 0x20 is equal to 32, the size of the square.

The region covered by the extends from uta->x0 * 32 to (uta->y0 + uta->width) * 32, and similarly in the y direction. Thus, all squares are aligned to 32-pixel boundaries.

The figure above represents the uta computed from a randomly generated vector path, along with its decomposition into rectangles. Both operations are extremely fast, on the order of 1.5 milliseconds on a PII 233.

The "u" in uta represents the Greek letter "micron." It has also been speculated that "uta" really stands for "User to Aardvark." Besides, it just sounds cooler than "mta."