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]

i found out the algorithm. im making a tutor which covers all types of line, circle drawing algorithms and descendants of bresenhams''.

Matthijs

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]