import Drawable;
import Vertex3D;
import Raster;
import Matrix3D;
import Point3D;

class Triangle implements Drawable 
{
  protected static final int ASHIFT = 24;
  protected static final int RSHIFT = 16;
  protected static final int GSHIFT = 8;
  protected static Vertex3D vList[];

  protected Vertex3D[] vert;

  // Holds the indices of the vertices
  protected int v[];
  
  // tells whether the last culling / illumination indicated that this
  // triangle was or wasn't visible.
  public boolean visible, shading;
  
  // Current surface
  private Surface surf;
  
  // Plane equation coefficients, depth interpolation coefficients
  float z[], norm[];

  float A, B, C, D;

  private boolean bLeft;
  private float Slope10, Slope20, Slope21;
  private int iColor, iColor1, iColor2, iColor0;
  
  //private float r[], g[], a[], b[];
  
  public Triangle(int v0, int v1, int v2) 
  {
    
    // Declarations
    v = new int[3];
    int iColor;

    v[0] = v0;
    v[1] = v1;
    v[2] = v2;

    // Initializations
    visible = true;
    surf = null;

    // REMOVE THIS ONCE ILLUMINATION WORKS
    shading = true;

    // Initializations
    z = new float[4];
    norm = new float[4];

    // NOTE: these calls are only used when Gouraud shading is used
    //r = new float[4];
    //a = new float[4];
    //g = new float[4];
    //b = new float[4];
  }
  
  public static void setVertexList(Vertex3D vL[])
  {
    vList = vL;
  }

  public void setSurface(Surface s)
  {
    surf = s;
  }
  
