fillTest.java

//
//  Test.java
//  
//
//  Created by Joe Geigel on 1/21/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

import java.awt.*;
import java.awt.event.*;

public class fillTest {
  
	public fillTest () {}	
    
	static public void main(String[] args){
		
		simpleCanvas T = new simpleCanvas(300, 300);
        Rasterizer R = new Rasterizer (300);
        
        T.setColor (0.0f, 0.0f, 0.0f);
		T.clear();
		T.setColor (1.0f, 1.0f, 1.0f);
        
        int x[] = new int[7];
		int y[] = new int[7];
        
        /* 
		 * Use Student's drawPolygon 
		 */
		x[0] = 10; y[0] = 10;
		x[1] = 20; y[1] = 10;
		x[2] = 20; y[2] = 20;
		x[3] = 10; y[3] = 20;
		
		/* 
		 * LL => Lower Left Start, CCW => Vertices entered in 
		 * counter clockwise progression 
		 */
		R.drawPolygon( 4, x, y, T );	/* Square, LL, CCW */
		
		x[0] = 40; y[0] = 30;
		x[1] = 40; y[1] = 50;
		x[2] = 30; y[2] = 50;
		x[3] = 30; y[3] = 30;
		
		R.drawPolygon( 4, x, y, T );	/* Rectangle, LR, CCW */
		
		x[0] = 40; y[0] = 90;
		x[1] = 40; y[1] = 70;
		x[2] = 10; y[2] = 70;
		x[3] = 10; y[3] = 90;
		
		R.drawPolygon( 4, x, y, T );	/* Rectangle, UR, CW */
		
		x[0] = 10; y[0] = 230;
		x[1] = 40; y[1] = 230;
		x[2] = 40; y[2] = 210;
		x[3] = 10; y[3] = 210;
		
		R.drawPolygon( 4, x, y, T );	/* Rectangle, UL, CW */
		
		x[0] = 100; y[0] = 10;
		x[1] = 150; y[1] = 10;
		x[2] = 125; y[2] = 20;
		
		R.drawPolygon( 3, x, y, T );	/* Isosceles, flat bottom */
		
		x[0] = 100; y[0] = 30;
		x[1] = 140; y[1] = 50;
		x[2] = 175; y[2] = 50;
		
		R.drawPolygon( 3, x, y, T );	/* flat top - tail to left */
		
		x[0] = 120; y[0] = 40;
		x[1] = 80;  y[1] = 60;
		x[2] = 45;  y[2] = 60;
		
		R.drawPolygon( 3, x, y, T );	/* flat top - tail to right */
		
		x[0] = 10; y[0] = 100;
		x[1] = 10; y[1] = 120;
		x[2] = 25; y[2] = 100;
		
		R.drawPolygon( 3, x, y, T );	/* Right */
		
		x[0] = 10; y[0] = 130;
		x[1] = 20; y[1] = 130;
		x[2] = 20; y[2] = 140;
		
		R.drawPolygon( 3, x, y, T );	/* Right */
		
		x[0] = 10; y[0] = 170;
		x[1] = 20; y[1] = 170;
		x[2] = 10; y[2] = 150;
		
		R.drawPolygon( 3, x, y, T );	/* Right */
		
		x[0] = 100; y[0] = 70;
		x[1] = 150; y[1] = 70;
		x[2] = 75;  y[2] = 90;
		
		R.drawPolygon( 3, x, y, T );	/* flat bottom - top left */
		
		x[0] = 100; y[0] = 100;
		x[1] = 150; y[1] = 100;
		x[2] = 195; y[2] = 120;
		
		R.drawPolygon( 3, x, y, T );	/* flat bottom - top right */
		
		x[0] = 100; y[0] = 170;
		x[1] = 150; y[1] = 150;
		x[2] = 175; y[2] = 130;
		
		R.drawPolygon( 3, x, y, T );	/* scalene */
		
		x[0] = 200; y[0] =  50;
		x[1] = 225; y[1] =  90;
		x[2] = 250; y[2] =  50;
		x[3] = 225; y[3] =  10;
		
		R.drawPolygon ( 4, x, y, T );     /* diamond */
		
		x[0] = 200; y[0] = 125;
		x[1] = 210; y[1] = 150;
		x[2] = 260; y[2] = 145;
		x[3] = 275; y[3] = 120;
		x[4] = 250; y[4] = 100;
		x[5] = 225; y[5] = 100;
		
		R.drawPolygon ( 6, x, y, T );     /* hexagon */
		
		x[0] = 215; y[0] = 225;
		x[1] = 200; y[1] = 250;
		x[2] = 215; y[2] = 250;
		x[3] = 225; y[3] = 275;
		x[4] = 235; y[4] = 250;
		x[5] = 250; y[5] = 250;
		x[6] = 235; y[6] = 225;
		
		R.drawPolygon ( 7, x, y, T );     /* star top */
        
        Frame f = new Frame( "polyfill Test" );
        f.add("Center", T);
		f.pack();
		f.setResizable (false);
        f.setVisible(true);
		
		f.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
		
	}
        
}

