import java.util.*;
import Drawable;
import Vertex2D;

class Triangle implements Drawable {
    protected Vertex2D v[];
    protected int idx_max, idx_min, idx_mid;//used when sorting vertices
    protected int bk_exi = -1;//=-1, no bk_point, =1, yes bk_point
    protected int color;
    protected boolean isFlat;//=true when vertices share same color 

    protected float area;//area of a triangle

    //A, B and C are coefficients of Color Plane. b, g, r, a are for
    //blue, green, red and alpha
    protected float Ab, Bb, Cb, Ag, Bg, Cg, Ar, Br, Cr, Aa, Ba, Ca;
    
    //default contructor. No use in my work-no children classes
    public Triangle() {
    }

    //Constructor
    public Triangle(Vertex2D v0, Vertex2D v1, Vertex2D v2) {
        v = new Vertex2D[3];
        v[0] = v0;
        v[1] = v1;
        v[2] = v2;

	isFlat = (v0.argb == v1.argb) && (v0.argb == v2.argb);
	if (isFlat) {
	    color = v0.argb;
	} else {
	    area = (float)((v[0].x * v[1].y + v[2].x * v[0].y +
			    v[1].x * v[2].y - v[2].x * v[1].y -
			    v[0].x * v[2].y - v[1].x * v[0].y)*0.5);
	
	    if(area == 0.0f)
		return;
	    if(area < 0)
		//just for debg
		System.out.println(area);
	    color = 0;
	    //calculate coefficients for Color Plane
	    ABCargb();
	}
    }

    private void ABCargb() {
	int t0 = v[0].argb;
	int t1 = v[1].argb;
	int t2 = v[2].argb;
    
	//In this method, I directly use the formular given in lecture notes
	//to calculate Color Plane, see Slide 22 of lecture 7
	Ab = ((v[1].y-v[2].y) * (t0 & 255) +
	      (v[2].y-v[0].y) * (t1 & 255) +
	      (v[0].y-v[1].y) * (t2 & 255)) / area * 0.5f;
	Bb = ((v[2].x-v[1].x) * (t0 & 255) +
	      (v[0].x-v[2].x) * (t1 & 255) +
	      (v[1].x-v[0].x) * (t2 & 255)) / area * 0.5f;
	Cb = ((v[1].x*v[2].y - v[2].x*v[1].y) * (t0 & 255) +
	      (v[2].x*v[0].y - v[0].x*v[2].y) * (t1 & 255) +
	      (v[0].x*v[1].y - v[1].x*v[0].y) * (t2 & 255)) / area * 0.5f;

	t0 >>= 8;   t1 >>= 8;   t2 >>= 8;
	Ag = ((v[1].y-v[2].y) * (t0 & 255) +
	      (v[2].y-v[0].y) * (t1 & 255) +
	      (v[0].y-v[1].y) * (t2 & 255)) / area * 0.5f;
	Bg = ((v[2].x-v[1].x) * (t0 & 255) +
	      (v[0].x-v[2].x) * (t1 & 255) +
	      (v[1].x-v[0].x) * (t2 & 255)) / area * 0.5f;
	Cg = ((v[1].x*v[2].y - v[2].x*v[1].y) * (t0 & 255) +
	      (v[2].x*v[0].y - v[0].x*v[2].y) * (t1 & 255) +
	      (v[0].x*v[1].y - v[1].x*v[0].y) * (t2 & 255)) / area * 0.5f;

	t0 >>= 8;   t1 >>= 8;   t2 >>= 8;
	Ar = ((v[1].y-v[2].y) * (t0 & 255) +
	      (v[2].y-v[0].y) * (t1 & 255) +
	      (v[0].y-v[1].y) * (t2 & 255)) / area * 0.5f;
	Br = ((v[2].x-v[1].x) * (t0 & 255) +
	      (v[0].x-v[2].x) * (t1 & 255) +
	      (v[1].x-v[0].x) * (t2 & 255)) / area * 0.5f;
	Cr = ((v[1].x*v[2].y - v[2].x*v[1].y) * (t0 & 255) +
	      (v[2].x*v[0].y - v[0].x*v[2].y) * (t1 & 255) +
	      (v[0].x*v[1].y - v[1].x*v[0].y) * (t2 & 255)) / area * 0.5f;
	
	t0 >>= 8;   t1 >>= 8;   t2 >>= 8;
	Aa = ((v[1].y-v[2].y) * (t0 & 255) +
	      (v[2].y-v[0].y) * (t1 & 255) +
	      (v[0].y-v[1].y) * (t2 & 255)) / area * 0.5f;
	Ba = ((v[2].x-v[1].x) * (t0 & 255) +
	      (v[0].x-v[2].x) * (t1 & 255) +
	      (v[1].x-v[0].x) * (t2 & 255)) / area * 0.5f;
	Ca = ((v[1].x*v[2].y - v[2].x*v[1].y) * (t0 & 255) +
	      (v[2].x*v[0].y - v[0].x*v[2].y) * (t1 & 255) +
	      (v[0].x*v[1].y - v[1].x*v[0].y) * (t2 & 255)) / area * 0.5f;
    }

