import java.awt.Color;
import Vertex3D;
import Matrix3D;
import Surface;
import ZRaster;

class EdgeEqn {
    public float A, B, C;
    public int flag;

    public EdgeEqn(Vertex3D v0, Vertex3D v1)

    {

        A = v0.y - v1.y;

        B = v1.x - v0.x;

        C = -0.5f * (A*(v0.x + v1.x) + B*(v0.y + v1.y));



        flag = 0;

        if (A >= 0) flag += 8;

        if (B >= 0) flag += 1;

    }



    public void flip()

    {

        A = -A;

        B = -B;

        C = -C;

    }



    public float evaluate(int x, int y)

    {

        return (A*x + B*y + C);

    }

}



public class Triangle {

    private static Vertex3D vlist[];

    protected int v[];

    protected float r[], g[], b[];

    protected Surface surface;

    private boolean culled;

    private Vertex3D vert[];
    public Point3D unitNormal;
    public Point3D centroid;
	public Vertex3D outputvert[];
	public int output;

	public Vertex3D tempvert[];int tsize;
	public Vertex3D invert[];int ivsize;
	public Vertex3D outvert[];int ovsize;

    public Triangle(){}

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

        r = new float[3];
        g = new float[3];
        b = new float[3];

        vert = new Vertex3D[3];
        vert[0] = new Vertex3D();
        vert[1] = new Vertex3D();
        vert[2] = new Vertex3D();

        unitNormal = new Point3D();
        centroid = new Point3D();

        outputvert = new Vertex3D[10];
        output = 0;

		tempvert = new Vertex3D[20];
		invert = new Vertex3D[20];
		outvert = new Vertex3D[20];
		tsize = ivsize = ovsize =0;
		for (int i = 0; i < 20; i++)
		{
			invert[i] = new Vertex3D();
			outvert[i] = new Vertex3D();
			tempvert[i] = new Vertex3D();
		}

        scale = -1;

