Scanline rendering
Encyclopedia
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 main advantage of this method is that sorting vertices along the normal of the scanning plane reduces the number of comparisons between edges. Another advantage 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.
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.
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.
Other early developments of the scanline rendering method were by Bouknight in 1969, and Newell, Newell, and Sancha in 1972. 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.
The Nintendo DS
is the latest hardware to render 3D scenes in this manner, with the option of caching the rasterized images into VRAM.
The sprite hardware
prevalent in 1980s games machines can be considered a simple 2D form of scanline rendering.
The technique was used in the first Quake engine for software rendering of environments (but moving objects were Z-buffered
over the top). Static scenery used BSP-derived
sorting for priority. It proved better than Z-buffer
/painter's
type algorithms at handling scenes of high depth complexity with costly pixel operations (i.e. perspective-correct texture mapping without hardware assist). This use preceded the widespread adoption of Z-buffer-based GPUs now common in PCs.
Sony experimented with software scanline renderers on a second Cell
processor during the development of the PlayStation 3
, before settling on a conventional CPU/GPU arrangement.
(most famously the PowerVR
3D chip); that is, primitives are sorted into screen space, then rendered in fast on-chip memory, one tile at a time. The Dreamcast provided a mode for rasterizing one row of tiles at a time for direct raster scanout, saving the need for a complete framebuffer, somewhat in the spirit of hardware scanline rendering.
Some software rasterizers use 'span buffering' (or 'coverage buffering'), in which a list of sorted, clipped spans are stored in scanline buckets. Primitives would be successively added to this datastructure, before rasterizing only the visible pixels in a final stage.
is that visible pixels are only ever processed once—a benefit for the case of high resolution or expensive shading computations.
In modern Z-buffer systems, similar benefits can be gained through rough front-to-back sorting (approaching the 'reverse painters algorithm'), early Z-reject (in conjunction with hierarchical Z), and less common deferred rendering techniques possible on programmable GPUs.
Scanline techniques working on the raster have the drawback that overload is not handled gracefully.
The technique is not considered to scale well as the number of primitives increases. This is because of the size of the intermediate datastructures required during rendering—which can exceed the size of a Z-buffer for a complex scene.
Consequently, in contemporary interactive graphics applications, the Z-buffer has become ubiquitous. The Z-buffer allows larger volumes of primitives to be traversed linearly, in parallel, in a manner friendly to modern hardware. Transformed coordinates, attribute gradients, etc., need never leave the graphics chip; only the visible pixels and depth values are stored.
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
,
that works on a row-by-row basis rather than a polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
-by-polygon or pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
-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
Scan line
A scan line or scanline is one line, or row, in a raster scanning pattern, such as a line of video on a cathode ray tube display of a television set or computer monitor....
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 main advantage of this method is that sorting vertices along the normal of the scanning plane reduces the number of comparisons between edges. Another advantage is that it is not necessary to translate the coordinates of all vertices
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
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
Phong reflection model
The Phong reflection model is an empirical model of the local illumination of points on a surface...
, the Z-buffer algorithm, and many other graphics techniques.
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
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, 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-bufferingZ-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
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
Deferred shading
In computer graphics, deferred shading is a three dimensional shading technique in which the result of a shading algorithm is calculated by dividing it into smaller parts that are written to intermediate buffer storage to be combined later, instead of immediately writing the shader result to the...
of the resulting visible pixels.
History
The first publication of the scanline rendering technique was probably by Wylie, Romney, Evans, and Erdahl in 1967.Other early developments of the scanline rendering method were by Bouknight in 1969, and Newell, Newell, and Sancha in 1972. Much of the early work on these methods was done in Ivan Sutherland
Ivan Sutherland
Ivan Edward Sutherland is an American computer scientist and Internet pioneer. He received the Turing Award from the Association for Computing Machinery in 1988 for the invention of Sketchpad, an early predecessor to the sort of graphical user interface that has become ubiquitous in personal...
's graphics group at the University of Utah
University of Utah
The University of Utah, also known as the U or the U of U, is a public, coeducational research university in Salt Lake City, Utah, United States. The university was established in 1850 as the University of Deseret by the General Assembly of the provisional State of Deseret, making it Utah's oldest...
, and at the Evans & Sutherland
Evans & Sutherland
Evans & Sutherland is a computer firm involved in the computer graphics field. Their products are used primarily by the military and large industrial firms for training and simulation, and in digital projection environments like planetariums.-History:...
company in Salt Lake City.
Use in realtime rendering
The early Evans & Sutherland ESIG line of image-generators (IGs) employed the technique in hardware 'on the fly', to generate images one raster-line at a time without a framebuffer, saving the need for then costly memory. Later variants used a hybrid approach.The Nintendo DS
Nintendo DS
The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...
is the latest hardware to render 3D scenes in this manner, with the option of caching the rasterized images into VRAM.
The sprite hardware
Sprite (computer graphics)
In computer graphics, a sprite is a two-dimensional image or animation that is integrated into a larger scene...
prevalent in 1980s games machines can be considered a simple 2D form of scanline rendering.
The technique was used in the first Quake engine for software rendering of environments (but moving objects were Z-buffered
Z-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
over the top). Static scenery used BSP-derived
Binary space partitioning
In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
sorting for priority. It proved better than Z-buffer
Z-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
/painter's
Painter's algorithm
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics...
type algorithms at handling scenes of high depth complexity with costly pixel operations (i.e. perspective-correct texture mapping without hardware assist). This use preceded the widespread adoption of Z-buffer-based GPUs now common in PCs.
Sony experimented with software scanline renderers on a second Cell
Cell (microprocessor)
Cell is a microprocessor architecture jointly developed by Sony, Sony Computer Entertainment, Toshiba, and IBM, an alliance known as "STI". The architectural design and first implementation were carried out at the STI Design Center in Austin, Texas over a four-year period beginning March 2001 on a...
processor during the development of the PlayStation 3
PlayStation 3
The is the third home video game console produced by Sony Computer Entertainment and the successor to the PlayStation 2 as part of the PlayStation series. The PlayStation 3 competes with Microsoft's Xbox 360 and Nintendo's Wii as part of the seventh generation of video game consoles...
, before settling on a conventional CPU/GPU arrangement.
Similar techniques
A similar principle is employed in tiled renderingTiled rendering
Tiled rendering is the process of subdividing a computer graphics image by a regular grid in image space to exploit local spatial coherence in the scene and/or to facilitate the use of limited hardware rendering resources later in the graphics pipeline...
(most famously the PowerVR
PowerVR
PowerVR is a division of Imagination Technologies that develops hardware and software for 2D and 3D rendering, and for video encoding, decoding, associated image processing and Direct X, OpenGL ES, OpenVG, and OpenCL acceleration....
3D chip); that is, primitives are sorted into screen space, then rendered in fast on-chip memory, one tile at a time. The Dreamcast provided a mode for rasterizing one row of tiles at a time for direct raster scanout, saving the need for a complete framebuffer, somewhat in the spirit of hardware scanline rendering.
Some software rasterizers use 'span buffering' (or 'coverage buffering'), in which a list of sorted, clipped spans are stored in scanline buckets. Primitives would be successively added to this datastructure, before rasterizing only the visible pixels in a final stage.
Comparison with Z-buffer algorithm
The main advantage of scanline rendering over Z-bufferingZ-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
is that visible pixels are only ever processed once—a benefit for the case of high resolution or expensive shading computations.
In modern Z-buffer systems, similar benefits can be gained through rough front-to-back sorting (approaching the 'reverse painters algorithm'), early Z-reject (in conjunction with hierarchical Z), and less common deferred rendering techniques possible on programmable GPUs.
Scanline techniques working on the raster have the drawback that overload is not handled gracefully.
The technique is not considered to scale well as the number of primitives increases. This is because of the size of the intermediate datastructures required during rendering—which can exceed the size of a Z-buffer for a complex scene.
Consequently, in contemporary interactive graphics applications, the Z-buffer has become ubiquitous. The Z-buffer allows larger volumes of primitives to be traversed linearly, in parallel, in a manner friendly to modern hardware. Transformed coordinates, attribute gradients, etc., need never leave the graphics chip; only the visible pixels and depth values are stored.
See also
- Raster scanRaster scanA raster scan, or raster scanning, is the rectangular pattern of image capture and reconstruction in television. By analogy, the term is used for raster graphics, the pattern of image storage and transmission used in most computer bitmap image systems...
- Ray tracing
- Z-bufferingZ-bufferingIn computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...
- Bresenham's line algorithmBresenham's line algorithmThe Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points...