/*
  Billiards.java
  
  by Yusuke Shinyama, yusuke @ cs dot nyu dot edu
*/

import java.awt.*;
import java.lang.Math;
import java.util.*;


//  BufferedApplet
//
class BufferedApplet extends java.applet.Applet implements Runnable
{
/*
   THIS CLASS HANDLES DOUBLE BUFFERING FOR YOU, SO THAT THE IMAGE
   DOESN'T FLICKER WHILE YOU'RE RENDERING IT.  YOU DON'T REALLY
   NEED TO WORRY ABOUT THIS TOO MUCH, AND YOU'LL PROBABLY NEVER NEED
   TO CHANGE IT.  IT'S REALLY JUST USEFUL LOW LEVEL PLUMBING.
*/

   public void render(Graphics g) { }   // *you* define how to render
   public boolean damage = true;        // you can force a render

   private Image image = null;
   private Graphics buffer = null;
   private Thread t;
   private Rectangle r = new Rectangle(0, 0, 0, 0);

   // A BACKGROUND THREAD CHECKS FOR CHANGES ABOUT 30 TIMES PER SECOND

   public void start() { if (t == null) { t = new Thread(this); t.start(); } }
   public void stop()  { if (t != null) { t.stop(); t = null; } }
   public void run()   { try { while (true) { repaint(); t.sleep(30); } }
                             catch(InterruptedException e){}; }
/*
   UPDATE GETS CALLED BY THE SYSTEM.
   IT CALLS YOUR RENDER METHOD, WHICH DRAWS INTO AN OFF-SCREEN IMAGE.
   THEN UPDATE COPIES THE IMAGE YOU'VE RENDERED ONTO THE APPLET WINDOW.
*/

   public void update(Graphics g) {
      if (r.width != bounds().width || r.height != bounds().height) {
         image = createImage(bounds().width, bounds().height);
         buffer = image.getGraphics();
         r = bounds();
         damage = true;
      }
      render(buffer);
      damage = false;
      if (image != null)
         g.drawImage(image,0,0,this);
   }
}


//  Scene3D
//
class Scene3D {

    Matrix3D matrix;
    Vector children;

    public Scene3D() {
	children = new Vector();
    }

    public void addChild(Scene3D child) {
	children.addElement((Object) child);
    }

    public void removeChild(int index) {
	children.removeElementAt(index);
    }

    public void setMatrix(Matrix3D m) {
	matrix = m;
    }
    
    public void multMatrix(Matrix3D m) {
	matrix.mult(m);
    }
    
    public Matrix3D updateMatrix(Matrix3D base) {
	Matrix3D m = base;
	if (matrix != null) {
	    m =	new Matrix3D(base);
	    m.mult(matrix);
	}
	for (int i = 0; i < children.size(); i++) {
	    ((Scene3D) children.elementAt(i)).updateMatrix(m);
	}
	return m;
    }

    public void draw(Canvas3D canvas) {
	for (int i = 0; i < children.size(); i++) {
	    ((Scene3D) children.elementAt(i)).draw(canvas);
	}	
    }
}


//  Shape3D
//
class Shape3D extends Scene3D {

    Vector pts;
    Vector lines;
    double[][] tmp_pts;

    public Shape3D() {
	super();
	pts = new Vector();
	lines = new Vector();
	tmp_pts = null;
    }

    public int addPoint(double x, double y, double z) {
	double[] p = { x, y, z };
	pts.addElement((Object) p);
	return pts.size()-1;
    }

    public int addLine(int[] l) {
	lines.addElement(l);
	return lines.size()-1;
    }

    public Matrix3D updateMatrix(Matrix3D base) {
	Matrix3D m = super.updateMatrix(base);
	tmp_pts = new double[pts.size()][3];
	for (int i = 0; i < tmp_pts.length; i++) {
	    double[] p = (double[]) pts.elementAt(i);
	    tmp_pts[i][0] = p[0];
	    tmp_pts[i][1] = p[1];
	    tmp_pts[i][2] = p[2];
	    m.apply(tmp_pts[i]);
	}
	return m;
    }

