Converting Map Images to Meshes

The JavaScript code below, when run, prompts the user to upload an image file. When this file is uploaded, the program traces any orthogonal, black, single-pixel lines in the image and converts them into a two-dimensional “mesh” object. In other words, it converts a very simple raster object into a very simple vector object. It then displays both the original image and the mesh as an overlay.

To see the code in action, copy it into an .html file and open that file in a web browser than runs JavaScript. If you’re running the program from your local filesystem, rather than on a web server, you may have to temporarily disable certain security features in your browser to avoid getting errors related to “cross-site scripting”. For example, while I was testing this in Google’s Chrome browser, I had to run the browser with the command-line option “–allow-file-access-from-files”. Also, you’ll want to make sure that your map image is fairly small, say 128×128 pixels, contains only black and white pixels, and that all lines are orthogonal (perfectly horizontal or vertical). A test image is provided below.

The ultimate purpose of this code is to serve as a first step toward a “level designer” for a three-dimensional video game, such as the one presented in a previous post.

Map-Complex

ImageToMesh

UPDATE 2015/03/04 – I have updated this program to display the walls as three-dimensional wireframes, and added a movable camera to view the resulting map.  I also added support for diagonal walls, though currently only diagonals with a 1:1 slope are supported.  Also, there’s some support for “altitude”, that is, walls with a sloping lower edge, which would be encoded on the map by replacing the black pixels of the walls with colored pixels whose hue indicates the depth of the wall at that point (red for shallow, yellow for medium, purple for deep, and so on).  But this feature hasn’t been thoroughly tested, and anyway there’s not much point to it when there’s no floor anyway.

Map-Diagonals

ImageToMesh-Diagonals

<html>
<body>

<p>Upload an image file, then use the W, A, S, and D keys to move the camera.</p>
<input id="inputMapImageFile" type="file" onchange="inputMapImageFile_OnChange(this);"></input>

<script type="text/javascript">

// events

function inputMapImageFile_OnChange(inputMapImageFile)
{
	var fileUploaded = inputMapImageFile.files[0];
	var imageUploaded = new Image(fileUploaded.name);
	imageUploaded.initialize
	(
		imageUploaded_OnLoad
	);
}

function imageUploaded_OnLoad(event)
{
	var imageMap = this;

	var world = new World
	(
		imageMap,
		new Camera
		(
			new Coords(200, 200, 0), // viewSize
			100, // focalLength
			new Coords(100, 100, -100), // pos
			new Orientation
			(
				new Coords(0, 0, 1),
				new Coords(0, 1, 0)
			)
		)
	);

	Globals.Instance.initialize(world);
}

// classes

function ArrayExtensions()
{}
{
	Array.prototype.insert = function(indexToInsertAt, itemToInsert)
	{
		this.splice(indexToInsertAt, 0, itemToInsert);
	}

	Array.prototype.remove = function(itemToRemove)
	{
		var indexToRemoveAt = this.indexOf(itemToRemove);
		this.removeAt(indexToRemoveAt);
	}

	Array.prototype.removeAt = function(indexToRemoveAt)
	{
		this.splice(indexToRemoveAt, 1);
	}
}

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.prototype.containsPos = function(posToCheck)
	{
		return posToCheck.isInRangeMinMax(this.min, this.max);
	}

	Bounds.prototype.overlapWith = function(bounds1)
	{
		var returnValue = false;

		var bounds = [ this, bounds1 ];

		for (var b = 0; b < bounds.length; b++)
		{
			var boundsThis = bounds[b];
			var boundsOther = bounds[1 - b];			

			var doAllDimensionsOverlapSoFar = true;

			for (var d = 0; d < Coords.NumberOfDimensions; d++)
			{
				if 
				(
					boundsThis.max.dimension(d) < boundsOther.min.dimension(d)
					|| boundsThis.min.dimension(d) > boundsOther.max.dimension(d)
				)
				{
					doAllDimensionsOverlapSoFar = false;
					break;
				}
			}

			if (doAllDimensionsOverlapSoFar == true)
			{
				returnValue = true;
				break;
			}
		}

		return returnValue;
	}


	Bounds.prototype.setFromPositions = function(positions)
	{
		this.min.overwriteWith(positions[0]);
		this.max.overwriteWith(positions[0]);

		for (var i = 1; i < positions.length; i++)
		{
			var pos = positions[i];

			for (var d = 0; d < Coords.NumberOfDimensions; d++)
			{
				var posDimension = pos.dimension(d);
				if (posDimension < this.min.dimension(d))
				{
					this.min.dimensionSet(d, posDimension);
				}
				if (posDimension > this.max.dimension(d))
				{
					this.max.dimensionSet(d, posDimension);
				}				
			}
		}
	}
}

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);
	this.transformCamera = new Transform_Camera(this);
}