        culled = false;

    }

    public void setSurface(Surface s)
    {
        surface = s;
    }

    public Surface getSurface()
    {
        return surface;
    }

    public boolean isVisible()
    {
        return (!culled);
    }

    /*

        ... you'll need to modify the following two methods ...

    */
    public void findCentroid()
    {
        vert[0] = vlist[v[0]];
		vert[1] = vlist[v[1]];
		vert[2] = vlist[v[2]];
		 centroid.x = (vert[0].x + vert[1].x + vert[2].x)/3;
		 centroid.y = (vert[0].y + vert[1].y + vert[2].y)/3;
		 centroid.z = (vert[0].z + vert[1].z + vert[2].z)/3;

    }
	public void findUnitNormal()
	{
		vert[0] = vlist[v[0]];
		vert[1] = vlist[v[1]];
		vert[2] = vlist[v[2]];
		Point3D t1 = new Point3D();
		Point3D t2 = new Point3D();

		t1.x = vert[1].x - vert[0].x;
		t1.y = vert[1].y - vert[0].y;
		t1.z = vert[1].z - vert[0].z;

		t2.x = vert[2].x - vert[0].x;
		t2.y = vert[2].y - vert[0].y;
		t2.z = vert[2].z - vert[0].z;

		float xx = t1.y*t2.z - t2.y*t1.z;
		float yy = t1.z*t2.x - t2.z*t1.x;
		float zz= t1.x*t2.y - t2.x*t1.y;

		float size = (float) (1/Math.sqrt(xx*xx + yy*yy + zz*zz));
		unitNormal.x = xx*size;
		unitNormal.y = yy*size;
		unitNormal.z = zz*size;
	}

    public void Illuminate(Light l[], int lights, Point3D eye, Point3D lookat, boolean cull)
    {
        findCentroid();
    	findUnitNormal();
    	Point3D eyeview = new Point3D();
    	eyeview.x = centroid.x - eye.x;
		eyeview.y = centroid.y - eye.y;
		eyeview.z = centroid.z - eye.z;
		/*float size = (float) (1/Math.sqrt(eyeview.x*eyeview.x + eyeview.y*eyeview.y + eyeview.z*eyeview.z));
		eyeview.x *= size;
		eyeview.y *= size;
		eyeview.z *= size;*/
		float t = eyeview.x*unitNormal.x + eyeview.y*unitNormal.y + eyeview.z*unitNormal.z;
		if (t > 0) {culled = true;}
		else
		{
			float costheta = -1.0f*(unitNormal.x*l[1].x + unitNormal.y*l[1].y + unitNormal.z*l[1].z);
			if (costheta < 0) costheta = 0.0f;
			float IR = surface.ka*l[0].ir*surface.r + l[1].ir*surface.kd*surface.r*costheta;
			float IG = surface.ka*l[0].ig*surface.g + l[1].ig*surface.kd*surface.g*costheta;
			float IB = surface.ka*l[0].ib*surface.b + l[1].ib*surface.kd*surface.b*costheta;

       		for (int i = 0; i < 3; i++)
       		{
            	r[i] = IR;
	            g[i] = IG;
	            b[i] = IB;
			}
		}
    }

    public void ClipAndDraw(ZRaster raster, Matrix3D project)
    {

    	vert[0] = vlist[v[0]];
		vert[1] = vlist[v[1]];
		vert[2] = vlist[v[2]];

		invert[0] = vert[0];
		invert[1] = vert[1];
		invert[2] = vert[2];
		ivsize = 3;

    	ClipNear();
    	if (tsize >2)
    	{
    		ClipFar();
    		if (ovsize > 2)
    		{
    			for (int j = 1; j < (ovsize-1); j++)
    			{
    				vert[0] = project.transform(outvert[0]);
    				vert[1] = project.transform(outvert[j]);
    				vert[2] = project.transform(outvert[j+1]);
    				//System.out.println("vert[0] x="+vert[0].x+"; y="+vert[0].y+"; z="+vert[0].z);
    				//System.out.println("vert[1] x="+vert[1].x+"; y="+vert[1].y+"; z="+vert[1].z);
    				//System.out.println("vert[2] x="+vert[2].x+"; y="+vert[2].y+"; z="+vert[2].z);
    				try{
    				Draw(raster);
    				} catch (ArrayIndexOutOfBoundsException e){}
    			}
    		}
    	}
    }


	public void ClipNear()  //Clip if z < -1
	{
		tsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();
		//System.out.println("ClipNear() is called! ");

		p1.copy(invert[ivsize - 1]);
		for (int i = 0; i < ivsize; i++)
		{
			p2.copy(invert[i]);
			if (p2.z >= -1)
			{
				if (p1.z >= -1)
				{ tempvert[tsize].copy(p2); tsize++;}
				else
				{
					u = (-1 - p1.z)/(p2.z - p1.z);
					ptemp.x = (p2.x - p1.x)*u + p1.x;
					ptemp.y = (p2.y - p1.y)*u + p1.y;
					ptemp.z = -1.0f;
					tempvert[tsize].copy(ptemp); tsize++;
					tempvert[tsize].copy(p2); tsize++;
					//System.out.println("p1 ClipNear()! p1:x="+p1.x+"; y="+p1.y+"; z="+p1.z);
					//System.out.println("pt ClipNear()! pt:x="+ptemp.x+"; y="+ptemp.y+"; z="+ptemp.z);
				    //System.out.println("u= "+u);
				    //System.out.println("tsize= "+tsize);
				}
			}
			else if (p1.z >= -1)
			{
				u = (-1 - p1.z)/(p2.z - p1.z);
				ptemp.x = (p2.x - p1.x)*u + p1.x;
				ptemp.y = (p2.y - p1.y)*u + p1.y;
				ptemp.z = -1.0f;
				tempvert[tsize].copy(ptemp); tsize++;
				//System.out.println("p2 ClipNear()! p2:x="+p2.x+"; y="+p2.y+"; z="+p2.z);
				//System.out.println("pt ClipNear()! pt:x="+ptemp.x+"; y="+ptemp.y+"; z="+ptemp.z);
			    //System.out.println("u= "+u);
			    //System.out.println("tsize= "+tsize);
			}
			p1.copy(p2);
		}
	}

	public void ClipFar()  //Clip if z > 1
	{
		ovsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();
		//System.out.println("ClipFar() is called! ");

		p1.copy(tempvert[tsize-1]);
		for (int i = 0; i < tsize; i++)
		{
			p2.copy(tempvert[i]);
			if (p2.z <= 1)
			{
				if (p1.z <= 1)
				{ outvert[ovsize].copy(p2); ovsize++;}
				else
				{
					u = (1 - p1.z)/(p2.z - p1.z);
					ptemp.x = (p2.x - p1.x)*u + p1.x;
					ptemp.y = (p2.y - p1.y)*u + p1.y;
					ptemp.z = 1.0f;
					outvert[ovsize].copy(ptemp); ovsize++;
					outvert[ovsize].copy(p2); ovsize++;
					//System.out.println("p1 ClipFar()! p1:x="+p1.x+"; y="+p1.y+"; z="+p1.z);
					//System.out.println("p1 ClipFar()! p2:x="+p2.x+"; y="+p2.y+"; z="+p2.z);
					//System.out.println("pt ClipFar()! pt:x="+ptemp.x+"; y="+ptemp.y+"; z="+ptemp.z);
                    //System.out.println("u= "+u);
                    //System.out.println("ovsize= "+ovsize);
				}
			}
			else if (p1.z <= 1)
			{
				u = (1 - p1.z)/(p2.z - p1.z);
				ptemp.x = (p2.x - p1.x)*u + p1.x;
				ptemp.y = (p2.y - p1.y)*u + p1.y;
				ptemp.z = 1.0f;
				outvert[ovsize].copy(ptemp); ovsize++;
				//System.out.println("p2 ClipFar()! p2:x="+p2.x+"; y="+p2.y+"; z="+p2.z);
				//System.out.println("p2 ClipFar()! p1:x="+p1.x+"; y="+p1.y+"; z="+p1.z);
				//System.out.println("pt ClipFar()! pt:x="+ptemp.x+"; y="+ptemp.y+"; z="+ptemp.z);
                //System.out.println("u= "+u);
                //System.out.println("ovsize= "+ovsize);
			}
			p1.copy(p2);
		}
	}


    public void setVertexList(Vertex3D list[])
    {
        vlist = list;
    }

    protected EdgeEqn edge[];

    protected float area;

    protected int xMin, xMax, yMin, yMax;

    protected float scale;

    private static byte sort[][] = {

        {0, 1}, {1, 2}, {0, 2}, {2, 0}, {2, 1}, {1, 0}

    };



    public void PlaneEqn(float eqn[], float p0, float p1, float p2)

    {

        float Ap, Bp, Cp;



        float sp0 = scale * p0;

        float sp1 = scale * p1;

        float sp2 = scale * p2;

        Ap = edge[0].A*sp2 + edge[1].A*sp0 + edge[2].A*sp1;

        Bp = edge[0].B*sp2 + edge[1].B*sp0 + edge[2].B*sp1;

        Cp = edge[0].C*sp2 + edge[1].C*sp0 + edge[2].C*sp1;

        eqn[0] = Ap;

        eqn[1] = Bp;

        eqn[2] = Ap*xMin + Bp*yMin + Cp;

    }



    protected boolean triangleSetup(Raster r)

    {

        if (edge == null) edge = new EdgeEqn[3];



        /*

            Compute the three edge equations

        */

        edge[0] = new EdgeEqn(vert[0], vert[1]);

        edge[1] = new EdgeEqn(vert[1], vert[2]);

        edge[2] = new EdgeEqn(vert[2], vert[0]);



        /*

            Trick #1: Orient edges so that the

            triangle's interior lies within all

            of their positive half-spaces.



            Assuring that the area is positive

            accomplishes this

        */

        area = edge[0].C + edge[1].C + edge[2].C;



        if (area == 0)

            return false;



        if (area < 0) {

            edge[0].flip();

            edge[1].flip();

            edge[2].flip();

            area = -area;

        }



        /*

            Trick #2: compute bounding box

        */

        int xflag = edge[0].flag + 2*edge[1].flag + 4*edge[2].flag;

        int yflag = (xflag >> 3) - 1;

        xflag = (xflag & 7) - 1;



        xMin = (int) (vert[sort[xflag][0]].x);

        xMax = (int) (vert[sort[xflag][1]].x + 1);

        yMin = (int) (vert[sort[yflag][1]].y);

        yMax = (int) (vert[sort[yflag][0]].y + 1);



        /*

            clip triangle's bounding box to raster

        */

        xMin = (xMin < 0) ? 0 : xMin;

        xMax = (xMax >= r.width) ? r.width - 1 : xMax;

        yMin = (yMin < 0) ? 0 : yMin;

        yMax = (yMax >= r.height) ? r.height - 1 : yMax;

        return true;

    }



    public void Draw(ZRaster raster)

    {

        float zPlane[] = new float[3];

        float rPlane[] = new float[3];

        float gPlane[] = new float[3];

        float bPlane[] = new float[3];



        if (!triangleSetup(raster)) return;

        scale = 1 / area;

        PlaneEqn(zPlane, vert[0].z, vert[1].z, vert[2].z);

        PlaneEqn(rPlane, r[0], r[1], r[2]);

        PlaneEqn(gPlane, g[0], g[1], g[2]);

        PlaneEqn(bPlane, b[0], b[1], b[2]);



        int x, y;

        float A0 = edge[0].A;        float B0 = edge[0].B;        float t0 = A0*xMin + B0*yMin + edge[0].C;

        float A1 = edge[1].A;        float B1 = edge[1].B;        float t1 = A1*xMin + B1*yMin + edge[1].C;

        float A2 = edge[2].A;        float B2 = edge[2].B;        float t2 = A2*xMin + B2*yMin + edge[2].C;

        float Az = zPlane[0];        float Bz = zPlane[1];        float tz = zPlane[2];

        float Ar = rPlane[0];        float Br = rPlane[1];        float tr = rPlane[2];

        float Ag = gPlane[0];        float Bg = gPlane[1];        float tg = gPlane[2];

        float Ab = bPlane[0];        float Bb = bPlane[1];        float tb = bPlane[2];



        yMin *= raster.width;

        yMax *= raster.width;



        /*

             .... scan convert triangle ....

        */

        for (y = yMin; y <= yMax; y += raster.width) {

	        float e0 = t0;

	        float e1 = t1;

	        float e2 = t2;

	        float r = tr;

	        float g = tg;

	        float b = tb;

	        float z = tz;

	        boolean beenInside = false;

	        for (x = xMin; x <= xMax; x++) {

	            if ((e0 >= 0) && (e1 >= 0) && (e2 >= 0)) {       // all 3 edges must be >= 0

	                int iz = (int) z;

	                if (iz <= raster.zbuff[y+x]) {

                        int pixr = (int) (255.0f*r);

	                    int pixg = (int) (255.0f*g);

	                    int pixb = (int) (255.0f*b);

                        pixr = ((pixr & ~255) == 0) ? pixr << 16 : ((r < 0)	? 0 : 255<<16);

                        pixg = ((pixg & ~255) == 0) ? pixg << 8  : ((g < 0)	? 0 : 255<<8);

                        pixb = ((pixb & ~255) == 0) ? pixb       : ((b < 0)	? 0 : 255);

		                raster.pixel[y+x] = (0xff000000 | pixr | pixg | pixb);

		                raster.zbuff[y+x] = iz;

		            }

		            beenInside = true;

	            } else if (beenInside) break;

	            e0 += A0;   e1 += A1;   e2 += A2;

	            z += Az;    r += Ar;    g += Ag;    b += Ab;

	        }

	        t0 += B0;   t1 += B1;   t2 += B2;

	        tz += Bz;   tr += Br;   tg += Bg;   tb += Bb;

        }

    }

}

