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[];
    static int facenum = 1;

    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)
    {
        ///////////////////////////////////////////////////////////////////
        // Backface culls triangle, then illuminates them
        ///////////////////////////////////////////////////////////////////
        if (Pipeline.DEBUG) System.out.println("Enetered Illuminate"); //debug
        
        float num;
        float red_intensity   = 0;
        float green_intensity = 0;
        float blue_intensity  = 0;

        // Compute the normal for n
        //vlist[v[0]]
        Vertex3D p1 = vlist[v[0]];
        Vertex3D p2 = vlist[v[1]];
        Vertex3D p3 = vlist[v[2]];
        Vertex3D t1 = new Vertex3D();
        Vertex3D t2 = new Vertex3D();
        Vertex3D t3 = new Vertex3D();
        Vertex3D n  = new Vertex3D();
        if (Pipeline.DEBUG) System.out.println("FACE NUM: "+facenum); //debug
        facenum++;
        //if (Pipeline.DEBUG) System.out.println("Illuminate: Initialized p's, t's, and n"); //debug
        t1 = p2.sub(p1);
        //if (Pipeline.DEBUG) System.out.println("Illuminate: calcuated t1:\n"+t1); //debug
        t2 = p3.sub(p1);
        //if (Pipeline.DEBUG) System.out.println("Illuminate: calcuated t2:\n"+t2); //debug
        n  = t1.cross(t2);
        if (Pipeline.DEBUG) System.out.println("Illuminate: calcuated n:\n"+n); //debug

        ///////////////////////////////////////////////////////////////////
        // First, backface cull (if cull = true)
        ///////////////////////////////////////////////////////////////////
        if (cull) {
            if (Pipeline.DEBUG) System.out.println("Illuminate: Culling"); //debug
            // Test whether eye is in same direction as normal -> can't see -> cull
            // Compute num = eye * n
            // Add .1 to allow leniency for errors in precision when subtracting
            num = eye.dot(n) + .1f;
            if (num >= 0) {
                if (Pipeline.CULLDEBUG) System.out.println("culled n:\n"+n); //debug
                culled = false;
            } else {
                culled = true;
            }
        }
        ///////////////////////////////////////////////////////////////////
        // Second, illuminate all the lights
        ///////////////////////////////////////////////////////////////////
        if (Pipeline.ILLUMDEBUG) System.out.println("(ka,kd) = ("+
                                                    surface.ka + "," +
                                                    surface.kd + ")"); //debug
        for (int i = 0; i < lights; i++) { // Iterate over all the triangles
            Light currentLight = l[i];
            if (Pipeline.ILLUMDEBUG) System.out.println(i+": (R,G,B) = (" +
                                                             red_intensity + "," +
                                                             green_intensity + "," +
                                                             blue_intensity + ")"); //debug
            // Compute num = n * currentLight.getPosition()
            if (currentLight.lightType == Light.AMBIENT) {
                // I(color) = I(color) + ka * Il(color)
                red_intensity   += surface.ka*currentLight.ir;
                green_intensity += surface.ka*currentLight.ig;
                blue_intensity  += surface.ka*currentLight.ib;
            } else if (currentLight.lightType == Light.DIRECTIONAL) {
                // I(color) = I(color) + kd * Il(oclor) * (N * L)
                //if (Pipeline.ILLUMDEBUG) System.out.println("currentLight.getPosition():\n"+currentLight.getPosition()); //debug
                num = n.dot(currentLight.getPosition()); // (N * L)
                if (Pipeline.ILLUMDEBUG) System.out.println("num = "+num); //debug
                red_intensity   += surface.kd*currentLight.ir*num;
                green_intensity += surface.kd*currentLight.ig*num;
                blue_intensity  += surface.kd*currentLight.ib*num;
            } else { // POINT
                if (Pipeline.DEBUG) System.out.println("You haven't done point lighting yet..."); //debug
            }
        }
        if (Pipeline.ILLUMDEBUG) System.out.println((lights-1)+": (R,G,B) = (" +
                                                                  red_intensity + "," +
                                                                  green_intensity + "," +
                                                                  blue_intensity + ")"); //debug

        if (red_intensity > 1) red_intensity = 1;
        if (blue_intensity > 1) blue_intensity = 1;
        if (green_intensity > 1) green_intensity = 1;
        for (int i = 0; i < 3; i++) { // Set all vertexes of triangle to same color
            r[i] = surface.r * red_intensity;
            g[i] = surface.g * green_intensity;
            b[i] = surface.b * blue_intensity;
        }
        //r[2] = surface.r;
        //g[2] = surface.g;
        //b[2] = surface.b;

    }
    
    public void ClipAndDraw(ZRaster raster, Matrix3D project) {

        ///////////////////////////////////////////////////////////////////
        // C L I P P I N G
        ///////////////////////////////////////////////////////////////////
        // In canonical cube space:
        //    +-------+
        //   /       /|
        //  +-------+ |
        //  |       | +
        //  |       |/
        //  +-------+
        ///////////////////////////////////////////////////////////////////
        
        ///////////////////////////////////////////////////////////////////
        // First, perform trivial rejection
        // Since we're in canonical space, all this involves is
        // eliminating triangles where the z's of all the vertices are
        // either less than -1 (too close) or greater than 1 (too far)
        ///////////////////////////////////////////////////////////////////
        
        Vertex3D vertex0 = vlist[v[0]];
        Vertex3D vertex1 = vlist[v[1]];
        Vertex3D vertex2 = vlist[v[2]];
        
        vertex0.normalize();
        vertex1.normalize();
        vertex2.normalize();
        
        if ( (vertex0.z < -1) && (vertex1.z < -1) && (vertex2.z < -1) || // all points too close
             (vertex0.z >  1) && (vertex1.z >  1) && (vertex2.z >  1) ) {// all points too far
            if (Pipeline.CLIPDEBUG) {
                System.out.println("TRIVIALLY CLIPPED:"); //debug
                System.out.println("  vertex0:\n"+vertex0);
                System.out.println("  vertex1:\n"+vertex1);
                System.out.println("  vertex2:\n"+vertex2);
            }
            return; // Don't draw
        }

        
        ///////////////////////////////////////////////////////////////////
        // Now, need to determine whether any of the triangles cross the
        // canonical cube's near or far planes.  If so, they need to be
        // clipped.
        ///////////////////////////////////////////////////////////////////
        
        if ( (vlist[v[0]].z < -1) || (vlist[v[1]].z < -1) || (vlist[v[2]].z < -1) ||
             (vlist[v[0]].z >  1) || (vlist[v[1]].z >  1) || (vlist[v[2]].z >  1) ) {
            // Clip vertices against near plane
            clipNear(vertex0, vertex1, vertex2);
            clipFar(vertex0, vertex1, vertex2);
        }

        ///////////////////////////////////////////////////////////////////
        // D R A W I N G
        ///////////////////////////////////////////////////////////////////

        vert[0] = project.transform(vlist[v[0]]);
        vert[1] = project.transform(vlist[v[1]]);
        vert[2] = project.transform(vlist[v[2]]);
        
        //if (Pipeline.CLIPDEBUG) {
        //    System.out.println("AFTER: vert[0]:\n"+vert[0]);
        //    System.out.println("AFTER: vert[1]:\n"+vert[1]);
        //    System.out.println("AFTER: vert[2]:\n"+vert[2]);
        //}
        
        Draw(raster);
    }
    
    public void clipNear(Vertex3D vertex0, Vertex3D vertex1, Vertex3D vertex2) {
        // Clips vertices against the plane z=-1
        // Check vertex0 -> vertex1
        
        System.out.println("Clipping near..."); //debug
        
        Vertex3D[] vertices = new Vertex3D[3];
        vertices[0] = vertex0;
        vertices[1] = vertex1;
        vertices[2] = vertex2;
        int i, j;

        //for (i = 0; i < 3; i++) {
        //    System.out.println("BEFORE: vertices["+i+"] = \n"+vertices[i]); //debug
        //}

        // Insertion sort vertices from closest (0) to furthest (2)
        for (j = 2; j <= 3; j++)
        {
            Vertex3D key = vertices[j-1];
            for (i = j - 1; ( (i > 0) && (vertices[i-1].z > key.z) ); i--)
            {
                vertices[i+1-1] = vertices[i-1];
            }
            vertices[i+1-1] = key;
        }
        
        //for (i = 0; i < 3; i++) {
        //    System.out.println("AFTER: vertices["+i+"] = \n"+vertices[i]); //debug
        //}

        boolean needToSplit;
        
        if (vertices[0].z >= -1) {
            // Since vertices[0] is the closest,
            // if it is greater than z=-1, so are the others,
            // so no clipping to do on near plane
            //     -3
            //     -2
            // z = -1 ----------------
            //      0    _____
            //      1    \   /
            //      2     \ /
            //      3      +
            return;
        } else if (vertices[1].z > -1) {
            // vertices[0] out, vertices[1] & vertices[2] in
            //     -3      +
            //     -2     / \
            // z = -1 ----------------
            //      0   /____\
            //      1
            // We need to find the intersection with z=-1
            // and split the trapezoid up into 2 triangles
            needToSplit = true;
        } else { // vertices[1].z <= -1
            // vertices[0] & vertices[1] out, vertices[2] in
            //     -3    _____
            //     -2    \   /
            // z = -1 ----------------
            //      0     \/
            //      1
            // We need to find the intersection with z=-1
            needToSplit = false;
        }
        
        float intersectX, intersectY, intersectZ;
        
        if (!needToSplit) {
        System.out.println("!needToSplit"); //debug
            // Find the intersection with z=-1
            // across vertices[0] -> vertices[2] and set that as new vertices[0]
            vertices[0].x = vertices[0].x + (-1 - vertices[0].z)*(vertices[2].x - vertices[0].x)/(vertices[2].z - vertices[0].z);
            vertices[0].y = vertices[0].y + (-1 - vertices[0].z)*(vertices[2].y - vertices[0].y)/(vertices[2].y - vertices[0].z);
            vertices[0].z = -1;
        
            // Find the intersection with z=-1
            // across vertices[1] -> vertices[2] and set that as new vertices[1]
            vertices[1].x = vertices[1].x + (-1 - vertices[1].z)*(vertices[2].x - vertices[1].x)/(vertices[2].z - vertices[1].z);
            vertices[1].y = vertices[1].y + (-1 - vertices[1].z)*(vertices[2].y - vertices[1].y)/(vertices[2].y - vertices[1].z);
            vertices[1].z = -1;
        
            //Vertex3D vertex0 = vlist[v[0]];
            //Vertex3D vertex1 = vlist[v[1]];
            //Vertex3D vertex2 = vlist[v[2]];
        } else {
            // Ut-oh!
        }
        if ( (vlist[v[0]].z < -1) || (vlist[v[1]].z < -1) || (vlist[v[2]].z < -1) ){
            if (!needToSplit) {
                System.out.println("clipNear failed!"); //debug
            }
        }

    }       

    public void clipFar(Vertex3D vertex0, Vertex3D vertex1, Vertex3D vertex2) {
        // Clips vertices against the plane z=1
        // Check vertex0 -> vertex1
        
        System.out.println("Clipping far..."); //debug
        
        Vertex3D[] vertices = new Vertex3D[3];
        vertices[0] = vertex0;
        vertices[1] = vertex1;
        vertices[2] = vertex2;
        int i, j;

        // Insertion sort vertices from closest (0) to furthest (2)
        for (j = 2; j <= 3; j++)
        {
            Vertex3D key = vertices[j-1];
            for (i = j - 1; ( (i > 0) && (vertices[i-1].z > key.z) ); i--)
            {
                vertices[i+1-1] = vertices[i-1];
            }
            vertices[i+1-1] = key;
        }
        
        boolean needToSplit;
        
        if (vertices[2].z <= 1) {
            // Since vertices[2] is the farthest,
            // if it is less than z=1, so are the others,
            // so no clipping to do on far plane
            //      3
            //      2
            // z =  1 ----------------
            //      0    _____
            //     -1    \   /
            //     -2     \ /
            //     -3      +
            return;
        } else if (vertices[1].z < 1) {
            // vertices[2] out, vertices[0] & vertices[1] in
            //      3      +
            //      2     / \
            // z =  1 ----------------
            //      0   /____\
            //     -1
            // We need to find the intersection with z=1
            needToSplit = true;
        } else { // vertices[1].z >= -1
            // vertices[2] & vertices[1] out, vertices[0] in
            //      3    _____
            //      2    \   /
            // z =  1 ----------------
            //      0     \/
            //     -1
            // We need to find the intersection with z=1
            // and split the trapezoid up into 2 triangles
            needToSplit = false;
        }
        
        if (!needToSplit) {
            System.out.println("!needToSplit"); //debug
            // Find the intersection with z=1
            // across vertices[2] -> vertices[0] and set that as new vertices[2]
            vertices[2].x = vertices[2].x + (1 - vertices[2].z)*(vertices[0].x - vertices[2].x)/(vertices[0].z - vertices[2].z);
            vertices[2].y = vertices[2].y + (1 - vertices[2].z)*(vertices[0].y - vertices[2].y)/(vertices[0].y - vertices[2].z);
            vertices[2].z = -1;
        
            // Find the intersection with z=1
            // across vertices[1] -> vertices[0] and set that as new vertices[1]
            vertices[1].x = vertices[1].x + (-1 - vertices[1].z)*(vertices[0].x - vertices[1].x)/(vertices[0].z - vertices[1].z);
            vertices[1].y = vertices[1].y + (-1 - vertices[1].z)*(vertices[0].y - vertices[1].y)/(vertices[0].y - vertices[1].z);
            vertices[1].z = -1;
        
            //Vertex3D vertex0 = vlist[v[0]];
            //Vertex3D vertex1 = vlist[v[1]];
            //Vertex3D vertex2 = vlist[v[2]];
        } else {
            // Ut-oh!
        }
        if ( (vlist[v[0]].z > 1) || (vlist[v[1]].z > 1) || (vlist[v[2]].z > 1) ){
            if (!needToSplit) {
                System.out.println("clipFar failed!"); //debug
            }
        }

    }       

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