/*
    canvastastic.js: a library for 3D rendering in Javascript
    Copyright (C) 2006  Matt Westcott

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License, version 2.1, as published by the Free Software Foundation.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
    
    Contact address:
      Matt Westcott, 14 Daisy Hill Drive, Adlington,
      Chorley, Lancs. PR6 9NE, United Kingdom
    E-mail: matt@west.co.tt
*/

/* Version: beta_1 (2006-09-11) */    

/* helper functions */
CT = {};
CT.util = {
	coalesce: function() {
		/* return the first non-null argument */
		for (var i = 0; i < arguments.length; i++) {
			if (arguments[i] != null) return arguments[i];
		}
	},
	makeColour: function(r,g,b) {
		/* return a function that takes a value in range [0..1] and returns a colour identifier
		for the colour given by r/g/b at that intensity */
		return function(i) {
			return "rgb(" + Math.floor(i*r) + ", " + Math.floor(i*g) + ", " + Math.floor(i*b) + ")";
		}
	}
}
CT.util.makeColor = CT.util.makeColour;
CT.vectors = {
	normalise: function(v) {
		var mod = Math.sqrt(v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
		return [v[0] / mod, v[1] / mod, v[2] / mod];
	},
	dotProduct: function(a, b) {
		return (a[0]*b[0] + a[1]*b[1] + a[2]*b[2]);
	},
	crossProduct: function(a, b) {
		return [a[1]*b[2] - a[2]*b[1], a[2]*b[0] - a[0]*b[2], a[0]*b[1] - a[1]*b[0]];
	},
	isFrontFacing: function(sv0, sv1, sv2) {
		/* takes three sets of screen coordinates. Must be in anticlockwise order to return true */
		return ((sv1[0] - sv0[0]) * (sv2[1] - sv0[1]) - (sv2[0] - sv0[0]) * (sv1[1] - sv0[1]) < 0);
	},
	transformVector: function(v, m) {
		return [
			v[0]*m[0] + v[1]*m[1] + v[2]*m[2] + m[3],
			v[0]*m[4] + v[1]*m[5] + v[2]*m[6] + m[7],
			v[0]*m[8] + v[1]*m[9] + v[2]*m[10] + m[11]
		];
	},
	transformNormal: function(v, m) {
		return [
			v[0]*m[0] + v[1]*m[1] + v[2]*m[2],
			v[0]*m[4] + v[1]*m[5] + v[2]*m[6],
			v[0]*m[8] + v[1]*m[9] + v[2]*m[10]
		];
	}
};

/* CT.Set: an unordered collection to which objects can be added and removed by method calls */
CT.Set = function() {
	this.currentId = 0;
	this.subjects = {};
}
CT.Set.prototype.append = function(x) {
	x.id = this.currentId++;
	x.parent = this;
	x.scene = this.scene;
	this.subjects[x.id] = x;
	return x;
}
CT.Set.prototype.remove = function(x) {
	delete(this.subjects[x.id]);
}

CT.Scene = function(canvas, opts) {
	if (typeof(canvas) == 'string') {
		this.canvas = document.getElementById(canvas);
	} else {
		this.canvas = canvas;
	}

	this.subjects = {};
	this.scene = this;
	this.ctx = this.canvas.getContext('2d');
	this.width = this.canvas.width;
	this.height = this.canvas.height;
	this.centreX = this.width / 2;
	this.centreY = this.height / 2;
	
	if (!opts) opts = {};
	this.viewAngle = CT.util.coalesce(opts.viewAngle, 1.5);
	this.verticalViewAngle = this.viewAngle * (this.height / this.width);
	this.projectionMultiplierX = (this.width / 2) / this.viewAngle;
	this.projectionMultiplierY = (this.height / 2) / this.verticalViewAngle;

	this.backgroundColour = CT.util.coalesce(opts.backgroundColour, opts.backgroundColor, '#000000');
	this.hideEdges = CT.util.coalesce(opts.hideEdges, true);
	
	this.subjects = [];
	
	this.setCamera([0,0,0], [0,0,1], [0,1,0]);
}
CT.Scene.prototype = new CT.Set();
CT.Scene.prototype.setCamera = function(pos, target, up) {
	if (!up) up = [0, 1, 0];
	var z = CT.vectors.normalise([target[0] - pos[0], target[1] - pos[1], target[2] - pos[2]]);
	var x = CT.vectors.normalise(CT.vectors.crossProduct(up, z));
	var y = CT.vectors.crossProduct(z, x);
	this.worldMatrix = [
		x[0], x[1], x[2], -CT.vectors.dotProduct(x, pos),
		y[0], y[1], y[2], -CT.vectors.dotProduct(y, pos),
		z[0], z[1], z[2], -CT.vectors.dotProduct(z, pos)
	];
	this.clearCache();
}
CT.Scene.prototype.clearCache = function() {
	for (var id in this.subjects) {
		this.subjects[id].clearCache();
	}
}

CT.Scene.prototype.render = function() {
	/* clear background */
	this.ctx.fillStyle = this.backgroundColour;
	this.ctx.fillRect(0, 0, this.canvas.width, this.canvas.height);
	
	this.lights = [];
	this.renderQueue = [];
	
	for (var id in this.subjects) {
		this.subjects[id].render();
	}

	/* now paint the things in the buffer */
	for (var i = this.renderQueue.length - 1; i >= 0; i--) {
		if (this.renderQueue[i]) {
			for (var j = 0; j < this.renderQueue[i].length; j++) {
				this.renderQueue[i][j]();
			}
		}
	}
}

CT.Scene.prototype.enqueue = function(f, z) {
	var bucket = Math.floor(z * 10);
	if (this.renderQueue[bucket]) {
		this.renderQueue[bucket].push(f);
	} else {
		this.renderQueue[bucket] = [f];
	}
}

CT.Scene.prototype.project = function(v) {
	return [
		this.centreX + v[0] * this.projectionMultiplierX / v[2],
		this.centreY - v[1] * this.projectionMultiplierY / v[2]
	];
}

CT.Scene.prototype.expandPoly = function(x0, y0, x1, y1, x2, y2) {
	/* expand 2D poly dimensions slightly to obscure sub-pixel gaps at poly edges */
	var xmid = (x0+x1+x2) / 3; var ymid = (y0+y1+y2) / 3;
	var d0 = (Math.abs(x0 - xmid) + Math.abs(y0-ymid)) / 2;
	var d1 = (Math.abs(x1 - xmid) + Math.abs(y1-ymid)) / 2;
	var d2 = (Math.abs(x2 - xmid) + Math.abs(y2-ymid)) / 2;
	x0 += (x0-xmid) / d0;	y0 += (y0-ymid) / d0;
	x1 += (x1-xmid) / d1;	y1 += (y1-ymid) / d1;
	x2 += (x2-xmid) / d2;	y2 += (y2-ymid) / d2;
	return [x0, y0, x1, y1, x2, y2];
}

CT.Scene.prototype.paintGouraudTriangle = function(x0, y0, i0, x1, y1, i1, x2, y2, i2, colour) {
	var sx, sy, si, mx, my, mi, ex, ey, ei;
	
	if (this.hideEdges) {
		var newVertices = this.expandPoly(x0, y0, x1, y1, x2, y2);
		x0 = newVertices[0]; y0 = newVertices[1];
		x1 = newVertices[2]; y1 = newVertices[3];
		x2 = newVertices[4]; y2 = newVertices[5];
	}
		
	/* sort vertices into start/midpoint/endpoint by intensity */
	if (i0 <= i1) {
		if (i1 <= i2) { /* i0 i1 i2 */
			sx = x0; sy = y0; si = i0;
			mx = x1; my = y1; mi = i1;
			ex = x2; ey = y2; ei = i2;
		} else if (i0 <= i2) { /* i0 i2 i1 */
			sx = x0; sy = y0; si = i0;
			mx = x2; my = y2; mi = i2;
			ex = x1; ey = y1; ei = i1;						
		} else { /* i2 i0 i1 */
			sx = x2; sy = y2; si = i2;
			mx = x0; my = y0; mi = i0;
			ex = x1; ey = y1; ei = i1;
		}
	} else {
		if (i0 <= i2) { /* i1 i0 i2 */
			sx = x1; sy = y1; si = i1;
			mx = x0; my = y0; mi = i0;
			ex = x2; ey = y2; ei = i2;
		} else if (i1 <= i2) { /* i1 i2 i0 */
			sx = x1; sy = y1; si = i1;
			mx = x2; my = y2; mi = i2;
			ex = x0; ey = y0; ei = i0;
		} else { /* i2 i1 i0 */
			sx = x2; sy = y2; si = i2;
			mx = x1; my = y1; mi = i1;
			ex = x0; ey = y0; ei = i0;
		}
	}
	
	if (si == ei) {
		/* need to flatshade instead */
		this.ctx.fillStyle = colour(si);
	} else {
		/* ratio of intensity increase before midpoint : intensity increase after midpoint */
		var r = (mi - si) / (ei - si);
		if (r == 0) {
			/* special case when mi = si: gradient boundary lines run parallel to edge SM,
			   so F must be the closest point to S on the boundary line through E, such that SF is perpendicular to those
			   boundary lines */
			var modms = (mx-sx)*(mx-sx) + (my-sy)*(my-sy);
			if (modms == 0) return; /* vertices are colinear */
			var u = (-(ex-sx)*(mx-sx) - (ey-sy)*(my-sy)) / modms;
			var fx = ex + u*(mx-sx); var fy = ey + u*(my-sy);
		} else {
			/* interpolate to find point I on line S-E with same intensity as point M */
			var ix = (1-r)*sx  + r*ex; var iy = (1-r)*sy + r*ey;
			
			/* find the point P on the line IM at which PS is perpendicular to IM;
			u is the coefficient satisfying P = I + u(M-I) */
			var modmi = (mx-ix)*(mx-ix) + (my-iy)*(my-iy);
			if (modmi == 0) return; /* vertices are colinear */
			var u = ((sx-ix)*(mx-ix) + (sy-iy)*(my-iy)) / modmi;
			var px = ix + u*(mx-ix); var py = iy + u*(my-iy);
			
			/* finally extend line SP by the ratio r to arrive at the final endpoint */
			var fx = sx + (px-sx)/r; var fy = sy + (py-sy)/r;
		}

		var grad = this.ctx.createLinearGradient(sx, sy, fx, fy);
		grad.addColorStop(0, colour(si));
		grad.addColorStop(1, colour(ei));
		this.ctx.fillStyle = grad;
	}

	this.ctx.beginPath();
	this.ctx.moveTo(x0, y0);
	this.ctx.lineTo(x1, y1);
	this.ctx.lineTo(x2, y2);
	this.ctx.fill();
}

CT.Transform = function() {};
CT.Transform.prototype = new CT.Set();
CT.Transform.prototype.clearCache = function() {
	this.isCached = false;
	for (var id in this.subjects) {
		this.subjects[id].clearCache();
	}
}

CT.Translate = function(x,y,z) {
	this.subjects = {};
	this.setPosition(x,y,z);
}
CT.Translate.prototype = new CT.Transform();
CT.Translate.prototype.setPosition = function(x,y,z) {
	this.position = [x,y,z];
	this.clearCache();
}
CT.Translate.prototype.render = function() {
	if (!this.isCached) {
		var m = this.parent.worldMatrix;
		this.worldMatrix = [
			m[0], m[1], m[2], m[0]*this.position[0] + m[1]*this.position[1] + m[2]*this.position[2] + m[3],
			m[4], m[5], m[6], m[4]*this.position[0] + m[5]*this.position[1] + m[6]*this.position[2] + m[7],
			m[8], m[9], m[10], m[8]*this.position[0] + m[9]*this.position[1] + m[10]*this.position[2] + m[11]
		];
		this.isCached = true;
	}
	for (var id in this.subjects) {
		this.subjects[id].render();
	}
}

CT.RotateX = function(a) {
	this.subjects = {};
	this.setRotation(a);
}
CT.RotateX.prototype = new CT.Transform();
CT.RotateX.prototype.setRotation = function(a) {
	this.rotation = a;
	this.clearCache();
}
CT.RotateX.prototype.render = function() {
	if (!this.isCached) {
		var cos_a = Math.cos(this.rotation);
		var sin_a = Math.sin(this.rotation);
		var m = this.parent.worldMatrix;
		this.worldMatrix = [
			m[0], m[1]*cos_a+m[2]*sin_a, m[2]*cos_a-m[1]*sin_a, m[3],
			m[4], m[5]*cos_a+m[6]*sin_a, m[6]*cos_a-m[5]*sin_a, m[7],
			m[8], m[9]*cos_a+m[10]*sin_a, m[10]*cos_a-m[9]*sin_a, m[11]
		];
		this.isCached = true;
	}
	for (var id in this.subjects) {
		this.subjects[id].render();
	}
}

CT.RotateY = function(a) {
	this.subjects = {};
	this.setRotation(a);
}
CT.RotateY.prototype = new CT.Transform();
CT.RotateY.prototype.setRotation = function(a) {
	this.rotation = a;
	this.clearCache();
}
CT.RotateY.prototype.render = function() {
	if (!this.isCached) {
		var cos_a = Math.cos(this.rotation);
		var sin_a = Math.sin(this.rotation);
		var m = this.parent.worldMatrix;
		this.worldMatrix = [
			m[0]*cos_a-m[2]*sin_a, m[1], m[0]*sin_a+m[2]*cos_a, m[3],
			m[4]*cos_a-m[6]*sin_a, m[5], m[4]*sin_a+m[6]*cos_a, m[7],
			m[8]*cos_a-m[10]*sin_a, m[9], m[8]*sin_a+m[10]*cos_a, m[11]
		];
		this.isCached = true;
	}
	for (var id in this.subjects) {
		this.subjects[id].render();
	}
}

CT.RotateZ = function(a) {
	this.subjects = {};
	this.setRotation(a);
}
CT.RotateZ.prototype = new CT.Transform();
CT.RotateZ.prototype.setRotation = function(a) {
	this.rotation = a;
	this.clearCache();
}
CT.RotateZ.prototype.render = function() {
	if (!this.isCached) {
		var cos_a = Math.cos(this.rotation);
		var sin_a = Math.sin(this.rotation);
		var m = this.parent.worldMatrix;
		this.worldMatrix = [
			m[0]*cos_a+m[1]*sin_a, m[1]*cos_a-m[0]*sin_a, m[2], m[3],
			m[4]*cos_a+m[5]*sin_a, m[5]*cos_a-m[4]*sin_a, m[6], m[7],
			m[8]*cos_a+m[9]*sin_a, m[9]*cos_a-m[8]*sin_a, m[10], m[11]
		];
		this.isCached = true;
	}
	for (var id in this.subjects) {
		this.subjects[id].render();
	}
}

CT.Light = function(x,y,z) {
	this.setPosition(x,y,z);
}
CT.Light.prototype.setPosition = function(x,y,z) {
	this.position = [x,y,z];
	this.isCached = false;
}
CT.Light.prototype.render = function() {
	if (!this.isCached) {
		this.worldPosition = CT.vectors.transformVector(this.position, this.parent.worldMatrix);
		this.isCached = true;
	}
	this.scene.lights.push(this.worldPosition);
}
CT.Light.prototype.clearCache = function() {
	this.isCached = false;
}

CT.Model = function(vertices, normals, polys, opts) {
	this.v = vertices;
	this.n = normals;
	this.p = polys;
	this.setOptions(opts);
}

CT.Model.prototype.setOptions = function(opts) {
	if (!opts) opts = {};
	this.colour = CT.util.coalesce(opts.colour, opts.color, CT.colour.white);
	this.ambient = CT.util.coalesce(opts.ambient, 0.2);
	this.diffuse = CT.util.coalesce(opts.diffuse, 0.8);
}

CT.Model.prototype.render = function() {
	/* TODO: Phong lighting */
	if (!this.isCached) {
		this.wv = [];
		this.wn = [];
		for (var j = 0; j < this.v.length; j++) {
			this.wv[j] = CT.vectors.transformVector(this.v[j], this.parent.worldMatrix);
		}
		for (var j = 0; j < this.n.length; j++) {
			this.wn[j] = CT.vectors.transformNormal(this.n[j], this.parent.worldMatrix);
		}
		this.isCached = true;
	}

	for (var j = 0; j < this.p.length; j++) {
		var poly = this.p[j];
		var pv = [this.wv[poly[0]], this.wv[poly[1]], this.wv[poly[2]]];
		/* clip at z=0 */
		if (pv[0][2] >= 0 && pv[1][2] >= 0 && pv[2][2] >= 0) {
			var sv0 = this.scene.project(pv[0]);
			var sv1 = this.scene.project(pv[1]);
			var sv2 = this.scene.project(pv[2]);
			if (CT.vectors.isFrontFacing(sv0,sv1,sv2)) {
				pn = [this.wn[poly[3]], this.wn[poly[4]], this.wn[poly[5]]];
				this.enqueueGouraudLambertian(pv, pn, sv0, sv1, sv2);
			}
		}
	}
}
CT.Model.prototype.enqueueGouraudLambertian = function(vert, norm, sv0, sv1, sv2) {
	var model = this;
	this.scene.enqueue(function() {
		var intensity = [];
		for (k = 0; k < 3; k++) {
			intensity[k] = model.ambient;
			for (var i = 0; i < model.scene.lights.length; i++) {
				var light = model.scene.lights[i];
				var lv = CT.vectors.normalise([light[0] - vert[k][0], light[1] - vert[k][1], light[2] - vert[k][2]]);
				var ndotl = CT.vectors.dotProduct(norm[k], lv);
				intensity[k] += model.diffuse * Math.max(0, ndotl);
			}
			if (intensity[k] > 1) { intensity[k] = 1; }
		}
		model.scene.paintGouraudTriangle(sv0[0], sv0[1], intensity[0], sv1[0], sv1[1], intensity[1], sv2[0], sv2[1], intensity[2], model.colour);
	}, (vert[0][2] + vert[1][2] + vert[2][2]) / 3);
}
CT.Model.prototype.clearCache = function() {
	this.isCached = false;
}

/* Colours */
CT.colour = {
	white: CT.util.makeColour(255,255,255),
	red: CT.util.makeColour(255,0,0),
	green: CT.util.makeColour(0,255,0),
	blue: CT.util.makeColour(0,0,255),
	yellow: CT.util.makeColour(255,255,0),
	magenta: CT.util.makeColour(255,0,255),
	cyan: CT.util.makeColour(0,255,255),
	silver: CT.util.makeColour(192,192,192),
	grey: CT.util.makeColour(128,128,128),
	gray: CT.util.makeColour(128,128,128)
};
CT.color = CT.colour;

/* Primitives */
CT.primitives = {};
CT.primitives.Box = function(opts, px0, py0, pz0, px1, py1, pz1) {
	if (!px1) px1 = 0; if (!py1) py1 = 0; if (!pz1) pz1 = 0;
	var x0 = Math.min(px0, px1); var x1 = Math.max(px0, px1);
	var y0 = Math.min(py0, py1); var y1 = Math.max(py0, py1);
	var z0 = Math.min(pz0, pz1); var z1 = Math.max(pz0, pz1);
	this.v = [
		[x0,y0,z0], [x1,y0,z0], [x1,y0,z1], [x0,y0,z1], 
		[x0,y1,z0], [x1,y1,z0], [x1,y1,z1], [x0,y1,z1]
	];
	this.n = [
		[0,-1,0], [0,0,-1], [1,0,0], [0,0,1], [-1,0,0], [0,1,0]
	];
	this.p = [ /* polys */
		[0,2,1,0,0,0], [0,3,2,0,0,0],
		[0,1,4,1,1,1], [1,5,4,1,1,1],
		[1,2,5,2,2,2], [2,6,5,2,2,2],
		[2,3,6,3,3,3], [3,7,6,3,3,3],
		[3,0,7,4,4,4], [0,4,7,4,4,4],
		[4,5,6,5,5,5], [4,6,7,5,5,5]
	];
	
	this.setOptions(opts);
}
CT.primitives.Box.prototype = CT.Model.prototype;

CT.primitives.Sphere = function(r, m, n, opts) {
	/* r = radius
	 * m = number of latitude subdivisions
	 * n = number of longitude subdivisions
	 */
	this.v = [];
	this.n = [];
	this.p = [];
	/* place vertex at north pole */
	this.v[0] = [0, r, 0]; this.n[0] = [0, 1, 0];
	/* then fill in the rest */
	for (var i = 1; i < m; i++) {
		for (var j = 0; j < n; j++) {
			var sini = Math.sin(Math.PI * i / m);
			var currentNorm = [
				sini * Math.cos(2*Math.PI*j / n),
				Math.cos(Math.PI*i/m),
				sini * Math.sin(2*Math.PI*j / n)
			];
			this.n[(i-1)*n + j + 1] = currentNorm;
			this.v[(i-1)*n + j + 1] = [r * currentNorm[0], r * currentNorm[1], r * currentNorm[2]];
		}
	}
	/* south pole */
	this.v[(m-1)*n+1] = [0, -r, 0]; this.n[(m-1)*n+1] = [0, -1, 0];
	/* now do the polys. First n polys attach to the north pole to form a cap */
	for (var i = 0; i < n; i++) {
		this.p.push([
			0, i+1, ((i+1)%n) + 1,
			0, i+1, ((i+1)%n) + 1
		]);
	}
	/* next, for each latitude row from 1 to m-2, each vertex connects to the one below it forming quads,
	and then those quads are slashed */
	for (var i = 1; i < m-1; i++) {
		var firstInRow = 1 + (i-1)*n;
		for (var j = 0; j < n; j++) {
			this.p.push([
				firstInRow + j, firstInRow + n + j, firstInRow + n + ((j+1)%n),
				firstInRow + j, firstInRow + n + j, firstInRow + n + ((j+1)%n)
			]);
			this.p.push([
				firstInRow + j, firstInRow + n + ((j+1)%n), firstInRow + ((j+1)%n),
				firstInRow + j, firstInRow + n + ((j+1)%n), firstInRow + ((j+1)%n)
			]);
		}
	}
	/* finally attach row m-1 to the south pole */
	for (var i = 0; i < n; i++) {
		this.p.push([
			1+(m-2)*n + i, 1+(m-1)*n, 1+(m-2)*n + ((i+1)%n),
			1+(m-2)*n + i, 1+(m-1)*n, 1+(m-2)*n + ((i+1)%n)
		]);
	}
	
	this.setOptions(opts);
}
CT.primitives.Sphere.prototype = CT.Model.prototype;