/*
public void ClipLeft()  //Clip if x < -1
	{
		ovsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();

		p1 = invert[ivsize-1];
		for (int i = 0; i < ivsize; i++)
		{
			p2 = invert[i];
			if (p2.x >= -1)
			{
				if (p1.x >= -1)
				{ outvert[ovsize] = p2; ovsize++;}
				else
				{
					u = (-1 - p1.x)/(p2.x - p1.x);
					ptemp.x = -1.0f;
					ptemp.y = (p2.y - p1.y)*u + p1.y;
					ptemp.z = (p2.z - p1.z)*u + p1.z;
					outvert[ovsize] = ptemp; ovsize++;
					outvert[ovsize] = p2; ovsize++;
				}
			}
			else if (p1.x >= -1)
			{
				u = (-1 - p1.x)/(p2.x - p1.x);
				ptemp.x = -1.0f;
				ptemp.y = (p2.y - p1.y)*u + p1.y;
				ptemp.z = (p2.z - p1.z)*u + p1.z;
				outvert[ovsize] = ptemp; ovsize++;
			}
			p1 = p2;
		}
	}

	public void ClipRight()  //Clip if x > 1
	{
		ovsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();

		p1 = invert[ivsize-1];
		for (int i = 0; i < ivsize; i++)
		{
			p2 = invert[i];
			if (p2.x <= 1)
			{
				if (p1.x <= 1)
				{ outvert[ovsize] = p2; ovsize++;}
				else
				{
					u = (1 - p1.x)/(p2.x - p1.x);
					ptemp.x = 1.0f;
					ptemp.y = (p2.y - p1.y)*u + p1.y;
					ptemp.z = (p2.z - p1.z)*u + p1.z;
					outvert[ovsize] = ptemp; ovsize++;
					outvert[ovsize] = p2; ovsize++;
				}
			}
			else if (p1.x <= 1)
			{
				u = (1 - p1.x)/(p2.x - p1.x);
				ptemp.x = 1.0f;
				ptemp.y = (p2.y - p1.y)*u + p1.y;
				ptemp.z = (p2.z - p1.z)*u + p1.z;
				outvert[ovsize] = ptemp; ovsize++;
			}
			p1 = p2;
		}
	}

	public void ClipTop()  //Clip if y < -1
	{
		ovsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();

		p1 = invert[ivsize-1];
		for (int i = 0; i < ivsize; i++)
		{
			p2 = invert[i];
			if (p2.y >= -1)
			{
				if (p1.y >= -1)
				{ outvert[ovsize] = p2; ovsize++;}
				else
				{
					u = (-1 - p1.y)/(p2.y - p1.y);
					ptemp.x = (p2.x - p1.x)*u + p1.x;
					ptemp.y = -1.0f;
					ptemp.z = (p2.z - p1.z)*u + p1.z;
					outvert[ovsize] = ptemp; ovsize++;
					outvert[ovsize] = p2; ovsize++;
				}
			}
			else if (p1.y >= -1)
			{
				u = (-1 - p1.y)/(p2.y - p1.y);
				ptemp.x = (p2.x - p1.x)*u + p1.x;
				ptemp.y = -1.0f;
				ptemp.z = (p2.z - p1.z)*u + p1.z;
				outvert[ovsize] = ptemp; ovsize++;
			}
			p1 = p2;
		}
	}

	public void ClipBottom()  //Clip if y > 1
	{
		ovsize = 0;
		float u = 0;
		Vertex3D p1 = new Vertex3D();
		Vertex3D p2 = new Vertex3D();
		Vertex3D ptemp = new Vertex3D();

		p1 = invert[ivsize-1];
		for (int i = 0; i < ivsize; i++)
		{
			p2 = invert[i];
			if (p2.y <= 1)
			{
				if (p1.y <= 1)
				{ outvert[ovsize] = p2; ovsize++;}
				else
				{
					u = (1 - p1.y)/(p2.y - p1.y);
					ptemp.x = (p2.x - p1.x)*u + p1.x;
					ptemp.y = 1.0f;
					ptemp.z = (p2.z - p1.z)*u + p1.z;
					outvert[ovsize] = ptemp; ovsize++;
					outvert[ovsize] = p2; ovsize++;
				}
			}
			else if (p1.y <= 1)
			{
				u = (1 - p1.y)/(p2.y - p1.y);
				ptemp.x = (p2.x - p1.x)*u + p1.x;
				ptemp.y = 1.0f;
				ptemp.z = (p2.z - p1.z)*u + p1.z;
				outvert[ovsize] = ptemp; ovsize++;
			}
			p1 = p2;
		}
	}

*/