Decompressing Data with the DEFLATE Algorithm in JavaScript

The code below, when run, prompts the user to upload a compressed file in GZIP format, which will then be uncompressed, and the uncompressed data will be displayed both as hexadecimal digits and as UTF8 text.

This implementation of DEFLATE is basically a port of a Java implementation created by Nyuki Minase, an edited Java version of which I presented in a previous post. I tried to leave the code in this port as nearly identical as possible, but I had to make a few questionable changes here and there. The most distressing of these is where I commented out the writing of data to the output byte stream in Decompressor.decodeHuffmanBlock(), because it seemed to be appending nonsense to the end of my test data. But no doubt it was there for a reason. It should go without saying that any bugs in this implementation should be assumed to be my own.

I tested the program by creating a simple .txt file and compressing it to a .gz with 7-Zip.

Note that this implementation only does decompression, not compression.

decompressingwithdeflate


<html>
<body>

<!-- ui -->

	<div>
		<div><label>Compressed Bytes as Hexadecimal:</label></div>
		<div><input type="file" onchange="inputCompressedDataLoadFromFile_Changed(this);"></input></div>
		<div><textarea id="textareaCompressed" cols="32" rows="8"></textarea></div>
	</div>

	<div>
		<button onclick="buttonDecompress_Clicked();">Decompress</button>
	</div>

	<div>
		<div><label>Uncompressed Bytes as Hexadecimal:</label></div>
		<div><textarea id="textareaUncompressed" cols="32" rows="8"></textarea></div>

		<div><label>Uncompressed Bytes as Text (UTF8):</label></div>
		<div><textarea id="textareaUncompressedAsUTF8" cols="32" rows="8"></textarea></div>
	</div>

<!-- ui ends -->

<script type="text/javascript">

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.removeAt = function(index)
	{
		this.splice(index, 1);
		return this;
	}
}

function StringExtensions()
{
	// extension class
}
{
	String.prototype.padLeft = function(charToPadWith, lengthToPadTo)
	{
		var returnValue = this;
		while (returnValue.length < lengthToPadTo)
		{
			returnValue = charToPadWith + returnValue;
		}
		return returnValue;
	}
}

// ui events

function buttonDecompress_Clicked()
{
	var textareaCompressed = document.getElementById("textareaCompressed");	
	var bytesCompressedAsHexadecimal = textareaCompressed.value;
	var bytesCompressed = [];
	for (var i = 0; i < bytesCompressedAsHexadecimal.length; i += 2)
	{
		var byteAsHexadecimal = bytesCompressedAsHexadecimal.substr(i, 2);
		var byte = parseInt(byteAsHexadecimal, 16);
		bytesCompressed.push(byte);
	}

	var inflator = new Inflator();
	var bytesDecompressed = inflator.decompressBytes(bytesCompressed);

	var bytesDecompressedAsHexadecimal = "";
	var bytesDecompressedAsUTF8 = "";
	for (var i = 0; i < bytesDecompressed.length; i++)
	{
		var byte = bytesDecompressed[i];

		var byteAsHexadecimal = byte.toString(16).padLeft("0", 2);
		bytesDecompressedAsHexadecimal += byteAsHexadecimal;

		var byteAsUTF8 = String.fromCharCode(byte);
		bytesDecompressedAsUTF8 += byteAsUTF8;
	}

	var textareaUncompressed = document.getElementById("textareaUncompressed");
	textareaUncompressed.value = bytesDecompressedAsHexadecimal;

	var textareaUncompressedAsUTF8 = document.getElementById("textareaUncompressedAsUTF8");
	textareaUncompressedAsUTF8.value = bytesDecompressedAsUTF8;

}

function inputCompressedDataLoadFromFile_Changed(input)
{
	var file = input.files[0];
	var fileReader = new FileReader();
	fileReader.onload = function(event)
	{
		var fileContentsAsBinaryString = event.target.result;
		var bytesCompressed = fileContentsAsBinaryString;
		var bytesCompressedAsHexadecimal = "";
		for (var i = 0; i < bytesCompressed.length; i++)
		{
			var byte = bytesCompressed.charCodeAt(i);
			var byteAsHexadecimal = byte.toString(16).padLeft("0", 2);
			bytesCompressedAsHexadecimal += byteAsHexadecimal;
		}
		var textareaCompressed = document.getElementById("textareaCompressed");
		textareaCompressed.value = bytesCompressedAsHexadecimal;
	}
	fileReader.readAsBinaryString(file);
}

// DEFLATE implementation

// Most of the code below is a port 
// of a Java implementation of DEFLATE written by Nyuki Minase.

/*(MIT License)

Copyright © 2012 Nayuki Minase
Copyright © 2017 This Could Be Better

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:

* The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

* The Software is provided "as is", without warranty of any kind, express or
  implied, including but not limited to the warranties of merchantability,
  fitness for a particular purpose and noninfringement. In no event shall the
  authors or copyright holders be liable for any claim, damages or other
  liability, whether in an action of contract, tort or otherwise, arising from,
  out of or in connection with the Software or the use or other dealings in the
  Software.

*/

// main

function Inflator()
{
	// do nothing
}
{
	Inflator.prototype.decompressBytes = function(fileContentsAsBytes)
	{	
		var input = new BitStream(fileContentsAsBytes);

		let magicNumberForGZIP = input.readInteger16LE();
		if (magicNumberForGZIP != 35615)
			throw "Invalid GZIP magic number";

		var compressionMethodCode = input.readByte();
		if (compressionMethodCode != 8)
			throw "Unsupported compression method: " + (compressionMethodCode & 0xFF);

		var flags = input.readByte();

		// Reserved flags
		if ((flags & 0xE0) != 0)
			throw "Reserved flags are set";

		// Modification time
		var mtime = input.readInteger32LE();
		if (mtime != 0)
		{
			//console.log("Last modified: " + new DateTime(1970, 1, 1).add(mtime * 1000000L));
		}
		else
		{
			console.log("Last modified: N/A");
		}

		var extraFlags = input.readByte();

		// Extra flags
		switch (extraFlags) 
		{
			case 2:   console.log("Extra flags: Maximum compression");  break;
			case 4:   console.log("Extra flags: Fastest compression");  break;
			default:  console.log("Extra flags: Unknown");  break;
		}

		// Operating system
		var osCode = input.readByte();
		var os;
		switch (osCode & 0xFF) 
		{
			case   0:  os = "FAT";             break;
			case   1:  os = "Amiga";           break;
			case   2:  os = "VMS";             break;
			case   3:  os = "Unix";            break;
			case   4:  os = "VM/CMS";          break;
			case   5:  os = "Atari TOS";       break;
			case   6:  os = "HPFS";            break;
			case   7:  os = "Macintosh";       break;
			case   8:  os = "Z-System";        break;
			case   9:  os = "CP/M";            break;
			case  10:  os = "TOPS-20";         break;
			case  11:  os = "NTFS";            break;
			case  12:  os = "QDOS";            break;
			case  13:  os = "Acorn RISCOS";    break;
			case 255:  os = "Unknown";         break;
			default :  os = "Really unknown";  break;
		}
		console.log("Operating system: " + os);

		// Text flag
		if ((flags & 0x01) != 0)
		{
			console.log("Flag: Text");
		}

		// Extra flag
		if ((flags & 0x04) != 0) 
		{
			console.log("Flag: Extra");
			var len = input.readInteger16LE();
			input.readBytes(len);  // Skip extra data
		}

		// File name flag
		if ((flags & 0x08) != 0) 
		{
			var sb = "";
			while (true) 
			{
				var temp = input.readByte();
				if (input.hasMoreBits() == false)
					throw "EOFException";
				else if (temp == 0)  // Null-terminated string
					break;
				else
					sb += String.fromCharCode(temp);
			}
			console.log("File name: " + sb);
		}

		// Header CRC flag
		if ((flags & 0x02) != 0) {
			
			var crc = input.readInteger16LE(2);
			console.log("Header CRC-16: %04X%n", crc);
		}

		// Comment flag
		if ((flags & 0x10) != 0) {
			var sb = "";
			while (true) {
				var temp = input.readByte();
				if (input.hasMoreBits() == false)
					throw "EOFException";
				else if (temp == 0)  // Null-terminated string
					break;
				else
					sb += String.fromCharCode(temp);
			}
			console.log("Comment: " + sb);
		}

		// Decompress
		var bytesDecompressed = Decompressor.decompress
		(
			input
		);

		return bytesDecompressed;
	}
}

// classes

function BitStream(bytes)
{
	this.bytes = bytes;
	this.byteIndex = 0;
	this.bitOffsetWithinByte = 0;
}
{
	BitStream.prototype.alignWithByteBoundary = function()
	{
		if (this.bitOffsetWithinByte != 0)
		{
			this.bitOffsetWithinByte = 0;
			this.byteIndex++;
		}
	}

	BitStream.prototype.hasMoreBits = function()
	{
		return (this.byteIndex < this.bytes.length);
	}

	BitStream.prototype.readBit = function()
	{
		var byteCurrent = this.bytes[this.byteIndex];
		var returnValue = (byteCurrent >> (8 - this.bitOffsetWithinByte - 1)) & 0x1;
		this.bitOffsetWithinByte++;
		if (this.bitOffsetWithinByte >= 8)
		{
			this.bitOffsetWithinByte = 0;
			this.byteIndex++;
		}
		return returnValue;
	}

	BitStream.prototype.readBits = function(numberOfBits)
	{
		var returnValues = [];	

		for (var i = 0; i < numberOfBits; i++)
		{
			var bit = this.readBit();
			returnValues.push(bit);
		}

		return returnValues;
	}

	BitStream.prototype.readByte = function()
	{
		var returnValue = this.bytes[this.byteIndex];
		this.byteIndex++;
		return returnValue;
	}

	BitStream.prototype.readBytes = function(numberOfBytes)
	{
		var returnValues = [];

		for (var i = 0; i < numberOfBytes; i++)
		{
			var byte = this.bytes[this.byteIndex];
			returnValues.push(byte);
			this.byteIndex++;
		}

		return returnValues;
	}


	BitStream.prototype.readIntegerOfBitWidthLE = function(numberOfBits)
	{
		var returnValue = 0;

		var bits = this.readBits(numberOfBits);
		for (var i = 0; i < bits.length; i++)
		{
			var bit = bits[i];
			var bitValueInPlace = bit << i;
			returnValue = returnValue | bitValueInPlace;
		}

		return returnValue;
	}

	BitStream.prototype.readInteger16LE = function()
	{
		// 16-bit, little-endian

		var bytes = this.readBytes(2);
		var returnValue = bytes[0] | (bytes[1] << 8);
		return returnValue;
	}

	BitStream.prototype.readInteger32LE = function()
	{
		// 32-bit, little-endian

		var bytes = this.readBytes(4);
		var returnValue = 
			bytes[0] 
			| (bytes[1] << 8) 
			| (bytes[2] << 16) 
			| (bytes[3] << 24);
		return returnValue;
	}

	BitStream.prototype.writeByte = function(byte)
	{
		this.bytes.push(byte);
		this.byteIndex = this.bytes.length;
	}

	BitStream.prototype.writeBytes = function(bytesToWrite)
	{
		for (var i = 0; i < bytesToWrite.length; i++)
		{
			var byte = bytesToWrite[i];
			this.bytes.push(byte);
		}
		this.byteIndex = this.bytes.length;
	}
}

function CanonicalCode(codeLengths)
{

	if (codeLengths == null)
	{
		throw "Argument is null";
	}

	this.codeLengths = codeLengths.slice(0);
	for (var i = 0; i < codeLengths.length; i++) 
	{
		var x = codeLengths[i];
		if (x < 0)
		{
			throw "Illegal code length";
		}
	}
}
{
	// static classes 

	CanonicalCode.constructor2 = function(tree, symbolLimit) 
	{
		var codeLengths = new Array(symbolLimit);
		var returnValue = new CanonicalCode(codeLengths);
		returnValue.buildCodeLengths(tree.root, 0);
	}

	CanonicalCode.prototype.buildCodeLengths = function(node, depth) 
	{
		if (node.constructor.name == "InternalNode") 
		{
			var internalNode = node;
			this.buildCodeLengths(internalNode.leftChild , depth + 1);
			this.buildCodeLengths(internalNode.rightChild, depth + 1);
		} 
		else if (node.constructor.name == "Leaf") 
		{
			var symbol = node.symbol;
			if (codeLengths[symbol] != 0)
			{
				throw "Symbol has more than one code"; 
			}
			if (symbol >= codeLengths.length)
			{
				throw "Symbol exceeds symbol limit";
			}
			this.codeLengths[symbol] = depth;
		} 
		else 
		{
			throw "Illegal node type";
		}
	}

	CanonicalCode.prototype.getSymbolLimit = function() 
	{
		return this.codeLengths.length;
	}

	CanonicalCode.prototype.getCodeLength = function(symbol) 
	{
		if (symbol < 0 || symbol >= this.codeLengths.length)
		{
			throw "Symbol out of range";
		}
		return this.codeLengths[symbol];
	}

	CanonicalCode.prototype.toCodeTree = function() 
	{
		var nodes = [];
		for (var i = this.max(this.codeLengths); i >= 1; i--) 
		{  
			// Descend through positive code lengths
			var newNodes = [];

			// Add leaves for symbols with code length i
			for (var j = 0; j < this.codeLengths.length; j++) {
				if (this.codeLengths[j] == i)
					newNodes.push(new Leaf(j));
			}

			// Merge nodes from the previous deeper layer
			for (var j = 0; j < nodes.length; j += 2)
			{
				newNodes.push(new InternalNode(nodes[j], nodes[j + 1]));
			}

			nodes = newNodes;
			if (nodes.length % 2 != 0)
			{
				throw "This canonical code does not represent a Huffman code tree";
			}
		}

		if (nodes.length != 2)
		{
			throw "This canonical code does not represent a Huffman code tree";
		}
		return new CodeTree(new InternalNode(nodes[0], nodes[1]), this.codeLengths.length);
	}

	CanonicalCode.prototype.max = function(array) 
	{
		var result = array[0];
		for (var i = 0; i < array.length; i++)
		{
			var x = array[i];
			result = Math.max(x, result);
		}
		return result;
	}	
}

function CircularDictionary(size)
{
	this.data = new Array(size);
	this.index = 0;

	if (IntegerMath.isPowerOf2(size))
	{
		this.mask = size - 1;
	}
	else
	{
		this.mask = 0;
	}
}
{
	CircularDictionary.prototype.append = function(b) 
	{
		this.data[this.index] = b;
		if (this.mask != 0)
			this.index = (this.index + 1) & this.mask;
		else
			this.index = (this.index + 1) % this.data.length;
	}

	CircularDictionary.prototype.copy = function(dist, len, out)
	{
		if (len < 0 || dist < 1 || dist > this.data.length)
		{
			throw "IllegalArgumentException";
		}

		if (this.mask != 0) 
		{
			var readIndex = (this.index - dist + this.data.length) & this.mask;
			for (var i = 0; i < len; i++) 
			{
				out.write(this.data[readIndex]);
				this.data[this.index] = this.data[readIndex];
				readIndex = (readIndex + 1) & this.mask;
				this.index = (this.index + 1) & this.mask;
			}
		} 
		else 
		{
			var readIndex = (this.index - dist + this.data.length) % this.data.length;
			for (var i = 0; i < len; i++) 
			{
				out.write(this.data[readIndex]);
				this.data[this.index] = this.data[readIndex];
				readIndex = (readIndex + 1) % this.data.length;
				this.index = (this.index + 1) % this.data.length;
			}
		}
	}	
}

function CodeTree(root, symbolLimit)
{
	// public final InternalNode root;  // Not null

	// Stores the code for each symbol, or null if the symbol has no code.
	// For example, if symbol 5 has code 10011, then codes.get(5) is the list [1, 0, 0, 1, 1].
	// private List<List<Integer>> codes;

	// Every symbol in the tree 'root' must be strictly less than 'symbolLimit'.

	if (root == null)
	{
		throw "Argument is null";
	}
	this.root = root;

	this.codes = [];  // Initially all null
	for (var i = 0; i < symbolLimit; i++)
	{
		this.codes.push(null);
	}

	this.buildCodeList(root, []);  // Fills 'codes' with appropriate data
}
{
	CodeTree.prototype.buildCodeList = function(node, prefix) 
	{
		var nodeConstructorName = node.constructor.name;
		if (nodeConstructorName == "InternalNode") 
		{
			var internalNode = node;

			prefix.push(0);
			this.buildCodeList(internalNode.leftChild , prefix);
			prefix.removeAt(prefix.length - 1);

			prefix.push(1);
			this.buildCodeList(internalNode.rightChild, prefix);
			prefix.removeAt(prefix.length - 1);	
		} 
		else if (nodeConstructorName == "Leaf") 
		{
			var leaf = node;
			if (leaf.symbol >= this.codes.length)
			{
				throw "Symbol exceeds symbol limit";
			}
			if (this.codes[leaf.symbol] != null)
			{
				throw "Symbol has more than one code";
			}
			this.codes[leaf.symbol] = new Array(prefix); // ?
		} 
		else 
		{
			throw "Illegal node type";
		}
	}

	CodeTree.prototype.getCode = function(symbol) 
	{
		if (symbol < 0)
		{
			throw new "Illegal symbol";
		}
		else if (this.codes[symbol] == null)
		{
			throw "No code for given symbol";
		}
		else
		{
			return this.codes[symbol];
		}
	}

	// Returns a string showing all the codes in this tree. The format is subject to change. Useful for debugging.
	CodeTree.prototype.toString = function() 
	{
		var sb = "";
		sb = this.toString2("", root, sb);
		return sb;
	}

	CodeTree.prototype.toString2 = function(prefix, node, sb) 
	{
		var nodeConstructorName = node.constructor.name;
		if (nodeConstructorName == "InternalNode") 
		{
			var internalNode = node;
			sb = this.toString2(prefix + "0", internalNode.leftChild , sb);
			sb = this.toString2(prefix + "1", internalNode.rightChild, sb);
		} 
		else if (nodeConstructorName == "Leaf") 
		{
			sb += String.format("Code %s: Symbol %d%n", prefix, node.symbol);
		} 
		else 
		{
			throw "Illegal node type";
		}

		return sb;
	}	
}

function InternalNode(leftChild, rightChild)
{
	if (leftChild == null || rightChild == null)
	{
		throw "Argument is null";
	}
	this.leftChild = leftChild;
	this.rightChild = rightChild;
}

function Leaf(symbol)
{	
	if (symbol < 0)
		throw "Illegal symbol value";
	this.symbol = symbol;
}