    public void draw(Canvas3D canvas) {
	super.draw(canvas);
	for (int i = 0; i < lines.size(); i++) {
	    int[] pointid = (int[]) lines.elementAt(i);
	    for (int j = 0; j < pointid.length; j++) {
		double x = tmp_pts[pointid[j]][0];
		double y = tmp_pts[pointid[j]][1];
		double z = tmp_pts[pointid[j]][2];
		if (j == 0) {
		    canvas.moveTo(x, y, z);
		} else {
		    canvas.lineTo(x, y, z);
		}
	    }
	}
    }
}


//  Canvas3D
//
class Canvas3D {

    final double zclip = 0.1;

    Graphics g;
    double c;
    int viewportx, viewporty;
    double x0, y0, z0;
    int prevx, prevy;
    float red, blue, green;

    public Canvas3D(int width, int height, double theta) {
	viewportx = width/2;
	viewporty = height/2;
	if (viewporty < viewportx) {
	    c = viewporty / Math.tan(theta);
	} else {
	    c = viewportx / Math.tan(theta);
	}
    }

    public void setGraphics(Graphics g0) {
	g = g0;
    }

    public void setColor(Color c) {
	red = c.getRed() / 256f;
	green = c.getGreen() / 256f;
	blue = c.getBlue() / 256f;
    }

    public void moveTo(double x, double y, double z) {
	x0 = x; y0 = y; z0 = z;
	prevx = -1; prevy = -1;
    }

    public void lineTo(double x1, double y1, double z1) {
	// clipping
	if (z0 <= zclip && z1 <= zclip) {
	    moveTo(x1, y1, z1);
	    return;
	}
	int px0, py0, px1, py1;
	if (z0 < zclip) {
	    // (x0,y0),z0 < zclip < z1
	    double t = (zclip-z0)/(z1-z0);
	    x0 = (1-t)*x0 + t*x1;
	    y0 = (1-t)*y0 + t*y1;
	    z0 = zclip;
	    px0 = (int)(c * x0 / z0) + viewportx;
	    py0 =-(int)(c * y0 / z0) + viewporty;
	    px1 = (int)(c * x1 / z1) + viewportx;
	    py1 =-(int)(c * y1 / z1) + viewporty;
	    prevx = px1; prevy = py1;
	} else if (z1 < zclip) {
	    // (x1,y1),z1 < zclip < z0
	    double t = (zclip-z1)/(z0-z1);
	    x1 = (1-t)*x1 + t*x0;
	    y1 = (1-t)*y1 + t*y0;
	    z1 = zclip;
	    if (prevx != -1) {
		px0 = prevx; py0 = prevy;
	    } else {
		px0 = (int)(c * x0 / z0) + viewportx;
		py0 =-(int)(c * y0 / z0) + viewporty;
	    }
	    px1 = (int)(c * x1 / z1) + viewportx;
	    py1 =-(int)(c * y1 / z1) + viewporty;
	    prevx = -1; prevy = -1;
	} else {
	    if (prevx != -1) {
		px0 = prevx; py0 = prevy;
	    } else {
		px0 = (int)(c * x0 / z0) + viewportx;
		py0 =-(int)(c * y0 / z0) + viewporty;
	    }
	    px1 = (int)(c * x1 / z1) + viewportx;
	    py1 =-(int)(c * y1 / z1) + viewporty;
	    prevx = px1; prevy = py1;
	}

	double r = 5.0-Math.pow(z0+z1,0.5);
	if (1.0 < r) r = 1.0;
	if (r < 0.3) r = 0.3;
	g.setColor(new Color((float)(red*r), (float)(green*r), (float)(blue*r)));
	g.drawLine(px0, py0, px1, py1);
	x0 = x1; y0 = y1; z0 = z1;
    }
}


//  Matrix3D
//
class Matrix3D {

    static final int ROTX = 1, ROTY = 2, ROTZ = 3;

    protected double[][] m;

