On the power of the frame buffer

Raster graphics displays are almost always refreshed out of a frame buffer in which a digital representation of the currently visible image is kept. The availability of the frame buffer as a two-dimensional memory array representing the displayable area in a screen coordinate system has motivated the development of algorithms that take advantage of this memory for more than just picture storage. The classic example of such an algorithm is the depth buffer algorithm for determining visible surfaces of a three-dimensional scene. This paper constitutes a first attempt at a disciplined analysis of the power of a frame buffer seen as a computational engine for use in graphics algorithms. We show the inherent power of frame buffers to perform a number of graphics algorithms in terms of the number of data fields (registers) required per pixel, the types of operations allowed on these registers, and the input data. In addition to upper bounds given by these algorithms, we prove lower bounds for most of them and show most of these algorithms to be optimal. One result of this study is the introduction of new frame buffer algorithms for computing realistic shadows and for determining the convex intersection of half spaces, an operation important in computational geometry and in rendering objects defined using planes rather than polygons. Another result is that it shows clearly the relationships between different and important areas of research in computer graphics, such as visible surface determination, compositing, and hardware for smart frame buffers.