function Decompressor(input)
{
	// These were formerly static variables.

	var llcodelens = new Array(288);
	llcodelens.fill(8, 0, 144);
	llcodelens.fill(9, 144, 256);
	llcodelens.fill(7, 256, 280);
	llcodelens.fill(8, 280, 288);
	this.llcodelens = llcodelens;

	this.fixedLiteralLengthCode = new CanonicalCode(llcodelens).toCodeTree();
	this.distcodelens = new Array(32);

	this.distcodelens.fill(5);
	this.fixedDistanceCode = new CanonicalCode(this.distcodelens).toCodeTree();

	// The original constructor picks up here.

	this.input = input;
	this.output = new BitStream([]);
	this.dictionary = new CircularDictionary(32 * 1024);

	// Process the stream of blocks
	while (true) 
	{
		// Block header
		var isFinal = (input.readBit() == 1);  // bfinal
		var type = input.readIntegerOfBitWidthLE(2); // btype

		// Decompress by type
		if (type == 0)
		{
			this.decompressUncompressedBlock();
		}
		else if (type == 1 || type == 2) 
		{
			var litLenCode, distCode;
			if (type == 1) 
			{
				litLenCode = this.fixedLiteralLengthCode;
				distCode = this.fixedDistanceCode;
			} 
			else 
			{
				var temp = this.decodeHuffmanCodes(input);
				litLenCode = temp[0];
				distCode = temp[1];
			}

			this.decompressHuffmanBlock(litLenCode, distCode);	
		} 
		else if (type == 3)
		{
			throw "Invalid block type";
		}
		else
		{
			throw "AssertionError";
		}

		if (isFinal)
		{
			break;
		}
	}
}
{	
	// static methods

	/* Public method */
	Decompressor.decompress = function(input)
	{
		var decompressor = new Decompressor(input);
		return decompressor.output.bytes;
	}

	// For handling static Huffman codes (btype = 1)
	Decompressor.fixedLiteralLengthCode = null; // todo
	Decompressor.fixedDistanceCode = null; // todo

	// For handling dynamic Huffman codes (btype = 2)
	Decompressor.prototype.decodeHuffmanCodes = function(input)
	{
		var numLitLenCodes = input.readIntegerOfBitWidthLE(5) + 257;  // hlit  + 257
		var numDistCodes = input.readIntegerOfBitWidthLE(5) + 1;      // hdist +   1

		var numCodeLenCodes = input.readIntegerOfBitWidthLE(4) + 4;   // hclen +   4
		var codeLenCodeLen = new Array(19);
		codeLenCodeLen[16] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[17] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[18] = input.readIntegerOfBitWidthLE(3);
		codeLenCodeLen[ 0] = input.readIntegerOfBitWidthLE(3);
		for (var i = 0; i < numCodeLenCodes - 4; i++) 
		{
			if (i % 2 == 0)
				codeLenCodeLen[8 + i / 2] = input.readIntegerOfBitWidthLE(3);
			else
				codeLenCodeLen[7 - i / 2] = input.readIntegerOfBitWidthLE(3);
		}
		var codeLenCode = new CanonicalCode(codeLenCodeLen).toCodeTree();

		var codeLens = new Array(numLitLenCodes + numDistCodes);
		var runVal = -1;
		var runLen = 0;
		for (var i = 0; i < codeLens.length; i++) 
		{
			if (runLen > 0) 
			{
				codeLens[i] = runVal;
				runLen--;	
			} 
			else 
			{
				var sym = this.decodeSymbol(codeLenCode);
				if (sym < 16) 
				{
					codeLens[i] = sym;
					runVal = sym;
				} 
				else 
				{
					if (sym == 16) 
					{
						if (runVal == -1)
						{
							throw "No code length value to copy";
						}
						runLen = input.readIntegerOfBitWidthLE(2) + 3;
					} 
					else if (sym == 17) 
					{
						runVal = 0;
						runLen = input.readIntegerOfBitWidthLE(3) + 3;
					} 
					else if (sym == 18) 
					{
						runVal = 0;
						runLen = input.readIntegerOfBitWidthLE(7) + 11;
					} 
					else
					{
						throw "AssertionError";
					}

					i--;
				}
			}
		}
		if (runLen > 0)
		{
			throw "Run exceeds number of codes";
		}

		// Create code trees
		var litLenCodeLen = codeLens.slice(0, numLitLenCodes); // ?
		var litLenCode = new CanonicalCode(litLenCodeLen).toCodeTree();

		var distCodeLen = codeLens.slice(numLitLenCodes, codeLens.length); // ?
		var distCode;
		if (distCodeLen.length == 1 && distCodeLen[0] == 0)
		{
			distCode = null;  // Empty distance code; the block shall be all literal symbols
		}
		else
		{
			distCode = new CanonicalCode(distCodeLen).toCodeTree();
		}

		return [litLenCode, distCode];
	}

	/* Block decompression methods */

	Decompressor.prototype.decompressUncompressedBlock = function()
	{
		// Discard bits to align to byte boundary
		this.input.alignWithByteBoundary();

		// Read length
		var len  = this.input.readInteger16LE();
		var nlen = this.input.readInteger16LE();
		var nlenCalculated = len ^ 0xFFFF; 
		if (nlenCalculated != nlen) 
		{
			throw "Invalid length in uncompressed block";
		}

		// Copy bytes
		for (var i = 0; i < len; i++) 
		{
			var temp = this.input.readByte();
			if (this.input.hasMoreBits() == false)
			{
				throw "EOFException";
			}
			this.output.writeByte(temp);
			this.dictionary.append(temp);
		}
	}

	Decompressor.prototype.decompressHuffmanBlock = function(litLenCode, distCode)
	{
		if (litLenCode == null)
		{
			throw "NullPointerException";
		}

		while (true) 
		{
			var sym = this.decodeSymbol(litLenCode);
			if (sym == 256)  // End of block
			{
				break;
			}

			if (sym < 256) 
			{  
				// Literal byte

				// Leaving the next line in
				// causes strange junk to appear 
				// at the end of the uncompressed data.
				// Not sure what's going on.
				//this.output.writeByte(sym);

				this.dictionary.append(sym);
			} 
			else 
			{  // Length and distance for copying
				var len = this.decodeRunLength(sym);
				if (distCode == null)
				{
					throw "Length symbol encountered with empty distance code";
				}
				var distSym = this.decodeSymbol(distCode);
				var dist = this.decodeDistance(distSym);
				this.dictionary.copy(dist, len, output);
			}
		}
	}

	/* Symbol decoding methods */
	Decompressor.prototype.decodeSymbol = function(code)
	{
		var currentNode = code.root;
		while (true) 
		{
			var temp = this.input.readBit();
			var nextNode;
			if (temp == 0)
			{			
				nextNode = currentNode.leftChild;
			}
			else if (temp == 1)
			{
				nextNode = currentNode.rightChild;
			}
			else
			{
				throw "AssertionError";
			}

			var nextNodeConstructorName = nextNode.constructor.name;
			if (nextNodeConstructorName == "Leaf")
			{
				return nextNode.symbol;
			}
			else if (nextNodeConstructorName == "InternalNode")
			{
				currentNode = nextNode;
			}
			else
			{
				throw "AssertionError";
			}
		}
	}

	Decompressor.prototype.decodeRunLength = function(sym)
	{
		if (sym < 257 || sym > 285)
		{
			throw "Invalid run length symbol: " + sym;
		}
		else if (sym <= 264)
		{
			return sym - 254;
		}
		else if (sym <= 284) 
		{
			var i = (sym - 261) / 4;  // Number of extra bits to read
			return (((sym - 265) % 4 + 4) << i) + 3 + input.readIntegerOfBitWidthLE(i);
		} 
		else  // sym == 285
		{
			return 258;
		}
	}

	Decompressor.prototype.decodeDistance = function(sym)
	{
		if (sym <= 3)
		{
			return sym + 1;
		}
		else if (sym <= 29) 
		{
			var i = sym / 2 - 1;  // Number of extra bits to read
			return ((sym % 2 + 2) << i) + 1 + input.readIntegerOfBitWidthLE(i);
		} 
		else
		{
			throw "Invalid distance symbol: " + sym;
		}
	}
}

function IntegerMath()
{
	// static class
}
{
	IntegerMath.isPowerOf2 = function(valueToCheck)
	{
		return ((Math.log(valueToCheck) / Math.log(2)) % 0) == 0;
	}
}

</script>
</body>
</html>

Posted in Uncategorized | Tagged , , , , | Leave a comment

Rendering to Texture with WebGL

The JavaScript program below, when run, will display a simple three-dimensional scene rendered with WebGL. It is nearly identical to a program from a previous post, except that this version demonstrates how to render a scene to a texture, rather than directly to the screen. This texture can then be used to texture another mesh within the scene.

This technique of “rendering to texture” is frequently used to model some advanced effects in a 3D scene, such as representing television screens or mirrors. It is also used as the first step in “shadow mapping”, which is a means of adding shadows to a scene by “rendering” it from the point of view of each light source, into a special texture called a “depth map”, and then using that depth map to determine whether a particular pixel in the camera’s view is in shadow or not. This code does not attempt to perform shadow mapping, though it is intended as a first step in that direction.

To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript. Use the W, A, S, D, Z, C, E and R keys to move the camera around, and press the Enter key to create a snapshot of the current view, which will then be added as another object in the scene.

UPDATE 2017/02/10 – Adapting this code to do shadow mapping has proven at least as difficult as I imagined. In the face of this continuing difficulty, I have refactored this code somewhat to make debugging easier. Notably, I have added an option to also render the scene as a simple wireframe without using WebGL for comparison purposes, added some further abstraction around the WebGL shader functionality, and simplified the code that builds the camera’s perspective matrix for WebGL.

webglscenerenderedtotexture


<html>
<body>

<script type="text/javascript">

// main

function WebGLTest()
{
	this.main = function()
	{
		var imageTextGL = ImageHelper.buildImageFromStrings
		(
			"ImageTextGL",
			8, // scaleMultiplier
			[
				"RRRRRRRRRRRRRRRR",
				"RRcccccRcRRRRRcR",
				"RRcRRRRRcRRRRRcR",
				"RRcRRRRRcRRRRRcR",
				"RRcRcccRcRRRRRcR",
				"RRcRRRcRcRRRRRRR",
				"RRcccccRcccccRcR",
				"RRRRRRRRRRRRRRRR",
			]
		);

		Globals.Instance.mediaHelper.loadImages
		(
			[ imageTextGL ],
			this.main2
		);
	}

	this.main2 = function(event)
	{
		var mediaHelper = Globals.Instance.mediaHelper;

		var displaySize = new Coords(320, 240, 2000);

		var scene = new DemoData().scene(mediaHelper, displaySize);

		var displays = 
		[
			//new Display2D(displaySize),
			new DisplayWebGL(displaySize),
		];

		Globals.Instance.initialize
		(
			displays,
			scene
		);
	}
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var key = element[keyName];
			this[key] = element;
		}

		return this;
	}

	Array.prototype.append = function(other)
	{
		for (var i = 0; i < other.length; i++)
		{
			var element = other[i];
			this.push(element);
		}

		return this;
	}

	// cloneable

	Array.prototype.clone = function()
	{
		var elementsCloned = [];

		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var elementCloned = element.clone();
			elementsCloned.push(elementCloned);
		}

		return elementsCloned;
	}

	Array.prototype.overwriteWith = function(other)
	{
		for (var i = 0; i < this.length; i++)
		{
			var elementThis = this[i];
			var elementOther = other[i];
			elementThis.overwriteWith(elementOther);
		}

		return this;
	}
}

// classes

function Body(name, defn, pos, orientation)
{
	this.name = name;
	this.defn = defn;
	this.pos = pos;
	this.orientation = orientation;
}
{
	Body.prototype.meshTransformed = function()
	{
		if (this._meshTransformed == null)
		{
			this._meshTransformed = this.defn.mesh.clone();

			this.transformLocate = new TransformMultiple
			([
				new TransformOrient(this.orientation),
				new TransformTranslate(this.pos),
			])
		}
		else
		{
			this._meshTransformed.overwriteWith(this.defn.mesh);
		}

		Transform.transformApplyToCoordsMany
		(
			this.transformLocate,
			this._meshTransformed.vertexPositions
		);

		return this._meshTransformed;
	}
	
	// WebGL

	Body.prototype.drawToWebGLContext = function(webGLContext, scene)
	{
		this.defn.mesh.drawToWebGLContext(webGLContext, scene);
	}
}

function BodyDefn(name, mesh)
{
	this.name = name;
	this.mesh = mesh;
}

function Camera(viewSize, focalLength, pos, orientation)
{
	this.viewSize = viewSize;
	this.focalLength = focalLength;
	this.pos = pos;
	this.orientation = orientation;

	this.viewSizeHalf = this.viewSize.clone().divideScalar(2);
}
{
	Camera.prototype.toString = function()
	{
		var returnValue = "<Camera "
			+ "pos='" + this.pos.toString() + "' "
			+ ">" 
			+ this.orientation.toString()
			+ "</Camera>";

		return returnValue;
	}
}

function Color(name, codeChar, systemColor, componentsRGBA)
{
	this.name = name;
	this.codeChar = codeChar;
	this.systemColor = systemColor;
	this.componentsRGBA = componentsRGBA;
}
{
	// constants

	Color.NumberOfComponentsRGBA = 4;

	// instances

	function Color_Instances()
	{
		this.Transparent = new Color("Transparent", ".", "rgba(0, 0, 0, 0)", [0, 0, 0, 0]);

		this.Black 	= new Color("Black",	"k", "Black", [0, 0, 0, 1]);
		this.Blue 	= new Color("Blue", 	"b", "Blue", [0, 0, 1, 1]);
		this.Cyan 	= new Color("Cyan", 	"c", "Cyan", [0, 1, 1, 1]);
		this.Gray 	= new Color("Gray", 	"a", "Gray", [.5, .5, .5, 1]);
		this.Green 	= new Color("Green", 	"g", "Green", [0, 1, 0, 1]);
		this.GreenDark 	= new Color("GreenDark", "G", "#008000", [0, .5, 0, 1]);
		this.Orange 	= new Color("Orange", 	"o", "Orange", [1, .5, 0, 1]);
		this.Red 	= new Color("Red", 	"r", "Red", [1, 0, 0, 1]);
		this.RedDark 	= new Color("RedDark", 	"R", "#800000", [.5, 0, 0, 1]);
		this.Violet 	= new Color("Violet", 	"v", "Violet", [1, 0, 1, 1]);
		this.White 	= new Color("White", 	"w", "White", [1, 1, 1, 1]);
		this.Yellow 	= new Color("Yellow", 	"y", "Yellow", [1, 1, 0, 1]);

		this._All = 
		[
			this.Transparent,

			this.Blue,
			this.Black,
			this.Cyan,
			this.Gray,
			this.Green,
			this.GreenDark,
			this.Orange,
			this.Red,
			this.RedDark,
			this.Violet,
			this.White,
			this.Yellow,

		].addLookups("codeChar");
	}

	Color.Instances = new Color_Instances();

}

function Constants()
{}
{
	Constants.DegreesPerCircle = 360;
	Constants.RadiansPerCircle = 2 * Math.PI;
	Constants.RadiansPerDegree = 
		Constants.RadiansPerCircle
		/ Constants.DegreesPerCircle;
}

function Coords(x, y, z)
{
	this.x = x;
	this.y = y;
	this.z = z;
}
{
	// constants

	Coords.NumberOfDimensions = 3;

	// instances

	function Coords_Instances()
	{
		this.OnesNegative = new Coords(-1, -1, -1);
		this.Zeroes = new Coords(0, 0, 0);
	}

	Coords.Instances = new Coords_Instances();

	// instance methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		this.z += other.z;

		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y, this.z);
	}

	Coords.prototype.crossProduct = function(other)
	{
		return this.overwriteWithXYZ
		(
			this.y * other.z - this.z * other.y,
			this.z * other.x - this.x * other.z,
			this.x * other.y - this.y * other.x
		);

	}

	Coords.prototype.dimensionValues = function()
	{
		return [ this.x, this.y, this.z ];
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		this.z /= other.z;

		return this;
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		this.z /= scalar;

		return this;
	}

	Coords.prototype.dotProduct = function(other)
	{
		var returnValue =
			this.x * other.x
			+ this.y * other.y
			+ this.z * other.z;

		return returnValue;
	}

	Coords.prototype.magnitude = function()
	{
		var returnValue = Math.sqrt
		(
			this.x * this.x
			+ this.y * this.y
			+ this.z * this.z
		);

		return returnValue;
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		this.z *= other.z;

		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		this.z *= scalar;

		return this;
	}

	Coords.prototype.normalize = function()
	{
		return this.divideScalar(this.magnitude());
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		this.z = other.z;

		return this;
	}

	Coords.prototype.overwriteWithXYZ = function(x, y, z)
	{
		this.x = x;
		this.y = y;
		this.z = z;

		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		this.z -= other.z;

		return this;
	}

	Coords.prototype.toString = function()
	{
		var returnValue = "(" + this.x + "," + this.y + "," + this.z + ")";

		return returnValue;
	}

	Coords.prototype.toWebGLArray = function()
	{
		var returnValues = new Float32Array(this.dimensionValues());

		return returnValues;
	}
}

function Display2D(size)
{
	this.size = size;

	this.colorFore = "LightGray";
	this.colorBack = "White";

	// helper variables

	this.drawPositions = 
	[
		new Coords(), new Coords(), new Coords(), new Coords()
	];
}
{
	Display2D.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.size.x;
		canvas.height = this.size.y;
		document.body.appendChild(canvas);

		this.graphics = canvas.getContext("2d");
	}

	Display2D.prototype.sceneInitialize = function(scene)
	{
		// do nothing
	}

	// drawing

	Display2D.prototype.clear = function()
	{
		this.drawRectangle
		(
			Coords.Instances.Zeroes, 
			this.size,
			this.colorBack, // colorFill
			this.colorFore
		)
	}

	Display2D.prototype.drawFace = function(camera, mesh, face)
	{
		var drawPositions = this.drawPositions;
		var cameraPos = camera.pos;
		var cameraOrientation = camera.orientation;
		var cameraFocalLength = camera.focalLength;

		var vertexIndices = face.vertexIndices;
		for (var i = 0; i < vertexIndices.length; i++)
		{
			var vertexIndex = vertexIndices[i];
			var vertex = mesh.vertexPositions[vertexIndex];

			var drawPos = drawPositions[i];

			drawPos.overwriteWith
			(
				vertex
			).subtract
			(
				cameraPos
			);

			cameraOrientation.projectCoords
			(
				drawPos
			);

			if (drawPos.z <= 0)
			{
				return; // hack
			}

			drawPos.multiplyScalar
			(
				cameraFocalLength / drawPos.z
			).add
			(
				camera.viewSizeHalf
			);

			var debug = "debug";
		}

		this.drawPolygon(drawPositions, null, this.colorFore);
	}

	Display2D.prototype.drawMesh = function(camera, mesh)
	{
		var faces = mesh.faces;
		for (var i = 0; i < faces.length; i++)
		{
			var face = faces[i];
			this.drawFace(camera, mesh, face);
		}
	}

	Display2D.prototype.drawPolygon = function(vertices, colorFill, colorBorder)
	{
		this.graphics.beginPath();

		var vertex = vertices[0];
		this.graphics.moveTo(vertex.x, vertex.y);

		for (var i = 1; i < vertices.length; i++)
		{
			vertex = vertices[i];
			this.graphics.lineTo(vertex.x, vertex.y);
		}
	
		this.graphics.closePath();

		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fill();
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorFill;
			this.graphics.stroke();
		}
	}

	Display2D.prototype.drawRectangle = function(pos, size, colorFill, colorBorder)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}

	Display2D.prototype.drawScene = function(scene)
	{
		this.clear();

		var camera = scene.camera;
		var bodies = scene.bodies;

		for (var i = 0; i < bodies.length; i++)
		{
			var body = bodies[i];
			var mesh = body.meshTransformed();
			this.drawMesh(camera, mesh);
		}
	}

}

function DisplayWebGL(size)
{
	this.size = size;
}
{
	DisplayWebGL.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.size.x;
		canvas.height = this.size.y;
		document.body.appendChild(canvas);

		this.webGLContext = new WebGLContext(canvas);
	}

	DisplayWebGL.prototype.sceneInitialize = function(scene)
	{
		var textures = scene.textures;

		for (var i = 0; i < textures.length; i++)
		{
			var texture = textures[i];
			this.textureInitialize(texture);
		}
	}

	DisplayWebGL.prototype.textureInitialize = function(texture)
	{
		var gl = this.webGLContext.gl;

		var systemTexture = gl.createTexture();
		texture.systemTexture = systemTexture;

		gl.bindTexture(gl.TEXTURE_2D, systemTexture);
		//gl.pixelStorei(gl.UNPACK_FLIP_Y_WEBGL, true);
		gl.texImage2D
		(
			gl.TEXTURE_2D, 
			0, 
			gl.RGBA, 
			gl.RGBA, 
			gl.UNSIGNED_BYTE, 
			texture.image.systemImage
		);
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, gl.NEAREST);
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.NEAREST);
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_S, gl.REPEAT);
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_WRAP_T, gl.REPEAT);
		gl.bindTexture(gl.TEXTURE_2D, null);
	}

	// drawing

	DisplayWebGL.prototype.drawScene = function(scene)
	{
		scene.drawToWebGLContext
		(
			this.webGLContext
		);
	}
}

function Face(vertexIndices, material, textureUVs, vertexNormals)
{
	this.vertexIndices = vertexIndices;
	this.material = material;
	this.textureUVs = textureUVs;
	this.vertexNormals = vertexNormals;
}
{
	// constants

	Face.VertexIndexIndicesForQuad = [ [ 0, 1, 2 ], [ 0, 2, 3 ] ];
	Face.VertexIndexIndicesForTriangle = [ [ 0, 1, 2 ] ];

	// methods

	Face.prototype.plane = function(mesh)
	{
		var returnValue = new Plane(this.vertices(mesh));
		return returnValue;
	}

	Face.prototype.vertices = function(mesh)
	{
		var returnValues = [];

		for (var i = 0; i < this.vertexIndices.length; i++)
		{
			var vertexIndex = this.vertexIndices[i];
			var vertexPosition = mesh.vertexPositions[vertexIndex];
			returnValues.push(vertexPosition);
		}

		return returnValues;
	}

	// cloneable

	Face.prototype.clone = function()
	{
		return new Face
		(
			this.vertexIndices, // hack
			this.material, // hack
			(this.textureUVS == null ? null : this.textureUVs.clone()),
			(this.vertexNormals == null ? null : this.vertexNormals.clone())
		);
	}

	// WebGL

	Face.prototype.drawToWebGLContext = function
	(
		webGLContext, 
		scene, 
		mesh,
		vertexPositionsAsFloatArray,
		vertexColorsAsFloatArray,
		vertexNormalsAsFloatArray,
		vertexTextureUVsAsFloatArray,		
		numberOfTrianglesSoFarWrapped
	)
	{
		var face = this;
		var facePlane = face.plane(mesh);
		var faceNormal = facePlane.normal;
		var faceMaterial = face.material;
		var faceVertexNormals = face.vertexNormals;
		var faceColor = (faceMaterial == null ? Color.Instances.Violet : faceMaterial.color);

		var numberOfVerticesInFace = face.vertexIndices.length;

		var vertexIndexIndicesForChildTriangles = 
			(numberOfVerticesInFace == 4) 
			? Face.VertexIndexIndicesForQuad
			: Face.VertexIndexIndicesForTriangle

		for (var t = 0; t < vertexIndexIndicesForChildTriangles.length; t++)
		{
			var vertexIndexIndicesForChildTriangle = 
				vertexIndexIndicesForChildTriangles[t];

			for (var vii = 0; vii < vertexIndexIndicesForChildTriangle.length; vii++)
			{
				var vertexIndexIndex = 
					vertexIndexIndicesForChildTriangle[vii];
				var vertexIndex = face.vertexIndices[vertexIndexIndex];
				var vertexPosition = mesh.vertexPositions[vertexIndex];

				vertexPositionsAsFloatArray.append
				(
					vertexPosition.dimensionValues()
				);

				vertexColorsAsFloatArray.append
				(
					faceColor.componentsRGBA
				);

				var vertexNormal = 
				(
					faceVertexNormals == null 
					? faceNormal
					: faceVertexNormals[vertexIndex]
				);

				vertexNormalsAsFloatArray.append
				(
					vertexNormal.dimensionValues()
				);

				var vertexTextureUV = 
				(
					face.textureUVs == null 
					? Coords.Instances.OnesNegative
					: face.textureUVs[vertexIndexIndex]
				);

				vertexTextureUVsAsFloatArray.append
				(
					[
						vertexTextureUV.x,
						vertexTextureUV.y
					]
				);
			}
		}

		numberOfTrianglesSoFarWrapped.value 
			+= vertexIndexIndicesForChildTriangles.length;
	}
}