  public void initNormal()
  {
    // Declarations
    float x1, x2, x3, y1, y2, y3, z1, z2, z3;

    // Get our vertex parameters
    x1 = vList[v[0]].x;
    y1 = vList[v[0]].y;
    z1 = vList[v[0]].z;
    x2 = vList[v[1]].x;
    y2 = vList[v[1]].y;
    z2 = vList[v[1]].z;
    x3 = vList[v[2]].x;
    y3 = vList[v[2]].y;
    z3 = vList[v[2]].z;

    // Obtain the plane equation for this triangle: will have to deal with 
    // transformation later.
    norm[0] = -(y1*(z2-z3) + y2*(z3-z1) + y3*(z1-z2));
    norm[1] = -(z1*(x2-x3) + z2*(x3-x1) + z3*(x1-x2));
    norm[2] = -(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
    norm[3] = -x1*(y2*z3-y3*z2) - x2*(y3*z1-y1*z3) - x3*(y1*z2-y2*z1);
  }
  
  public void updateNormal(Matrix3D m)
  {

    
  }
    
  public void Illuminate(Light l[], int lights, Point3D eye, boolean cull,
			 Matrix3D m)
  {
    // Declarations
    float in[], out[];
    float cx, cy, cz;
    float r, b, g, mag;
    int i;

    in = new float[4];
    out = new float[4];
    
    for(i=0;i<4;i++)
      in[i] = norm[i];

    m.transformNormal(in, out);

    // BACK CULLING OCCURS HERE
    //perform the back culling
    if(0 > (out[0]*(vList[v[0]].x-eye.x) + 
	    out[1]*(vList[v[0]].y-eye.y) + 
	    out[2]*(vList[v[0]].z-eye.z)))
    {
      visible = false;
      return;
    }else visible = true;

    // Normalize the normal vector
    mag = (float)Math.sqrt(out[0]*out[0] + out[1]*out[1] + out[2]*out[2]);
    out[0] = out[0] / mag;
    out[1] = out[1] / mag;
    out[2] = out[2] / mag;
    
    // REAL ILLUMINATION CALLS: CURRENTLY IN FLAT SHADING MODE
    float x1, x2, x3, y1, y2, y3, z1, z2, z3;
    
    // Get our vertex parameters
    x1 = vList[v[0]].x;
    y1 = vList[v[0]].y;
    z1 = vList[v[0]].z;
    x2 = vList[v[1]].x;
    y2 = vList[v[1]].y;
    z2 = vList[v[1]].z;
    x3 = vList[v[2]].x;
    y3 = vList[v[2]].y;
    z3 = vList[v[2]].z;
    
    // Calculate the centroid 
    cx = (x1 + x2 + x3) / 3;
    cy = (y1 + y2 + y3) / 3;
    cz = (z1 + z2 + z3) / 3;
    
    // Initialize the lights
    r = 0;
    b = 0;
    g = 0;
    
    // Perform the illumination
    for(i=0;i<lights;i++)
      {
	if(l[i].lightType == Light.AMBIENT)
	  {
	    r += surf.ka * l[i].ir;
	    g += surf.ka * l[i].ig;
	    b += surf.ka * l[i].ib;
	  }	
	else if(l[i].lightType == Light.DIRECTIONAL)
	  if((mag = l[i].x * out[0] + l[i].y * out[1] + l[i].z * out[2]) > 0)
	    {
	      r += surf.kd * l[i].ir * mag;
	      g += surf.kd * l[i].ig * mag;
	      b += surf.kd * l[i].ib * mag;
	    }	
	  else if(l[i].lightType == Light.POINT)
	    {
	    }
      }

    if(r>1) r = 1;
    if(b>1) b = 1;
    if(g>1) g = 1;
    
    r = r * surf.r;
    g = g * surf.g;
    b = b * surf.b;
    
    iColor = (0xff000000 | (int)(r*255) << RSHIFT |
	      (int)(g*255) << GSHIFT | (int)(b*255));
    iColor0 = iColor;
    iColor2 = iColor;
    iColor1 = iColor;
  }
  
  private void triangleSetup()
  {
    // Declarations
    Vertex3D tmp[] = new Vertex3D[3];
    float c0, c1, c2;
    float calc[][];
    
    // Figure out the matrix
    calc = new float[2][3];
    
    calc[0][0] = vert[1].x - vert[0].x;
    calc[0][1] = vert[1].y - vert[0].y;
    calc[1][0] = vert[2].x - vert[0].x;
    calc[1][1] = vert[2].y - vert[0].y;
    
    // Need to do the color computations
    // Perform the color calculation: this only happens
    // when you've got to Gouraud shade
    if(shading)
      {
	// Do the red
	/*
	  c0 = (iColor0 >> RSHIFT) & 0xff;
	  c1 = (iColor1 >> RSHIFT) & 0xff;
	  c2 = (iColor2 >> RSHIFT) & 0xff;
	  calc[0][2] = c1 - c0;
	  calc[1][2] = c2 - c0;
	  r[0] = (calc[0][1] * calc[1][2]) - (calc[0][2] * calc[1][1]);
	  r[1] = (calc[0][2] * calc[1][0]) - (calc[0][0] * calc[1][2]);
	  r[2] = (calc[0][0] * calc[1][1]) - (calc[0][1] * calc[1][0]);
	  r[3] = (r[0] * vert[0].x) + (r[1] * vert[0].y) + (r[2] * c0);
	  
	  // Do the alpha
	  c0 = iColor0 >>> ASHIFT;
	  c1 = iColor1 >>> ASHIFT;
	  c2 = iColor2 >>> ASHIFT;
	  calc[0][2] = c1 - c0;
	  calc[1][2] = c2 - c0;
	  a[0] = (calc[0][1] * calc[1][2]) - (calc[0][2] * calc[1][1]);
	  a[1] = (calc[0][2] * calc[1][0]) - (calc[0][0] * calc[1][2]);
	  a[2] = (calc[0][0] * calc[1][1]) - (calc[0][1] * calc[1][0]);
	  a[3] = (a[0] * vert[0].x) + (a[1] * vert[0].y) + (a[2] * c0);
	  
	  // Do the green
	  c0 = (iColor0 >> GSHIFT) & 0xff;
	  c1 = (iColor1 >> GSHIFT) & 0xff;
	  c2 = (iColor2 >> GSHIFT) & 0xff;
	  calc[0][2] = c1 - c0;
	  calc[1][2] = c2 - c0;
	  g[0] = (calc[0][1] * calc[1][2]) - (calc[0][2] * calc[1][1]);
	  g[1] = (calc[0][2] * calc[1][0]) - (calc[0][0] * calc[1][2]);
	  g[2] = (calc[0][0] * calc[1][1]) - (calc[0][1] * calc[1][0]);
	  g[3] = (g[0] * vert[0].x) + (g[1] * vert[0].y) + (g[2] * c0);
	  
	  // Do the blue
	  c0 = iColor0 & 0xff;
	  c1 = iColor1 & 0xff;
	  c2 = iColor2 & 0xff;
	  calc[0][2] = c1 - c0;
	  calc[1][2] = c2 - c0;
	  b[0] = (calc[0][1] * calc[1][2]) - (calc[0][2] * calc[1][1]);
	  b[1] = (calc[0][2] * calc[1][0]) - (calc[0][0] * calc[1][2]);
	  b[2] = (calc[0][0] * calc[1][1]) - (calc[0][1] * calc[1][0]);
	  b[3] = (b[0] * vert[0].x) + (b[1] * vert[0].y) + (b[2] * c0);	
	  */
      }
    
    // Do the depth interpolation
    c0 = vert[0].z;
    c1 = vert[1].z;
    c2 = vert[2].z;
    calc[0][2] = c1 - c0;
    calc[1][2] = c2 - c0;
    z[0] = (calc[0][1] * calc[1][2]) - (calc[0][2] * calc[1][1]);
    z[1] = (calc[0][2] * calc[1][0]) - (calc[0][0] * calc[1][2]);
    z[2] = (calc[0][0] * calc[1][1]) - (calc[0][1] * calc[1][0]);
    z[3] = (z[0] * vert[0].x) + (z[1] * vert[0].y) + (z[2] * c0);	
  
    // Sort the vertices in y
    if(vert[0].y <= vert[1].y && vert[0].y <= vert[2].y)
      {
	tmp[0] = vert[0];
	if(vert[1].y <= vert[2].y)
	  {
	    tmp[1] = vert[1];
	    tmp[2] = vert[2];
	  }
	else
	  { 
	    tmp[1] = vert[2];
	    tmp[2] = vert[1];
	  }
      }
    else if(vert[1].y <= vert[0].y && vert[1].y <= vert[2].y)
      {
	tmp[0] = vert[1];	
	if(vert[0].y <= vert[2].y)
	  {
	    tmp[1] = vert[0];
	    tmp[2] = vert[2];
	  }
	else
	  { 
	    tmp[1] = vert[2];
	    tmp[2] = vert[0];
	  }
      }
    else
      {
	tmp[0] = vert[2];
	if(vert[0].y <= vert[1].y)
	  {
	    tmp[1] = vert[0];
	    tmp[2] = vert[1];
	  }
	else
	  { 
	    tmp[1] = vert[1];
	    tmp[2] = vert[0];
	  }
      }

    // Reassign the Vertices
    vert[0] = tmp[0];
    vert[1] = tmp[1];
    vert[2] = tmp[2];

    // Determine the line slopes
    Slope10 = (vert[1].x - vert[0].x) / (vert[1].y - vert[0].y); 
    Slope20 = (vert[2].x - vert[0].x) / (vert[2].y - vert[0].y); 
    Slope21 = (vert[2].x - vert[1].x) / (vert[2].y - vert[1].y); 

    // Determine whether we're playing with a left-sided or a right-sided
    // triangle: this will be used to determine which edge equation is used
    // for the scan start and finish.
    
    if(vert[1].x <= vert[0].x && vert[1].x <= vert[2].x)
      bLeft = true;
    else if(vert[1].x <= vert[0].x && vert[1].x >= vert[2].x)
      if(Slope10 < Slope20)
	bLeft = true;
      else bLeft = false;
    else if(vert[1].x >= vert[0].x && vert[1].x <= vert[2].x)
      if(Slope10 > Slope20)
	bLeft = false;
      else bLeft = true;
    else 
      bLeft = false;
  }
  
  private static int ClipAgainstPlane(Vertex3D pts[], int points, Vertex3D out[], 
				      int cA, int cB, int cC, int cD)
  {
    // Declarations
    int i, count = 0;
    boolean special = false;
    Vertex3D one, two;
    float iOne, iTwo;
    
    // Check if it trivially clips in or out
    for(i=0;i<points;i++)
      {
	if((pts[i].x * cA + pts[i].y * cB + pts[i].z * cC + cD) > 0)
	  count += 1;
      }

    // Trivial accept
    if(count == points)
      {
	for(i=0;i<points;i++)
	  {
	    out[i].x = pts[i].x;
	    out[i].y = pts[i].y;
	    out[i].z = pts[i].z;
	  }

	return count;
      }
    // Trivial reject
    else if(count == 0)
      return 0;

    //for(i=0;i<points;i++)
    //  System.err.println(":"+i+":"+pts[i]);

    count = 0;

    // Thus it doesn't trivially clip. Since there are only 2 sides we are 
    // clipping against, it can only generate at most 4 points.
    for(i=0;i<points;i++)
      {
	// Get the current point pair.
	//System.out.println("Here: i = "+i+";count = "+count);
	one = pts[i];
	two = pts[(i+1)%points];
		
	// Get the point side values
	iOne = one.x * cA + one.y * cB + one.z * cC + cD;
	iTwo = two.x * cA + two.y * cB + two.z * cC + cD;
	
	//System.out.println("iOne = " + iOne + "; one: " + one);
	//System.out.println("iTwo = " + iTwo + "; two: " + two);

	// out->in
	if(iOne < 0 && iTwo > 0)
	  {
	    float fact = iOne / (iOne - iTwo);
	    	    
	    if(out[count == 0 ? count : count--].x == one.x + fact*(two.x-one.x) &&
	       out[count == 0 ? count : count--].y == one.y + fact*(two.y-one.y) &&
	       out[count == 0 ? count : count--].z == one.z + fact*(two.z-one.z))
	      {
		out[count].x = two.x;
		out[count].y = two.y;
		out[count].z = two.z;
		count++;
	      }
	    else{
	      out[count].x = one.x + fact*(two.x-one.x); 
	      out[count].y = one.y + fact*(two.y-one.y); 
	      out[count].z = one.z + fact*(two.z-one.z); 
	      //System.out.println("Count: " + count + "; out[count] = " + out[count]);
	      count++;
	      out[count].x = two.x;
	      out[count].y = two.y;
	      out[count].z = two.z;
	      //System.out.println("Count: " + count + "; out[count] = " + out[count]);
	      count++;
	    }
	  }  // in -> in
	else if(iOne > 0 && iTwo > 0)
	  {
	    if(out[count == 0 ? count : count--].x == one.x &&
	       out[count == 0 ? count : count--].y == one.y &&
	       out[count == 0 ? count : count--].z == one.z)
	      {
		out[count].x = two.x;
		out[count].y = two.y;
		out[count].z = two.z;
		count++;
	      }
	    else
	      {
		out[count].x = one.x;
		out[count].y = one.y;
		out[count].z = one.z;
		count++;
		out[count].x = two.x;
		out[count].y = two.y;
		out[count].z = two.z;
		count++;
	      }
	  }  // in -> out
	else if(iOne > 0 && iTwo < 0)
	  {
	    float fact = iOne / (iOne - iTwo);

	    if(out[count == 0 ? count : count--].x == one.x &&
	       out[count == 0 ? count : count--].y == one.y &&
	       out[count == 0 ? count : count--].z == one.z)
	      {
		out[count].x = one.x + fact*(two.x-one.x);
		out[count].y = one.y + fact*(two.y-one.y);
		out[count].z = one.z + fact*(two.z-one.z);
		count++;
	      }
	    else
	      {
		out[count].x = one.x;
		out[count].y = one.y;
		out[count].z = one.z;
		count++;
		out[count].x = one.x + fact*(two.x-one.x);
		out[count].y = one.y + fact*(two.y-one.y);
		out[count].z = one.z + fact*(two.z-one.z);
		count++;
	      }
	  }  // out -> out
	else
	  {
	  }
      }

    //for(i=0;i<count;i++)
    //  System.err.println(":"+i+":"+out[i]);

    return count;
  }

  public void ClipAndDraw(Raster raster, Matrix3D project)
  {
    int pts = 0, i;
    vert = new Vertex3D[3];
    
    for(pts = 0;pts < 3;pts++)
      vert[pts] = new Vertex3D(vList[v[pts]]);

    //for(i=0;i<3;i++)
    //  System.err.println(i+":"+vert[i]);
  
    
    // THIS IS HARDWIRED FOR ONLY HITHER AND YON CLIPPING
    Vertex3D out[] = new Vertex3D[5];  
    Vertex3D out2[] = new Vertex3D[5];  
    
    for(pts = 0;pts<5;pts++){
      out[pts] = new Vertex3D();
      out2[pts] = new Vertex3D();
    }
    
    // Clip in NDC against the 2 required planes,
    // The planes to be clipped against have the coefficients
    // H_n = ( 0  0  1  1)
    // H_f = ( 0  0 -1  1)
    pts = ClipAgainstPlane(vert, 3, out, 0, 0, 1, 1);
    if(pts != 0) ClipAgainstPlane(out, pts, out2, 0, 0, -1, 1);

    if(pts != 0)
      {
	project.transform(out2[0], vert[0]);
	project.transform(out2[1], vert[1]);
	project.transform(out2[2], vert[2]);

	//for(i=0;i<3;i++)
	//  System.err.println("vert"+i+":"+vert[i]);
	
	Draw(raster);
	
	if(pts == 4)
	  {
	    project.transform(out2[2], vert[1]);
	    project.transform(out2[3], vert[2]);	
	    
	    //for(i=0;i<3;i++)
	    //  System.err.println("vert"+i+":"+vert[i]);
	    
	    Draw(raster);
	  }
	
    	if(pts == 5)
	  {
	    project.transform(out2[3], vert[1]);
	    project.transform(out2[4], vert[2]);	
	    Draw(raster);
	  }
      }
  }
  
  public void Draw(Raster ras)
  {
    // Declarations
    int yVal, xVal;
    int xR, i, pts;
    float lSlope, rSlope;
    double xLeft, xRight;
    int iScolor;
    float Blue, Green, Red, Alpha, Z;
    float iBlue, iRed, iGreen, iAlpha, iZ;

    // Do the triangle setup
    triangleSetup();
      
    // THIS LINE ONLY WORKS FOR FLAT SHADING
    iScolor = iColor0;
    if(bLeft)
      {
	lSlope = Slope10; rSlope = Slope20;
      }
    else
      {
	lSlope = Slope20; rSlope = Slope10;
      }
      
    for(yVal=(int)Math.ceil(vert[0].y); yVal<=(int)vert[1].y && yVal < ras.height;yVal++)
      {
	if(yVal < 0) continue;

    	xLeft = (yVal - vert[0].y)*lSlope + vert[0].x;
	xRight = (yVal - vert[0].y)*rSlope + vert[0].x;	
	  
	xVal=(int)Math.ceil(xLeft);
	  
	if(shading)
	  {
	    // Gouraud shading
	      
	    //Blue = (b[3] - (b[0] * xVal) - (b[1] * yVal)) / b[2];
	    //Red = (r[3] - (r[0] * xVal) - (r[1] * yVal)) / r[2];
	    //Green = (g[3] -(g[0] * xVal) - (g[1] * yVal)) / g[2];
	    // HACK THE ALPHA CHANNEL: IT'S ALWAYS 255 anyway
	    //Alpha = (a[3] - (a[0] * xLeft) - (a[1] * yVal)) / a[2];
	      
	    //iBlue = b[0] / b[2];
	    //iRed = r[0] / r[2];
	    //iGreen = g[0] / g[2];
	    //iAlpha = a[0] / a[2];
	  }
	  
	// Depth interpolation set up
	Z = (z[3] - (z[0] * xVal) - (z[1] * yVal)) / z[2];
	iZ = z[0] / z[2];
	  
	for(;xVal<=(int)xRight && xVal < ras.width;xVal++)
	  {
	    if(xVal < 0) continue;
	    // Get the color
	    //if(shading)
	    // {
	    // Gouraud shading
	      
	    //iScolor = (0xff000000 | (int)(0.5 + Red) << RSHIFT | 
	    //       (int)(0.5 + Green) << GSHIFT | (int)(0.5 + Blue));
	    //Blue -= iBlue;
	    //Green -= iGreen;
	    //Red -= iRed;
	    //Alpha -= iAlpha;
	    //}else{
	    // Flat shading
	    //iScolor = iColor;
	    //  }
	    ras.setPixel(iScolor, xVal, yVal, (int)(0.5+Z));
	    
	    // Do the interpolation incrementation
	    Z -= iZ;
	  }
      }
    
    if(bLeft)
      lSlope = Slope21;
    else
      rSlope = Slope21;
      
    for(yVal=(int)Math.ceil(vert[1].y);yVal<=(int)vert[2].y && yVal < ras.height;yVal++)
      {
	if(yVal < 0) continue;
 
	if(bLeft)
	  {
	    xLeft = (yVal - vert[1].y)*lSlope + vert[1].x;
	    xRight = (yVal - vert[0].y)*rSlope + vert[0].x;
	  }
	else
	  {
	    xLeft = (yVal - vert[0].y)*lSlope + vert[0].x;
	    xRight = (yVal - vert[1].y)*rSlope + vert[1].x;
	  }
	  
	xVal=(int)Math.ceil(xLeft);
	  
	if(shading)
	  {
	    // Gouraud shading
	    
	    //Blue = (b[3] - (b[0] * xVal) - (b[1] * yVal)) / b[2];
	    //Red = (r[3] - (r[0] * xVal) - (r[1] * yVal)) / r[2];
	    //Green = (g[3] - (g[0] * xVal) - (g[1] * yVal)) / g[2];
	    //Alpha = a[3]/a[2] - (a[0] * xVal)/a[2] - (a[1] * yVal)/a[2];
	      
	    //iBlue = b[0] / b[2];
	    //iRed = r[0] / r[2];
	    //iGreen = g[0] / g[2];
	    //iAlpha = a[0] / a[2];
	  }
	
	// Depth interpolation set up
	Z = (z[3] - (z[0] * xVal) - (z[1] * yVal)) / z[2];
	iZ = z[0] / z[2];
	
	for(;xVal<=(int)xRight && xVal < ras.width;xVal++)
	  {
	    if(xVal < 0) continue;
	    // Get the color
	    //if(shading)
	    // {
	    // Gouraud shading
	    
	    //iScolor = (0xff000000 | (int)(Red + 0.5) << RSHIFT | 
	    //	   (int)(Green + 0.5) << GSHIFT | (int)(0.5 + Blue));
	    //Blue -= iBlue;
	    //Green -= iGreen;
	    //Red -= iRed;
	    //Alpha -= iAlpha;		
	    //}else{
	    //iScolor = iColor;
	    //}
	    
	    // try{
	    ras.setPixel(iScolor, xVal, yVal, (int)(0.5+Z));
	    //}catch(Exception e)
	    // {
	    //	System.err.println(vert[0]+" "+vert[1]+" "+vert[2]);
	    //System.err.println(xVal+" "+yVal+" "+(int)(0.5+Z));
	    //System.exit(0);
	    //}
	    
	    // Do the interpolation incrementation
	    Z -= iZ;
	  }
      }
  }
}