CSci 480 Lecture Notes

(Fall) Week Three, Wednesday; (Summer) Week One, Thursday: Basic Raster Graphics Algorithms, Continued

3.3 Scan Converting Circles

There are several bad ways to do this. Solve the circle equation to get y = f(x) = sqr(R^2 - x^2). It's inefficient (sqr() function is slow) and gets increasing gaps with increasing x. Another inefficient method plots R * cos(theta) by steps.

Eight-Way Symmetry

We can do a whole circle by computing a 1/8 circle arc and mirroring it using the CirclePoints() function.

Midpoint Circle Algorithm

Consider only 45 degrees, the second octant. Select which of two pixels is closer to the ideal circle by evaluating a function at the midpoint between the the two pixels.

The only difference between this algorithm and the midpoint line algorithm is that in updating d, we evaluate a linear function in the line version.

3.4 Filling Rectangles

Basic questions: Which pixels to fill? What values to fill them with?

Spatial coherence: generally no change from pixel to pixel.

Span coherence: for solid shades, all pixels on a span are set to the same value.

Rectangles exhibit scan-line coherence: consecutive scan lines are identical.

The algorithm is a simple nested for() loop.

Need a rule for shared edges: don't draw bottom and left, but draw top and right pixels. This also applies to arbitrary polygons, but has some errors.

3.5 Filling Polygons

A number of complex issues come into play in filling polygons. The scan conversion algorithm described in the text handles general polygons, ones that are self-intersecting or have interior holes.

We want to draw only those pixels that are strictly interior to the region.

  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 the pixels using the odd-parity rule.
    1. Fractional x intersections: which pixel is interior?
    2. Case of integer intersections?
    3. Case of shared vertices?
    4. Horizontal edge vertices?

Horizontal Edges

Don't count the vertices. Does not work perfectly: omits pixels. As before, this is better than writing them several times.

Slivers

There is the problem of missing pixels in thin slivers, a variant of the aliasing problem.

Edge Coherence and the Scan-Line Algorithm

See program 3.6, LeftEdgeScan().

The Scan-Line algorithm takes advantage of edge coherence and scan line coherence using two edge tables, a global edge table, ET, and a table for the line currently being scanned, the active edge table (AET).

This page established September 15, 1998; last updated September 12, 1999.