function Globals()
{
	this.mediaHelper = new MediaHelper();
}
{
	Globals.Instance = new Globals();

	Globals.prototype.initialize = function(displays, scene)
	{
		this.displays = displays;
		this.scene = scene;
	
		for (var i = 0; i < this.displays.length; i++)
		{
			var display = this.displays[i];
			display.initialize();
			display.sceneInitialize(scene);
		}

		this.inputHelper = new InputHelper();
		this.inputHelper.initialize();

		for (var i = 0; i < this.displays.length; i++)
		{
			var display = this.displays[i];
			this.scene.drawToDisplay(display);
		}
	}
}

function Image(name, systemImage)
{
	this.name = name;
	this.systemImage = systemImage;
	this.filePath = this.systemImage.src;
}
{
}

function ImageHelper()
{}
{
	// static methods

	ImageHelper.buildImageFromStrings = function
	(
		name, 
		scaleMultiplier, 
		stringsForPixels
	)
	{
		var sizeInPixels = new Coords
		(
			stringsForPixels[0].length, stringsForPixels.length
		);

		var canvas = document.createElement("canvas");
		canvas.width = sizeInPixels.x * scaleMultiplier;
		canvas.height = sizeInPixels.y * scaleMultiplier;

		var graphics = canvas.getContext("2d");

		var pixelPos = new Coords(0, 0);
		var colorForPixel = Color.Instances.Transparent;

		for (var y = 0; y < sizeInPixels.y; y++)
		{
			var stringForPixelRow = stringsForPixels[y];
			pixelPos.y = y * scaleMultiplier;

			for (var x = 0; x < sizeInPixels.x; x++)
			{
				var charForPixel = stringForPixelRow[x];
				pixelPos.x = x * scaleMultiplier;

				colorForPixel = Color.Instances._All[charForPixel];

				graphics.fillStyle = colorForPixel.systemColor;
				graphics.fillRect
				(
					pixelPos.x, pixelPos.y, 
					scaleMultiplier, scaleMultiplier
				);				
			}
		}

		var imageFromCanvasURL = canvas.toDataURL("image/png");
		var htmlImageFromCanvas = document.createElement("img");

		htmlImageFromCanvas.width = canvas.width;
		htmlImageFromCanvas.height = canvas.height;
		htmlImageFromCanvas.isLoaded = false;
		htmlImageFromCanvas.onload = function(event) 
		{ 
			event.target.isLoaded = true; 
		}
		htmlImageFromCanvas.src = imageFromCanvasURL;

		var returnValue = new Image(name, htmlImageFromCanvas);

		// hack
		// WebGL doesn't support images from DataURLs?
		returnValue.canvas = canvas;

		return returnValue;
	}
}

function InputHelper()
{
	this.tempCoords = new Coords();
}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onkeydown = this.processKeyDownEvent.bind(this);
	}

	InputHelper.prototype.processKeyDownEvent = function(event)
	{
		var scene = Globals.Instance.scene
		var camera = scene.camera;

		var key = event.key.toLowerCase();

		var distanceToMove = 10;
		var amountToTurn = .05;
		var cameraOrientation = camera.orientation;

		if (key == "a")
		{
			// move left
			camera.pos.subtract
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.right
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "d")
		{
			// move right
			camera.pos.add
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.right
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "e")
		{
			// roll right
			cameraOrientation.overwriteWithForwardDown
			(
				cameraOrientation.forward,
				cameraOrientation.down.add
				(
					cameraOrientation.right.multiplyScalar
					(
						amountToTurn
					)
				)
			);

		}
		else if (key == "f")
		{
			// fall
			camera.pos.subtract
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.down
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "q")
		{
			// roll left
			cameraOrientation.overwriteWithForwardDown
			(
				cameraOrientation.forward,
				cameraOrientation.down.subtract
				(
					cameraOrientation.right.multiplyScalar
					(
						amountToTurn
					)
				)
			);

		}
		else if (key == "r")
		{
			// rise
			camera.pos.add
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.down
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "s")
		{
			// move back
			camera.pos.subtract
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.forward
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "w")
		{
			// move forward
			camera.pos.add
			(
				this.tempCoords.overwriteWith
				(
					cameraOrientation.forward
				).multiplyScalar
				(
					distanceToMove
				)
			);
		}
		else if (key == "z")
		{
			// turn left
			cameraOrientation.overwriteWithForwardDown
			(
				cameraOrientation.forward.subtract
				(
					cameraOrientation.right.multiplyScalar
					(
						amountToTurn
					)
				),
				cameraOrientation.down
			);
		}
		else if (key == "c")
		{
			// turn right
			cameraOrientation.overwriteWithForwardDown
			(
				cameraOrientation.forward.add
				(
					cameraOrientation.right.multiplyScalar
					(
						amountToTurn
					)
				),
				cameraOrientation.down
			);
		}
		else if (key == "x")
		{
			// cancel roll
			cameraOrientation.overwriteWithForwardDown
			(
				cameraOrientation.forward,
				new Coords(0, 0, 1)
			);
		}
		else if (key == "enter")
		{
			// take a snapshot
			scene.snapshotCreate(scene);
		}

		var displays = Globals.Instance.displays;
		for (var i = 0; i < displays.length; i++)
		{
			var display = displays[i];
			scene.drawToDisplay(display);
		}
	}
}

function Lighting(ambientIntensity, direction, directionalIntensity)
{
	this.ambientIntensity = ambientIntensity;
	this.direction = direction.clone().normalize();
	this.directionalIntensity = directionalIntensity;
}

function Material(name, color)
{
	this.name = name;
	this.color = color;
}
{	
	function Material_Instances()
	{
		var colors = Color.Instances;

		this.Blue 	= new Material("Blue", 	colors.Blue);
		this.Cyan 	= new Material("Cyan", 	colors.Cyan);
		this.Green 	= new Material("Green", colors.Green);
		this.GreenDark 	= new Material("GreenDark", colors.GreenDark);
		this.Orange 	= new Material("Orange", colors.Orange);
		this.Red 	= new Material("Red", 	colors.Red);
		this.Violet 	= new Material("Violet", colors.Violet);
		this.Yellow 	= new Material("Yellow", colors.Yellow);
		this.White 	= new Material("White", colors.White);
	}

	Material.Instances = new Material_Instances();
}

function Matrix(values)
{
	this.values = values;
}
{
	// static methods

	Matrix.buildZeroes = function()
	{
		var returnValue = new Matrix
		([
			0, 0, 0, 0,
			0, 0, 0, 0,
			0, 0, 0, 0,
			0, 0, 0, 0,
		]);

		return returnValue;
	}

	// instance methods

	Matrix.prototype.clone = function()
	{
		var valuesCloned = [];

		for (var i = 0; i < this.values.length; i++)
		{
			valuesCloned[i] = this.values[i];
		}

		var returnValue = new Matrix(valuesCloned);

		return returnValue;
	}

	Matrix.prototype.divideScalar = function(scalar)
	{
		for (var i = 0; i < this.values.length; i++)
		{
			this.values[i] /= scalar;
		}

		return this;
	}

	Matrix.prototype.multiply = function(other)
	{
		// hack
		// Instantiates a new matrix.

		var valuesMultiplied = [];

		for (var y = 0; y < 4; y++)
		{
			for (var x = 0; x < 4; x++)
			{
				var valueSoFar = 0;

				for (var i = 0; i < 4; i++)
				{
					// This appears backwards,
					// but the other way doesn't work?
					valueSoFar += 
						other.values[y * 4 + i] 
						* this.values[i * 4 + x];
				}

				valuesMultiplied[y * 4 + x] = valueSoFar;
			}
		}

		this.overwriteWithValues(valuesMultiplied);

		return this;
	}

	Matrix.prototype.multiplyScalar = function(scalar)
	{
		for (var i = 0; i < this.values.length; i++)
		{
			this.values[i] *= scalar;
		}

		return this;
	}

	Matrix.prototype.overwriteWith = function(other)
	{
		for (var i = 0; i < this.values.length; i++)
		{
			this.values[i] = other.values[i];
		}

		return this;
	}

	Matrix.prototype.overwriteWithOrientationBody = function(orientation)
	{
		var forward = orientation.forward;
		var right = orientation.right;
		var down = orientation.down;

		this.overwriteWithValues
		([
			right.x, 	down.x, 	forward.x, 	0,
			right.y, 	down.y,		forward.y, 	0,
			right.z, 	down.z, 	forward.z, 	0,
			0, 		0, 		0, 		1,
		]);


		return this;
	}

	Matrix.prototype.overwriteWithOrientationCamera = function(orientation)
	{
		var forward = orientation.forward;
		var right = orientation.right;
		var down = orientation.down;

		this.overwriteWithValues
		([

			right.x, 	right.y, 	right.z, 	0,
			0-down.x, 	0-down.y,	0-down.z, 	0,
			0-forward.x, 	0-forward.y, 	0-forward.z, 	0,
			0, 		0, 		0, 		1,
		]);
	

		return this;
	}

	Matrix.prototype.overwriteWithPerspectiveForCamera = function(camera) 
	{
		var viewSize = camera.viewSize;
		var y = camera.focalLength / (viewSize.y / 2);
		var x = camera.focalLength / (viewSize.x / 2);
		var zNear = .001;
		var zFar = viewSize.z;
		var zRange = zNear - zFar; // Yes, it's negative.

		this.overwriteWithValues
		([
			x, 	0,	0,			0,
			0,	y, 	0, 			0,
			0, 	0,	(zNear+zFar)/zRange,	(2*zFar*zNear)/zRange,
			0,	0,	-1,			0,
		]);

		return this;
	}

	Matrix.prototype.overwriteWithRotate = function(axisToRotateAround, radiansToRotate)
	{
		var x = axisToRotateAround.x;
		var y = axisToRotateAround.y;
		var z = axisToRotateAround.z;

		var cosine = Math.cos(radiansToRotate);
		var sine = Math.sin(radiansToRotate);
		var cosineReversed = 1 - cosine;

		var xSine = x * sine;
		var ySine = y * sine;
		var zSine = z * sine;

		var xCosineReversed = x * cosineReversed;
		var yCosineReversed = y * cosineReversed;
		var zCosineReversed = z * cosineReversed;

		var xyCosineReversed = x * yCosineReversed;
		var xzCosineReversed = x * zCosineReversed;
		var yzCosineReversed = y * zCosineReversed;

		this.overwriteWithValues
		([
			(x * xCosineReversed + cosine), 	(xyCosineReversed + z * sine), 		(xzCosineReversed - ySine), 	0,
			(xyCosineReversed - zSine), 		(y * yCosineReversed + cosine), 	(yzCosineReversed + xSine), 	0,
			(xzCosineReversed + ySine), 		(yzCosineReversed - xSine), 		(z * zCosineReversed + cosine), 0,
			0,					0, 					0, 				1,
		]);

		return this;
	}

	Matrix.prototype.overwriteWithScale = function(scaleFactors)
	{
		this.overwriteWithValues
		([
			scaleFactors.x,	0, 		0, 		0,
			0, 		scaleFactors.y, 0, 		0,
			0, 		0, 		scaleFactors.z, 0,
			0, 		0, 		0, 		1,

		]);

		return this;
	}

	Matrix.prototype.overwriteWithTranslate = function(displacement)
	{
		this.overwriteWithValues
		([
			1, 0, 0, displacement.x,
			0, 1, 0, displacement.y,
			0, 0, 1, displacement.z,
			0, 0, 0, 1,

		]);

		return this;
	}

	Matrix.prototype.overwriteWithValues = function(otherValues)
	{
		for (var i = 0; i < this.values.length; i++)
		{
			this.values[i] = otherValues[i];
		}

		return this;
	}

	Matrix.prototype.toWebGLArray = function()
	{
		var returnValues = [];

		for (var x = 0; x < 4; x++)
		{
			for (var y = 0; y < 4; y++)
			{
				returnValues.push(this.values[(y * 4 + x)]);
			}
		}

		var returnValues = new Float32Array(returnValues);

		return returnValues;
	}
}

function MediaHelper()
{
	this.images = [];
}
{
	MediaHelper.prototype.loadImages = function
	(
		imagesToLoad,
		methodToCallWhenAllImagesLoaded
	)
	{
		for (var i = 0; i < imagesToLoad.length; i++)
		{
			var imageToLoad = imagesToLoad[i];

			this.images.push(imageToLoad);
			this.images[imageToLoad.name] = imageToLoad;
		}

		this.methodToCallWhenAllImagesLoaded = methodToCallWhenAllImagesLoaded;	

		setTimeout
		(
			this.checkWhetherAllImagesAreLoaded, 
			100
		);
	}

	MediaHelper.prototype.checkWhetherAllImagesAreLoaded = function()
	{
		var mediaHelper = Globals.Instance.mediaHelper;

		var numberOfImagesLeftToLoad = 0;

		for (var i = 0; i < mediaHelper.images.length; i++)
		{
			var image = mediaHelper.images[i];
			if (image.systemImage.isLoaded == false)
			{
				numberOfImagesLeftToLoad++;
			}
		}	

		if (numberOfImagesLeftToLoad > 0)
		{
			setTimeout
			(
				mediaHelper.checkWhetherAllImagesAreLoaded, 
				100
			);
		}
		else
		{
			mediaHelper.methodToCallWhenAllImagesLoaded();
		}
	}
}

function Mesh
(
	name, 
	vertexPositions, 
	texture,
	faces
)
{
	this.name = name;
	this.vertexPositions = vertexPositions;
	this.texture = texture;
	this.faces = faces;
}
{
	// constants

	Mesh.VerticesInATriangle = 3;
	Mesh.TextureUVsDefault = 
	[ 
		new Coords(0, 1), 
		new Coords(1, 1), 
		new Coords(1, 0), 
		new Coords(0, 0) 
	];

	// instance methods

	// cloneable

	Mesh.prototype.clone = function()
	{
		return new Mesh
		(
			this.name + "_Cloned",
			this.vertexPositions.clone(),
			(this.texture == null ? null : this.texture.clone())	,
			this.faces.clone()
		);
	}

	Mesh.prototype.overwriteWith = function(other)
	{
		this.vertexPositions.overwriteWith(other.vertexPositions);
	}

	// WebGL

	Mesh.prototype.drawToWebGLContext = function(webGLContext, scene)
	{
		var gl = webGLContext.gl;

		var shader = webGLContext.shader;

		var vertexPositionsAsFloatArray = [];
		var vertexColorsAsFloatArray = [];
		var vertexNormalsAsFloatArray = [];
		var vertexTextureUVsAsFloatArray = [];

		var numberOfTrianglesSoFarWrapped = new NumberWrapper(0);

		for (var f = 0; f < this.faces.length; f++)
		{
			var face = this.faces[f];
			face.drawToWebGLContext
			(
				webGLContext, 
				scene, 
				this, // mesh
				vertexPositionsAsFloatArray,
				vertexColorsAsFloatArray,
				vertexNormalsAsFloatArray,
				vertexTextureUVsAsFloatArray,
				numberOfTrianglesSoFarWrapped
			);
		}

		var colorBuffer = gl.createBuffer();
		gl.bindBuffer(gl.ARRAY_BUFFER, colorBuffer);
		gl.bufferData
		(
			gl.ARRAY_BUFFER, 
			new Float32Array(vertexColorsAsFloatArray), 
			gl.STATIC_DRAW
		);
		gl.vertexAttribPointer
		(
			shader.inputs["aVertexColor"].location, 
			Color.NumberOfComponentsRGBA, 
			gl.FLOAT, 
			false, 
			0, 
			0
		);

		var normalBuffer = gl.createBuffer();
		gl.bindBuffer(gl.ARRAY_BUFFER, normalBuffer);
		gl.bufferData
		(
			gl.ARRAY_BUFFER, 
			new Float32Array(vertexNormalsAsFloatArray), 
			gl.STATIC_DRAW
		);		
		gl.vertexAttribPointer
		(
			shader.inputs["aVertexNormal"].location, 
			Coords.NumberOfDimensions, 
			gl.FLOAT, 
			false, 
			0, 
			0
		);

		var positionBuffer = gl.createBuffer();
		gl.bindBuffer(gl.ARRAY_BUFFER, positionBuffer);
		gl.bufferData
		(
			gl.ARRAY_BUFFER, 
			new Float32Array(vertexPositionsAsFloatArray), 
			gl.STATIC_DRAW
		);
		gl.vertexAttribPointer
		(
			shader.inputs["aVertexPosition"].location,
			Coords.NumberOfDimensions, 
			gl.FLOAT, 
			false, 
			0, 
			0
		);

		// hack - Prevents some texture-related warnings and errors.
		var textureToBind = (this.texture == null ? scene.textures[0] : this.texture);
		gl.activeTexture(gl.TEXTURE0);
		gl.bindTexture(gl.TEXTURE_2D, textureToBind.systemTexture);

		gl.uniform1i(shader.inputs["uSampler"], 0);

		var textureBuffer = gl.createBuffer();
		gl.bindBuffer(gl.ARRAY_BUFFER, textureBuffer);
		gl.bufferData
		(
			gl.ARRAY_BUFFER, 
			new Float32Array(vertexTextureUVsAsFloatArray), 
			gl.STATIC_DRAW
		);
		gl.vertexAttribPointer
		(
			shader.inputs["aVertexTextureUV"].location, 
			2, 
			gl.FLOAT, 
			false, 
			0, 
			0
		);

		gl.drawArrays
		(
			gl.TRIANGLES,
			0, 
			numberOfTrianglesSoFarWrapped.value 
				* Mesh.VerticesInATriangle
		);
	}
}

function NumberWrapper(value)
{
	this.value = value;
}

function Orientation(forward, down)
{
	this.forward = new Coords();
	this.down = new Coords();
	this.right = new Coords();

	this.overwriteWithForwardDown(forward, down);
}
{
	// instance methods

	Orientation.prototype.clone = function()
	{
		return new Orientation
		(
			this.forward, 
			this.down
		);
	}

	Orientation.prototype.overwriteWithForwardDown = function(forward, down)
	{
		this.forward.overwriteWith(forward).normalize();
		this.down.overwriteWith(down).normalize();
		this.right.overwriteWith(this.down).crossProduct(this.forward).normalize();
	}

	Orientation.prototype.projectCoords = function(coordsToProject)
	{
		coordsToProject.overwriteWithXYZ
		(
			coordsToProject.dotProduct(this.right),
			coordsToProject.dotProduct(this.down),
			coordsToProject.dotProduct(this.forward)
		);
	}

	Orientation.prototype.toString = function()
	{
		var returnValue = "<Orientation "
			+ "forward='" + this.forward.toString() + "' "
			+ "right='" + this.right.toString() + "' "
			+ "down='" + this.down.toString() + "' "
			+ " />";

		return returnValue;			
	}
}

function Plane(positionsOnPlane)
{
	var pos0 = positionsOnPlane[0];
	var displacementFromPos0To1 = Plane.TempCoords0.overwriteWith
	(
		positionsOnPlane[1]
	).subtract
	(
		pos0
	);
	var displacementFromPos0To2 = Plane.TempCoords1.overwriteWith
	(
		positionsOnPlane[2]
	).subtract
	(
		pos0
	);
	var normal = displacementFromPos0To1.clone().crossProduct
	(
		displacementFromPos0To2
	).normalize();

	this.normal = normal;
	this.distanceFromOrigin = this.normal.dotProduct(pos0);
}
{
	// helper variables

	Plane.TempCoords0 = new Coords();
	Plane.TempCoords1 = new Coords();
}

