/*
 * Alec Jacobson
 * 
 */
import java.awt.*;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.PriorityQueue;
/**
 *
 * @author ajx
 */



/**
 * Class to hold a character
 *
 */
class Character implements Comparable{
  double x,y,z;//location of character 
  double cam_z;
  double rotZ, rotX, rotY;
  double sx = 1.;
  double sy = 1.;
  double sz = 1.;
  double radius;
  Point velocity;
  LinkedList<Surface> s_list;//list of surfaces associated with this Character
  Matrix4x4 mat;//transformation to entire character
  
  public Character(){
    init();
  }
  
  public void init(){
    //init matrix for machine as whole
    mat = new Matrix4x4();
    mat.identity();
    
    s_list = new LinkedList<Surface>();
    //make individual parts here
  }
  
  /**go through all of the surfaces and update matrices*/
  public void updateMatrices(){

    this.mat.identity();
    this.mat.translate(x,y,z);
    this.mat.rotateZ(rotZ);
    this.mat.rotateX(rotX);
    this.mat.rotateY(rotY);
    this.mat.scale(sx ,sy, sz);
    
    //update matrices of all surfaces
    for(Surface s: s_list)
      s.matrix = mat.getCopy();
  }
  
  public void applyVelocity(double dt){
    x += dt*velocity.x;
    y += dt*velocity.y;
    z += dt*velocity.z;
    
  }
  
  public void addToVelocity(double x, double y, double z){
    velocity.x += x;
    velocity.y += y;
    velocity.z += z;
  }
  
  public void multiplyToVelocity(double x, double y, double z){
    velocity.x *= x;
    velocity.y *= y;
    velocity.z *= z;
  }
  
  public int compareTo(Object o){
    Double t = this.cam_z;
    Double s = ( (Character) o).cam_z;
    int cam = t.compareTo(s);
    if( cam == 0){
      t = this.z;
      s = ( (Character) o).z;
      return t.compareTo(s);
    }
    return cam;
  }
  
}

/**
 * Donut shaped cannon that shoots balls
 * 
 */
class Cannon extends Character{
  final int MAX_SHOTS = 8;
  final long MAX_WAIT = 1*1000/2;
  int don_lat;
  int don_lon;
  double don_rad;
  double mass;
  Color color;//or should each surface have its own color?
  LinkedList<Ball> shots;
  Torus don;
  boolean isLoaded;
  long time0;
  public Cannon(int a, int o, double r){
    don_lat = a;
    don_lon = o;
    don_rad = r;
    radius = r;
    init();
  }
  
  public void init(){
    mat = new Matrix4x4();
    mat.identity();
    rotX -= Math.PI/4;
    
    velocity = new Point(0.0,0.0,0.0);
    
    s_list = new LinkedList<Surface>();
    shots = new LinkedList<Ball>();
    isLoaded = false;
    
    //make individual parts here
    don = new Torus(don_lat, don_lon, 0.25);
    loadBall();
//	s_list.clear();
    s_list.add(don);
//    for(Ball s: shots)
  //    s_list.addAll(s.s_list);
  }
  
  
  public void setColor(Color c){
    color = c;
    for(Surface s: s_list)
      s.color = color;
    setBallColor(c);
  }
  
  
  public void setBallColor(Color c){
    for(Ball s: shots){
      s.color = c;
      s.setColor( color);
    }
  }
  
  private boolean loadBall(){
    if(isLoaded || (System.currentTimeMillis()-time0) < MAX_WAIT)
       return false;
       
    if(!isLoaded){
      /**
       * half resolution
       * reverse lat and lon resolution for spheres
       */
	  Ball shot = new Ball(don_lon/2, don_lat/2, don_rad/4, 0.1);
	  shot.setColor(color);
      shots.add(shot);
	  //if exceeding the max number of live shots then kill last shot
	  if(shots.size()>MAX_SHOTS)
		shots.removeFirst();
      isLoaded = true;
    }
    return true;
  }
  
  public boolean fireBall(){
    if(shots.isEmpty()){
      //no shots to fire
      loadBall();
      return false;
    }
    
    //else there are shots
    Ball last = shots.getLast();
    if(last.isFired){
      loadBall();
      return false;
    }
    
    //else there is a loaded shot
	Matrix4x4 pre = new Matrix4x4();
	pre.identity();
	pre.rotateZ(rotZ);
	pre.rotateX(rotX);
	pre.rotateY(rotY);
	double trans[] = new double[3];
	pre.transform(0,0,don_rad*10.,trans);
	last.addToVelocity(velocity.x+trans[0], velocity.y+trans[1], velocity.z+trans[2]);
	
    last.isFired = true;
    isLoaded = false;
    time0 = System.currentTimeMillis();
    
    return true;
  }
  
  
  /**go through all of the surfaces and update matrices*/
  public void updateMatrices(){
    
    loadBall();
      
    
    this.mat.identity();
    this.mat.translate(x,y,z);
    this.mat.rotateZ(rotZ);
    this.mat.rotateX(rotX);
    this.mat.rotateY(rotY);
    
    //update matrices of all surfaces
    //s_list.clear();
    
    don.matrix = this.mat.getCopy();
    don.matrix.scale(sx*don_rad ,sy*don_rad, sz*don_rad);
//    s_list.add(don);
    
    LinkedList<Ball> dead = new LinkedList<Ball>();
    
    for(Ball s: shots){
      if(!s.isFired){
        Matrix4x4 pre = new Matrix4x4();
        pre.identity();
        pre.rotateZ(rotZ);
		pre.rotateX(rotX);
		pre.rotateY(rotY);
        double trans[] = new double[3];
        pre.transform(0,0,don_rad/2.,trans);
        s.x = x+trans[0];
        s.y = y+trans[1];
        s.z = z+trans[2];
      }else{
        if((s.velocity.norm() < 0.1) && (s.y<1.1*s.radius)){
          dead.add(s);
        }
      }
      s.updateMatrices();
//      s_list.addAll(s.s_list);
    }
    
    for(Ball s: dead)
      shots.remove(s);
  
  }
  
