CSci 480 Lecture Notes

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

Overview

Primitives: ideal mathematical objects. We need to approximate these with sets of pixels. For this we need some low level graphics algorithms.

Implications of Display-System Architecture


                  ----------Output Pipeline----------->

  Application --> Application  --Output primitives----> SRGP <--> Display
  Model       <-- Program      --Output attributes---->           Hardware
                               --Canvas control------->
                               --copyPixel------------>
                               --Input device control->
                               <-Input device measures-

                  <----------Input Pipeline------------
The graphics package (SRGP in this case) gives the program a device-independent interface to the hardware. This is achieved by providing separate versions of a package for each type of hardware.

Output Pipeline

Primitives are clipped and scan converted by the graphics package. That is, the application programmer doesn't have to worry about it.

Displays with frame buffers and display controllers. A hardware display controller is used in some high-end graphics machines, such as Silicon Graphics workstations.

Displays with frame buffers only. This is the typical situation with personal computers and inexpensive Unix workstations.

Hardcopy devices. Sending images to film recorders or printers is generally problematic. Separate algorithms must generally be used because hard copy devices are usually quite different from video displays in both their resolution and color depth.

Scan Converting Lines

Pixel: point or rectangle (not necessarily square). Macintosh rectangle (x1, y1, x1, y1) has zero extent. Usually that rectangle contains one pixel (SRGP, Java, etc.).

Basic Incremental Algorithm

The fundamental problem is that the ideal line is represented with floating point arithmetic, whereas pixels are represented as integers. The brute force strategy (pick the pixel nearest the ideal line) is inefficient.

In the basic incremental algorithm, we increment x, and pick y based on the slope m and rounding off.

Midpoint Line Algorithm

Rounding a floating point value to an integer takes time. The midpoint algorithm is much faster because it uses all-integer arithmetic.

Additional Issues

Endpoint order: a line drawn from a to b must look the same as a line drawn from b to a.

Clip edges: The starting point might have a floating point y value.

Intensity and slope: A line at a 45 degree angle has a lower pixel density.

Shared pixels in polylines: don't draw them twice.

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