    private void identity() {
	m = new double[4][4];
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		if (i == j) {
		    m[i][j] = 1.0;
		} else {
		    m[i][j] = 0.0;
		}
	    }
	}
    }

    public Matrix3D() {
	identity();
    }

    public Matrix3D(Matrix3D m0) {
	m = new double[4][4];
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		m[i][j] = m0.m[i][j];
	    }
	}
    }

    public static Matrix3D rotation(int d, double theta) {
	Matrix3D m = new Matrix3D();
	double s = Math.sin(theta);
	double c = Math.cos(theta);
	if (d == ROTX) {
	    m.m[1][1] = c; m.m[1][2] =-s;
	    m.m[2][1] = s; m.m[2][2] = c;
	} else if (d == ROTY) {
	    m.m[0][0] = c; m.m[0][2] = s;
	    m.m[2][0] =-s; m.m[2][2] = c;
	} else if (d == ROTZ) {
	    m.m[0][0] = c; m.m[0][1] =-s;
	    m.m[1][0] = s; m.m[1][1] = c;
	}
	return m;
    }

    public static Matrix3D inverse(Matrix3D m0) {
	Matrix3D m1 = new Matrix3D(m0);
	Matrix3D m = new Matrix3D();
	for (int i = 0; i < 4; i++) {
	    double a = m1.m[i][i];
	    if (a == 0) {
		// swap rows
		int i1 = i+1;
		while (m1.m[i1][i1] == 0) {
		    i1++;
		}
		a = m1.m[i1][i1];
		for (int k = 0; k < 4; k++) {
		    double t = m1.m[i1][k];
		    m1.m[i1][k] = m1.m[i][k];
		    m1.m[i][k] = t;
		    t = m.m[i1][k];
		    m.m[i1][k] = m.m[i][k];
		    m.m[i][k] = t;
		}
	    }
	    for (int k = 0; k < 4; k++) {
		m1.m[i][k] /= a;
		m.m[i][k] /= a;
	    }
	    for (int j = 0; j < 4; j++) {
		if (i != j) {
		    double b = m1.m[j][i];
		    for (int k = 0; k < 4; k++) {
			m1.m[j][k] -= b*m1.m[i][k];
			m.m[j][k] -= b*m.m[i][k];
		    }
		}
	    }
	}
	return m;
    }

    public static Matrix3D translation(double x, double y, double z) {
	Matrix3D m = new Matrix3D();
	m.m[0][3] = x;
	m.m[1][3] = y;
	m.m[2][3] = z;
	return m;
    }

    public void mult(Matrix3D obj) {
	double[][] mtmp = new double[4][4];
	double[][] m1 = obj.m;
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		double x = 0.0;
		for (int k = 0; k < 4; k++) {
		    x += m[i][k] * m1[k][j];
		}
		mtmp[i][j] = x;
	    }
	}
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		m[i][j] = mtmp[i][j];
	    }
	}
    }

    public void apply(double p[]) {
	double x = m[0][0]*p[0] + m[0][1]*p[1] + m[0][2]*p[2] + m[0][3];
	double y = m[1][0]*p[0] + m[1][1]*p[1] + m[1][2]*p[2] + m[1][3];
	double z = m[2][0]*p[0] + m[2][1]*p[1] + m[2][2]*p[2] + m[2][3];
	p[0] = x; p[1] = y; p[2] = z;
    }

    public void debug(String s) {
	System.out.println(s + " = {");
	System.out.println("  { "+m[0][0]+", "+m[0][1]+", "+m[0][2]+" },");
	System.out.println("  { "+m[1][0]+", "+m[1][1]+", "+m[1][2]+" },");
	System.out.println("  { "+m[2][0]+", "+m[2][1]+", "+m[2][2]+" }");
	System.out.println("}");
    }
}


//  Shape Library
//

//  Sphere
class Sphere extends Shape3D {
    public Sphere(double r, int nh, int nv) {
	for (int i = -nv+1; i <= nv-1; i++) {
	    double phi = i*0.5*Math.PI/nv;
	    for (int j = 0; j < nh; j++) {
		double theta = j*2*Math.PI/nh;
		addPoint(r*Math.cos(theta)*Math.cos(phi),
			 r*Math.sin(phi),
			 r*Math.sin(theta)*Math.cos(phi));
	    }
	}
	for (int i = -nv+1, p = 0; i <= nv-1; i++, p+=nh) {
	    int[] l = new int[nh+1];
	    for (int j = 0; j < nh+1; j++) {
		l[j] = (j % nh) + p;
	    }
	    addLine(l);
	}
	int p0 = addPoint(0,-r, 0);
	int p1 = addPoint(0, r, 0);
	for (int i = 0; i < nh; i++) {
	    int[] l = new int[nv*2+1];
	    l[0] = p0;
	    for (int j = 0; j < nv*2; j++) {
		l[j+1] = j*nh + i;
	    }
	    l[nv*2] = p1;
	    addLine(l);
	}
    }
}

