Midpoint ellipse counterclockwise
I am trying to convert the standard clockwise middle ellipse algorithm taken from Computer Graphics with OpenGL to work counterclockwise starting from region 2. I got it to work and will draw an ellipse, but its not identical to the one using original algorithm, so I am guessing that I have a small error in my code that I cannot find, can anyone 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 am very grateful for your help in finding what I did wrong.
source to share
The first problem is that the original code is not symmetrical about x and y (and your MidpointCounterClockwise ellipse 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 the Midpoint ellipse (0,0,2,3) generates for the first quadrant
0 3
1 3
2 2
2 1
2 0
when exchanging coordinates and in reverse 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 the points of the ellipse in both results, 1 - only in the first result, 2 - only in the second result (mirror image).
If you want your ellipseMidpointCounterClockwise to generate exactly the same points, you could - instead of replacing x and y - just go in the negative x-direction (that is, x-- instead of x ++ in your source code). Otherwise, you will have to live with a symmetry difference.
The second problem is that you have not only replaced x and y, but also made some other strange replacements. If you just replace x and y in 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);
}
}
source to share