Rasterization of polygons

The rasterization of polygons and lined up line segments ( polygons ) is a task of computer graphics . The grids of polygons based on the line drawing algorithm , but requires at thicker stroke width extra effort. The rasterization of filled polygons plays an important role in 3D computer graphics, as 3D scenes can be rendered by filling in color the polygons projected onto the image plane.

Connect line segments

Different types of rasterization of polygon corners: a) blunt ends, b) rounded ends, c) miter ring, d) miter ring with truncated tips.

When rasterizing thick line segments, it is important to decide how they will be connected to each other. Viewing thick lines as rectangles will produce unsightly results. It is better to draw lines with rounded ends. Another possibility is mitering ( " skew ") at which the line ends are drawn obliquely so that they adjoin one another. At very acute angles, the line ends protrude too much beyond the actual polygon corner, which is why they are better cut off.

Artifacts

Two different ways of rasterizing a rectangle

When rasterizing polygons, it must be decided how their coordinates are to be interpreted. For example, if a rectangle with the end point coordinates (1, 1) and (5, 4) is rasterized, 5 × 4 pixels are normally colored, although the rectangle is only 4 × 3 units in size. This undesirable effect is a consequence of the finite image resolution. If polygons that are next to each other are drawn, this leads to some pixels being colored several times. One way to get around this problem, at least with integer coordinates, is to shift them half a pixel distance to the left and down when rasterizing, so that in reality the rectangle with the coordinates (0.5, 0.5) and ( 4.5, 3.5) is rasterized (see picture). This prevents edges from being colored twice when polygons are adjacent, which would cause undesirable results with certain raster operations such as XOR. An alternative method that avoids floating point numbers is not to rasterize the last pixel of a row or column. It is accepted that the polygon appears to be slightly displaced.

Even very acute-angled polygon corners can result in pixels being colored by several segments. Another example of artifacts are slivers , which are pieces of polygons that are so thin that they do not enclose any pixels, and where some raster algorithms draw only individual pixels or no pixels at all.

If a gridded angle is to be halved by a further line, for example to represent arrows, it is generally not possible to achieve an exactly symmetrical result.

Adjacent triangles

Choosing the color of a pixel that lies exactly on an edge divided by two triangles. Here point a is closer to the reference point, so such pixels are colored light blue.

Polygons with more than three corners as part of a mesh are often converted to triangles before rasterization. A lot of triangles share their edges. If these adjacent triangles are colored differently and each edge is rasterized as a single-colored line, the appearance depends on the order in which the triangles are rasterized.

To get around this problem, a pixel is colored if and only if it lies within the triangle to be drawn. These can barycentric coordinates are used. In relation to a triangle, every point of the plane can be described by the coordinates . A point or pixel is strictly within this triangle if and only if each of these coordinates is in the interval . This method is also valid for non-integer corner point coordinates. ${\displaystyle (\alpha ,\beta ,\gamma )}$ ${\displaystyle ]0,1[}$

A special case are pixels that are located exactly on an edge and therefore cannot be assigned to one of the two adjacent triangles in a trivial way. For these cases one chooses a reference point lying outside the image and chooses the color of the triangle whose corner point not on the edge is closer to this point. This method always works if the reference point does not lie on the straight line running through the edge.

filling

The easiest way to rasterize filled triangles and thus polygons is to apply the test described above for each pixel of the image: Pixels are only colored if they lie within a triangle. A more efficient method only tests those pixels within a rectangle that encloses the triangle to be rasterized. In addition to these simple methods, however, faster methods have been developed, which are described below.

Edge list algorithms

Basic principle

Polygon rasterized with the edge list algorithm

Edge list algorithms determine the intersection points with the image lines for each edge of the polygon. These can be calculated directly, or algorithms can be used to rasterize lines . Horizontal edges are ignored. The intersection points determined in this way are stored in a list.

In order to avoid that too many pixels are colored at the edges, as described above, the intersection points are actually calculated with straight lines running exactly between two image lines. For the example polygon shown on the right in the picture, the following intersection points are stored in the list:

Edge	Saved intersections
(1; 1) - (8; 1)	Ignored because of the horizontal edge
(8; 1) - (8; 6)	(8; 1.5) (8; 2.5) (8; 3.5) (8; 4.5) (8; 5.5)
(8; 6) - (5; 3)	(7.5; 5.5) (6.5; 4.5) (5.5; 3.5)
(5; 3) - (1; 7)	(4.5; 3.5) (3.5; 4.5) (2.5; 5.5) (1.5; 6.5)
(1; 7) - (1; 1)	(1; 6.5) (1; 5.5) (1; 4.5) (1; 3.5) (1; 2.5) (1; 1.5)