  public void applyVelocity(double dt){
    //for cannon and loaded ball
    x += dt*velocity.x;
    y += dt*velocity.y;
    z += dt*velocity.z;
    
    for(Ball s: shots){
      if(s.isFired){
        s.x += dt*s.velocity.x;
        s.y += dt*s.velocity.y;
        s.z += dt*s.velocity.z;
      }
	  s.rotZ += dt*Math.PI/1*s.velocity.y+dt*Math.PI/1*s.velocity.x;
	  s.rotX += -dt*Math.PI/1*s.velocity.y-dt*Math.PI/1*s.velocity.z;
	  s.rotY += dt*Math.PI/1*s.velocity.z+dt*Math.PI/1*s.velocity.x; 
    }
    
  }
  
  
}








/** 
 * Bouncey Donut
 */
class Donut extends Character{
  int lat;
  int lon;
  double mass;
  Color color;
  public Donut(int a, int o, double r){
    lat = a;
    lon = o;
    radius = r;
    init();
  }
  
  public void init(){
    //init matrix for machine as whole
    mat = new Matrix4x4();
    mat.identity();
    
    //velocity to zero
    velocity = new Point(0.,0.,0.);
    
    s_list = new LinkedList<Surface>();
    //make individual parts here
    s_list.add( new Torus(lat, lon, 0.25));
    
  }
    /**go through all of the surfaces and update matrices*/
  public void updateMatrices(){
    
    
    this.mat.identity();
    this.mat.translate(x,y,z);
    this.mat.scale(sx*radius ,sy*radius, sz*radius);
    this.mat.rotateZ(rotZ);
    this.mat.rotateX(rotX);
    this.mat.rotateY(rotY);
    
    //update matrices of all surfaces
    for(Surface s: s_list)
      s.matrix = mat.getCopy();
  
  }
  
  public void setColor(Color c){
    color = c;
    for(Surface s: s_list)
      s.color = color;
  }
 
  
  public void applyVelocity(double dt){
    x += dt*velocity.x;
    y += dt*velocity.y;
    z += dt*velocity.z;
    
    //fake spin
    rotZ += dt*Math.PI/32*velocity.y+dt*Math.PI/32*velocity.x;
    rotX += -dt*Math.PI/32*velocity.y-dt*Math.PI/32*velocity.z;
    rotY += dt*Math.PI/32*velocity.z+dt*Math.PI/32*velocity.x;
  }
  
}

/**
 *
 */
class Table extends Character{
  Color color;
  public Table(double lr, double wr, double hr, double r){
    sx = lr;
    sy = wr;
    sz = hr;
    radius = r;
    init();
  }

  public void setColor(Color c){
    color = c;
    for(Surface s: s_list)
      s.color = color;
  }
 
 public void init(){
    //init matrix for machine as whole
    mat = new Matrix4x4();
    mat.identity();
    
    //velocity to zero
    velocity = new Point(0.,0.,0.);
    
    s_list = new LinkedList<Surface>();
    //make individual parts here
    s_list.add( new Cube());
    
  }
     /**go through all of the surfaces and update matrices*/
  public void updateMatrices(){
    
    
    this.mat.identity();
    this.mat.translate(x,y,z);
    this.mat.rotateX(rotX);
    this.mat.rotateY(rotY);
    this.mat.rotateZ(rotZ);
    this.mat.scale(sx*radius ,sy*radius, sz*radius);
    
    //update matrices of all surfaces
    for(Surface s: s_list)
      s.matrix = mat.getCopy();
  
  }
 
 
}

/** 
 * Bouncey Ball
 */
class Ball extends Character{
  int lat;
  int lon;
  double mass;
  Color color;
  boolean isFired;
  public Ball(int a, int o, double r, double m){
    lat = a;
    lon = o;
    radius = r;
    mass = m;
    init();
  }
  
  public void init(){
    //init matrix for machine as whole
    isFired = false;
    mat = new Matrix4x4();
    mat.identity();
    
    //velocity to zero
    velocity = new Point(0.,0.,0.);
    
    s_list = new LinkedList<Surface>();
    //make individual parts here
    s_list.add( new Sphere(lat, lon));
    
  }
    /**go through all of the surfaces and update matrices*/
  public void updateMatrices(){
    
    
    this.mat.identity();
    this.mat.translate(x,y,z);
    this.mat.scale(sx*radius ,sy*radius, sz*radius);
    this.mat.rotateZ(rotZ);
    this.mat.rotateX(rotX);
    this.mat.rotateY(rotY);
    
    //update matrices of all surfaces
    for(Surface s: s_list)
      s.matrix = mat.getCopy();
  
  }
  
  public void setColor(Color c){
    color = c;
    for(Surface s: s_list)
      s.color = color;
  }
 
  
  public void applyVelocity(double dt){
    x += dt*velocity.x;
    y += dt*velocity.y;
    z += dt*velocity.z;
    
    //fake spin
    rotZ += dt*Math.PI/32*velocity.y+dt*Math.PI/32*velocity.x;
    rotX += -dt*Math.PI/32*velocity.y-dt*Math.PI/32*velocity.z;
    rotY += dt*Math.PI/32*velocity.z+dt*Math.PI/32*velocity.x;
  }
  
  
  
}



/** class to hold surface info**/
class Surface{
  ArrayList<Point> v_list;//vertex list
  LinkedList<int[]> f_list;//facelist
  Matrix4x4 matrix;
  Color color;
  
  public Surface(){
    v_list = new ArrayList<Point>();
    f_list = new LinkedList<int[]>();
    matrix = new Matrix4x4();
    matrix.identity();//start with identity
    color = Color.WHITE;//just in case color is not later defined
  }
  
  public void addVertex(Point p){
    v_list.add(p);
  }
  
  //assume distinct is all false
  public void addFace(Point[] a){
    boolean[] distinct = new boolean[a.length];//default false
    addFace(a, distinct);
  }

  
  public void addFace(Point[] a, boolean[] distinct){
    int[] face = new int[a.length];
    boolean[] found = new boolean[a.length];
    for(int i = 0; i < v_list.size(); i++){
      for(int j = 0; j < a.length; j++){
        if(!distinct[j]
          &&a[j].equals(v_list.get(i))){
          face[j] = i;
          found[j] = true;
        }
      }
    }
    
    //add all the vertices which didn't already exist
    for( int j = 0; j< a.length;j++){
      if(!found[j]){
        int i = v_list.size();
        v_list.add(a[j]);
        face[j] = i;
      }
    }
    
    f_list.add(face);
  
  }
  
}



class Torus extends Surface{
  public Torus(int lat, int lon, double rat){
    v_list = new ArrayList<Point>();
    f_list = new LinkedList<int[]>();
    matrix = new Matrix4x4();
    matrix.identity();//start with identity
    color = Color.WHITE;//just in case color is not later defined
    make(lat, lon, rat);
  }
  
  private void make(int lat, int lon, double ratio){
    double theta = 2.*Math.PI/(double)lat;//change in angle
    double phi = 2.*Math.PI/(double)lon;
    double r = ratio;
    double R = 1;
    double x = R+r;
    double y = 0;
    double z = Math.sin(Math.PI/lat);
    //make all of the sides
    Point[] prev = new Point[lon];
    Point[] first = new Point[lon];
    for(int j = 0; j<prev.length; j++){
      x = Math.cos( 0*theta)*(R + r*Math.cos(j*phi)); 
      y = Math.sin( 0*theta)*(R + r*Math.cos(j*phi));
      z = r*Math.sin(j*phi);
      prev[j] = new Point(x,y,z);
      first[j] = new Point(x,y,z);
    }
    
    Point[] cur;
    for(int i = 1; i<= lat; i++){
      //make the cur ring
      cur = new Point[lon];
      for(int j = 0; j<lon; j++){
		x = Math.cos( i*theta)*(R + r*Math.cos(j*phi)); 
		y = Math.sin( i*theta)*(R + r*Math.cos(j*phi));
		z = r*Math.sin(j*phi);
        cur[j]  = new Point(x,y,z);
      }
      
      //make sides from prev ring to cur ring
      for(int j=0; j< lon; j++){
        int fj = (j)%lon;
        int fi = (j+1)%lon;
        Point[] side = new Point[4];//really is always 4
        side[0] = prev[fj];
        side[1] = cur[fj];
        side[2] = cur[fi];
        side[3] = prev[fi];
        this.addFace(side);
      }
      prev = cur;
    }
    
    //make sides from last ring to first ring
	/*for(int j=0; j< lon; j++){
	  int fj = (j)%lon;
	  int fi = (j+1)%lon;
	  Point[] side = new Point[4];//really is always 4
	  side[0] = prev[fj];
	  side[1] = first[fj];
	  side[2] = first[fi];
	  side[3] = prev[fi];
	  this.addFace(side);
	}*/
    
    
  }
}


class Sphere extends Surface{
  public Sphere(int lat, int lon){
    v_list = new ArrayList<Point>();
    f_list = new LinkedList<int[]>();
    matrix = new Matrix4x4();
    matrix.identity();//start with identity
    color = Color.WHITE;//just in case color is not later defined
    make(lat, lon);
  }
  
  private void make(int lat, int lon){
    //make top and bottom
    double theta = 2*Math.PI/lon;//change in angle
    double x = 1;
    double y = 0;
    double z = Math.cos(Math.PI/(lat+1));
    double w = Math.sin(Math.PI/(lat+1));
    //make all of the sides
    Point[] prev = new Point[lon];
    for(int j = 0; j<prev.length; j++)
      prev[j] = new Point(0,0,1);
    
    Point[] cur;
    double phi = Math.PI/(lat+1);
    for(int i = 1; i<= (lat+1); i++){
      //make the cur ring
      cur = new Point[lon];
      z = Math.cos(i*Math.PI/(lat+1));
      w = Math.sin(i*Math.PI/(lat+1));
      for(int j = 0; j<lon; j++){
        x = w*Math.cos(j*theta);
        y = w*Math.sin(j*theta);
        cur[j]  = new Point(x,y,z);
      }
      
      //make sides from prev ring to cur ring
      for(int j=0; j< lon; j++){
        int fj = (j)%lon;
        int fi = (j+1)%lon;
        Point[] side = new Point[4];//really is always 4
        side[0] = prev[fj];
        side[1] = cur[fj];
        side[2] = cur[fi];
        side[3] = prev[fi];
        this.addFace(side);
      }
      prev = cur;
    }
    
    
    
    
  }
}


class Cylinder extends Surface{
  public Cylinder(int n){
    v_list = new ArrayList<Point>();
    f_list = new LinkedList<int[]>();
    matrix = new Matrix4x4();
    matrix.identity();//start with identity
    color = Color.WHITE;//just in case color is not later defined
    make(n);
  }
  
  private void make(int n){
    Point[] front = new Point[n];
    Point[] back = new Point[n];
    double theta = 2*Math.PI/n;//change in angle
    double x = 1;
    double y = 0;
    double z = 1;
    //make front and back
    for(int j = 0; j<n; j++){
      x = Math.cos(j*theta);
      y = Math.sin(j*theta);
      front[j]  = new Point(x,y,z);
      //be sure this is going the other way around!!
      x = Math.cos(j*theta);
      y = -Math.sin(j*theta);
      back[j]  = new Point(x,y,-z);
    }
    this.addFace(front);
    this.addFace(back);
    
    //make side panels all around
    for(int j=0; j< n; j++){
      int fj = (j)%n;
      int bj = (n-j)%n;
      int bi = (n-j-1)%n;
      int fi = (j+1)%n;
      
      Point[] side = new Point[4];//really is always 4
      side[0] = front[fj];
      side[1] = back[bj];
      side[2] = back[bi];
      side[3] = front[fi];
      this.addFace(side);
    }
    
  }
}


class Cube extends Surface{
  public Cube(){
    v_list = new ArrayList<Point>();
    f_list = new LinkedList<int[]>();
    matrix = new Matrix4x4();
    matrix.identity();//start with identity
    color = Color.WHITE;//just in case color is not later defined
    make();
  }
  
  private void make(){
    Point[] front = new Point[4];
    Point[] back = new Point[4];
    Point[] top = new Point[4];
    Point[] bottom = new Point[4];
    Point[] left = new Point[4];
    Point[] right = new Point[4];
    
    front[3] = new Point(1,-1,1);
    front[2] = new Point(1,1,1);
    front[1] = new Point(-1,1,1);
    front[0] = new Point(-1,-1,1);
    
    back[0] = new Point(1,-1,-1);
    back[1] = new Point(1,1,-1);
    back[2] = new Point(-1,1,-1);
    back[3] = new Point(-1,-1,-1);
    
    left[3] = new Point(-1,1,1);
    left[2] = new Point(-1,1,-1);
    left[1] = new Point(-1,-1,-1);
    left[0] = new Point(-1,-1,1);
    
    right[0] = new Point(1,1,1);
    right[1] = new Point(1,1,-1);
    right[2] = new Point(1,-1,-1);
    right[3] = new Point(1,-1,1);
    
    bottom[3] = new Point(-1,-1,-1);
    bottom[2] = new Point(1,-1,-1);
    bottom[1] = new Point(1,-1,1);
    bottom[0] = new Point(-1,-1,1);
    
    top[3] = new Point(-1,-1,-1);
    top[2] = new Point(1,-1,-1);
    top[1] = new Point(1,-1,1);
    top[0] = new Point(-1,-1,1);
    
    
    //make front and back
    this.addFace(front);
    this.addFace(back);
    this.addFace(left);
    this.addFace(right);
    this.addFace(top);
    this.addFace(bottom);
    
  }
}




class ZPoly implements Comparable{
  Double z;
  int xpoints[],ypoints[];
  Color color;
  int len;
  boolean facing;
  public ZPoly(int[] x, int[] y, double n, Color c, boolean f){
    xpoints = x;
    ypoints = y;
    len = xpoints.length;
    z = n;
    color = c;
    facing = f;
  }
  
  public int compareTo(Object o){
    return this.z.compareTo(( (ZPoly)o).z);
  }

}



class Point{
  double x, y, z;
  
  public Point(double i, double j, double k){
    x = i;
    y = j;
    z = k;
  }
  public boolean equals(Point p){
     return (this.x==p.x)&&(this.y==p.y)&&(this.z==p.z);
  }

  
  /**return z value of surface normal
   * Uses first 3 values
   */
  public static double normalZ(Point[] f){
    Point p1 = f[0];
    Point p2 = f[1];
    Point p3 = f[2];
    
    //if rect then I can do a little err check and get a true triangle
    if (f.length>3){
	  if(p1.equals(p2)){
		p1 = f[3];
      }else if(p1.equals(p3)){
		p1 = f[3];
      }else if(p2.equals(p3)){
		p3 = f[3];
      }
    }
    
    
    Point a = new Point(p2.x-p1.x,p2.y-p1.y,p2.z-p1.z);
    Point b = new Point(p3.x-p1.x,p3.y-p1.y,p3.z-p1.z);
    
    /* 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)
     */
     
//     double z =  (p2.x - p1.x)*(p3.y-p1.y)-(p3.y-p1.y)*(p3.x-p1.x);

//let's try that again
//(a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1)
     Point cross = new Point(a.y*b.z - a.z*b.y,
       a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x);

     return cross.z;
     
  }
  