    //There are three steps in spanning the triangle
    //1. Find the intersections of the scan line with two edges of tri.
    //2. Sort the intersections by increasing x coordinates
    //3. Fill in all pixels between pairs of intersections.

    private void sortPoints() {
	float temp_max = -1000.0f, temp_min = 1000.0f;
	
	for( int i = 0; i < 3; i++)
	    {
		if(temp_max <= v[i].y) {
		    idx_max = i;
		    temp_max = v[i].y;
		}		
		if(temp_min >= v[i].y) {
		    idx_min = i;
		    temp_min = v[i].y;
		}
	    }

	//check mid-point
	if(idx_max == idx_min)
	    //degenerate triangle
	    {
		idx_max = 0;
		idx_min = 1;
		idx_mid = 2;
	    }
	else
	    idx_mid = 3 - idx_max - idx_min;
	if( (int)(v[idx_mid].y+0.5f) == (int)(v[idx_min].y +0.5f) ) 
	    //top edge parallel to scan line
	    bk_exi = -1;
	else if( (int)(v[idx_mid].y+0.5f) == (int)(v[idx_max].y+0.5f) )
	    //bottom edge parallel to scan line
	    bk_exi = 0;
	else
	    //break point in between
	    bk_exi = 1;
    }	
	
    
    public void Draw(Raster r) {
	Vector tEdges;
	
	sortPoints();

	if( bk_exi == -1 ) {	    
	    activeEdge at1 = new activeEdge(v[idx_min],v[idx_max]);

	    activeEdge at2 = new activeEdge(v[idx_mid], v[idx_max]);
	    
	    tEdges = new Vector();
	    tEdges.addElement(at1);
	    tEdges.addElement(at2);
	    drawSpanLines(r, tEdges);
	}

	if( bk_exi == 0 ) {	    
	    activeEdge at1 = new activeEdge(v[idx_min], v[idx_max]);
	    
	    activeEdge at2 = new activeEdge(v[idx_min], v[idx_mid]);
	    
	    tEdges = new Vector();
	    tEdges.addElement(at1);
	    tEdges.addElement(at2);
	    drawSpanLines(r, tEdges);
	}

	if( bk_exi == 1 ) {	    
	    activeEdge at1 = new activeEdge(v[idx_min], v[idx_max]);
	    
	    activeEdge at2 = new activeEdge(v[idx_min], v[idx_mid]);

	    activeEdge at3 = new activeEdge(v[idx_mid], v[idx_max]);
	    
	    tEdges = new Vector();
	    tEdges.addElement(at1);
	    tEdges.addElement(at2);
	    tEdges.addElement(at3);
	    drawSpanLines(r, tEdges);
	}
    }

