Assignment #2 -- FAQs


Here are the answers to the most frequently asked questions on the conventions you need to implement for assignment #2.

1. Snap vertices to pixel centers

The algorithm in H&B assumes that the vertex positions are integer coordinates (or can be somehow converted to integers). To make your lives easier we will use the same assumption and convert the floating point vertex coordinates (that range between 0.0 and 1.0) to integer coordinates (that range between 0 and 49) by snapping every vertex to the center of each pixel they are in before starting the scan conversion.

Below is a picture of a simple 4x4 grid of pixels. The red vertices are the original floating point vertices (the ones that you read in from the file). Each red vertex is snapped to the center (black vertices) of the pixel they are in. If a vertex is right between two pixels, then you should choose the left/bottom one. If a vertex is right at the corner of 4 pixels, then you should choose the bottom-left. For example v3 is between pixel (3,0) and (3,1) and is therefore snapped to (3,0).

Your program should display and scan convert the black polygon (not the red one).

2. Picking pixels at intersection points

Remember that when scan converting polygons that share an edge we need to make sure that the pixels along the edge should be filled by only one of the polygons, i.e. polygons that do not overlap in continuous space should not overlap in pixel space. The convention we chose in the class was to fill left and bottom of the polygon and leave right and top empty whenever there is an ambiguity.

You already know what to do for top and bottom rows. The main question is to decide what to do for left and right sides of a polygon during scan converting a given scanline, i.e you have a fractional x intersection value (xi) and you need to decide which integer to choose. H&B proposes to either rounding the number or flooring it. Unfortunately neither is enough to resolve the ambiguities. We need something better.

In order to solve our problems we will use the following convention: whenever the center of a pixel is inside the polygon we will fill that pixel no matter which side of the polygon it is (left, right, top or bottom). Note that for this case there is no ambiguity since the center of a pixel can only be in one polygon. However if the center of the pixel lies on an edge or a vertex of a polygon, then the pixel will be filled if and only if it's on the left (i.e. it corresponds to an odd numbered intersection).

Let's look at the two cases for the left side:

Case 1: The left edge goes through two pixel centers. The right one is filled since the center of the left one is not in the polygon:

Case 2: This one shows the ambiguous case where the edge goes through the center of the pixel. Since it's a left edge we fill it in:

Taking the ceil(xi) of the intersection value xi would take care of the both cases above (remember due to snapping step above the pixel centers correspond to integer values).

Now, let's look at cases for the right side:

Case 1: The right edge goes through two pixel centers. The left one is filled since the center of the right one is not in the polygon:

Case 2: This one shows the ambiguous case where the edge goes through the center of the pixel. Since it's a right edge we do not fill it in:

Taking the ceil(xi-1.0) of the intersection value xi would take care of the both cases above.


Questions should be posted to the news group