ellipse midpoint algorithm counterclockwise version

Question

I'm trying to convert the standart clockwise ellipse midpoint algorithm taken from the book "Computer Graphics with OpenGL" so that it would work counter-clockwise starting from region 2. I got it to work and draw an ellipse but its not identical to the one the original algorithm draws so I assume I have a small bug in my code which I can't seem to find, can some please help?

This is the original algorithm:

void ellipseMidpoint(int xCenter, int yCenter, int Rx, int Ry)
{
    int Rx2 = Rx * Rx;
    int Ry2 = Ry * Ry;
    int twoRx2 = 2 * Rx2;
    int twoRy2 = 2 * Ry2;
    int p;
    int x = 0;
    int y = Ry;
    int px = 0;
    int py = twoRx2 * y;
    void ellipsePlotPoints(int, int, int, int);

    /* Plot the initial point in each quadrant. */
    ellipsePlotPoints(xCenter, yCenter, x, y);

    /* Region 1 */
    p = round(Ry2 - (Rx2 * Ry) + (0.25 * Rx2));
    while (px < py) {
        x++;
        px += twoRy2;
        if (p < 0)
            p += Ry2 + px;
        else {
            y--;
            py -= twoRx2;
            p += Ry2 + px - py;
        }
        ellipsePlotPoints(xCenter, yCenter, x, y);
    }

    /* Region 2 */
    p = round(Ry2 * (x + 0.5) * (x + 0.5) + Rx2 * (y - 1) * (y - 1) - Rx2 * Ry2);
    while (y > 0) {
        y--;
        py -= twoRx2;
        if (p > 0)
            p += Rx2 - py;
        else {
            x++;
            px += twoRy2;
            p += Rx2 - py + px;
        }
        ellipsePlotPoints(xCenter, yCenter, x, y);
    }
}

void ellipsePlotPoints(int xCenter, int yCenter, int x, int y)
{
    setPixel(xCenter + x, yCenter + y);
    setPixel(xCenter - x, yCenter + y);
    setPixel(xCenter + x, yCenter - y);
    setPixel(xCenter - x, yCenter - y);
}

and this is my version:

void ellipseMidpointCounterClockwise(int xCenter, int yCenter, int Rx, int Ry)
{
    int Rx2 = Rx * Rx;
    int Ry2 = Ry * Ry;
    int twoRx2 = 2 * Rx2;
    int twoRy2 = 2 * Ry2;
    int p;
    int x = Rx;
    int y = 0;
    int px = twoRy2 * x;
    int py = 0;
    void ellipsePlotPoints(int, int, int, int);

    /* Plot the initial point in each quadrant. */
    ellipsePlotPoints(xCenter, yCenter, x, y);

    /* Region 2 */
    p = round(Ry2 * (x - 0.5) * (x - 0.5) + Rx2 * (y + 1) * (y + 1) - Rx2 * Ry2);
    while (py < px) {
        y++;
        py += twoRx2;
        if (p > 0)
            p += Rx2 - py;
        else {
            x--;
            px -= twoRy2;
            p += Rx2 - py + px;
        }
        ellipsePlotPoints(xCenter, yCenter, x, y);
    }

    /* Region 1 */

    p = round(Ry2 * (x - 1.0) * (x - 1.0) + Rx2 * (y + 0.5) * (y + 0.5) - Rx2 * Ry2);
    while (x > 0) {
        x--;
        px -= twoRy2;
        if (p < 0)
            p += Ry2 + px;
        else {
            y++;
            py += twoRx2;
            p += Ry2 + px - py;
        }
        ellipsePlotPoints(xCenter, yCenter, x, y);
    }
}

I would really appreciate some helping finding what I did wrong.

Answer 1

The first problem is that the original code is not symmetric with respect to x and y (and your ellipseMidpointCounterClockwise actually just replaces x and y).

ellipseMidpoint(0,0,3,2) generates for the first quadrant

0 2
1 2
2 1
3 0

whereas ellipseMidpoint(0,0,2,3) generates for the first quadrant

0 3
1 3
2 2
2 1
2 0

when exchanging coordinates and reversing the order we get:

0 2
1 2
2 2
3 1
3 0

Graphically this means:

002
| 12
+--0

where + denotes the center, 0 denotes ellipse points in both results, 1 a point only in the first result, 2 points only in the second result (mirrored).

If you want your ellipseMidpointCounterClockwise to generate exactly the same points you could - instead of replacing x and y - just go into the negative x-direction (i.e. x-- instead of x++ in the original code). Otherwise you have to live with the difference in symmetry.

The second problem is that you did not just replace x and y but also do some other strange replacements. If you just replace x and y within the regions you get the correct result:

void ellipseMidpointCounterClockwise(int xCenter, int yCenter, int Rx, int Ry)
{
  int Rx2 = Rx * Rx;
  int Ry2 = Ry * Ry;
  int twoRx2 = 2 * Rx2;
  int twoRy2 = 2 * Ry2;
  int p;
  int x = Rx;
  int y = 0;
  int px = twoRy2 * x;
  int py = 0;
  void ellipsePlotPoints(int, int, int, int);

  /* Plot the initial point in each quadrant. */
  ellipsePlotPoints(xCenter, yCenter, x, y);

  /* Region 2 */
  p = round(Rx2 - (Ry2 * Rx) + (0.25 * Ry2));
  while (py < px) {
    y++;
    py += twoRx2;
    if (p < 0)
      p += Rx2 + py;
    else {
      x--;
      px -= twoRy2;
      p += Rx2 + py - px;
    }
    ellipsePlotPoints(xCenter, yCenter, x, y);
  }

  /* Region 1 */
  p = round(Rx2 * (y + 0.5) * (y + 0.5) + Ry2 * (x - 1) * (x - 1) - Ry2 * Rx2);
  while (x > 0) {
    x--;
    px -= twoRy2;
    if (p > 0)
      p += Ry2 - px;
    else {
      y++;
      py += twoRx2;
      p += Ry2 - px + py;
    }
    ellipsePlotPoints(xCenter, yCenter, x, y);
  }
}