Scanline rendering

related topics
{system, computer, user}
{math, number, function}
{math, energy, light}
{line, north, south}
{work, book, publish}
{style, bgcolor, rowspan}
{company, market, business}

Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics, that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis. All of the polygons to be rendered are first sorted by the top y coordinate at which they first appear, then each row or scan line of the image is computed using the intersection of a scan line with the polygons on the front of the sorted list, while the sorted list is updated to discard no-longer-visible polygons as the active scan line is advanced down the picture.

The asset of this method is that it is not necessary to translate the coordinates of all vertices from the main memory into the working memory—only vertices defining edges that intersect the current scan line need to be in active memory, and each vertex is read in only once. The main memory is often very slow compared to the link between the central processing unit and cache memory, and thus avoiding re-accessing vertices in main memory can provide a substantial speedup.

This kind of algorithm can be easily integrated with the Phong reflection model, the Z-buffer algorithm, and many other graphics techniques.

Contents

Algorithm

The usual method starts with edges of projected polygons inserted into buckets, one per scanline; the rasterizer maintains an active edge table(AET). Entries maintain sort links, X coordinates, gradients, and references to the polygons they bound. To rasterize the next scanline, the edges no longer relevant are removed; new edges from the current scanlines' Y-bucket are added, inserted sorted by X coordinate. The active edge table entries have X and other parameter information incremented. Active edge table entries are maintained in an X-sorted list by bubble-sort, effecting a change when 2 edges cross. After updating edges, the active edge table is traversed in X order to emit only the visible spans, maintaining a Z-sorted active Span table, inserting and deleting the surfaces when edges are crossed.

Variants

A hybrid between this and Z-buffering does away with the active edge table sorting, and instead rasterizes one scanline at a time into a Z-buffer, maintaining active polygon spans from one scanline to the next.

In another variant, an ID buffer is rasterized in an intermediate step, allowing deferred shading of the resulting visible pixels.

History

The first publication of the scanline rendering technique was probably by Wylie, Romney, Evans, and Erdahl in 1967.[1]

Other early developments of the scanline rendering method were by Bouknight in 1969,[2] and Newell, Newell, and Sancha in 1972.[3] Much of the early work on these methods was done in Ivan Sutherland's graphics group at the University of Utah, and at the Evans & Sutherland company in Salt Lake City, Utah.

Full article ▸

related documents
Wavelet compression
Java remote method invocation
Netwide Assembler
Wikipedia:Federal Standard 1037C terms/telecommunications encryption terms
Application programming interface
Gnumeric
Cacti (software)
Alternating bit protocol
Automatic data processing
Pseudorandom noise
Challenge-handshake authentication protocol
GNUstep
Applet
Pico (text editor)
Instruction register
Sinclair Scientific
A20 handler
Rock Ridge
Acme (text editor)
BitchX
Terabyte
Differential Manchester encoding
XMMS
Binary image
Mail transfer agent
OS/390
Sircam
Distributed database
Data stream
8-bit clean