Sketches
Anti-Aliased Curve Algorithms
home top contents previous up next

//Linear-constrain circle anti-aliased algorithm.
//Copyright (c) 2011 Konstantin Kirillov
//License: MIT

/*

A l g o r i t h m ` s   b r i e f   d e s c r i p t i o n

Circle is a solution of constraint F=0 where 
function F(x,y)=R^2 - x^2 - y^2.
When moving from x=R, y=0 till y=R/2 we 

 1. change x-- when F becomes <0
 2. we calculate intensities I1, I2 of neighbour pixels assuming
    that I1/I2 ~ DF1/DF2 at fixed y.

Following notations are used in program:

  E=R^2-y^2 ( "available excess" )
  x    - point on the left from circle
  xTop - x+1, point to the right from circle
  L    - "low difference", L=E-x^2         =DF1
  U    - "upper difference", U=(x+1)^2-E   =-DF2
  u    - intensity "contributed" by difference from upper node
  l    - intensity "contributed" by lower node  
  I    - summary intensity I=u+l of both left and right pixels

(2) implies u/l=U/L
    u=IU/(U+L)

We must assign u to the left pixel and l to the right.

End of second algorithm.

*/



import java.applet.Applet;
import java.awt.*;

public class NoSqrt extends Applet{

    //==========================================================================
    //Algorithm:
    //--------------------------------------------------------------------------

    //Principal parameters:
        int I=255;          //Intensity range. Determines algorithms' accuracy.

        
        
    //----------------------------------------------------------------
    // Calculation of an arc
    //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

    //No precalculation is required.
    //Calculation of the 1/8 of circle will take
    // R/sq(2) steps = R/sq(2)*(3mult+1div+8add) ~ 1.4R(3mult+1div)
    // All operations are of integer type.
        
        
    //Input: uses precalculated variables D and I.     
    public void drawArch( int R ) {
       int R2=R*R;
       int y=0;
       int x=R;

       int B=x*x;
       int xTop=x+1;
       int T=xTop*xTop;

       while( y<x ) {
           int E=R2-y*y;
           int L=E-B;
           int U=T-E;
           if(L<0){ //We had Wu's lemma before: if( dnew < d ) x--;
        	   xTop=x;
        	   x--;
        	   T=B;
        	   U=-L;
        	   B=x*x;
               L=E-B;
           }
           int u=I*U/(U+L);
           
           //good for debug:
           con("x="+x+" y="+y+" E="+E+" B="+B+" T="+T+" L="+L+" U="+U+" u="+u);
           
           //These two statements are not a part of the algorithm:
           //Each language, OS, or framework has own ways to put a "pixel".
           putpixel(x,      y,     u,  doDemo);
           putpixel(xTop,   y, (I-u), !doDemo);
           
           y++;
       }    
    }
    //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
    // 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" );
        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( "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
   /////////////////////////////////////////////////////////////////////////////

   
   

}


Copyright (C) 2011 Konstantin Kirillov. MIT License