import java.awt.Color;
import java.util.*;
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);
    }
    
    
    /*
        ... you'll need to modify the following two methods ...
    */
    public void Illuminate(Light l[], int lights, Point3D eye, boolean cull)
    {
 
      // Compute Normal to triangle plane

      Point3D edge1 = new Point3D((vlist[v[0]].x - vlist[v[1]].x), (vlist[v[0]].y - vlist[v[1]].y), (vlist[v[0]].z - vlist[v[1]].z));
      Point3D edge2 = 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 M = Point3D.cross(edge1, edge2);
      M.normalize();

      
      if (cull) // backface culling on
	{
	  // compute line of sight vector
	  Point3D V = new Point3D(vlist[v[0]].x - eye.x, vlist[v[0]].y - eye.y, vlist[v[0]].z - eye.z);
	  
	  
	  float check = Point3D.dot(V, M);
	  if (check > 0.0)
	    culled = false;
	  else
	    {
	      culled = true;
	      return;
	    }
	}
     
      for (int i = 0; i < 3; i++)
	{
	  r[i] = surface.r;
	  g[i] = surface.g;
	  b[i] = surface.b;
	  
	}
      
      	  float ka = surface.ka;
	  float kd = surface.kd;
	  float ks = surface.ks;
	  float ns = surface.ns;
	  boolean dot;
	  
	  for (int i = 0; i < 3; i++) 
	    {
	      Point3D N = new Point3D(vlist[v[i]].nx, vlist[v[i]].ny, vlist[v[i]].nz);
	      if (Point3D.dot(N, M) > (1/ Math.sqrt(2)))
		{
		  // use vertex normal
		  dot = true;
		
		  
		  if (vlist[v[i]].hasColor)
		  {
		    r[i] = vlist[v[i]].r;
		    g[i] = vlist[v[i]].g;
		    b[i] = vlist[v[i]].b;
		    continue;
		  }
		}
	      else
		{
		  // revert to triangle normal
		  dot = false;
		  N.x = M.x;
		  N.y = M.y;
		  N.z = M.z;
		}
	      float ir = 0.0f;
	      float ig = 0.0f;
	      float ib = 0.0f;
	      
	      Point3D V = new Point3D(eye.x - vlist[v[i]].x, eye.y - vlist[v[i]].y, eye.z - vlist[v[i]].z);
	      V.normalize();

	      // illuminate

	      for (int li = 0; li < lights; li++)
		{
		  Light lt = l[li];
		  if (lt.lightType == Light.AMBIENT)
		    {
		      ir += ka*lt.ir;
		      ig += ka*lt.ig;
		      ib += ka*lt.ib;
		    }
		  else
		    {
		      Point3D L;
		      if (lt.lightType == Light.DIRECTIONAL)
			 L = new Point3D(lt.x, lt.y, lt.z);
		      else
			{
			  L = new Point3D(lt.x - vlist[v[i]].x, lt.y - vlist[v[i]].y, lt.z - vlist[v[i]].x);
			  L.normalize();
			}
			float d = Point3D.dot(N, L);
			
			ir += kd*lt.ir*d;
			ig += kd*lt.ig*d;
			ib += kd*lt.ib*d;
			Point3D R = new Point3D(2*d*N.x - L.x, 2*d*N.y - L.y, 2*d*N.z - L.z);
			float d2 = (float) Math.exp(ns*Math.log(Point3D.dot(V, R)));
			ir += ks*lt.ir*d2;
			ig += ks*lt.ig*d2;
			ib += ks*lt.ib*d2;
		      }
		}
		  
	      r[i]*=ir;
	      g[i]*=ig;
	      b[i]*=ib;
	      if (r[i] > 1.0f)
		r[i] = 1.0f;
	      if (g[i] > 1.0f)
		g[i] = 1.0f;
	      if (b[i] > 1.0f)
		b[i] = 1.0f;
	      if (dot)
		{
		  vlist[v[i]].r = r[i];
		  vlist[v[i]].g = g[i];
		  vlist[v[i]].b = b[i];
		  vlist[v[i]].hasColor = true;
		}
	    }
    }
  
	

  
  
  
  public static Vertex3D intersect(Vertex3D v1, Vertex3D v2, int z)
  {
    float newx, newy, newr, newg, newb;
    float dx, dy, dr, dg, db,deltaz;
    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.g = newg;
    out.b = newb;
    out.hasColor = true;
    return out;
  }

  public static Vector ClipToNearPlane(Vector v)
  {
    Vector out = new Vector();
    int currloc;
    if (((Vertex3D) v.elementAt(0)).z <  -1)
      currloc = 1;
    else 
      currloc = 0;
    for (int i = 0; i < v.size(); i++)
      {
	int j = (i+1)%v.size();
	Vertex3D v1 = (Vertex3D) v.elementAt(i);
	Vertex3D v2 = (Vertex3D) v.elementAt(j);
	int newloc;
	if (v2.z < -1)
	  newloc = 1;
	else
	  newloc = 0;
	if (currloc == 1)
	  {
	    if (newloc == 0)
	      {
		out.addElement(intersect(v1, v2, -1));
		out.addElement(v2);
	      }
	  }
	else
	  {
	    if (newloc == 0)
	      out.addElement(v2);
	    else
	      out.addElement(intersect(v1, v2, -1));
	  }
	currloc = newloc;
      }
    return out;
  }


  public static Vector ClipToFarPlane(Vector v)
  {
    Vector out = new Vector();
    int currloc;
    if (((Vertex3D) v.elementAt(0)).z >  1)
      currloc = 1;
    else 
      currloc = 0;
    for (int i = 0; i < v.size(); i++)
      {
	int j = (i+1)%v.size();
	Vertex3D v1 = (Vertex3D) v.elementAt(i);
	Vertex3D v2 = (Vertex3D) v.elementAt(j);
	int newloc;
	if (v2.z > 1)
	  newloc = 1;
	else
	  newloc = 0;
	if (currloc == 1)
	  {
	    if (newloc == 0)
	      {
		out.addElement(intersect(v1, v2, 1));
		out.addElement(v2);
	      }
	  }
	else
	  {
	    if (newloc == 0)
	      out.addElement(v2);
	    else
	      out.addElement(intersect(v1, v2, 1));
	  }
	currloc = newloc;
      }
    return out;
  }
	      
	
			     


	  
	  
    public void ClipAndDraw(ZRaster raster, Matrix3D project)
    {
      vert[0].copy(vlist[v[0]]);
      vert[1].copy(vlist[v[1]]);
      vert[2].copy(vlist[v[2]]);
      for (int i = 0; i< 3; i++)
	{
	  vert[i].r = r[i];
	  vert[i].b = b[i];
	  vert[i].g = g[i];
	}
    
      vert[2].normalize();
      vert[1].normalize();
      vert[0].normalize();
      if ((vert[0].z > 1) && (vert[1].z > 1) && (vert[2].z > 1))
	return;
      if ((vert[0].z < -1) && (vert[1].z < -1) && (vert[2].z < -1))
	return;
      if (((vert[0].z < 1) && (vert[0].z > -1)) &&
	  ((vert[1].z < 1) && (vert[1].z > -1)) &&
	  ((vert[2].z < 1) && (vert[2].z > -1)))
	{
	  vert[0] = project.transform(vlist[v[0]]);
	  vert[1] = project.transform(vlist[v[1]]);
	  vert[2] = project.transform(vlist[v[2]]);
	  
	  Draw(raster);
	  return;
	}
      else
	{
	  Vector vertices = new Vector();
	    vertices.addElement(vert[0]);
	    vertices.addElement(vert[1]);
	    vertices.addElement(vert[2]);
	    vertices = ClipToNearPlane(vertices);
	    if (vertices.size() != 0)
	      {
		
		vertices = ClipToFarPlane(vertices);
		if (vertices.size() == 0)
		  return;
		Vertex3D v0 = (Vertex3D) vertices.elementAt(0);
		Vertex3D v2 = (Vertex3D) vertices.elementAt(1);
		
		Vertex3D v1;
		vert[0] = project.transform(vert[0]);
		vert[1] = project.transform(vert[1]);
		vert[2] = project.transform(vert[2]);
		Draw(raster);
		vert[0]= v0;
				

		for (int i = 2; i < vertices.size(); i++)
		  {
		    v1 = v2;
		    v2 = (Vertex3D) vertices.elementAt(i);
		    
		    vert[1] = v1;
		    vert[2] = v2;
		    for (int j = 0; j < 3; j++)
		      {
			r[j] = vert[j].r;
			g[j] = vert[j].g;
			b[j] = vert[j].b;
		      }
		    
		    vert[0] = project.transform(vert[0]);
		    vert[1] = project.transform(vert[1]);
		    vert[2] = project.transform(vert[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;
        }
    }
}