Archived

This topic is now archived and is closed to further replies.

rmdeboer82

Michener's Circle Algorithm

Recommended Posts

Hi all, Could someone tell me the derivation of this algorithm, because i can't find it. On many pages it says how to apply it, but there is no derivation at all. Like this: { int x = 0; int y = nRadius; // Error term int d = 3 - 2 * nRadius; while (x <= y) { DrawPixel(pSurface, xc + x, yc + y, color); DrawPixel(pSurface, xc - x, yc + y, color); DrawPixel(pSurface, xc + x, yc - y, color); DrawPixel(pSurface, xc - x, yc - y, color); DrawPixel(pSurface, xc + y, yc + x, color); DrawPixel(pSurface, xc - y, yc + x, color); DrawPixel(pSurface, xc + y, yc - x, color); DrawPixel(pSurface, xc - y, yc - x, color); // Error update term if (d < 0) { d += 4 * x + 6; } else { d += 4 * (x - y) + 10; --y; } ++x; } } I want to know the derivation. Can somebody help me out? The final result is like this: di+1 = di + 4x_{i-1} + 6 + 2(y_{i}^2 - (y_{i-1})^2) - 2(y_{i}-y_{i-1} BTW: '_{i}' means it is a lower index like in math '^x' means to the power of x Matthijs [edited by - rm82 on December 24, 2002 8:54:27 AM]

Share this post


Link to post
Share on other sites
That algorithm is mostly referred to as "Bresenham''s circle algorithm". Do a search on Google for that and you''ll find numerous of links to it (I hardly found anything on Michener :/ ).

Does anybody actually know which line, circle- and ellipse-routines are by Bresenham, and which "extensions" are by others? I''d really want to know, it seems that everybody''s using "Bresenham" for everything...

Share this post


Link to post
Share on other sites
I found this. Note that the math is different because this example increments x and decrements y before d is updated, instead of after like in your algorithm.



Assume that the last point was (x-1,y). Find whether (x,y-½) is above or below the circle, and move SE to (x,y-1) or E to (x,y), respectively.


y=r;
pixel(0,r);
for(x=1;x < r/sqrt(2);x++)
{ d=x^2+(y-1/2)^2-r^2;
if (d>=0) y--;
pixel(x,y);
}


Optimize: d=x^2+(y-1/2)^2-r^2 becomes d=x^2+y^2-y+1/4-r^2. How does the d for a given x differ from d for x-1? If y is unchanged, then d{x} = d{x-1}+2x-1. If y decreases, add -2y+2, where that is the old y. Also the only time that 1/4 affects the test d>0 is when d=1/4, so ignore it, but make the test d>=0.


y=r;
d= -r;
pixel(0,r);
for(x=1;x < r/sqrt(2);x++)
{ d+= 2x-1;
if (d>=0)
{ y--;
d -= 2y; /* Must do this AFTER y-- */
}
pixel(x,y);
}


This is Bresenham's circle algorithm. Note that you can store 2x-1 and -2y and update them by adding or subtracting 2.



[edited by - jediknight219 on December 27, 2002 11:48:48 AM]

Share this post


Link to post
Share on other sites