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 PlaneEqn plane;
  
  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;
    plane = new PlaneEqn(vert[0], vert[1], vert[2]);
  }
  
  public void setSurface(Surface s)
  {
    surface = s;
  }

  public Surface getSurface()
  {
    return surface;
  }

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

  public void setCulled(Point3D eye) {
    plane = new PlaneEqn(vlist[v[0]], vlist[v[1]], vlist[v[2]]);
    if (plane.eval(eye) <= 0) 
      culled = true;
    else culled = false;
  }
    
  /*
    ... you'll need to modify the following two methods ...
    */
  public void Illuminate(Light l[], int lights, Point3D eye, boolean cull)
  {
    for (int j = 0; j < 3; j++) {
      r[j] = 0;
      g[j] = 0;
      b[j] = 0;
      Normal n = new Normal(vlist[v[0]], vlist[v[1]], vlist[v[2]]);
      for (int i = 0; i < lights; i++) {
	float dp = dotProd(n.x, n.y, n.z, l[i].x, l[i].y, l[i].z);
	if (l[i].lightType == Light.AMBIENT) {
	  r[j] = r[j] + surface.ka * surface.r * l[i].ir;
	  g[j] = g[j] + surface.ka * surface.g * l[i].ig;
	  b[j] = b[j] + surface.ka * surface.b * l[i].ib;
	}
      	else if ((l[i].lightType == Light.DIRECTIONAL) && (dp < 0)) {  
	  r[j] = r[j] - (surface.kd * surface.r * l[i].ir * dp);
	  g[j] = g[j] - (surface.kd * surface.g * l[i].ig * dp);
	  b[j] = b[j] - (surface.kd * surface.b * l[i].ib * dp);
	}
      }
      if (r[j] > 1)
	r[j] = 1;
      if (g[j] > 1)
	g[j] = 1;
      if (b[j] > 1)
	b[j] = 1;
    }
  }

  public float dotProd(float nx, float ny, float nz,
		       float lx, float ly, float lz) {
    return (nx * lx + ny * ly + nz * lz);
  }

  public void ClipAndDraw(ZRaster raster, Matrix3D project)
  {
   
    // original
    /*
    vert[0] = project.transform(vlist[v[0]]);
    vert[1] = project.transform(vlist[v[1]]);
    vert[2] = project.transform(vlist[v[2]]);
    Draw(raster);
    */
    
    int nVertices = 3;
    Vertex3D fin[] = new Vertex3D[5];
    int ptsgot = 0;
    Vertex3D holder = new Vertex3D();
    Vertex3D vl[] = new Vertex3D[5];
    vl[0] = vlist[v[0]];
    vl[1] = vlist[v[1]];
    vl[2] = vlist[v[2]];

    for (int pln = 0; pln < 2; pln++) {
      if (pln > 1) {
	for (int j = 0; j < 5; j++) {
	  vl[j] = fin[j];
	}
      }
      for (int i = 0; i < nVertices; i++) {
	if (withinPlane(pln, vl[i])) {
	  //	  System.out.println("first in");
	  if (withinPlane(pln, vl[(i + 1) % nVertices])) {
	    // both in, add second
	    //System.out.println("second in");
	    fin[ptsgot] = vl[(i + 1) % nVertices];
	    ptsgot++;
	  }
	  else {
	    // first in, second out
	    //System.out.println("second out");
	    fin[ptsgot] = boundarypt(pln, vl[i], vl[(i + 1) % nVertices]);
	    ptsgot++;
	  }
	}
	else {
	  //System.out.println("first out");
	  if (withinPlane(pln, vl[(i + 1) % nVertices])) {
	    // first out, second in
	    //System.out.println("second in");
	    fin[ptsgot] = boundarypt(pln, vl[i], vl[(i + 1) % nVertices]);
	    ptsgot++;
	    fin[ptsgot] = vl[(i + 1) % nVertices];
	    ptsgot++;
	  }
	  // both out, do nothing
	  //System.out.println("second out");
	}
      }
      nVertices = ptsgot;
      ptsgot = 0;
    }
    if (nVertices < 3)
      return; // all outside plane
    vert[0] = project.transform(fin[0]);
    for (int i = 1; i < nVertices - 1; i++) {
      vert[1] = project.transform(fin[i]);
      vert[2] = project.transform(fin[i + 1]);
      Draw(raster);
    }
    
  }

  public boolean withinPlane(int pln, Vertex3D p) {
    boolean within;
    if (pln == 0) 
      within = (p.z >= -1);
    else within = (p.z <= 1);
    return within;
  }

  public Vertex3D boundarypt(int pln, Vertex3D v1, Vertex3D v2) {
    float dydz = (v2.y - v1.y) / (v2.z - v1.z);
    float dxdz = (v2.x - v1.x) / (v2.z - v1.z);
    Vertex3D onboundary = new Vertex3D();
    if (pln == 0) 
      onboundary = new Vertex3D(v1.x + (-1 - v1.z) * dxdz,
				v1.y + (-1 - v1.z) * dydz,
				-1);
    else onboundary = new Vertex3D(v1.x + (1 - v1.z) * dxdz,
				   v1.y + (1 - v1.z) * dydz,
				   1);
    return onboundary;
  }

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