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

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

import java.applet.*;
import java.awt.*;
import java.awt.image.*;


// JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.

final class ImprovedNoise {
   static public double noise(double x, double y, double z) {
      int X = (int)Math.floor(x) & 255,                  // FIND UNIT CUBE THAT
          Y = (int)Math.floor(y) & 255,                  // CONTAINS POINT.
          Z = (int)Math.floor(z) & 255;
      x -= Math.floor(x);                                // FIND RELATIVE X,Y,Z
      y -= Math.floor(y);                                // OF POINT IN CUBE.
      z -= Math.floor(z);
      double u = fade(x),                                // COMPUTE FADE CURVES
             v = fade(y),                                // FOR EACH OF X,Y,Z.
             w = fade(z);
      int A = p[X  ]+Y, AA = p[A]+Z, AB = p[A+1]+Z,      // HASH COORDINATES OF
          B = p[X+1]+Y, BA = p[B]+Z, BB = p[B+1]+Z;      // THE 8 CUBE CORNERS,

      return lerp(w, lerp(v, lerp(u, grad(p[AA  ], x  , y  , z   ),  // AND ADD
                                     grad(p[BA  ], x-1, y  , z   )), // BLENDED
                             lerp(u, grad(p[AB  ], x  , y-1, z   ),  // RESULTS
                                     grad(p[BB  ], x-1, y-1, z   ))),// FROM  8
                     lerp(v, lerp(u, grad(p[AA+1], x  , y  , z-1 ),  // CORNERS
                                     grad(p[BA+1], x-1, y  , z-1 )), // OF CUBE
                             lerp(u, grad(p[AB+1], x  , y-1, z-1 ),
                                     grad(p[BB+1], x-1, y-1, z-1 ))));
   }
   static double fade(double t) { return t * t * t * (t * (t * 6 - 15) + 10); }
   static double lerp(double t, double a, double b) { return a + t * (b - a); }
   static double grad(int hash, double x, double y, double z) {
      int h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
      double u = h<8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
             v = h<4 ? y : h==12||h==14 ? x : z;
      return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
   }
   static final int p[] = new int[512], permutation[] = { 151,160,137,91,90,15,
   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
   };
   static { for (int i=0; i < 256 ; i++) p[256+i] = p[i] = permutation[i]; }
}


// MISApplet (Modified)

/*
   This is the support code that implements a frame buffer in a Java Applet,
   by using a Memory Image Source.

   You can probably use this class without ever needing to change it.
*/

class MISApplet extends Applet implements Runnable {

    final int SKIP = 4;
    final int NSAMPLES = 2;
    final int LINESKIP = 4;
    public int W, H;
    public boolean inited = false;
    public boolean need_rendered = false;

    // PRIVATE DATA

    private int[] pix;              // THE FRAME BUFFER ARRAY
    private int[] samp;		// the number of samplings
    private MemoryImageSource mis;  // MEMORY IMAGE SOURCE CONTAINING FRAME BUFFER
    private Image im;               // IMAGE CONTAINING THE MEMORY IMAGE SOURCE
    private double startTime;       // CLOCK TIME THAT THE APPLET STARTED

    // YOUR APPLET CAN OVERRIDE THE FOLLOWING TWO METHODS:
    public void initFrame() { }            // INITIALIZE EACH FRAME
    public void setPixel(double x, double y, double rgb[]) { } // SET COLOR AT EACH PIXEL
    public void postProcess(Graphics g) { } // post process

    // INITIALIZE THINGS WHEN APPLET STARTS UP

    public void init() {
	super.init();
        setLayout(new BorderLayout());
    }
    
    public void init_finished() {
	(new Thread(this)).start();
	inited = true;
    }

    private int W1 = -1, H1 = -1;
    private boolean need_image_created = false;
    public void initImage() {
	if (W1 == W && H1 == H) return;
	W = W1; H = H1;
//	System.out.println("initImage:"+W+","+H);
        pix = new int[W*H];         // ALLOCATE A FRAME BUFFER IMAGE
        samp = new int[W*H];         // ALLOCATE A FRAME BUFFER IMAGE
        mis = new MemoryImageSource(W, H, pix, 0, W);
        mis.setAnimated(true);
        im = createImage(mis);      // MAKE MEMORY IMAGE SOURCE FOR FRAME BUFFER
    }
    public void resized(int w, int h) {
	W1 = w; H1 = h;
	need_rendered = true;
    }
    public void resize(int w, int h) {
//	System.out.println("resize!");
	super.resize(w, h);
	resized(w, h);
    }
    public void reshape(int x, int y, int w, int h) {
//	System.out.println("reshape!");
	super.reshape(x, y, w, h);
	resized(w, h);
    }
    
    public void render() {
//	System.out.println("render!");
	if (!inited) return;
	need_rendered = false;
	repaint();
	need_rendered = true;
    }

