Aliasing and Antialiasing

EECE 478

Lecture notes for January 12, 2001

Aliasing and Antialiasing

Since the resolution of a screen is limited, we can see jaggies (or staircases) on a line drawn using the algorithms described before. This undesirable effect is due to the all-or-nothing approach to scan conversion. This phenomenon is called aliasing.

To reducing aliasing, there are some antialiasing methods.
1. Increasing Resolution

By increasing the resolution, the appearance of the lines will be improved but the jaggies effect would not be removed. Also, this will require more memory and increase scan conversion time.

2. Adjusting Pixel Intensities along the Line Path

A. Varying Intensity of Lines as a Function of Slope

Since the densities of the pixels along lines with different slopes are different, slope line intensities are adjusted according to horizontal and vertical lines. Horizontal and vertical lines with minimum intensity and 45 degree lines are given max intensity. The number of pixels turned on for a 45 degree line is the same as that for a horizontal but the length of this 45 degree line is 2 times longer, so its intensity has to be increased by 2 times.

B. Overlapping Axes

A pixel is a spot covering a small area of the screen. Lines have a width equal to that of a pixel. We may think that any line as a rectangle covering a portion of a grid, which may represents a screen, as shown in the figure below.


Then only the squares (or pixels) covered by line will be turned on. To perform antialiasing, the intensity of each square depends on how much the square is covered by the line. If a square is totally inside the line, it will have 100% of intensity, otherwise, it will only have an intensity proportional to the area covered.

The problem of this method is that it will complicate the scan conversion algorithm a lot.

3. Pixel Phasing

Intensities of line edges are adjusted by micro-partitioning of the electron beam. Individual pixel can be shifted by a fraction of a pixel diameter.

Polygon Area Filling

A polygon can be formed by at least three connecting lines. (That is a triangle if there are only three lines.) To fill this polygon, filling algorithms are required.

Filling Algorithms

• 
  Decide what pixels to fill
  
• 
  Decide what value to fill them (solid/pattern)
  
  • 
    Regions of pixels
    

Fill algorithms

• 
  Primitives: rectangles/polygons
  

Scan line algorithms

Filling Regions of Pixels

• 
  Choose any point inside the region to be filled.
  
• 
  For 4-connectivity, check the 4 pixels to the left, right, up and down of this pixel.
  
• 
  Turn on those inside the region and not turned on yet.
  
• 
  Repeat the same process for those pixels just being switched on until no more “new” pixels in the region being found.
  
• 
  For 8-connectivity, the idea is the same but this time all 8 neighbours of a pixels will be checked.
  

Filling Rectangles

Fill each span (segment of scan-line containing the rectangle) from x_min to x_max while traveling from y_min to y_max (reversing the order is trivial of course).


Span exhibit a primitive’s COHERENCE, the degree to which parts of an environment or its projection exhibit local similarities.

• 
  Spatial coherence:
  

Primitives do not often change from pixel to pixel within a span or consecutive span lines(look only for pixels where change occurs, such as boundaries)

• 
  Span coherence:
  

Primitives do not often change from span to span (e.g., all pixels set to same value for solidly shaded polygon).

• 
  Scan-line coherence:
  

Not much change between successive scan-lines(e.g., consecutive scan-lines that intersect rectangle are identical).

• 
  Edge coherence:
  

Edges of polygon intersect successive scan-lines (continuity of edges, will be useful later).

• 
  Coherence greatly increases efficiency of scanline algorithms (can output an entire span or scan-line rather than pixel by pixel).
  

• 
  Problem: boundary pixels may be drawn several times for shaded edges. (what colour should a shared edge be?)
  

• 
  Partial solution, only draw “left” and “bottom” edges (skip right and top)
  

• 
  Problem with this is that the left/bottom vertex still drawn twice, not so good for unfilled polygons there is no perfect solution)
  

Filling Polygons

• 
  Basic Idea: intersect the polygon with consecutive scan-lines and check for points of intersection (i.e. Compute and fill the spans)
  

• 
  Digression: nice example of a problem in computation geometry (simple for us humanoids, but more complex for computers as we shall see.)
  

• 
  Could determine span extrema (outer most pixels of a span), using midpoint algorithm, but watch out for extrema outside of polygon (want to fill the interior)