import java.awt.Color;
import java.util.Vector;
import Vertex3D;
import Matrix3D;
import Point3D;
import Surface;
import ZRaster;

/** all code provided unless otherwise indicated **/

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

  Point3D normal;
  float D;
  Vector poly1;
  
  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;
      normal = new Point3D();

    }
  
  public void setSurface(Surface s)
    {
      surface = s;
    }
  
  public Surface getSurface()
    {
      return surface;
    }
  
  public boolean isVisible()
    {
      return (!culled);
    }

  /*
    ... added to calculate the normal to the triangular plane
  */
  public Point3D getNormal(Vertex3D[] vtxlist) {
    Point3D norm = new Point3D();

    //calculate A, B, C using formulas pg 308 in text
    norm.x = -(vtxlist[v[0]].y*(vtxlist[v[1]].z - vtxlist[v[2]].z) +
             vtxlist[v[1]].y*(vtxlist[v[2]].z - vtxlist[v[0]].z) +
             vtxlist[v[2]].y*(vtxlist[v[0]].z - vtxlist[v[1]].z));
    norm.y = -(vtxlist[v[0]].z*(vtxlist[v[1]].x - vtxlist[v[2]].x) +
             vtxlist[v[1]].z*(vtxlist[v[2]].x - vtxlist[v[0]].x) +
             vtxlist[v[2]].z*(vtxlist[v[0]].x - vtxlist[v[1]].x));
    norm.z = -(vtxlist[v[0]].x*(vtxlist[v[1]].y - vtxlist[v[2]].y) +
             vtxlist[v[1]].x*(vtxlist[v[2]].y - vtxlist[v[0]].y) +
             vtxlist[v[2]].x*(vtxlist[v[0]].y - vtxlist[v[1]].y));

    //get magnitude
    //float mag = magnitude(norm.x, norm.y, norm.z);
    //System.out.println("this is the magnitude" + mag);

    //normalize
    //norm.x = norm.x/mag;
    //norm.y = norm.y/mag;
    //norm.z = norm.z/mag;  <--in an effort to debug this ended up in Illuminate instead
    
    //return
    return norm;

  }
  
  
  /*
    ... modified
  */
  public void Illuminate(Light l[], int lights, Point3D eye, boolean cull)
    {
      //local declarations
      Point3D L;
      float NdotL;
      float kdNL;
      Point3D VminEye;

      //find the normal if not already done by the constructor that takes 3 v's
      normal = getNormal(vlist);

      //if wants culling, then dot normal with eye to determine culling or no culling
      if (cull) {
	VminEye = new Point3D(vlist[v[0]].x - eye.x, vlist[v[0]].y - eye.y, vlist[v[0]].z - eye.z);
	if (dot(normal, VminEye) < 0) {
	  culled = true;
	  return;
	}
	else {
	  culled = false;
	}
      }

      //normalize the normal to the triangle.
      float mag = magnitude(normal.x, normal.y, normal.z);
      normal.x = normal.x/mag;
      normal.y = normal.y/mag;
      normal.z = normal.z/mag;

      //illuminate - the following executes the equation on slide 20, Lecture 18

      //loop three times, this would normally be one per vertex, but in
      //our case we aren't doing that yet. Use this outer loop when doing Gouraud.
      for (int i = 0; i < 3; i++) {
     
	//initialize the rgb vals
	r[i] = 0;
	g[i] = 0;
	b[i] = 0;
	
	for (int j = 0; j < lights; j++) {
	  if (l[j].lightType == Light.AMBIENT){ // Ambient light: ka*Iambient
	    r[i] += l[j].ir*surface.ka;
	    g[i] += l[j].ig*surface.ka;
	    b[i] += l[j].ib*surface.ka;
	  }
	  if (l[j].lightType == Light.DIRECTIONAL) { // Directional light: Ii*kd(NdotL)
	    //System.out.println("hey we are at directional");
	    L = new Point3D(l[j].x, l[j].y, l[j].z);
	    NdotL = dot(normal, L);
	    kdNL = surface.kd * NdotL;
	    if(kdNL < 0) //some problem with negative light? I'm confused, but this fixes it.
	      kdNL = -kdNL;
	    else kdNL = kdNL;
	    //if (kdNL > 0) {
	      r[i] += l[j].ir * kdNL;
	      g[i] += l[j].ig * kdNL;
	      b[i] += l[j].ib * kdNL;
	      //}
	  }
	  if (surface.ks > 0) { //specular part: ks(VdotR)^nshiny
	    //not implemented yet, not mandatory for this pset 4
	  }
	  if (l[j].lightType == Light.POINT) { // Point light (not implemented for this pset)
	    System.out.println("Point lighting not implemented in pset 4");
	  }
	}//end loop through lights l[]

	r[i] *= surface.r;
	g[i] *= surface.g;
	b[i] *= surface.b;

	//System.out.println(r[i] + " " + g[i] + " " + b[i]);
      }//end loop per vertex...
    }

  /*
    ... modified
  */
  public void ClipAndDraw(ZRaster raster, Matrix3D project) {
    //calculate D
    //D = -vlist[v[0]].x*(vlist[v[1]].y*vlist[v[2]].z - vlist[v[2]].y*vlist[v[1]].z) - 
    //  vlist[v[1]].x*(vlist[v[2]].y*vlist[v[0]].z - vlist[v[0]].y*vlist[v[2]].z) - 
    // vlist[v[2]].x*(vlist[v[0]].y*vlist[v[1]].z - vlist[v[1]].y*vlist[v[0]].z);

    
    //trivial accept or reject ?
    if ((AxByCzD(vlist[v[0]],1) && AxByCzD(vlist[v[1]],1) && AxByCzD(vlist[v[2]],1))
      || (!AxByCzD(vlist[v[0]],-1) && !AxByCzD(vlist[v[1]],-1) && !AxByCzD(vlist[v[2]],-1))) {
      //trivial reject
      return;
    }
    else if ((!AxByCzD(vlist[v[0]],1) && !AxByCzD(vlist[v[1]],1) && !AxByCzD(vlist[v[2]],1))&&
	     (AxByCzD(vlist[v[0]],-1) && AxByCzD(vlist[v[1]],-1) && AxByCzD(vlist[v[2]],-1))){
      //trivial accept - no clipping necessary
      vert[0] = project.transform(vlist[v[0]]);
      vert[1] = project.transform(vlist[v[1]]);
      vert[2] = project.transform(vlist[v[2]]);
      Draw(raster);
    }
    //implement Sutherland-Hodgeman clipping for the near and far planes
    else {
      
      //create a vector to hold the vertices of the polygon clipped against plane z=1
      poly1 = new Vector();
      
      //first, clip against the far z plane, z = 1
      clipTriangle(1, vlist[v[0]], vlist[v[1]], vlist[v[2]], poly1);
      //System.out.println("Triangle clipped to a polygon with " + poly1.size() + " sides against z = 1");
 
      //break resulting polygon into two triangles or just keep the resulting triangle
      //clip and draw either the new triangle or the two resulting ones against plane z = -1
      

      //then break up this vlist into triangles to draw.

      vert[0] = project.transform(vlist[v[0]]);
      vert[1] = project.transform(vlist[v[1]]);
      vert[2] = project.transform(vlist[v[2]]);
      Draw(raster);
    }
  }

  //fills in the Vector vtxlist with the vertices of a clipped triangle resulting from
  //v1 v2 and v3 and against plan z
  private void clipTriangle(int z, Vertex3D v1, Vertex3D v2, Vertex3D v3, Vector vtxlist) {
    clipEdge(z, v1, v2, vtxlist);
    clipEdge(z, v2, v3, vtxlist);
    clipEdge(z, v3, v1, vtxlist);

    //check to make sure vtxlist has at least 3 values
    if (vtxlist.size() < 3) System.out.println("whoah, somehow the triangle clipped to a line. V. Bad.");

    //then reset all v.added values to false
    for (int i = 0; i < vtxlist.size(); i++) {
      Vertex3D tmpv = (Vertex3D)vtxlist.elementAt(i);
      tmpv.added = false;
      vtxlist.setElementAt(tmpv, i);
    }

    //sort vtxlist so that it's easy to break up into separate triangles...
    
  }

  //checks two vertices against the plane specified by z
  //and adds them or the intersection to the Vector if needed
  private void clipEdge(int z, Vertex3D v1, Vertex3D v2, Vector vtxlist) {
      //temporary Vertex3D to hold new vertices
      Vertex3D newv = new Vertex3D();

    if (AxByCzD(v1,z) && AxByCzD(v2,z)) {} //both lie outside plane
      else if (!AxByCzD(v1,z) && !AxByCzD(v2,z)) { //both lie inside plane
	addVertex(vtxlist, v1);
	addVertex(vtxlist, v2);
      }
      else { //one inside, one outside. need to find intersecting point with plane and add that.
	newv = intersect(v1, v2, z);
	addVertex(vtxlist, newv);
	if (AxByCzD(v1,z)) {
	  addVertex(vtxlist, v2);
	}
	else {
	  addVertex(vtxlist, v1);
	}
      }
  }
  
  //checks to see if a vertex is already added to the poly list,
  //and if it is, adds it.
  private void addVertex(Vector vtxlist, Vertex3D v) {
    if (!v.added) {
      vtxlist.addElement(v);
      v.added = true;
    }
  }

  /*
    interpolates intersection of line with plane without handling colour
  public static Vertex3D intersect(Vertex3D v1, Vertex3D v2, int z)  {
    float newx, newy;
    float dx, dy, deltaz;
    deltaz = v2.z - v1.z;
    dx = (v2.x - v1.x) / deltaz;
    dy = (v2.y - v1.y) /deltaz;
    newx = v1.x + (z - v1.z)*dx;
    newy = v1.y + (z - v1.z)*dy;
    Vertex3D out = new Vertex3D(newx, newy, z);
    return out;
  }
  */

  /*
    ...added to calculate the point at which a line intersects the z-plane
    ...interpolates the color at that point as well.
  */
 public static Vertex3D intersect(Vertex3D v1, Vertex3D v2, int z)
  {
    float newx, newy;
    float dx, dy, dr, db, dg, deltaz, newr, newb, newg;
    deltaz = v2.z - v1.z;
    dx = (v2.x - v1.x) / deltaz;
    dy = (v2.y - v1.y) /deltaz;
    dr = (v2.r - v1.r) /deltaz;
    dg = (v2.g - v1.g) /deltaz;
    db = (v2.b - v1.b) /deltaz;
    
    newx = v1.x + (z - v1.z)*dx;
    newy = v1.y + (z - v1.z)*dy;
    newr = v1.r + (z - v1.z)*dr;
    newg = v1.g + (z - v1.z)*dg;
    newb = v1.b + (z - v1.z)*db;
    Vertex3D out = new Vertex3D(newx, newy, z);
    out.r = newr;
    out.b = newb;
    out.g = newg;
    
    return out;
  }
  
  public boolean AxByCzD(Vertex3D vtx, float z) {
    float num;
    num = z*vtx.z + 1;
    return (num > 0);
  }
  
  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;
      }
    }

  /*
    added - general utility functions
  */
  public float magnitude(float fx, float fy, float fz) {
    float sum;
    sum = fx*fx + fy*fy + fz*fz;
    return (float)java.lang.Math.sqrt(sum);
  }

  public float dot(Point3D px, Point3D py) {
    return (px.x*py.x + px.y*py.y + px.z*py.z);
  }

}