// Plane
class Plane extends Shape3D {
    public Plane(double w, double h, int nwidth, int nheight) {
	int p = 0;
	for (int i = -nwidth+1; i <= nwidth-1; i++) {
	    double x = (double)i * w / (double)nwidth;
	    addPoint(x, 0,-h);
	    addPoint(x, 0, h);
	    int[] l = { p, p+1 };
	    p += 2;
	    addLine(l);
	}
	for (int i = -nheight+1; i <= nheight-1; i++) {
	    double z = (double)i * h / (double)nheight;
	    addPoint( w, 0, z);
	    addPoint(-w, 0, z);
	    int[] l = { p, p+1 };
	    p += 2;
	    addLine(l);
	}
	addPoint(-w, 0,-h);
	addPoint(-w, 0, h);
	addPoint( w, 0, h);
	addPoint( w, 0,-h);
	int[] l = { p, p+1, p+2, p+3, p };
	addLine(l);
    }
}

// BouncingBall
class BouncingBall extends Sphere {
    double r, x, z, v, vx, vz, dir, rot, bound;
    boolean bounced;
    Matrix3D mat;
    public BouncingBall(double r, int nh, int nv, double bound) {
	super(r, nh, nv);
	this.r = r;
	this.bound = bound;
	x = (Math.random()-0.5)*2.0*bound;
	z = (Math.random()-0.5)*2.0*bound;
	dir = Math.random()*Math.PI*2.0;
	v = 0.05*bound;
	vx = Math.cos(dir)*v;
	vz = Math.sin(dir)*v;
	rot = 0;
	mat = new Matrix3D();
//	x=0; vx=0; // for test
    }
    public void check(BouncingBall b1) {
	double dx = (x+vx) - (b1.x+b1.vx);
	double dz = (z+vz) - (b1.z+b1.vz);
	double dist = dx*dx+dz*dz;
	bounced = (Math.sqrt(dist) < r+b1.r);
	b1.bounced = bounced;
	if (!bounced) return;
	double a = (vx*dx+vz*dz)/dist;
	double a1 = (b1.vx*dx+b1.vz*dz)/dist;
	vx -= a*dx; vz -= a*dz;
	vx += a1*dx; vz += a1*dz;
	b1.vx -= a1*dx; b1.vz -= a1*dz;
	b1.vx += a*dx; b1.vz += a*dz;
	while (true) {
	    dx = (x+vx) - (b1.x+b1.vx);
	    dz = (z+vz) - (b1.z+b1.vz);
	    dist = dx*dx+dz*dz;
	    if (r+b1.r < Math.sqrt(dist)) break;
	    x += vx; z += vz;
	}
    }
    public void update() {
	if (!bounced) {
	    if (x+vx < -bound) { vx = Math.abs(vx); }
	    else if (bound < x+vx) { vx = -Math.abs(vx); }
	    if (z+vz < -bound) { vz = Math.abs(vz); }
	    else if (bound < z+vz) { vz = -Math.abs(vz); }
	}
	x += vx; z += vz;
	setMatrix(Matrix3D.translation(x, r, z));
	multMatrix(mat);
	mat.mult(Matrix3D.rotation(Matrix3D.ROTX, vz));
	mat.mult(Matrix3D.rotation(Matrix3D.ROTZ, -vx));
    }
}


//  Applet
//
public class Billiards extends BufferedApplet
{
    Canvas3D canvas = null;
    Random rand = new Random();
    Scene3D scene;
    Plane plane;
    Vector balls;
    double i = 0.0;
    double r = 4.0;
    int mode = 0;
    int ballid = 0;

