Scanline algorithm

from Wikipedia, the free encyclopedia

As Scanline algorithm or image lines algorithm is used in the computer graphics (English an image line by image line scan line ) operating process for masking calculation of from polygons built 3D scenes called. The entire display process is also called scanline rendering or image line rendering . Scanline algorithms take advantage of the fact that the line-by-line operation reduces the problem of masking computation from three to two dimensions. The first scanline algorithms were published in the late 1960s.

Basic principle

Rasterization of two polygons using the scanline algorithm

Scanline algorithms are based on the edge list algorithm with an active edge list for filling polygons (see Rasterizing of polygons ), which is sometimes also called the scanline algorithm . This algorithm has been expanded so that it can also rasterize several polygons at once and, in cases of doubt, decide which polygon is visible to the viewer.

The Scanline algorithm for rendering polygons uses an edge table that contains an entry for each edge of a polygon. Horizontal edges are ignored. Each entry in the edge table contains the following information:

  • the x -coordinate of the corner point with the smaller y -coordinate,
  • the y -coordinate of the other corner point,
  • Δx, the difference between the x -coordinates of the intersection points with two consecutive image lines (the reciprocal of the slope of the edge),
  • the number of the polygon to which the edge belongs.

In addition, a polygon table is required that contains at least the following information for each polygon, in addition to its number:

  • the coefficients of the plane equation of the plane containing the polygon,
  • Shading or color information,
  • a flag that is used during the scanline algorithm and indicates whether you are currently inside this polygon. It must be initialized to false at the beginning .

Furthermore, as with the simple algorithm for filling polygons, an active edge table (table of active edges) is required which contains all edges that intersect the currently processed image line. The active edge table contains the following values ​​for the image lines specified in the example:

Image line edge
c AB AC
b AB AC FD FE
a AB DE CB FE

The image lines are processed from left to right. The algorithm proceeds as follows for image line c: As soon as edge AB is reached, the in-out flag of the corresponding polygon is set; the algorithm is now “in” this polygon, and pixels are colored according to the shading information associated with the polygon. As soon as the edge AC is reached, the flag is set to false again. Since the edge AC is the last in the active edge table, the process for this picture line is finished. Two polygons are involved in image line b, but since they do not overlap here, the algorithm always only considers a maximum of one polygon per pixel, just as in the previous case.

More effort is required for image line a. As soon as the triangle ABC is reached, the algorithm sets the corresponding flag in the polygon table. The shading information of this polygon is used until the edge DE is reached. The flag for the triangle DEF is now also set here, so the algorithm is now "in" two polygons at the same time. It must now be decided which of these two polygons is closer to the viewer. This is done by calculating the z coordinate of the polygon at this point with the help of the stored plane equation coefficients . In this example, ABC has the larger z coordinate, so it is not visible. If it is assumed that the two polygons do not intersect, the shading parameters of the triangle DEF are used accordingly. When the next edge CB is reached, the flag of polygon ABC is set to false and the algorithm is only located in polygon DEF, whose shading parameters are still used.

variants

The basic scanline algorithm calculates the depth of the overlapping polygons at each pixel. The number of these calculations can be reduced by dividing the image line into individual areas ("spans"), for which only one calculation is performed. Such methods, which also include the algorithm published by Watkins in 1970, are called spanning scanline algorithms .

Scanline algorithms can also be combined with the Z-buffer . A Z-buffer, a so-called scanline Z-buffer, which comprises only one image line , is used for the current image line. It is useful if there is not enough memory for a complete Z-buffer.

Comparison with the Z-buffer

Compared to the Z-buffer, spanning scanline algorithms have the advantage that shading calculations only have to be carried out once per pixel. However, spans do not necessarily begin and end at the intersections with the edges of the visible polygon. This complicates the incremental (step-by-step) shading calculation, since the starting values ​​have to be calculated at any point on the polygon. The Z-buffer is more efficient than spanning scanline algorithms above a certain number of polygons, which is why it is usually preferred for today's complex scenes.

literature

  • Hans-Joachim Bungartz ao: Introduction to computer graphics: basics, geometric modeling, algorithms. Vieweg, Braunschweig 2002, ISBN 3-528-16769-6
  • James Foley et al: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
  • William Newman, Robert Sproull: Principles of Interactive Computer Graphics, pp. 313-321. McGraw-Hill, New York 1973, ISBN 0-07-046337-9
  • David Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5

Individual evidence

  1. ↑ Jack Bouknight: A procedure for generation of three-dimensional half-toned computer graphics presentations. Communications of the ACM 13,9 (Sep 1970): 527-536, ISSN  0001-0782
  2. ↑ Jack Bouknight, K. Kelley: An algorithm for producing half-tone computer graphics presentations with shadows and movable light sources. In AFIPS Conference Proceedings, vol. 36: 1970 Fall Joint Computer Conference. Pp. 1-10. AFIPS Press, Montvale 1970
  3. ^ Gary Scott Watkins: A Real Time Visible Surface Algorithm. Dissertation, University of Utah 1970
  4. ↑ C. Wylie et al .: Halftone perspective drawings by computer. In AFIPS Conference Proceedings, vol. 31: 1967 Fall Joint Computer Conference. Pp. 49-58. AFIPS Press, Montvale 1967
  5. ^ AJ Myers: An Efficient Visible Surface Program. Report to the National Science Foundation, Computer Graphics Research Group, Ohio State University 1975
  6. ^ Alan Watt: 3D Computer Graphics, p. 194. Addison-Wesley, Harlow 2000, ISBN 0-201-39855-9