function Scene(name, lighting, camera, textures, bodies)
{
	this.name = name;
	this.lighting = lighting;
	this.camera = camera;
	this.textures = textures;
	this.bodies = bodies;

	// helper variables

	this.matrixBody = Matrix.buildZeroes();
	this.matrixCamera = Matrix.buildZeroes();
	this.matrixOrient = Matrix.buildZeroes();
	this.matrixPerspective = Matrix.buildZeroes();
	this.matrixTranslate = Matrix.buildZeroes();
	this.tempCoords = new Coords();
	this.tempMatrix0 = Matrix.buildZeroes();
	this.tempMatrix1 = Matrix.buildZeroes();
}
{
	Scene.prototype.snapshotCreate = function(scene)
	{
		var textureSize = new Coords(512, 512);

		var webGLContext = Globals.Instance.displays[0].webGLContext;
		var gl = webGLContext.gl;

		var framebuffer = gl.createFramebuffer();
		gl.bindFramebuffer(gl.FRAMEBUFFER, framebuffer);

		var glTexture = gl.createTexture();
		gl.bindTexture(gl.TEXTURE_2D, glTexture);
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, gl.NEAREST)
		gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.NEAREST);
		//gl.generateMipmap(gl.TEXTURE_2D);
		gl.texImage2D
		(
			gl.TEXTURE_2D, 
			0, 
			gl.RGBA, 
			textureSize.x, textureSize.y, 
			0, 
			gl.RGBA, 
			gl.UNSIGNED_BYTE, 
			null
		);

		var renderbuffer = gl.createRenderbuffer();
		gl.bindRenderbuffer(gl.RENDERBUFFER, renderbuffer);
		gl.renderbufferStorage
		(
			gl.RENDERBUFFER, gl.DEPTH_COMPONENT16, textureSize.x, textureSize.y
		);

		gl.framebufferTexture2D
		(
			gl.FRAMEBUFFER, gl.COLOR_ATTACHMENT0, gl.TEXTURE_2D, glTexture, 0
		);
		gl.framebufferRenderbuffer
		(
			gl.FRAMEBUFFER, gl.DEPTH_ATTACHMENT, gl.RENDERBUFFER, renderbuffer
		);

		this.drawToWebGLContext(webGLContext);

		gl.bindTexture(gl.TEXTURE_2D, null);
		gl.bindRenderbuffer(gl.RENDERBUFFER, null);
		gl.bindFramebuffer(gl.FRAMEBUFFER, null);

		var texture = new Texture("Snapshot", null);
		texture.systemTexture = glTexture;

		var camera = this.camera;
		var meshSize = camera.viewSize.clone().divideScalar(16);
		var meshSizeHalf = meshSize.clone().divideScalar(2);
		var cameraViewOverTextureSize = camera.viewSize.clone().divide(textureSize);

		var meshForSnapshot = new Mesh
		(
			"Snapshot", 
			// vertexPositions
			[
				new Coords(-1, -1, 0).multiply(meshSizeHalf),
				new Coords(1, -1, 0).multiply(meshSizeHalf),
				new Coords(1, 1, 0).multiply(meshSizeHalf),
				new Coords(-1, 1, 0).multiply(meshSizeHalf),
			],
			texture,
			// faces
			[
				new Face
				(
					[0, 1, 2, 3],
					null, // material
					[
						new Coords(0, 1).multiply(cameraViewOverTextureSize),
						new Coords(1, 1).multiply(cameraViewOverTextureSize),
						new Coords(1, 0).multiply(cameraViewOverTextureSize),
						new Coords(0, 0).multiply(cameraViewOverTextureSize),
					]
				),
			]
		);

		var cameraOrientation = camera.orientation;

		var bodyForSnapshot = new Body
		(
			"Snapshot", 
			new BodyDefn("Snapshot", meshForSnapshot),
			camera.pos.clone().add
			(
				cameraOrientation.forward.clone().multiplyScalar
				(
					camera.focalLength / 4
				)
			), 
			cameraOrientation.clone()
		);

		scene.bodies.push(bodyForSnapshot);		
	}

	// draw

	Scene.prototype.drawToDisplay = function(display)
	{
		display.drawScene(this);
	}

	Scene.prototype.drawToWebGLContext = function(webGLContext)
	{
		var gl = webGLContext.gl;
		var shader = webGLContext.shader;

		gl.viewport(0, 0, gl.viewportWidth, gl.viewportHeight);
		gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT);

		var camera = this.camera;

		var cameraMatrix = this.matrixCamera.overwriteWithTranslate
		(
			this.tempCoords.overwriteWith(camera.pos).multiplyScalar(-1)
		).multiply
		(
			this.matrixOrient.overwriteWithOrientationCamera
			(
				camera.orientation
			)
		).multiply
		(
			this.matrixPerspective.overwriteWithPerspectiveForCamera
			(
				camera
			)
		)

		gl.uniform1f
		(
			shader.inputs["uLightAmbientIntensity"].location,
			this.lighting.ambientIntensity
		);

		gl.uniform3fv
		(
			shader.inputs["uLightDirection"].location, 
			this.lighting.direction.toWebGLArray()
		);

		gl.uniform1f
		(
			shader.inputs["uLightDirectionalIntensity"].location,
			this.lighting.directionalIntensity
		);

		gl.uniformMatrix4fv
		(
			shader.inputs["uCameraMatrix"].location, 
			false, // transpose
			cameraMatrix.toWebGLArray()
		);

		for (var b = 0; b < this.bodies.length; b++)
		{
			var body = this.bodies[b];

			var normalMatrix = this.matrixOrient.overwriteWithOrientationBody
			(
				body.orientation
			);

			var bodyMatrix = this.matrixBody.overwriteWith
			(
				normalMatrix
			).multiply
			(
				this.matrixTranslate.overwriteWithTranslate
				(
					body.pos
				)
			);

			gl.uniformMatrix4fv
			(
				shader.inputs["uBodyMatrix"].location, 
				false, // transpose
				bodyMatrix.toWebGLArray()
			);

			gl.uniformMatrix4fv
			(
				shader.inputs["uNormalMatrix"].location, 
				false, // transpose
				normalMatrix.multiplyScalar(-1).toWebGLArray()
			);

			body.drawToWebGLContext(webGLContext, this);
		}
	}
}

function Texture(name, image)
{
	this.name = name;
	this.image = image;
}
{
	Texture.prototype.clone = function()
	{
		return this; // hack
	}
}

function Transform()
{
	// static class
}
{
	Transform.transformApplyToCoordsMany = function(transform, coordsMany)
	{
		for (var i = 0; i < coordsMany.length; i++)
		{
			var coordsToTransform = coordsMany[i];
			transform.applyToCoords(coordsToTransform);
		}
	}
}

function TransformMultiple(children)
{
	this.children = children;
}
{
	TransformMultiple.prototype.applyToCoords = function(coordsToTransform)
	{
		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			child.applyToCoords(coordsToTransform);
		}

		return coordsToTransform;
	}
}

function TransformOrient(orientation)
{
	this.orientation = orientation;
}
{
	TransformOrient.prototype.applyToCoords = function(coordsToTransform)
	{
		return coordsToTransform.overwriteWith
		(
			this.orientation.forward.clone().multiplyScalar
			(	
				coordsToTransform.z
			).add
			(
				this.orientation.right.clone().multiplyScalar
				(
					coordsToTransform.x
				)
			).add
			(
				this.orientation.down.clone().multiplyScalar
				(
					coordsToTransform.y
				)
			)
		);
	}
}

function TransformTranslate(offset)
{
	this.offset = offset;
}
{
	TransformTranslate.prototype.applyToCoords = function(coordsToTransform)
	{
		return coordsToTransform.add(this.offset);
	}
}

function WebGLContext(canvas)
{
	var vertexShaderInputs = 
	[
		new WebGLShaderInput("Attribute", "aVertexColor"),
		new WebGLShaderInput("Attribute", "aVertexNormal"),
		new WebGLShaderInput("Attribute", "aVertexPosition"),
		new WebGLShaderInput("Attribute", "aVertexTextureUV"),

		new WebGLShaderInput("Uniform", "uBodyMatrix"),
		new WebGLShaderInput("Uniform", "uCameraMatrix"),
		new WebGLShaderInput("Uniform", "uLightAmbientIntensity"),
		new WebGLShaderInput("Uniform", "uLightDirection"),
		new WebGLShaderInput("Uniform", "uLightDirectionalIntensity"),
		new WebGLShaderInput("Uniform", "uNormalMatrix"),
	];

	var vertexShaderCode = document.getElementById
	(
		"divShaderCodeVertex"
	).childNodes[0].nodeValue;

	var fragmentShaderCode = document.getElementById
	(
		"divShaderCodeFragment"
	).childNodes[0].nodeValue;

	this.shader = new WebGLShader
	(
		vertexShaderInputs,
		vertexShaderCode,
		fragmentShaderCode
	);
	
	this.initialize(canvas);
}
{
	WebGLContext.prototype.initialize = function(canvas)
	{
		var gl = canvas.getContext("webgl");
		this.gl = gl;

		gl.viewportWidth = canvas.width;
		gl.viewportHeight = canvas.height;

		var colorBack = Color.Instances.Cyan;
		var colorBackComponentsRGBA = colorBack.componentsRGBA;
		gl.clearColor
		(
			colorBackComponentsRGBA[0], 
			colorBackComponentsRGBA[1], 
			colorBackComponentsRGBA[2], 
			colorBackComponentsRGBA[3]
		);

		gl.enable(gl.DEPTH_TEST);

		this.shader.initialize(gl);
	}
}

function WebGLShader(inputs, vertexShaderCode, fragmentShaderCode)
{
	this.inputs = inputs;
	this.vertexShaderCode = vertexShaderCode;
	this.fragmentShaderCode = fragmentShaderCode;

	this.inputs.addLookups("name");
}
{
	WebGLShader.prototype.initialize = function(gl)
	{
		var vertexShader = gl.createShader(gl.VERTEX_SHADER);
		gl.shaderSource(vertexShader, this.vertexShaderCode);
		gl.compileShader(vertexShader);

		var fragmentShader = gl.createShader(gl.FRAGMENT_SHADER);
		gl.shaderSource(fragmentShader, this.fragmentShaderCode);
		gl.compileShader(fragmentShader);

		var systemShader = gl.createProgram();
		gl.attachShader(systemShader, vertexShader);
		gl.attachShader(systemShader, fragmentShader);
		gl.linkProgram(systemShader);
		gl.useProgram(systemShader);

		this.systemShader = systemShader;

		for (var i = 0; i < this.inputs.length; i++)
		{
			var input = this.inputs[i];
			input.initialize(gl, this.systemShader);
		}
	}
}

function WebGLShaderInput(typeName, name)
{
	this.typeName = typeName;
	this.name = name;
}
{
	WebGLShaderInput.prototype.initialize = function(gl, systemShader)
	{
		var returnValue;

		if (this.typeName == "Attribute")
		{
			returnValue = gl.getAttribLocation
			(
				systemShader, this.name
			);
			gl.enableVertexAttribArray(returnValue);
		}
		else if (this.typeName == "Uniform")
		{
			returnValue = gl.getUniformLocation
			(
				systemShader, this.name
			);
		}
		else
		{
			throw "Unexpected WebGLShaderInput.typeName.";
		}

		this.location = returnValue;
	}
}

// demo

function DemoData()
{
	// do nothing
}
{
	DemoData.prototype.scene = function(mediaHelper, displaySize)
	{
		var imageTextGL = mediaHelper.images["ImageTextGL"];

		var textureTextGL = new Texture
		(
			"TextureTextGL",
			imageTextGL
		);

		var materials = Material.Instances;

		var meshGround = new Mesh
		(
			"Ground",
			// vertexPositions
			[
				new Coords(1000, -1000, 0),
				new Coords(1000, 1000, 0),
				new Coords(-1000, 1000, 0), 
				new Coords(-1000, -1000, 0),
			],
			null, // texture
			// faces
			[
				new Face
				(
					[0, 1, 2, 3], // vertexIndices
					materials.GreenDark,
					null, // textureUVs
					null // vertexNormals - todo
				),
			]
		);

		var textureUVsForMeshFaces = Mesh.TextureUVsDefault;

		var meshRainbowMonolith = new Mesh
		(
			"RainbowMonolith",
			// vertexPositions
			[
				// back 
				new Coords(-40, 0, -10), 
				new Coords(40, 0, -10),
				new Coords(40, -180, -10),
				new Coords(-40, -180, -10),

				// front
				new Coords(-40, 0, 10),
				new Coords(40, 0, 10),
				new Coords(40, -180, 10),
				new Coords(-40, -180, 10),
			],
			textureTextGL,
			// faces
			[
				new Face
				(
					[5, 4, 7, 6], 
					materials.Red, 
					textureUVsForMeshFaces
				), // front

				new Face
				(
					[0, 1, 2, 3], 
					materials.Orange, 
					textureUVsForMeshFaces
				), // back

				new Face
				(
					[3, 0, 4, 7], 
					materials.Yellow, 
					textureUVsForMeshFaces
				), // left

				new Face
				(
					[5, 6, 2, 1], 
					materials.Green, 
					textureUVsForMeshFaces
				), // right

				new Face
				(
					[6, 7, 3, 2], 
					materials.Blue, 
					textureUVsForMeshFaces
				), // top

				new Face
				(
					[4, 5, 1, 0], 
					materials.Violet, 
					textureUVsForMeshFaces
				), // bottom

			]
		);

		var bodyDefnGround = new BodyDefn
		(
			"Ground",
			meshGround
		);

		var bodyDefnRainbowMonolith = new BodyDefn
		(
			"RainbowMonolith",
			meshRainbowMonolith
		);		

		var bodyGround = new Body
		(
			"Ground0",
			bodyDefnGround,
			new Coords(0, 0, 0), // pos
			new Orientation
			(
				new Coords(0, 0, -1), // forward
				new Coords(1, 0, 0) // down
			)
		);

		var scene = new Scene
		(
			"Scene0",
			new Lighting
			(
				.5, // ambientIntensity
				new Coords(-1, -1, -1), // direction
				2 // directionalIntensity
			),
			new Camera
			(
				displaySize.clone(),
				displaySize.y / 2, // focalLength
				new Coords(-200, 0, -100), // pos
				new Orientation
				(
					new Coords(1, 0, 0), // forward
					new Coords(0, 0, 1) // down
				)
			),
			// textures
			[
				textureTextGL,
			],
			// bodies
			[
				bodyGround, 

				new Body
				(
					"RainbowMonolith0",
					bodyDefnRainbowMonolith,
					new Coords(0, 0, 0), // pos
					new Orientation
					(
						new Coords(1, 0, 0), // forward
						new Coords(0, 0, 1) // down
					)
				),

				new Body
				(
					"RainbowMonolith1",
					bodyDefnRainbowMonolith,
					new Coords(100, 0, 0), // pos
					new Orientation
					(
						new Coords(1, 0, 0), // forward
						new Coords(0, 0, 1) // down
					)
				),

				new Body
				(
					"RainbowMonolith2",
					bodyDefnRainbowMonolith,
					new Coords(0, 100, 0), // pos
					new Orientation
					(
						new Coords(1, 1, 0), // forward
						new Coords(0, 0, 1) // down
					)
				),
			]
		);

		return scene;
	}
}

// run

new WebGLTest().main();

</script>

<!-- WebGL shader programs -->

<div id="divShaderCodeFragment" style="display:none">

	precision mediump float;
	uniform sampler2D uSampler;
	varying vec4 vColor;
	varying vec3 vLight;
	varying vec2 vTextureUV;
	void main(void) 
	{
		if (vTextureUV.x < 0.0)
		{
			gl_FragColor = vColor;
		} 
		else 
		{
			vec4 textureColor = texture2D(uSampler, vec2(vTextureUV.s, vTextureUV.t));
			gl_FragColor = vec4(vLight * textureColor.rgb, textureColor.a);
		}
	}

</div>

<div id="divShaderCodeVertex" style="display:none">

	attribute vec4 aVertexColor;
	attribute vec3 aVertexNormal;
	attribute vec3 aVertexPosition;
	attribute vec2 aVertexTextureUV;
	uniform mat4 uBodyMatrix;
	uniform mat4 uCameraMatrix;
	uniform float uLightAmbientIntensity;
	uniform vec3 uLightDirection;
	uniform float uLightDirectionalIntensity;
	uniform mat4 uNormalMatrix;
	varying vec4 vColor;
	varying vec3 vLight;
	varying vec2 vTextureUV;
	void main(void) 
	{
		vColor = aVertexColor;
		vec4 vertexNormal4 = vec4(aVertexNormal, 0.0);
		vec4 transformedNormal4 = uNormalMatrix * vertexNormal4;
		vec3 transformedNormal = vec3(transformedNormal4.xyz) * -1.0;
		float lightMagnitude = uLightAmbientIntensity;
		lightMagnitude += 
			uLightDirectionalIntensity 
			* max(dot(transformedNormal, uLightDirection), 0.0);
		vLight = vec3(1.0, 1.0, 1.0) * lightMagnitude;
		vTextureUV = aVertexTextureUV;
		vec4 vertexPos = vec4(aVertexPosition, 1.0);
		gl_Position = uCameraMatrix * uBodyMatrix * vertexPos;
	}

</div>


</body>
</html>

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Finding Collisions of Circles and Line Segments in Javascript

The JavaScript program below creates a field full of circles and line segments of random size, position, and velocity, and calculates and displays the collisions between them.

To see the code in action, copy it into an .html file and open it in a web browser that runs JavaScript.

collisionsofcirclesandlinesegments


<html>
<body>
<div id="divMain"></div>
<script type="text/javascript">

// main

function main()
{
	var display = new Display
	(
		new Coords(200, 200),
		"LightGray", "White"
	);

	Globals.Instance.initialize
	(
		new TimerHelper(10), 
		display,
		World.random
		(
			display.size, 
			16, // numberOfBodies
			20, // bodyDimensionMin
			80, // bodyDimensionMax
			1 // speedMax 
		)
	);
}

// classes

function Body(collider, vel)
{
	this.collider = collider;
	this.vel = vel;
}
{
	Body.prototype.posAddAndWrap = function(offset, rangeMax)
	{
		this.collider.posAddAndWrap(offset, rangeMax);
	}

	// drawable

	Body.prototype.drawToDisplay = function(display)
	{
		this.collider.drawToDisplay(display);
	}
}

function Collision()
{
	this.isActive = null;
	this.colliders = [];
	this.points = [];
}
{	
	Collision.prototype.ofColliders = function(collider0, collider1)
	{
		var collider0TypeName = collider0.constructor.name;
		var collider1TypeName = collider1.constructor.name;
	
		if (collider0TypeName == "ShapeCircle")
		{
			if (collider1TypeName == "ShapeCircle")
			{
				this.ofCircles(collider0, collider1);
			}
			else // if (collider1TypeName == "ShapeLineSegment")
			{
				this.ofCircleAndLineSegment(collider0, collider1);
			}
		}
		else // if (collider0TypeName == "ShapeLineSegment")
		{
			if (collider1TypeName == "ShapeCircle")
			{
				this.ofCircleAndLineSegment(collider1, collider0);	
			}
			else // if (collider1TypeName == "ShapeLineSegment")
			{
				this.ofLineSegments(collider0, collider1);
			}
		}

		return this;
	}

	// shapes

	Collision.prototype.ofCircleAndLineSegment = function(circle, segment)
	{

		// todo

		var segmentRight = segment.right;
		var closestApproachOfSegmentLineToOrigin = segment.right.dotProduct
		(
			segment.start
		);

		var centerOfCircleProjectedOntoRight = circle.center.dotProduct
		(
			segmentRight
		);

		var distanceToRadicalCenter =
			closestApproachOfSegmentLineToOrigin 
			- centerOfCircleProjectedOntoRight;

		if (Math.abs(distanceToRadicalCenter) >= circle.radius)
		{
			this.isActive = false;
			this.colliders.length = 0;
			this.points.length = 0;
		}
		else
		{
			this.isActive = true;
			this.colliders.push(circle);
			this.colliders.push(segment);

			var radicalCenter = circle.center.clone().add
			(
				segment.right.clone().multiplyScalar
				(
					distanceToRadicalCenter
				)
			);
			
			var distanceFromRadicalCenterToIntersection = 
				Math.sqrt
				(
					circle.radius * circle.radius
					- (distanceToRadicalCenter * distanceToRadicalCenter)
				);

			var offsetFromRadicalCenterToIntersection = 
				segment.direction.clone().multiplyScalar
				(
					distanceFromRadicalCenterToIntersection 
				);


			for (var i = 0; i < 2; i++)
			{
				var intersection = radicalCenter.clone().add
				(
					offsetFromRadicalCenterToIntersection
				);

				var distanceAlongSegment = 
					intersection.clone().subtract
					(
						segment.start
					).dotProduct
					(
						segment.direction
					);

				if 
				(
					distanceAlongSegment > 0 
					&& distanceAlongSegment < segment.length
				)
				{
					this.points.push(intersection); 				
				}

				// hack
				offsetFromRadicalCenterToIntersection.multiplyScalar(-1);
			}
		}
	}

	Collision.prototype.ofCircles = function(circle0, circle1)
	{
		var displacementFromCenter0To1 = 
			circle1.center.clone().subtract
			(
				circle0.center	
			);

		var distanceBetweenCenters = 
			displacementFromCenter0To1.magnitude();

		var circle0Radius = circle0.radius;
		var circle1Radius = circle1.radius;

		var sumOfRadii = circle0Radius + circle1Radius;

		if (distanceBetweenCenters > sumOfRadii)
		{
			this.isActive = false;
			this.colliders.length = 0;
			this.points.length = 0;
		}
		else
		{

			this.isActive = true;
			this.colliders.push(circle0);
			this.colliders.push(circle1);

			// Adapted from formulas derived at the URL
			// http://mathworld.wolfram.com/Circle-CircleIntersection.html
			
			var distanceToRadicalCenter = 
			(
				distanceBetweenCenters * distanceBetweenCenters
				+ circle0Radius * circle0Radius
				- circle1Radius * circle1Radius
			)
			/ (2 * distanceBetweenCenters);

			var directionToRadicalCenter = 
				displacementFromCenter0To1.divideScalar
				(
					distanceBetweenCenters
				);

			var displacementToRadicalCenter = 
				directionToRadicalCenter.clone().multiplyScalar
				(
					distanceToRadicalCenter
				)

			var radicalCenter = circle0.center.clone().add
			(
				displacementToRadicalCenter
			);

			var differenceOfRadii = circle1Radius - circle0Radius;

			var directionFromRadicalCenterToIntersection = 
				directionToRadicalCenter.right();

			var radicalLineLengthHalf = Math.sqrt
			(
				(-distanceBetweenCenters + differenceOfRadii)
				* (-distanceBetweenCenters - differenceOfRadii)
				* (-distanceBetweenCenters + sumOfRadii)
				* (distanceBetweenCenters + sumOfRadii)
			) / (2 * distanceBetweenCenters);

			var displacementFromRadicalCenterToIntersection = 
				directionFromRadicalCenterToIntersection.multiplyScalar
				(
					radicalLineLengthHalf
				);

			var intersection0 = radicalCenter.clone().add
			(
				displacementFromRadicalCenterToIntersection
			);			
		

			var intersection1 = radicalCenter.clone().subtract
			(
				displacementFromRadicalCenterToIntersection
			);

			// this.points.push(radicalCenter);
			this.points.push(intersection0);
			this.points.push(intersection1);			

		}

		return this;
	}

	Collision.prototype.ofLineSegments = function(segment0, segment1)
	{
		this.isActive = false;
		this.colliders.length = 0;
		this.points.length = 0;

		var segment1ProjectedOnto0 = segment1.clone().projectOnto
		(
			segment0
		);
		var segmentProjected = segment1ProjectedOnto0;

		var segmentProjectedLength = segmentProjected.length;

		var point0 = segmentProjected.start;
		var point1 = segmentProjected.end();

		var lineProjectedCrossesXAxis = (point0.y / point1.y < 0);

		if (lineProjectedCrossesXAxis == true)
		{
			var lengthAlongSegment1ToIntersection = Math.abs
			(
				point0.y / segmentProjected.direction.y
			);

			var lengthAlongSegment0ToIntersection =  
				segmentProjected.start.x
			 	+ segmentProjected.direction.x
				* lengthAlongSegment1ToIntersection; 

			if 
			(
				lengthAlongSegment0ToIntersection > 0
				&& lengthAlongSegment0ToIntersection < segment0.length
				&& lengthAlongSegment1ToIntersection > 0
				&& lengthAlongSegment1ToIntersection < segment1.length
			)
			{
				this.isActive = true;
				this.colliders.push(segment0);
				this.colliders.push(segment1);

				var collisionPos = segment1.start.clone().add
				(
					segment1.direction.clone().multiplyScalar
					(
						lengthAlongSegment1ToIntersection
					)
				);	

				this.points.push(collisionPos);			
			}
		}

		return this;
	}


	// drawable

	Collision.prototype.drawToDisplay = function(display)
	{
		for (var i = 0; i < this.points.length; i++)
		{
			var point = this.points[i];

			display.drawCircle(point, 3);
		}
	}
}

function Constants()
{
	// static class
}
{
	// constants

	Constants.RadiansPerCycle = 2.0 * Math.PI;
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	// instances

	Coords.Instances = new Coords_Instances();

	function Coords_Instances()
	{
		this.Ones = new Coords(1, 1);
		this.Zeroes = new Coords(0, 0);
	}

	// methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.dotProduct = function(other)
	{
		return this.x * other.x + this.y * other.y;
	}

	Coords.prototype.fromAngle = function(angleInCycles)
	{
		var radiansPerCycle = Constants.RadiansPerCycle;
		var angleInRadians = angleInCycles * radiansPerCycle;
		this.x = Math.cos(angleInRadians);
		this.y = Math.sin(angleInRadians);
		return this;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;
		return this;
	}

	Coords.prototype.projectOntoXY = function(axisX, axisY)
	{
		return this.overwriteWithXY
		(
			this.dotProduct(axisX),
			this.dotProduct(axisY)
		);
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

	Coords.prototype.right = function()
	{
		var temp = this.y;
		this.y = this.x;
		this.x = 0 - temp;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}

	Coords.prototype.wrapToRangeMax = function(max)
	{
		while (this.x < 0)
		{
			this.x += max.x;
		}

		while (this.x >= max.x)
		{
			this.x -= max.x;
		}

		while (this.y < 0)
		{
			this.y += max.y;
		}

		while (this.y >= max.y)
		{
			this.y -= max.y;
		}

		return this;
	}
}

function Display(size, colorFore, colorBack)
{
	this.size = size;
	this.colorFore = colorFore;
	this.colorBack = colorBack;
}
{
	// methods

	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			Coords.Instances.Zeroes,
			this.size,
			this.colorBack, this.colorFore
		);
	}

	Display.prototype.drawCircle = function(center, radius)
	{
		this.graphics.beginPath();
		this.graphics.arc
		(
			center.x, center.y,
			radius,
			0, Constants.RadiansPerCycle
		);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();
	}

	Display.prototype.drawLine = function(fromPos, toPos)
	{
		this.graphics.beginPath();
		this.graphics.moveTo(fromPos.x, fromPos.y);
		this.graphics.lineTo(toPos.x, toPos.y);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();	
	}

	Display.prototype.drawRectangle = function
	(
		pos, size, colorFill, colorBorder
	)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.size.x;
		this.canvas.height = this.size.y;

		this.graphics = this.canvas.getContext("2d");

		var divMain = document.getElementById("divMain");
		divMain.appendChild(this.canvas);
		
	}
}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();

	// methods

	Globals.prototype.initialize = function(timerHelper, display, world)
	{
		this.timerHelper = timerHelper;
		this.display = display;
		this.world = world;

		this.display.initialize();
		this.timerHelper.initialize(this.handleEventTimerTick.bind(this));
	}

	// events

	Globals.prototype.handleEventTimerTick = function()
	{
		this.world.updateForTimerTick();
		this.world.drawToDisplay(this.display);
	}
}

function ShapeCircle(center, radius)
{
	this.center = center;
	this.radius = radius;
}
{
	ShapeCircle.prototype.posAddAndWrap = function(offset, rangeMax) 
	{ 
		this.center.add(offset).wrapToRangeMax(rangeMax); 
	}

	// drawable

	ShapeCircle.prototype.drawToDisplay = function(display)
	{
		display.drawCircle(this.center, this.radius);
	}
}

function ShapeLineSegment(start, displacement)
{
	this.start = start;
	this.displacement = displacement;

	this.length = null;
	this.direction = new Coords();
	this.right = new Coords();

	this.recalculateDerivedValues();
}
{
	ShapeLineSegment.prototype.clone = function()
	{
		return new ShapeLineSegment
		(
			this.start.clone(), this.displacement.clone()
		);
	}

	ShapeLineSegment.prototype.end = function()
	{
		return this.start.clone().add(this.displacement);
	}

	ShapeLineSegment.prototype.posAddAndWrap = function(offset, rangeMax) 
	{
		this.start.add(offset).wrapToRangeMax(rangeMax);
	}

	ShapeLineSegment.prototype.projectOnto = function(other)
	{
		this.start.subtract
		(
			other.start
		).projectOntoXY
		(
			other.direction, other.right
		);

		this.displacement.projectOntoXY(other.direction, other.right);

		this.recalculateDerivedValues();

		return this;
	}

	ShapeLineSegment.prototype.recalculateDerivedValues = function()
	{
		this.length = this.displacement.magnitude();

		this.direction.overwriteWith
		(
			this.displacement
		).divideScalar
		(
			this.length
		);

		this.right.overwriteWith(this.direction).right();
	}

	// drawable

	ShapeLineSegment.prototype.drawToDisplay = function(display)
	{
		display.drawLine
		(
			this.start, 
			this.end()
		);
	}

}

function TimerHelper(ticksPerSecond)
{
	this.ticksPerSecond = ticksPerSecond;
}
{
	TimerHelper.prototype.initialize = function(tickEventHandler)
	{
		var millisecondsPerTick = 1000 / this.ticksPerSecond;
		this.timer = setInterval
		(
			tickEventHandler,
			millisecondsPerTick
		);
	}
}

function World(size, bodies)
{
	this.size = size;
	this.bodies = bodies;
}
{
	// static methods

	World.random = function
	(
		size, numberOfBodies, bodyDimensionMin, bodyDimensionMax, speedMax
	)
	{
		var bodies = [];

		var bodyDimensionRange = bodyDimensionMax - bodyDimensionMin;
		var ones = Coords.Instances.Ones;

		for (var i = 0; i < numberOfBodies; i++)
		{
			var collider;

			var pos = new Coords().randomize().multiply(size);

			var bodyDimension = 
				bodyDimensionMin 
				+ bodyDimensionRange * Math.random();	

			if (i % 2 == 0)
			{
				collider = new ShapeCircle
				(
					pos, bodyDimension / 2
				);
			}
			else
			{
				var angle = 
					Math.random() 
					* Constants.RadiansPerCycle;
				var direction = new Coords().fromAngle(angle);
				var displacement = direction.multiplyScalar
				(
					bodyDimension
				);

				collider = new ShapeLineSegment
				(
					pos, displacement
				);
			}

			var vel = new Coords().randomize().multiplyScalar
			(
				2
			).subtract
			(
				ones
			).multiplyScalar
			(
				speedMax
			);

			var body = new Body(collider, vel);

			bodies.push(body);
		}

		var returnValue = new World
		(
			size, 
			bodies
		);

		return returnValue;
	}

	World.simpleLines = function(size)
	{
		return new World
		(
			size,
			[
				new Body
				(
					new ShapeLineSegment
					(
						new Coords(size.x / 4, size.y / 2), // start
						new Coords(size.x / 2, 0) // disp
					),
					new Coords(0, 0)
				),

				new Body
				(
					new ShapeLineSegment
					(
						new Coords(size.x / 2, 3 * size.y / 4), // start
						new Coords(-size.x / 4, - size.y / 2) // disp
					),
					new Coords(0, 0)
				),
			]
		);
	}

	// instance methods

	World.prototype.updateForTimerTick = function()
	{
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			body.posAddAndWrap
			(
				body.vel,
				this.size
			);
		}
	}

	// drawable

	World.prototype.drawToDisplay = function(display)
	{
		display.clear();
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];

			body.drawToDisplay(display);
		}

		var collision = new Collision();

		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			var collider = body.collider;

			for (var j = i + 1; j < this.bodies.length; j++)
			{
				var bodyOther = this.bodies[j];
				var colliderOther = bodyOther.collider;

				collision.ofColliders(collider, colliderOther);

				if (collision.isActive == true)
				{
					collision.drawToDisplay(display);
				}				
			}
		}

	}
}

// run

main();

</script>
</body>

Posted in Uncategorized | Tagged , , , , | Leave a comment

Finding Collisions of Circles in JavaScript

The JavaScript program below creates a field full of circles of random size, position, and velocity, and calculates and displays the collisions between them.

To see the code in action, open it in a web browser that runs JavaScript.

collisionsofcircles


<html>
<body>
<div id="divMain"></div>
<script type="text/javascript">

// main

function main()
{
	var display = new Display
	(
		new Coords(200, 200),
		"LightGray", "White"
	);

	Globals.Instance.initialize
	(
		new TimerHelper(10), 
		display,
		World.random
		(
			display.size, 
			16, // numberOfBodies
			10, // radiusMin
			40, // radiusMax
			1 // speedMax 
		)
	);
}

// classes

function Body(radius, pos, vel)
{
	this.radius = radius;
	this.pos = pos;
	this.vel = vel;

	this.collider = new ShapeCircle(this.pos, this.radius);
}
{
	// drawable

	Body.prototype.drawToDisplay = function(display)
	{
		display.drawCircle(this.pos, this.radius);
	}
}

function Collision()
{
	this.isActive = null;
	this.colliders = [];
	this.points = [];
}
{
	Collision.prototype.ofCircles = function(circle0, circle1)
	{
		var displacementFromCenter0To1 = 
			circle1.center.clone().subtract
			(
				circle0.center	
			);

		var distanceBetweenCenters = 
			displacementFromCenter0To1.magnitude();

		var circle0Radius = circle0.radius;
		var circle1Radius = circle1.radius;

		var sumOfRadii = circle0Radius + circle1Radius;

		if (distanceBetweenCenters > sumOfRadii)
		{
			this.isActive = false;
			this.colliders.length = 0;
			this.points.length = 0;
		}
		else
		{
			this.isActive = true;
			this.colliders.push(circle0);
			this.colliders.push(circle1);

			// Adapted from formulas derived at the URL
			// http://mathworld.wolfram.com/Circle-CircleIntersection.html
			
			var distanceToRadicalCenter = 
			(
				distanceBetweenCenters * distanceBetweenCenters
				+ circle0Radius * circle0Radius
				- circle1Radius * circle1Radius
			)
			/ (2 * distanceBetweenCenters);

			var directionToRadicalCenter = 
				displacementFromCenter0To1.divideScalar
				(
					distanceBetweenCenters
				);

			var displacementToRadicalCenter = 
				directionToRadicalCenter.clone().multiplyScalar
				(
					distanceToRadicalCenter
				)

			var radicalCenter = circle0.center.clone().add
			(
				displacementToRadicalCenter
			);

			var differenceOfRadii = circle1Radius - circle0Radius;

			var directionFromRadicalCenterToIntersection = 
				directionToRadicalCenter.right();

			var radicalLineLengthHalf = Math.sqrt
			(
				(-distanceBetweenCenters + differenceOfRadii)
				* (-distanceBetweenCenters - differenceOfRadii)
				* (-distanceBetweenCenters + sumOfRadii)
				* (distanceBetweenCenters + sumOfRadii)
			) / (2 * distanceBetweenCenters);

			var displacementFromRadicalCenterToIntersection = 
				directionFromRadicalCenterToIntersection.multiplyScalar
				(
					radicalLineLengthHalf
				);

			var intersection0 = radicalCenter.clone().add
			(
				displacementFromRadicalCenterToIntersection
			);			
		

			var intersection1 = radicalCenter.clone().subtract
			(
				displacementFromRadicalCenterToIntersection
			);

			// this.points.push(radicalCenter);
			this.points.push(intersection0);
			this.points.push(intersection1);			

		}

		return this;
	}

	// drawable

	Collision.prototype.drawToDisplay = function(display)
	{
		for (var i = 0; i < this.points.length; i++)
		{
			var point = this.points[i];

			display.drawCircle(point, 3);
		}
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	// instances

	Coords.Instances = new Coords_Instances();

	function Coords_Instances()
	{
		this.Ones = new Coords(1, 1);
		this.Zeroes = new Coords(0, 0);
	}

	// methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

	Coords.prototype.right = function()
	{
		var temp = this.y;
		this.y = this.x;
		this.x = 0 - temp;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}

	Coords.prototype.wrapToRangeMax = function(max)
	{
		while (this.x < 0)
		{
			this.x += max.x;
		}

		while (this.x >= max.x)
		{
			this.x -= max.x;
		}

		while (this.y < 0)
		{
			this.y += max.y;
		}

		while (this.y >= max.y)
		{
			this.y -= max.y;
		}

		return this;
	}
}

function Display(size, colorFore, colorBack)
{
	this.size = size;
	this.colorFore = colorFore;
	this.colorBack = colorBack;
}
{
	// constants

	Display.RadiansPerCycle = 2.0 * Math.PI;

	// methods

	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			Coords.Instances.Zeroes,
			this.size,
			this.colorBack, this.colorFore
		);
	}

	Display.prototype.drawCircle = function(center, radius)
	{
		this.graphics.beginPath();
		this.graphics.arc
		(
			center.x, center.y,
			radius,
			0, Display.RadiansPerCycle
		);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();
	}

	Display.prototype.drawLine = function(fromPos, toPos)
	{
		this.graphics.beginPath();
		this.graphics.moveTo(fromPos.x, fromPos.y);
		this.graphics.lineTo(toPos.x, toPos.y);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();	
	}

	Display.prototype.drawRectangle = function
	(
		pos, size, colorFill, colorBorder
	)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.size.x;
		this.canvas.height = this.size.y;

		this.graphics = this.canvas.getContext("2d");

		var divMain = document.getElementById("divMain");
		divMain.appendChild(this.canvas);
		
	}
}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();

	// methods

	Globals.prototype.initialize = function(timerHelper, display, world)
	{
		this.timerHelper = timerHelper;
		this.display = display;
		this.world = world;

		this.display.initialize();
		this.timerHelper.initialize(this.handleEventTimerTick.bind(this));
	}

	// events

	Globals.prototype.handleEventTimerTick = function()
	{
		this.world.updateForTimerTick();
		this.world.drawToDisplay(this.display);
	}
}

function ShapeCircle(center, radius)
{
	this.center = center;
	this.radius = radius;
}

function TimerHelper(ticksPerSecond)
{
	this.ticksPerSecond = ticksPerSecond;
}
{
	TimerHelper.prototype.initialize = function(tickEventHandler)
	{
		var millisecondsPerTick = 1000 / this.ticksPerSecond;
		this.timer = setInterval
		(
			tickEventHandler,
			millisecondsPerTick
		);
	}
}

function World(size, bodies)
{
	this.size = size;
	this.bodies = bodies;
}
{
	// static methods

	World.random = function(size, numberOfBodies, radiusMin, radiusMax, speedMax)
	{
		var bodies = [];

		var radiusRange = radiusMax - radiusMin;
		var ones = Coords.Instances.Ones;

		for (var i = 0; i < numberOfBodies; i++)
		{
			var radius = radiusMin + radiusRange * Math.random();

			var pos = new Coords().randomize().multiply
			(
				size
			);

			var vel = new Coords().randomize().multiplyScalar
			(
				2
			).subtract
			(
				ones
			).multiplyScalar
			(
				speedMax
			);

			var body = new Body(radius, pos, vel);

			bodies.push(body);
		}

		var returnValue = new World
		(
			size, 
			bodies
		);

		return returnValue;
	}

	// instance methods

	World.prototype.updateForTimerTick = function()
	{
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			body.pos.add(body.vel).wrapToRangeMax
			(
				this.size
			);
		}
	}

	// drawable

	World.prototype.drawToDisplay = function(display)
	{
		display.clear();
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];

			body.drawToDisplay(display);
		}

		var collision = new Collision();

		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			var collider = body.collider;

			for (var j = i + 1; j < this.bodies.length; j++)
			{
				var bodyOther = this.bodies[j];
				var colliderOther = bodyOther.collider;

				collision.ofCircles(collider, colliderOther);

				if (collision.isActive == true)
				{
					collision.drawToDisplay(display);
				}				
			}
		}

	}
}

// run

main();

</script>
</body>
</html>

Posted in Uncategorized | Tagged , , , , | Leave a comment

A JSON Serializer with Referential Integrity

Below is a JSON serializer implemented in JavaScript, along with an automated test of that serializer.

When run, the program creates a complex test object, serializes it to a string in JSON format, deserializes that string back to an object, re-serializes the deserialized object back to a string, compares the original serialized string to the re-serialized string, and, if the two strings are identical, prints a confirmation message to the debugging console to that effect.

To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

This serializer provides some enhancements over other serializers I have written and used in previous projects. First, the code is somewhat cleaner. Second, the actual objects being serialized are not modified in any way during the serialization process–instead, a tree of separate “SerializationNode” objects is built that shadows the structure of the original object and its descendant objects. Third, this serializer does not require a static list of “known types” to be specified beforehand in order to assign class prototypes to generic deserialized objects, instead using the “eval” function to obtain these prototypes dynamically when needed. Fourth, this serializer can serialize objects that contain circular references, which is something that even the built-in JSON.stringify() can’t do by itself.

Fifth, and most significantly, this serializer maintains “referential integrity” of the serialized objects. That is, if objects A and B both reference a single object C before the serialization, then the subsequently deserialized versions of A and B will both reference the same deserialized instance of object C, rather than each getting their own copy of C. This breaking of referential integrity has played havoc with the architecture of past projects, requiring me to completely redesign otherwise working systems to support serialization. Hopefully this new serializer will make that sort of thing unnecessary.


<html>
<body>
<script type="text/javascript">

// main

function testSerializer()
{
	// Create a complex object to serialize.
	var one = new SerializationTestObject
	(
		true, // booleanValue
		1, // numberValue
		"One", // stringValue,
		function (a, b)
		{
			return a - b
		},
		// arrayValue
		[
			new SerializationTestObject
			(
				true,
				2, 
				"Two",
				null, // functionValue
				[] // arrayValue
			),

			new SerializationTestObject
			(
				true,
				3, 
				"Three",
				null, // functionValue
				[] // arrayValue
			),
		]
	);

	var four = new SerializationTestObject
	(
		true,
		4, 
		"Four",
		null, // functionValue
		null // arrayValue
	);

	// Create two references to a single object.
	
	one.arrayValue[0].arrayValue.push(four);
	one.arrayValue[1].arrayValue.push(four);	

	// Create a circular reference.
	one.arrayValue.push(objectToSerialize);

	var serializer = new Serializer
	([
		// known types
		SerializationTestObject
	]);

	var objectToSerialize = one;
	var objectSerialized = serializer.serialize(objectToSerialize);
	var objectDeserialized = serializer.deserialize(objectSerialized);
	var objectReserialized = serializer.serialize(objectDeserialized);

	if (objectSerialized != objectReserialized)
	{
		console.log("Test failed!");
	}
	else
	{
		console.log("Test passed!");
	}
}

// classes

function SerializationTestObject
(
	booleanValue, numberValue, stringValue, functionValue, arrayValue
)
{
	this.booleanValue = booleanValue;
	this.numberValue = numberValue;
	this.stringValue = stringValue;
	this.functionValue = functionValue;
	this.arrayValue = arrayValue;
}
{
	SerializationTestObject.prototype.add = function(a, b)
	{
		// This is part of the prototype,
		// and thus should not be serialized!
		return a + b;
	}
}

function Serializer()
{
	// do nothing
}
{
	Serializer.prototype.deserialize = function(stringToDeserialize)
	{
		var nodeRoot = JSON.parse(stringToDeserialize);
		nodeRoot.__proto__ = SerializerNode.prototype;
		nodeRoot.prototypesAssign();
		var returnValue = nodeRoot.unwrap([]);

		return returnValue;
	}

	Serializer.prototype.serialize = function(objectToSerialize)
	{
		var nodeRoot = new SerializerNode(objectToSerialize);

		nodeRoot.wrap([], []);

		var nodeRootSerialized = JSON.stringify
		(
			nodeRoot, 
			null, // ? 
			4 // pretty-print indent size
		);

		return nodeRootSerialized;
	}
}