  public double norm(){
    return Math.sqrt(x*x+y*y+z*z);
  }
  
}


public class HW05 extends BufferedApplet{

  boolean debug = true;
  boolean label = false;
  boolean wired = true;//show edges...
  boolean trans = false;//transparent? no faces...
  
  int scoreSeq = 0;//either score seq opr laying a round
  boolean rightWon = false;
  int leftWins = 0;
  int rightWins = 0;
  
  int w, h;//bounds of applet
  boolean uninit = true;//start applet as uninitiallezedasd 
  double vec1[] = new double[3];//temporary 3D vector
  double vec2[] = new double[3];//temporary 3D vector
  Matrix4x4 pre;
  double foc  = -1.0;//focal length of pinhole camera
  double scale;//camera scale
  double zoom = 1;//camera
  double rotX = 0;//camera 
  double rotY = 0;//camera 
  double rotZ = 0;//camera 
  Matrix4x4 zoo;
  final double dampening = 0.99;
  final double START_X_OFF = 0.75;
  double res = 0.08;  

  double time0;
  double cur_time;
  Cannon cannon_r;
  Cannon cannon_l;
  Ball puck;
//  Table base;
  Point grav = new Point(0,-.4,0);//gravity force
  
  PriorityQueue<ZPoly> faceQ;//queue of faces
  
  public void initVals(){
    scale = 1;
    
    time0 = System.currentTimeMillis() / 1000.0;
    
    //gravity
    
    //construct characters
//    base = new Table(1.,1.,0.1,1.);
 //   base.setColor(Color.CYAN);
  //  base.y = -1;
   // base.rotX -= Math.PI/4;
   // base.rotY -= Math.PI/4;
    
    cannon_r = new Cannon( (int)(2*res*100),  (int)(res*100), 0.1);
    cannon_r.setColor(Color.BLUE);
    cannon_r.x = START_X_OFF;
    cannon_r.rotZ += Math.PI/8;

    cannon_l = new Cannon( (int)(2*res*100),  (int)(res*100), 0.1);
    cannon_l.setColor(Color.RED);
    cannon_l.x = -START_X_OFF;
    cannon_l.rotZ -= Math.PI/8;
    
    puck = new Ball( (int)(res*100),  (int)(2*res*100), 0.2, 0.11);
    puck.setColor(Color.GREEN);
    puck.y = 0.1;
    puck.addToVelocity(0,1,0);
    puck.rotZ -= Math.PI/8;
    puck.rotX -= Math.PI/8;

  }
  
  public void render(Graphics g) {
    if (true||w == 0) {//true here for resizing appletviewer
      w = bounds().width;
      h = bounds().height;
      if(uninit){
        initVals();
        uninit = false;
      }
    }
    
    
    if(scoreSeq>0){                                                                                                                                                                      
	  int u,v;
	  if(rightWon){
		u = 0;                                                                                                                                                                              
		v = w/2;                                                                                                                                                                            
	  }else{                                                                                                                                                                                
		u = w/2;                                                                                                                                                                            
		v = w;                                                                                                                                                                              
	  }                                                                                                                                                                                     
	  g.setColor(Color.PINK);                                                                                                                                                               
	  g.fillRect(0, 0, w, h);                                                                                                                                                         
	  if(rotX==0&&rotZ==0){                                                                                                                                                          
		g.setColor(Color.ORANGE);                                                                                                                                                              
		g.fillRect(0, 2*h/3, w, h); 
		if(rotY==0){
		g.setColor(Color.CYAN);
		g.fillRect(w/2, 2*h/3, w, h);
		}
      }
      																																													
	  if(scoreSeq%2==0){                                                                                                                                                                    
	   g.setColor(Color.WHITE);                                                                                                                                                             
	   g.fillRect(u, 0, v, h);                                                                                                                                                          
	  }                                                                                                                                                                                     
																																															
	  g.setColor(Color.BLACK);                                                                                                                                                              
	  g.drawString("SCORE: "+rightWins,100,100);                                                                                                                                            
	  g.drawString("SCORE: "+leftWins,w-150,100);                                                                                                                                           
																																															
	  if(wired&&rotX==0&&rotZ==0){
	   g.setColor(Color.BLACK);                                                                                                                                                             
			for(int j=1;j<h-2*h/3;j = j*2+1){                                                                                                                                               
			  g.drawLine(0,j+2*h/3,w,j+2*h/3);                                                                                                                                              
			}                                                                                                                                                                               
	   }                                                                                                                                                                                    
	 scoreSeq--;                                                                                                                                                                            
	 if(scoreSeq==0) initVals();                                                                                                                                                            
	}else{   
      checkForWin();  
	  //clear the screen
	  g.setColor(Color.PINK);
	  g.fillRect(0, 0, w, h);
      if(rotX==0 &&rotZ==0){
		g.setColor(Color.ORANGE);
		g.fillRect(0, 2*h/3, w, h);
		if(rotY==0){
		g.setColor(Color.CYAN);
		g.fillRect(w/2, 2*h/3, w, h);
		}
      }
      
	  if(wired&&rotX==0&&rotZ==0){
	   g.setColor(Color.BLACK);
		for(int j=1;j<h-2*h/3;j = j*2+1){
		  g.drawLine(0,j+2*h/3,w,j+2*h/3);
		}
	  }
    }
	double past_time = cur_time;
	cur_time = System.currentTimeMillis() / 1000.0;
	double cur_step = Math.min(1,cur_time - past_time);
	
	//Make pre camera matrix
	zoo = new Matrix4x4();
	zoo.makeTranslation(0,0,-zoom);
	zoo.rotateX(rotX);
	zoo.rotateY(rotY);
	zoo.rotateZ(rotZ);
      
	
	//update all the physics going on
	update(cur_step);
	
	//update all matrices
	cannon_r.updateMatrices();
	cannon_l.updateMatrices();
	puck.updateMatrices();
	
	
	//draw characters here
	PriorityQueue<Character> charQ = new PriorityQueue<Character>();
//	setCamZ(base);
//	charQ.add(base);
	
	setCamZ(cannon_r);
	charQ.add(cannon_r);
	
	for(Ball s: cannon_r.shots){
	  setCamZ(s);
	  charQ.add(s);
	}
	
	setCamZ(cannon_l);
	charQ.add(cannon_l);
	for(Ball s: cannon_l.shots){
      setCamZ(s);
	  charQ.add(s);
    }
    
	setCamZ(puck);
	charQ.add(puck);

	while(!charQ.isEmpty()){
	 Character ch = charQ.remove();
	 drawCharacter(g, ch);
	}
  
    
    
    animating = true; //set animating to true;
  }
  
  public void setCamZ(Character c){
    double dummy[] = new double[3];
    zoo.transform(c.x,c.y,c.z,dummy);
    c.cam_z = dummy[2];
  }
  
  public void collide(Ball b1, Ball b2){
     Point diff = new Point(b1.x-b2.x,
       b1.y-b2.y, b1.z-b2.z);
     double d = diff.norm();
     if( d < (b1.radius + b2.radius) ){

       Point v1 = b1.velocity;
       Point v2 = b2.velocity;

// Between the comment bars is modified code from
// http://www.plasmaphysics.org.uk/programs/coll3d_cpp.htm
//////////////////////////////////////////////////////////////////


       double distance =b1.radius+b2.radius;
       double x21=b2.x-b1.x;
       double y21=b2.y-b1.y;
       double z21=b2.z-b1.z;
       double m21=b2.mass/b1.mass;
//       System.out.println("m21: "+m21+" b2.mass: "+b2.mass+" b1.mass: "+b1.mass);
       double vx21=v2.x-v1.x;
       double vy21=v2.y-v1.y;
       double vz21=v2.z-v1.z;
             
//     **** calculate relative distance and relative speed ***
       double v=Math.sqrt(vx21*vx21 +vy21*vy21 +vz21*vz21);
       
//     **** return if distance between balls smaller than sum of radii ****
       if (d>distance){
       }else if (v==0){
       }else{
   //     **** shift coordinate system so that ball 1 is at the origin ***
         b2.x=x21;
         b2.y=y21;
         b2.z=z21;
  //     **** boost coordinate system so that ball 2 is resting ***
         v1.x=-vx21;
         v1.y=-vy21;
         v1.z=-vz21;
  //     **** find the polar coordinates of the location of ball 2 ***
         double theta2=Math.acos(b2.z/d);
         double phi2 = 0;
         if (b2.x==0 && b2.y==0) {
           phi2=0;
         } else {
           phi2=Math.atan2(b2.y,b2.x);
         }
         double st=Math.sin(theta2);
         double ct=Math.cos(theta2);
         double sp=Math.sin(phi2);
         double cp=Math.cos(phi2);
  
  //     **** express the velocity vector of ball 1 in a rotated coordinate
  //          system where ball 2 lies on the z-axis ******
         double v1xr=ct*cp*v1.x+ct*sp*v1.y-st*v1.z;
         double v1yr=cp*v1.y-sp*v1.x;
         double v1zr=st*cp*v1.x+st*sp*v1.y+ct*v1.z;
         double thetav=Math.acos(v1zr/v);
         
         double phiv = 0;
         if (v1xr==0 && v1yr==0) {
           phiv=0;
         } else {
           phiv=Math.atan2(v1yr,v1xr);
         }
  
                                  
  //     **** calculate the normalized impact parameter ***
         double dr=d*Math.sin(thetav)/distance;
  
         
  //     **** calculate impact angles if balls do collide ***
         double alpha=Math.asin(-dr);
         double beta=phiv;
         double sbeta=Math.sin(beta);
         double cbeta=Math.cos(beta);
          
         
  //     **** calculate time to collision ***
         double t=(d*Math.cos(thetav) -distance*Math.sqrt(1-dr*dr))/v;
  
       
  //     **** update positions and reverse the coordinate shift ***
         b2.x=b2.x+v2.x*t +b1.x;
         b2.y=b2.y+v2.y*t +b1.y;
         b2.z=b2.z+v2.z*t +b1.z;
         b1.x=(v1.x+v2.x)*t +b1.x;
         b1.y=(v1.y+v2.y)*t +b1.y;
         b1.z=(v1.z+v2.z)*t +b1.z;
          
   
         
  //  ***  update velocities ***
  
         double a=Math.tan(thetav+alpha);
  
//         double dv2z=1*(v1zr+a*(cbeta*v1xr+sbeta*v1yr))/((1+a*a)*(1+m21));
         double dv2z=1*(v1zr+a*(cbeta*v1xr+sbeta*v1yr))/((1+a*a)*(1+m21));
         
         double v2zr=dv2z;
         double v2xr=a*cbeta*dv2z;
         double v2yr=a*sbeta*dv2z;
         v1zr=v1zr-m21*v2zr;
         v1xr=v1xr-m21*v2xr;
         v1yr=v1yr-m21*v2yr;
  
         
  //     **** rotate the velocity vectors back and add the initial velocity
  //           vector of ball 2 to retrieve the original coordinate system ****
                       
         v1.x=ct*cp*v1xr-sp*v1yr+st*cp*v1zr +v2.x;
         v1.y=ct*sp*v1xr+cp*v1yr+st*sp*v1zr +v2.y;
         v1.z=ct*v1zr-st*v1xr               +v2.z;
         v2.x=ct*cp*v2xr-sp*v2yr+st*cp*v2zr +v2.x;
         v2.y=ct*sp*v2xr+cp*v2yr+st*sp*v2zr +v2.y;
         v2.z=ct*v2zr-st*v2xr               +v2.z;
       }
 
 ////////////////////////////////////////////////////////////////
       
       
       if(b1.mass == b2.mass){
         cannon_l.shots.remove(b1);
         cannon_r.shots.remove(b1);
         cannon_l.shots.remove(b2);
         cannon_r.shots.remove(b2);
       }else if(b1.mass < b2.mass){
         cannon_r.shots.remove(b1);
         cannon_l.shots.remove(b1);
       }else{
         cannon_r.shots.remove(b2);
         cannon_l.shots.remove(b2);
       }
         
       
       
       
     }
  
  }
  