These intersection points are now sorted in descending order according to y -coordinates. Values ​​with the same y -coordinates are sorted in ascending order according to x -coordinates. After sorting the list looks like this:

(1; 6.5) (1.5; 6.5) (1; 5.5) (2.5; 5.5) (7.5; 5.5) (8; 5.5) (1 ; 4.5) (3.5; 4.5) (6.5; 4.5) (8; 4.5) (1; 3.5) (4.5; 3.5) (5.5 ; 3.5) (8; 3.5) (1; 2.5) (8; 2.5) (1; 1.5) (8; 1.5)

In this list there is always an even number of values ​​with the same y -coordinate. The polygon is drawn by looking at pairs of points from the list one after the other. They are always of the form (x ₁ ; y) (x ₂ ; y); so both points have the same y -coordinate. All pixels of the corresponding image line are now drawn whose x -coordinate is in the interval . ${\displaystyle [x_{1}-0{,}5;x_{2}-0{,}5]}$

The first pair of points is (1; 6.5) (1.5; 6.5) . The only pixel that fulfills the condition just mentioned is here (1; 6). Then the next pair of points, (1; 5.5) (2.5; 5.5) , is considered. There are two pixels here that are colored, namely (1; 5) and (2; 5). The polygon is completely rasterized when all point pairs in the sorted list have been processed.

Active edge list

The precalculation of the intersection points of polygon edges and straight lines running between the image lines is unnecessarily time-consuming and can require considerable storage space. With what is known as an active edge list, the intersection points can be calculated incrementally and the storage space reduced. This method is sometimes called the scanline algorithm ; however, scanline algorithms are also used to designate processes based on them in order to rasterize scenes made up of polygons line by line within the framework of 3D computer graphics.

With this algorithm, the intersection points with all straight lines are not determined for each polygon edge, but only with the straight line with the largest y -coordinate that intersects the edge. In addition to the x coordinate of the intersection, the following data is determined:

• Δx, the difference between the x coordinates of the intersection points of two vertically adjacent straight lines (the reciprocal of the slope of the edge);
• n _y , the number of lines intersected by the polygon edge.

The data is saved in a table, the entries of which are sorted according to the image line. The following table results for the example polygon:

Image line	Edge	x	Δx	n y
8th
7th
6th	(5, 3) - (1, 7)	1.5	1	3
	(1, 7) - (1, 1)	1	0	5
5	(8, 1) - (8, 6)	8th	0	4th
	(8, 6) - (5, 3)	7.5	−1	2
4th
⋮
0

The basic idea of ​​the algorithm is to start from this precalculated data and to continuously calculate the coordinates of the other intersection points with the aid of the Δx values. This starts with the highest image line and changes gradually to the lower image line. An active edge list stores the edges that intersect the straight line belonging to the image line, as well as the current x , Δx and n _y values for each edge .

At the beginning the active edge list is empty. The highest image line is used as a starting point. For each image line, a search is made in the precalculated table to see whether it contains edges that are not yet contained in the active edge list, and if so, the corresponding data is copied into the active edge list. Now the x values ​​of all edges in the active edge list are sorted in ascending order. The resulting pairs of points are used, as in the basic edge list algorithm, to color pixels. Then the n _y values ​​in the active edge list are decreased by 1; if a value falls below 0, the corresponding edge is removed from the active edge list. Finally, Δx is added to all x values ​​in the active edge list, and the procedure is repeated with the next, lower image line. The rasterization is finished as soon as all image lines have been processed.

In the polygon example, the active edge list changes in the first four lines of the image as follows:

Image line		Active edge list x Δx n y		Sorted intersection coordinates
8th
7th
6th		1.5 1 3 1 0 5		(1, 6.5) (1.5, 6.5)
5		2.5 1 2 1 0 4th 8th 0 4th 7.5 −1 2		(1; 5.5) (2.5; 5.5) (7.5; 5.5) (8; 5.5)
		⋮

Edge-fill algorithm