    public void run() {
	while(true) {
	    if (need_rendered) {
		initImage();

//		System.out.println("render start");
		initFrame();
		int i = 0;
		double rgb[] = new double[3];
		// CLEAR
		for(i = 0; i < W*H; i++) {
		    samp[i] = 0;
		}
		i = 0;
		int curline = 0;
		for(int y0 = 0; y0 < H*NSAMPLES; y0++) {
		    for(int x0 = 0; x0 < W*NSAMPLES; x0++) { // COMPUTE COLOR FOR EACH PIXEL
			i = (y0/NSAMPLES)*W+x0/NSAMPLES;
			double x = (double)x0/NSAMPLES;
			double y = (double)y0/NSAMPLES;
			setPixel(x, y, rgb);
			int samp1 = samp[i];
			int r = (((pix[i] >> 16) & 255)*samp1 +
				 (int)(255*Math.max(0.0, Math.min(1.0, rgb[0])))) / (samp1+1);
			int g = (((pix[i] >>  8) & 255)*samp1 +
				 (int)(255*Math.max(0.0, Math.min(1.0, rgb[1])))) / (samp1+1);
			int b = (((pix[i] >>  0) & 255)*samp1 + 
				 (int)(255*Math.max(0.0, Math.min(1.0, rgb[2])))) / (samp1+1);
			//Prin.t.f("hoge: %f, ",rgb[0]).f("%f, ",rgb[1]).f("%f: ",rgb[2]).f("%d,",r).f("%d,",g).f("%d",b).f();
			pix[i] = (255<<24) | (r<<16) | (g<<8) | b;
			samp[i]++;
		    }
		    if (curline+LINESKIP <= y0/NSAMPLES) {
			mis.newPixels(0, curline, W, LINESKIP, true);
			curline += LINESKIP;
			repaint();
		    }
		}
//		System.out.println("render end");
		mis.newPixels(0, curline, W, LINESKIP, true);
		need_rendered = false;
		repaint();
	    } else {
		try {
		    Thread.sleep(120);
		} catch(InterruptedException ie) {}
	    }
	}
    }

    // UPDATE DISPLAY AT EACH FRAME, BY DRAWING FROM MEMORY IMAGE SOURCE

    public void paint(Graphics g) {
//	System.out.println("update!");
	if (im == null) return;
	g.drawImage(im, 0, 0, null);
	if (need_rendered) {
	    status(g, "Rendering...");
	} else {
	    postProcess(g);
	}
    }

    public void status(Graphics g, String s) {
	g.setColor(Color.black);
	g.drawString(s, 10+1, 20+1);
	g.setColor(Color.white);
	g.drawString(s, 10, 20);
    }

    public void update(Graphics g) {
	paint(g);
    }
}


//  Utilities
//
class Util {
    static Random rand = new Random();
    static double norm(double x, double y, double z) {
	return Math.sqrt(x*x + y*y + z*z);
    }
    static double norm(double p[]) {
	return Math.sqrt(product(p, p));
    }
    static double product(double p1[], double p2[]) {
	return p1[0]*p2[0] + p1[1]*p2[1] + p1[2]*p2[2];
    }
    static void scale(double n, double p[]) {
	p[0] *= n;
	p[1] *= n;
	p[2] *= n;
    }
    static void normalize(double p[]) {
	scale(1.0/norm(p), p);
    }
    static int randint(int n) {
	return Math.abs(rand.nextInt()) % n;
    }
}

// printf
class Prin {
    static public Prin t = new Prin();
    public Prin f() {
	System.out.println();
	return this;
    }
    public Prin f(Object s) {
	System.out.print(s);
	return this;
    }
    public Prin f(int x) {
	System.out.print(x);
	return this;
    }
    public Prin f(String s, int x) {
	int i = s.indexOf("%d");
	System.out.print(s.substring(0, i)+Integer.toString(x)+s.substring(i+2));
	return this;
    }
    public Prin f(double x) {
	System.out.print(x);
	return this;
    }
    public Prin f(String s, double x) {
	int i = s.indexOf("%f");
	System.out.print(s.substring(0, i)+Double.toString(Math.round(x*1000.0)/1000.0)+s.substring(i+2));
	return this;
    }
    public Prin f(double x, int t) {
	String s = Double.toString(x);
	int i = s.indexOf('.');
	if (i != -1 && i+t <= s.length()) {
	    s = s.substring(0, i+t);
	}
	System.out.print(s);
	return this;
    }
}


//  Matrix
//
class Matrix {

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

    private double[][] m;
    private Matrix() {
	m = new double[4][4];
    }

    public static Matrix i() {
	Matrix m = new Matrix();
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		if (i == j) {
		    m.m[i][j] = 1.0;
		} else {
		    m.m[i][j] = 0.0;
		}
	    }
	}
	return m;
    }

    public static Matrix dup(Matrix m0) {
	Matrix m = new Matrix();
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		m.m[i][j] = m0.m[i][j];
	    }
	}
	return m;
    }

    public static Matrix rotation_primitive(int d, double c, double s) {
	Matrix m = Matrix.i();
	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 Matrix rotation(int d, double theta) {
	return Matrix.rotation_primitive(d, Math.cos(theta), Math.sin(theta));
    }
    public static Matrix rotation_xy(int d, double x, double y) {
	double l = Math.sqrt(x*x+y*y);
	return Matrix.rotation_primitive(d, x/l, y/l);
    }
    public static Matrix rotation_X(double theta) {
	return Matrix.rotation(ROTX, theta);
    }
    public static Matrix rotation_Y(double theta) {
	return Matrix.rotation(ROTY, theta);
    }
    public static Matrix rotation_Z(double theta) {
	return Matrix.rotation(ROTZ, theta);
    }

    public static Matrix orthogonal(Matrix m0) {
	Matrix m1 = Matrix.i();
	m1.m[0][3] = m0.m[0][3];
	m1.m[1][3] = m0.m[1][3];
	m1.m[2][3] = m0.m[2][3];
	return m1;
    }
    public static Matrix origin(Matrix m0) {
	Matrix m1 = Matrix.dup(m0);
	m1.m[0][3] = 0;
	m1.m[1][3] = 0;
	m1.m[2][3] = 0;
	return m1;
    }

    public static Matrix inverse(Matrix m0) {
	Matrix m1 = Matrix.dup(m0);
	Matrix m = Matrix.i();
	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 Matrix translation(double x, double y, double z) {
	Matrix m = Matrix.i();
	m.m[0][3] = x;
	m.m[1][3] = y;
	m.m[2][3] = z;
	return m;
    }

    public Matrix mult(Matrix 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];
	    }
	}
	return this;
    }

    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 apply_rotation(double p[]) {
	double x = m[0][0]*p[0] + m[0][1]*p[1] + m[0][2]*p[2];
	double y = m[1][0]*p[0] + m[1][1]*p[1] + m[1][2]*p[2];
	double z = m[2][0]*p[0] + m[2][1]*p[1] + m[2][2]*p[2];
	p[0] = x; p[1] = y; p[2] = z;
    }

    public void apply_translation(double p[]) {
	p[0] += m[0][3]; p[1] += m[1][3]; p[2] += m[2][3];
    }

    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("}");
    }
}