function SerializerNode(objectWrapped)
{
	this.objectWrappedTypeName = null;
	this.id = null;
	this.isReference = null;

	this.objectWrapped = objectWrapped;
}
{
	SerializerNode.prototype.wrap = function
	(
		objectsAlreadyWrapped, objectIndexToNodeLookup
	)
	{
		if (this.objectWrapped != null)
		{			
			var typeName = this.objectWrapped.constructor.name;

			var objectIndexExisting = 
				objectsAlreadyWrapped.indexOf(this.objectWrapped);
				
			if (objectIndexExisting >= 0)
			{
				var nodeForObjectExisting = objectIndexToNodeLookup[objectIndexExisting];
				this.id = nodeForObjectExisting.id;
				this.isReference = true;
				this.objectWrapped = null;
			}
			else
			{
				this.isReference = false;
				var objectIndex = objectsAlreadyWrapped.length;
				this.id = objectIndex;
				objectsAlreadyWrapped.push(this.objectWrapped);
				objectIndexToNodeLookup[objectIndex] = this;

				this.objectWrappedTypeName = typeName;
	
				if (typeName == "Function")
				{
					this.objectWrapped = this.objectWrapped.toString();
				}
				else
				{
					this.children = {};
	
					for (var propertyName in this.objectWrapped)
					{
						if (this.objectWrapped.__proto__[propertyName] == null)
						{
							var propertyValue = this.objectWrapped[propertyName];

							if (propertyValue == null)
							{
								child = null;
							}
							else 
							{			
								var propertyValueTypeName = propertyValue.constructor.name;

								if 
								(
									propertyValueTypeName == "Boolean"
									|| propertyValueTypeName == "Number"
									|| propertyValueTypeName == "String"
								)
								{
									child = propertyValue;
								}
								else
								{
									child = new SerializerNode
									(
										propertyValue
									);
								}

							}

							this.children[propertyName] = child;
						}
					}

					delete this.objectWrapped;
	
					for (var childName in this.children)
					{
						var child = this.children[childName];
						if (child != null)
						{
							var childTypeName = child.constructor.name;
							if (childTypeName == "SerializerNode")
							{
								child.wrap
								(
									objectsAlreadyWrapped,
									objectIndexToNodeLookup
								);
							}
						}
					}
				}
			}

		} // end if objectWrapped != null

		return this;		

	} // end method

	SerializerNode.prototype.prototypesAssign = function()
	{
		if (this.children != null)
		{
			for (var childName in this.children)
			{
				var child = this.children[childName];
				if (child != null)
				{
					var childTypeName = child.constructor.name;
					if (childTypeName == "Object")
					{
						child.__proto__ = SerializerNode.prototype;
						child.prototypesAssign();
					}
				}
			}
		}
	}

	SerializerNode.prototype.unwrap = function(nodesAlreadyProcessed)
	{
		if (this.isReference == true)
		{
			var nodeExisting = nodesAlreadyProcessed[this.id];
			this.objectWrapped = nodeExisting.objectWrapped;
		}
		else
		{
			nodesAlreadyProcessed[this.id] = this;
			var typeName = this.objectWrappedTypeName;
			if (typeName == null)
			{
				// Value is null.  Do nothing.
			}
			else if (typeName == "Array")
			{
				this.objectWrapped = [];
			}
			else if (typeName == "Function")
			{
				this.objectWrapped = eval("(" + this.objectWrapped + ")");
			}
			else if 
			(
				typeName == "Boolean" 
				|| typeName == "Number" 
				|| typeName == "String"
			)
			{
				// Primitive types. Do nothing.
			}
			else
			{
				this.objectWrapped = {};
				var objectWrappedType = eval("(" + typeName + ")");
				this.objectWrapped.__proto__ = objectWrappedType.prototype;
			}

	
			if (this.children != null)
			{
				for (var childName in this.children)
				{
					var child = this.children[childName];
			
					if (child != null)
					{
						if (child.constructor.name == "SerializerNode")
						{
							child = child.unwrap
							(
								nodesAlreadyProcessed
							);
						}
					}

					this.objectWrapped[childName] = child;
				}
			}

		}

		return this.objectWrapped;
	}


}

// run

testSerializer();

</script>
</body>
</html>

Posted in Uncategorized | Tagged , , , | Leave a comment

A Rudimentary Mesh Editor in JavaScript

The code below implements a rudimentary editor for three-dimensional forms called “meshes”. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript. Or, for an online version, visit “https://thiscouldbebetter.neocities.org/mesheditor.html“.

MeshEditor.png


<html>
<body>

<div id="divMain"></div>
<div id="divUI">
	<div id="divView" style="border:1px solid">
		<label>View:</label>
		<div style="border:1px solid">
			<label>Camera:</label>
			<button onclick="buttonViewUp_Clicked();">^</button>
			<button onclick="buttonViewDown_Clicked();">v</button>
			<button onclick="buttonViewLeft_Clicked();">&lt;</button>
			<button onclick="buttonViewRight_Clicked();">&gt;</button>
			<button onclick="buttonViewIn_Clicked();">+</button>
			<button onclick="buttonViewOut_Clicked();">-</button>
			<button onclick="buttonViewFront_Clicked();">Front</button>	
			<button onclick="buttonViewSide_Clicked();">Side</button>	
			<button onclick="buttonViewTop_Clicked();">Top</button>			
			<button onclick="buttonViewSelected_Clicked();">Selected</button>			
		</div>
		<div style="border:1px solid">
			
			<label>Highlight:</label>
			<label>Vertices:</label>
			<input id="checkboxHighlightVertices" type="checkbox" checked="true" onchange="checkboxHighlightVertices_Changed();"></input>
			<label>Faces:</label>
			<input id="checkboxHighlightFaces" type="checkbox" checked="true" onchange="checkboxHighlightFaces_Changed();"></input>
		</div>
	</div>
	<div id="divSelect" style="border:1px solid">
		<label>Select:</label>
		<button onclick="buttonSelectAtCursor_Clicked();">At Cursor</button>
		<button onclick="buttonSelectAll_Clicked();">All</button>
		<button onclick="buttonSelectNone_Clicked();">None</button>
		<button onclick="buttonDeselectAtCursor_Clicked();">Deselect At Cursor</button>
	</div>
	<div id="divVertexOperations" style="border:1px solid">
		<label>Vertices:</label>
		<button onclick="buttonVertexAddAtCursor_Clicked();">Add at Cursor</button>
		<button onclick="buttonVertexDeleteSelected_Clicked();">Delete Selected</button>	
		<button onclick="buttonVertexConnectSelected_Clicked();">Connect Selected</button>		
		<button onclick="buttonVertexFaceBuildWithSelected_Clicked();">Face from Selected</button>				
	</div>
	
	<div id="divTransform" style="border:1px solid">
		<label>Transform:</label>
		<div id="divTransformParameters">
			<div>
				<label>Relative to:</label>
				<select id="selectTransformCenter">
					<option>Origin</option>				
					<option>Median of Selected</option>
					<option>Cursor</option>
				</select>
			</div>
			<div>
				<label>Axes:</label>
				<select id="selectTransformAxes">
					<option>All</option>
					<option>X</option>
					<option>Y</option>
					<option>Z</option>
					<option>Camera Forward</option>
				</select>
			</div>
			<div>
				<label>Operation:</label>
				<select id="selectTransformOperation">
					<option>Translate</option>
					<option>Rotate</option>
					<option>Scale</option>
				</select>
			</div>
			<div>
				<label>Amount:</label>
				<input id="inputTransformAmount" type="number" value="0"></input>
			</div>
			<button onclick="buttonTransform_Clicked();">Transform Selected</button>
		</div>
	</div>
	<div style="border:1px solid">
		<label>File:</label>
		<button onclick="buttonFileSave_Clicked();">Save</button>
		<button onclick="buttonFileLoad_Clicked();">Load:</button>
		<input id="inputFileToLoad" type="file"></input>
	</div>
</div>

<script type="text/javascript">

// ui events

function buttonDeselectAtCursor_Clicked()
{
	Globals.Instance.session.deselectAtCursor();
}

function buttonFileLoad_Clicked()
{
	var inputFileToLoad = document.getElementById("inputFileToLoad");
	var fileToLoad = inputFileToLoad.files[0];
	if (fileToLoad == null)
	{
		alert("No file specified!")
	}
	else
	{
		Globals.Instance.session.sceneLoadFromFile(fileToLoad);
	}
}

function buttonFileSave_Clicked()
{
	Globals.Instance.session.sceneSaveToFile();
}

function buttonSelectAll_Clicked()
{
	Globals.Instance.session.selectAll();
}

function buttonSelectAtCursor_Clicked()
{
	Globals.Instance.session.selectAtCursor();
}

function buttonSelectNone_Clicked()
{
	Globals.Instance.session.selectNone();
}

function buttonTransform_Clicked()
{
	var session = Globals.Instance.session;

	var centerName = document.getElementById("selectTransformCenter").value;

	var center;
	if (centerName == "Origin")
	{
		center = new Coords(0, 0, 0);
	}
	else if (centerName == "Median of Selected")
	{
		var scene = session.scene;
		center = scene.selection.medianForMesh(scene.mesh);
	}
	else if (centerName == "Cursor")
	{
		center = session.scene.cursor.pos;
	}
	
	var axes = document.getElementById("selectTransformAxes").value;
	var operation = document.getElementById("selectTransformOperation").value;
	var amount = parseFloat(document.getElementById("inputTransformAmount").value);
	if (isNaN(amount) == true)
	{
		amount = 0;
	}
	
	var amountAsCoords;
	var axis;
	if (axes == "All")
	{
		amountAsCoords = new Coords(1, 1, 1);
		axis = null;
	}
	else if (axes == "X")
	{
		amountAsCoords = new Coords(1, 0, 0);
		axis = new Coords(1, 0, 0);		
	}
	else if (axes == "Y")
	{
		amountAsCoords = new Coords(0, 1, 0);
		axis = new Coords(0, 1, 0);		
	}
	else if (axes == "Z")
	{
		amountAsCoords = new Coords(0, 0, 1);
		axis = new Coords(0, 0, 1);
	}
	else if (axes == "Camera Forward")
	{
		var camera = session.scene.camera;
		var cameraForward = camera.loc.orientation.forward;
		amountAsCoords = cameraForward.clone().normalize();	
		axis = cameraForward.clone();
	}	
	
	amountAsCoords.multiplyScalar(amount);

	var transform = null;
	if (operation == "Translate")
	{
		if (axes != "All")
		{
			transform = new Transform_Translate(amountAsCoords);
		}
	}
	else if (operation == "Rotate")
	{
		if (axes != "All")
		{
			transform = new Transform_Rotate(axis, amount);
		}
	}
	else if (operation == "Scale")
	{
		transform = new Transform_Scale(amountAsCoords);
	}

	if (transform == null)
	{
		alert("Invalid parameters for transform!");
	}
	else
	{
		session.transformWithCenterApplyToSelected(transform, center);
		session.update();
	}
}

function buttonVertexAddAtCursor_Clicked()
{
	var session = Globals.Instance.session;
	var scene = session.scene;
	var vertexNew = scene.cursor.pos.clone();
	var mesh = scene.mesh;
	mesh.vertices.push(vertexNew);
	session.selectNone();
	session.selectAtCursor();
	session.update();
}

function buttonVertexConnectSelected_Clicked()
{
	var session = Globals.Instance.session;
	var scene = session.scene;
	var mesh = scene.mesh;
	var selection = scene.selection;
	mesh.verticesConnectWithEdge(selection.vertexIndices);
	session.update();
}

function buttonVertexDeleteSelected_Clicked()
{
	var session = Globals.Instance.session;
	var scene = session.scene;
	var mesh = scene.mesh;
	var verticesToRemove = scene.selection.verticesForMesh(mesh);
	mesh.verticesRemove(verticesToRemove);
	session.selectNone();
	session.update();
}

function buttonVertexFaceFromSelected_Clicked()
{
	var session = Globals.Instance.session;
	var scene = session.scene;
	var mesh = scene.mesh;
	var selection = scene.selection;
	mesh.edgesConnectWithFace(selection.vertexIndices);
	session.update();
}

function buttonViewDown_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveDown();
	session.update();
}

function buttonViewFront_Clicked()
{
	var session = Globals.Instance.session;
	session.viewSetFront();
	session.update();
}

function buttonViewIn_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveIn();
	session.update();	
}

function buttonViewLeft_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveLeft();
	session.update();
}

function buttonViewOut_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveOut();
	session.update();
}

function buttonViewRight_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveRight();
	session.update();
}

function buttonViewSelected_Clicked()
{
	var session = Globals.Instance.session;
	session.viewSetSelected();
	session.update();
}

function buttonViewSide_Clicked()
{
	var session = Globals.Instance.session;
	session.viewSetSide();
	session.update();
}

function buttonViewTop_Clicked()
{
	var session = Globals.Instance.session;
	session.viewSetTop();
	session.update();
}

function buttonViewUp_Clicked()
{
	var session = Globals.Instance.session;
	session.viewMoveUp();
	session.update();	
}

function checkboxHighlightVertices_Changed()
{
	var highlightVertices = document.getElementById("checkboxHighlightVertices").checked;	
	var session = Globals.Instance.session;
	session.scene.highlightVertices = highlightVertices;
	session.update();	
}

function checkboxHighlightFaces_Changed()
{
	var highlightFaces = document.getElementById("checkboxHighlightFaces").checked;	
	var session = Globals.Instance.session;
	session.scene.highlightFaces = highlightFaces;
	session.update();	
}


// main

function main()
{
	var camera = new Camera
	(
		new Coords(100, 100, 0), // viewSize
		50, // focalLength
		new Location
		(
			new Coords(-2, -2, -2), // pos
			Orientation.fromForwardAndDown
			(
				new Coords(1, 1, 1), // forward
				new Coords(0, 0, 1) // down
			)
		)
	);

	var display = new Display
	(
		camera.viewSize
	);
	
	var mesh = MeshBuilder.cube();
	
	var scene = new Scene
	(
		camera,
		mesh
	);

	Globals.Instance.initialize
	(
		display,
		scene
	);
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.contains = function(element)
	{
		return (this.indexOf(element) >= 0);
	}

	Array.prototype.remove = function(element)
	{
		this.splice(this.indexOf(element), 1);
		return this;
	}
	
	Array.prototype.removeAt = function(index)
	{
		this.splice(index, 1);
		return this;
	}
	
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
	this.size = new Coords();
	this.sizeRecalculate();
}
{
	// static methods
	
	Bounds.ofPoints = function(pointsToFindBoundsOf)
	{
		var point0 = pointsToFindBoundsOf[0];
		var min = point0.clone();
		var max = point0.clone();
		
		for (var i = 1; i < pointsToFindBoundsOf.length; i++)
		{
			var point = pointsToFindBoundsOf[i];
			if (point.x < min.x)
			{
				min.x = point.x;
			}
			else if (point.x > max.x)
			{
				max.x = point.x;
			}

			if (point.y < min.y)
			{
				min.y = point.y;
			}
			else if (point.y > max.y)
			{
				max.y = point.y;
			}

			if (point.z < min.z)
			{
				min.z = point.z;
			}
			else if (point.z > max.z)
			{
				max.z = point.z;
			}
		}
		
		var returnValue = new Bounds(min, max);
		
		return returnValue;
	}

	// instance methods
	
	Bounds.prototype.center = function()
	{
		return this.min.clone().add(this.max).divideScalar(2);
	}

	Bounds.prototype.sizeRecalculate = function()
	{
		this.size.overwriteWith(this.max).subtract(this.min);
	}

	Bounds.prototype.trimCoords = function(coordsToTrim)
	{
		if (coordsToTrim.x < this.min.x)
		{
			coordsToTrim.x = this.min.x;
		}
		else if (coordsToTrim.x > this.max.x)
		{
			coordsToTrim.x = this.max.x;
		}
		
		if (coordsToTrim.y < this.min.y)
		{
			coordsToTrim.y = this.min.y;
		}
		else if (coordsToTrim.y > this.max.y)
		{
			coordsToTrim.y = this.max.y;
		}

		if (coordsToTrim.z < this.min.z)
		{
			coordsToTrim.z = this.min.z;
		}
		else if (coordsToTrim.z > this.max.z)
		{
			coordsToTrim.z = this.max.z;
		}		
		
		return coordsToTrim;
	}
}

function Camera(viewSize, focalLength, loc)
{
	this.viewSize = viewSize;
	this.focalLength = focalLength;
	this.loc = loc;
	
	this.viewSizeHalf = this.viewSize.clone().divideScalar(2);
			
	this.constraints = 
	[
		new Constraint_Upright(),	
		new Constraint_LookAt(new Coords(0, 0, 0)),
		new Constraint_KeepDistance(new Coords(0, 0, 0), this.loc.pos.magnitude()),
	];
	
	this.reinitialize();
}
{
	Camera.prototype.constraintsApply = function()
	{
		for (var i = 0; i < this.constraints.length; i++)
		{
			var constraint = this.constraints[i];
			constraint.constrainLoc(this.loc)
		}
	}
		
	Camera.prototype.transformCoordsWorldToView = function(coordsToTransform)
	{
		return this.transformWorldToView.transformCoords(coordsToTransform);
	}
	
	Camera.prototype.transformCoordsViewToWorld = function(coordsToTransform)
	{
		return this.transformViewToWorld.transformCoords(coordsToTransform);
	}	

	Camera.prototype.transformDistanceWorldToView = function(distanceToTransform, distanceFromCamera)
	{
		var returnValue = distanceToTransform * this.focalLength * this.focalLength / distanceFromCamera;
		return returnValue;
	}
	
	// serialization
	
	Camera.prototype.reinitialize = function()
	{
		// hack
	
		this.loc.orientation.axesReset();
	
		this.transformWorldToView = new Transform_Multiple
		([
			new Transform_TranslateInverse(this.loc.pos),
			new Transform_Orient(this.loc.orientation),
			new Transform_Perspective(this.focalLength),
			new Transform_Translate(this.viewSizeHalf),
		]);
		
		this.transformViewToWorld = new Transform_Multiple
		([
			new Transform_TranslateInverse(this.viewSizeHalf),	
			new Transform_PerspectiveInverse(this.focalLength),
			new Transform_OrientInverse(this.loc.orientation),
			new Transform_Translate(this.loc.pos),
		]);		
	}

	
}

function Constraint_KeepDistance(targetPos, distanceToMaintain)
{
	this.targetPos = targetPos;
	this.distanceToMaintain = distanceToMaintain;
}
{
	Constraint_KeepDistance.prototype.constrainLoc = function(loc)
	{
		var displacement = loc.pos.subtract // No clone needed.
		(
			this.targetPos
		);
		
		displacement.normalize().multiplyScalar
		(
			this.distanceToMaintain
		).add
		(
			this.targetPos
		);		
	}
}


function Constraint_LookAt(targetPos)
{
	this.targetPos = targetPos;
}
{
	Constraint_LookAt.prototype.constrainLoc = function(loc)
	{
		var orientation = loc.orientation;
		orientation.forward.overwriteWith
		(
			this.targetPos
		).subtract
		(
			loc.pos
		)
		
		orientation.orthogonalizeAxes().normalizeAxes();		
	}
}

function Constraint_Upright()
{
	// do nothing
}
{
	Constraint_Upright.prototype.constrainLoc = function(loc)
	{
		var orientation = loc.orientation;
		if (orientation.forward.equals(Coords.Instances.ZeroZeroOne) == false)
		{
			orientation.down.overwriteWithXYZ(0, 0, 1);
		}
	}
}

function Coords(x, y, z)
{
	this.x = x;
	this.y = y;
	this.z = z;
}
{
	// instances
	
	Coords.Instances = new Coords_Instances()
	
	function Coords_Instances()
	{
		this.Ones = new Coords(1, 1, 1);
		this.ZeroZeroOne = new Coords(0, 0, 1);	
		this.Zeroes = new Coords(0, 0, 0);
	}

	// methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		this.z += other.z;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y, this.z);
	}
	
	Coords.prototype.crossProduct = function(other)
	{
		return this.overwriteWithXYZ 
		(
			this.y * other.z - this.z * other.y,
			this.z * other.x - this.x * other.z,
			this.x * other.y - this.y * other.x
		);
	}
	
	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		this.z /= other.z;
		return this;
	}
	
	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		this.z /= scalar;
		return this;
	}
	
	Coords.prototype.dotProduct = function(other)
	{
		return this.x * other.x + this.y * other.y + this.z * other.z;
	}
	
	Coords.prototype.equals = function(other)
	{
		var returnValue = 
		(
			this.x == other.x
			&& this.y == other.y
			&& this.z == other.z
		);
		
		return returnValue;
	}
	
	Coords.prototype.invert = function()
	{
		return this.multiplyScalar(-1);
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y + this.z * this.z);
	}
	
	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		this.z *= other.z;
		return this;
	}
	
	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		this.z *= scalar;
		return this;
	}	
	
	Coords.prototype.normalize = function()
	{
		return this.divideScalar(this.magnitude());
	}
	
	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		this.z = other.z;
		return this;
	}	
	
	Coords.prototype.overwriteWithXYZ = function(x, y, z)
	{
		this.x = x;
		this.y = y;
		this.z = z;
		return this;
	}		
	
	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		this.z -= other.z;
		return this;
	}
}

function Cursor()
{
	this.radius = 5;
	this.pos = new Coords(0, 0, 0);
}
{
	Cursor.prototype.drawToDisplayForCamera = function(display, camera)
	{
		var drawPos = display.drawPos;
		camera.transformCoordsWorldToView
		(
			drawPos.overwriteWith
			(
				this.pos
			)
		);
		display.drawCircle(drawPos, this.radius, null, "Black");
	}
}

function Display(viewSize)
{
	this.viewSize = viewSize;
	
	this.colorFore = "LightGray";
	this.colorBack = "White";
	
	// helper variables
	this.drawPos = new Coords();
}
{
	Display.prototype.clear = function()
	{
		this.drawRectangle(Coords.Instances.Zeroes, this.viewSize, this.colorBack, this.colorFore);
	}

	Display.prototype.drawCircle = function(center, radius, colorFill, colorBorder)
	{
		this.graphics.beginPath();
		
		this.graphics.arc
		(
			center.x, center.y,
			radius,
			0, Math.PI * 2 // start and stop angles
		);
		
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fill();
		}
		
		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;		
			this.graphics.stroke();
		}
	}

	Display.prototype.drawLine = function(fromPos, toPos)
	{
		this.graphics.beginPath();
		this.graphics.moveTo(fromPos.x, fromPos.y);
		this.graphics.lineTo(toPos.x, toPos.y);
		this.graphics.stroke();
	}
	
	Display.prototype.drawRectangle = function(pos, size, colorFill, colorBorder)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
		
		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}
	
	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.viewSize.x;
		this.canvas.height = this.viewSize.y;
		
		this.graphics = this.canvas.getContext("2d");
		
		var divMain = document.getElementById("divMain");
		divMain.appendChild(this.canvas);
	}
}

