Michener's Circle Algorithm
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]
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...
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...
i found out the algorithm. im making a tutor which covers all types of line, circle drawing algorithms and descendants of bresenhams''.
Matthijs
Matthijs
Cool, I gotta see that to make sure I know which line (circle, ellipse, whatever) is made by who
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.
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.
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement