JS1k: The JavaScript code golfing competition

w=300;S=[H=99,[0,-H,0],9,9,0,w,4,1,[0,0,3],9,0,0,H,5,1,[-2,1,4],0,9,0,9,5,1,[2,1,4],0,0,9,H,6];A=2;T=[8,[2,2,0],];G=Math;Q=G.sqrt;v=document.body.childNodes[1];v.width=v.height=w;O=v.getContext("2d");V=O.getImageData(a=0,0,w,w);P=V.data;function d(Y,Z){return Y[0]*Z[0]+Y[1]*Z[1]+Y[2]*Z[2]}function N(B,D,L,U){W=H;for(s=n=0;r=S[n++];){F=2*(d(C=S[n],D)-d(B,D));J=2*d(D,D);if(M=Q(F*F-2*J*(d(B,B)+d(C,C)-r*r-2*d(B,C)))){for(e=2;e--;M=-M){t=(F+M)/J;if(L<t&&t<U&&t<W)s=n,W=t}}n+=6}return s}function f(Y,Z,k){return[Y[0]-Z[0]*k,Y[1]-Z[1]*k,Y[2]-Z[2]*k]}function R(B,D,L,U,p,q){if(!(g=N(B,D,L,U)))return 0;o=f(X=f(B,D,-W),S[g],1);i=A;for(l=0;u=T[l++];){j=d(o,I=f(T[l++],X,1));v=j/Q(d(I,I)*d(o,o));if(v>0&&!N(X,I,.01,1)){i+=v*u;v=G.pow(d(M=f(I,o,2*j),D)/Q(d(M,M)*d(D,D)),S[g+4]);v>0&&(i+=v*u)}}q=S[g+c]*i*2.8;k=S[g+5]/9;return p--?R(X,f(D,o,2*d(o,D)),.01,H,p)*k+q*(1-k):q}for(y=h=w/2;y-->-h;)for(x=-h;x++<h;){for(c=0;++c<4;)P[a++]=R([0,1,0],[x/w,y/w,1],1,H,2);P[a++]=255}O.putImageData(V,0,0);

dz0zMDA7Uz1bSD05OSxbMCwtSCwwXSw5LDksMCx3LDQsMSxbMCwwLDNdLDksMCwwLEgsNSwxLFstMiwxLDRdLDAsOSwwLDksNSwxLFsyLDEsNF0sMCwwLDksSCw2XTtBPTI7VD1bOCxbMiwyLDBdLF07Rz1NYXRoO1E9Ry5zcXJ0O3Y9ZG9jdW1lbnQuYm9keS5jaGlsZE5vZGVzWzFdO3Yud2lkdGg9di5oZWlnaHQ9dztPPXYuZ2V0Q29udGV4dCgiMmQiKTtWPU8uZ2V0SW1hZ2VEYXRhKGE9MCwwLHcsdyk7UD1WLmRhdGE7ZnVuY3Rpb24gZChZLFope3JldHVybiBZWzBdKlpbMF0rWVsxXSpaWzFdK1lbMl0qWlsyXX1mdW5jdGlvbiBOKEIsRCxMLFUpe1c9SDtmb3Iocz1uPTA7cj1TW24rK107KXtGPTIqKGQoQz1TW25dLEQpLWQoQixEKSk7Sj0yKmQoRCxEKTtpZihNPVEoRipGLTIqSiooZChCLEIpK2QoQyxDKS1yKnItMipkKEIsQykpKSl7Zm9yKGU9MjtlLS07TT0tTSl7dD0oRitNKS9KO2lmKEw8dCYmdDxVJiZ0PFcpcz1uLFc9dH19bis9Nn1yZXR1cm4gc31mdW5jdGlvbiBmKFksWixrKXtyZXR1cm5bWVswXS1aWzBdKmssWVsxXS1aWzFdKmssWVsyXS1aWzJdKmtdfWZ1bmN0aW9uIFIoQixELEwsVSxwLHEpe2lmKCEoZz1OKEIsRCxMLFUpKSlyZXR1cm4gMDtvPWYoWD1mKEIsRCwtVyksU1tnXSwxKTtpPUE7Zm9yKGw9MDt1PVRbbCsrXTspe2o9ZChvLEk9ZihUW2wrK10sWCwxKSk7dj1qL1EoZChJLEkpKmQobyxvKSk7aWYodj4wJiYhTihYLEksLjAxLDEpKXtpKz12KnU7dj1HLnBvdyhkKE09ZihJLG8sMipqKSxEKS9RKGQoTSxNKSpkKEQsRCkpLFNbZys0XSk7dj4wJiYoaSs9dip1KX19cT1TW2crY10qaSoyLjg7az1TW2crNV0vOTtyZXR1cm4gcC0tP1IoWCxmKEQsbywyKmQobyxEKSksLjAxLEgscCkqaytxKigxLWspOnF9Zm9yKHk9aD13LzI7eS0tPi1oOylmb3IoeD0taDt4Kys8aDspe2ZvcihjPTA7KytjPDQ7KVBbYSsrXT1SKFswLDEsMF0sW3gvdyx5L3csMV0sMSxILDIpO1BbYSsrXT0yNTV9Ty5wdXRJbWFnZURhdGEoViwwLDApOw==