Rasterizer.java

//
//  Rasterizer.java
//  
//
//  Created by Joe Geigel on 1/21/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

/**
 * 
 * This is a class that performas rasterization algorithms
 *
 */

import java.util.*;

public class Rasterizer {
    
    /**
     * number of scanlines
     */
    int n_scanlines;

    Hashtable<Integer, ArrayList<Rasterizer.Bucket>> ET;
    ArrayList<Bucket> AEL;

    class Bucket implements Comparable<Bucket> {
        Integer ymax, x, dx, dy, sum;
        boolean positive_slope;

        // First compare x; then dx; then dy.
        public int compareTo(Bucket that) {
            int value1 = this.x.compareTo(that.x);
            if (value1 == 0) {
                int value2 = this.dx.compareTo(that.dx);
                if (value2 == 0) {
                    return this.dy.compareTo(that.dy);
                } else {
                    return value2;
                }
            } else {
                return value1;
            }
        }

        public void print() {
            System.out.printf("ymax: %d, x: %d, +/-: %b, dx: %d, dy: %d, sum: %d\n", ymax, x, positive_slope, dx, dy, sum);
        }
    }
    
    /**
     * Constructor
     *
     * @param n - number of scanlines
     *
     */
    Rasterizer (int n)
    {
        n_scanlines = n;
    }
    
    /**
     * Draw a filled polygon in the simpleCanvas C.
     *
     * The polygon has n distinct vertices. The 
     * coordinates of the vertices making up the polygon are stored in the 
     * x and y arrays.  The ith vertex will have coordinate  (x[i], y[i])
     *
     * You are to add the implementation here using only calls
   * to C.setPixel()
     */
    public void drawPolygon(int n, int x[], int y[], simpleCanvas C)
    {
        ET = new Hashtable<Integer, ArrayList<Rasterizer.Bucket>>();
        populateET(n, x, y);
        printET();
        AEL = new ArrayList<Bucket>();
        drawPolygonImpl(C);
    }

    public void drawPolygonImpl(simpleCanvas C) {
        int y = firstNonEmptyBucketIndex();
        while (AEL.size() > 0 || ET.size() > 0) {
            discardAELEntries(y);
            moveFromETtoAEL(y);
            Collections.sort(AEL);
            printAEL(y);
            fillPixelsOnScanLine(y, C);
            y++;
            nonVerticalAELEdges();
        }

    }

    private void populateET(int n, int x[], int y[]) {
        int j;
        System.out.println("Populate ET:");
        //System.out.printf("n: %d, x[]: %d\n", n, x.length);
        // n - 2: -1 to offset index; another -1 to end loop on the i-1th element
        for (int i = 0; i <= n-1; i++) {
            // choose the next element unless we are the last element-- then pick the first (i==0).
            j = (i + 1 < n) ? i + 1 : 0;
            
            if (y[i] < y[j]) {
                addEdgeToET(x[i], y[i], x[j], y[j]);
            } else if (y[j] < y[i]) {
               addEdgeToET(x[j], y[j], x[i], y[i]);
            } else { // y[i] == y[j]
               addEdgeToET(Math.min(x[i], x[j]), y[i], Math.max(x[i], x[j]), y[j]);
            }
        }
    }

    private void addEdgeToET(int x1, int y1, int x2, int y2) {

        System.out.printf("Adding edge %d, %d, %d, %d\n", x1, y1, x2, y2);
        // Instantiate bucket and populate instance variables
        Bucket b = new Bucket();
        b.ymax = Math.max(y1, y2);
        if (y1 < y2) {
            b.x = x1;
        } else if (y2 < y1) {
            b.x = x2;
        } else { // y1 == y2
            b.x = Math.min(x1, x2);
        }
        b.dx = Math.abs(x2-x1);
        b.dy = Math.abs(y2-y1);
        if (y2-y1 < 0 ^ x2-x1 < 0) {
            b.positive_slope = false;
        } else {
            b.positive_slope = true;
        }
        b.sum = 0;

        // Add bucket to hashtable
        ArrayList<Bucket> array;
        if (ET.containsKey(Math.min(y1, y2))) {
            array = ET.get(Math.min(y1, y2));
            array.add(b);
        } else {
            array = new ArrayList<Bucket>();
            array.add(b);
            ET.put(Math.min(y1, y2), array);
        }
        b.print();
    }

