Polygon Filling
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.
An Efficient Polygon Filling Algorithm
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.
Scan Line Single Polygon Filling
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.
Scan line Intersection of a Vertex
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.
Edge Coherence
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:
yi+1 - yi = 1
|
Therefore: |
xi+1 |
= xi + 1/m |
(1/m is the inverse slope) |
|
And: |
1/m |
= x2 - x1 |
Active Edge Table (AET)
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 x-intersection order so that sequences (runs) of pixels are easily determined.
Edge Table (ET)
To make the addition and removal of edges to the AET more efficient we create an edge table (ET) containing all non-horizontal 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).
Efficient Algorithm for Scan Line Single Polygon Filling
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 non-empty 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 = ymax.
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.
Hidden Surface Removal
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.
A Simple Algorithm for Hidden Surface Removal:
The z-Buffer Algorithm
The z-buffer (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 z-buffer.
The z-buffer 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 z-buffer value at (x,y) then:
a. Place z into the z-buffer at position (x,y)
b. Place pixel value of current polygon into the refresh buffer at position (x,y)
Calculation of a Polygon's depth at any point along a scan-line
In order to use the z-buffer algorithm (or any other hidden surface removal algorithm) we need to be able calculate each polygon's depth at each pixel along a scan-line.
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 end-points, we can interpolate along the edge to calculate its depth for each scanline that intersects it.
There will be y2-y1 interpolation steps. The depth that will be interpolated will go from z1 to z2; 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 scan-line. We can use:
A. interpolation;
B. the polygon's plane equation.
A. Interpolation
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 xe2-xe1 interpolation steps. The depth that will be interpolated will go from ze1 to ze2; 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.
B. the polygon's plane equation
The equation of a plane is:
nxx + nyy + nzz + d = 0
where:
· (x,y,z) is any point on the plane;
· (nx,ny,nz) is the normal to the plane;
· -d = nx*x + ny*y + nz*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:
· xi+1 - xi = 1;
· yi+1 - yi = 0.
Therefore:
equals:
equals:
Rearranging gives:
The above formula means that if we know the depth of a polygon at position (xi,y) along the scanline (i.e zi), we can calculate the polygon's depth (zi+1) for the next pixel (xi+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 nx/nz is constant for any given polygon, so it need only be calculated once for each polygon. The value nx/nz can be added to the Polygon Table for a given polygon.
WORKED EXAMPLE:
Calculation of a Polygon's Depth
A polygon is defined in a left-handed coordinate system in a clockwise order by the three vertices:
· V1(5,3,100)
· V2(120,20,15)
· V3(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 V1V3 between two adjacent scanlines is:
As the scanline advances, the depth along edge V1V3 changes as shown below:
|
Scanline |
depth along edge V1V3 |
|
1 |
not affected |
|
2 |
not affected |
|
3 |
100 |
|
4 |
90 |
|
5 |
80 |
|
6 |
70 |
|
7 |
60 |
|
8 |
50 |
Therefore, the depth along edge V1V3 at scanline y=8 is 50.
Similarly, the change of depth between adjacent scanlines along edge V1V2 is:
|
(15-100) / (20-3) |
|
|
= |
-5 |
and the depth along edge V1V2 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 V1V3:
= -0.44444444444
Therefore the x coordinate on the edge V1V3 for each scanline is:
|
Scanline |
Edge V1V3 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 V1V3 has an x coordinate of value 3 at scanline y=8.
Similarily, polygon edge V1V2 inverse slope is:
|
(120-5) / (20-3) |
|
|
= |
6.764705882 |
and the polygon's edge V1V2 has an x coordinate of value 38.82352941 (rounded to 39) at scanline y=8.
Summary so far:
For scanline y=8
Edge V1V3:
x = 2.77777778 (rounded to 3)
z = 50
Edge V1V2
x = 38.82352941 (rounded to 39)
z = 75
Calculation of polygon's depth:
Interpolation along the scanline
where:
· edge e1 is V1V3
· edge e2 is V1V2
Plugging in the values gives:
zi+1 = zi + 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 |
= (nx,ny,nz) |
|
= (ay*bz - az*by, az*bx - ax*bz, ax*by - ay*bx) |
where:
|
(ax,ay,az) |
= first vertex - third vertex |
|
= (4, -9, 90) |
and
|
(bx,by,bz) |
= second vertex - third vertex |
|
= (119, 8, 5) |
|
n |
= (-765,10690,1103) |
|
The stepsize is -nx/nz |
= 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.
Advantages and Disadvantages of the Z-Buffer Hidden Surface Removal Algorithm
The advantage of the z-buffer algorithm is that it is easy to implement.
Three problems associated with the z-buffer algorithm are:
· The z-buffer requires that a memory block the size of the resolution of the screen is available.
· The z-buffer algorithm is inefficient. Every point in every polygon is compared against the z-buffer.
· 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.
Efficient Scan Line Algorithm for Several Polygons
A more efficient polygon filling algorithm than the z-buffer algorithm is based on the Single Polygon Scan Conversion Algorithm discussed earlier.
Polygon Table (PT)
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 non-horizontal 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 x-increment (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.
Example
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.
Efficiency
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 z-depth comparison between it and the currently visible polygon. We do not need to compare the new polygon against any currently hidden polygons.