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.txt


  
This a Google ad. Not a part of this Web page content: