import java.awt.*;

public class HW08 extends MISApplet{
   // MATERIAL PROPERTIES
   double ambientColor[] = { 0.02, 0.025, 0.0  };
   double diffuseColor[] = { 0.7, 0.75, 0.0 };
   double specularColor[] = {.7,.8,.0};
   double specularPower = 8.0;
   // LIGHTING PROPERTIES
   double lightDirections[][] = { {1,1,1}, {-1,0,0} ,{0,-1,1}   };
   double lightColors[][]     = { {1.0,1.0,1.0}, {0.9,0.0,0.45}, {0.0,0.5,0.9} };

  Matrix4x4 zoo;
  double zoom = 5.0;
  double rotY = 0.0;
  double rotX = 0.0;
  double rotZ = 0.0;
  double foc = -1.0;//focal length of pinhole camera

  double vec1[] = new double[3];//temporary 3D vector
  double vec2[] = new double[3];//temporary 3D vector
  boolean wired = false;
  Geometry ball;

  public void initialize() {
    for (int l = 0 ; l < lightDirections.length ; l++)
      normalize(lightDirections[l]);
    ball = new Geometry();
    ball.northGlobe(24,12);
  }
  
   public void initFrame(double time) {
     zoom = 5.0 +Math.sin(0.4*time) * .1;
     lightColors[0][1] = 0.5+Math.cos(1.5*time)*0.5;
     lightColors[0][1] = 0.5+Math.cos(1.0*time)*0.5;
     lightColors[0][2] = 0.5+Math.cos(2.0*time)*0.5;
      lightDirections[0][0] = Math.cos(time) *Math.cos(time) * .5;
      lightDirections[0][1] = Math.sin(time)*Math.cos(time) * .5;
      lightDirections[0][2] = Math.sin(time) * .5;
      normalize(lightDirections[0]);
   }
  
  /** Overriden method that must define frame in doube pix[] array */
  public void computeImage(double time){
    initFrame(time);
    //paint the backdrop
    for(int i=0;i<pix.length;i++) pix[i] = pack(10,15,10);
    
    zoo = new Matrix4x4(); 
	zoo.makeTranslation(0,0,-zoom);
    draw(ball);
//    writeTriangle(new double[] {266.0,253.0,0,0,0,0},
 //     new double[] {235.0,253,100,100,100,100}, 
   //   new double[] {253.0,235.0,100,25,50,100});
  }
  
  private void draw(Geometry g){
    for(int i=0; i<g.faces.length;i++){
      double transformed[][] = new double[g.faces.length][6];
	  for(int j=0; j<g.faces[i].length;j++){
	    //get the vertex from faces list
	    double v[] = g.vertices[g.faces[i][j]];
	    
	    Matrix4x4 m = new Matrix4x4();
	    m.identity();
	    m.rotateY(rotY);
	    m.rotateX(rotX);
	    m.rotateZ(rotZ);
        m.preMultiply(zoo);
        m.transform(v[0], v[1], v[2], vec1);
        
        vec1[0] = foc * vec1[0] / (vec1[2]+foc) ;
        vec1[1] = foc * vec1[1] / (vec1[2] +foc) ;
        vec1[2] = 1 /(vec1[2] +foc) ;
		
		vec2[0] = (int)(W/2 + H * vec1[0]);
		vec2[1] = (int)(H/2 - H * vec1[1]);
		vec2[2] = (int)vec2[2];      
        
        transformed[j] = new double[] {vec2[0],vec2[1],vec2[2], v[3],v[4],v[5]};
        setRGB(transformed[j]);
        //pix[xy2i((int)vec2[0],(int)vec2[1])] = pack(255,255,255);
        //System.out.println(""+(int)vec2[0]+", "+(int)vec2[1]);
      }
      if(g.faces[i].length==3)
        writeTriangle(transformed[0], transformed[1], transformed[2]);
      }

  }
  
