import java.awt.*;
import java.awt.image.MemoryImageSource;

class G3Renderer {
	private static final int VER_POS = 0;
	private static final int VER_WPOS = 1;
	private static final int VER_VPOS = 2;
	private static final int VER_PPOS = 3;
	private static final int VER_SPOS = 4;
	private static final int VER_NOR = 5;
	private static final int VER_COL = 6;
	private static final int VER_SPC = 7;
	private static final int VER_UV = 8;
	private static final int VER_TUV = 9;
	private static final int VER_W = 10;
	private static final int MAT_AMB = 0;
	private static final int MAT_DIF = 1;
	private static final int MAT_EMI = 2;
	private static final int MAT_SPC = 3;
	private static final int MAT_POW = 4;
	private static final int MAT_R = 5;
	private static final int MAT_G = 6;
	private static final int MAT_B = 7;
	private static final int MAT_A = 8;
	private int width, height, size;
	private float aspect;
	private int[] fbuf, zbuf;
	private MemoryImageSource mis;
	private Image img;
	private float[][] worldM, viewM, projM, tempM;
	private float[] cam;
	private float[] tar;
	private float[] up;
	float[][][] vertices;
	private int numVertices;
	private float[] material;
	private boolean frustum;
	private float near, far, fov;

	G3Renderer(int wid, int hei) {
		width = wid;
		height = hei;
		size = width * height;
		aspect = (float) height / (float) width;
		fbuf = new int[size];
		zbuf = new int[size];
		cam = new float[3];
		tar = new float[3];
		up = new float[3];
		worldM = new float[4][4];
		viewM = new float[4][4];
		projM = new float[4][4];
		tempM = new float[4][4];
		material = new float[9];
		vertices = new float[64][][];
		for (int i = 0; i < vertices.length; i++)
			vertices[i] = makeVertex();
		setCamera(0, 0, -500, 0, 0, 0, 0, 1, 0);
		perspective(50, 5000, (float) Math.toRadians(60));
		updateScene(0xff000000);
		mis = new MemoryImageSource(width, height, fbuf, 0, width);
		mis.setAnimated(true);
		mis.setFullBufferUpdates(true);
		img = Toolkit.getDefaultToolkit().createImage(mis);
	}

	Image getSceneImage() {
		return img;
	}

	void updateScene(int col) {
		for (int i = 0; i < size; i++) {
			fbuf[i] = col;
			zbuf[i] = 0x7fffffff;
		}
		updateWorldMatrix();
		updateViewMatrix();
		updateProjectionMatrix();
	}

	void perspective(float near, float far, float fov) {
		this.near = near;
		this.far = far;
		this.fov = fov;
		frustum = true;
	}

	void ortho(float near, float far) {
		this.near = near;
		this.far = far;
		frustum = false;
	}

	private void updateViewMatrix() {
		float[] z = new float[3];
		float[] x = new float[3];
		float[] y = new float[3];
		subVec(tar, cam, z);
		normalizeVec(z);
		crossVec(up, z, x);
		normalizeVec(x);
		crossVec(z, x, y);
		viewM[0][0] = x[0];
		viewM[0][1] = y[0];
		viewM[0][2] = z[0];
		viewM[0][3] = 0;
		viewM[1][0] = x[1];
		viewM[1][1] = y[1];
		viewM[1][2] = z[1];
		viewM[1][3] = 0;
		viewM[2][0] = x[2];
		viewM[2][1] = y[2];
		viewM[2][2] = z[2];
		viewM[2][3] = 0;
		viewM[3][0] = -dotVec(x, cam);
		viewM[3][1] = -dotVec(y, cam);
		viewM[3][2] = -dotVec(z, cam);
		viewM[3][3] = 1;
	}

	private void updateProjectionMatrix() {
		if (frustum) {
			float h = 1f / (float) Math.tan(fov * 0.5f);
			float d = far / (far - near);
			projM[0][0] = h * aspect;
			projM[0][1] = 0;
			projM[0][2] = 0;
			projM[0][3] = 0;
			projM[1][0] = 0;
			projM[1][1] = h;
			projM[1][2] = 0;
			projM[1][3] = 0;
			projM[2][0] = 0;
			projM[2][1] = 0;
			projM[2][2] = d;
			projM[2][3] = 1;
			projM[3][0] = 0;
			projM[3][1] = 0;
			projM[3][2] = -near * d;
			projM[3][3] = 0;
		} else {
			projM[0][0] = 2f / width;
			projM[0][1] = 0;
			projM[0][2] = 0;
			projM[0][3] = 0;
			projM[1][0] = 0;
			projM[1][1] = 2f / height;
			projM[1][2] = 0;
			projM[1][3] = 0;
			projM[2][0] = 0;
			projM[2][1] = 0;
			projM[2][2] = 1f / (far - near);
			projM[2][3] = 0;
			projM[3][0] = 0;
			projM[3][1] = 0;
			projM[3][2] = near / (near - far);
			projM[3][3] = 1;
		}
	}

