Polygon fill algorithms
Today I read an interesting article on fill algorithms and decided to supplement it a bit. If the original article talked about filling in arbitrary areas, then we'll talk about a particular, but more common case of filling polygons.
In this topic, we consider three groups of algorithms:
Using this algorithm, you can paint over any closed areas. The initial data for this algorithm are the color of the boundary of the region and the point belonging to this region (the so-called seed pixel). The essence of the method is as follows: we take the seed point and paint over it. For each unfilled neighbor, we perform a similar procedure. T.O. we get a recursive algorithm, the description of which on the pseudo-code is presented below:
Of course, you can use both a four- and eight-connected neighborhood.
This algorithm has more drawbacks than advantages: it is slow and consumes a lot of memory for the stack, so it will be much more correct to go on to the next group of algorithms.
This algorithm is only suitable for cases where the shaded area can be specified as a polygon. We assume that we are working with a polygon with vertices P1, P2, ..., PN, P1 and we want to display it on the screen along with all the internal points. For convenience, we assume that each edge of the polygon is given by the coordinates of its ends x1, y1 and x2, y2 (with y2≥y1). We also agree that the x coordinate increases when moving from left to right, and the y coordinate when moving from top to bottom.
The vast majority of polygon rasterization algorithms are based on the following assumption: any secant line intersects the polygon boundary an even number of times. This statement is only true in two cases:
These two cases are quite easy to detect, therefore, when considering algorithms for rasterizing polygons, we assume that the above assumption is always true. The algorithm based on working with a list of edge points consists of three main stages: At the first stage, all non-horizontal edges of the polygon are rasterized. For each y value, a list of x-coordinates filled in during rasterization is compiled. For example, for the polygon in question, we get the following values (when moving clockwise): At the second stage, for each value of y, the lists are sorted in ascending order. After that, the lists will look as follows: At the third stage, for each y, all received segments are filled.
The advantage of this algorithm is that each pixel is processed strictly once. T.O. it can be argued that this algorithm is suitable for devices where access to video memory takes a relatively long time.
There is a modification of this algorithm, optimized for memory consumption. In it, at each step, only those edges are processed that intersect with the current scan line.
This polygon rasterization method is based on the properties of a logical XOR operation. This algorithm, like the algorithm with a list of edge points, starts with rasterizing the borders. After the boundaries are built, the shading is reduced to filling in the gaps in each line between two shaded points.
Imagine the image as a binary array I. We agree that I [x; y] = 1 when the pixel is shaded, and I [x; y] = 0 when the pixel is not shaded. It is easy to see that applying the operation I [x + 1, y] = I [x; y] XOR I [x + 1; y] to all the pixels in a row will produce an almost perfect result. As a result of this operation, all gaps will be filled, but the last pixel in each gap will not be filled. In most cases, this error is insignificant and imperceptible, but if you want to get an accurate result, you can re-display the borders on the screen after completing the algorithm, or use a small modification of this algorithm.
The advantage of this algorithm is its extreme simplicity and high speed. The disadvantage is that the algorithm cannot work if there are extraneous images.
The XOR method for faces is described by the following simple algorithm: For each edge in the polygon, the colors of all the pixels located to the right of this edge are inverted. Moreover, the order of traversing the edges does not matter. The table shows the steps of this algorithm (clockwise movement): The disadvantage of this algorithm is its high time consumption, as some pixels are processed more than once. In addition, the greater the distance from the image to the right border of the screen area, the more unnecessary operations will be performed.
A modified version of the XOR algorithm for faces is free from some of the shortcomings. It is called the XOR algorithm for partitioned faces. His idea is to invert the region not between the edge and the border of the screen, but between the edge and a special vertical line (the so-called partition). Most often, the partition is held so that it intersects the polygon. The steps of the algorithm are given in the table.
In this topic, we consider three groups of algorithms:
- Seed Fill Algorithm
- Algorithms with a list of edge points
- XOR Algorithms
Seed Fill Algorithm
Using this algorithm, you can paint over any closed areas. The initial data for this algorithm are the color of the boundary of the region and the point belonging to this region (the so-called seed pixel). The essence of the method is as follows: we take the seed point and paint over it. For each unfilled neighbor, we perform a similar procedure. T.O. we get a recursive algorithm, the description of which on the pseudo-code is presented below:
1. Place the seed pixel on the stack ;
2. Extract a pixel from the stack ;
3. Assign the desired value to the pixel ( color of the inner area ) ;
4. Add each neighboring pixel to the stack, if it is
4.1. It is not boundary ;
4.2. Not processed earlier ( i.e. its color differs from the color of the border or the color of the inner region ) ;
5. If the stack is not empty, go to step 2.6
Of course, you can use both a four- and eight-connected neighborhood.
This algorithm has more drawbacks than advantages: it is slow and consumes a lot of memory for the stack, so it will be much more correct to go on to the next group of algorithms.
Algorithms with a list of edge points
This algorithm is only suitable for cases where the shaded area can be specified as a polygon. We assume that we are working with a polygon with vertices P1, P2, ..., PN, P1 and we want to display it on the screen along with all the internal points. For convenience, we assume that each edge of the polygon is given by the coordinates of its ends x1, y1 and x2, y2 (with y2≥y1). We also agree that the x coordinate increases when moving from left to right, and the y coordinate when moving from top to bottom.
The vast majority of polygon rasterization algorithms are based on the following assumption: any secant line intersects the polygon boundary an even number of times. This statement is only true in two cases:
- When the secant line contains an edge;
- When a secant line contains a vertex, and adjacent edges lie on one side of the secant line.
These two cases are quite easy to detect, therefore, when considering algorithms for rasterizing polygons, we assume that the above assumption is always true. The algorithm based on working with a list of edge points consists of three main stages: At the first stage, all non-horizontal edges of the polygon are rasterized. For each y value, a list of x-coordinates filled in during rasterization is compiled. For example, for the polygon in question, we get the following values (when moving clockwise): At the second stage, for each value of y, the lists are sorted in ascending order. After that, the lists will look as follows: At the third stage, for each y, all received segments are filled.
The advantage of this algorithm is that each pixel is processed strictly once. T.O. it can be argued that this algorithm is suitable for devices where access to video memory takes a relatively long time.
There is a modification of this algorithm, optimized for memory consumption. In it, at each step, only those edges are processed that intersect with the current scan line.
XOR Algorithms
XOR line-by-line processing
This polygon rasterization method is based on the properties of a logical XOR operation. This algorithm, like the algorithm with a list of edge points, starts with rasterizing the borders. After the boundaries are built, the shading is reduced to filling in the gaps in each line between two shaded points.
Imagine the image as a binary array I. We agree that I [x; y] = 1 when the pixel is shaded, and I [x; y] = 0 when the pixel is not shaded. It is easy to see that applying the operation I [x + 1, y] = I [x; y] XOR I [x + 1; y] to all the pixels in a row will produce an almost perfect result. As a result of this operation, all gaps will be filled, but the last pixel in each gap will not be filled. In most cases, this error is insignificant and imperceptible, but if you want to get an accurate result, you can re-display the borders on the screen after completing the algorithm, or use a small modification of this algorithm.
for y : = 1 to YMax do
begin
fl : = false ;
for x : = 1 to XMax do
begin
if I [ x , y ] = 1 then
fl : = not fl;
if fl then
I [ x , y ] : = 1 ;
end ;
end ;
The advantage of this algorithm is its extreme simplicity and high speed. The disadvantage is that the algorithm cannot work if there are extraneous images.
XOR Algorithm for Faces
The XOR method for faces is described by the following simple algorithm: For each edge in the polygon, the colors of all the pixels located to the right of this edge are inverted. Moreover, the order of traversing the edges does not matter. The table shows the steps of this algorithm (clockwise movement): The disadvantage of this algorithm is its high time consumption, as some pixels are processed more than once. In addition, the greater the distance from the image to the right border of the screen area, the more unnecessary operations will be performed.
XOR Algorithm for Partitioned Faces
A modified version of the XOR algorithm for faces is free from some of the shortcomings. It is called the XOR algorithm for partitioned faces. His idea is to invert the region not between the edge and the border of the screen, but between the edge and a special vertical line (the so-called partition). Most often, the partition is held so that it intersects the polygon. The steps of the algorithm are given in the table.