function Collision(pos, distanceToCollision, colliders)
{
	this.pos = pos;
	this.distanceToCollision = distanceToCollision;
	this.colliders = colliders;
}
{
	// static methods

	Collision.addCollisionsOfEdgeAndMeshToList = function(edge, mesh, listToAddTo)
	{
		for (var f = 0; f < mesh.faces.length; f++)
		{
			var face = mesh.faces[f];
	
			if (face.plane.normal.dotProduct(edge.direction) < 0)
			{
				var collision = Collision.findCollisionOfEdgeAndFace
				(
					edge,
					face	
				);

				if (collision != null)
				{
					collision.colliders["Mesh"] = mesh;
					listToAddTo.push(collision);
				}
			}
		}

		return listToAddTo;
	}

	Collision.findClosest = function(collisionsToCheck)
	{
		var collisionClosest = collisionsToCheck[0];
		
		for (var i = 1; i < collisionsToCheck.length; i++)
		{
			var collision = collisionsToCheck[i];
			if (collision.distanceToCollision < collisionClosest.distanceToCollision)
			{
				collisionClosest = collision;
			}
		}

		return collisionClosest;
	}

	Collision.findCollisionOfEdgeAndFace = function(edge, face)
	{
		var returnValue = null;

		var collisionOfEdgeWithFacePlane = Collision.findCollisionOfEdgeAndPlane
		(
			edge,
			face.plane
		);

		if (collisionOfEdgeWithFacePlane != null)
		{
			var isWithinFace = Collision.isPosWithinFace
			(
				collisionOfEdgeWithFacePlane.pos, 
				face
			);

			if (isWithinFace == true)
			{
				returnValue = collisionOfEdgeWithFacePlane;
				returnValue.colliders["Face"] = face;
			}
		}

		return returnValue;
	}

	Collision.findCollisionOfEdgeAndPlane = function(edge, plane)
	{
		var returnValue = null;

		var ray = new Ray(edge.vertices[0], edge.direction);

		var collisionOfRayAndPlane = Collision.findCollisionOfRayAndPlane
		(
			ray, plane
		);

		if 
		(
			collisionOfRayAndPlane != null 
			&& collisionOfRayAndPlane.distanceToCollision <= edge.length
		)
		{
			returnValue = collisionOfRayAndPlane;
			returnValue.colliders["Edge"] = edge;	
		}

		return returnValue;
	}

	Collision.findCollisionOfRayAndFace = function(ray, face)
	{
		var returnValue = null;

		var collisionOfRayAndPlane = Collision.findCollisionOfRayAndPlane
		(
			ray, face.plane
		);

		if 
		(
			collisionOfRayAndPlane != null 
			&& Collision.isPosWithinFace(collisionOfRayAndPlane.pos, face) == true
		)
		{
			returnValue = collisionOfRayAndPlane;
			returnValue.colliders["Face"] = face;
		}

		return returnValue;
	}

	Collision.findCollisionOfRayAndPlane = function(ray, plane)
	{
		var returnValue = null;

		var distanceToCollision = 
			(
				plane.distanceFromOrigin 
				- plane.normal.dotProduct(ray.vertex)
			)
			/ plane.normal.dotProduct(ray.direction);

		if (distanceToCollision >= 0)
		{
			var collisionPos = ray.direction.clone().multiplyScalar
			(
				distanceToCollision
			).add
			(
				ray.vertex
			);

			var colliders = [];
			colliders["Ray"] = ray;
			colliders["Plane"] = plane;
	
			returnValue = new Collision
			(
				collisionPos,
				distanceToCollision,
				colliders
			);
		}

		return returnValue;
	}

	Collision.isPosWithinFace = function(posToCheck, face)
	{
		var displacementFromVertex0ToCollision = new Coords();

		var isPosWithinAllEdgesOfFaceSoFar = true;
		var edgeFromFaceTransverse = new Coords();

		for (var e = 0; e < face.edges.length; e++)
		{
			var edgeFromFace = face.edges[e];
			edgeFromFaceTransverse.overwriteWith
			(
				edgeFromFace.direction
			).crossProduct
			(
				face.plane.normal	
			);

			displacementFromVertex0ToCollision.overwriteWith
			(
				posToCheck
			).subtract
			(
				edgeFromFace.vertices[0]
			);		

			var displacementProjectedAlongEdgeTransverse = 
				displacementFromVertex0ToCollision.dotProduct
				(
					edgeFromFaceTransverse
				);

			if (displacementProjectedAlongEdgeTransverse > 0)
			{
				isPosWithinAllEdgesOfFaceSoFar = false;
				break;
			}
		}

		return isPosWithinAllEdgesOfFaceSoFar;
	}

	Collision.findDistanceOfPositionAbovePlane = function(posToCheck, plane)
	{
		var returnValue = posToCheck.dotProduct
		(
			plane.normal
		) - plane.distanceFromOrigin;

		return returnValue;
	}
}

