CS 248: Midterm Solutions

Question 5

Grader: Matt

Points were given for both correctness and efficiency. Correctness criteria included:

Are exactly n pixels drawn?
Are there any gaps in the curve drawn? (A common mistake was to always increment x and then increment y based on the e variable. This causes problems further along the curve when x is larger and many pixels need to be drawn in y before moving along in x.)
Are the correct pixels drawn?

Efficiency was basically based on whether you came up with a reasonable algorithm based on finite differences. Writing the implicit function properly gave partial credit: 0 = y^2 - 2^x + 1, and computing f(x+1, y) - f(x, y) = -2^x and

f(x, y+1) - f(x, y) = 2y
+ 1

also gave partial credit.

Based on finite differences, an efficient rasterizer can be written like this:

void rasterize(int n)
{
  int x = 0;
  int y = 0;
  int e = 0;

  for (int i = 0; i < n; ++i) {
    point(x, y);
    e += 2 * y + 1;
    ++y;
    if (e > 0) {
      e -= 1 << x;
      ++x;
    }
  }
}

A common error was to switch the places of x and y; always taking a step in x; this is incorrect, since it causes large gaps in the curve as x gets large.

The following table shows the first few values of the curve as well as the points that the rasterizer should draw and the value of e. Note that for the first few pixels, the points plotted are actually above the curve. However, since the instructions said to ignore half-pixel offsets, the above rasterizer is a good enough solution. Some people wrote rasterizers that had a special case for x < 4; this answer was fine, too, though not necessary for full credit.

x	y	(float)y	e
0	0	0	0
1	1	1	0
2	2	1.73205	1
3	3	2.64575	2
4	4	3.87298	1
5	5	5.56776	-6
6	6	7.93725	-27
6	7	7.93725	-14
7	8	11.2694	-63
7	9	11.2694	-46
7	10	11.2694	-27
7	11	11.2694	-6

The above rasterizer can be improved further by incrementally computing the adjustments to e, however the above version was sufficient for full credit.

void rasterize(int n)
{
  int x = 0;
  int y = 0;
  int e = 0;
  int dedy = 1;
  int dedx = -1;

  for (int i = 0; i < n; ++i) {
    point(x, y);
    e += dedy;
    dedy += 2;
    ++y;
    if (e > 0) {
      e += dedx;
      dedx *= 2;
      ++x;
    }
  }
}

A few people came up with more creative solutions; as long as they were both correct and efficient, credit was given.