椭圆中点算法逆时针版本

Question

我正试图转换《OpenGL的计算机图形学》一书中的标准顺时针椭圆中点算法，使其从区域2开始逆时针工作。我让它工作并绘制了一个椭圆，但它与原始算法绘制的椭圆不完全相同，所以我认为我的代码中有一个小错误，我似乎找不到，可以帮忙吗？

这是原始算法：

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);
}

这是我的版本：

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);
}
}

如果能帮我找出我做错的地方，我将不胜感激。

Answer 1

第一个问题是原始代码相对于x和y不是对称的(而您的ellipseMidpointCounterClockwise实际上只是替换了x和y)。

ellipseMidpoint(0,0,3,2)为第一象限生成

0 2
1 2
2 1
3 0

而ellipseMidpoint(0,0,2,3)为第一象限生成

0 3
1 3
2 2
2 1
2 0

当交换坐标并颠倒顺序时，我们得到：

0 2
1 2
2 2
3 1
3 0

从图形上看，这意味着：

002
| 12
+--0

其中+表示中心，0表示两个结果中的椭圆点，1仅在第一个结果中为点，2仅在第二个结果(镜像)中为点。

如果你想让你的ellipseMidpointCounterClockwise生成完全相同的点，你可以——而不是替换x和y——只朝负x方向(即x——而不是原始代码中的x++)。否则，你就不得不忍受对称性的差异。

第二个问题是，你不仅替换了x和y，还做了一些其他奇怪的替换。如果你只替换区域内的x和y，你会得到正确的结果：

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);
}
}