// -----------------------------------------------------------------------------
//  Configuration and scene
// -----------------------------------------------------------------------------
// Size of the canvas
w = 300;

// Spheres : radius, [cx,  cy,  cz], R,  G,  B, specular exponent, reflectiveness 
// R, G, B in [0, 9], reflectiveness in [0..9]
//
S = [
		H=99,	[ 0, -H, 0],	9, 9, 0,	w,		4,	// Yellow sphere. H is used as a "big constant" - "H" < "99"
		1, 		[ 0,  0, 3], 	9, 0, 0, 	H,		5,	// Red sphere
		1, 		[-2,  1, 4],	0, 9, 0, 	9,		5,	// Green sphere
		1, 		[ 2,  1, 4], 	0, 0, 9,	H,		6	// Blue sphere
	];

// Ambient light. Hardcoding it in the lighting code feels like cheating so I won't
A = 2;

// Point lights : intensity, [x,  y,  z]
// Intensities should add to 10, including ambient
T = [
		8, [2, 2, 0],
	];

// -----------------------------------------------------------------------------

// Shorten some names
G=Math;
Q=G.sqrt;

// Get to the raw pixel data
v = document.body.childNodes[1];
v.width = v.height = w;

O = v.getContext("2d");
V = O.getImageData(a=0, 0, w, w);	// "a=0;" takes 4 bytes, doing it here saves 2 bytes
P = V.data;

// Dot product
function d(Y, Z)
{
	return Y[0]*Z[0] + Y[1]*Z[1] + Y[2]*Z[2];
}


// Find nearest intersection of the ray from B in direction D with any sphere
// "Interesting" parameter values must be in the range [L, U]
// Returns the index in S of the center of the hit sphere, or 0 if none
// The parameter value for the hit is in the global variable W
function N (B, D, L, U)
{
	W = H;	// Min distance found
	
	// For each sphere
	for (s = n = 0; r = S[n++];)	// Get the radius and test for end of array at the same time; S[n] == undefined ends the loop
	{
		// Compute quadratic equation coefficients K1, K2, K3
		F = 2*(d( C = S[n] , D) - d(B, D));	// -K2, also store the center in C
		J = 2*d(D, D);	// 2*K1
		
		// Compute sqrt(Discriminant) = sqrt(K2*K2 - 4*K1*K3), go ahead if there are solutions
		if ( M = Q( F*F - 2*J*(d(B, B) + d(C, C) - r*r - 2*d(B, C)) ) )
		{
			// Compute the two solutions
			for (e = 2; e--; M = -M)	// TODO : I have a feeling this loop can be minimized further, but I can't figure it out
			{
				t = (F + M)/J;
				if (L < t && t < U && t < W) 
					s=n, W=t;
			}
		}
		
		n += 6;
	}

	// Return index of closest sphere in range; W is global
	return s;
}


