//Graphics algorithms: 
//Bresenham's style:
//  WU
//    http://www.mini.pw.edu.pl/~kotowski/Grafika/RasterDrawing/Index.html
//      Apparently, 
//         there is a typo:
//         ...
//         y++;
//         if (D(R,y)<T)  // Initial T=0, and D >= 0 for circle's points which are not on the grid.
//                        // Therefore, this condition never works.
//            x--;
//         ...


class TestsWU {

    public static void main( String args[] ) {
        for( int accuracy = 1; accuracy<8; accuracy++ )
        //accuracy = 8 gives array of 100 000 000 of int32 = 400Mbytes
        //which gives java.lang.OutOfMemoryError: Java heap space ...
        //in our 1 Gig RAM PC.
        {  
           long start = System.currentTimeMillis();        
           String s = InitializeISqrt( accuracy );
           if( s == "" ){
               System.out.println( "Total Duration=" + ( System.currentTimeMillis() - start) + " milliseconds."  );
               System.out.println( "Duration per array element =" + 
                                   ( 1000000. * ( System.currentTimeMillis() - start)) / ISqrt.length  +
                                   " nanoseconds." );
               int arg = 0;
               ISQRT(arg);
               System.out.println( "sqrt(" + arg + "0)="+ ISignificand + " * 10^-" + IExponent);
               arg = 1;
               ISQRT(arg);
               System.out.println( "sqrt(" + arg + "0)="+ ISignificand + " * 10^-" + IExponent);
               arg = 20000;
               ISQRT(arg);
               System.out.println( "sqrt(" + arg + "0)="+ ISignificand + " * 10^-" + IExponent);
               arg = 999999;
               ISQRT(arg);
               System.out.println( "sqrt(" + arg + "0)="+ ISignificand + " * 10^-" + IExponent + "\r\n\r\n\r\n");


    } else {
               System.out.println( s );
           }
        }           
    }    

    //To not exceede limts of int32:
    private static final int SAFE_DIGITS = 6;  
    private static int ROOTS_ARRAY_SIZE;
    //Redundant digits which exceed accuracy restricted by ACCURACY:
    private static int BONUS_DIGITS;          
    private static int BONUS_MULTIPLIER;
    //Auxiliary array to store precalculated powers of 10:
    private static int POWERES_OF_TEN[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
    //Primary array where precalculated roots will be stored:
	private static int[] ISqrt;              
    

    //ACCURACY value 3 should provide sqrt(10^3) accuracy ~ 3% accuracy. 
    //ACCURACY value 4 should provide sqrt(10^4) accuracy ~ 1% accuracy. 
    //         In application to IntegerWU algorithm to find Intensity*ceil(sqrt(RR-yy)),
    //         this will give 100 grades of shade which should be good.
    //ACCURACY value 5 should provide sqrt(10^5) accuracy ~ .3% accuracy. 
	public static String InitializeISqrt(int ACCURACY) {
        System.out.println( "ACCURACY=" + ACCURACY + ". SAFE DIGITS=" + SAFE_DIGITS );
        if( ACCURACY < 3 ) {
            return "ACCURACY is too small: ACCURACY < " +  3;
        }
        int w = 2 * SAFE_DIGITS - ACCURACY;
        BONUS_DIGITS = (w - (w%2)) / 2;
        if( BONUS_DIGITS < 0 ) { 
            return "ACCURACY is too big: ACCURACY > " +  (2 * SAFE_DIGITS);
        }
        ROOTS_ARRAY_SIZE = POWERES_OF_TEN[ACCURACY];
        BONUS_MULTIPLIER = POWERES_OF_TEN[BONUS_DIGITS];
        System.out.println( "ROOTS_ARRAY_SIZE=" + ROOTS_ARRAY_SIZE + ". BONUS_DIGITS=" + BONUS_DIGITS + ". BONUS_MULTIPLIER=" + BONUS_MULTIPLIER + ".");
        ISqrt = new int[ ROOTS_ARRAY_SIZE ];
    	for( int i=0; i<ROOTS_ARRAY_SIZE; i++ ){
	       ISqrt[i] = (int) (  Math.sqrt((double)i)  *  BONUS_MULTIPLIER  );
        }		 
	    return "";
    }

    //Calculating square root represented by integer numbers.
    //Input x>=0.
    //Output:  ISignificand * 10^IExponent
    //         where
    public static int IExponent;
    public static int ISignificand; 
	public static void ISQRT( int x ) {
       int shift=0;
       if ( x!=0 ) {
        while ( x<ROOTS_ARRAY_SIZE ) {
           x = x*100;
           shift -=1;
        }
       }
       while ( x>=ROOTS_ARRAY_SIZE ) {
           x = x/100;
           shift +=1;
       }
       IExponent    = BONUS_DIGITS-shift;
       //System.out.println("x=" + x + ". Len=" + ISqrt.length );
       ISignificand = ISqrt[x];
    }

    
	//This function calculates D(R,y) = ceil(sqrt(RR-yy)) - sqrt(RR-yy).
    //It returns distance scaled with FullIntensity.
    //Input: FullIntensity < 2000. (To avoid integer overflow when FullIntensity * id.)
    //       R<1000. Otherwise, no guarantee for accuracy.
	private static int ID( int R, int y, int FullIntensity ) {
           ISQRT( R*R-y*y );
           int p = POWERES_OF_TEN[IExponent];
           int id = ISignificand % p;
           return FullIntensity * id / p;
	}
    
} 


Copyright_C_2008_Landkey_Computers.txt