public class Render extends MISApplet {
	final int p = 16;
	final double ambient[] = {0.1, 0.1, 0.1},
	      diffuse[] = {0.5, 0.5, 0.5},
	      specular[] = {1.0, 1.0, 1.0},
	      L[][] = {{1.0/Math.sqrt(2.25), 1.0/Math.sqrt(2.25), 0.5/Math.sqrt(2.25)}, {-1.0/Math.sqrt(1.25), 0.0, -0.5*Math.sqrt(1.25)}},
	      E[] = {0.0, 0.0, 1.0};

	int frame[][][];
	double zbuffer[][];
	Shape3D s = new Shape3D();

	public void initialize() {
		frame = new int[W][H][3];
		zbuffer = new double[W][H];
		s.sphere(360);
	}

	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] = 0;
				zbuffer[i][j] = Double.NEGATIVE_INFINITY;
			}
		}

		for (int i = 0; i < s.faces.length; i++) {
			final double x1 = s.M.transform(s.vertices[s.faces[i][0]])[0],
				      y1 = s.M.transform(s.vertices[s.faces[i][0]])[1],
				      x2 = s.M.transform(s.vertices[s.faces[i][1]])[0],
				      y2 = s.M.transform(s.vertices[s.faces[i][1]])[1],
				      x3 = s.M.transform(s.vertices[s.faces[i][2]])[0],
				      y3 = s.M.transform(s.vertices[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.M.transform(s.vertices[s.faces[i][0]])[2],
				       z2 = s.M.transform(s.vertices[s.faces[i][1]])[2],
				       z3 = s.M.transform(s.vertices[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; 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[0]*ndotLor0 + specular[0]*Math.pow(RdotEor0, p))*255);
								frame[px][py][1] += (int)((diffuse[1]*ndotLor0 + specular[1]*Math.pow(RdotEor0, p))*255);
								frame[px][py][2] += (int)((diffuse[2]*ndotLor0 + specular[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; 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[0]*ndotLor0 + specular[0]*Math.pow(RdotEor0, p))*255);
								frame[px][py][1] += (int)((diffuse[1]*ndotLor0 + specular[1]*Math.pow(RdotEor0, p))*255);
								frame[px][py][2] += (int)((diffuse[2]*ndotLor0 + specular[2]*Math.pow(RdotEor0, p))*255);
							}
						}
					}
				}
			}
		}

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