function Edge(vertexIndices)
{
	this.vertexIndices = vertexIndices;
}
{
	// helper variables

	Edge.drawPosFrom = new Coords();
	Edge.drawPosTo = new Coords();

	// methods

	Edge.prototype.vertices = function(mesh)
	{
		var returnValues = [];
	
		var vertices = mesh.vertices;
		for (var i = 0; i < this.vertexIndices.length; i++)
		{
			var vertexIndex = this.vertexIndices[i];
			var vertex = vertices[vertexIndex];
			returnValues.push(vertex);
		}
		
		return returnValues;	
	}
	
	// drawable
	
	Edge.prototype.drawToDisplayForCameraAndMesh = function(display, camera, mesh)
	{
		var fromPos = Edge.drawPosFrom;
		var toPos = Edge.drawPosTo;
		
		var vertices = this.vertices(mesh);
		
		fromPos.overwriteWith(vertices[0]);
		camera.transformCoordsWorldToView(fromPos);
		
		toPos.overwriteWith(vertices[1]);
		camera.transformCoordsWorldToView(toPos);
		
		display.drawLine(fromPos, toPos);
	}
}

function Face(vertexIndices)
{
	this.vertexIndices = vertexIndices;
}
{
	Face.prototype.medianForMesh = function(mesh)
	{
		var vertices = this.vertices(mesh);
		var median = vertices[0].clone();
		for (var i = 1; i < vertices.length; i++)
		{
			var vertex = vertices[i];
			median.add(vertex);
		}
		median.divideScalar(vertices.length);
		
		return median;
	}

	Face.prototype.plane = function(mesh)
	{
		var vertices = this.vertices(mesh);
		var plane = Plane.fromPoints(vertices);
		return plane;
	}

	Face.prototype.vertices = function(mesh)
	{
		var returnValues = [];
	
		var vertices = mesh.vertices;
		for (var i = 0; i < this.vertexIndices.length; i++)
		{
			var vertexIndex = this.vertexIndices[i];
			var vertex = vertices[vertexIndex];
			returnValues.push(vertex);
		}
		
		return returnValues;
	}
	
	// drawable
	
	Face.prototype.drawToDisplayForCameraAndMesh = function(display, camera, mesh)
	{
		var median = this.medianForMesh(mesh);
		var normal = this.plane(mesh).normal;

		var fromPos = median;

		var normalIndicatorLength = 1;
		var toPos = normal.multiplyScalar(normalIndicatorLength).add(median);

		camera.transformCoordsWorldToView(fromPos);
		camera.transformCoordsWorldToView(toPos);
		
		display.drawRectangle(fromPos, Coords.Instances.Ones, null, display.colorFore);
		display.drawLine(fromPos, toPos);
	}

}

function FileHelper()
{
	// do nothing
}
{
    FileHelper.prototype.loadFileAsBinaryString = function(systemFileToLoad, callback, contextForCallback)
    {
        var fileReader = new FileReader();
        fileReader.systemFile = systemFileToLoad;
        fileReader.callback = callback;
        fileReader.contextForCallback = contextForCallback;
        fileReader.onload = this.loadFile_FileLoaded.bind(this);
        fileReader.readAsBinaryString(systemFileToLoad);
    }
	
    FileHelper.prototype.loadFileAsText = function(systemFileToLoad, callback, contextForCallback)
    {
        var fileReader = new FileReader();
        fileReader.systemFile = systemFileToLoad;
        fileReader.callback = callback;
        fileReader.contextForCallback = contextForCallback;
        fileReader.onload = this.loadFile_FileLoaded.bind(this);
        fileReader.readAsText(systemFileToLoad);
    }
	 
    FileHelper.prototype.loadFile_FileLoaded = function(fileLoadedEvent)
    {
        var fileReader = fileLoadedEvent.target;
        var contentsOfFileLoaded = fileReader.result;
        var fileName = fileReader.systemFile.name;
 
        var callback = fileReader.callback;
        var contextForCallback = fileReader.contextForCallback;
        callback.call(contextForCallback, contentsOfFileLoaded);
    }
 
    FileHelper.prototype.saveBinaryStringToFileWithName = function(fileAsBinaryString, fileName)
    {
        var fileAsArrayBuffer = new ArrayBuffer(fileAsBinaryString.length);
        var fileAsArrayUnsigned = new Uint8Array(fileAsArrayBuffer);
        for (var i = 0; i < fileAsBinaryString.length; i++) 
        {
            fileAsArrayUnsigned[i] = fileAsBinaryString.charCodeAt(i);
        }
 
        var fileAsBlob = new Blob([fileAsArrayBuffer], {type:'unknown/unknown'});
 
        var link = document.createElement("a");
        link.href = window.URL.createObjectURL(fileAsBlob);
        link.download = fileName;
        link.click();
    }
	
	FileHelper.prototype.saveTextStringToFileWithName = function(textToSave, fileNameToSaveAs)
	{
		var textToSaveAsBlob = new Blob([textToSave], {type:"text/plain"});	 
        var link = document.createElement("a");
        link.href = window.URL.createObjectURL(textToSaveAsBlob);
        link.download = fileNameToSaveAs;
        link.click();
	}
}

function Globals()
{
	// do nothing
}
{
	// instance
	
	Globals.Instance = new Globals();
	
	// methods

	Globals.prototype.initialize = function(display, scene)
	{
		this.display = display;
		this.session = new Session(scene);
		
		this.inputHelper = new InputHelper();
		
		this.display.initialize();		
		this.session.initialize();		
		this.update();
		
		this.inputHelper.initialize();
	}
	
	Globals.prototype.update = function()
	{
		this.session.update();
	}
}

function InputHelper()
{
	this.keyPressed = null;
	this.isMouseButtonPressed = false;
	this.mouseClickPos = new Coords();
}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onkeydown = this.handleEventKeyDown.bind(this);
		document.body.onkeyup = this.handleEventKeyUp.bind(this);

		var canvas = Globals.Instance.display.canvas;
		canvas.onmousedown = this.handleEventMouseDown.bind(this);
		canvas.onmouseup = this.handleEventMouseUp.bind(this);
		
		var divMainBounds = divMain.getBoundingClientRect();
		this.mouseClickPosOffset = new Coords
		(
			divMainBounds.left,
			divMainBounds.top,
			0
		);
	}
	
	// events
	
	InputHelper.prototype.handleEventKeyDown = function(event)
	{
		this.keyPressed = event.key;
		Globals.Instance.update();
	}
	
	InputHelper.prototype.handleEventKeyUp = function(event)
	{
		this.keyPressed = null;
	}
	
	InputHelper.prototype.handleEventMouseDown = function(event)
	{
		this.isMouseButtonPressed = true;
		this.mouseClickPos.overwriteWithXYZ
		(
			event.x, event.y, 0
		).subtract
		(
			this.mouseClickPosOffset
		);
		Globals.Instance.update();
	}
	
	InputHelper.prototype.handleEventMouseUp = function(event)
	{
		this.isMouseButtonPressed = false;
	}
	
	
}

function Location(pos, orientation)
{
	this.pos = pos;
	this.orientation = orientation;
}

function Mesh(vertices, faces)
{
	this.vertices = vertices;
	this.faces = faces;
	
	this.edgesBuild();
}
{
	// helper variables
	
	Mesh.drawPos = new Coords();

	// instance methods

	Mesh.prototype.edgesBuild = function()
	{
		this.edges = [];
		var edgeLookup = [];
		
		for (var f = 0; f < this.faces.length; f++)
		{
			var face = this.faces[f];
			var faceVertexIndices = face.vertexIndices;
			
			for (var vi = 0; vi < faceVertexIndices.length; vi++)
			{			
				var vertexIndex = faceVertexIndices[vi];
				var vertex = this.vertices[vertexIndex];

				var viNext = NumberHelper.wrapValueToRangeMax(vi + 1, faceVertexIndices.length);
				var vertexIndexNext = faceVertexIndices[viNext];
				var vertexNext = this.vertices[vertexIndexNext];
				
				var vertexIndicesSorted;
				if (vertexIndex < vertexIndexNext)
				{
					vertexIndicesSorted = [vertexIndex, vertexIndexNext];
				}
				else
				{
					vertexIndicesSorted = [vertexIndexNext, vertexIndex];
				}
				
				var vertexIndexLesser = vertexIndicesSorted[0];
				var vertexIndexGreater = vertexIndicesSorted[1];
				
				var edgesWithVertexIndexLesser = edgeLookup[vertexIndexLesser];
				if (edgesWithVertexIndexLesser == null)
				{
					edgesWithVertexIndexLesser = [];
					edgeLookup[vertexIndexLesser] = edgesWithVertexIndexLesser;
				}
				var edgeExisting = edgesWithVertexIndexLesser[vertexIndexGreater];
				if (edgeExisting == null)
				{
					var edgeNew = new Edge([vertexIndexLesser, vertexIndexGreater])
					edgesWithVertexIndexLesser.push(edgeNew);
					
					this.edges.push(edgeNew);
				}
				else
				{
					// todo
				}
			}
		}
	}
	
	Mesh.prototype.edgesConnectWithFace = function(vertexIndicesForEdges)
	{
		if (vertexIndicesToConnect.length < 3 || vertexIndicesToConnect.length > 4)
		{
			alert("Either 3 or 4 vertices must be selected!");
		}
		else
		{
			var face = new Face(vertexIndicesToConnect.slice(0));
			this.faces.add(face);
			this.edgesBuild();
		}
	}
	

	Mesh.prototype.vertexRemove = function(vertexToRemove)
	{
		// todo
		var vertexIndexBeingRemoved = this.vertices.indexOf(vertexToRemove);
		this.vertices.remove(vertexToRemove);
		
		var facesToRemove = [];
		
		for (var f = 0; f < this.faces.length; f++)
		{
			var face = this.faces[f];
			var faceVertexIndices = face.vertexIndices;
			for (var vi = 0; vi < faceVertexIndices.length; vi++)
			{
				var faceVertexIndex = faceVertexIndices[vi];
				if (faceVertexIndex == vertexIndexBeingRemoved)
				{
					facesToRemove.push(face);
					break;
				}
				else if (faceVertexIndex > vertexIndexBeingRemoved)
				{
					faceVertexIndices[vi] = faceVertexIndex - 1;
				}
			}
		}
		
		for (var fi = 0; fi < facesToRemove.length; fi++)
		{
			var faceToRemove = facesToRemove[fi];
			this.faces.remove(faceToRemove);
		}
		
		this.edgesBuild();
	}
	
	Mesh.prototype.verticesConnectWithEdge = function(vertexIndicesToConnect)
	{
		if (vertexIndicesToConnect.length != 2)
		{
			alert("Exactly 2 vertices must be selected!");
		}
		else
		{
			var edge = new Edge(vertexIndicesToConnect);
			this.edges.push(edge);
		}
	}
	
	Mesh.prototype.verticesRemove = function(verticesToRemove)
	{
		for (var i = 0; i < verticesToRemove.length; i++)
		{
			var vertex = verticesToRemove[i];
			
			this.vertexRemove(vertex);
		}
	}
		
	// drawable
	
	Mesh.prototype.drawToDisplayForScene = function(display, scene)
	{
		var camera = scene.camera;
	
		for (var i = 0; i < this.edges.length; i++)
		{
			var edge = this.edges[i];
			edge.drawToDisplayForCameraAndMesh(display, camera, this);
		}
		
		var drawPos = Mesh.drawPos;
		var vertexHandleRadiusActual = .25;
		
		if (scene.highlightVertices == true)
		{
			for (var i = 0; i < this.vertices.length; i++)
			{
				var vertex = this.vertices[i];
				drawPos.overwriteWith(vertex);
				camera.transformCoordsWorldToView(drawPos);
				var vertexHandleRadiusApparent = camera.transformDistanceWorldToView
				(
					vertexHandleRadiusActual, drawPos.z
				);
				display.drawCircle(drawPos, vertexHandleRadiusApparent, null, display.colorFore);
			}
		}
		
		if (scene.highlightFaces == true)
		{
			for (var i = 0; i < this.faces.length; i++)
			{
				var face = this.faces[i];
				face.drawToDisplayForCameraAndMesh(display, camera, this);
			}
		}
	}
}

function MeshBuilder()
{
	// static class
}
{
	MeshBuilder.cube = function()
	{
		var returnValue = new Mesh
		(
			// vertices
			[
				// top
				new Coords(-1, -1, -1), // 0 - nw
				new Coords(1, -1, -1), // 1 - ne
				new Coords(1, 1, -1), // 2 - se
				new Coords(-1, 1, -1), // 3 - sw
				
				// bottom
				new Coords(-1, -1, 1), // 4 - nw
				new Coords(1, -1, 1), // 5 - ne
				new Coords(1, 1, 1), // 6 - se
				new Coords(-1, 1, 1), // 7 - sw
			],
			// faces
			[
				new Face([0, 3, 2, 1]), // top
				new Face([1, 2, 6, 5]), // east
				new Face([2, 3, 7, 6]), // south 
				new Face([3, 0, 4, 7]), // west
				new Face([0, 1, 5, 4]), // north
				new Face([4, 5, 6, 7]), // bottom
			]
		);
		
		return returnValue;
	}
}

function NumberHelper()
{
	// static class
}
{
	NumberHelper.wrapValueToRangeMax = function(valueToWrap, max)
	{
		while (valueToWrap < 0)
		{
			valueToWrap += max; // rangeSize == max
		}
	
		while (valueToWrap >= max)
		{
			valueToWrap -= max;
		}
		
		return valueToWrap;
	}
}

function Orientation(forward, right, down)
{
	this.forward = forward;
	this.right = right;
	this.down = down;
	this.axesReset();
}
{
	// static methods

	Orientation.fromForwardAndDown = function(forward, down)
	{
		var returnValue = new Orientation(forward.clone(), new Coords(), down.clone());
		returnValue.orthogonalizeAxes().normalizeAxes();
		return returnValue;
	}
	
	Orientation.prototype.axesReset = function()
	{
		this.axes = [this.forward, this.right, this.down];	
	}
	
	// instance methods
	
	Orientation.prototype.normalizeAxes = function()
	{
		for (var i = 0; i < this.axes.length; i++)
		{
			this.axes[i].normalize();
		}
		
		return this;
	}
	
	Orientation.prototype.orthogonalizeAxes = function()
	{
		this.right.overwriteWith(this.down).crossProduct(this.forward);
		this.down.overwriteWith(this.forward).crossProduct(this.right);
		return this;
	}
	
	Orientation.prototype.overwriteWith = function(other)
	{
		this.forward.overwriteWith(other.forward);
		this.right.overwriteWith(other.right);
		this.down.overwriteWith(other.down);
		return this;
	}
}

function Plane(normal, distanceFromOrigin)
{
	this.normal = normal;
	this.distanceFromOrigin = distanceFromOrigin;
}
{
	// helper variables
	Plane.displacementFromPoint0To1 = new Coords();
	Plane.displacementFromPoint1To2 = new Coords();

	// static methods

	Plane.fromPoints = function(points)
	{
		var displacementFromPoint0To1 = Plane.displacementFromPoint0To1;
		var displacementFromPoint1To2 = Plane.displacementFromPoint1To2;
		
		var point0 = points[0];
		var point1 = points[1];
		var point2 = points[2];
		
		displacementFromPoint0To1.overwriteWith(point1).subtract(point0);
		displacementFromPoint1To2.overwriteWith(point2).subtract(point1);
		
		var normal = new Coords().overwriteWith
		(
			displacementFromPoint0To1
		).crossProduct
		(
			displacementFromPoint1To2
		).normalize();
		
		var distanceFromOrigin = normal.dotProduct(point0);
		
		var returnValue = new Plane(normal, distanceFromOrigin);
		
		return returnValue;
	}
}

function Scene(camera, mesh)
{
	this.camera = camera;
	this.mesh = mesh;

	this.selection = new Selection();
	this.cursor = new Cursor();
	
	this.highlightVertices = true;
	this.highlightFaces = true;
}
{
	Scene.prototype.drawToDisplay = function(display)
	{
		this.mesh.drawToDisplayForScene(display, this);
		this.selection.drawToDisplayForCameraAndMesh(display, this.camera, this.mesh);
		this.cursor.drawToDisplayForCamera(display, this.camera);
	}
		
	Scene.prototype.update = function()
	{
		this.update_Input();
		this.camera.constraintsApply();
		this.drawToDisplay(Globals.Instance.display);
	}
	
	Scene.prototype.update_Input = function()
	{
		var session = Globals.Instance.session;
		var inputHelper = Globals.Instance.inputHelper;
		var keyPressed = inputHelper.keyPressed;
		if (keyPressed != null)
		{
			inputHelper.keyPressed = null;
					
			if (keyPressed.startsWith("Arrow") == true)
			{				
				if (keyPressed == "ArrowDown")
				{
					session.viewMoveDown();
				}
				else if (keyPressed == "ArrowLeft")
				{
					session.viewMoveLeft();
				}
				else if (keyPressed == "ArrowRight")
				{
					session.viewMoveRight();
				}				
				else if (keyPressed == "ArrowUp")
				{
					session.viewMoveUp();
				}				
			}
			else if (keyPressed == "=") // +
			{
				session.viewMoveIn();
			}
			else if (keyPressed == "-")
			{
				session.viewMoveOut();	
			}

		}	
		
		if (inputHelper.isMouseButtonPressed == true)
		{
			inputHelper.isMouseButtonPressed = false;
			var cursorPosApparent = this.camera.transformCoordsWorldToView(this.cursor.pos.clone());			
			var cursorPosNext = inputHelper.mouseClickPos.clone();
			cursorPosNext.z = cursorPosApparent.z;
			this.camera.transformCoordsViewToWorld(cursorPosNext);
			this.cursor.pos.overwriteWith(cursorPosNext);
		}
	}
}

function Selection()
{
	this.vertexIndices = [];
}
{	
	Selection.prototype.medianForMesh = function(mesh)
	{
		var returnValue = null;
		if (this.vertexIndicesSelected.length > 0)
		{
			var verticesSelected = this.verticesForMesh(mesh);
			var bounds = Bounds.ofPoints(verticesSelected);
			returnValue = bounds.center();
		}
		return returnValue;
	}
	
	Selection.prototype.verticesForMesh = function(mesh)
	{		
		var returnValues = [];
	
		for (var i = 0; i < this.vertexIndices.length; i++)
		{
			var vertexIndex = this.vertexIndices[i];
			var vertex = mesh.vertices[vertexIndex];
			returnValues.push(vertex);
		}
		
		return returnValues;
	}

	// drawable

	Selection.prototype.drawToDisplayForCameraAndMesh = function(display, camera, mesh)
	{
		var drawPos = display.drawPos;
		var vertexHandleRadiusActual = .25;
		
		for (var i = 0; i < this.vertexIndices.length; i++)
		{
			var vertexIndex = this.vertexIndices[i];
			var vertex = mesh.vertices[vertexIndex];
			drawPos.overwriteWith(vertex);
			camera.transformCoordsWorldToView(drawPos);
			var vertexHandleRadiusApparent = camera.transformDistanceWorldToView
			(
				vertexHandleRadiusActual, drawPos.z
			);
			display.drawCircle(drawPos, vertexHandleRadiusApparent, display.colorFore, null);
		}
	}	
}


function Serializer(knownTypes)
{
	this.knownTypes = knownTypes;

	for (var i = 0; i < this.knownTypes.length; i++)
	{
		var knownType = this.knownTypes[i];
		this.knownTypes[knownType.name] = knownType;
	}
}

