Copyright Derek O'Reilly, Dundalk Institute of Technology (DkIT), Dundalk, Co. Louth, Ireland.
Very often the region to be displayed is described in terms of polygons. Efficient polygon filling algorithms operate on one scanline at a time, filling in that part of the polygon that lies on the current scanline of the monitor.
For each scanline, we must determine which pixels are inside the polygon. These can then be set to some desired colour.
We can test each pixel against the polygon to see if it lies inside or outside. Obviously, this is very inefficient.
In developing an efficient polygon filling algorithm, we make the following two observations:
a. In general, a polygon does not change significantly as we move between adjacent scan lines.
b. In general, a polygon does not change significantly between two adjacent pixels.
i.e. Pixels tend to be grouped as "runs" within a polygon.
Firstly, we shall develop a scan line region filling algorithm dealing with the simple case of having only a single polygon.
Then, we shall develop the general case of having several polygons.
One scan line of a polygon can be filled in by a three step process:
1. Find the intersections of the scan line with all edges of the polygon.
2. Sort the intersections by increasing x coordinate.
3. Fill in all pixels between pairs of intersections.
From step 3), we note that if there are an odd number of intersections then the algorithm will not work. This will be the case if the scan line intersects the vertex of a polygon and thereby introduces the same value twice into the intersection list.
It is not valid to simply remove one of the two vertices from the list. We need to include the vertex twice if it represents a local minimum or maximum, otherwise include the vertex only once. To find out which vertices are local minimum and maximum is computationally expensive.
An easier way to ensure that vertices are never intersected by a scanline is to shorten one of the polygon's edges. This needs only be done when a vertex is found to intersect the scan line.
We can use edge coherence to improve Step 1) of the scanline algorithm.
Edge coherence means that if a scan line intersects an edge then it is very probable that the next scan line will also intersect the edge.
As we move from one scan line to the next we can compute the x intersection of the edge based on the old x intersection:
The slope of the line is:
m 

