Microtile Arrays
Author John R. Sheets talks about the usefulness of microtile arrays, as used in the libart graphics rendering library.
Microtile Arrays
This content is excerpted from section 10.4.4 of John R. Sheets' book, Writing GNOME Applications (Addison-Wesley, 2001).
Libart's microtile arrays make it easier to optimize image redrawing, by breaking down the "dirty" areas into smaller rectangles. The microtile array (affectionately abbreviated uta, with the "u" standing for the Greek letter m, or micron) represents a grid of 32x32 pixel squares overlaid on an area of coordinate space. For example, a 96x64 pixel buffer would have six microtiles, arranged in a 3x2 grid.
Figure 1 shows a path drawn in the shape of a guitar case. Rather than having to rerender the bounding box of the entire path, indicated by the dotted line, the microtile array breaks the dirty regions into smaller components. The gray rectangles show the areas that need to be refreshed when using the uta.
){kind=link}
Microtile arrays
Each microtile has a single bounding box within its 32x32 area, to mark the entire area of interest—the "dirty" area in the case of repainting algorithms—within its grid square. When an application attempts to refresh its microtiled drawing areas, it can roll through the uta and redraw only the area contents of each bounding box. It can ignore all microtiles with zero-area bounding boxes. The fewer unnecessary pixels the application has to redraw, the faster the refresh will take place each time. In practice, the microtiles are usually merged and decomposed into an array of rectangles, optimized for efficient redraws.
A significant advantage to utas is that you can add to them dynamically, as the dirty area changes. The microtiles will adjust their bounding boxes to include the new areas or ignore the areas they already cover. This makes it much easier to implement deferred painting updates, in which redraws happen during idle times. Between updates, the microtiles accumulate "dirt," but they always remain in a ready-to-use state, whenever the next repaint event happens to occur.
Another advantage of microtile arrays is their stable memory footprint. No matter how many times a drawing area is damaged, the number of microtiles never increases. Only the coordinates of the existing bounding boxes change. Utas are also very efficient, especially because of their 32-pixel grid size. The 32-pixel boundaries result in convenient 4-byte-aligned chunks of the pixel buffer. Also, the fact that each bounding box is constrained to a coordinate range of 0 to 32 pixels makes it possible to fit all four coordinate values into a single 32-bit integer. Technically, each coordinate fits into 5 bits, but to maintain the optimization, each coordinate is padded to 8 bits. Thus, our earlier 96x64 pixel example requires only 24 bytes (6 microtiles x 4 bytes) to express its bounding-box data.
See also:
http://www.aw.com/cseng/titles/0-201-65791-0/
About the Author
John R. Sheets has been following the GNOME project on a day-to-day basis for more than two years, since GNOME was only six months old. He is a software developer for CodeWeavers, Inc., where he works on Wine and GNOME. In his free time, he is helping the WorldForge Project to create a free online multiplayer gaming environment. John is the author of Writing GNOME Applications (Addison-Wesley, 2001), and the maintainer of the OpenBooks Web site.