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[];

	// these values used for hodeman sutherland clipping
	// used as constants instead of passed as values, for simplicity sake
    private final static int minZDist = -50;
    private final static int maxZDist = 50;
    private final static int HITHER = 0;
    private final static int YON = 1;
    private int cnt = 0;

    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();
        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 Illuminate(Light l[], int lights, Point3D eye, boolean cull)
    {
        boolean cantcull = false;
        int i,j,k;
        Point3D norm; // normal to the triangle
        Point3D eyeV = new Point3D(); // vector from eye to triangle
        Point3D V, N, L, R;  // vectors as defined in lecture

        
        //added this to handle backface culling

        // this code used on assumption that normals are availble per point
        /*
        for(i = 0; i < 3; i++ ) {
            if(!vert[i].hasNormal) cantcull = true;
        }
        // compute normal of triangle as average of normals of vertices
        norm.x = (vert[0].nx + vert[1].nx + vert[2].nx)/3;
        norm.y = (vert[0].ny + vert[1].ny + vert[2].ny)/3;
        norm.z = (vert[0].nz + vert[1].nz + vert[2].nz)/3;
        */
        
        // initialzes the vertices
        vert[0] = vlist[v[0]];
        vert[1] = vlist[v[1]];
        vert[2] = vlist[v[2]];
         
        // calculate the normal to the triangle
        norm = cross(new Point3D(vert[0].x-vert[1].x, vert[0].y - vert[1].y, vert[0].z - vert[1].z),
                     new Point3D(vert[0].x-vert[2].x, vert[0].y - vert[2].y, vert[0].z - vert[2].z));

        // calculte the centroid
        Point3D center = new Point3D();
        center.x = (vert[0].x + vert[1].x + vert[2].x)/3;
        center.y = (vert[0].y + vert[1].y + vert[2].y)/3;
        center.z = (vert[0].z + vert[1].z + vert[2].z)/3;


        if(cull)
        {
            culled = false;

            // sets the Normal based on one calculated by cross producting the edges of triangle
            for(i = 0; i < 3; i++ )
            {
                if(!vert[i].hasNormal)
                {
                    vert[i].nx = norm.x;
                    vert[i].ny = norm.y;
                    vert[i].nz = norm.z;
                    vert[i].hasNormal = true;
                }
            }
            
            // calculate the vector from the eye to the surface
            eyeV.x = center.x - eye.x;
            eyeV.y = center.y - eye.y;
            eyeV.z = center.z - eye.z;
            
            if(dot(norm, eyeV) > 0)
            {
                culled = true;
            }
        }
        
        
        // illuminate

        if( !culled )
        {
            float ir, ig, ib;
            
            // intensity of light for each color
            ir = 0; ig = 0; ib = 0;
            
            // compute variables as specified in lecture
            V = normalize(scalar(-1, eyeV));
            N = normalize(norm);
            
            for(i = 0; i < lights; i++ )
            {
                // This handles point lights
                /*L = normalize(new Point3D(l[i].x - vert[0].x,
                                l[i].y - vert[0].y,
                                l[i].z - vert[0].z));*/

                // this handles directional lights
                L = normalize(new Point3D(-l[i].x,
                                -l[i].y,
                                -l[i].z ));
                                
                R = normalize(sub(scalar(2*dot(N,L), N), L));
                
                if(l[i].lightType == l[i].AMBIENT )
                {
                    ir += surface.ka * l[i].ir;
                    ig += surface.ka * l[i].ig;
                    ib += surface.ka * l[i].ib;
                }
                else
                {
                    ir += l[i].ir * (surface.kd * dot(N,L) + surface.ks * Math.pow(dot(V,R), surface.ns));
                    ig += l[i].ig * (surface.kd * dot(N,L) + surface.ks * Math.pow(dot(V,R), surface.ns));
                    ib += l[i].ib * (surface.kd * dot(N,L) + surface.ks * Math.pow(dot(V,R), surface.ns));
                }
                
                //System.out.println(">" + ir + "," + ig + "," + ib);
            }
            for (i = 0; i < 3; i++) {
                r[i] = surface.r * ir;
                g[i] = surface.g * ig;
                b[i] = surface.b * ib;
            }
        }

        
        
    }
    
    // elementary matrix operations
    private Point3D cross(Point3D a, Point3D b)
    {
        return new Point3D(-a.z * b.y + a.y * b.z, a.z * b.x - a.x * b.z, -a.y * b.x + a.x * b.y);
    }
    
    private float dot(Point3D a, Point3D b)
    {
        return (a.x * b.x + a.y * b.y + a.z * b.z);
    }
    
    private Point3D normalize(Point3D in)
    {
        float mag = (float)Math.sqrt(in.x * in.x + in.y * in.y + in.z * in.z);
        return new Point3D(in.x / mag, in.y / mag, in.z / mag);
    }
    
    private Point3D add(Point3D a, Point3D b)
    {
        return new Point3D(a.x + b.x, a.y + b.y, a.z + b.z);
    }
    
    private Point3D sub(Point3D a, Point3D b)
    {
        return new Point3D(a.x - b.x, a.y - b.y, a.z - b.z);
    }
    
    private Point3D scalar(float s, Point3D a)
    {
        return new Point3D(s * a.x, s * a.y, s* a.z);
    }
    
    

	// This begins the code for the Sutherland Hodgeman polygon clipping
	// algorithm.
	// this code is based on an example from Hearn and Baker 238-242

	// tests if a given point is within the neawr and far edge of the frustrum
    private boolean inside(Vertex3D p, int b)
    {

        if (b == HITHER)
        {
            if (p.z < minZDist) return false;
        }
        else
        {
            if (p.z > maxZDist) return false;
        }

        return true;
    }

    // chcecks if both ends of vertex are in correct place
    private boolean crossCheck(Vertex3D p1, Vertex3D p2, int b)
    {

        if (inside(p1, b) == inside(p2, b)) return false;
        else return true;

    }

    // computes point of intersection
    private Vertex3D intersect(Vertex3D p1, Vertex3D p2, int b)
    {

        Vertex3D v = new Vertex3D();

        float mX = 0, mY = 0, mW = 0;

        if (p1.z != p2.z)
        {
            mX = (p2.x - p1.x) / (p2.z - p1.z);
            mY = (p2.y - p1.y) / (p2.z - p1.z);
            mW = (p2.w - p1.w) / (p2.z - p1.z);
        }

        if (b == HITHER)
        {
            v.x = p1.x + (minZDist - p1.z) * mX;
            v.y = p1.y + (minZDist - p1.z) * mY;
            v.z = minZDist;
            v.w = p1.w + (minZDist - p1.z) * mW;
        }
        else
        {
            v.x = p1.x + (maxZDist - p1.z) * mX;
            v.y = p1.y + (maxZDist - p1.z) * mY;
            v.z = maxZDist;
            v.w = p1.w + (maxZDist - p1.z) * mW;
        }

        return v;
    }

    // Clips a point p, readjusting all the other vertices
    // differs from Hearna nd Baker in that it does not pass cnt, but instead
    // has clound as a global variable
    private void clipPoint(Vertex3D p, int b, Vertex3D[] pOut, Vertex3D[] first, Vertex3D[] s)
    {
        Vertex3D iPt;

        // saves the point if no point existed for this edge
        if (first[b] == null)
        {
            first[b] = p;
        }
        // previous point exists, if p and previous point cross edge, find
        // intersection.  Cip against next boundary.
        // If no more edges, add to output list
        else if (crossCheck(p, s[b], b))
        {
            iPt = intersect(p, s[b], b);

            if (b == HITHER)
            {
                clipPoint(iPt, YON, pOut, first, s);
            }
            else
            {
                pOut[cnt] = iPt;
                cnt++;
            }
        }

        s[b] = p;

        if (inside(p, b))
        {
            if (b == HITHER)
            {
                clipPoint(p, YON, pOut, first, s);
            }
            else
            {
                pOut[cnt] = p;
                cnt++;
            }
        }
    }
    
    private void closeClip(Vertex3D[] pOut, Vertex3D[] first, Vertex3D[] s)
    {
        Vertex3D i;
        int b;

        for (b = HITHER; ((b <= YON) && (first[b] != null)); b++)
        {
            if ( crossCheck(s[b], first[b], b) )
            {
                i = intersect(s[b], first[b], b);
                if (b == HITHER)
                {
                    clipPoint(i, YON, pOut, first, s);
                }
                else
                {
                    pOut[cnt] = i;
                    cnt++;
                }
            }
        }
    }
    

    // Clips the polygon and draws it to the raster
    public void ClipAndDraw(ZRaster raster, Matrix3D project)
    {
        Vertex3D[] first = new Vertex3D[2];  // N_Edge is 2
        Vertex3D[] s = new Vertex3D[2];
        Vertex3D[] myVert = new Vertex3D[4];  // vertices of quadrilateral

        // initializes cnt
        cnt = 0;

        for (int i = 0; i < 3; i++)
        {
            clipPoint(vlist[v[i]], HITHER, myVert, first, s);
        }
        closeClip(myVert, first, s);

        // Code to handle Triangle clipping
        if (cnt == 0)
        {
            return;
        }
        else if (cnt == 3)  // base case, no need to split quadrilateral
        {

            vert[0] = project.transform(myVert[0]);
            vert[1] = project.transform(myVert[1]);
            vert[2] = project.transform(myVert[2]);
            Draw(raster);

        }
        else  //  Must divide resulting quadrilateral into two triangle
        {

            // triangle for each half of quad to split
            Triangle tri1 = new Triangle();
            Triangle tri2 = new Triangle();
            
            tri1.vert = new Vertex3D[3];
            tri2.vert = new Vertex3D[3];
            
            tri1.vert[0] = project.transform(myVert[0]);
            tri1.vert[1] = project.transform(myVert[1]);
            tri1.vert[2] = project.transform(myVert[2]);
            tri2.vert[0] = project.transform(myVert[0]);
            tri2.vert[1] = project.transform(myVert[2]);
            tri2.vert[2] = project.transform(myVert[3]);            
            
            tri1.r = tri2.r = r;
            tri1.g = tri2.g = g;
            tri1.b = tri2.b = b;
            
            tri1.scale = -1;
            tri2.scale = -1;
            
            tri1.Draw(raster);
            tri2.Draw(raster);
        }

    }
    
    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;
        }
    }
}