//  SegmentSet
//
class EndPoint {
    double t;
    boolean positive;		// true: +1, false: -1
    boolean positive0;		// true: +1, false: -1
    Object data;
    public EndPoint(double t, boolean positive, Object data) {
	this.t = t;
	this.positive = positive; 
	this.positive0 = positive; 
	this.data = data;
    }
    public void neg() { 
	positive = !positive; 
    }
    public boolean isneg() {
	return positive != positive0;
    }
    public void debug() {
 	Prin.t.f(this.positive? "+" : "-").f(":%f", t);
    }
}

class SegmentSet {
    Vector pts;
    boolean filled;

    public SegmentSet() {
	pts = new Vector();
	filled = false;
    }
    
    public SegmentSet(SegmentSet ss) {
	pts = new Vector();
	filled = false;
	for(int i = 0; i < ss.pts.size(); i++) {
	    pts.addElement(ss.pts.elementAt(i));
	}
    }

    public SegmentSet(double t, boolean positive, Object data) {
	pts = new Vector();
	filled = false;
	pts.addElement(new EndPoint(t, positive, data));
    }
    
    public SegmentSet(double t0, double t1, boolean positive, Object data) {
	pts = new Vector();
	filled = false;
	pts.addElement(new EndPoint(t0, positive, data));
	pts.addElement(new EndPoint(t1, !positive, data));
    }

    public void debug() {
	for(int i = 0; i < pts.size(); i++) {
	    if (0 < i) Prin.t.f(" ");
	    ((EndPoint) pts.elementAt(i)).debug();
	}
	if (filled) Prin.t.f("(FILLED)");
    }
    public void debug(String s) {
	Prin.t.f(s);
	debug();
	Prin.t.f();
    }

    public EndPoint find(double t) {
	for(int i = 0; i < pts.size(); i++) {
	    EndPoint p = (EndPoint)pts.elementAt(i);
	    if (t <= p.t) return p;
	}
	return null;
    }

    public static SegmentSet neg(SegmentSet ss) {
	SegmentSet snew = new SegmentSet(ss);
	if (snew.pts.size() == 0) {
	    snew.filled = !ss.filled;
	} else {
	    for(int i = 0; i < snew.pts.size(); i++) {
		((EndPoint) snew.pts.elementAt(i)).neg();
	    }
	    snew.filled = false;
	}
	return snew;
    }

    public static SegmentSet union(SegmentSet s1, SegmentSet s2) {
	if (s1.filled) return s1;
	if (s2.filled) return s2;
	if (s1.pts.size() == 0) return s2;
	if (s2.pts.size() == 0) return s1;
	SegmentSet snew = new SegmentSet();
	int i = 0, j = 0, x = 0;
	if (!((EndPoint)s1.pts.elementAt(0)).positive) x++;
	if (!((EndPoint)s2.pts.elementAt(0)).positive) x++;
	while (i < s1.pts.size() || j < s2.pts.size()) {
	    EndPoint p;	// p: smaller one
	    if (s1.pts.size() <= i) {
		p = (EndPoint) s2.pts.elementAt(j++);
	    } else if (s2.pts.size() <= j) {
		p = (EndPoint) s1.pts.elementAt(i++);
	    } else {
		EndPoint p1 = (EndPoint) s1.pts.elementAt(i);
		EndPoint p2 = (EndPoint) s2.pts.elementAt(j);
		if (p1.t < p2.t) {
		    p = p1; i++;
		} else {
		    p = p2; j++;
		}
	    }
	    if ((p.positive && x == 0) || (!p.positive && x == 1)) {
		snew.pts.addElement(p);
	    }
	    if (p.positive) x++; else x--;
	}
	if (snew.pts.size() == 0) {
	    snew.filled = true;
	}
	return snew;
    }

    public static SegmentSet intersection(SegmentSet s1, SegmentSet s2) {
	return neg(union(neg(s1), neg(s2)));
    }

}


//  SceneNode
//
abstract class SceneNode {

    int mode;
    static final int POS = 0;
    static final int NEG = 1;

    Matrix matrix = null;
    Matrix accumulated = null;
    Matrix accu_inv = null;