    public static void main(String args[]) {
	Frame f = new Frame("Billiards");
	Billiards me = new Billiards();
	me.init();
	me.start();
	f.add("Center", me);
	f.setSize(600, 600);
	f.show();
    }

    public void resize(int w, int h) {
	super.resize(w, h);
	canvas = null;
    }

    public void reshape(int x, int y, int w, int h) {
	super.reshape(x, y, w, h);
	canvas = null;
    }

    public void addBall1() {
	BouncingBall b1 = new BouncingBall(Math.random()*0.5+0.3, 8, 4, r);
	balls.addElement((Object) b1);
	scene.addChild(b1);
    }
    
    public void removeBall1() {
	if (balls.size() == 0) return;
	int i = 0;
	balls.removeElementAt(i);
	scene.removeChild(i+1);
    }
    
    public void init() {
	super.init();
	scene = new Scene3D();
	requestFocus();
	balls = new Vector();
	plane = new Plane(r, r, 10, 10);
	scene.addChild(plane);
	for(int i=0; i<5; i++) addBall1();
    }
    
    public void render(Graphics g) {
	// clear it
	g.setColor(Color.black);
	g.fillRect(0, 0, bounds().width, bounds().height);

	// get the canvas
	if (canvas == null) {
	    double theta = Math.PI/6.0;
	    if (mode == 2) { theta = Math.PI/4.0; }
	    canvas = new Canvas3D(size().width, size().height, theta);
	}
	canvas.setGraphics(g);
	canvas.setColor(Color.white);

	// move balls.
	for (int i = 0; i < balls.size(); i++) {
	    BouncingBall b1 = (BouncingBall) balls.elementAt(i);
	    for (int j = i+1; j < balls.size(); j++) {
		b1.check((BouncingBall) balls.elementAt(j));
	    }
	}
	for (int i = 0; i < balls.size(); i++) {
	    BouncingBall b1 = (BouncingBall) balls.elementAt(i);
	    b1.update();
	}
	
	// change the view.
	Matrix3D m = null;
	if (mode == 0) {
	    m = Matrix3D.translation(0, 0, 8);
	    m.mult(Matrix3D.rotation(Matrix3D.ROTX, -Math.PI/6.0));
	    m.mult(Matrix3D.rotation(Matrix3D.ROTY, i));
	} else if (mode == 1) {
	    BouncingBall b1 = (BouncingBall) balls.elementAt(ballid);
	    m = Matrix3D.rotation(Matrix3D.ROTY, i*5.0);
	    m.mult(Matrix3D.rotation(Matrix3D.ROTZ, 0.5*Math.sin(i)));
	    m.mult(Matrix3D.translation(-b1.x, -b1.r, -b1.z));
	} else if (mode == 2) {
	    BouncingBall b1 = (BouncingBall) balls.elementAt(ballid);
	    m = Matrix3D.translation(0, 0, 3.0*b1.r);
	    m.mult(Matrix3D.inverse(b1.mat));
	    m.mult(Matrix3D.translation(-b1.x, -b1.r, -b1.z));
	}

	// draw the scene.
	scene.updateMatrix(m);
	scene.draw(canvas);

	// some additional stuff.
	if (mode == 0) {
	    g.setColor(Color.white);
	    g.drawString("Click the screen to feel like a ball...", 10, 20);
	} else if (mode == 1) {
	    g.setColor(Color.white);
	    int x = 10;
	    String s = "Click for";
	    g.drawString(s, x, 20);
	    x += g.getFontMetrics().stringWidth(s);
	    s = " MORE";
	    g.setColor(Color.red);
	    g.drawString(s, x, 20);
	    x += g.getFontMetrics().stringWidth(s);
	    s = " ...";
	    g.setColor(Color.white);
	    g.drawString(s, x, 20);
	} else if (mode == 2) {
	    g.setColor(Color.white);
	    g.drawString("Click to be sane again.", 10, 20);
	}
	
	i += 0.01;
    }

    // handle mouse events.
    public boolean mouseUp(Event e, int x, int y) {
	mode = (mode+1) % 3;
	canvas = null;
	ballid = Math.abs(rand.nextInt()) % balls.size();
	return true;
    }
}