Rearranging gives:
As we are moving exactly one scan line down:
y_{i+1}  y_{i} = 1
Therefore: 
x_{i+1} 
= x_{i} + 1/m 
(1/m is the inverse slope) 
And: 
1/m 
= x_{2}  x_{1} 
For any scan line we work with, we need a list of the polygon edges it intersects. The intersected edges of the CURRENT scan line are kept in an active edge table (AET).
As we move from one scan line to the next scan line:
· any edges from the AET that are not intersected by the new scan line are removed from the AET.
· new x intersections are calculated using the inverse slope formula (from previous webpage).
· any new edges that intersect the scan line are added to the AET.
The edges in the AET are kept sorted in ascending xintersection order so that sequences (runs) of pixels are easily determined.
To make the addition and removal of edges to the AET more efficient we create an edge table (ET) containing all nonhorizontal edges, sorted by their smaller y coordinate.
The ET is built by using a bucket sort, with one bucket for each scan line.
Within each bucket, edges are kept in order of increasing x coordinate of the lower endpoint.
Each entry in the ET contains:
· the larger y coordinate of the edge
· the x coordinate of the lower endpoint
· the x increment used in stepping from one scan line to the next (the inverse slope).
Once the ET has been formed, the processing steps for the scan line algorithm are:
1. Set y to the smallest y coordinate that has an entry in the ET. (i.e. the first nonempty bucket);
2. Initialise the AET to be empty;
3. Repeat until the AET and ET are empty:
3.1 Fill in desired pixel values on scan line y by using pairs of x coordinates from the AET.
3.2 Remove from the AET those entries for which scanline y = y_{max}.
3.3 For each entry remaining in the AET, replace x by x + 1/m.
3.4 Increment y by 1, thereby moving onto the next scan line.
3.5 Move information from ET bucket y into the AET, maintaining AET sort order on x.
Dealing With Several Polygons
Dealing with several polygons means that we need to deal with hidden surfaces.
When more than one polygon is being displayed two, or more, polygons may overlap on the screen.
If this happens, then only one polygon's face should be displayed and all other polygons should be hidden.
It would be inefficient to compare every polygon at every pixel when deciding which polygon (if any) should be displayed at the pixel.
There are several ways to reduce the number of calculations for polygon/pixel and polygon/polygon intersection.
The zbuffer (or depth buffer) algorithm requires that we have a second memory buffer that is the same size as the screen resolution. This second memory buffer is called the zbuffer.
The zbuffer is initialised to the largest allowable z value, while the video RAM is initialised to the background pixel value.
Each polygon in turn is scan converted into video RAM.
No sorting of the polygons prior to scan converting is necessary.
During the scan conversion, the following steps are performed for each point (x,y) inside a polygon.
1. Calculate the polygon depth, z, at position (x,y).
2. If z < current zbuffer value at (x,y) then:
a. Place z into the zbuffer at position (x,y)
b. Place pixel value of current polygon into the refresh buffer at position (x,y)
In order to use the zbuffer algorithm (or any other hidden surface removal algorithm) we need to be able calculate each polygon's depth at each pixel along a scanline.
The only depth information that we have to begin with is the polygon's depth at each of its vertices.
Calculating the depth involves:
1. Calculate the change in depth along each edge as we move down one scanline.
2. Calculate the change of depth as we move along a scanline between two edges of a ploygon.
1. Calculate the change in depth along each edge as we move down one scanline.
Given the depth of a polygon's edge at its two endpoints, we can interpolate along the edge to calculate its depth for each scanline that intersects it.
There will be y_{2}y_{1} interpolation steps. The depth that will be interpolated will go from z_{1} to z_{2}; therefore the change in depth as the scanline advances one row is:
This stepsize will be constant for a given edge, so we need only calculate the formula once for each edge. The formula can be added into the Edge Table for the given edge.
2. Calculate the change of depth as we move along a scanline between two edges of a ploygon.
There are two methods that we can use to calculate z for any (x,y) position of a polygon along a scanline. We can use:
A. interpolation;
B. the polygon's plane equation.
Given that we can calculate a polygon's depth at its two edges for any scanline we can interpolate between the two edges to find the polygon's depth along the scanline.
We know the x coordinate of the intersection of the scanline with each of the edges. We got this from the inverse slope.
There will be x_{e2}x_{e1} interpolation steps. The depth that will be interpolated will go from z_{e1} to z_{e2}; therefore the change in depth as the scanline advances one pixel is:
Calculating the stepsize using the polygon edge's on any scanline will result in the same answer. The stepsize is constant for a given polygon, so we need only calculate the formula once for each polygon. The formula can be added into the Polygon Table for the given polygon.
The equation of a plane is:
n_{x}x + n_{y}y + n_{z}z + d = 0
where:
· (x,y,z) is any point on the plane;
· (n_{x},n_{y},n_{z}) is the normal to the plane;
· d = n_{x}*x + n_{y}*y + n_{z}*z
we are looking for z, so:
Given two adjacent polygon points on a scanline
The difference in depth between the two points is:
As we scan through adjacent pixels on the same scan line:
· x_{i+1}  x_{i} = 1;
· y_{i+1}  y_{i} = 0.
Therefore:
equals:
equals:
Rearranging gives:
The above formula means that if we know the depth of a polygon at position (x_{i},y) along the scanline (i.e z_{i}), we can calculate the polygon's depth (z_{i+1}) for the next pixel (x_{i+1},y) along the scanline. As with interpolation, when processing a scanline, only one subtraction is needed to calculate the depth of a polygon at (x + 1,y) given its depth at (x,y).
The value n_{x}/n_{z} is constant for any given polygon, so it need only be calculated once for each polygon. The value n_{x}/n_{z} can be added to the Polygon Table for a given polygon.
Calculation of a Polygon's Depth
A polygon is defined in a lefthanded coordinate system in a clockwise order by the three vertices:
· V_{1}(5,3,100)
· V_{2}(120,20,15)
· V_{3}(1,12,10)
What is the polygon's depth at each pixel along the scanline y=8?
Interpolation of the polygon's two edges' depths:
The change in depth along the edge V_{1}V_{3} between two adjacent scanlines is:
As the scanline advances, the depth along edge V_{1}V_{3} changes as shown below:
Scanline 
depth along edge V_{1}V_{3} 
1 
not affected 
2 
not affected 
3 
100 
4 
90 
5 
80 
6 
70 
7 
60 
8 
50 
Therefore, the depth along edge V_{1}V_{3} at scanline y=8 is 50.
Similarly, the change of depth between adjacent scanlines along edge V_{1}V_{2} is:
(15100) / (203) 

= 
5 
and the depth along edge V_{1}V_{2} at scanline y=8 is 75
The polygon's two edges' x coordinates for the intersection of the scanline are calculated (using the inverse slope) as:
Edge V_{1}V_{3}:
= 0.44444444444
Therefore the x coordinate on the edge V_{1}V_{3} for each scanline is:
Scanline 
Edge V_{1}V_{3} X coordinate 
Rounded 
1 
not affected 

2 
not affected 

3 
5 
5 
4 
4.5555556 
5 
5 
4.1111111 
4 
6 
3.6666667 
4 
7 
3.2222222 
3 
8 
2.7777778 
3 
The polygon's edge V_{1}V_{3} has an x coordinate of value 3 at scanline y=8.
Similarily, polygon edge V_{1}V_{2} inverse slope is:
(1205) / (203) 