    static final double EPSILON = 0.00001;

    public SceneNode(int mode) {
	this.mode = mode;
    }

    public void setMatrix(Matrix m) {
	matrix = m;
    }
    
    public void multMatrix(Matrix m) {
	if (matrix == null) {
	    setMatrix(m);
	} else {
	    matrix.mult(m);
	}
    }
    
    public void updateMatrix(Matrix base) {
	accumulated = base;
	if (matrix != null) {
	    accumulated = Matrix.dup(base);
	    accumulated.mult(matrix);
	}
	accu_inv = Matrix.inverse(accumulated);
    }

    public EndPoint isHitRay(double p0[], double v0[]) {
	SegmentSet segs = hitRay(p0, v0);
	return segs.find(+EPSILON);
    }

    // returns true if shadow
    public boolean calcPixel(int nest, Background bg, Vector lights,
			     double p0[], double v0[], boolean influx, double rgb[]) {
	if (nest <= 0) return false;
	Util.normalize(v0);
	EndPoint p1 = isHitRay(p0, v0);
	if (p1 == null) {
	    bg.hit(v0, rgb);
	    return false;
	}
	Shape s1 = (Shape) p1.data;
	double p[] = new double[3];
	double n[] = new double[3];
	s1.getPoint(p, p1.t);
	s1.getNormal(n, p1.t);
	if (p1.isneg()) {
	    Util.scale(-1, n);
	}
	return s1.material.hit(nest-1, this, bg, lights, p, v0, n, influx, p1.t, rgb);
    }

    abstract public SegmentSet hitRay(double p[], double v[]);
}


//  Material
//
class Material {
    double red, green, blue;
    double amb_red, amb_green, amb_blue;

    public Material(Color col, Color amb) {
	red = col.getRed() / 255.0;
	green = col.getGreen() / 255.0;
	blue = col.getBlue() / 255.0;
	amb_red = amb.getRed() / 255.0;
	amb_green = amb.getGreen() / 255.0;
	amb_blue = amb.getBlue() / 255.0;
    }

    public boolean hit(int nest, SceneNode root, Background bg, Vector lights,
		    double p[], double v[], double n[], boolean influx, double dist,
		    double rgb[]) {
	for(int i = 0; i < lights.size(); i++) {
	    Light light1 = (Light) lights.elementAt(i);
	    double lcolor[] = { red, green, blue };
	    if (light1.lit(nest, root, bg, lights, p, n, lcolor)) {
		rgb[0] += lcolor[0];
		rgb[1] += lcolor[1];
		rgb[2] += lcolor[2];
	    }
	}
	rgb[0] += amb_red;
	rgb[1] += amb_green;
	rgb[2] += amb_blue;
	return true;
    }
}
class CheckMaterial extends Material {
    double alt_red, alt_green, alt_blue;
    double r;
    
    public CheckMaterial(Color col, Color amb, Color alt, double r) {
	super(col, amb);
	alt_red = alt.getRed() / 255.0;
	alt_green = alt.getGreen() / 255.0;
	alt_blue = alt.getBlue() / 255.0;
	this.r = r;
    }
    
    public boolean hit(int nest, SceneNode root, Background bg, Vector lights,
		    double p[], double v[], double n[], boolean influx, double dist,
		    double rgb[]) {
	for(int i = 0; i < lights.size(); i++) {
	    Light light1 = (Light) lights.elementAt(i);
	    double lcolor[] = { red, green, blue };
	    if (Math.sin(r*p[0]) * Math.sin(r*p[1]) * Math.sin(r*p[2]) < 0) {
		lcolor[0] = alt_red;
		lcolor[1] = alt_green;
		lcolor[2] = alt_blue;
	    }
	    if (light1.lit(nest, root, bg, lights, p, n, lcolor)) {
		rgb[0] += lcolor[0];
		rgb[1] += lcolor[1];
		rgb[2] += lcolor[2];
	    }
	}
	rgb[0] += amb_red;
	rgb[1] += amb_green;
	rgb[2] += amb_blue;
	return true;
    }
}
class ReflectMaterial extends Material {
    double hil_red, hil_green, hil_blue;
    double ref_red, ref_green, ref_blue;
    double pow;