function Color(componentsRGBA)
{
	this.componentsRGBA = componentsRGBA;

	this.systemColor = 
		"rgba(" 
		+ this.componentsRGBA[0] + "," 
		+ this.componentsRGBA[1] + ","
		+ this.componentsRGBA[2] + ","
		+ (this.componentsRGBA[3] / 255)
		+ ")";
}
{
	Color.prototype.equals = function(other)
	{
		var returnValue = true;

		for (var i = 0; i < this.componentsRGBA.length; i++)
		{
			var componentThis = this.componentsRGBA[i];
			var componentOther = other.componentsRGBA[i];

			if (componentThis != componentOther)
			{
				returnValue = false;
				break;
			}
		}
	
		return returnValue;
	}

	Color.prototype.hue = function()
	{
		var returnValue = null;

		var red = this.componentsRGBA[0];
		var green = this.componentsRGBA[1];
		var blue = this.componentsRGBA[2];

		var hue = null;
		var saturation = null;
		var value = null;

		var rgbComponentMin = red;
		if (rgbComponentMin > green)
		{
			rgbComponentMin = green;
		}
		if (rgbComponentMin > blue)
		{
			rgbComponentMin = blue;
		}

		var rgbComponentMax = red;
		if (rgbComponentMax < green)
		{
			rgbComponentMax = green;
		}
		if (rgbComponentMax < blue)
		{
			rgbComponentMax = blue;
		}

		var rgbComponentRange = rgbComponentMax - rgbComponentMin;

		value = rgbComponentMax;

		if (rgbComponentRange == 0)
		{
			hue = 0;
		   	saturation = 0;
		}
		else
		{
			if (rgbComponentMax == red)
			{
				hue = Math.abs(green - blue) / rgbComponentRange;
			}
			else if (rgbComponentMax == green)
			{
				hue = Math.abs(blue - red) / rgbComponentRange + (1 / 3);
			}
			else if (rgbComponentMax == blue)
			{
				hue = Math.abs(red - green) / rgbComponentRange + (2 / 3);
			}

			saturation = rgbComponentRange / value;
		}

		return hue;
	}

	Color.prototype.luminance = function()
	{
		var returnValue = Math.floor
		(
			(
				this.componentsRGBA[0]
				+ this.componentsRGBA[1]
				+ this.componentsRGBA[2]
			) 
			/ 3
		);

		return returnValue;
	}
}

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

	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.overwriteWithDimensions
		(
			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.dimension = function(dimensionIndex)
	{
		var returnValue;

		if (dimensionIndex == 0)
		{
			returnValue = this.x;
		}
		else if (dimensionIndex == 1)
		{
			returnValue = this.y;
		}
		else
		{
			returnValue = this.z;
		}

		return returnValue;		
	}

	Coords.prototype.dimensionSet = function(dimensionIndex, value)
	{
		if (dimensionIndex == 0)
		{
			this.x = value;
		}
		else if (dimensionIndex == 1)
		{
			this.y = value;
		}
		else
		{
			this.z = value;
		}

		return this;
	}

	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.equalsXY = function(other)
	{
		var returnValue = 
		(
			this.x == other.x
			&& this.y == other.y
		);
		return returnValue;
	}

	Coords.prototype.isInRangeMinMax = function(min, max)
	{
		var returnValue =
		(
			this.x >= min.x
			&& this.y >= min.y
			&& this.z >= min.z
			&& this.x <= max.x
			&& this.y <= max.y
			&& this.z <= max.z
		);

		return returnValue;
	}

	Coords.prototype.isInRangeMax = function(max)
	{
		var returnValue =
		(
			this.x >= 0
			&& this.y >= 0
			&& this.z >= 0
			&& this.x <= max.x
			&& this.y <= max.y
			&& this.z <= max.z
		);

		return returnValue;
	}

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


	Coords.prototype.magnitudeOrthogonal = function()
	{
		return Math.abs(this.x) + Math.abs(this.y) + Math.abs(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.overwriteWithDimensions = 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;
	}
}

function DisplayHelper()
{}
{
	DisplayHelper.prototype.clear = function()
	{
		this.graphics.fillStyle = "White";
		this.graphics.fillRect
		(
			0, 0,
			this.viewSizeInPixels.x,
			this.viewSizeInPixels.y
		);

		this.graphics.strokeStyle = "LightGray";
		this.graphics.lineWidth = 1;
		this.graphics.lineJoin = null;
		this.graphics.strokeRect
		(
			0, 0,
			this.viewSizeInPixels.x,
			this.viewSizeInPixels.y
		);
	}

	DisplayHelper.prototype.drawImage = function(image, drawPosInPixels)
	{
		this.graphics.drawImage
		(
			image.systemImage,
			drawPosInPixels.x,
			drawPosInPixels.y
		);
	}

	DisplayHelper.prototype.drawMeshAbsolute = function(mesh)
	{
		this.graphics.strokeStyle = mesh.color;
		this.graphics.lineWidth = 8;
		this.graphics.lineJoin = "round";
		
		for (var f = 0; f < mesh.vertexIndicesForFaces.length; f++)
		{
			var vertexIndicesForFace = mesh.vertexIndicesForFaces[f];

			this.graphics.beginPath();

			for (var vi = 0; vi < vertexIndicesForFace.length; vi++)
			{
				var vertexIndex = vertexIndicesForFace[vi];
				var vertex = mesh.vertices[vertexIndex];

				if (vi == 0)
				{
					this.graphics.moveTo
					(
						vertex.x,
						vertex.y
					);
				}
				else
				{
					this.graphics.lineTo
					(
						vertex.x,
						vertex.y
					);
				}
			}

			this.graphics.closePath();
			this.graphics.stroke();
		}
	}

	DisplayHelper.prototype.drawMeshForCamera = function(mesh, camera)
	{
		this.graphics.strokeStyle = mesh.color;
		this.graphics.fillStyle = mesh.color;

		var drawPos = new Coords(0, 0, 0);
		this.graphics.beginPath();

		var vertexIndicesForFaces = mesh.vertexIndicesForFaces;
		for (var f = 0; f < vertexIndicesForFaces.length; f++)
		{
			var vertexIndicesForFace = vertexIndicesForFaces[f];

			for (var vi = 0; vi < vertexIndicesForFace.length; vi++)
			{
				var vertexIndex = vertexIndicesForFace[vi];
				var vertex = mesh.vertices[vertexIndex];

				drawPos.overwriteWith(vertex);
				camera.transformCamera.applyToCoords(drawPos);

				if (vi == 0)
				{
					this.graphics.moveTo(drawPos.x, drawPos.y);
				}
				else
				{
					this.graphics.lineTo(drawPos.x, drawPos.y);
				}

				if (this.isDebugModeActive == true)
				{
					this.graphics.fillText
					(
						vertex.toString(),
						drawPos.x, 
						drawPos.y
					);
				}
				
			}

			this.graphics.closePath();
			this.graphics.stroke();
		}
	}


	DisplayHelper.prototype.drawWorld = function(world)
	{
		this.clear();

		//this.drawImage(world.imageForMap, new Coords(0, 0));

		var meshesForMap = world.meshesForMap;
		for (var i = 0; i < meshesForMap.length; i++)
		{
			var mesh = meshesForMap[i];
			//this.drawMeshAbsolute(mesh);
			this.drawMeshForCamera(mesh, world.camera);
		}
	}

	DisplayHelper.prototype.initialize = function(viewSizeInPixels)
	{
		this.viewSizeInPixels = viewSizeInPixels;

		var canvas = document.createElement("canvas");
		canvas.width = this.viewSizeInPixels.x;
		canvas.height = this.viewSizeInPixels.y;
		
		this.graphics = canvas.getContext("2d");

		document.body.appendChild(canvas);
	}
}

function Edge(vertices)
{
	this.vertices = vertices;
	this.displacement = this.vertices[1].clone().subtract
	(
		this.vertices[0]
	);
	this.length = this.displacement.magnitude();
	this.direction = this.displacement.clone().divideScalar
	(
		this.length
	);
}
{
	Edge.prototype.isConnectedToXY = function(other)
	{
		var returnValue = false;

		for (var i = 0; i < this.vertices.length; i++)
		{
			var vertexThis = this.vertices[i];
				
			for (var j = 0; j < other.vertices.length; j++)
			{
				var vertexOther = other.vertices[j];
				
				var areVerticesEqual = vertexThis.equalsXY
				(
					vertexOther
				);
	
				if (areVerticesEqual == true)
				{
					returnValue = true;					
					break;
				}
			}
		}

		return returnValue;

	}

	Edge.prototype.mergeWith = function(other)
	{
		var returnValue = null; 

		var codirectionalityXY = Math.abs
		(
			this.direction.clone().dimensionSet(2, 0).normalize().dotProduct
			(
				other.direction.clone().dimensionSet(2,0).normalize()
			)
		);

		var codirectionalityThreshold = 1;

		if (codirectionalityXY >= codirectionalityThreshold)
		{
			for (var i = 0; i < this.vertices.length; i++)
			{
				var vertexThis = this.vertices[i];
					
				for (var j = 0; j < other.vertices.length; j++)
				{
					var vertexOther = other.vertices[j];
					
					var areVerticesEqual = vertexThis.equals
					(
						vertexOther
					);
		
					if (areVerticesEqual == true)
					{	
						var vertexThisOuter = this.vertices[1 - i];
						var vertexOtherOuter = other.vertices[1 - j];

						if (vertexThis.z == 0)
						{
							returnValue = new Edge
							([
								vertexThisOuter,
								vertexOtherOuter
							]);
						}
						
						break;
					}
				}
			}
		}

		return returnValue;	
	}
}

function Face(vertices)
{
	this.vertices = vertices;
	this.bounds = new Bounds(new Coords(0, 0, 0), new Coords(0, 0, 0));

	this.plane = new Plane
	(
		new Coords(), 
		new Coords()
	).fromPoints
	(
		this.vertices[0],
		this.vertices[1],
		this.vertices[2]
	);

	this.edges = [];

	for (var i = 0; i < this.vertices.length; i++)
	{
		var iNext = i + 1;
		if (iNext >= this.vertices.length)
		{
			iNext = 0;
		}

		var vertexPos = this.vertices[i];
		var vertexPosNext = this.vertices[iNext];

		var edge = new Edge([vertexPos, vertexPosNext]);

		this.edges.push(edge);
	}

	this.bounds.setFromPositions(this.vertices);
}
{
	Face.prototype.recalculateDerivedValues = function()
	{
		this.plane.fromPoints
		(
			this.vertices[0].pos,
			this.vertices[1].pos,
			this.vertices[2].pos
		);

		for (var i = 0; i < this.edges.length; i++)
		{
			var edge = this.edges[i];

			edge.recalculateDerivedValues();	
		}

		var vertexPositions = Vertex.addPositionsOfManyToList(this.vertices, []);
		this.bounds.setFromPositions(vertexPositions);

	}
}

function Globals()
{}
{
	Globals.Instance = new Globals();

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

		this.displayHelper = new DisplayHelper();
		this.displayHelper.initialize(this.world.camera.viewSize);
		this.displayHelper.drawWorld(this.world);

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

function Image(source)
{
	this.source = source;
}
{
	Image.prototype.colorOfPixelAtPos = function(pixelPos)
	{
		var imageDataForPixel = this.graphics.getImageData
		(
			pixelPos.x, pixelPos.y, 1, 1
		);
		var pixelComponentsAsUint8ClampedArray = imageDataForPixel.data;
		var pixelComponentsRGBA = 
		[
			pixelComponentsAsUint8ClampedArray[0],
			pixelComponentsAsUint8ClampedArray[1],
			pixelComponentsAsUint8ClampedArray[2],
			pixelComponentsAsUint8ClampedArray[3]
		];
		var returnValue = new Color(pixelComponentsRGBA);
		return returnValue;
	}

	Image.prototype.initialize = function(callback)
	{
		this.systemImage = document.createElement("img");
		this.systemImage.src = this.source;
		this.systemImage.onload = this.initialize_2.bind(this, callback);
	}

	Image.prototype.initialize_2 = function(callback)
	{
		this.size = new Coords
		(	
			this.systemImage.width,
			this.systemImage.height
		);

		var canvas = document.createElement("canvas");
		canvas.width = this.size.x;
		canvas.height = this.size.y;
		this.graphics = canvas.getContext("2d");
		this.graphics.drawImage(this.systemImage, 0, 0);

		callback.call(this);
	}
}

function ImageToMeshParser(colorToIgnore, colorForWall, wallHeight, depthMax)
{
	this.colorToIgnore = colorToIgnore;
	this.colorForWall = colorForWall;
	this.wallHeight = wallHeight;
	this.depthMax = depthMax;
}
{
	ImageToMeshParser.prototype.imageToMeshes = function(image)
	{
		var pointsOnWalls = this.imageToMeshes_1_ImageToPoints(image);

		var edgesForWalls = this.imageToMeshes_2_WallPointsToEdges(pointsOnWalls);

		edgesForWalls = this.imageToMeshes_3_EdgesMerge(edgesForWalls);

		edgesForWalls = this.imageToMeshes_4_EdgesCullDiagonalCorners(edgesForWalls);

		var edgeGroupsConnected = this.imageToMeshes_5_EdgesConnect(edgesForWalls);

		var meshesForWalls = this.imageToMeshes_6_EdgeGroupsToMeshes(edgeGroupsConnected);

		return meshesForWalls;
	}

	ImageToMeshParser.prototype.imageToMeshes_1_ImageToPoints = function(image)
	{
		var mapSize = image.size;

		var pointsOnWalls = [];

		var pixelPos = new Coords(0, 0, 0);

		for (var y = 0; y < mapSize.y; y++)
		{
			pixelPos.y = y;

			for (var x = 0; x < mapSize.x; x++)
			{
				pixelPos.x = x;

				var pixelColor = image.colorOfPixelAtPos(pixelPos);

				if (pixelColor.equals(this.colorToIgnore) == true)
				{
					// do nothing
				}
				else
				{
					var depth = 
						pixelColor.hue() 
						* this.depthMax;

					pointsOnWalls.push
					(
						pixelPos.clone().dimensionSet(2, depth)
					);
				}
			}
		}

		return pointsOnWalls;
	}

	ImageToMeshParser.prototype.imageToMeshes_2_WallPointsToEdges = function(pointsOnWalls)
	{
		var edgesForWalls = [];

		var distanceThreshold = 2;

		for (var i = 0; i < pointsOnWalls.length; i++)
		{
			var pointThis = pointsOnWalls[i];

			var pointsClosestSoFar = [];
			var distancesToPointsClosestSoFar = [];						

			for (var j = i + 1; j < pointsOnWalls.length; j++)
			{
				var pointOther = pointsOnWalls[j];
				
				var distanceBetweenPointsXY = pointThis.clone().subtract
				(
					pointOther
				).dimensionSet
				(
					2, 0
				).magnitude();

				if (distanceBetweenPointsXY < distanceThreshold)
				{	
					var d;
					for (d = 0; d < distancesToPointsClosestSoFar.length; d++)
					{
						var distance = distancesToPointsClosestSoFar[d];
						if (distanceBetweenPointsXY <= distance)
						{
							break;
						}
					}
			
					distancesToPointsClosestSoFar.insert
					(
						d, distanceBetweenPointsXY
					);
					pointsClosestSoFar.insert
					(
						d, pointOther
					);
				}
			}

			for (var d = 0; d < pointsClosestSoFar.length; d++)
			{
				var pointOther = pointsClosestSoFar[d];
				var edgeForPoints = new Edge
				([
					pointThis,
					pointOther
				]);
				edgesForWalls.push(edgeForPoints);
			}
		}

		return edgesForWalls;
	}

	ImageToMeshParser.prototype.imageToMeshes_3_EdgesMerge = function(edgesForWalls)
	{
		var wereAnyEdgesMergedInPreviousRun = true;

		while (wereAnyEdgesMergedInPreviousRun == true)
		{
			wereAnyEdgesMergedInPreviousRun = false;

			var edgesForWallsNext = [];

			for (var i = 0; i < edgesForWalls.length; i++)
			{
				var edgeThis = edgesForWalls[i];

				var j;
				var edgeMerged = null;

				for (j = i + 1; j < edgesForWalls.length; j++)
				{
					var edgeOther = edgesForWalls[j];

					edgeMerged = edgeThis.mergeWith
					(
						edgeOther
					);

					if (edgeMerged != null)
					{
						break;
					}
				}

				if (edgeMerged != null)
				{
					edgesForWallsNext.push(edgeMerged);
					wereAnyEdgesMergedInPreviousRun = true;
					edgesForWalls.splice(j, 1);
				}
				else
				{
					edgesForWallsNext.push(edgeThis);
				}
			}

			edgesForWalls = edgesForWallsNext;
		}

		return edgesForWalls;
	}	

	ImageToMeshParser.prototype.imageToMeshes_4_EdgesCullDiagonalCorners = function(edgesForWalls)
	{
		var indicesOfEdgesToCull = [];

		for (var e = 0; e < edgesForWalls.length; e++)
		{
			var edgeForWall = edgesForWalls[e];

			var magnitudeOrthogonal = edgeForWall.displacement.magnitudeOrthogonal();

			if (magnitudeOrthogonal == 2)
			{
				indicesOfEdgesToCull.insert(0, e);
			}
		}

		for (var i = 0; i < indicesOfEdgesToCull.length; i++)
		{
			var indexOfEdgeToCull = indicesOfEdgesToCull[i];
			edgesForWalls.removeAt(indexOfEdgeToCull);
		}

		return edgesForWalls;
	}

	ImageToMeshParser.prototype.imageToMeshes_5_EdgesConnect = function(edgesForWalls)
	{
		var edgeGroupsConnected = [];

		for (var i = 0; i < edgesForWalls.length; i++)
		{
			var edgeThis = edgesForWalls[i];
			var edgeThisAsGroup = [ edgeThis ];
			edgeGroupsConnected.push(edgeThisAsGroup);
		}

		var wereAnyGroupsMerged = true;

		while (wereAnyGroupsMerged == true)
		{
			wereAnyGroupsMerged = false;

			for (var g = 0; g < edgeGroupsConnected.length; g++)
			{
				var edgeGroupThis = edgeGroupsConnected[g];
	
				for (var h = g + 1; h < edgeGroupsConnected.length; h++)
				{
					var edgeGroupOther = edgeGroupsConnected[h];
	
					areGroupsConnected = false;
	
					for (var i = 0; i < edgeGroupThis.length; i++)
					{
						var edgeThis = edgeGroupThis[i];
						
						for (var j = 0; j < edgeGroupOther.length; j++)
						{
							var edgeOther = edgeGroupOther[j];
							var areEdgesConnectedXY = edgeThis.isConnectedToXY
							(
								edgeOther
							);
	
							if (areEdgesConnectedXY == true)
							{
								areGroupsConnected = true;
								wereAnyGroupsMerged = true;
								break;
							}
						}
	
						if (areGroupsConnected == true)
						{
							break;
						}
					}
	
					if (areGroupsConnected == true)
					{
						for (var k = 0; k < edgeGroupOther.length; k++)
						{
							var edgeToAppend = edgeGroupOther[k];
							edgeGroupThis.push(edgeToAppend);
						}
						edgeGroupsConnected.splice(h, 1);
						break;
					}
				}
			}
		}

		return edgeGroupsConnected;
	}

	ImageToMeshParser.prototype.imageToMeshes_6_EdgeGroupsToMeshes = function(edgeGroupsConnected)
	{
		var returnValues = [];	

		for (var g = 0; g < edgeGroupsConnected.length; g++)
		{
			var edgesInGroup = edgeGroupsConnected[g];

			var verticesMerged = [];
			var vertexIndicesForFaces = [];

			for (var e = 0; e < edgesInGroup.length; e++)
			{
				var edge = edgesInGroup[e];
	
				for (var i = 0; i < edge.vertices.length; i++)
				{
					var edgeVertex = edge.vertices[i];

					if (verticesMerged.indexOf(edgeVertex) == -1)
					{
						var hasEdgeVertexBeenMerged = false;

						for (var j = 0; j < verticesMerged.length; j++)
						{
							var vertexMerged = verticesMerged[j];
							if (vertexMerged.equals(edgeVertex) == true)
							{
								edge.vertices[i] = vertexMerged;
								hasEdgeVertexBeenMerged = true;
								break;
							}
						}
	
						if (hasEdgeVertexBeenMerged == false)
						{
							verticesMerged.push(edgeVertex);
						}
					}
				}
			}

			var numberOfCorners = verticesMerged.length;

			for (var v = 0; v < numberOfCorners; v++)
			{
				var vertex = verticesMerged[v];
				var vertexAbove = vertex.clone().dimensionSet
				(
					2, 0 - this.wallHeight
				);
				verticesMerged.push(vertexAbove);
			}

			var vertexIndicesForFaces = [];

			for (var e = 0; e < edgesInGroup.length; e++)
			{
				var edge = edgesInGroup[e];
				var edgeVertices = edge.vertices;

				var vertexIndicesForFace = 
				[
					verticesMerged.indexOf(edgeVertices[0]),
					verticesMerged.indexOf(edgeVertices[1]),
				];

				vertexIndicesForFace.push
				(
					vertexIndicesForFace[1] + numberOfCorners
				);
				vertexIndicesForFace.push
				(
					vertexIndicesForFace[0] + numberOfCorners
				);

				vertexIndicesForFaces.push(vertexIndicesForFace);
			}				

			var hueMax = 360;
			var hue = Math.floor(Math.random() * hueMax);
			var meshColor = "hsl(" + hue + ", 100%, 50%)";

			var mesh = new Mesh
			(
				"Mesh" + i,
				meshColor,
				verticesMerged,
				vertexIndicesForFaces
			);

			returnValues.push(mesh);
		}

		return returnValues;
	}
}

function InputHelper()
{}
{
	InputHelper.prototype.initialize = function()
	{
		document.body.onkeydown = this.handleEventKeyDown.bind(this);
		document.body.onkeyup = this.handleEventKeyUp.bind(this);
	}

	// events

	InputHelper.prototype.handleEventKeyDown = function(event)
	{
		this.keyCodePressed = event.keyCode;
		Globals.Instance.world.update();
	}

	InputHelper.prototype.handleEventKeyUp = function(event)
	{
		this.keyCodePressed = null;
		Globals.Instance.world.update();
	}
}

function Mesh(name, color, vertices, vertexIndicesForFaces)
{
	this.name = name;
	this.color = color;
	this.vertices = vertices;
	this.vertexIndicesForFaces = vertexIndicesForFaces;
}
{
	Mesh.prototype.face = function(faceIndex)
	{
		var verticesForFace = [];
		var vertexIndicesForFace = this.vertexIndicesForFaces[faceIndex];
		for (var vi = 0; vi < vertexIndicesForFace.length; vi++)
		{
			var vertexIndex = vertexIndicesForFace[vi];
			var vertex = this.vertices[vertexIndex];
			verticesForFace.push(vertex);
		}

		var returnValue = new Face(verticesForFace);

		return returnValue;
	}
}

function Plane(normal, distanceFromOrigin)
{
	this.normal = normal;
	this.distanceFromOrigin = distanceFromOrigin;
}
{
	// static variables
	Plane.DisplacementFromPoint0To1 = new Coords(0, 0, 0);

	// instance methods

	Plane.prototype.equals = function(other)
	{
		var returnValue = 
		(
			this.normal.equals(other.normal) 
			&& this.distanceFromOrigin == other.distanceFromOrigin
		);

		return returnValue;
	}

	Plane.prototype.fromPoints = function(point0, point1, point2)
	{
		var displacementFromPoint0To1 = Plane.DisplacementFromPoint0To1;
		displacementFromPoint0To1.overwriteWith
		(
			point1
		).subtract
		(
			point0
		);

		var displacementFromPoint0To2 = point2.clone().subtract(point0);

		this.normal.overwriteWith
		(
			displacementFromPoint0To1
		).crossProduct
		(
			displacementFromPoint0To2
		).normalize();

		this.distanceFromOrigin = this.normal.dotProduct
		(
			point0
		);

		return this;
	}

}

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

function Ray(vertex, direction)
{
	this.vertex = vertex;
	this.direction = direction;
}

function Transform_Camera(camera)
{
	this.camera = camera;

	this.transformTranslateInverse = new Transform_TranslateInverse(this.camera.pos);
	this.transformOrient = new Transform_Orient(this.camera.orientation);
	this.transformPerspective = new Transform_Perspective(this.camera.focalLength);
	this.transformTranslateCenter = new Transform_Translate(this.camera.viewSizeHalf);
}
{
	Transform_Camera.prototype.applyToCoords = function(coordsToTransform)
	{
		this.transformTranslateInverse.applyToCoords(coordsToTransform);

		this.transformOrient.applyToCoords(coordsToTransform);

		this.transformPerspective.applyToCoords(coordsToTransform);

		this.transformTranslateCenter.applyToCoords(coordsToTransform);

		return coordsToTransform;
	}	
}

function Transform_Perspective(focalLength)
{
	this.focalLength = focalLength;
}
{
	Transform_Perspective.prototype.applyToCoords = function(coordsToTransform)
	{
		var distanceFromFocus = coordsToTransform.z;
		coordsToTransform.multiplyScalar
		(
			this.focalLength
		).divideScalar
		(
			distanceFromFocus
		);
		coordsToTransform.z = distanceFromFocus;

		return coordsToTransform;
	}
}

function Transform_Translate(displacement)
{
	this.displacement = displacement;
}
{
	Transform_Translate.prototype.applyToCoords = function(coordsToTransform)
	{
		return coordsToTransform.add(this.displacement);
	}
}

function Transform_TranslateInverse(displacement)
{
	this.displacement = displacement;
}
{
	Transform_TranslateInverse.prototype.applyToCoords = function(coordsToTransform)
	{
		return coordsToTransform.subtract(this.displacement);
	}
}

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

function World(imageForMap, camera)
{
	this.imageForMap = imageForMap;
	this.camera = camera;
}
{
	World.prototype.initialize = function()
	{
		var colorToIgnore = new Color([255, 255, 255, 255]);
		var colorForWall = new Color([0, 0, 0, 255]);
		var wallHeight = 10;
		var parser = new ImageToMeshParser
		(
			colorToIgnore,
			colorForWall, 
			wallHeight,
			10 // depthMax
		);
		this.meshesForMap = parser.imageToMeshes(this.imageForMap);
	}

	World.prototype.update = function()
	{
		var inputHelper = Globals.Instance.inputHelper;
		var keyCodePressed = inputHelper.keyCodePressed;

		if (keyCodePressed != null)
		{
			var cameraPos = this.camera.pos;
			var cameraMoveAxes = new Orientation
			(
				new Coords(0, 0, 1),
				new Coords(0, 1, 0)
			);
			var cameraSpeed = 4;

			if (keyCodePressed == 65) // a
			{
				cameraPos.add
				(
					cameraMoveAxes.right.clone().multiplyScalar
					(
						0 - cameraSpeed
					)
				);
			}
			else if (keyCodePressed == 68) // d
			{
				cameraPos.add
				(
					cameraMoveAxes.right.clone().multiplyScalar
					(
						cameraSpeed
					)
				);
			}
			else if (keyCodePressed == 70) // f
			{
				cameraPos.add
				(
					cameraMoveAxes.forward.clone().multiplyScalar
					(
						cameraSpeed
					)
				);
			}
			else if (keyCodePressed == 82) // r
			{
				cameraPos.add
				(
					cameraMoveAxes.forward.clone().multiplyScalar
					(
						0 - cameraSpeed
					)
				);
			}
			else if (keyCodePressed == 83) // s
			{
				cameraPos.add
				(
					cameraMoveAxes.down.clone().multiplyScalar
					(
						cameraSpeed
					)
				);
			}
			else if (keyCodePressed == 87) // w
			{
				cameraPos.add
				(
					cameraMoveAxes.down.clone().multiplyScalar
					(
						0 - cameraSpeed
					)
				);
			}
		}

		Globals.Instance.displayHelper.drawWorld(this);
	}
}

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

This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s