rmdeboer82 128 Report post Posted December 24, 2002 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] 0 Share this post Link to post Share on other sites

coelurus 259 Report post Posted December 27, 2002 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... 0 Share this post Link to post Share on other sites

rmdeboer82 128 Report post Posted December 27, 2002 i found out the algorithm. im making a tutor which covers all types of line, circle drawing algorithms and descendants of bresenhams''.Matthijs 0 Share this post Link to post Share on other sites

coelurus 259 Report post Posted December 27, 2002 Cool, I gotta see that to make sure I know which line (circle, ellipse, whatever) is made by who 0 Share this post Link to post Share on other sites

jediknight219 122 Report post Posted December 27, 2002 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] 0 Share this post Link to post Share on other sites