    public ReflectMaterial(Color col, Color amb, Color hil, Color ref, double p) {
	super(col, amb);
	hil_red = hil.getRed() / 255.0;
	hil_green = hil.getGreen() / 255.0;
	hil_blue = hil.getBlue() / 255.0;
	ref_red = ref.getRed() / 255.0;
	ref_green = ref.getGreen() / 255.0;
	ref_blue = ref.getBlue() / 255.0;
	pow = p;
    }
    public boolean hit(int nest, SceneNode root, Background bg, Vector lights,
		    double p[], double v[], double n[], boolean influx, double dist,
		    double rgb[]) {
	super.hit(nest, root, bg, lights, p, v, n, influx, dist, rgb);
	// |n| == 1
	// r := v + 2*(n,v)*n
	double c = -2*Util.product(n, v);
	if (c < 0) return true;
	double r[] = { v[0]+c*n[0], v[1]+c*n[1], v[2]+c*n[2] };
	for(int i = 0; i < lights.size(); i++) {
	    Light light1 = (Light) lights.elementAt(i);
	    double lcolor[] = { hil_red, hil_green, hil_blue };
	    if (light1.lit(nest, root, bg, lights, p, r, lcolor)) {
		rgb[0] += Math.pow(lcolor[0], pow);
		rgb[1] += Math.pow(lcolor[1], pow);
		rgb[2] += Math.pow(lcolor[2], pow);
	    }
	}
	double rcolor[] = { 0, 0, 0 };
	root.calcPixel(nest, bg, lights, p, r, true, rcolor);
	rgb[0] += rcolor[0]*ref_red;
	rgb[1] += rcolor[1]*ref_green;
	rgb[2] += rcolor[2]*ref_blue;
	return true;
    }
}
abstract class Bumper {
    double EPSILON = +0.001;
    // Taken from Prof. Perlin's Sphare2.java
    public void flutter(double p[], double n[]) {
	double f0 = f(p[0], p[1], p[2]);
	double fx = f(p[0]+EPSILON, p[1], p[2]);
	double fy = f(p[0], p[1]+EPSILON, p[2]);
	double fz = f(p[0], p[1], p[2]+EPSILON);
	n[0] -= (fx - f0) / EPSILON;
	n[1] -= (fy - f0) / EPSILON;
	n[2] -= (fz - f0) / EPSILON;
	Util.normalize(n);
    }
    abstract double f(double x, double y, double z);
}
class WaterBumper extends Bumper {
    ImprovedNoise noise = new ImprovedNoise();
    double f(double x, double y, double z) {
	return noise.noise(x*4, y*4, z*4)*0.001;
    }
}
class WaterMaterial extends Material {
    double ref_red, ref_green, ref_blue;
    double pow;
    WaterBumper bumper = new WaterBumper();

    public WaterMaterial(Color col, Color amb, Color ref) {
	super(col, amb);
	ref_red = ref.getRed() / 255.0;
	ref_green = ref.getGreen() / 255.0;
	ref_blue = ref.getBlue() / 255.0;
    }
    public boolean hit(int nest, SceneNode root, Background bg, Vector lights,
		    double p[], double v[], double n[], boolean influx, double dist,
		    double rgb[]) {
	// |n| == 1
	// r := v + 2*(n,v)*n
	if (0 < Util.product(n, v)) return true;
	bumper.flutter(p, n);
	double c = -2*Util.product(n, v);
	double r[] = { v[0]+c*n[0], v[1]+c*n[1], v[2]+c*n[2] };
	double rcolor[] = { 0, 0, 0 };
	root.calcPixel(nest, bg, lights, p, r, true, rcolor);
	rgb[0] += red + rcolor[0]*ref_red;
	rgb[1] += green + rcolor[1]*ref_green;
	rgb[2] += blue + rcolor[2]*ref_blue;
	return true;
    }
}
class TransparentMaterial extends Material {
    double hil_red, hil_green, hil_blue;
    double ref_red, ref_green, ref_blue;
    double tra_red, tra_green, tra_blue;
    double pow, rate, decay;

    public TransparentMaterial(Color col, Color amb, Color hil, Color ref, Color tra, 
			       double p, double r, double d) {
	super(col, amb);
	hil_red = hil.getRed() / 255.0;
	hil_green = hil.getGreen() / 255.0;
	hil_blue = hil.getBlue() / 255.0;
	ref_red = ref.getRed() / 255.0;
	ref_green = ref.getGreen() / 255.0;
	ref_blue = ref.getBlue() / 255.0;
	tra_red = tra.getRed() / 255.0;
	tra_green = tra.getGreen() / 255.0;
	tra_blue = tra.getBlue() / 255.0;
	pow = p;
	rate = r;
	decay = d;
    }

    public boolean hit(int nest, SceneNode root, Background bg, Vector lights, 
		       double p[], double v[], double n[], boolean influx, double dist,
		       double rgb[]) {
//	super.hit(nest, root, bg, lights, p, v, n, influx, dist, rgb);
	// |n| == |v| == 1
	// r := v + 2*(n,v)*n
	double c = Util.product(n, v);
	if (influx) c = -c;
	c = Math.abs(c);
//	if (c < 0) return false;
	double nv[] = { -c*n[0], -c*n[1], -c*n[2] };
	double nh[] = { v[0]-nv[0], v[1]-nv[1], v[2]-nv[2] };
	double r[] = { v[0]-2*nv[0], v[1]-2*nv[1], v[2]-2*nv[2] };

// Brewster's Angle

	double rcolor[] = { 0, 0, 0 };
	if (9 < nest) {
	    root.calcPixel(nest, bg, lights, p, r, !influx, rcolor);
	    rgb[0] += rcolor[0]*ref_red;
	    rgb[1] += rcolor[1]*ref_green;
	    rgb[2] += rcolor[2]*ref_blue;	
	}

	// nh' = nh/|nh| * (|nh|/|v|)*rate = nh * rate
	if (!influx) {
	    Util.scale(1.0/rate, nh);
	} else {
	    Util.scale(rate, nh);
	}
	double f[] = { nv[0]+nh[0], nv[1]+nh[1], nv[2]+nh[2] };
	double fcolor[] = { 0, 0, 0 };
	root.calcPixel(nest, bg, lights, p, f, !influx, fcolor);
	if (!influx) {
	    fcolor[0] *= tra_red*Math.sqrt(1/dist*decay);
	    fcolor[1] *= tra_green*Math.sqrt(1/dist*decay);
	    fcolor[2] *= tra_blue*Math.sqrt(1/dist*decay);
	}
	rgb[0] += fcolor[0];
	rgb[1] += fcolor[1];
	rgb[2] += fcolor[2];

	return false;
    }
}

