import java.awt.*;
import java.util.LinkedList;

public class HW12a extends MISApplet{
  // MATERIAL PROPERTIES
  double ambientColor[] = { 0.2, 0., 0.0  };
  double diffuseColor[] = { 0.8, 0.0, 0.0 };
  double specularColor[] = {.1,.1,.1};
  double specularPower = 20.0;
  // LIGHTING PROPERTIES
  /**
  double lightDirections[][] = { {1,0,0} };
  double lightColors[][]     = { {1.0,1.0,1.0} };
  */
  double lightDirections[][] = { {1,1,1}, {0,0,1} ,{-1,0,-1}   };
  double lightColors[][]     = { {0.8,0.9,0.8}, {0.5,0.6,0.5}, {0.5,0.6,0.5} };
  boolean useLight[] = new boolean[lightDirections.length];

  int res = 10;

  double foc = 5.0;//focal length of pinhole camera

  int type;

  double oldTime;
  double dt;
  LinkedList<ImplicitSurface> surface_list;
  final double EPSILON = 0.0001; 
  final double INFINITY = Double.MAX_VALUE;

  double eye[]; 
  boolean mouseDown = false;
  boolean texture = false;

  int pixel_width_max = 10;
  int pixel_width_min = 1;
  int pixel_width = pixel_width_max;
  int pass_pixel_width = pixel_width;

  double camRotX;
  double camRotY;
  double camRotZ;
  double rotY;
  double lrotY;
  double rrotY;
  double lrotX;
  double rrotX;
  double xMAX=2;
  double yMAX=2;
  double zMAX=2;
  int alias = 0;
  double opacity = 0.0;
  Cube s;
  double dx[];
  double dy[];
  double dz[];
  double old_dx[];
  double old_dy[];
  double old_dz[];
  boolean frozen;
  
  /**  Do this once per run */
  public void initialize() {
    camRotX =  0.16493361431346415;
    camRotY = -0.38222710618675815;
    camRotZ = 0.0;
    surface_list = new LinkedList<ImplicitSurface>();
//  Hemisphere s = new Hemisphere(1.0);
//    Sphere s = new Sphere(1.0);
    s = new Cube(1.0);
    s.indigo().clear();
    surface_list.add(s);
    surface_list.add(new Sphere(0.5).red().semiclear().metal());
    surface_list.add(new Sphere(0.5).yellow().semiclear().metal());
    surface_list.add(new Sphere(0.5).darkGray().semiclear().metal());
    //surface_list.add(new InfinitePlane(0,0,1,1).blue());
    dx  = new double[] {0.0, 1.5*Math.cos(0/10), 0.0,0.0};
    dy = new double[] {0.0, 0.0, 1.5*Math.cos(2*Math.PI/3+0/10), 0};
    dz = new double[] {0.0,0.0,0.0, 1.5*Math.cos(2*2*Math.PI/3+0/10)};
    frozen = false;
  }

  
  /** Overriden method that must define frame in doube pix[] array */
  public void computeImage(double time){
    dt = Math.min(1,time - oldTime);
    oldTime = time;  
    
    //FREEZING NEEDS TO REVERT TO "LAST SEEN" NOT "LAST PAINTED"
    if(!frozen){
      old_dx = dx;
      old_dy = dy;
      old_dz = dz;
      dx  = new double[] {0.0, 1.5*Math.cos(time/10), 0.0,0.0};
      dy = new double[] {0.0, 0.0, 1.5*Math.cos(2*Math.PI/3+time/10), 0};
      dz = new double[] {0.0,0.0,0.0, 1.5*Math.cos(2*2*Math.PI/3+time/10)};
    }else{
      dx = old_dx;
      dy = old_dy;
      dz = old_dz;
    }
    
    // MOVE THE WORLD ACCORDING TO "CAMERA"
    Matrix4x4 m = new Matrix4x4();
    m.identity();
    m.translate(0,0,-20);
    m.rotateX(camRotX);
    m.rotateY(camRotY);
    m.rotateZ(camRotZ);
    int in= 0;
    for(ImplicitSurface s: surface_list){
      m.translate(dx[in],dy[in],dz[in]);
      s.transform(m);
      m.translate(-dx[in],-dy[in],-dz[in]);
      if(in==0) s.opacity = opacity;
      else s.opacity = 1.0 - opacity;
      in++;
    }

    // SLOWLY INCREASE RESOLUTION
    if(pass_pixel_width > pixel_width_min)
      pixel_width = pass_pixel_width;
    pass_pixel_width = -1;
    if(mouseDown)
      pixel_width = pixel_width_max;
    else
      pixel_width = Math.max(pixel_width_min, pixel_width/2);
    
    
    double rgb[] = new double[3];
    double v  [] = new double[3];
    double w  [] = new double[3];
    
    
    // NON ANTI-ALIASING IS FASTER BECAUSE IT DOESN'T LOOP OVER DOUBLES
    if(alias==0){
	    for (int i = 0 ; i < W ; i+=pixel_width)   // LOOP OVER IMAGE COLUMNS
  	  for (int j = 0 ; j < H ; j+=pixel_width) {  // LOOP OVER IMAGE ROWS

        // CONSTRUCT ORIGINAL RAY FROM EYE
  		  v[0] = 0; 
  		  v[1] = 0;
  		  v[2] = 0;
		  
  		  w[0] = (double)(i - W/2) / W; // COMPUTE RAY DIRECTION AT EACH PIXEL
  		  w[1] = (double)(H/2 - j) / W; //
  		  w[2] = -foc;          // PLACE IMAGE PLANE AT z=-focalLength
        //initialize pixel color to black
  		  rgb[0]=0;
  		  rgb[1]=0;
  		  rgb[2]=0;
  		  
  		  normalize(w);
  		  rayTrace(v, w, rgb, 0, null , false);          // COMPUTE COLOR AT PIXEL BY RAY TRACING
  		  int[] color = new int[] {(int)(255*rgb[0]), (int)(255*rgb[1]), (int)(255*rgb[2]) };
  		  for(int _i = i; _i<W && _i < i+pixel_width; _i++)
  		  for(int _j = j; _j<H && _j < j+pixel_width; _j++)
  			pix[xy2i(_i,_j)] = pack(color[0],color[1],color[2]);
  		  //setPixel(i, j, color);
  	  }
    }else{
    
      int color[];
	    for (int ii = 0 ; ii < W ; ii+=pixel_width)   // LOOP OVER IMAGE COLUMNS
  	  for (int jj = 0 ; jj < H ; jj+=pixel_width) {  // LOOP OVER IMAGE ROWS
  		int rayCount = 0;
  		color = new int[] {0,0,0}; // initialize to black ( 0 for averaging )
  	  for (double i = ii ; i<W && i < ii+pixel_width; i+=pixel_width/alias)   // LOOP OVER IMAGE COLUMNS
  	  for (double j = jj ; j<H && j < jj+pixel_width; j+=pixel_width/alias) {  // LOOP OVER IMAGE ROWS
  		  rayCount++;
  		  //System.out.println("ij "+i+" , "+j);
  		  v[0] = 0; 
  		  v[1] = 0;
  		  v[2] = 0;
		  
  		  w[0] = (double)(i - W/2) / W; // COMPUTE RAY DIRECTION AT EACH PIXEL
  		  w[1] = (double)(H/2 - j) / W; //
  		  w[2] = -foc;          // PLACE IMAGE PLANE AT z=-focalLength
        
        //initialize pixel color to black
  		  rgb[0]=0;
  		  rgb[1]=0;
  		  rgb[2]=0;
  		  normalize(w);
  		  rayTrace(v, w, rgb, 0, null , false);          // COMPUTE COLOR AT PIXEL BY RAY TRACING
  		  for(int k =0; k<color.length;k++)
  			color[k] += (int)(255*rgb[k]);
  	  }
  		  for(int k =0; k<color.length;k++)
  			color[k] = color[k]/rayCount;
	   
  		  for(int _i = ii; _i<W && _i < ii+pixel_width; _i++)
  		  for(int _j = jj; _j<H && _j < jj+pixel_width; _j++)
  			pix[xy2i(_i,_j)] = pack(color[0],color[1],color[2]);
  		  //setPixel(i, j, color);
  	  }
      }
  }

  
  private void rayTrace(double v[], double w[], double rgb[], int depth, ImplicitSurface within, boolean skip){
    double t = INFINITY; 
    ImplicitSurface closest = null;
    //loop over all surfaces
    for(ImplicitSurface surface: surface_list){
      //Try to intersect the ray with Sphn, to get tn;
      //If the ray intersects Sphn at some tn, and tn < t, then this is the
      //nearest sphere, so:
      double tn = surface.intersect(v,w,skip);
      //System.out.println("tn: "+tn );
      if(tn>0&&tn<t){
        t = tn;
        closest = surface;
      }
    }  
    // hit something? add color
    if(null!=closest)
      if(depth<surface_list.size()+2) //to avoid infinity
        computeShade(v,w,closest,t,rgb, depth, within, skip);
      //else
      //  System.out.println("Infinity avoided...");
  }

  private void computeShade(
    double v[],
    double w[],
    ImplicitSurface surface,
    double t,
    double rgb[],
    int depth,
    ImplicitSurface within,
    boolean skip
  ){
    double point[] = new double[]{ 
      (v[0]+w[0]*t),
      (v[1]+w[1]*t),
      (v[2]+w[2]*t)
    };
    double normal[] = new double[3];
    surface.computeNormal(point, normal);
    normalize(normal);//be sure it is unit length
    
    // SHADOWS
    //initialize all lights
    for(int k = 0;k<useLight.length;k++)
      useLight[k] = true;
    
    //first find out which lights are in shadow.
    for(int k=0;k<lightDirections.length;k++){
      if(useLight[k]){
        double L[] = new double[] {
           lightDirections[k][0],
           lightDirections[k][1], 
           lightDirections[k][2]
        };
        normalize(L);
        double vp[] = new double[] {
          point[0],
          point[1],
          point[2]
        };
        //check for shadowing objects
        for(ImplicitSurface s: surface_list){
          if(s!=surface){//don't shadow yourself
            double tn =  s.intersect(vp,L,skip);
            if(tn< INFINITY&&tn>0){
              useLight[k] = false;
              break;
            }
          }
        }
      } 
    }

    
    type = surface.type;
    ambientColor = surface.ambientColor;
    diffuseColor = surface.diffuseColor;
    specularColor = surface.specularColor;
    specularPower= surface.specularPower;
    if(!skip && surface.opacity>0)
      phong(normal, rgb, depth, surface.opacity);


    // REFLECTION
    double vp[] = new double[] {
      point[0] + EPSILON*normal[0],
      point[1] + EPSILON*normal[1],
      point[2] + EPSILON*normal[2]
    };
    normalize(normal);//superfluous?
    double wdn = dot(w,normal);// w dot normal
    double wp[] = new double[] {
      w[0] - 2*wdn*normal[0], 
      w[1] - 2*wdn*normal[1], 
      w[2] - 2*wdn*normal[2] 
    };
    //recursive call to continue ray
    rayTrace(vp,wp,rgb, depth+1,within, false);  
    
    
    //REFRACTION
    double c[] = new double[] {
      wdn*normal[0], 
      wdn*normal[1], 
      wdn*normal[2] 
    };
    double s[] = new double[] {
      w[0]-c[0], 
      w[1]-c[1], 
      w[2]-c[2] 
    };
    // air is 1, air is not being in something
    double n1 = null==within ? 1.0 : within.n;
    double n2 = (null!=within && surface==within) ? 1.0 : surface.n;
    
    double theta1 = Math.acos(norm(c));
    double theta2 = Math.asin(Math.sin(theta1)*n1/n2);
    normalize(c);
    normalize(s);
    wp[0] = c[0]*Math.cos(theta2)+s[0]*Math.sin(theta2);
    wp[1] = c[1]*Math.cos(theta2)+s[1]*Math.sin(theta2);
    wp[2] = c[2]*Math.cos(theta2)+s[2]*Math.sin(theta2); 

    //normalize(wp);
    vp[0] = point[0] + EPSILON*wp[0];
    vp[1] = point[1] + EPSILON*wp[1];
    vp[2] = point[2] + EPSILON*wp[2];
    
    
    //if(theta1<Math.PI/4)
    if(surface.opacity<1.0)
      rayTrace(vp,wp,rgb, depth+1, surface, surface==within);  
  }


  /** Phong algorithm for shading vertices
    * takes a normal and an initial color then adds phong shade to color given
    */
  private void phong(double[] normal, double rgb[], int depth, double opacity){
        // SAMPLE THE FUNCTION FOUR TIMES TO GET GRADIENT INFO

         if(texture){
         double f0 = f(normal[0]      ,normal[1]      ,normal[2]      ),
                fx = f(normal[0]+.0001,normal[1]      ,normal[2]      ),
                fy = f(normal[0]      ,normal[1]+.0001,normal[2]      ),
                fz = f(normal[0]      ,normal[1]      ,normal[2]+.0001);

         // SUBTRACT THE FUNCTION'S GRADIENT FROM THE SURFACE NORMAL

         
         normal[0] -= (fx - f0) / .0001;
         normal[1] -= (fy - f0) / .0001;
         normal[2] -= (fz - f0) / .0001;
         normalize(normal);
         }
    // ADD AMBIENT
    for (int i = 0 ; i < 3 ; i++){
      color[i] = 0;
      if(depth==0) color[i] = ambientColor[i];
    }
    // LOOP THROUGH ALL LIGHT SOURCES
    for (int l = 0 ; l < lightDirections.length ; l++) {
      if(useLight[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++) {
      rgb[i] += opacity*Math.pow(0.25,depth)* Math.max(0, Math.min(1.0, color[i]));
      rgb[i] = Math.min(rgb[i],1.0);
    }
  }
  
  // MERGE SORT
  
  /** 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;
  }

  // INTERACTION 
  
  public boolean keyUp(Event e, int key){
    switch(key){
      case 'O':
      case 'o':
        if(opacity==0.0){
          opacity = 0.5;
        }else if(opacity<=0.5){
          opacity = 1.0;
        }else if(opacity>0.5){
          opacity = 0.0;
        }
        pass_pixel_width = pixel_width_max;
        break;
      case '-':
      case '_':
        pixel_width_max= Math.max(1,pixel_width_max/2);
        pixel_width_min= Math.max(1,pixel_width_min/2);
        pass_pixel_width = pixel_width_max;
        break;
      case '+':
      case '=':
        pixel_width_max*=2;
        pixel_width_min*=2;
        pass_pixel_width = pixel_width_max;
        break;
      case 't':
      case 'T':
        texture = !texture;
        pass_pixel_width = pixel_width_max;
        break;
      case 'f':
      case 'F':
        frozen = !frozen;
        pass_pixel_width = pixel_width_max;
        break;
      case 'c':
      case 'C':
        System.out.println("camRotX: "+camRotX);
        System.out.println("camRotY: "+camRotY);
        System.out.println("camRotZ: "+camRotZ);
        break;
    }
    return true;
  }
  
  public boolean mouseDown(Event e, int x, int y){
    mouseDown = true;
    return true;
  }
  public boolean mouseUp(Event e, int x, int y){
    mouseDown = false;
    return true;
  }
  public boolean mouseDrag(Event e, int x, int y) {
    int wx = W/2;
    int wy = H/2;
    y = H - y - 1;
    double radius = Math.min( W, H )/2.;
    double sx = (x-wx)/radius;
    double sy = (y-wy)/radius;
    if(sx*sx+sy*sy>1){
      double denom = Math.sqrt(sx*sx+sy*sy);
      sx /= denom;
      sy /= denom;
    }
    double sz= Math.sqrt(Math.max(0,1-sx*sx-sy*sy));
    double off[] = {sx,sy,sz};
    normalize(off);
    //camRotX = sign(sy)*Math.acos(dot(off,new double[]{1,0,0}));
    //camRotY = sign(sx)*Math.acos(dot(off,new double[]{0,0,1}));
    //camRotZ = Math.acos(dot(off,new double[]{1,0,0}));
    camRotY = Math.PI*(x-W/2)/W;
    camRotX = -Math.PI*(y-H/2)/H;
    //camRotY = sign(x)*Math.PI/2*(x-W/2)/W;
    //camRotX = -sign(y)*Math.PI/2*(y-H/2)/H;
    return true;
  }






  // USEFUL MATH
  public static void lerp(double f , double y0[], double y1[], double dst[]){
    for(int i=0;i<y0.length;i++)
      dst[i] = y0[i] + (y1[i]-y0[i])*f;
  }
  public static void lerp(double f , int y0[], int y1[], int dst[]){
    for(int i=0;i<y0.length;i++)
      dst[i] = (int) (y0[i] + (y1[i]-y0[i])*f);
  }
  public static double lerp(double f , double y0, double y1){
    return y0 + (y1-y0)*f;
  }

  public static void normalize(double vec[]) {
     double len = norm(vec);
     for (int i = 0 ; i < 3 ; i++)
        vec[i] /= len; 
  }
  
  /**
   * return z value of surface normal
   * Uses first 3 values
   */
  public static double normalZ(double[][] triangle){
    double[] p1 = triangle[0];
    double[] p2 = triangle[1];
    double[] p3 = triangle[2];
    
    //if rect then I can do a little err check and get a true triangle
    if (triangle.length>3){
      if(equals(p1,p2)){
        p1 = triangle[3];
      }else if(equals(p1,p3)){
        p1 = triangle[3];
      }else if(equals(p2,p3)){
        p3 = triangle[3];
      }
    }
    
    
    double[] a = new double[] {p2[0]-p1[0],p2[1]-p1[1],p2[2]-p1[2]};
    double[] b = new double[] {p3[0]-p1[0],p3[1]-p1[1],p3[2]-p1[2]};
    
    /* Surface normal is (p2-p1)x(p3-p1)
     * of which we only need the z-coordinate
     * so if n = axb then the z-coordinate is 
     * a1b2 - a2b1
     * which in this case is
     * (p21 - p11)(p32-p12)-(p32-p12)(p31-p11)
     */
    //let's try that again
    //(a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1)
    double[] cross = new double[] {a[1]*b[2] - a[2]*b[1],
      a[2]*b[0] - a[0]*b[2], a[0]*b[1] - a[1]*b[0]};
    return cross[2];  
  }
  
  public static boolean equals(double p1[], double p2[]){
    for(int i =0; i<p1.length; i++)
      if(p1[i]!=p2[i]) return false;
    return true;
  }
  
  public static double norm(double vec[]) {
     return Math.sqrt(dot(vec, vec));
  }

  public static double dot(double a[], double b[]) {
     return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
  }
  
  //0 is positive
  public int sign(double d){
    if(d==0) return 0;
    else return (int)(d/Math.abs(d));
  }
  //FINAL CONSTANTS
  final int NUM_SIDES_ON_TRIANGLE = 3;
  final double dampening = 0.99;

  // 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;
 // STRIPES TEXTURE (GOOD FOR MAKING MARBLE)

   double stripes(double x, double f) {
      double t = .5 + .5 * Math.sin(f * 2*Math.PI * x);
      return t * t - .5;
   }

   // TURBULENCE TEXTURE

   double turbulence(double x, double y, double z, double freq) {
      double t = -.5;
      for ( ; freq <= W/12 ; freq *= 2)
         t += Math.abs(noise(x,y,z,freq) / freq);
      return t;
   }
        
        // CHOOSE A TYPE OF SPACE FILLING TEXTURE

   double f(double x,double y,double z) {
     switch(type){

      case 0:  return .008 * stripes(x+ 2.2*turbulence(x,y,0,1), 1.6); 
      case 1:  return .02 * stripes(x+ 2.2*turbulence(x,y,0,2), 0.4); 
      default: return .01 * stripes(x+ 2.2*turbulence(x,y,0,1), 0.5); 
       //case 2: return 0.11*turbulence(x+stripes(x,0.5),y,z,0.5); 
       //case 1: return .01 * noise(x,y,z, 10); 
       //default: return 0.12*turbulence(x+stripes(x,0.3),y+stripes(y,0.3),z,1);
     }
   }
   
   // NOISE TEXTURE

   double noise(double x, double y, double z, double freq) {
      double x1, y1, z1;
      x1 = .707*x-.707*z;
      z1 = .707*x+.707*z;
      y1 = .707*x1+.707*y;
      x1 = .707*x1-.707*y;
      return ImprovedNoise.noise(freq*x1 + 100, freq*y1, freq*z1);
   }

}