    private void printETKeys() {
        ArrayList<Integer> keys = Collections.list(ET.keys());
        for (Integer i : keys) {
            System.out.printf("%d ", i);
        }
        System.out.println("\n");
    }

    private int firstNonEmptyBucketIndex() {
        int min = Integer.MAX_VALUE;
        ArrayList<Integer> keys = Collections.list(ET.keys());
        for (Integer i : keys) {
            if (i < min) {
                min = i;
            }
        }
        return min;
    }

    private void discardAELEntries(int y) {
        System.out.printf("AEL Size: %d\n", AEL.size());
        Iterator<Bucket> iter = AEL.iterator();
        while (iter.hasNext()) {
            if (y >= iter.next().ymax) {
                iter.remove();
            }
        }
        System.out.printf("AEL Size: %d\n\n", AEL.size());
    }

    private void moveFromETtoAEL(int y) {
        System.out.printf("ET Size: %d\n", ET.size());
        if (ET.containsKey(y)) {
            ArrayList<Bucket> array = ET.get(y);
            for (Bucket b : array) {
                AEL.add(b);
            }
            ET.remove(y);
        }
        System.out.printf("ET Size: %d\n\n", ET.size());
    }

    private void fillPixelsOnScanLine(int y, simpleCanvas C) {
        // Iterate all even indexes; except the last one
        for (int i = 0; i <= AEL.size() - 2; i++) {
            System.out.println("Print pixels from x=" + AEL.get(i).x + " to x=" + AEL.get(i+1).x);
            for (int x = AEL.get(i).x; x <= AEL.get(i+1).x; x++) {
                C.setPixel(x, y);
            }
        }
    }

    private void nonVerticalAELEdges() {
        // For each non-vertical edge
        for (Bucket b : AEL) {
            if (b.dx != 0 && b.dy != 0) {
                b.sum = b.sum + b.dx;
                if (b.sum >= b.dy) {
                    System.out.println("here! b.sum:" + b.sum + " b.dy:" + b.dy);
                    int change = b.sum / b.dy;
                    b.sum = b.sum % b.dy;
                    if (b.positive_slope) {
                        b.x = b.x + change;
                    }
                    else {
                        b.x = b.x - change;
                    }
                }
            }
        }
    }

    private void printAEL(int y) {
        System.out.println("---AEL--- (y=" + y +")");
        for (Bucket b : AEL) {
            b.print();
        }
        System.out.println();
    }

    private void printET() {
        Iterator it = ET.keySet().iterator();
        while (it.hasNext()) {
            Integer key = (Integer) it.next();
            System.out.printf("\nScanline %d:\n\n", key);
            for (Bucket b : ET.get(key)) {
                b.print();
            } 
        }
    }
    
}

simpleCanvas.java

//
//  simpleCanvas.java
//  
//
//  Created by Joe Geigel on 1/21/10.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

/**
 * This is a simple class to allow pixel level drawing in
 * java without using OpenGL
 *
 * techniques for pixel drawing taken from:
 *
 *   http://www.cap-lore.com/code/java/JavaPix.java
 *
 *  with my thanks.
 */
import java.awt.*;
import java.awt.image.*;
import java.awt.geom.*;
import java.util.*;

public class simpleCanvas extends Canvas {
  
	public BufferedImage I;
	private int	clearC;
	private int width;
	private int height;
	private Color curColor;

	simpleCanvas (int w, int h) 
	{
		width = w;
		height = h;
		I = new BufferedImage (width, height, BufferedImage.TYPE_INT_RGB);
		curColor = new Color (0.0f, 0.0f, 0.0f);
		
		setSize (w, h);

	}
	
	
	public void clear()
	{
		for (int i=0; i < width; i++)
			for (int j=0; j < height; j++)
				I.setRGB (i,j, curColor.getRGB());
	}
	
	public void setColor (float r, float g, float b)
	{
		curColor = new Color (r,g, b);
	}
	
	
	public void setPixel (int x, int y)
	{
		I.setRGB (x, (height - y - 1), curColor.getRGB());
		
	}
	
	public void paint(Graphics g)
    {
		// draw pixels
        g.drawImage(I, 0, 0, Color.red, null);
    }	

}