    private void drawSpanLines(Raster r, Vector tEdges) {
	int index = 1;
	activeEdge at;
	int y_min, y_max, x_start, x_end, y, dY;
	int edge_y_min, edge_y_max, edge_x_start, edge_x_end, edge_dY;
	float true_x = 0.0f, true_edge_x = 0.0f;
	float slope, edge_slope;
	int max_xline, min_xline;
	
	//This is the edge spans from y_min to y_max. It is the edge that
	//we walk along till the bottom line of clipped raster for this
	//triangle
	activeEdge at1 = (activeEdge)tEdges.elementAt(0);
	
	//Figure out the span along y_direction
	y_min = (int)(at1.y_start+0.5f);//round to nearest integer
	y_max = (int)(at1.y_end+0.5f);//round to nearest integer
	x_start = (int)(at1.x_start + 0.5f);
	x_end = (int)(at1.x_end + 0.5f);
	y = y_min;//y starts from here
	dY = y_max - y_min;
	slope = ((float)(x_start - x_end))/((float)(y_min - y_max)); 
	
      	//Pick all other edges(for triangle, at most 2) out one by one,
	//store them in at temperorarily
	
	for(;;) {
	    //all edges must be walked
	    if(index < tEdges.size()) {
		//kick an edge out of storage.
		at = (activeEdge)tEdges.elementAt(index);
		index++;
	    }else
		return;

	    //pick this edge, scan convert
	    edge_y_min = (int)(at.y_start+0.5f);
	    //round to nearest integer
	    edge_y_max = (int)(at.y_end+0.5f);
	    //round to nearest integer
	    edge_x_start = (int)(at.x_start+0.5f);
	    edge_x_end = (int)(at.x_end+0.5f);
	    edge_dY = edge_y_max - edge_y_min;
	    edge_slope = ((float)(edge_x_start - edge_x_end))/
	                 ((float)(edge_y_min - edge_y_max));

	    while( y <= edge_y_max && y<= y_max) {

		if(dY != 0) {
		    //true_x is x(corresponding to current y)calculated
		    //with the straight line equation. So is the true_edge_x
		    //show below
		    true_x = (float)x_start + slope*((float)(y - y_min));
		}

		if(edge_dY != 0) {
		    true_edge_x = (float)edge_x_start + edge_slope*
		      ((float)(y - edge_y_min));
		}

		min_xline = (int)Math.ceil(Math.min(true_x, true_edge_x));
		max_xline = (int)Math.floor(Math.max(true_x, true_edge_x));

		if(dY == 0) {
		    //be careful when degenerate triangles are found
		    if(edge_dY != 0) {
			System.out.println("degenerate != dY");
			System.exit(0);
		    }
		    //then edge_dY == 0
		    min_xline = (int)Math.ceil(Math.min(
				     Math.min(at.x_end, at1.x_end),
				     Math.min(at.x_end, at.x_start)));
		    max_xline = (int)Math.floor(Math.max(
				     Math.max(at.x_end, at1.x_end),
				     Math.max(at.x_end, at.x_start)));
		}
		if(edge_dY == 0 && dY != 0){
		    min_xline = (int)Math.ceil(Math.min(at1.x_start,
							at1.x_end));
		    max_xline = (int)Math.floor(Math.max(at1.x_start,
							 at1.x_end));
		}

		//Start scan
		for( int x_line = min_xline; x_line <= max_xline;
		     x_line++)
		    r.setPixel(getColor(x_line, y), x_line, y);
		
		//next scan line
		y++;
	    }
	    y--;
	}
    }

    class activeEdge {
	float x_start, y_start, x_end, y_end;
	int c_start, c_end;

	public activeEdge(Vertex2D v_start, Vertex2D v_end) {
	    this.x_start = v_start.x;
	    this.y_start = v_start.y;
	    this.c_start = v_start.argb;
	    this.x_end = v_end.x;
	    this.y_end = v_end.y;
	    this.c_end = v_end.argb;
	}
    }

    private int getColor(int x, int y) {
	if(isFlat)
	    return color;
	    
	//Calculate the color at (x,y) using Color Plane Equation
	int pixa = (int)(Aa * x + Ba * y + Ca + 0.5f);
	int pixr = (int)(Ar * x + Br * y + Cr + 0.5f);
	int pixg = (int)(Ag * x + Bg * y + Cg + 0.5f);
	int pixb = (int)(Ab * x + Bb * y + Cb + 0.5f);

	return (pixa<<24 | pixr<<16 | pixg<<8 | pixb);
    }
}