//"Wu-style" circle anti-aliased algorithm implementation.
// Here are references we saw:
// 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
// We did not have full access to this articles.
//Program emulating Wu-algorithm.
//Copyright (c) 2011 Konstantin Kirillov
//License: MIT
import java.awt.*;
import java.applet.*;
public class WUCircle extends Applet{
//==========================================================================
//Algorithm:
//--------------------------------------------------------------------------
//Principal parameters:
int I=255; //Intensity range. Determines algorithms' accuracy.
int A=2; //Parameter A determines algorithm's accuracy and
//range of R which is:
// R < 10^A
// Memory = 4 * 10^(2A)
// For example:
// for memory 40K (small machines), screens not more than about 100*100,
// for memory 4Meg, screens about 1000*1000.
//Auxiliary variables:
int[] D; //Precalcuated complimentary fractions of root in units of I.
private static int POWERES_OF_TEN[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
//----------------------------------------------------------------
// Data preparation
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//1.
//For simplicity, this function does redundant job: we really need olny y-s in the
//range of R/sqrt(2) to R. Hence, yy is in the range RR/2 till RR.
//We "sacrifice" this time for simplicity.
//
//2.
//Amount of pre-calculations is "horrible", = 10^2A * (sqrt-time)
//Where (sqrt-time) is time dedicated to calculate sqrt(N).
//It is a startup time. May cause a delay when application is loaded.
//Worths it if there are many circles to draw then.
private void initD(){
int p = POWERES_OF_TEN[A*2];
D = new int[p];
for( int i=0; i<p; i++ ){
int f = ( (int)(I*Math.sqrt((double)i)) )%I;
D[i] = f == 0 ? 0 : I-f;
}
D[0] = 0; //Secure from floating point errors on poor platforms.
}
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Data preparation end
//----------------------------------------------------------------
//----------------------------------------------------------------
// Calculation of an arc
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
//After precalculation, calculation of the 1/8 of circle will take
// R/sq(2) steps = R/sq(2)*(2mult+4plus) ~ 1.4R(int-multiplications)
//Input: uses precalculated variables D and I.
public void drawArch( int R ) {
int y=0;
int x=R;
int d=0;
while( y<x ) {
int dnew = D[R*R-y*y]; //memorize R2=R*R for speed.
if( dnew < d ) x--; //Here we use Wu's lemma.
//These two statements are not a part of the algorithm:
//Each language, OS, or framework has own ways to put a "pixel".
putpixel(x-1,y, dnew, doDemo);
putpixel(x, y,(I-dnew), !doDemo);
y++;
d = dnew;
}
}
//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// Calculation of an arc
//----------------------------------------------------------------
//----------------------------------------------------------------
//End of Algorithm.
//==========================================================================
/////////////////////////////////////////////////////////////////////////////
// DEMO
//
// The rest of this file is an application of above code.
// It is done in form of Java applet to make above code
// the part of a live demo.
// Radius R can be set in index.htm file.
//==========================================================================
//Test:
int R=20; //Radius.
//Platform specific graphics auxiliary.
Dimension scrDimension;
Image img;
Graphics g;
boolean imageIsReady = false;
//Graphics Aux:
int xCenter = 5;
int yCenter;
int squareSize = 14;
//Demonstration
boolean doDemo = true;
int lightBackground = 0;
Color realCurveColor = new Color( 255,0,0 );
//This is a standard method used to initialize an applet:
public void init(){
//Preparation:
try{ String s=getParameter("Radius"); if( s != null && s != "" ) R = Integer.parseInt(s); }catch( Exception e ) {};
scrDimension = new Dimension( (squareSize*R+400), (squareSize*R+200) );
yCenter = R * 12 / 10;
setSize(scrDimension);
img = createImage( scrDimension.width, scrDimension.height );
g = img.getGraphics();
//Algorithm Principal:
con( "initRoot" );
initD();
setImageBackground(255);
con("DrawArch");
drawArch(R);
drawCoodinateLines(R);
if(doDemo) drawRealCircleInDemo(R);
imageIsReady = true;
//con("repaint");
repaint();
}
public void paint( Graphics g ) {
//con("update. " + "imageIsReady=" + imageIsReady + " image=" + img);
if( imageIsReady && img != null ) {
con( "draw image" );
//Move result image to master image:
g.drawImage( img, 0,0, null );
}
}
private void putpixel( int x, int y, int intensity, boolean addDescription ){
//Demo Circle:
con("put: x=" + x + " y=" + y + " i=" + intensity);
int i = lightBackground == 1 ? I - intensity : intensity;
g.setColor( new Color( i, i, i ) );
int xScr = (xCenter+x)*squareSize;
int yScr = (yCenter-y)*squareSize;
g.fillRect( xScr, yScr, squareSize, squareSize);
g.setColor(realCurveColor);
int sQ2 = squareSize/2;
if(addDescription) g.drawString( "x=" + x + "," + ((float)Math.sqrt(R*R-y*y)) + "," + (x+1) + " y=" + y + " i=" + intensity + "," + (I-intensity), xScr+3*squareSize, yScr+sQ2);
//Real Circle:
int rX = xCenter*squareSize + sQ2 + x;
int rY = yCenter*squareSize + sQ2 - y;
g.setColor(new Color(i,i,i));
g.drawLine( rX, rY, rX, rY );
}
private void setImageBackground(int background){
int xSize = scrDimension.width;
int ySize = scrDimension.height;
int c = background*lightBackground;
g.setColor( new Color(c,c,c) );
g.fillRect( 0, 0, xSize, ySize );
}
private void drawCoodinateLines(int R){
g.setColor(new Color(0,0,255));
int sQ2 = squareSize/2;
int x1 = xCenter*squareSize+sQ2;
int x2 = (xCenter + R)*squareSize+sQ2;
int y1 = yCenter*squareSize+sQ2;
int y2 = (yCenter-R)*squareSize+sQ2;
g.drawLine( x1, y1, x2, y1 ); //Axis x.
g.drawLine( x1, y1, x1, y2 ); //Axis y.
g.drawString( "Accuracy=" + A + " Memory~" + (D.length * 4) + " bytes. Intensity=" + I + " Radius=" + R, x1 + 40, y1 + 20);
}
private void drawRealCircleInDemo( int R ){
g.setColor(realCurveColor);
int sQ2 = squareSize/2;
int sXCenter = xCenter*squareSize;
int sYCenter = yCenter*squareSize;
int sR=R*squareSize;
int x=sR;
int y=0;
while(y<x){
x = (int) Math.sqrt((double)(sR*sR-y*y));
int xC = sXCenter+x+sQ2;
int yC = sYCenter-y+sQ2;
g.drawLine(xC,yC,xC,yC);
y++;
}
}
public static void prn( Object ob ){
System.out.println( ob );
}
static public void con( Object ob) {
String s1 = " " + System.currentTimeMillis();
int wLen = s1.length();
s1 = s1.substring( wLen - 7, wLen-1 );
String s2 =Thread.currentThread().getName() + " ";
s2 = s1 + " \"" + s2.substring ( 0, 20 ) + "\" " + ob;
System.out.println(s2);
}//con
//===========================================================================
// END OF DEMO
/////////////////////////////////////////////////////////////////////////////
}//class
Copyright (C) 2011 Konstantin Kirillov. MIT License