public class Render extends MISApplet {
	final int p = 1;
	final double ambient[] = {0.1, 0.1, 0.1},
	      diffuse[][] = {{1.0, 1.0, 1.0}, {1.0, 1.0, 1.0}, {1.0, 1.0, 1.0}, {0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {1.0, 1.0, 0.0}, {1.0, 1.0, 0.0}},
	      specular[][] = {{0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {0.0, 0.0, 0.0}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}, {0.5, 0.5, 0.5}},
	      L[][] = {{0.0, 0.0, 1.0}},
	      E[] = {0.0, 0.0, 1.0};

	int frame[][][];
	double zbuffer[][];
	Shape3D s[] = new Shape3D[10];

	public void initialize() {
		frame = new int[W][H][3];
		zbuffer = new double[W][H];
		s[0] = new Shape3D();
		s[0].sphere(360);
		s[0].M.scale(1.0/3.0, 1.0/3.0, 1.0/3.0);
		s[0].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0), 0.0);
		s[1] = new Shape3D();
		s[1].sphere(360);
		s[1].M.scale(1.0/4.0, 1.0/4.0, 1.0/4.0);
		s[1].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0), 0.0);
		s[2] = new Shape3D();
		s[2].sphere(360);
		s[2].M.scale(1.0/5.0, 1.0/5.0, 1.0/5.0);
		s[2].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0), 0.0);
		s[3] = new Shape3D();
		s[3].cylinder(180);
		s[3].M.scale(1.0/5.0, 1.0/100.0, 1.0/5.0);
		s[3].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/100.0, 0.0);
		s[4] = new Shape3D();
		s[4].cylinder(180);
		s[4].M.scale(1.0/7.0, 1.0/7.0, 1.0/7.0);
		s[4].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/7.0, 0.0);
		s[5] = new Shape3D();
		s[5].sphere(360);
		s[5].M.scale(1.0/50.0, 1.0/50.0, 1.0/50.0);
		s[5].M.translate(-1.0/5.0/3.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/5.0/3.0, 1.0/5.0);
		s[6] = new Shape3D();
		s[6].sphere(360);
		s[6].M.scale(1.0/50.0, 1.0/50.0, 1.0/50.0);
		s[6].M.translate(1.0/5.0/3.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) + 1.0/5.0/3.0, 1.0/5.0);
		s[7] = new Shape3D();
		s[7].cylinder(180);
		s[7].M.rotateX(Math.PI/2);
		s[7].M.scale(1.0/50.0, 1.0/50.0, 1.0/50.0);
		s[7].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0), 1.0/5.0);
		s[8] = new Shape3D();
		s[8].cylinder(180);
		s[8].M.scale(1.0/100.0, 1.0/10.0, 1.0/100.0);
		s[8].M.rotateX(Math.PI/2);
		s[8].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) - 1.0/5.0/3.0, 1.0/5.0);
		s[8].M.rotateY(-Math.PI/4);
		s[9] = new Shape3D();
		s[9].cylinder(180);
		s[9].M.scale(1.0/25.0, 1.0/25.0, 1.0/25.0);
		s[9].M.translate(0.0, -2.0/3.0 - 0.25*(1.0/3.0) + 1.0/3.0 + 1.0/4.0 - 0.25*(1.0/4.0) + 1.0/4.0 + 1.0/5.0 - 0.25*(1.0/5.0) - 1.0/5.0/3.0, 1.0/5.0 + 1.0/10.0);
		s[9].M.rotateY(-Math.PI/4);
	}

	public void initFrame(double t) {
		for (int i = 0; i < W; i++) {
			for (int j = 0; j < H; j++) {
				frame[i][j][0] = frame[i][j][1] = frame[i][j][2] = 255;
				zbuffer[i][j] = Double.NEGATIVE_INFINITY;
			}
		}

		for (int i_s = 0; i_s < s.length; i_s++) {
		for (int i = 0; i < s[i_s].faces.length; i++) {
			final double x1 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][0]])[0],
				      y1 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][0]])[1],
				      x2 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][1]])[0],
				      y2 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][1]])[1],
				      x3 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][2]])[0],
				      y3 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][2]])[1],
				      u_x = x2 - x1,
				      u_y = y2 - y1,
				      v_x = x3 - x1,
				      v_y = y3 - y1;

			if (u_x*v_y > u_y*v_x) {
				double z1 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][0]])[2],
				       z2 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][1]])[2],
				       z3 = s[i_s].M.transform(s[i_s].vertices[s[i_s].faces[i][2]])[2];

				final double u_z = z2 - z1,
					      v_z = z3 - z1,
					      udotv = (u_x*v_x + u_y*v_y + u_z*v_z),
					      u_mag = Math.sqrt(u_x*u_x + u_y*u_y + u_z*u_z),
					      v_mag = Math.sqrt(v_x*v_x + v_y*v_y + v_z*v_z),
					      u_magtimesv_mag = u_mag*v_mag,
					      c = Math.sqrt(u_magtimesv_mag*u_magtimesv_mag - udotv*udotv),
					      n_x = (u_y*v_z - u_z*v_y)/c,
					      n_y = (u_z*v_x - u_x*v_z)/c,
					      n_z = (u_x*v_y - u_y*v_x)/c;

				double dtmp, z_l, z_r, z, ndotL, R_x, R_y, R_z, RdotE, ndotLor0, RdotEor0;
				int px1 = (int)(x1*W/2 + W/2.),
				    py1 = (int)(y1*-H/2 + H/2.),
				    px2 = (int)(x2*W/2 + W/2.),
				    py2 = (int)(y2*-H/2 + H/2.),
				    px3 = (int)(x3*W/2 + W/2.),
				    py3 = (int)(y3*-H/2 + H/2.),
				    itmp, py_star, px_l, px_r;

				final int min = py1 < py2 ? py1 < py3 ? py1 : py3 : py2 < py3 ? py2 : py3;

				if (py1 != min) {
					if (py2 == min) {
						itmp = py1;
						py1 = py2;
						py2 = py3;
						py3 = itmp;
						itmp = px1;
						px1 = px2;
						px2 = px3;
						px3 = itmp;
						dtmp = z1;
						z1 = z2;
						z2 = z3;
						z3 = dtmp;
					} else {
						itmp = py1;
						py1 = py3;
						py3 = py2;
						py2 = itmp;
						itmp = px1;
						px1 = px3;
						px3 = px2;
						px2 = itmp;
						dtmp = z1;
						z1 = z3;
						z3 = z2;
						z2 = dtmp;
					}
				}

				py_star = py2 < py3 ? py2 : py3;

				for (int py = py1; py < (py_star < H ? py_star : H); py++) {
					px_l = (int)((py - py1)*(double)(px2 - px1)/(py2 - py1) + px1);
					px_r = (int)((py - py1)*(double)(px3 - px1)/(py3 - py1) + px1);
					z_l = (py - py1)*(z2 - z1)/(py2 - py1) + z1;
					z_r = (py - py1)*(z3 - z1)/(py3 - py1) + z1;
					for (int px = px_l; px < px_r; px++) {
						z = (px - px_l)*(z_r - z_l)/(px_r - px_l) + z_l;
						if (z > zbuffer[px][py]) {
							zbuffer[px][py] = z;
							frame[px][py][0] = (int)(ambient[0]*255);
							frame[px][py][1] = (int)(ambient[1]*255);
							frame[px][py][2] = (int)(ambient[2]*255);
							for (int j = 0; j < L.length; j++) {
								ndotL = n_x*L[j][0] + n_y*L[j][1] + n_z*L[j][2];
								R_x = 2*ndotL*n_x - L[j][0];
								R_y = 2*ndotL*n_y - L[j][1];
								R_z = 2*ndotL*n_z - L[j][2];
								RdotE = R_x*E[0] + R_y*E[1] + R_z*E[2];
								//c = Math.sqrt((E[0] - (x1 + x2 + x3)/3)*(E[0] - (x1 + x2 + x3)/3) + (E[1] - (y1 + y2 + y3)/3)*(E[1] - (y1 + y2 + y3)/3) + (E[2] - (z1 + z2 + z3)/3)*(E[2] - (z1 + z2 + z3)/3));
								//RdotE = R_x*(E[0] - (x1 + x2 + x3)/3*c) + R_y*(E[1] - (y1 + y2 + y3)/3*c) + R_z*(E[2] - (z1 + z2 + z3)/3*c);
								ndotLor0 = ndotL > 0 ? ndotL : 0;
								RdotEor0 = RdotE > 0 ? RdotE : 0;
								frame[px][py][0] += (int)((diffuse[i_s][0]*ndotLor0 + specular[i_s][0]*Math.pow(RdotEor0, p))*255);
								frame[px][py][1] += (int)((diffuse[i_s][1]*ndotLor0 + specular[i_s][1]*Math.pow(RdotEor0, p))*255);
								frame[px][py][2] += (int)((diffuse[i_s][2]*ndotLor0 + specular[i_s][2]*Math.pow(RdotEor0, p))*255);
							}
						}
					}
				}

				if (py2 < py3) {
					itmp = py1;
					py1 = py2;
					py2 = py3;
					py3 = itmp;
					itmp = px1;
					px1 = px2;
					px2 = px3;
					px3 = itmp;
					dtmp = z1;
					z1 = z2;
					z2 = z3;
					z3 = dtmp;
				}

				for (int py = py_star; py < (py2 < H ? py2 : H); py++) {
					px_l = (int)((py - py2)*(double)(px1 - px2)/(py1 - py2) + px2);
					px_r = (int)((py - py2)*(double)(px3 - px2)/(py3 - py2) + px2);
					z_l = (py - py2)*(z1 - z2)/(py1 - py2) + z2;
					z_r = (py - py2)*(z3 - z2)/(py3 - py2) + z2;
					for (int px = px_l; px < px_r; px++) {
					    z = (px - px_l)*(z_r - z_l)/(px_r - px_l) + z_l;
						if (z > zbuffer[px][py]) {
							zbuffer[px][py] = z;
							frame[px][py][0] = (int)(ambient[0]*255);
							frame[px][py][1] = (int)(ambient[1]*255);
							frame[px][py][2] = (int)(ambient[2]*255);
							for (int j = 0; j < L.length; j++) {
								ndotL = n_x*L[j][0] + n_y*L[j][1] + n_z*L[j][2];
								R_x = 2*ndotL*n_x - L[j][0];
								R_y = 2*ndotL*n_y - L[j][1];
								R_z = 2*ndotL*n_z - L[j][2];
								RdotE = R_x*E[0] + R_y*E[1] + R_z*E[2];
								//c = Math.sqrt((E[0] - (x1 + x2 + x3)/3)*(E[0] - (x1 + x2 + x3)/3) + (E[1] - (y1 + y2 + y3)/3)*(E[1] - (y1 + y2 + y3)/3) + (E[2] - (z1 + z2 + z3)/3)*(E[2] - (z1 + z2 + z3)/3));
								//RdotE = R_x*(E[0] - (x1 + x2 + x3)/3*c) + R_y*(E[1] - (y1 + y2 + y3)/3*c) + R_z*(E[2] - (z1 + z2 + z3)/3*c);
								ndotLor0 = ndotL > 0 ? ndotL : 0;
								RdotEor0 = RdotE > 0 ? RdotE : 0;
								frame[px][py][0] += (int)((diffuse[i_s][0]*ndotLor0 + specular[i_s][0]*Math.pow(RdotEor0, p))*255);
								frame[px][py][1] += (int)((diffuse[i_s][1]*ndotLor0 + specular[i_s][1]*Math.pow(RdotEor0, p))*255);
								frame[px][py][2] += (int)((diffuse[i_s][2]*ndotLor0 + specular[i_s][2]*Math.pow(RdotEor0, p))*255);
							}
						}
					}
				}
			}
		}

			s[i_s].M.rotateY(-Math.PI/180);
		}
	}

	public void setPixel(int x, int y, int rgb[]) {
		rgb[0] = frame[x][y][0];
		rgb[1] = frame[x][y][1];
		rgb[2] = frame[x][y][2];
	}
}