Scanline rendering

As a scanline algorithm or image lines algorithm for image line image line (english scan online ) operating process for masking calculation of polygons constructed from 3D scenes is called in computer graphics. The whole rendering process is also known as scanline rendering and Bildzeilenrenderung. Scanline algorithms exploit the fact that through the line as forming line work, the problem of occlusion calculation is reduced from three to two dimensions. The first scanline algorithms have been published in the late 1960s.

Basic principle

Scanline algorithms are based on the edge lists algorithm with active edge list for filling polygons (see rasterizing polygons ), which is sometimes also called scan-line algorithm. This algorithm is extended such that it can scan several polygons at once, and in case of problems, which polygon is visible from the observer.

The scan-line algorithm for rendering polygons used 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 Kanteneckpunkts smaller y-coordinate
• The y- coordinate of the other Kanteneckpunkts,
• ∂ x, the difference between the x coordinates of the intersection points of two successive picture 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, which, for each polygon, in addition to the number, at least the following information:

• The coefficients of the plane equation of the plane containing the polygon
• Shading or color information,
• A flag is used during the scan line algorithm and indicates whether it is currently located within that polygon. It must be initialized at the beginning to false.

Further an active edge table ( table of active edges) as the simple algorithm for filling polygons required, which contains all edges that intersect the current processed image line. For the example given in the active picture lines edge table contains the following values ​​:

The image lines are processed from left to right. In the image line c, the algorithm proceeds as follows: As soon as the edge AB is reached, the in-out flag of the corresponding polygon is set; the algorithm is now " in" this polygon, and the pixels are colored according to the polygon associated shading information. Once the edge AC is achieved, the flag is reset to false. Since the edge AC is the last in the active edge table, the operation of this image line is complete. In the image line b two polygons are involved, but as they here do not overlap, the algorithm looks exactly as in the previous cases, use only a maximum of one polygon per pixel.

In the image a line more effort is required. As soon as the triangle ABC is obtained, the algorithm sets the corresponding flag in the polygon table. The shading information of this polygon will be used until the edge DE is reached. Here is also the flag of the triangle DEF is set, the algorithm is now so at the same time "in" two polygons. It must be decided now, which is these two polygons closer to the viewer. This is done by the Z- coordinate of the polygon is calculated at this point using the plane equation coefficients stored. In this example, ABC is greater z-coordinate, so it is not visible. Assuming that the two polygons do not intersect each other, so, consequently, the shading parameters of the triangle DEF can be used. If the next edge CB is achieved, the flag of the polygon ABC is set to false and the algorithm is only in the polygon DEF whose shading parameters continue to be used.

Variants

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

Scanline algorithms can also be combined with the Z-buffer. In this case, only one image line comprehensive Z-buffer, called a scanline Z-buffer, for the current image line will be used. It makes sense, if there is insufficient memory for a complete Z-buffer is available.

Comparison with the Z-buffer

Compared to the Z-buffer have Spanning scanline algorithms has the advantage that shading calculations need only be performed once per pixel. However, begin and end spans not necessarily at the intersections with the edges of the visible polygon. This makes the incremental ( stepwise) shading calculation as the initial values ​​must be calculated at any point of the polygon. The Z-buffer is more efficient from a certain number of polygons as Spanning scanline algorithms, which is why it is usually preferred for today's complex scenes.