  private void writeTriangle(double A[], double B[], double C[]){
    //System.out.println("<"+A[0]+","+A[1]+"> "+
    //  "<"+B[0]+","+B[1]+"> "+
    //  "<"+C[0]+","+C[1]+"> ");
    //sort on vertical position
    double[][] list = new double[][] { A, B, C};
    list = mergeSort(list);
    
    
    int topRGB[] = new int[3];
    int midRGB[] = new int[3];
    int botRGB[]  = new int[3];
    int leftRGB[]  = new int[3];
    int rightRGB[]  = new int[3];
    
    topRGB = new int[] { (int) list[0][3] , (int) list[0][4],(int) list[0][5]} ;
    midRGB = new int[] {(int) list[1][3] , (int) list[1][4],(int) list[1][5]} ;
    botRGB = new int[] {(int) list[2][3] , (int) list[2][4],(int) list[2][5]} ;
  
    double f  = (list[1][1] - list[0][1]);
    f= f/ (list[2][1] - list[0][1]);
    int projX = (int)lerp(f,list[0][0],list[2][0]);
    int projZ = (int)lerp(f,list[0][2],list[2][2]);
    int projR = (int)lerp(f,botRGB[0],topRGB[0]);
    int projG = (int)lerp(f,botRGB[1],topRGB[1]);
    int projB = (int)lerp(f,botRGB[2],topRGB[2]);
    int leftX=-1;
    int rightX=-1;
    int leftZ=-1;
    int rightZ=-1;
    if(projX<list[1][0]){
      leftX = projX;
      leftZ = projZ;
      rightX = (int)list[1][0];
      rightZ = (int)list[1][2];
      leftRGB = new int[] {projR, projG, projB};
      rightRGB = midRGB;
    }else{
      rightX = projX;
      rightZ = projZ;
      leftX = (int)list[1][0];
      leftZ = (int)list[1][2];
      rightRGB = new int[] {projR, projG, projB};
      leftRGB = midRGB;
    }

    int[] top = new int[] {(int)list[0][0], (int)list[0][1], (int)list[0][2], 
     topRGB[0], topRGB[1], topRGB[2]};
    int[] bot = new int[] {(int)list[2][0], (int)list[2][1], (int)list[2][2], 
     botRGB[0], botRGB[1], botRGB[2]};
    int[] midL = new int[] {leftX, (int)list[1][1], leftZ, 
     leftRGB[0], leftRGB[1], leftRGB[2]};
    int[] midR = new int[] {rightX,(int)list[1][1], rightZ, 
     rightRGB[0], rightRGB[1], rightRGB[2]};
    
    
    writeTrapezoid(top,top,midL,midR);
    writeTrapezoid(midL,midR,bot,bot);
  }
  
  private void writeTrapezoid(
    int[] topL,
    int[] topR, 
    int[] botL, 
    int[] botR){
    
    // LOOP THRU SCAN LINES
    for (int j = topL[1]; j < botL[1]+1 ; j++) {   
      double t = (j - topL[1]);
      t = t/ (botL[1] - topL[1]);       // COMPUTE FRACTION t
      int Li = (int) lerp(t, topL[0], botL[0])-1;            // COMPUTE LEFT EDGE FOR SCAN LINE
      int Ri = (int) lerp(t, topR[0], botR[0])+1;            // COMPUTE RIGHT EDGE FOR SCAN LINE
      int LR = (int) lerp(t, topL[3], botL[3]);
      int RR = (int) lerp(t, topR[3], botR[3]);
      int LG = (int) lerp(t, topL[4], botL[4]);
      int RG = (int) lerp(t, topR[4], botR[4]);
      int LB = (int) lerp(t, topL[5], botL[5]);
      int RB = (int) lerp(t, topR[5], botR[5]);
      for (int i = Li ; i < Ri ; i++){    // FILL PIXELS IN SCAN LINE
        int z = xy2i(i,j);
        double  s = (i-Li);
        s= s/(Ri-Li);
        int rgb[] = new int[] { 
          (int) lerp(s,LR,RR),
          (int) lerp(s,LG,RG),
          (int) lerp(s,LB,RB)  };
        if(i>0&&i<W&&j>0&&j<H){
          if(wired&&(i==Ri-1||i==Li)&&j!=0&&j!=botL[1]-1)
            pix[z] = pack(rgb[0],rgb[1],rgb[2]); 
          else
            pix[z] = pack(rgb[0],rgb[1],rgb[2]); 
        }
        
      }
      //System.out.println();
    }
  }
    
    // USEFUL MATH

  public static double lerp(double f , double y0, double y1){
    return y0 + (y1-y0)*f;
  }
  
  /***/
  private void setRGB(double[] og){
    int[] rgb = new int[3];
    normal = new double[]{ og[3],og[4],og[5]};
    // START OUT WITH A BLACK PIXEL
    rgb[0] = rgb[1] = rgb[2] = 0;
    // ADD AMBIENT
    for (int i = 0 ; i < 3 ; i++)
      color[i] = ambientColor[i];
    // LOOP THROUGH ALL LIGHT SOURCES
	for (int l = 0 ; l < lightDirections.length ; l++) {
	  // COMPUTE DIFFUSE
	  double n_dot_l = dot(lightDirections[l], normal);
	  if (n_dot_l > 0)
		for (int i = 0 ; i < 3 ; i++)
		  diffuse[i] = diffuseColor[i] * n_dot_l;
	  else
		for (int i = 0 ; i < 3 ; i++)
		  diffuse[i] = 0;

	  // COMPUTE REFLECTION DIRECTION
	  for (int i = 0 ; i < 3 ; i++)
		reflection[i] = 2 * n_dot_l * normal[i] - lightDirections[l][i];

	  double r_dot_e = dot(reflection, eyeDirection);

	  // COMPUTE SPECULAR
	  if (r_dot_e > 0) {
		double specularFactor = Math.pow(r_dot_e, specularPower);
	    for (int i = 0 ; i < 3 ; i++)
	    specular[i] = specularColor[i] * specularFactor;
	  }
	  else
	    for (int i = 0 ; i < 3 ; i++)
	      specular[i] = 0;
	  
	  // ADD DIFFUSE AND SPECULAR
	  for (int i = 0 ; i < 3 ; i++)
	    color[i] += lightColors[l][i] * (diffuse[i] + specular[i]);
	}
	  
	  
	// SEND COLOR TO THE FRAME BUFFER
	for (int i = 0 ; i < 3 ; i++) {
	  double shade = Math.max(0, Math.min(1.0, color[i]));
	  rgb[i] = (int)(255 * shade);
    }
    og[3] = rgb[0];
    og[4] = rgb[1];
    og[5] = rgb[2];
  }
  
  
  