	private void updateWorldMatrix() {
		worldM[0][0] = worldM[1][1] = worldM[2][2] = worldM[3][3] = 1;
		worldM[0][1] = worldM[0][2] = worldM[0][3] = 0;
		worldM[1][0] = worldM[1][2] = worldM[1][3] = 0;
		worldM[2][0] = worldM[2][1] = worldM[2][3] = 0;
		worldM[3][0] = worldM[3][1] = worldM[3][2] = 0;
	}

	private void addVec(float[] v1, float[] v2, float[] res) {
		res[0] = v1[0] + v2[0];
		res[1] = v1[1] + v2[1];
		res[2] = v1[2] + v2[2];
	}

	private void subVec(float[] v1, float[] v2, float[] res) {
		res[0] = v1[0] - v2[0];
		res[1] = v1[1] - v2[1];
		res[2] = v1[2] - v2[2];
	}

	private void mulVec(float[] v, float s, float[] res) {
		res[0] = v[0] * s;
		res[1] = v[1] * s;
		res[2] = v[2] * s;
	}

	private float dotVec(float[] v1, float[] v2) {
		return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];
	}

	private void crossVec(float[] v1, float[] v2, float[] res) {
		res[0] = v1[1] * v2[2] - v1[2] * v2[1];
		res[1] = -v1[0] * v2[2] + v1[2] * v2[0];
		res[2] = v1[0] * v2[1] - v1[1] * v2[0];
	}

	private void normalizeVec(float[] v) {
		float len = (float) Math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
		if (len > 0)
			len = 1f / len;
		v[0] *= len;
		v[1] *= len;
		v[2] *= len;
	}

	private void mulMatVec(float[] v, float[][] m, float[] res) {
		res[0] = m[0][0] * v[0] + m[1][0] * v[1] + m[2][0] * v[2] + m[3][0];
		res[1] = m[0][1] * v[0] + m[1][1] * v[1] + m[2][1] * v[2] + m[3][1];
		res[2] = m[0][2] * v[0] + m[1][2] * v[1] + m[2][2] * v[2] + m[3][2];
	}

	private float mulMatVecW(float[] v, float[][] m) {
		return m[0][3] * v[0] + m[1][3] * v[1] + m[2][3] * v[2] + m[3][3];
	}

	private void mulMatMat(float[][] m1, float[][] m2, float[][] res) {
		float t00 = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0] + m1[0][2]
				* m2[2][0] + m1[0][3] * m2[3][0];
		float t01 = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1] + m1[0][2]
				* m2[2][1] + m1[0][3] * m2[3][1];
		float t02 = m1[0][0] * m2[0][2] + m1[0][1] * m2[1][2] + m1[0][2]
				* m2[2][2] + m1[0][3] * m2[3][2];
		float t03 = m1[0][0] * m2[0][3] + m1[0][1] * m2[1][3] + m1[0][2]
				* m2[2][3] + m1[0][3] * m2[3][3];
		float t10 = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0] + m1[1][2]
				* m2[2][0] + m1[1][3] * m2[3][0];
		float t11 = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1] + m1[1][2]
				* m2[2][1] + m1[1][3] * m2[3][1];
		float t12 = m1[1][0] * m2[0][2] + m1[1][1] * m2[1][2] + m1[1][2]
				* m2[2][2] + m1[1][3] * m2[3][2];
		float t13 = m1[1][0] * m2[0][3] + m1[1][1] * m2[1][3] + m1[1][2]
				* m2[2][3] + m1[1][3] * m2[3][3];
		float t20 = m1[2][0] * m2[0][0] + m1[2][1] * m2[1][0] + m1[2][2]
				* m2[2][0] + m1[2][3] * m2[3][0];
		float t21 = m1[2][0] * m2[0][1] + m1[2][1] * m2[1][1] + m1[2][2]
				* m2[2][1] + m1[2][3] * m2[3][1];
		float t22 = m1[2][0] * m2[0][2] + m1[2][1] * m2[1][2] + m1[2][2]
				* m2[2][2] + m1[2][3] * m2[3][2];
		float t23 = m1[2][0] * m2[0][3] + m1[2][1] * m2[1][3] + m1[2][2]
				* m2[2][3] + m1[2][3] * m2[3][3];
		float t30 = m1[3][0] * m2[0][0] + m1[3][1] * m2[1][0] + m1[3][2]
				* m2[2][0] + m1[3][3] * m2[3][0];
		float t31 = m1[3][0] * m2[0][1] + m1[3][1] * m2[1][1] + m1[3][2]
				* m2[2][1] + m1[3][3] * m2[3][1];
		float t32 = m1[3][0] * m2[0][2] + m1[3][1] * m2[1][2] + m1[3][2]
				* m2[2][2] + m1[3][3] * m2[3][2];
		float t33 = m1[3][0] * m2[0][3] + m1[3][1] * m2[1][3] + m1[3][2]
				* m2[2][3] + m1[3][3] * m2[3][3];
		worldM[0][0] = t00;
		worldM[0][1] = t01;
		worldM[0][2] = t02;
		worldM[0][3] = t03;
		worldM[1][0] = t10;
		worldM[1][1] = t11;
		worldM[1][2] = t12;
		worldM[1][3] = t13;
		worldM[2][0] = t20;
		worldM[2][1] = t21;
		worldM[2][2] = t22;
		worldM[2][3] = t23;
		worldM[3][0] = t30;
		worldM[3][1] = t31;
		worldM[3][2] = t32;
		worldM[3][3] = t33;
	}

	private float[][] makeVertex() {
		float[][] v = new float[11][];
		v[VER_POS] = new float[3];
		v[VER_WPOS] = new float[3];
		v[VER_VPOS] = new float[3];
		v[VER_PPOS] = new float[3];
		v[VER_SPOS] = new float[3];
		v[VER_NOR] = new float[3];
		v[VER_COL] = new float[3];
		v[VER_SPC] = new float[3];
		v[VER_UV] = new float[2];
		v[VER_TUV] = new float[2];
		v[VER_W] = new float[1];
		return v;
	}

	void updateFrame() {
		mis.newPixels();
	}

	void scale(float sx, float sy, float sz) {
		tempM[3][3] = 1;
		tempM[0][1] = tempM[0][2] = tempM[0][3] = 0;
		tempM[1][0] = tempM[1][2] = tempM[1][3] = 0;
		tempM[2][0] = tempM[2][1] = tempM[2][3] = 0;
		tempM[3][0] = tempM[3][1] = tempM[3][2] = 0;
		tempM[0][0] = sx;
		tempM[1][1] = sy;
		tempM[2][2] = sz;
		mulMatMat(tempM, worldM, worldM);
	}

	void rotateX(float theta) {
		float sin = (float) Math.sin(theta);
		float cos = (float) Math.cos(theta);
		tempM[0][0] = tempM[1][1] = tempM[2][2] = tempM[3][3] = 1;
		tempM[0][1] = tempM[0][2] = tempM[0][3] = 0;
		tempM[1][0] = tempM[1][2] = tempM[1][3] = 0;
		tempM[2][0] = tempM[2][1] = tempM[2][3] = 0;
		tempM[3][0] = tempM[3][1] = tempM[3][2] = 0;
		tempM[1][1] = cos;
		tempM[1][2] = -sin;
		tempM[2][1] = sin;
		tempM[2][2] = cos;
		mulMatMat(tempM, worldM, worldM);
	}

	void rotateY(float theta) {
		float sin = (float) Math.sin(theta);
		float cos = (float) Math.cos(theta);
		tempM[0][0] = tempM[1][1] = tempM[2][2] = tempM[3][3] = 1;
		tempM[0][1] = tempM[0][2] = tempM[0][3] = 0;
		tempM[1][0] = tempM[1][2] = tempM[1][3] = 0;
		tempM[2][0] = tempM[2][1] = tempM[2][3] = 0;
		tempM[3][0] = tempM[3][1] = tempM[3][2] = 0;
		tempM[0][0] = cos;
		tempM[0][2] = sin;
		tempM[2][0] = -sin;
		tempM[2][2] = cos;
		mulMatMat(tempM, worldM, worldM);
	}

	void rotateZ(float theta) {
		float sin = (float) Math.sin(theta);
		float cos = (float) Math.cos(theta);
		tempM[0][0] = tempM[1][1] = tempM[2][2] = tempM[3][3] = 1;
		tempM[0][1] = tempM[0][2] = tempM[0][3] = 0;
		tempM[1][0] = tempM[1][2] = tempM[1][3] = 0;
		tempM[2][0] = tempM[2][1] = tempM[2][3] = 0;
		tempM[3][0] = tempM[3][1] = tempM[3][2] = 0;
		tempM[0][0] = cos;
		tempM[0][1] = -sin;
		tempM[1][0] = sin;
		tempM[1][1] = cos;
		mulMatMat(tempM, worldM, worldM);
	}

	void drawPolygon(float[] p1, float[] p2, float[] p3, float[] uv1,
			float[] uv2, float[] uv3, float[] n1, float[] n2, float[] n3) {
		vertices[0][VER_POS][0] = p1[0];
		vertices[0][VER_POS][1] = p1[1];
		vertices[0][VER_POS][2] = p1[2];
		if (n1 == null)
			vertices[0][VER_NOR][0] = 0;
		else {
			vertices[0][VER_NOR][0] = n1[0];
			vertices[0][VER_NOR][1] = n1[1];
			vertices[0][VER_NOR][2] = n1[2];
		}
		if (uv1 == null)
			vertices[0][VER_UV][0] = vertices[0][VER_UV][1] = 0;
		else {
			vertices[0][VER_UV][0] = uv1[0];
			vertices[0][VER_UV][1] = uv1[1];
		}
		vertices[1][VER_POS][0] = p2[0];
		vertices[1][VER_POS][1] = p2[1];
		vertices[1][VER_POS][2] = p2[2];
		if (n2 == null)
			vertices[1][VER_NOR][0] = 0;
		else {
			vertices[1][VER_NOR][0] = n2[0];
			vertices[1][VER_NOR][1] = n2[1];
			vertices[1][VER_NOR][2] = n2[2];
		}
		if (uv2 == null)
			vertices[1][VER_UV][0] = vertices[1][VER_UV][1] = 0;
		else {
			vertices[1][VER_UV][0] = uv2[0];
			vertices[1][VER_UV][1] = uv2[1];
		}
		vertices[2][VER_POS][0] = p3[0];
		vertices[2][VER_POS][1] = p3[1];
		vertices[2][VER_POS][2] = p3[2];
		if (n3 == null)
			vertices[2][VER_NOR][0] = 0;
		else {
			vertices[2][VER_NOR][0] = n3[0];
			vertices[2][VER_NOR][1] = n3[1];
			vertices[2][VER_NOR][2] = n3[2];
		}
		if (uv3 == null)
			vertices[2][VER_UV][0] = vertices[2][VER_UV][1] = 0;
		else {
			vertices[2][VER_UV][0] = uv3[0];
			vertices[2][VER_UV][1] = uv3[1];
		}
		numVertices = 3;
		transformWV();
		drawPolygonAfterClipNearFar(0, 1, 2, true);
	}

	void setMaterial(float amb, float dif, float emi, float spc, float pow,
			float r, float g, float b, float a) {
		material[MAT_AMB] = amb;
		material[MAT_DIF] = dif;
		material[MAT_EMI] = emi;
		material[MAT_SPC] = spc;
		material[MAT_POW] = pow;
		material[MAT_R] = r;
		material[MAT_G] = g;
		material[MAT_B] = b;
		material[MAT_A] = a;
	}

	private void transformWV() {
		float[][][] copy_vertices = vertices;
		for (int i = 0; i < numVertices; i++) {
			mulMatVec(copy_vertices[i][VER_POS], worldM,
					copy_vertices[i][VER_WPOS]);
			mulMatVec(copy_vertices[i][VER_WPOS], viewM,
					copy_vertices[i][VER_VPOS]);
		}
	}

	private void transformPS(float[][]... vertices) {
		for (int i = 0; i < 3; i++) {
			mulMatVec(vertices[i][VER_VPOS], projM, vertices[i][VER_PPOS]);
			if (frustum)
				vertices[i][VER_W][0] = 1f / mulMatVecW(vertices[i][VER_VPOS],
						projM);
			else vertices[i][VER_W][0] = 1;
			mulVec(vertices[i][VER_PPOS], vertices[i][VER_W][0],
					vertices[i][VER_SPOS]);
			vertices[i][VER_SPOS][0] = width * 0.5f + vertices[i][VER_SPOS][0]
					* width * 0.5f;
			vertices[i][VER_SPOS][1] = height * 0.5f - vertices[i][VER_SPOS][1]
					* height * 0.5f;
		}
	}

	private void drawPolygonAfterClipNearFar(int vi1, int vi2, int vi3,
			boolean step) {
		float[][] v1, v2, v3;
		int num;
		int i1, i2;
		v1 = vertices[vi1];
		v2 = vertices[vi2];
		v3 = vertices[vi3];
		if (step) {
			// clip by near
			num = 0;
			if (v1[VER_VPOS][2] < near)
				num++;
			if (v2[VER_VPOS][2] < near)
				num += 2;
			if (v3[VER_VPOS][2] < near)
				num += 4;
			switch (num) {
			case 1:// v1
				clipVertexNear(v1, v2, vertices[i1 = numVertices++]);
				clipVertexNear(v1, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(i1, vi2, vi3, false);
				drawPolygonAfterClipNearFar(i1, vi3, i2, false);
				return;
			case 2:// v2
				clipVertexNear(v2, v1, vertices[i1 = numVertices++]);
				clipVertexNear(v2, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(vi1, i1, vi3, false);
				drawPolygonAfterClipNearFar(i1, i2, vi3, false);
				return;
			case 3:// v1 v2
				clipVertexNear(v1, v3, vertices[i1 = numVertices++]);
				clipVertexNear(v2, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(i1, i2, vi3, false);
				return;
			case 4:// v3
				clipVertexNear(v3, v2, vertices[i1 = numVertices++]);
				clipVertexNear(v3, v1, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(vi1, vi2, i1, false);
				drawPolygonAfterClipNearFar(vi1, i1, i2, false);
				return;
			case 5:// v1 v3
				clipVertexNear(v1, v2, vertices[i1 = numVertices++]);
				clipVertexNear(v3, v2, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(i1, vi2, i2, false);
				return;
			case 6:// v2 v3
				clipVertexNear(v2, v1, vertices[i1 = numVertices++]);
				clipVertexNear(v3, v1, vertices[i2 = numVertices++]);
				drawPolygonAfterClipNearFar(vi1, i1, i2, false);
				return;
			case 7:// v1 v2 v3
				return;
			}
		}
		transformPS(v1, v2, v3);
		num = 0;
		if (v1[VER_VPOS][2] > far)
			num++;
		if (v2[VER_VPOS][2] > far)
			num += 2;
		if (v3[VER_VPOS][2] > far)
			num += 4;
		switch (num) {
		case 0:
			drawPolygonAfterClipScreenLeftTop(vi1, vi2, vi3, true);
			return;
		case 1:// v1
			clipVertexFar(v1, v2, vertices[i1 = numVertices++]);
			clipVertexFar(v1, v3, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(i1, vi2, vi3, true);
			drawPolygonAfterClipScreenLeftTop(i1, vi3, i2, true);
			return;
		case 2:// v2
			clipVertexFar(v2, v1, vertices[i1 = numVertices++]);
			clipVertexFar(v2, v3, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(vi1, i1, vi3, true);
			drawPolygonAfterClipScreenLeftTop(i1, i2, vi3, true);
			return;
		case 3:// v1 v2
			clipVertexFar(v1, v3, vertices[i1 = numVertices++]);
			clipVertexFar(v2, v3, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(i1, i2, vi3, true);
			return;
		case 4:// v3
			clipVertexFar(v3, v2, vertices[i1 = numVertices++]);
			clipVertexFar(v3, v1, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(vi1, vi2, i1, true);
			drawPolygonAfterClipScreenLeftTop(vi1, i1, i2, true);
			return;
		case 5:// v1 v3
			clipVertexFar(v1, v2, vertices[i1 = numVertices++]);
			clipVertexFar(v3, v2, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(i1, vi2, i2, true);
			return;
		case 6:// v2 v3
			clipVertexFar(v2, v1, vertices[i1 = numVertices++]);
			clipVertexFar(v3, v1, vertices[i2 = numVertices++]);
			drawPolygonAfterClipScreenLeftTop(vi1, i1, i2, true);
			return;
		case 7:// v1 v2 v3
			return;
		}
	}

	private void drawPolygonAfterClipScreenLeftTop(int vi1, int vi2, int vi3,
			boolean step) {
		float[][] v1, v2, v3;
		int num;
		int i1, i2;
		v1 = vertices[vi1];
		v2 = vertices[vi2];
		v3 = vertices[vi3];
		if (step) {
			// clip by screen left
			num = 0;
			if (v1[VER_SPOS][0] < 0)
				num++;
			if (v2[VER_SPOS][0] < 0)
				num += 2;
			if (v3[VER_SPOS][0] < 0)
				num += 4;
			switch (num) {
			case 1:// v1
				clipVertexLeft(v1, v2, vertices[i1 = numVertices++]);
				clipVertexLeft(v1, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(i1, vi2, vi3, false);
				drawPolygonAfterClipScreenLeftTop(i1, vi3, i2, false);
				return;
			case 2:// v2
				clipVertexLeft(v2, v1, vertices[i1 = numVertices++]);
				clipVertexLeft(v2, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(vi1, i1, vi3, false);
				drawPolygonAfterClipScreenLeftTop(i1, i2, vi3, false);
				return;
			case 3:// v1 v2
				clipVertexLeft(v1, v3, vertices[i1 = numVertices++]);
				clipVertexLeft(v2, v3, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(i1, i2, vi3, false);
				return;
			case 4:// v3
				clipVertexLeft(v3, v2, vertices[i1 = numVertices++]);
				clipVertexLeft(v3, v1, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(vi1, vi2, i1, false);
				drawPolygonAfterClipScreenLeftTop(vi1, i1, i2, false);
				return;
			case 5:// v1 v3
				clipVertexLeft(v1, v2, vertices[i1 = numVertices++]);
				clipVertexLeft(v3, v2, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(i1, vi2, i2, false);
				return;
			case 6:// v2 v3
				clipVertexLeft(v2, v1, vertices[i1 = numVertices++]);
				clipVertexLeft(v3, v1, vertices[i2 = numVertices++]);
				drawPolygonAfterClipScreenLeftTop(vi1, i1, i2, false);
				return;
			case 7:// v1 v2 v3
				return;
			}
		}
		// clip by screen top
		num = 0;
		if (v1[VER_SPOS][1] < 0)
			num++;
		if (v2[VER_SPOS][1] < 0)
			num += 2;
		if (v3[VER_SPOS][1] < 0)
			num += 4;
		switch (num) {
		case 0:
			render(vi1, vi2, vi3);
			return;
		case 1:// v1
			clipVertexTop(v1, v2, vertices[i1 = numVertices++]);
			clipVertexTop(v1, v3, vertices[i2 = numVertices++]);
			render(i1, vi2, vi3);
			render(i1, vi3, i2);
			return;
		case 2:// v2
			clipVertexTop(v2, v1, vertices[i1 = numVertices++]);
			clipVertexTop(v2, v3, vertices[i2 = numVertices++]);
			render(vi1, i1, vi3);
			render(i1, i2, vi3);
			return;
		case 3:// v1 v2
			clipVertexTop(v1, v3, vertices[i1 = numVertices++]);
			clipVertexTop(v2, v3, vertices[i2 = numVertices++]);
			render(i1, i2, vi3);
			return;
		case 4:// v3
			clipVertexTop(v3, v2, vertices[i1 = numVertices++]);
			clipVertexTop(v3, v1, vertices[i2 = numVertices++]);
			render(vi1, vi2, i1);
			render(vi1, i1, i2);
			return;
		case 5:// v1 v3
			clipVertexTop(v1, v2, vertices[i1 = numVertices++]);
			clipVertexTop(v3, v2, vertices[i2 = numVertices++]);
			render(i1, vi2, i2);
			return;
		case 6:// v2 v3
			clipVertexTop(v2, v1, vertices[i1 = numVertices++]);
			clipVertexTop(v3, v1, vertices[i2 = numVertices++]);
			render(vi1, i1, i2);
			return;
		case 7:// v1 v2 v3
			return;
		}
	}

	private void clipVertexNear(float[][] clip, float[][] noClip, float[][] res) {
		if (clip[VER_VPOS][2] - noClip[VER_VPOS][2] == 0) {
			res[VER_POS] = clip[VER_POS];
			res[VER_WPOS] = clip[VER_WPOS];
			res[VER_VPOS] = clip[VER_VPOS];
			res[VER_PPOS] = clip[VER_PPOS];
			res[VER_SPOS] = clip[VER_SPOS];
			res[VER_NOR] = clip[VER_NOR];
			res[VER_COL] = clip[VER_COL];
			res[VER_SPC] = clip[VER_SPC];
			res[VER_UV] = clip[VER_UV];
			res[VER_TUV] = clip[VER_TUV];
			res[VER_W] = clip[VER_W];
			return;
		}
		clipVertex(clip, noClip, (near - noClip[VER_VPOS][2])
				/ (clip[VER_VPOS][2] - noClip[VER_VPOS][2]), res);
	}

	private void clipVertexFar(float[][] clip, float[][] noClip, float[][] res) {
		if (clip[VER_VPOS][2] - noClip[VER_VPOS][2] == 0) {
			res[VER_POS] = clip[VER_POS];
			res[VER_WPOS] = clip[VER_WPOS];
			res[VER_VPOS] = clip[VER_VPOS];
			res[VER_PPOS] = clip[VER_PPOS];
			res[VER_SPOS] = clip[VER_SPOS];
			res[VER_NOR] = clip[VER_NOR];
			res[VER_COL] = clip[VER_COL];
			res[VER_SPC] = clip[VER_SPC];
			res[VER_UV] = clip[VER_UV];
			res[VER_TUV] = clip[VER_TUV];
			res[VER_W] = clip[VER_W];
			return;
		}
		clipVertex(clip, noClip, (far - noClip[VER_VPOS][2])
				/ (clip[VER_VPOS][2] - noClip[VER_VPOS][2]), res);
	}

	private void clipVertexLeft(float[][] clip, float[][] noClip, float[][] res) {
		if (clip[VER_SPOS][0] - noClip[VER_SPOS][0] == 0) {
			res[VER_POS] = clip[VER_POS];
			res[VER_WPOS] = clip[VER_WPOS];
			res[VER_VPOS] = clip[VER_VPOS];
			res[VER_PPOS] = clip[VER_PPOS];
			res[VER_SPOS] = clip[VER_SPOS];
			res[VER_NOR] = clip[VER_NOR];
			res[VER_COL] = clip[VER_COL];
			res[VER_SPC] = clip[VER_SPC];
			res[VER_UV] = clip[VER_UV];
			res[VER_TUV] = clip[VER_TUV];
			res[VER_W] = clip[VER_W];
			return;
		}
		clipVertex(clip, noClip, -noClip[VER_SPOS][0]
				/ (clip[VER_SPOS][0] - noClip[VER_SPOS][0]), res);
	}

	private void clipVertexTop(float[][] clip, float[][] noClip, float[][] res) {
		if (clip[VER_SPOS][1] - noClip[VER_SPOS][1] == 0) {
			res[VER_POS] = clip[VER_POS];
			res[VER_WPOS] = clip[VER_WPOS];
			res[VER_VPOS] = clip[VER_VPOS];
			res[VER_PPOS] = clip[VER_PPOS];
			res[VER_SPOS] = clip[VER_SPOS];
			res[VER_NOR] = clip[VER_NOR];
			res[VER_COL] = clip[VER_COL];
			res[VER_SPC] = clip[VER_SPC];
			res[VER_UV] = clip[VER_UV];
			res[VER_TUV] = clip[VER_TUV];
			res[VER_W] = clip[VER_W];
			return;
		}
		clipVertex(clip, noClip, -noClip[VER_SPOS][1]
				/ (clip[VER_SPOS][1] - noClip[VER_SPOS][1]), res);
	}

	void render(int vi1, int vi2, int vi3) {
		float[][][] copy_vertices = new float[][][] { vertices[vi1],
			vertices[vi2], vertices[vi3] };
		int min, mid, max;
		int it, il, ir;
		float y0, y1, y2;
		y0 = copy_vertices[0][VER_SPOS][1];
		y1 = copy_vertices[1][VER_SPOS][1];
		y2 = copy_vertices[2][VER_SPOS][1];
		if (y0 < y1) {
			if (y0 < y2) {
				it = 0;
				if (y1 < y2) {
					il = 1;
					ir = 2;
				} else {
					il = 2;
					ir = 1;
				}
			} else {
				it = 2;
				il = 0;
				ir = 1;
			}
		} else {
			if (y0 > y2) {
				ir = 0;
				if (y1 > y2) {
					il = 1;
					it = 2;
				} else {
					il = 2;
					it = 1;
				}
			} else {
				it = 1;
				il = 0;
				ir = 2;
			}
		}
		min = (int) (copy_vertices[it][VER_SPOS][1] + 0.5f);
		mid = (int) (copy_vertices[il][VER_SPOS][1] + 0.5f);
		max = (int) (copy_vertices[ir][VER_SPOS][1] + 0.5f);
		if (min == max)
			return;
		if ((copy_vertices[il][VER_SPOS][0] - copy_vertices[it][VER_SPOS][0])
				/ (copy_vertices[il][VER_SPOS][1] - copy_vertices[it][VER_SPOS][1]) > (copy_vertices[ir][VER_SPOS][0] - copy_vertices[it][VER_SPOS][0])
				/ (copy_vertices[ir][VER_SPOS][1] - copy_vertices[it][VER_SPOS][1])) {
			int temp = il;
			il = ir;
			ir = temp;
		}
		int r, g, b;
		r = (int) (material[MAT_R] * 255f + 0.5f);
		g = (int) (material[MAT_G] * 255f + 0.5f);
		b = (int) (material[MAT_B] * 255f + 0.5f);
		int fill = 0xff000000 | r << 16 | g << 8 | b;
		renderPolygonFlat(copy_vertices, it, il, ir, min, mid, max, fill);
	}

	private void renderPolygonFlat(float[][][] v, int it, int il, int ir,
			int min, int mid, int max, int fill) {
		float ftx, flx, frx;
		float fty, fly, fry;
		float ftz, flz, frz;
		// float fitz, filz, firz;
		// copy for speedup
		int[] copy_zbuf = zbuf;
		int[] copy_fbuf = fbuf;
		ftx = v[it][VER_SPOS][0] + 0.5f;
		fty = v[it][VER_SPOS][1] + 0.5f;
		ftz = v[it][VER_SPOS][2] + 0.5f;
		flx = v[il][VER_SPOS][0] + 0.5f;
		fly = v[il][VER_SPOS][1] + 0.5f;
		flz = v[il][VER_SPOS][2] + 0.5f;
		frx = v[ir][VER_SPOS][0] + 0.5f;
		fry = v[ir][VER_SPOS][1] + 0.5f;
		frz = v[ir][VER_SPOS][2] + 0.5f;
		// fitz = 1f / ftz;
		// filz = 1f / flz;
		// firz = 1f / frz;
		// check width and height
		if (min == max || ((int) ftx == (int) flx && (int) flx == (int) frx))
			return;
		// pixel offset
		int off = min * width;
		// invert length
		float invL;
		// left y and right y
		int ly, ry;
		// calc thickness
		float t = (frx - ftx) * (fly - fty) - (flx - ftx) * (fry - fty);
		int ddz;
		// check thickness
		if (t == 0)
			return;
		t = 1f / t;
		ddz = (int) (((frz - ftz) * (fly - fty) - (flz - ftz) * (fry - fty))
				* t * 0xffffff);
		// left datas
		float ll, lx, ldx, lz, ldz;
		// calc left datas
		ly = (int) fly;
		ll = (int) (fly - fty + 0.5f);
		invL = 1f / ll;
		lx = ftx;
		ldx = (flx - ftx) * invL;
		// System.out.println(lddx);
		lz = ftz;
		ldz = (flz - ftz) * invL;
		// right datas
		float rl, rx, rdx, rz, rdz;
		// calc right datas
		ry = (int) fry;
		rl = (int) (fry - fty + 0.5f);
		invL = 1f / rl;
		rx = ftx;
		rdx = (frx - ftx) * invL;
		rz = ftz;
		rdz = (frz - ftz) * invL;
		int y;
		// set height
		y = min;
		// clip by bottom screen
		if (max > height)
			max = height;
		// start rasterize
		while (y < max) {
			if (y == mid) {
				if (ly == ry)
					return;
				if (y == ly) {
					ll = (int) (fry - fly + 0.5f);
					invL = 1f / ll;
					lx = flx;
					ldx = (frx - flx) * invL;
					lz = flz;
					ldz = (frz - flz) * invL;
				}
				if (y == ry) {
					rl = (int) (fly - fry + 0.5f);
					invL = 1f / rl;
					rx = frx;
					rdx = (flx - frx) * invL;
					rz = frz;
					rdz = (flz - frz) * invL;
				}
			}
			int ilx = (int) (lx + 0.2f);
			int irx = (int) (rx + 0.8f);
			if (irx - ilx > 0) {
				int iz = (int) (lz * 0xffffff);
				int x = ilx;
				if (irx > width)
					irx = width;
				while (x < irx) {
					if (copy_zbuf[off + x] > iz) {
						copy_fbuf[off + x] = fill;
						copy_zbuf[off + x] = iz;
					}
					x++;
					iz += ddz;
				}
			}
			lx += ldx;
			rx += rdx;
			lz += ldz;
			rz += rdz;
			off += width;
			y++;
		}
	}

	void clipVertex(float[][] clip, float[][] noClip, float t, float[][] res) {
		for (int i = 0; i < res.length; i++)
			for (int j = 0; j < res[i].length; j++)
				res[i][j] = (clip[i][j] - noClip[i][j]) * t + noClip[i][j];
	}

	void setCamera(float camX, float camY, float camZ, float tarX, float tarY,
			float tarZ, float upX, float upY, float upZ) {
		cam[0] = camX;
		cam[1] = camY;
		cam[2] = camZ;
		tar[0] = tarX;
		tar[1] = tarY;
		tar[2] = tarZ;
		up[0] = upX;
		up[1] = upY;
		up[2] = upZ;
	}
}