//  Background
//
class Background {
    double red, green, blue;
    public Background(Color col) {
	red = col.getRed() / 255.0;
	green = col.getGreen() / 255.0;
	blue = col.getBlue() / 255.0;
    }
    public void hit(double v[], double rgb[]) {
	rgb[0] += red;
	rgb[1] += green;
	rgb[2] += blue;
    }
}
class CloudBackground extends Background {
    double cl_red, cl_green, cl_blue;
    double fx, fy, fz;
    ImprovedNoise noise = new ImprovedNoise();
    public CloudBackground(Color col, Color cl, double fx, double fy, double fz) {
	super(col);
	cl_red = cl.getRed() / 255.0;
	cl_green = cl.getGreen() / 255.0;
	cl_blue = cl.getBlue() / 255.0;
	this.fx = fx;
	this.fy = fy;
	this.fz = fz;
    }
    public void hit(double v[], double rgb[]) {
	double c = noise.noise(v[0]*fx, v[1]*fy, v[2]*fz);
	rgb[0] += red + c*c*cl_red;
	rgb[1] += green + c*c*cl_green;
	rgb[2] += blue + c*c*cl_blue;
    }
}


//  Light
//
abstract class Light {
    double red, green, blue;
    public Light(Color col) {
	red = col.getRed() / 255.0;
	green = col.getGreen() / 255.0;
	blue = col.getBlue() / 255.0;
    }
    abstract public boolean lit(int nest, SceneNode root, Background bg, Vector lights,
				double p[], double n[], double rgb[]);
}

class ParallelLight extends Light {
    double lv[] = new double[3];

    public ParallelLight(Color col, double vx, double vy, double vz) {
	super(col);
	lv[0] = -vx;
	lv[1] = -vy;
	lv[2] = -vz;
	Util.normalize(lv);
    }

    public boolean lit(int nest, SceneNode root, Background b, Vector lights, 
		       double p[], double n[], double rgb[]) {
	// check shadow
	double c = Util.product(lv, n);
	if (c < 0) return false;
	rgb[0] *= red*c;
	rgb[1] *= green*c;
	rgb[2] *= blue*c;
	return true;
    }
}

class ParallelLightWithShadow extends ParallelLight {
    Background bg;

    public ParallelLightWithShadow(Color col, double vx, double vy, double vz) {
	super(col, vx, vy, vz);
	bg = new Background(col);
    }

    public boolean lit(int nest, SceneNode root, Background b, Vector lights, 
		       double p[], double n[], double rgb[]) {
	// check shadow
	double tcolor[] = { 0, 0, 0 };
	if (root.calcPixel(nest, bg, new Vector(), p, lv, false, tcolor)) {
	    return false;
	}
	double c = Util.product(lv, n);
	if (c < 0) return false;
	rgb[0] *= red*tcolor[0]*c;
	rgb[1] *= green*tcolor[1]*c;
	rgb[2] *= blue*tcolor[2]*c;
	return true;
    }
}


//  Group
//
class Group extends SceneNode {

    Vector children = new Vector();
    static final int OR = 2;
    static final int AND = 4;
    
    public Group(int mode) {
	super(mode);
    }
    
    public void addChild(SceneNode child) {
	children.addElement((Object) child);
    }

    public void removeChild(SceneNode child) {
	children.removeElement((Object) child);
    }

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

    public void updateMatrix(Matrix base) {
	super.updateMatrix(base);
	for (int i = 0; i < children.size(); i++) {
	    ((SceneNode) children.elementAt(i)).updateMatrix(accumulated);
	}
    }

    public SegmentSet hitRay(double p[], double v[]) {
	SegmentSet segs = new SegmentSet();
	for (int i = 0; i < children.size(); i++) {
	    SceneNode node = (SceneNode) children.elementAt(i);
	    SegmentSet s1 = node.hitRay(p, v);
	    if (i == 0) {
		segs = s1;
	    } else {
		if ((mode & AND) != 0) { // AND
		    segs = SegmentSet.intersection(segs, s1);
		} else {	// OR
		    segs = SegmentSet.union(segs, s1);
		}
	    }
	}
	if ((mode & NEG) != 0) {
	    segs = SegmentSet.neg(segs);
	}
	return segs;
    }
}


//  Shape
//
abstract class Shape extends SceneNode {

    Material material;
    double x0, y0, z0;
    double vx, vy, vz;

    public Shape(int mode, Material m) {
	super(mode);
	material = m;
    }

    public SegmentSet hitRay(double p0[], double v0[]) {
	double p[] = { p0[0], p0[1], p0[2] };
	double v[] = { v0[0], v0[1], v0[2] };
	accu_inv.apply(p);
	accu_inv.apply_rotation(v);
	x0 = p[0]; y0 = p[1]; z0 = p[2];
	vx = v[0]; vy = v[1]; vz = v[2];
	SegmentSet segs = compute();
	if ((mode & NEG) != 0) {
	    segs = SegmentSet.neg(segs);
	}
	return segs;
    }

    public void getPoint(double p[], double t) {
	p[0] = x0+t*vx;
	p[1] = y0+t*vy;
	p[2] = z0+t*vz;
	accumulated.apply(p);
    }

    public void getNormal(double v[], double t) {
	calc_norm(v, t);
	Util.normalize(v);
	accumulated.apply_rotation(v);
    }

