**
Grader: Kekoa Proudfoot
**

Recall Bresenhan's algorithm to draw a line (we've slightly simplified the procedure):

line(int x, int y, int n, int a, int b, int c) { int i; int e = a * x + b * y + c; for (i = 0; i < n; i++) { point(x, y); e += a; x += 1; if (e < 0) { y += 1; e += b; } } }

This procedure works for lines drawn in the first octant (slopes less than 45 degrees). It also assumes that the orientation of the line has been chosen so that vector (a,b) perpendicular to the line points upward and to the left.

One clever optimization that can be performed is to take two steps every time through the loop, in the process drawing two pixels instead of one. What are the possible two-step pixel patterns that may occur?

**Answer:**

**Remarks:**

This question was about two-step pixel patterns. There are four possible patterns; what distinguishes each pattern from the next is, for each of the two pixels, whether or not the step after that pixel goes straight to the right, or up and to the right.

**Grading:**

**5 points** were awarded to students who demonstrated, in their answer
to question 5A, that they recognized that all four cases were possible.

**4 points** were awarded to students who only answered that three cases
were possible. Usually, these students incorrectly eliminated the the
up-up case as a case that could not occur.

**3 points** were awarded to students that only reported two cases. A
majority of these students focused on the pixels themselves and not on the
steps taken after the pixels.

**1 point** was awarded to students that otherwise made a reasonable
attempt at an answer.

**0 points** were awarded to students who did not make a reasonable
attempt at an answer.

How would you modify the inner loop to distinguish between these cases? For simplicity, assume that n is even. Your changes should be as efficient as possible.

**Answer:**

line(int x, int y, int n, int a, int b, int c) { int i; int e = a * x + b * y + c; int aa = a + a; int bb = b + b; if (-b - aa >= 0) { for (i = 0; i < n; i += 2) { if (e < -a) { if (e < -b - aa) { point(x++, y++); point(x++, y++); e += aa + bb; } else { point(x++, y++); point(x++, y); e += aa + b; } else { point(x++, y); point(x++, y++); e += aa + b; } } } else { for (i = 0; i < n; i += 2) { if (e < -a) { point(x++, y++); point(x++, y); e += aa + b; } else { if (e < -aa) { point(x++, y); point(x++, y++); e += aa + b; } else { point(x++, y); point(x++, y); e += aa; } } } } }

**Remarks:**

The most important aspect of question 5B was finding the correct conditions on e to distinguish the four cases efficiently. The correct conditions were:

Condition Case 0 <= e < -b - 2a up, up -b - 2a <= e < -a up, right -a <= e < -2a right, up -2a <= e < 1 right, right Up denotes a step up and to the right, right denotes a step to the right only.

Note that, because of the slope of the line, a < 0, b > 0, and b > -a. Also note that 0 <= e < b.

A secondary aspect of this question was to notice that the "right, right" case is not possible if the "up, up" case is possible, and vice-versa. Which case is possible depends on whether or not -b - 2a < 0. If -b - 2a < 0, then b > -2a, and the line is mostly horizontal, elimintaing the "up, up" case; likewise, if -b - 2a >= 0, then b <= -2a, the line is closer to 45° than to horizontal, eliminating the "right, right" case. You can also see that this is the case by looking at how these relationships between b and -2a affect the "up, up" case and the "right, right" case given that 0 <= e < b.

The answer shown above takes into account both aspects of the problem, and illustrates the minimum required for the full 15 points, under the assumption that the compiler would handle the rest of the optimizations, including loop invariance and common subexpression elimination.

Because the final point was hard to get, here is code that would have earned 14 points:

line(int x, int y, int n, int a, int b, int c) { int i; int e = a * x + b * y + c; int aa = a + a; int bb = b + b; for (i = 0; i < n; i += 2) { if (e < -a) { if (e < -b - aa) { point(x++, y++); point(x++, y++); e += aa + bb; } else { point(x++, y++); point(x++, y); e += aa + b; } else { if (e < -aa) { point(x++, y); point(x++, y++); e += aa + b; } else { point(x++, y); point(x++, y); e += aa; } } } }

Students that first offset e by 2a, then used -b, a, and 0 as boundary values were given credit for correctly determining the conditions on e.

Students that did not determine the correct boundary values for e, but specifically noted which sections of code applied to which of the four cases, were given points for making it clear that they knew which case was which.

Some students approached the problem by simply unrolling the loop once. We awarded only half credit for this solution.

Some students unrolled the loop once and transformed their code to make it more efficient, but never got to the point where they made it clear that they knew the boundary conditions on e. Other students wrote code from scratch, but never discovered the boundary conditions on e. We awarded the same number of points to these students, which, depending on the level of optimizations, was a few points more than we gave to students who simply unrolled the loop once.

**Grading:**

**14 points** were awarded to students who calculated or described
the boundary conditions on e or who explicitly expressed these boundary
conditions in their code. Specifically, I was looking for some variation
of the -b - 2a, -a, and -2a conditions.

**13 points** were awarded to students who did not calculate the
boundary conditions on e or express them in their code, but who instead
labelled which sections of code corresponded to each of the four cases.

**12 points** were awarded to students who thought that only three
cases existed and went ahead and calculated or described the boundary
conditions on e or explicitly expressed these boundary conditions in their
code, but only for the three cases.

**10 points** were awarded to students who did not calculate or describe
the boundary conditions on e but who otherwise managed to write reasonably
efficient code.

**9 points** were awarded to students who did not calculate or describe
the boundary conditions on e but did manage to write code that looked only
slightly more efficient than unrolled code.

**8 points** were awarded to students who simply unrolled the loop.

**5-7 points** were awarded to students who only handled two cases in
their code, or who otherwise made an attempt to get things to work with
only two cases.

**3 points** were awarded to students who otherwise made a reasonable
attempt at writing code that made sense.

**0-1 points** were awarded to students who didn't make a reasonable
attempt to solve the problem.

**1 additional point** was awarded for the observation that the "up, up"
case and the "right, right" case could not both appear within a single
line.

**1 point was deducted** for inefficient code if your base score was
higher than 12 points.

**1-2 points were deducted** for various small mistakes, such as a
flipped sign, a flipped comparison operator, a misplaced preincrement or
postincrement, or a dropped first pixel.