  public void checkForWin(){
    if (Math.abs(puck.x)>START_X_OFF){
       scoreSeq = 10;
       rightWon = ( puck.x<0 );
       if(rightWon) leftWins++;                                                                                                                                                                 
       else rightWins++;
    }    
  }
  
  /**update all the physics*/
  public void update(double dt){
    cannon_r.applyVelocity(dt);
    cannon_l.applyVelocity(dt);
    puck.applyVelocity(dt);
    
    LinkedList<Ball> list = new LinkedList<Ball>();
    
    for(Ball s: cannon_r.shots){
       if(s.isFired){
         list.add(s);
       }
    }
    for(Ball s: cannon_l.shots){
       if(s.isFired){
         list.add(s);
       }
    }
    
    list.add(puck);
    
    for(Ball b1: list){
      for(Ball b2: list){
        if(b1!=b2)
          collide(b1,b2);
      }
    }
    updateCannon(cannon_r, dt);
    updateCannon(cannon_l, dt);
    updateChar(puck,dt);
  }
  
  public void updateCannon(Cannon b, double dt){
    updateChar(b, dt);
    for(Ball s: b.shots){
      if (s.isFired){
        updateChar(s, dt);
      }
    }
  }
  
  public void updateChar(Character b, double dt){
    if(b.y>b.radius){
      b.addToVelocity(dt*grav.x,dt*grav.y,dt*grav.z);
    }else{
      b.y = b.radius;

      b.multiplyToVelocity(1,-1,1);
      b.multiplyToVelocity(dampening,dampening,dampening);
      if(b.y>0) 
        b.addToVelocity(dt*grav.x,dt*grav.y,dt*grav.z);
    }
//    System.out.println("p = <"+cannon_r.x+","+cannon_r.y+","+cannon_r.z+">");
//    System.out.println("v = <"+cannon_r.velocity.x+","+cannon_r.velocity.y+","+cannon_r.velocity.z+">");
//    System.out.println("dt = "+dt);
  }
  
  /**iterate over the surfaces in machine, drawing each one**/
  public void drawCharacter(Graphics g, Character c){
    for(Surface s: c.s_list)
        placeSurface(g, s);
  }
  
  
  /**Method to draw a surface in the 3D space*/
  public void placeSurface(Graphics g, Surface s){
	//get matrix for surface
	Matrix4x4 mat = s.matrix;
	faceQ = new PriorityQueue<ZPoly>();
 
	//sort the faces based on proximity to camera
	for(int[] face: s.f_list){
	   Point[] f = new Point[face.length];
	   for(int j =0; j<face.length;j++){
		 f[j] = s.v_list.get(face[j]);
	   }
	   drawFace(g, f, s.matrix, s.color);
	 }
	 
	 Color old = g.getColor();
	 while(!faceQ.isEmpty()){
	   ZPoly p = faceQ.remove();
	   //actually draw the polygon
	   g.setColor(p.color);
	   if(!trans&&p.facing) g.fillPolygon(p.xpoints,p.ypoints,p.len);    
	   g.setColor(Color.BLACK);
	   if((wired&&p.facing)||
		  (wired&&trans)) g.drawPolygon(p.xpoints,p.ypoints,p.len);
	 }
	 g.setColor(old);
  }
  
 
  