    public SegmentSet cross0() {
	return new SegmentSet();
    }
    public SegmentSet cross1(double t, boolean positive) {
	return new SegmentSet(t, positive, this);
    }
    public SegmentSet cross2(double t0, double t1, boolean positive) {
	return new SegmentSet(t0, t1, positive, this);
    }

    abstract SegmentSet compute();
    abstract void calc_norm(double p[], double t);
}


//  PRIMITIVES
//

//  Oval
class Oval extends Shape {
    double rx, ry, rz, rx2, ry2, rz2;
    public Oval(int mode, Material m, double rx, double ry, double rz) {
	super(mode, m);
	this.rx = rx;
	this.ry = ry;
	this.rz = rz;
	rx2 = rx*rx;
	ry2 = ry*ry;
	rz2 = rz*rz;
    }
    public SegmentSet compute() {
	// ((x0+t*vx)/rx)^2 + ((y0+t*vy)/ry)^2 + ((z0+t*vz)/rz)^2 - 1 = 0?
	// (x0*x0/(rx*rx) + 2*x0*t*vx/(rx*rx) + t*t*vx*vx/(rx*rx)) + ... -1 = 0
	double a = vx*vx/rx2 + vy*vy/ry2 + vz*vz/rz2;
	double b = 2*(x0*vx/rx2 + y0*vy/ry2 + z0*vz/rz2);
	double c = x0*x0/rx2 + y0*y0/ry2 + z0*z0/rz2 - 1;
	double D = b*b - 4*a*c;
	if (D < 0) return cross0();
	D = Math.sqrt(D);
	double t0 = (-b-D)/(2*a);
	double t1 = (-b+D)/(2*a);
	// t0 <= t1
	return cross2(t0, t1, true);
    }
    public void calc_norm(double p[], double t) {
	p[0] = ry*rz*(x0+t*vx);
	p[1] = rx*rz*(y0+t*vy);
	p[2] = rx*ry*(z0+t*vz);
    }
}


//  Cylinder
class Cylinder extends Shape {
    double rx, rz, rx2, rz2;
    public Cylinder(int mode, Material m, double rx, double rz) {
	super(mode, m);
	this.rx = rx;
	this.rz = rz;
	rx2 = rx*rx;
	rz2 = rz*rz;
    }
    public SegmentSet compute() {
	// ((x0+t*vx)/rx)^2 + ((y0+t*vy)/ry)^2 + ((z0+t*vz)/rz)^2 - 1 = 0?
	// (x0*x0/(rx*rx) + 2*x0*t*vx/(rx*rx) + t*t*vx*vx/(rx*rx)) + ... -1 = 0
	double a = vx*vx/rx2 + vz*vz/rz2;
	double b = 2*(x0*vx/rx2 + z0*vz/rz2);
	double c = x0*x0/rx2 + z0*z0/rz2 - 1;
	double D = b*b - 4*a*c;
	if (D < 0) return cross0();
	D = Math.sqrt(D);
	double t0 = (-b-D)/(2*a);
	double t1 = (-b+D)/(2*a);
	// t0 <= t1
	return cross2(t0, t1, true);
    }
    public void calc_norm(double p[], double t) {
	p[0] = rz*(x0+t*vx);
	p[1] = 0;
	p[2] = rx*(z0+t*vz);
    }
}


//  Plane
class Plane extends Shape {
    double dx, dy, dz;
    public Plane(int mode, Material m, double dx, double dy, double dz) {
	super(mode, m);
	double v[] = { dx, dy, dz };
	Util.normalize(v);
	this.dx = v[0];
	this.dy = v[1];
	this.dz = v[2];
    }
    public SegmentSet compute() {
	double d = dx*vx+dy*vy+dz*vz;
	if (d == 0) return cross0();
	double t = -(dx*x0+dy*y0+dz*z0) / d;
	return cross1(t, (d < 0));
    }
    public void calc_norm(double p[], double t) {
	p[0] = dx;
	p[1] = dy;
	p[2] = dz;
    }
}


//  COMBINED
//

