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 get used alot. Allocate one time only and mutate to save memory/time
  private Point3D L = new Point3D(), V = new Point3D(), R = new Point3D();
  private Vertex3D fourVList[] = new Vertex3D[4], newList[], 
    fiveVList[] = new Vertex3D[5];

    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)
  {
    // Compute centroid for flat shading and for culling
    Point3D centroid = 
      new Point3D((vlist[v[0]].x + vlist[v[1]].x + vlist[v[2]].x)/3,
		  (vlist[v[0]].y + vlist[v[1]].y + vlist[v[2]].y)/3,
		  (vlist[v[0]].z + vlist[v[1]].z + vlist[v[2]].z)/3);
    
    // Compute surface normal
    Point3D e1 = new Point3D(vlist[v[1]].x - vlist[v[0]].x, 
			     vlist[v[1]].y - vlist[v[0]].y, 
			     vlist[v[1]].z - vlist[v[0]].z);
    Point3D e2 = new Point3D(vlist[v[2]].x - vlist[v[1]].x, 
			     vlist[v[2]].y - vlist[v[1]].y, 
			     vlist[v[2]].z - vlist[v[1]].z);
    Point3D normal = e1.cross(e2).unit();

    Point3D look = new Point3D(centroid.x - eye.x,
			       centroid.y - eye.y,
			       centroid.z - eye.z).unit();
    
    
    if (cull) {
      // Dot with vector from eye to triangle. Use centroid
      /*
      Point3D look = new Point3D(centroid.x - eye.x,
				 centroid.y - eye.y,
				 centroid.z - eye.z);
				 */
      
      culled = (look.x*normal.x + look.y*normal.y + look.z*normal.z > 0);
    }
    
    // Compute color
    if (!culled) {
      float rtotal[]=new float[3], gtotal[]=new float[3], btotal[]=new float[3], 
	rambient=0, gambient=0, bambient=0;

      for (int c = 0; c < lights; c++) {
	switch (l[c].lightType) {
	case Light.AMBIENT:
	  rambient = l[c].ir;
	  gambient = l[c].ig;
	  bambient = l[c].ib;
	  break;
	  
	case Light.DIRECTIONAL:
	  // Compute required vectors: 
	  L.x = l[c].x; L.y = l[c].y; L.z = l[c].z;
	  V.x = -look.x; V.y = -look.y; V.z = -look.z;

	  /* Per vertex! */
	  for (int i=0; i < 2; i++) {
	    /*
	    if (!vlist[v[i]].hasNormal) System.out.println("oops");
	    System.out.println("> " + vlist[v[i]].nx + " " + vlist[v[i]].ny +
			       " " + vlist[v[i]].nz);
			       */
	    normal = new Point3D(vlist[v[i]].nx,
				 vlist[v[i]].ny,
				 vlist[v[i]].nz);
	    normal.unit();
	    
	    float scale = 2*(normal.x*L.x + normal.y*L.y + normal.z*L.z);
	    R.x = scale*normal.x - L.x;
	    R.y = scale*normal.y - L.y;
	    R.z = scale*normal.z - L.z;
	    R.unit();
	    
	    scale = surface.kd * normal.dot(L) + 
	      surface.ks * (float)Math.pow(V.dot(R), surface.ns);
	  
	    rtotal[i] += l[c].ir * scale;
	    gtotal[i] += l[c].ig * scale;
	    btotal[i] += l[c].ib * scale;
	  }
	}
      }

      /* Gourad shading. All vertices get this color. */
      for (int i = 0; i < 3; i++) {
	r[i] = surface.r * (rtotal[i] + rambient);
	g[i] = surface.g * (btotal[i] + bambient);
	b[i] = surface.b * (gtotal[i] + gambient);
      }
    }
  }
    
    
  public void ClipAndDraw(ZRaster raster, Matrix3D project)
  {
    /*
    System.out.println("*Vertices: " + vlist[v[0]] + "/"+
		       vlist[v[1]]+"/"+vlist[v[2]]);
		       */

    int vertices = 0, vertices2 = 0;
    Vertex3D oldList[];

    /* Check z = -1 boundary */
    /* Check the three edges */
    newList = fourVList;
    vertices = check_edge(vlist[v[0]], vlist[v[1]], vertices, -1);
    vertices = check_edge(vlist[v[1]], vlist[v[2]], vertices, -1);
    vertices = check_edge(vlist[v[2]], vlist[v[0]], vertices, -1);

    /* Check the z=1 boundary. Up to 4 edges to examine. */
    oldList = newList;
    newList = fiveVList;
    for (int i=0; i < vertices; i++) 
      vertices2 = check_edge(oldList[i], oldList[(i+1) % vertices], 
			     vertices2, 1);

    /* Draw them triangles */
    if (vertices2 == 0) ; /* System.out.println("Punting triangle");  */
    else
    if (vertices2 < 3) System.out.println("Assertion Failed: Not poly.");
    for (int i=1; i < vertices2 - 1; i++) {
      /*
      System.out.println("    Draw: " + newList[i] + "/"+
			 newList[i+1]+"/"+newList[0]);
			 */
      vert[0] = project.transform(newList[i]);
      vert[1] = project.transform(newList[i+1]);
      vert[2] = project.transform(newList[0]);

      Draw(raster);
    }
  }

  private int check_edge(Vertex3D s, Vertex3D t, int count, int z)
  {
    if (z < 0 )
      if (s.z < z) {  /* start outside */
	if (t.z >= z) {  /* end up in */
	  /* Add intersection point and end point */
	  newList[count++] = intersect(t, s, z);
	  newList[count++] = t;
	}
	/* out -> out: add nothing. */
      } else {  /* start in. */
	if (t.z >= z)  /* Stay in */
	  /* Add end point */
	  newList[count++] = t;
	else  /* in -> out */
	  /* Add intersection point */
	  newList[count++] = intersect(s, t, z);
      }
    else
      if (s.z > z) {  /* start outside */
	if (t.z <= z) {  /* end up in */
	  /* Add intersection point and end point */
	  newList[count++] = intersect(t, s, z);
	  newList[count++] = t;
	}
	/* out -> out: add nothing. */
      } else {  /* start in. */
	if (t.z <= z)  /* Stay in */
	  /* Add end point */
	  newList[count++] = t;
	else  /* in -> out */
	  /* Add intersection point */
	  newList[count++] = intersect(s, t, z);
      }

    return count;
  }

  /* By convention, Q is the vertex OUTSIDE the area. */
  private Vertex3D intersect(Vertex3D P, Vertex3D Q, float z)
  {
    /*
      Derive parametric equations for line using point P and
      direction vector v = Q-P:

      x = P.x + v.x*t;    y = P.y + v.y*t;   z = P.z + v.z*t;

      z is known; use that to compute t, and thus x and y.
      [Taken from a book titled "Calculus" by Larson, Hostetler, Edwards]
      */
    /*    System.out.println("Vertex out of bounds: " + Q); */

    Point3D v = new Point3D(Q.x-P.x, Q.y-P.y, Q.z-P.z);
    float t = (z - P.z) / v.z;
    Vertex3D ret = new Vertex3D();
    ret.copy(Q);  /* To preserve normals */
    ret.x = P.x + v.x*t;
    ret.y = P.y + v.y*t;
    ret.z = z;
    return ret;
  }

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