  /**Method to draw a face in the 3D space*/
  public void drawFace(Graphics g, Point[] face, Matrix4x4 mat, Color c){
    boolean visible = true;//assume face is in view
    int len = face.length;
    Point[] transformed = new Point[face.length];
    int[] xpoints = new int[len];
    int[] ypoints = new int[len];
    double max_z = 0;
    for(int j =0; j<face.length; j++){
      Point p = face[j];
      Matrix4x4 m = mat.getCopy();

      m.preMultiply(zoo);
      
      m.transform(p.x, p.y, p.z, vec1);

      visible  = visible && (vec1[2] < -foc);
      String text = "("+(int)vec1[0]+","+(int)vec1[1]+","+(int)vec1[2]+")";
      
      vec1[0] = foc * vec1[0] / (vec1[2]+foc) ;
      vec1[1] = foc * vec1[1] / (vec1[2] +foc) ;
      vec1[2] = 1 / (vec1[2] +foc) ;

      max_z += Math.abs(vec1[2]);

//      camera.transform(vec1[0],vec1[1],vec1[2], vec2);    
      
      vec2[0] = (int)(w/2 + h * vec1[0]);
      vec2[1] = (int)(2*h/3 - h * vec1[1]);
      vec2[2] = (int)vec2[2];

      xpoints[j] = (int)vec2[0];
      ypoints[j] = (int)vec2[1];
      
      transformed[j] = new Point(vec2[0],vec2[1],vec2[2]);
      
      if (label) g.drawString(text,(int)vec2[0],(int)vec2[1]);
      
    }
    boolean facing = ( Point.normalZ(transformed) > 0);
    
    
    if(visible){
      //actually draw the polygon
      if(!facing) c = Color.BLACK;
      faceQ.add(new ZPoly(xpoints, ypoints, max_z/len, c, facing));
    }
  }
  
  
  public boolean mouseUp(Event e, int x, int y) {
    damage = true;
    return true;
  }
  
  public boolean mouseDrag(Event e, int x, int y) {
//    mach.x = (((double) x)-w/2)/scale;
//    mach.y = (((double) y)-h/2)/scale;
    damage = true;
    return true;
  }  
  public boolean keyUp(Event e, int key) {
    switch (key) {
    
      //RIGHT CONTROLLERS        
      case Event.LEFT:
      case '4':
        cannon_r.rotZ += Math.PI/16;
        break;
      case Event.RIGHT:
      case '6':
        cannon_r.rotZ -= Math.PI/16;
           break;
      case Event.UP:
      case '8':
        cannon_r.addToVelocity(0,0,-.2);
           break;
      case Event.DOWN:
      case '5':
      case '2':
        cannon_r.addToVelocity(0,0,.2);
           break;
      case Event.ENTER:
        cannon_r.addToVelocity(0,.3,0);
//        cannon_r.y -= 0.1;
        break;
      case '0':
        cannon_r.fireBall();
        break;
        
      //LEFT CONTROLLERS        
      case 's':
        cannon_l.rotZ += Math.PI/16;
        break;
      case 'f':
        cannon_l.rotZ -= Math.PI/16;
           break;
      case 'e':
        cannon_l.addToVelocity(0,0,-.2);
           break;
      case 'd':
        cannon_l.addToVelocity(0,0,.2);
           break;
      case 'a':
        cannon_l.addToVelocity(0,.3,0);
//        cannon_r.y -= 0.1;
        break;
      case ' ':
        cannon_l.fireBall();
        break;       
//GAME CONTROLLERS        
      case 'r':
      case 'R':
        leftWins = 0;
        rightWins = 0;
        zoom = 1;
        rotX = 0;
        rotY = 0;
        rotZ = 0;
        initVals();
        break;
      case 'g':
        grav = new Point(grav.x/2, grav.y/2, grav.z/2);
        break;
      case 'G':
        grav = new Point(grav.x*2, grav.y*2, grav.z*2);
        break;
//DISPLAY CONTROLLERS        
      case '+':
      case '=':
        res = res*1.5;
        if(res>0.5) res=0.5;
        initVals();
        break;
      case '_':
      case '-':
        res = res/1.5;
        if(res<0.02) res=0.02    ;
        initVals();
        break;
      case 'l':
      case 'L':
        label  = !label;
        break;
      case 'w':
      case 'W':
        wired  = !wired;
        break;
      case 't':
      case 'T':
        trans  = !trans;
        break;
      case Event.END:
        puck.velocity = new Point(0,0,0);
        puck.y = 0;
        break;
      case Event.PGDN:
        zoom += .5;
        break;
      case Event.PGUP:
        zoom -= 1.0;
           break;
      case '<':
        rotX += Math.PI/16;
           break;
      case ',':
        rotX -= Math.PI/16;
           break;
      case '>':
        rotY += Math.PI/16;
           break;
      case '.':
        rotY -= Math.PI/16;
           break;
      case '?':
        rotZ += Math.PI/16;
           break;
      case '/':
        rotZ -= Math.PI/16;
           break;

    }
    damage = true;
    return true;
  }
}