//  Cube
class Cube extends Group {
    public Cube(int mode, Material m, double xr, double yr, double zr) {
	super(Group.AND | mode);
	Shape s;
	s = new Plane(Shape.POS, m, 1, 0, 0);
	s.setMatrix(Matrix.translation( xr, 0, 0));
	addChild(s);
	s = new Plane(Shape.POS, m,-1, 0, 0);
	s.setMatrix(Matrix.translation(-xr, 0, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, 1, 0);
	s.setMatrix(Matrix.translation( 0, yr, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0,-1, 0);
	s.setMatrix(Matrix.translation( 0,-yr, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, 0, 1);
	s.setMatrix(Matrix.translation( 0, 0, zr));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, 0,-1);
	s.setMatrix(Matrix.translation( 0, 0,-zr));
	addChild(s);
    }
}

//  Tube
class Tube extends Group {
    public Tube(int mode, Material m, double r, double h) {
	super(Group.AND | mode);
	Shape s;
	s = new Cylinder(Shape.POS, m, r, r);
//	s.setMatrix(Matrix.translation( 0, 0, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, -1, 0);
//	s.setMatrix(Matrix.translation( 0, 0, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, 1, 0);
	s.setMatrix(Matrix.translation( 0, h, 0));
	addChild(s);
    }
}

// Pyramid
class Pyramid extends Group {
    public Pyramid(int mode, Material m, double x, double z, double h) {
	super(Group.AND | mode);
	Shape s;
	s = new Plane(Shape.POS, m, -h, x, 0);
	s.setMatrix(Matrix.translation( 0, h, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, h, x, 0);
	s.setMatrix(Matrix.translation( 0, h, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, z, -h);
	s.setMatrix(Matrix.translation( 0, h, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, z, h);
	s.setMatrix(Matrix.translation( 0, h, 0));
	addChild(s);
	s = new Plane(Shape.POS, m, 0, -1, 0);
//	s.setMatrix(Matrix.translation( 0, 0, 0));
	addChild(s);
    }
}

// Buildings
class Building extends Group {
    public Building(int mode, Material m, int type) {
	super(Group.OR | mode);
	SceneNode s;
	double h, x, z, h2;
	x = Math.random()*0.4+0.2;
	z = Math.random()*0.4+0.2;
	h = Math.random()*2+0.5;
	switch(type) {
	case 0:
	    h += 0.5;
	    s = new Cube(Shape.POS, m, x, h, z);
	    s.setMatrix(Matrix.translation(0, h, 0));
	    addChild(s);
/*
	    if (Util.randint(3) == 0) {
		x = (Math.random()*0.3+0.1)*x;
		z = (Math.random()*0.3+0.1)*z;
		h2 = (Math.random()*0.3+0.1)*h;
		s = new Cube(Shape.POS, m, x, h2, z);
		s.setMatrix(Matrix.translation(0, 2*h+h2, 0));
		addChild(s);
	    }
*/
	    break;
	case 1:
	    s = new Cube(Shape.POS, m, x, h, z);
	    s.setMatrix(Matrix.translation(0, h, 0));
	    addChild(s);
	    h2 = Math.random()*1.2+1.0;
	    s = new Pyramid(Shape.POS, m, x, z, h2);
	    s.setMatrix(Matrix.translation(0, 2*h, 0));
	    addChild(s);
	    break;
	case 2:
	    h += 0.7;
	    x = Math.random()*0.5+0.4;
	    s = new Tube(Shape.POS, m, x, h);
	    addChild(s);
	    break;
	}
    }
}



//  Renderer
//
class RTApplet extends MISApplet
{
    double SCRDIST = 2.0;
    int MAXNEST = 10;
    double width;
    Matrix base = Matrix.i();
    Group scene = new Group(Group.OR);
    Vector lights = new Vector();
    Background bg;

    public void addObject(SceneNode s) {
	scene.addChild(s);
    }
    
    public void removeObject(SceneNode s) {
	scene.removeChild(s);
    }
    
    public void addLight(Light lt) {
	lights.addElement(lt);
    }

    public void setBackground(Background b) {
	bg = b;
    }

    public void initFrame() {
	scene.updateMatrix(base);
	if (H < W) {
	    width = (double)W;
	} else {
	    width = (double)H;
	}
    }

    public void setPixel(double x0, double y0, double rgb[]) {
	double x = -(x0-W/2)/width;
	double y = -(y0-H/2)/width;

	double p[] = { 0, 0, -SCRDIST };
	double v[] = { x, y, +SCRDIST };
	rgb[0] = 0.0;
	rgb[1] = 0.0;
	rgb[2] = 0.0;
/*
	if ((x0 % 20) == 0 && (y0 % 20) == 0) {
	    Prin.t.f("%d, ",(int)x0).f("%d: ",(int)y0);
	    scene.isHitRay(p, v);
	    Prin.t.f();
	}
*/
	scene.calcPixel(MAXNEST, bg, lights, p, v, true, rgb);
    }
}


// The Scene   
public class City extends RTApplet
{
    CutObject myobj;
    Shape floor;
    int i = 0;

    // for standalone
    public static void main(String args[]) {
	City me = new City();
	me.init();
	me.start();
	Frame f = new Frame("City of Glass");
	f.add("Center", me);
	f.setSize(200, 200);
	f.show();
    }

    public void init() {
	super.init();
	SceneNode s;
	Color amb = new Color(32,32,48);
	setBackground(new CloudBackground(new Color(100, 130, 240), Color.white, 2, 50.0, 50.0 ));
	
	base = Matrix.translation(0, -3, 5);
	base.mult(Matrix.rotation_X(-0.13));
	base.mult(Matrix.rotation_Y(-0.1));
	addLight(new ParallelLight(Color.white, -1, -1, 1));

	// floor
	Material m = new WaterMaterial(new Color(100, 100, 100), amb, new Color(100, 150, 200));
	floor = new Plane(0, m, 0, 1, 0);
	addObject(floor);

	Material m1 = new TransparentMaterial(Color.black, Color.black, Color.white, 
					      new Color(80,80,80), new Color(180,180,180), 
					      20, 1.5, 0.7);
        // testing
//	m1 = new Material(new Color(200,200,150), amb);

	int i = 0;
	for(int z0 = 5; z0 <= 30; z0 += 3) {
	    for(int x0 = -z0/4; x0 <= z0/4; x0++) {
		if (Util.randint(6) == 0) {
		    s = new Building(Shape.POS, m1, (i++)%3);
		    double x = (Math.random()-0.5)*0.5 + x0+1;
		    double z = (Math.random()-0.5)*0.5 + z0;
		    s.setMatrix(Matrix.translation(x, 0.001, z));
		    addObject(s);
		}
	    }
	}

	init_finished();
    }

}