{
	// internal classes
	
	function _ArrayWrapper(arrayToWrap)
	{
		this.arrayWrapped = arrayToWrap;
	}
	
	function _FunctionWrapper(functionBody)
	{
		this.functionBody = functionBody;
	}
	
	// methods
	
	Serializer.prototype.deserialize = function(stringToDeserialize)
	{
		var objectDeserialized = JSON.parse(stringToDeserialize);
		this.unwrapArraysRecursively(objectDeserialized);
		this.unwrapFunctionsRecursively(objectDeserialized);
		this.setPrototypeRecursively(objectDeserialized);
		this.deleteClassNameRecursively(objectDeserialized);

		return objectDeserialized;
	}

	Serializer.prototype.serialize = function(objectToSerialize)
	{
		this.wrapFunctionsRecursively(objectToSerialize);
		this.wrapArraysRecursively(objectToSerialize);		
		this.setClassNameRecursively(objectToSerialize);
		var returnValue = JSON.stringify(objectToSerialize);
		this.unwrapArraysRecursively(objectToSerialize);		
		this.unwrapFunctionsRecursively(objectToSerialize);
		this.deleteClassNameRecursively(objectToSerialize);

		return returnValue;
	}
	
	// class names
	
	Serializer.prototype.deleteClassNameRecursively = function(objectToDeleteClassNameOn)
	{
		if (objectToDeleteClassNameOn == null)
		{
			return; //throw "Unrecognized type!"
		}
		
		var className = objectToDeleteClassNameOn.constructor.name;
		if (this.knownTypes[className] != null)
		{
			delete objectToDeleteClassNameOn.className;

			for (var childPropertyName in objectToDeleteClassNameOn)
			{
				var childProperty = objectToDeleteClassNameOn[childPropertyName];
				this.deleteClassNameRecursively(childProperty);
			}
		}
		else if (className == "Array")
		{
			delete objectToDeleteClassNameOn.className;
			for (var i = 0; i < objectToDeleteClassNameOn.length; i++)
			{
				var element = objectToDeleteClassNameOn[i];
				this.deleteClassNameRecursively(element);
			}
		}
	}
	
	Serializer.prototype.setClassNameRecursively = function(objectToSetClassNameOn)
	{
		if (objectToSetClassNameOn == null)
		{
			return; // throw "Unrecognized type!"
		}
		var className = objectToSetClassNameOn.constructor.name;
		
		if (this.knownTypes[className] != null)
		{
			objectToSetClassNameOn.className = className;

			for (var childPropertyName in objectToSetClassNameOn)
			{
				var childProperty = objectToSetClassNameOn[childPropertyName];
				this.setClassNameRecursively(childProperty);
			}
		}
		else if (className == "Array")
		{
			for (var i = 0; i < objectToSetClassNameOn.length; i++)
			{
				var element = objectToSetClassNameOn[i];
				this.setClassNameRecursively(element);
			}
		}
		else if (className == "_ArrayWrapper")
		{
			objectToSetClassNameOn.className = className;

			var arrayWrapped = objectToSetClassNameOn.arrayWrapped;
			this.setClassNameRecursively(arrayWrapped);
		}
	}
	
	// prototypes
	
	Serializer.prototype.setPrototypeRecursively = function(objectToSetPrototypeOn)
	{
		if (objectToSetPrototypeOn == null)
		{
			return; // throw "Unrecognized type!"
		}
	
		var className = objectToSetPrototypeOn.className;
		var typeOfObjectToSetPrototypeOn = this.knownTypes[className];

		if (typeOfObjectToSetPrototypeOn != null)
		{
			objectToSetPrototypeOn.__proto__ = typeOfObjectToSetPrototypeOn.prototype;
	
			for (var childPropertyName in objectToSetPrototypeOn)
			{
				var childProperty = objectToSetPrototypeOn[childPropertyName];
				this.setPrototypeRecursively(childProperty);
			}
		}
		else if (objectToSetPrototypeOn.constructor.name == "Array")
		{
			for (var i = 0; i < objectToSetPrototypeOn.length; i++)
			{
				var element = objectToSetPrototypeOn[i];
				this.setPrototypeRecursively(element);
			}
		}
	}

	// functions
	
	Serializer.prototype.unwrapFunctionsRecursively = function(objectToUnwrapFunctionsOn)
	{
		if (objectToUnwrapFunctionsOn == null)
		{
			return;
		}
				
		var className = objectToUnwrapFunctionsOn.className;
				
		if (this.knownTypes[className] != null)
		{
			for (var childPropertyName in objectToUnwrapFunctionsOn)
			{
				var childProperty = objectToUnwrapFunctionsOn[childPropertyName];
				if (childProperty != null)
				{
					var childPropertyIsFunctionWrapped = 
						(childProperty.className == "_FunctionWrapper");
						
					if (childPropertyIsFunctionWrapped == true)
					{
						var functionBodyAsString = "(" + childProperty.functionBody + ")";
						delete childProperty.functionBody;
						var functionBodyAsFunction = eval(functionBodyAsString);
						functionBodyAsFunction.__proto__ = Function.prototype;

						objectToUnwrapFunctionsOn[childPropertyName] = functionBodyAsFunction;
					}
					else
					{
						this.unwrapFunctionsRecursively(childProperty);
					}
				}
			}
		}
		else if (objectToUnwrapFunctionsOn.constructor.name == "Array")
		{
			for (var i = 0; i < objectToUnwrapFunctionsOn.length; i++)
			{
				var element = objectToUnwrapFunctionsOn[i];
				this.unwrapFunctionsRecursively(element);
			}
		}
	}
	
	Serializer.prototype.wrapFunctionsRecursively = function(objectToWrapFunctionsOn)
	{
		var className = objectToWrapFunctionsOn.constructor.name;
		if (this.knownTypes[className] != null)
		{
			for (var childPropertyName in objectToWrapFunctionsOn)
			{
				var childProperty = objectToWrapFunctionsOn[childPropertyName];
				if (childProperty != null)
				{
					if (childProperty.constructor.name == "Function")
					{
						if (objectToWrapFunctionsOn.__proto__[childPropertyName] == null)
						{
							childProperty = new _FunctionWrapper
							(
								childProperty.toString()
							);
							objectToWrapFunctionsOn[childPropertyName] = childProperty;
						}
					}
					else
					{
						this.wrapFunctionsRecursively(childProperty);
					}
				}
			}
		}
		else if (className == "Array")
		{
			for (var i = 0; i < objectToWrapFunctionsOn.length; i++)
			{
				var element = objectToWrapFunctionsOn[i];
				this.wrapFunctionsRecursively(element);
			}
		}
	}
	
	// arrays
	
	Serializer.prototype.unwrapArraysRecursively = function(objectToUnwrapArraysOn)
	{
		if (objectToUnwrapArraysOn == null)
		{
			return;
		}
				
		var className = objectToUnwrapArraysOn.className;
				
		if (this.knownTypes[className] != null)
		{
			for (var childPropertyName in objectToUnwrapArraysOn)
			{
				var childProperty = objectToUnwrapArraysOn[childPropertyName];
				if (childProperty != null)
				{
					var childPropertyIsArrayWrapped = 
						(childProperty.className == "_ArrayWrapper");
						
					if (childPropertyIsArrayWrapped == true)
					{
						var wrapper = childProperty;
						var arrayWrapped = wrapper.arrayWrapped;
						delete wrapper.arrayWrapped;
						for (var grandchildPropertyName in wrapper)
						{
							var indexOfPropertyWithinArray = wrapper[grandchildPropertyName];
							var grandchildProperty = arrayWrapped[indexOfPropertyWithinArray];
							arrayWrapped[grandchildPropertyName] = grandchildProperty; 		
						}
						
						childProperty = arrayWrapped;
						objectToUnwrapArraysOn[childPropertyName] = childProperty;
					}

					this.unwrapArraysRecursively(childProperty);
				}
			}
		}
		else if (objectToUnwrapArraysOn.constructor.name == "Array")
		{
			for (var i = 0; i < objectToUnwrapArraysOn.length; i++)
			{
				var element = objectToUnwrapArraysOn[i];
				this.unwrapArraysRecursively(element);
			}
		}
	}
		
	Serializer.prototype.wrapArraysRecursively = function(objectToWrapArraysOn)
	{
		var className = objectToWrapArraysOn.constructor.name;
		if (this.knownTypes[className] != null)
		{
			for (var childPropertyName in objectToWrapArraysOn)
			{
				var childProperty = objectToWrapArraysOn[childPropertyName];
				if (childProperty != null)
				{
					if (childProperty.constructor.name == "Array")
					{
						var arrayWrapped = childProperty;

						var wrapper = new _ArrayWrapper(arrayWrapped);
						
						objectToWrapArraysOn[childPropertyName] = wrapper;						
						
						for (var grandchildPropertyName in arrayWrapped)
						{
							if (arrayWrapped.__proto__[grandchildPropertyName] == null)
							{
								var grandchildProperty = arrayWrapped[grandchildPropertyName];
								var indexOfPropertyWithinArray = arrayWrapped.indexOf(grandchildProperty);
								if (indexOfPropertyWithinArray >= 0)
								{
									wrapper[grandchildPropertyName] = indexOfPropertyWithinArray;
								}
							}
						}
						
						this.wrapArraysRecursively(arrayWrapped);
					}
					else
					{
						this.wrapArraysRecursively(childProperty);
					}
				}
			}
		}
		else if (className == "Array")
		{
			for (var i = 0; i < objectToWrapArraysOn.length; i++)
			{
				var element = objectToWrapArraysOn[i];
				this.wrapArraysRecursively(element);
			}
		}
	}
} 

function Session(scene)
{
	this.scene = scene;
}
{
	Session.prototype.initialize = function()
	{
		// todo
	}
		
	Session.prototype.update = function()
	{
		var display = Globals.Instance.display;
		display.clear();
		this.scene.update();
	}
	
	// tools
	
	Session.prototype.deselectAtCursor = function()
	{
		this.selectOrDeselectAtCursor(true);
	}
	
	Session.prototype.sceneLoadFromFile = function(fileToLoad)
	{
		var fileHelper = new FileHelper();
		fileHelper.loadFileAsText
		(
			fileToLoad,
			this.sceneLoadFromFile_2, // callback
			this // contextForCallback
		);
	}
	
	Session.prototype.sceneLoadFromFile_2 = function(fileAsText)
	{
		var sceneSerialized = fileAsText;
		var serializer = this.serializerBuild();
		var sceneDeserialized = serializer.deserialize(sceneSerialized);

		// hack - Serializer currently breaks referential integrity.		
		sceneDeserialized.camera.reinitialize();
		
		this.scene = sceneDeserialized;
		this.update();
	}
		
	Session.prototype.sceneSaveToFile = function()
	{
		var serializer = this.serializerBuild();
		var sceneSerialized = serializer.serialize(this.scene);
		var fileHelper = new FileHelper();
		fileHelper.saveTextStringToFileWithName(sceneSerialized, "Scene.json");
	}

	Session.prototype.selectAll = function()
	{
		var vertexIndicesSelected = this.scene.selection.vertexIndices;
		vertexIndicesSelected.length = 0;
		
		var numberOfVertices = this.scene.mesh.vertices.length;
				
		for (var i = 0; i < numberOfVertices; i++)
		{
			vertexIndicesSelected.push(i);
		}
		this.update();
	}
	
	Session.prototype.selectAtCursor = function()
	{
		this.selectOrDeselectAtCursor(false);
	}
	
	Session.prototype.selectOrDeselectAtCursor = function(deselectRatherThanSelect)
	{
		var inputHelper = Globals.Instance.inputHelper;
		var camera = this.scene.camera;
		var mesh = this.scene.mesh;
		var selection = this.scene.selection;
		var vertices = (deselectRatherThanSelect == true ? selection.verticesForMesh(mesh) : mesh.vertices);
		
		var vertexPosApparent = new Coords();
		var displacement = vertexPosApparent;
		var vertexHandleRadius = 5;
		
		var vertexZClosestSoFar = Number.POSITIVE_INFINITY;
		var vertexIndexClosestSoFar = null;

		for (var i = 0; i < vertices.length; i++)
		{
			var vertex = vertices[i];
			displacement = camera.transformCoordsWorldToView
			(
				vertexPosApparent.overwriteWith
				(
					vertex
				)
			).subtract
			(
				inputHelper.mouseClickPos
			);
			
			var vertexZ = displacement.z;
			displacement.z = 0;
			
			var distanceOfVertexFromClick = displacement.magnitude();
			
			if (distanceOfVertexFromClick <= vertexHandleRadius)
			{
				if (vertexZ < vertexZClosestSoFar)
				{
					vertexZClosestSoFar = vertexZ;
					vertexIndexClosestSoFar = i;
				}
			}
			
		} // end for each vertex
		
		if (vertexIndexClosestSoFar != null)
		{
			if (deselectRatherThanSelect == true)
			{
				selection.vertexIndices.remove(vertexIndexClosestSoFar);
			}
			else
			{
				if (selection.vertexIndices.contains(vertexIndexClosestSoFar) == false)
				{
					selection.vertexIndices.push(vertexIndexClosestSoFar);
				}
			}
		}
		this.update();
	}
	
	Session.prototype.selectNone = function()
	{
		var vertexIndicesSelected = this.scene.selection.vertexIndices;
		vertexIndicesSelected.length = 0;
		this.update();
	}
	
	Session.prototype.transformWithCenterApplyToSelected = function(transform, center)
	{
		// todo - Use center.
	
		var scene = this.scene;
		var selection = scene.selection;
		var selectionVertices = selection.verticesForMesh(scene.mesh);
		for (var i = 0; i < selectionVertices.length; i++)
		{
			var vertex = selectionVertices[i];
			transform.transformCoords(vertex);
		}
	}		
	
	Session.prototype.viewMove = function(direction)
	{
		var distanceToMove = .05;
		var camera = this.scene.camera;
		var cameraPos = camera.loc.pos;
		var offset = direction.clone().multiplyScalar(distanceToMove);
		cameraPos.add(offset);
	}
	
	Session.prototype.viewMoveDown = function() 
	{	
		this.viewMove(this.scene.camera.loc.orientation.down); 
	}
	
	Session.prototype.viewMoveIn = function() 
	{
		var distanceToMove = .1;
		var camera = this.scene.camera;
		camera.constraints[2].distanceToMaintain -= distanceToMove; // hack
	}	
	
	Session.prototype.viewMoveLeft = function() 
	{	
		this.viewMove(this.scene.camera.loc.orientation.right.clone().invert()); 
	}
	
	Session.prototype.viewMoveOut = function() 
	{	
		var distanceToMove = .1;
		var camera = this.scene.camera;
		camera.constraints[2].distanceToMaintain += distanceToMove; // hack
	}		

	Session.prototype.viewMoveRight = function() 
	{	
		this.viewMove(this.scene.camera.loc.orientation.right); 
	}

	Session.prototype.viewMoveUp = function() 
	{	
		this.viewMove(this.scene.camera.loc.orientation.down.clone().invert()); 
	}
	
	Session.prototype.viewSet = function(cameraOrientationNew)
	{
		var scene = this.scene;
		var camera = scene.camera;
		var cameraLoc = camera.loc;
		
		var distanceOfCameraFromOrigin = cameraLoc.pos.magnitude();

		cameraLoc.pos.overwriteWith
		(
			cameraOrientationNew.forward
		).invert().multiplyScalar
		(
			distanceOfCameraFromOrigin
		);
		
		cameraLoc.orientation.overwriteWith(cameraOrientationNew);
	}
	
	Session.prototype.viewSetFront = function()
	{
		this.viewSet
		(
			new Orientation
			(
				new Coords(0, 1, 0), // forward
				new Coords(1, 0, 0), // right
				new Coords(0, 0, 1) // down
			)
		);
	}
	
	Session.prototype.viewSetSelected = function()
	{
		var scene = this.scene;
		var camera = scene.camera;
		var mesh = scene.mesh;
		var selection = scene.selection;
		
		var selectionMedian = selection.medianForMesh(mesh);
		if (selectionMedian != null)
		{
			var constraintLookAt = this.scene.camera.constraints[1]; // hack
			constraintLookAt.targetPos.overwriteWith(selectionMedian);
		}
	}
		
	Session.prototype.viewSetSide = function()
	{
		this.viewSet
		(
			new Orientation
			(
				new Coords(-1, 0, 0), // forward
				new Coords(0, 1, 0), // right
				new Coords(0, 0, 1) // down
			)
		);
	}
			
	Session.prototype.viewSetTop = function()
	{
		this.viewSet
		(
			new Orientation
			(
				new Coords(0, 0, 1), // forward
				new Coords(1, 0, 0), // right
				new Coords(0, -1, 0) // down
			)
		);
	}
	
	// serializer
	
	Session.prototype.serializerBuild = function()
	{
		return new Serializer
		([
			Camera,
			Constraint_KeepDistance,
			Constraint_LookAt,
			Constraint_Upright,
			Coords,
			Cursor,
			Edge,
			Face,
			Location,
			Mesh,
			Orientation,
			Scene,
			Selection,
			Transform_Multiple,
			Transform_Orient,
			Transform_OrientInverse,
			Transform_Perspective,
			Transform_PerspectiveInverse,
			Transform_Rotate,
			Transform_Scale,
			Transform_Translate,
			Transform_TranslateInverse,
		]);
	}
}

function Transform_Multiple(children)
{
	this.children = children;
}
{
	Transform_Multiple.prototype.transformCoords = function(coordsToTransform)
	{
		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			child.transformCoords(coordsToTransform);
		}
		
		return coordsToTransform;
	}
}

function Transform_Orient(orientation)
{
	this.orientation = orientation;
}
{
	Transform_Orient.prototype.transformCoords = function(coordsToTransform)
	{
		coordsToTransform.overwriteWithXYZ
		(
			this.orientation.right.dotProduct(coordsToTransform),
			this.orientation.down.dotProduct(coordsToTransform),
			this.orientation.forward.dotProduct(coordsToTransform)
		);
	
		return coordsToTransform;
	}
}

function Transform_OrientInverse(orientation)
{
	this.orientation = orientation;
}
{
	Transform_OrientInverse.prototype.transformCoords = function(coordsToTransform)
	{
		var original = coordsToTransform.clone();
		
		coordsToTransform.overwriteWith
		(
			this.orientation.right.clone().multiplyScalar(original.x)
		).add
		(
			this.orientation.down.clone().multiplyScalar(original.y)
		).add
		(
			this.orientation.forward.clone().multiplyScalar(original.z)
		);
	
		return coordsToTransform;
	}
}

function Transform_Perspective(focalLength)
{
	this.focalLength = focalLength;
}
{
	Transform_Perspective.prototype.transformCoords = function(coordsToTransform)
	{
		if (coordsToTransform.z != 0)
		{
			var multiplier = this.focalLength / coordsToTransform.z;
			coordsToTransform.x *= multiplier;
			coordsToTransform.y *= multiplier;
			coordsToTransform.z *= this.focalLength;
		}
		return coordsToTransform;
	}
}

function Transform_PerspectiveInverse(focalLength)
{
	this.focalLength = focalLength;
}
{
	Transform_PerspectiveInverse.prototype.transformCoords = function(coordsToTransform)
	{
		if (coordsToTransform.z != 0)
		{
			var multiplier = coordsToTransform.z / (this.focalLength * this.focalLength); // hack
			coordsToTransform.x *= multiplier;
			coordsToTransform.y *= multiplier;
			coordsToTransform.z /= this.focalLength; // fix
		}
		return coordsToTransform;
	}
}

function Transform_Rotate(axis, angleInCycles)
{
	this.axis = axis;
	this.angleInCycles = angleInCycles;
	
	var orientation = Orientation.fromForwardAndDown
	(
		this.axis.clone().right(), 
		this.axis
	);
	this.transformOrient = new Transform_Orient(orientation);
}
{
	Transform_Rotate.prototype.transformCoords = function(coordsToTransform)
	{
		this.transformOrient.transformCoords
		(
			coordsToTransform
		);
		
		// todo
		var one = 1;
		
		return coordsToTransform;
	}
}

function Transform_Scale(scaleFactors)
{
	this.scaleFactors = scaleFactors;
}
{
	Transform_Scale.prototype.transformCoords = function(coordsToTransform)
	{
		return coordsToTransform.multiply(this.scaleFactors);
	}
}

function Transform_Translate(offset)
{
	this.offset = offset;
}
{
	Transform_Translate.prototype.transformCoords = function(coordsToTransform)
	{
		return coordsToTransform.add(this.offset);
	}
}

function Transform_TranslateInverse(offset)
{
	this.offset = offset;
}
{
	Transform_TranslateInverse.prototype.transformCoords = function(coordsToTransform)
	{
		return coordsToTransform.subtract(this.offset);
	}
}

// run

main();

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , , , | Leave a comment

Drawing a Rotated Image to an HTML5 Canvas

The JavaScript code below, when run, prompts the user to specify an image file to be uploaded, and then displays that image, scaled to 100 x 100 pixels and rotated 45 degrees clockwise in the center of an HTML5 canvas.

ImageRotatedOnHTML5Canvas.png


<html>
<body>

<!-- ui -->

<input type="file" onchange="inputFileImageToDraw_Changed(this);" />

<!-- ui ends -->

<script type="text/javascript">

// ui event handlers

function inputFileImageToDraw_Changed(inputFileImageToDraw)
{
	var fileToLoad = inputFileImageToDraw.files[0];
	if (fileToLoad != null)
	{
		if (fileToLoad.type.match("image.*") != null)
		{
			var fileReader = new FileReader();
			fileReader.onload =
				inputFileImageToDraw_Changed_FileLoaded;
			fileReader.readAsDataURL(fileToLoad);
		}
	}
}

function inputFileImageToDraw_Changed_FileLoaded(fileLoadedEvent)
{
	var imageToDraw = document.createElement("img");
	imageToDraw.src = fileLoadedEvent.target.result;

	var display = new Display
	(
		new Coords(200, 200), "Gray", "Black"
	);
	display.initialize();

	display.clear();

	display.drawImageAtPosWithSizeAndRotation
	(
		imageToDraw,
		new Coords(100, 100), // pos
		new Coords(100, 100), // size
		.125 // rotationInCycles
	);

}
// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}

function Display(sizeInPixels, colorFore, colorBack)
{
	this.sizeInPixels = sizeInPixels;
	this.colorFore = colorFore;
	this.colorBack = colorBack;
}
{
	// constants

	Display.RadiansPerCycle = Math.PI * 2;

	// methods

	Display.prototype.clear = function()
	{
		this.graphics.fillStyle = this.colorBack;
		this.graphics.fillRect
		(
			0, 0, this.sizeInPixels.x, this.sizeInPixels.y
		);

		this.graphics.strokeStyle = this.colorFore;
		this.graphics.strokeRect
		(
			0, 0, this.sizeInPixels.x, this.sizeInPixels.y
		);
	}

	Display.prototype.drawImageAtPosWithSizeAndRotation = function
	(
		imageToDraw, pos, size, rotationInCycles
	)
	{
		this.graphics.save();
		this.graphics.translate(pos.x, pos.y);
		var rotationInRadians =
			rotationInCycles * Display.RadiansPerCycle;
		this.graphics.rotate(rotationInRadians);
		this.graphics.drawImage
		(
			imageToDraw,
			0 - size.x / 2, 0 - size.y / 2, // pos
			size.x, size.y // size
		);
		this.graphics.restore();
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.sizeInPixels.x;
		this.canvas.height = this.sizeInPixels.y;
		document.body.appendChild(this.canvas);

		this.graphics = this.canvas.getContext("2d");
	}
}

</script>

</body>
</html>

Posted in Uncategorized | Tagged , , , , | Leave a comment