// Triangle.java -- Triangle rasterizer with illumination, z-buffering, etc.
//
// This is based on the class provided by Leonard (as opposed to my own
// Triangle.java from earlier projects.)

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 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);
  }
    
  public void Illuminate(Light l[], int lights, Point3D eye, boolean cull) {
    // For each color, total illumination is: (with Phong Lighting model)
    //   for each ambient light source:      i * ka 
    //   for each directional light source:  
    //                                  i * (kd*(N^ . L^) + ks*(V^ . R^)^ns)
    //   point lights are similar to directional, but requires the L vector
    //   to be recomputed.

    float c_x, c_y, c_z; // Centroid
    Point3D vec1, vec2;
    float n_x, n_y, n_z; // Surface normal
    float l_x = 0, l_y = 0, l_z = 0; // Light vector
    float r_x, r_y, r_z; // Reflectance vector
    float v_x, v_y, v_z; // Viewer vector
    double scale;

    // Flat shading, compute illumination at the centroid
    c_x = (vlist[v[0]].x + vlist[v[1]].x + vlist[v[2]].x) / 3;
    c_y = (vlist[v[0]].y + vlist[v[1]].y + vlist[v[2]].y) / 3;
    c_z = (vlist[v[0]].z + vlist[v[1]].z + vlist[v[2]].z) / 3;

    // Surface normal is (v1 - v0) x (v2 - v0)
    vec1 = new Point3D();
    vec1.x = vlist[v[1]].x - vlist[v[0]].x;
    vec1.y = vlist[v[1]].y - vlist[v[0]].y;
    vec1.z = vlist[v[1]].z - vlist[v[0]].z;

    vec2 = new Point3D();
    vec2.x = vlist[v[2]].x - vlist[v[0]].x;
    vec2.y = vlist[v[2]].y - vlist[v[0]].y;
    vec2.z = vlist[v[2]].z - vlist[v[0]].z;

    n_x = vec1.y*vec2.z - vec1.z*vec2.y;
    n_y = vec1.z*vec2.x - vec1.x*vec2.z;
    n_z = vec1.x*vec2.y - vec1.y*vec2.x;
    scale = Math.sqrt(n_x*n_x + n_y*n_y + n_z*n_z);
    n_x = (float)(n_x / scale);
    n_y = (float)(n_y / scale);
    n_z = (float)(n_z / scale);

    // Find unit viewer vector
    v_x = eye.x - c_x;
    v_y = eye.y - c_y;
    v_z = eye.z - c_z;
    scale = Math.sqrt(v_x*v_x + v_y*v_y + v_z*v_z);
    v_x = (float)(v_x / scale);
    v_y = (float)(v_y / scale);
    v_z = (float)(v_z / scale);

    // Backface culling
    if ((n_x*v_x + n_y*v_y + n_z*v_z) < 0) {
      culled = true;
      return;
    }
    culled = false;

    float i_r = 0;
    float i_g = 0;
    float i_b = 0;
    for (int i = 0; i < lights; i++) {

      // Determine light vector
      if (l[i].lightType == Light.DIRECTIONAL) {
	l_x = l[i].x;  l_y = l[i].y;  l_z = l[i].z;
      } else if (l[i].lightType == Light.POINT) {
	l_x = c_x - l[i].x;  l_y = c_y - l[i].y;  l_z = c_z - l[i].z;
      }

      if (l[i].lightType == Light.AMBIENT) {
	i_r += l[i].ir * surface.ka; 
	i_g += l[i].ig * surface.ka;
	i_b += l[i].ib * surface.ka;

      } else if ((l[i].lightType == Light.DIRECTIONAL) ||
		 (l[i].lightType == Light.POINT)) {
	// Find normalized light vector
	scale = Math.sqrt(l_x*l_x + l_y*l_y + l_z*l_z);
	l_x = -(float)(l_x / scale); 
	l_y = -(float)(l_y / scale);
	l_z = -(float)(l_z / scale);

	float n_dot_l = n_x*l_x + n_y*l_y + n_z*l_z;
	// Can this light really illuminate this surface?
	if (n_dot_l < 0) continue;

	i_r += l[i].ir * surface.kd * n_dot_l;
	i_g += l[i].ig * surface.kd * n_dot_l;
	i_b += l[i].ib * surface.kd * n_dot_l;

	// Find normalized reflectance vector
	r_x = 2*n_dot_l*n_x - l_x;
	r_y = 2*n_dot_l*n_y - l_y;
	r_z = 2*n_dot_l*n_z - l_z;

	float v_dot_r = v_x*r_x + v_y*r_y + v_z*r_z;
	// Can this specular reflection be seen?
	if (v_dot_r < 0) continue;

	i_r += l[i].ir * surface.ks * Math.pow(v_dot_r, surface.ns);
	i_g += l[i].ig * surface.ks * Math.pow(v_dot_r, surface.ns);
	i_b += l[i].ib * surface.ks * Math.pow(v_dot_r, surface.ns);
      }
    }

    for (int i = 0; i < 3; i++) {
      r[i] = i_r * surface.r;
      g[i] = i_g * surface.g;
      b[i] = i_b * surface.b;
    }
    
    // TODO
    // Gouraud shading, compute illumination at each vertex (need vertex
    // normals!)
  }
    

  static final float HITHER = -1;
  static final float YON = 1;

  public void ClipAndDraw(ZRaster raster, Matrix3D project) {
    // Hither and Yon clipping can generate up to 5 vertices (3 triangles).
    // Note this currently screws up vertex normals, but that only matters
    // for goraud shading, which we're not doing.
    Vertex3D newvert[] = new Vertex3D[5];
    Vertex3D newvert2[] = new Vertex3D[5];
    int numvert, numvert2;

    newvert[0] = new Vertex3D(vlist[v[0]]);
    newvert[1] = new Vertex3D(vlist[v[1]]);
    newvert[2] = new Vertex3D(vlist[v[2]]);
    numvert = 3;
    newvert[0].normalize();
    newvert[1].normalize();
    newvert[2].normalize();

 
    // Clip hither (-1)
    numvert2=0;
    for (int i=0; i<numvert; i++) {
      Vertex3D v1 = newvert[i];
      Vertex3D v2 = newvert[(i+1)%numvert];
      
      // From newvert[i] to newvert[(i+1)%numvert]
      if (v1.z < HITHER) { // out ->
	if (v2.z >= HITHER) { // -> in
	  // save V'1, V2
	  float xm = (v2.x - v1.x) / (v2.z - v1.z);
	  float ym = (v2.y - v1.y) / (v2.z - v1.z);
	  
	  newvert2[numvert2] = new Vertex3D(v1.x + (HITHER - v2.z)*xm,
					    v1.y + (HITHER - v2.z)*ym,
                                            HITHER);
	  numvert2++;
	  newvert2[numvert2] = new Vertex3D(v2);
	  numvert2++;
	}
      } else { // in ->
	if (v2.z < HITHER) { // -> out
	  // save V'1
	  float xm = (v2.x - v1.x) / (v2.z - v1.z);
	  float ym = (v2.y - v1.y) / (v2.z - v1.z);

	  newvert2[numvert2] = new Vertex3D(v1.x + (HITHER - v1.z)*xm,
					    v1.y + (HITHER - v1.z)*ym,
                                            HITHER);
	  numvert2++;
	} else { // -> in
	  // save V2
	  newvert2[numvert2] = new Vertex3D(v2);
	  numvert2++;
	}
      }
    }
    
    // Clip yon (1)
    numvert=0;
    for (int i=0; i<numvert2; i++) {
      Vertex3D v1 = newvert2[i];
      Vertex3D v2 = newvert2[(i+1)%numvert2];
      
      // From newvert2[i] to newvert2[(i+1)%numvert2]
      if (v1.z > YON) { // out ->
	if (v2.z <= YON) { // -> in
	  // save V'1, V2
	  float xm = (v2.x - v1.x) / (v2.z - v1.z);
	  float ym = (v2.y - v1.y) / (v2.z - v1.z);
	  
	  newvert[numvert] = new Vertex3D(v1.x + (YON - v1.z)*xm,
					  v1.y + (YON - v1.z)*ym,
                                          YON);
	  numvert++;
	  newvert[numvert] = new Vertex3D(v2);
	  numvert++;
	}
      } else { // in ->
	if (v2.z > YON) { // -> out
	  // save V'1
	  float xm = (v2.x - v1.x) / (v2.z - v1.z);
	  float ym = (v2.y - v1.y) / (v2.z - v1.z);

	  newvert[numvert] = new Vertex3D(v1.x + (YON - v1.z)*xm,
					  v1.y + (YON - v1.z)*ym,
                                          YON);
	  numvert++;
	} else { // -> in
	  // save V2
	  newvert[numvert] = new Vertex3D(v2);
	  numvert++;
	}
      }
    }

    // project maps from canonical to screen space
    for (int i=0; i<(numvert-2); i++) {
      // Draw triangles
      vert[0] = project.transform(newvert[0]);
      vert[1] = project.transform(newvert[i+1]);
      vert[2] = project.transform(newvert[i+2]);
      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;
    }
  }
}