= 
6.764705882 
and the polygon's edge V_{1}V_{2} has an x coordinate of value 38.82352941 (rounded to 39) at scanline y=8.
Summary so far:
For scanline y=8
Edge V_{1}V_{3}:
x = 2.77777778 (rounded to 3)
z = 50
Edge V_{1}V_{2}
x = 38.82352941 (rounded to 39)
z = 75
Calculation of polygon's depth:
Interpolation along the scanline
where:
_{· } edge e1 is V_{1}V_{3}
_{· } edge e2 is V_{1}V_{2}
Plugging in the values gives:
z_{i+1} = z_{i} + 0.69356301
The change in depth along the scanline y=8 is:
x 
depth (z) 
3 
50 
4 
50.6936 
5 
51.3871 
6 
52.0807 
7 
52.7743 
8 
53.4678 
9 
54.1614 
10 
54.8549 
11 
55.5485 
12 
56.2421 
13 
56.9356 
14 
57.6292 
15 
58.3228 
16 
59.0163 
17 
59.7099 
18 
60.4034 
19 
61.0970 
20 
61.7906 
21 
62.4841 
22 
63.1777 
23 
63.8713 
24 
64.5648 
25 
65.2584 
26 
65.9519 
27 
66.6455 
28 
67.3391 
29 
68.0326 
30 
68.7262 
31 
69.4198 
32 
70.1133 
33 
70.8069 
34 
71.5005 
35 
72.1940 
36 
72.8876 
37 
73.5811 
38 
74.2747 
39 
74.9683 
Using the plane equation the polygon's normal vector n is:
n 
= (n_{x},n_{y},n_{z}) 
= (a_{y}*b_{z}  a_{z}*b_{y}, a_{z}*b_{x}  a_{x}*b_{z}, a_{x}*b_{y}  a_{y}*b_{x}) 
where:
(a_{x},a_{y},a_{z}) 
= first vertex  third vertex 
= (4, 9, 90) 
and
(b_{x},b_{y},b_{z}) 
= second vertex  third vertex 
= (119, 8, 5) 
n 
= (765,10690,1103) 
The stepsize is n_{x}/n_{z} 
= 765/1103 
= 0.69356301 
This is exactly the value we got for the interpolation method. Therefore, if we were to generate the table of depth values for the polygon's various x coordinates along the scanline y=8 it would be identical to the one shown above.
The advantage of the zbuffer algorithm is that it is easy to implement.
Three problems associated with the zbuffer algorithm are:
· The zbuffer requires that a memory block the size of the resolution of the screen is available.
· The zbuffer algorithm is inefficient. Every point in every polygon is compared against the zbuffer.
· Depending on the order that overlapping polygons are processed, a video RAM (x,y) location may be written to more than once, which is not visually pleasant.
A more efficient polygon filling algorithm than the zbuffer algorithm is based on the Single Polygon Scan Conversion Algorithm discussed earlier.
In addition to the edge table and active edge table that we have already discussed, a polygon table (PT) is used to hold (at least) the following information about each of the polygons:
· The coefficients of the polygon's plane equation;
· Colour information for the polygon.
· An in/out Boolean flag, which is used during scan line processing. It is initialised to FALSE.
We create an edge table (ET) for all nonhorizontal edges of all polygons.
Entries in the ET, which are sorted into buckets based on each edge's smaller y coordinate and within buckets based on x and then on inverse slope, contain:
· The x coordinate of the end of the edge with the smaller y coordinate;
· The y coordinate of the edge's other end.
· The xincrement (inverse slope) of the edge, which will be used when stepping to the next scan line.
· The polygon's identification, stating to which polygon an edge belongs.
We shall study how the scanline algorithm deals with the two polygons, ABCD and EFG, in the diagram above.
We shall only deal with the two scan lines, y1 and y2.
· Scan line y1
At scan line y1 the AET contains AD, BC, EG and EF, in that order. The edges are processed from left to right.
To process AD we first invert the in/out flag of polygon ABCD, so that it becomes TRUE. The scan line is now in the polygon, so the polygon must be considered. Because the scan is in only one polygon, that polygon must be visible, so the colouring for ABCD is applied from edge AD to the next edge in the AET (edge BC).
At this edge the flag for ABCD is inverted to FALSE, so the scan line in now not in any polygon.
The edges EG and EF are processed similarly, so that the colouring for polygon EFG is invoked.
Because EF is the last edge in the AET we proceed to the next scan line and we update the AET from the ET.
· Scan line y2
At scan line y2 the AET is AD, BC, EG and EF.
Entering polygon ABCD causes its flag to invert to TRUE, and its colouring is displayed up to the next entry in the AET, EG. At this point the flag for EFG also becomes TRUE, so the scan is in two polygons.
We determine which of the two polygons is nearest to the viewpoint by evaluating the plane equation of both polygons for z.
In this example, ABCD has a smaller z value and thus is visible. The colouring for ABCD is used up to the next edge in the AET, BC. At this point ABCD's in/outflag inverts to FALSE and the scan is in only in the polygon EFG, so EFG's colouring rules apply.
When we are dealing with several polygons, it is often the case that more than one polygon is hidden by a visible polygon.
Every time we enter a new polygon we need only perform a zdepth comparison between it and the currently visible polygon. We do not need to compare the new polygon against any currently hidden polygons.
Copyright Derek O' Reilly, Dundalk Institute of Technology (DkIT), Dundalk, Co. Louth, Ireland.