ATTENTION: For newer content, please go to Antialiased algorithms. September 2011 and newer. Using WU-like algorithm to draw circles in computers with limited resources. Demo and its Source Code We don't have access to original article. We found WU algorithm in http://www.mini.pw.edu.pl/~kotowski/Grafika/RasterDrawing/Index.html today on September 8, 2008. Here it is how we understand the algorithm: //***** Beginning of the WU algorithm. //To avoid copyright issues, we rewrote the algorithm. //We are using C-style language. //A - amplitude (Intensity). //r - radius. DrawArch( int r ){ int y=0; int x=r; float d=0; putpixel(x,y,A); while( x>y ){ y++; if( DC(r,y) < d ) x--; putpixel(x, y, A*(1-DC(R,y) ); putpixel(x-1, y, A* DC(R,y) ); d = DC(r,y) } } //Distance to ceil: double DC(int r, int y){ double x = Math.sqrt(r*r-y*y); return Math.ceil(x) - x; } //***** End of WU algorithm. The advantage of WU-algorithm is using precalculated DC. If by some reason, algorithm is implemented without precalculation step, then using condition "DC(r,y) < d" can be avoided and algorithm can be writtend in following form: //***** Beginning of the WC-non-optimized algorithm. //Description: Draws arch of a circle starting from point // (x,y)=(r,0) until point (x,x). //Language: C-style. //Input: A - amplitude (intensity). // r - circle radius. //Implementation: this source code is not ment to be executed, // but is only a description. DrawArch( int r, int A ){ x=r; for( int y=0; y<x; y++ ){ double x = sqrt(r*r-y*y); mod f = x%1.; xleft = (int)(x-f); putpixel(xleft, y, A*(1.-f) ); putpixel(xleft+1, y, A*f ); } } //***** End of WC-non-optimized algorithm. We see the main advantage of WU algorithm in using a precious lemma that "if( DC(r,y) < d ), step back must be done". However, using this lemma is not required if there is no constrain on memory for prestored values. Here, we wrote one of the possible implementations of WU algorithm by excluding floating point operations and non-using abovementioned lemma. //*********** Begin WU-no-memory-optimized algorithm. //Precalculated values: //These arrays require about 80 Kilobytes memory public static int XLeft[10000]; public static int Fraction[10000]; public static int Intensity; //This function must be run before beginning to draw circles. public static PrecalculateFraction( int I ){ Intensity = I; for( i=0; i<10000; i++ ){ x = Math.sqrt(i); Fraction = (int) (Intensity * (x%1.)); XLeft = (int)x; } } //Input: radius r<100 public static WUDrawArchNoMemoryConstrain( int r ); int y=0; int x=r; while( y<x ){ int arg=r*r-y*y; int x=Xleft[arg]; int f=Fraction[arg]; putpixel(x, y, Intensity-f); putpixel(x+1, y, f ); y++; } } //*********** End of WU-no-memory-optimized algorithm. Disadvantages of above implementation are 1. restriction to radius value: r<100, 2. 80K memory usage can be non-acceptable for some portable telephones. We experimented with more optimized versions and intermediate steps of these experiments are in child folders of this text: Step2Optimized, WU, ShortWU. Reader should be able to use these samples for more optimization. References: Wu, Xiaolin (1991). "Fast Anti-Aliased Circle Generation", in James Arvo (Ed.): Graphics Gems II. San Francisco: Morgan Kaufmann, pp. 446–?. ISBN 0-12-064480-0. There were available pages from: http://books.google.com/books?id=ZQQssYF3i7wC&pg=PA446&lpg=PA446&dq=Fast+Anti-Aliased+Circle+Generation&source=web&ots=3tEqjTmXRM&sig=8Yalwrv81RcW5QPg46_fjgmRgZU&hl=en&sa=X&oi=book_result&resnum=2&ct=result Xiaolin Wu's line algorithm http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm Copyright_C_2008_Landkey_Computers.txtThis a Google ad. Not a part of this Web page content: