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

class Sphere{
  double c[];//center
  double v[];
  double f[];
  double r;//radius
  double m;
  double ambientColor[] = { 0.2, 0.2, 0.2  };
  double diffuseColor[] = { 0.8, 0.8, 0.8 };
  double specularColor[] = {.000001,.000001,.000001};
  double specularPower = 20.0;
  public Sphere(double x, double y, double z, double r){
    c= new double[] {x,y,z};
    this.r  = r;
    v= new double[] {0,0,0};
    f= new double[] {0,0,0};
    m=1;
  }
  
  public Sphere blue(){
    ambientColor = new double[] {0.1,0.1,0.2};
    diffuseColor = new double[] {0.1,0.1,0.8};
    return this;
  }
  public Sphere green(){
    ambientColor = new double[] {0.1,0.2,0.1};
    diffuseColor = new double[] {0.0,0.8,0.0};
    return this;
  }
  public Sphere pink(){
    ambientColor = new double[] {0.2,0.1,0.1};
    diffuseColor = new double[] {0.6,0.0,0.3};
    return this;
  }
  public Sphere purple(){
    ambientColor = new double[] {0.12,0.1,0.18};
    diffuseColor = new double[] {0.3,0.0,0.6};
    return this;
  }
  public Sphere red(){
    ambientColor = new double[] {0.2,0.1,0.1};
    diffuseColor = new double[] {0.8,0.0,0.0};
    return this;
  }
  
  public void applyForce(double dt){
    v[0] += f[0]/m*dt;
    v[1] += f[1]/m*dt;
    v[2] += f[2]/m*dt;
  }
  public void applyVelocity(double dt){
    c[0] += v[0]*dt;
    c[1] += v[1]*dt;
    c[2] += v[2]*dt;
  }
  public void addToForce(double x, double y, double z){
     f[0]+=x;
     f[1]+=y;
     f[2]+=z;
  }
}

public class HW10 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}, {1,0,0} ,{-1,0,0}   };
  double lightColors[][]     = { {0.9,0.9,0.8}, {0.9,0.0,0.45}, {0.45,0.0,0.9} };
  boolean useLight[] = new boolean[lightDirections.length];

  double grav[] = new double[] {0,-.4,0};//gravity force
  
  int res = 10;

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

  double vec1[] = new double[3];//temporary 3D vector
  double vec2[] = new double[3];//temporary 3D vector

  double oldTime;
  double dt;
  LinkedList<Sphere> sphere_list;
  final double EPSILON = 0.0001; 
  final double INFINITY = Double.MAX_VALUE;
  double eye[]; 
  Sphere moon;
  Sphere head;
  Sphere leye;
  Sphere reye;
  Sphere lpupil;
  Sphere rpupil;
  
  double rotY;
  double lrotY;
  double rrotY;
  double lrotX;
  double rrotX;
  
  /**  Do this once per run */
  public void initialize() {
    sphere_list = new LinkedList<Sphere>();
    lpupil = new Sphere(-0.3,0.3,-18.5,0.1);
    rpupil = new Sphere(0.3,0.3,-18.5,0.1);
    sphere_list.add(lpupil);
    sphere_list.add(rpupil);
    leye = new Sphere(-0.3,0.3,-18.7,0.2).pink(); 
    reye = new Sphere(0.3,0.3,-18.7,0.2).pink(); 
    sphere_list.add(leye);
    sphere_list.add(reye);
    head = new Sphere(-0,0,-20,1).purple(); 
    sphere_list.add(head);
    moon = new Sphere(-1.5,0,-20,0.25).green();
    sphere_list.add(moon);
    rotY = 0;
    lrotY = 0;
    lrotX = 0;
    rrotY = 0;
    rrotX = 0;
  }
  
  /** Overriden method that must define frame in doube pix[] array */
  public void computeImage(double time){
    dt = Math.min(1,time - oldTime);
    oldTime = time;
    
    double h2m[] = {moon.c[0]-head.c[0], 0,moon.c[2]-head.c[2]};
    normalize(h2m);
    double angle = sign(moon.c[0])*Math.acos(dot(h2m,new double[] {0,0,1}));
    if(angle>rotY) rotY+= (angle-rotY)/8;
    else rotY-= (rotY-angle)/8;

    double le2m[] = {0,moon.c[1]-leye.c[1],moon.c[2]-leye.c[2]};
    normalize(le2m);
    angle = -0.5*sign(moon.c[1])*Math.acos(dot(le2m,new double[] {0,0,1}));
    if(angle>lrotX) lrotX+= (angle-lrotX)/4;
    else lrotX-= (lrotX-angle)/4;
    
    double re2m[] = {0,moon.c[1]-reye.c[1],moon.c[2]-reye.c[2]};
    normalize(re2m);
    angle = -0.5*sign(moon.c[1])*Math.acos(dot(re2m,new double[] {0,0,1}));
    if(angle>rrotX) rrotX+= (angle-rrotX)/4;
    else rrotX-= (rrotX-angle)/4;

    boolean within = false;/**Math.abs(rotY-angle)<0.1;
    double le2m[] = { moon.c[0]-leye.c[0],moon.c[1]-leye.c[1],moon.c[2]-leye.c[2]};
    normalize(le2m);
    le2m[0]*=.18;
    le2m[1]*=.18;
    le2m[2]*=.18;
    double re2m[] = { moon.c[0]-reye.c[0],moon.c[1]-reye.c[1],moon.c[2]-reye.c[2]};
    normalize(re2m);
    re2m[0]*=.18;
    re2m[1]*=.18;
    re2m[2]*=.18;**/
  
    Matrix4x4 m = new Matrix4x4();
    m.identity();
    m.translate(0,0,-20);
    m.rotateX(0);
    m.rotateY(rotY);
    m.rotateZ(0);
    m.transform(0,0,0,head.c);
    Matrix4x4 left = m.getCopy();
    left.translate(-0.3,0.3,0.8);
    left.transform(0,0,0,leye.c);
    //if(within){
    //  left.rotateY(-rotY);
    //  left.translate(le2m[0],le2m[1],le2m[2]);
   // }else
    left.rotateX(lrotX);
    left.translate(0.0,0.0,0.18);
    left.transform(0,0,0,lpupil.c);
    m.translate(0.3,0.3,0.8);
    m.transform(0,0,0,reye.c);
    //if(within){
    ///  m.rotateY(-rotY);
    //  m.translate(re2m[0],re2m[1],re2m[2]);
   // }else
    m.rotateX(rrotX);
      m.translate(0.0,0.0,0.18);
    m.transform(0,0,0,rpupil.c);

    // moon.c[2] = -20+1.5*Math.cos(time);
    //moon.c[0] = 1.5*Math.sin(time);


    double rgb[];
    int color[];
    double v  [] = new double[3];
    double w  [] = new double[3];
    for (int i = 0 ; i < W ; i++)   // LOOP OVER IMAGE COLUMNS
    for (int j = 0 ; j < H ; j++) {  // LOOP OVER IMAGE ROWS
        //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

        rgb = new double[] {0,0,0};//initialize pixel color to black
        normalize(w);
        rayTrace(v, w, rgb);          // COMPUTE COLOR AT PIXEL BY RAY TRACING
        color = new int[] {(int)(255*rgb[0]), (int)(255*rgb[1]), (int)(255*rgb[2]) };
        pix[xy2i(i,j)] = pack(color[0],color[1],color[2]);
        //setPixel(i, j, color);
    }
  }
  
  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);
    off[0]*=1.5;
    off[1]*=1.5;
    off[2]*=1.5;
    moon.c[0] = 0+off[0];
    moon.c[1] = 0+off[1];
    moon.c[2] = -20+off[2];
    return true;
  }
  
  private void updatePhysics(){
    /**ball1.addToForce(grav[0]*ball1.m,grav[1]*ball1.m,grav[2]*ball1.m);
    double T[] = {ball1.c[0]-hinge.c[0], ball1.c[1]-hinge.c[1],ball1.c[2]-hinge.c[2] };
    normalize(T);
    double gdt = dot(grav,T);
    double F[] = {-gdt*T[0], -gdt*T[1], -gdt*T[2]};
    ball1.addToForce(F[0]*ball1.m,F[1]*ball1.m,F[2]*ball1.m);
    ball1.applyForce(dt);
    ball1.applyVelocity(dt);
    double h2b[] = {ball1.c[0]-hinge.c[0], ball1.c[1]-hinge.c[1],ball1.c[2]-hinge.c[2] };
    normalize(h2b);
    ball1.c[0] = 5*h2b[0]+hinge.c[0];
    ball1.c[1] = 5*h2b[1]+hinge.c[1];
    ball1.c[2] = 5*h2b[2]+hinge.c[2];
    */
  }
  
  private void rayTrace(double v[], double w[], double rgb[]){
    double t = INFINITY; 
    Sphere closest_sphere = null;
    //loop over all spheres
    for(Sphere sphere: sphere_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 = raySphereIntersect(v,w,sphere);
      //System.out.println("tn: "+tn );
      if(tn>0&&tn<t){
        t = tn;
        closest_sphere = sphere;
      }
    }
    if(null!=closest_sphere)
      computeShade(v,w,closest_sphere,t,rgb);
  }

  private void computeShade(
    double v[],
    double w[],
    Sphere sphere,
    double t,
    double rgb[]
  ){
    double point[] = new double[]{ 
      (v[0]+w[0]*t),
      (v[1]+w[1]*t),
      (v[2]+w[2]*t)
    };
    double normal[] = new double[] {
      (point[0]-sphere.c[0])/sphere.r,
      (point[1]-sphere.c[1])/sphere.r,
      (point[2]-sphere.c[2])/sphere.r
    };
    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);
        v = new double[] {
          point[0],
          point[1],
          point[2]
        };
        for(Sphere s : sphere_list)
          if(s!=sphere){
            double tn = raySphereIntersect(v,L,s);
            if(tn< INFINITY&&tn>0){
              useLight[k] = false;
              break;
            }
          }
      }
      
    }
    ambientColor = sphere.ambientColor;
    diffuseColor = sphere.diffuseColor;
    specularColor = sphere.specularColor;
    specularPower= sphere.specularPower;
    phong(normal, rgb);
    v = new double[] {
      point[0] + EPSILON*normal[0],
      point[1] + EPSILON*normal[1],
      point[2] + EPSILON*normal[2]
    };
    double wdn = dot(w,normal);// w dot normal
    w = 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(v,w,rgb);  
  }

  private double raySphereIntersect(double v[], double w[], Sphere sphere){
    //vector vmc = v - c 
    double vmc[] = new double[3];
    for(int i =0;i<vmc.length;i++)
      vmc[i] = v[i] - sphere.c[i];
    double A = dot(w,w);
    double B = 2*dot(vmc,w);
    double C = dot(vmc,vmc)-sphere.r*sphere.r;
    double tn = INFINITY;
    if(B*B-4*A*C>=0)
      tn = (-B-Math.sqrt(B*B-4*A*C))/2*A;
    return tn;
  }
  
  /** 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[]){
    // 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++) {
      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] +=  Math.max(0, Math.min(1.0, color[i]));
      rgb[i] = Math.min(rgb[i],1.0);
    }
  }
  
  
  
  /** 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;
  }

  // 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 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 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];
  }
  
  //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;
}