// Helper : f(Y, Z, k)  =  Y - Z*k. Since f is used more with k < 0, using - here
// saves a couple of bytes later
function f (Y, Z, k)
{
	return [Y[0] - Z[0]*k, Y[1] - Z[1]*k, Y[2] - Z[2]*k];
}


// Trace the ray from B with direction D considering hits in [L, U]
// If p > 0, trace recursive reflection rays
// Returns the value of the current color channel as "seen" through the ray
// q is a fake parameter used to avoid using "var" below
function R (B, D, L, U, p, q)
{
	// Find nearest hit; if no hit, return black
	if (!(g = N(B, D, L, U)))
		return 0;
	
	// Compute "normal" at intersection : o = X - S[g]
	o = f( 
		X = f(B, D, -W), 	// Compute intersection : X = B + D*W = B - D*(-W)
		S[g], 1);

	// Start with ambient light only
	i = A;
	
	// For each light
	for (l = 0; u = T[l++]; )	// Get intensity and check for end of array
	{
		// Compute vector from intersection to light (I = T[l++] - X) and 
		// j = <N,L> (reused below)
		j = d(o, I = f(T[l++], X, 1) );

		// V = <N,L> / (|L|*|N|) = cos(alpha)
		// Also, |N|*|L| = sqrt(<N,N>)*sqrt(<L,L>) = sqrt(<N,N>*<L,L>)
		v = j / Q(d(I, I)*d(o, o));
		
		// Add diffuse contribution only if it's facing the point 
		// (cos(alpha) > 0) and no other sphere casts a shadow
		// [L, U]  =  [epsilon,  1] - epsilon avoids self-shadow, 1 doesn't look 
		// farther than the light itself
		if (v > 0 && !N(X, I, .01, 1))
		{
			i += v*u;

			// Specular highlights
			//
			// specular = (<R,V>   / (|R|*|V|))   ^ exponent
			//			= (<-R,-V> / (|-R|*|-V|)) ^ exponent
			//			= (<-R,D>  / (|-R|*|D|))  ^ exponent
			//
			// R = 2*N*<N,I> - I
			// M = -R = -2*o*<o,I> + I = I + o*(-2*<o,I>)
			//
			v = G.pow( d( M = f(I, o, 2*j), D)/ Q(d(M, M)*d(D, D)), S[g+4]);

			// Add specular contribution only if visible
			v > 0 && 
				(i += v*u);
		}
	}
	

	// Compute the color channel multiplied by the light intensity. 2.8 "fixes"
	// the color range in [0, 9] instead of [0, 255] and the intensity in [0, 10]
	// instead of [0, 1],  because 2.8 ~ (255/9)/10
	// 
	// S[g] = sphere center, so S[g+c] = color channel c (c = [1..3] because a=c++ below)
	q = S[g+c]*i*2.8;
	
	// If the recursion limit hasn't been hit yet, trace reflection rays
	// o = normal
	// D = -view
	// M = 2*N*<N,V> - V = 2*o*<o,-D> + D = D - o*(2*<o,D>)
	k = S[g+5]/9;

	return p--  ? R(X, f(D, o, 2*d(o, D)), .01, H, p)*k + q*(1-k)
				: q;
}

// For each y; also compute h=w/2 without paying an extra ";"
for (y = h=w/2; y-- > -h;)

	// For each x
	for (x = -h; x++ < h;)
	{
		// For each color channel
		for (c = 0; ++c < 4;)
			// Camera is at (0, 1, 0)
			//
			// Ray direction is (x*vw/cw, y*vh/ch, 1) where vw = viewport width, 
			// cw = canvas width (vh and ch are the same for height). vw is fixed
			// at 1 so (x/w, y/w, 1)
			//
			// [L, U] = [1, H], 1 starts at the projection plane, H is +infinity
			//
			// 2 is a good recursion depth to appreciate the reflections without
			// slowing things down too much
			//
			P[a++] = R([0, 1, 0], [x/w, y/w, 1], 1, H, 2);
			
		P[a++] = 255; // Opaque alpha
	}

O.putImageData(V, 0, 0);