The greatest disadvantage of the edge list algorithms is the effort required to sort and manipulate the lists. The very simple edge-fill algorithm manages without this effort. With the edge-fill algorithm, for each image line that intersects a polygon edge, all pixels of this image line with an x -coordinate are strictly larger than inverted. "Inversion" here means that colored pixels are reset to their initial state and vice versa. The order in which the polygon edges are processed is arbitrary. If the algorithm processes the edges of the example polygon counterclockwise, the following steps result: ${\displaystyle x_{\mathrm {Schnittpunkt} }}$ ${\displaystyle x_{\mathrm {Schnittpunkt} }+0,5}$

The rasterized polygon differs from that of the edge list algorithms because three pixels are not colored. The disadvantage of the algorithm is that many pixels have to be changed several times.

Fence-fill algorithm

The fence-fill algorithm is a further development of the edge-fill algorithm, which reduces the number of pixel inversions required. Here, a is a fence (engl. "Fence"), a line passing through the intersection of two polygon edges vertical line, used.

• For all intersections on the left side of the fence, all pixels from the intersection to the left of the fence are inverted.
• For all intersections on the right side of the fence, all pixels from the fence to the left of the intersection are inverted.

This results in the following steps:

Edge flag algorithm

Colored contour after the first step of the edge flag algorithm

The edge flag algorithm consists of two steps:

• In the first step the contour of the polygon is drawn. For this purpose, the first pixel is colored with the coordinate for each intersection of a polygon edge with an image line (see picture). ${\displaystyle x>x_{\mathrm {Schnittpunkt} }+0,5}$

 Für jede Polygonkante  linie, des Polygons
   punkt1 = linie.punkt1
   punkt2 = linie.punkt2
   wenn (punkt1.y > punkt2.y) dann tausche punkt1 mit punkt2
   Für jede Bildzeile y, des Bildes
     steigung_inv = (punkt1.x - punkt2.x) / (punkt1.y - punkt2.y)
     schnittpunkt_y = y + 0.5
     schnittpunkt_x = punkt1.x + steigung_inv * (schnittpunkt_y - punkt1.y)
     x = abrunden(schnittpunkt_x)
     wenn (x + 0,5) <= schnittpunkt_x dann x=x+ 1
     //- Randpunkt des Schnittpunktes mit der Bildzeile umkehren (einfärben oder zurücksetzen)
     Pixel (x,y) = ! Pixel (x,y);

• In the second step, the pixels within this contour are colored. A Boolean variable is used for this purpose, which indicates whether you are currently inside the polygon or not. This step can be described as pseudocode as follows:

Für jede Bildzeile y, die das Polygon schneidet
  Innerhalb = Falsch
  Für jedes x von links bis rechts
    Wenn Pixel (x, y) eingefärbt ist
      Innerhalb negieren
    Wenn Innerhalb
      Pixel (x, y) einfärben
    ansonsten
      Pixel (x, y) auf Hintergrundfarbe zurücksetzen

As a software implementation, the edge list algorithm and the edge flag algorithm are comparably fast, but implemented in hardware the latter is considerably faster.

literature

• James D. Foley et al: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6 .
• David F. Rogers: Procedural Elements for Computer Graphics. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5 .
• Peter Shirley et al: Fundamentals of Computer Graphics. AK Peters, Wellesley 2005, ISBN 1-56881-269-8 .

Individual evidence

1. ^ Donald E. Knuth : A note on digitized angles. In: Electronic Publishing — Origination, Dissemination, and Design. 3, 2, May 1990, pp. 99-104, ISSN  0894-3982 .
2. ↑ James D. Foley et al. Computer Graphics: Principles and Practice. P. 97.
3. ↑ Bryan Ackland, Neil Weste: Real time animation playback on a frame store display system. In: ACM SIGGRAPH Computer Graphics. 14, 3, July 1980, pp. 182-188, ISSN  0097-8930 .
4. ↑ Michael Dunlavey: Efficient polygon-filling algorithms for raster displays. In: ACM Transactions on Graphics. 2, October 4, 1983, pp. 264-273, ISSN  0730-0301 .
5. ^ Bryan Ackland, Neil Weste: The edge flag algorithm - a fill method for raster scan displays. In: IEEE Transactions on Computers. 30, January 1, 1981, pp. 41-48, ISSN  0018-9340 .
6. ^ Turner Whitted, David Weimer: A software test bed for the development of 3-D raster graphics systems. In: ACM SIGGRAPH Computer Graphics. 15, 3, August 1981, pp. 271-277.