  /** Universal Merge sort using dist function and point P */
  private double[][] mergeSort(double[][] m){

    //sub-problem arrays and result
    double[][] left, right, result;
    
    //base cases
    if(m.length <= 1)
      return m;

    //find middle and create and fille sub-problem arrays
    int middle = m.length/2;
    left = new double[middle][6];
    right = new double[m.length-middle][6];
    for(int j=0;j<left.length;j++)
      left[j] = m[j];
    for(int j=0;j<right.length;j++)
      right[j] = m[middle+j];

    //recursive calls
    left = mergeSort(left);
    right = mergeSort(right);

    //merge sub-problem results into result
    result = merge(left, right);
    return result;
  }

  private double[][] merge(double[][] left, double[][] right){
    //place for merged result 
    double[][] result = new double[left.length+right.length][6];
    int li = 0;
    int ri = 0;
    //merge using dist to compare
    while(li < left.length && ri < right.length){
      if(left[li][1] <= right[ri][1]){
        result[li+ri] = left[li];
        li++;
      }else{
        result[li+ri] = right[ri];
        ri++;
      }
    }

    //clean up left overs
    while(li<left.length){
      result[li+ri] = left[li];
      li++;
    }    
    while(ri<right.length){
      result[li+ri] = right[ri];
      ri++;
    }
    
    return result;
  }


  
  
  
  public void XXXsetPixel(int x, int y, int rgb[]) {

      // START OUT WITH A BLACK PIXEL

      rgb[0] = rgb[1] = rgb[2] = 0;


      // IF ON A SPHERE

      double X =  (x - W/2) / (radius * W);
      double Y = -(y - H/2) / (radius * W);
      double RR = X * X + Y * Y;
      if (RR < 1.0) {

         double Z = Math.sqrt(1.0 - RR);

         point[0] = normal[0] = X;
         point[1] = normal[1] = Y;
         point[2] = normal[2] = Z;



         // ADD AMBIENT

         for (int i = 0 ; i < 3 ; i++)
            color[i] = ambientColor[i];


         // LOOP THROUGH ALL LIGHT SOURCES

         for (int l = 0 ; l < lightDirections.length ; l++) {


            // COMPUTE DIFFUSE

            double n_dot_l = dot(lightDirections[l], normal);

            if (n_dot_l > 0)
               for (int i = 0 ; i < 3 ; i++)
                   diffuse[i] = diffuseColor[i] * n_dot_l;
            else
               for (int i = 0 ; i < 3 ; i++)
                  diffuse[i] = 0;



            // COMPUTE REFLECTION DIRECTION

            for (int i = 0 ; i < 3 ; i++)
               reflection[i] = 2 * n_dot_l * normal[i] - lightDirections[l][i];

            double r_dot_e = dot(reflection, eyeDirection);



            // COMPUTE SPECULAR

            if (r_dot_e > 0) {
               double specularFactor = Math.pow(r_dot_e, specularPower);
               for (int i = 0 ; i < 3 ; i++)
                  specular[i] = specularColor[i] * specularFactor;
            }
            else
               for (int i = 0 ; i < 3 ; i++)
                  specular[i] = 0;


            // ADD DIFFUSE AND SPECULAR

            for (int i = 0 ; i < 3 ; i++)
               color[i] += lightColors[l][i] * (diffuse[i] + specular[i]);
         }


         // SEND COLOR TO THE FRAME BUFFER

         for (int i = 0 ; i < 3 ; i++) {
            double shade = Math.max(0, Math.min(1.0, color[i]));
            rgb[i] = (int)(255 * shade);
         }
      }
   }

   // USEFUL MATH

   public void normalize(double vec[]) {
      double len = norm(vec);
      for (int i = 0 ; i < 3 ; i++)
         vec[i] /= len; 
   }

   public double norm(double vec[]) {
      return Math.sqrt(dot(vec, vec));
   }

   public double dot(double a[], double b[]) {
      return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
   }

   // WORKING VARIABLES

   double color[] = new double[3];
   double diffuse[] = new double[3];
   double specular[] = new double[3];
   double point[] = {0,0,0};
   double normal[] = {0,0,0};
   double eyeDirection[] = {0,0,1};
   double reflection[] = {0,0,0};
   double radius = 0.2;
}