University of California, Berkeley
EECS Dept, CS Division
Jordan Smith SLIDE: Scene Language for
Interactive Dynamic Environments
Prof. Carlo H. Séquin

Home Goals Publications People Gallery Assignments Distributions

Assignment 7: Scan Conversion and Z-Buffering


In this assignment, you are building slidescan, a polygon scan converter which implements a Z-Buffer algorithm for visibility calculations. The scan conversion algorithm will compute a winding number for each polygon at each pixel and will fill the area outlined by the polygon boundary according to the parity rule or the non-zero winding number rule depending on the currently selected option.

Rendering Options

New options appear in bold.

Scan Conversion

See the class notes on scan conversion.

You will be using a software frame buffer to hold the intermediate results of the scan conversion. This buffer is width x height of the window where the first element (0, 0) is the bottom left hand corner of the window. As you set the color of each pixel that is interior to a polygon, you will add the color of that pixel to the current color of the frame buffer if it has the same Z value of the pixel currently stored. This will help you to identify pixels that have erroneously been assigned to multiple polygons. After rendering all of the polygons in one render statement to the software frame buffer, the contents of that buffer will be drawn to the screen with the GLDrawPixels command.

In the scan converter, you will be given the list of vertices around the polygon. These vertices will be in their full 4D Homogeneous form in the canonical half cube. You will need to apply the homogeneous division by W and apply the viewport mapping matrix Gvp<-proj.

For each polygon in the scene, after it has been fully transformed and clipped, scan convert that polygon to the software frame buffer by the following steps:

  1. Create a list of all of the edges in the polygon, sorted by the y-coordinate of their lower ends. This is the edge list

  2. Start at the lower y-coordinate of the viewport. Create an empty list of edges, called the active edge list (AEL).

    For each scanline:

    1. Move all edges that begin at or before the current scan line from the edge list to the active edge list. (ymin <= yscan)

    2. Remove all edges that end at or before the current scan line from the active edge list. (ymax <= yscan)

    3. Initialize or update the x-intercept values and other changing values for the edges in the active edge list.

    4. Sort the active edge list by the x-intercept value with the current scan line.

    5. Color all pixels that are ``interior'' to the polygon within the current scan line according to the current fill rule. (ceil(xleft) <= x <= ceil(xright)-1)


Along with the frame buffer that holds the pixel color values, you will have a Z-Buffer which is an array of 8 bit integers. After the homogeneous divide, all of your Z values will be in the range [0, -1]. You need to convert the current Z value to an 8 bit integer for each pixel, check to see if this value against the current value, and only contribute to the frame buffer if the current value is closer than the previous value.

When updating Z, you should compute a dz/dy and dz/dx for the polygon and use these deltas to incrementally calculate the current Z value.

Getting Started

Follow the listed instructions for as7.

Here is a pre-compiled reference solution (Windows .exe in .zip format).

SLIDE Implementation Specification

The SLIDE Implementation Specification gives information about the C++ class structure which implements the SLIDE viewer. It also gives an outline of the operation of the viewer.

Submission Details

  1. This assignment is to be done in pairs. You can settle down with a partner who you may keep for the rest of the semester.
  2. Follow the listed instructions for as7.

This page was originally built by Jordan Smith.

Last modified: Wednesday, 27-Oct-2004 16:26:01 PDT