babylon-navigation-mesh - npm Package Compare versions

Comparing version 1.1.3 to 1.1.4

.jshintrc

package.json

		{
		"name": "babylon-navigation-mesh",
		"version": "1.1.3",
		"version": "1.1.4",
		"description": "A toolkit to move on navigation mesh with BABYLONJS",
		@@ -5,0 +5,0 @@ "scripts": {

README.md

		@@ -48,6 +48,6 @@ # Babylon-navigation-mesh

		Article in progress
		An article is available to create and use a navigation mesh [here](https://www.wanadev.fr/43-tuto-creer-et-utiliser-un-maillage-de-navigation-avec-babylon-js/) (french)

		## Demo

		![](https://github.com/wanadev/babylon-navigation-mesh/blob/master/demo/demo.gif?raw=true)
		![](https://github.com/wanadev/babylon-navigation-mesh/blob/master/demo/demo.gif?raw=true)

1405

src/Navigation.js

		@@ -0,1 +1,3 @@
		"use strict";

		var Class = require("abitbol");
		@@ -6,2 +8,4 @@ var _ = require("lodash");

		var BABYLON = require("babylonjs");

		/**
		@@ -15,988 +19,981 @@ * This component generates screenshots of 3D models, in order to preview them when they are rendered.
		var Navigation = Class.$extend({
		__init__: function() {
		this.zoneNodes = {};
		this.astar = new Astar();
		},

		buildNodes: function (mesh) {
		var navigationMesh = this._buildNavigationMesh(mesh.geometry);
		__init__: function() {
		this.zoneNodes = {};
		this.astar = new Astar();
		},

		var zoneNodes = this._groupNavMesh(navigationMesh);
		buildNodes: function(mesh) {
		var navigationMesh = this._buildNavigationMesh(mesh.geometry);

		return zoneNodes;
		},
		var zoneNodes = this._groupNavMesh(navigationMesh);

		setZoneData: function (zone, data) {
		this.zoneNodes[zone] = data;
		},
		return zoneNodes;
		},

		getGroup: function (zone, position) {
		setZoneData: function(zone, data) {
		this.zoneNodes[zone] = data;
		},

		if (!this.zoneNodes[zone]) return null;
		getGroup: function(zone, position) {

		var closestNodeGroup = null;
		if (!this.zoneNodes[zone]) {
		return null;
		}

		var distance = Infinity;
		var closestNodeGroup = null;

		_.each(this.zoneNodes[zone].groups, function (group, index) {
		_.each(group, function (node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, position);
		if (measuredDistance < distance) {
		closestNodeGroup = index;
		distance = measuredDistance;
		}
		});
		});
		var distance = Infinity;

		return closestNodeGroup;
		},
		_.each(this.zoneNodes[zone].groups, function(group, index) {
		_.each(group, function(node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, position);
		if (measuredDistance < distance) {
		closestNodeGroup = index;
		distance = measuredDistance;
		}
		});
		});

		getRandomNode: function (zone, group, nearPosition, nearRange) {
		return closestNodeGroup;
		},

		if (!this.zoneNodes[zone]) return new BABYLON.Vector3();
		getRandomNode: function(zone, group, nearPosition, nearRange) {

		nearPosition = nearPosition \|\| null;
		nearRange = nearRange \|\| 0;
		if (!this.zoneNodes[zone]) return new BABYLON.Vector3();

		var candidates = [];
		nearPosition = nearPosition \|\| null;
		nearRange = nearRange \|\| 0;

		var polygons = this.zoneNodes[zone].groups[group];
		var candidates = [];

		_.each(polygons, function (p) {
		if (nearPosition && nearRange) {
		if (BABYLON.Vector3.DistanceSquared(nearPosition, p.centroid) < nearRange * nearRange) {
		candidates.push(p.centroid);
		}
		} else {
		candidates.push(p.centroid);
		}
		});
		var polygons = this.zoneNodes[zone].groups[group];

		return _.sample(candidates) \|\| new BABYLON.Vector3();
		},
		_.each(polygons, function(p) {
		if (nearPosition && nearRange) {
		if (BABYLON.Vector3.DistanceSquared(nearPosition, p.centroid) < nearRange * nearRange) {
		candidates.push(p.centroid);
		}
		} else {
		candidates.push(p.centroid);
		}
		});

		projectOnNavmesh: function (position, zone, group) {
		var allNodes = this.zoneNodes[zone].groups[group];
		var vertices = this.zoneNodes[zone].vertices;
		return _.sample(candidates) \|\| new BABYLON.Vector3();
		},

		var closestNode = null;
		var distance = Infinity;
		var finalProj = null, proj = null;
		projectOnNavmesh: function(position, zone, group) {
		var allNodes = this.zoneNodes[zone].groups[group];
		var vertices = this.zoneNodes[zone].vertices;

		for (var i = 0; i < allNodes.length; i++) {
		var node = allNodes[i];
		var closestNode = null;
		var distance = Infinity;
		var finalProj = null,
		proj = null,
		node = null,
		measuredDistance = 0;

		var proj = this._getProjectionOnNode(position, node, vertices);
		var measuredDistance = BABYLON.Vector3.DistanceSquared(proj, position);
		for (var i = 0; i < allNodes.length; i++) {
		node = allNodes[i];

		if (measuredDistance < distance) {
		distance = measuredDistance;
		//this.meshes[3].position.copyFrom(proj);
		finalProj = proj;
		closestNode = node;
		}
		proj = this._getProjectionOnNode(position, node, vertices);
		measuredDistance = BABYLON.Vector3.DistanceSquared(proj, position);

		}
		if (measuredDistance < distance) {
		distance = measuredDistance;
		//this.meshes[3].position.copyFrom(proj);
		finalProj = proj;
		closestNode = node;
		}

		return finalProj;
		},
		}

		_getProjectionOnNode: function(position, node, vertices) {
		return finalProj;
		},

		var A = this.getVectorFrom(vertices, node.vertexIds[0]);
		var B = this.getVectorFrom(vertices, node.vertexIds[1]);
		var C = this.getVectorFrom(vertices, node.vertexIds[2]);
		var u = B.subtract(A);
		var v = C.subtract(A);
		var n = BABYLON.Vector3.Cross(u, v).normalize();

		var plane = {
		normal: n,
		d: -A.dot(n)
		};
		var p = position.projectOnPlane(plane);
		// Compute barycentric coordinates (u, v, w) for
		// point p with respect to triangle (a, b, c)
		var barycentric = function(p, a, b, c) {
		var ret = {};
		_getProjectionOnNode: function(position, node, vertices) {

		var v0 = c.subtract(a),
		v1 = b.subtract(a),
		v2 = p.subtract(a);
		var A = this.getVectorFrom(vertices, node.vertexIds[0]);
		var B = this.getVectorFrom(vertices, node.vertexIds[1]);
		var C = this.getVectorFrom(vertices, node.vertexIds[2]);
		var u = B.subtract(A);
		var v = C.subtract(A);
		var n = BABYLON.Vector3.Cross(u, v).normalize();

		var d00 = v0.dot(v0);
		var d01 = v0.dot(v1);
		var d02 = v0.dot(v2);
		var d11 = v1.dot(v1);
		var d12 = v1.dot(v2);
		var denom = d00 * d11 - d01 * d01;
		ret.u = (d11 * d02 - d01 * d12) / denom;
		ret.v = (d00 * d12 - d01 * d02) / denom;
		ret.w = 1 - ret.u - ret.v;
		var plane = {
		normal: n,
		d: -BABYLON.Vector3.Dot(A, n)
		};
		var p = position.projectOnPlane(plane);
		// Compute barycentric coordinates (u, v, w) for
		// point p with respect to triangle (a, b, c)
		var barycentric = function(p, a, b, c) {
		var ret = {};

		return ret;
		}
		var v0 = c.subtract(a),
		v1 = b.subtract(a),
		v2 = p.subtract(a);

		var bary = barycentric(p, A, B, C);
		var d00 = BABYLON.Vector3.Dot(v0, v0);
		var d01 = BABYLON.Vector3.Dot(v0, v1);
		var d02 = BABYLON.Vector3.Dot(v0, v2);
		var d11 = BABYLON.Vector3.Dot(v1, v1);
		var d12 = BABYLON.Vector3.Dot(v1, v2);
		var denom = d00 * d11 - d01 * d01;
		ret.u = (d11 * d02 - d01 * d12) / denom;
		ret.v = (d00 * d12 - d01 * d02) / denom;
		ret.w = 1 - ret.u - ret.v;

		bary.u = Math.min(Math.max(bary.u, 0), 1);
		bary.v = Math.min(Math.max(bary.v, 0), 1);
		return ret;
		};

		if (bary.u + bary.v >= 1) {
		var sum = bary.u + bary.v;
		bary.u /= sum;
		bary.v /= sum;
		}
		var bary = barycentric(p, A, B, C);

		var proj = A.add(B.subtract(A).scale(bary.v).add(C.subtract(A).scale(bary.u)));
		bary.u = Math.min(Math.max(bary.u, 0), 1);
		bary.v = Math.min(Math.max(bary.v, 0), 1);

		return proj;
		},
		if (bary.u + bary.v >= 1) {
		var sum = bary.u + bary.v;
		bary.u /= sum;
		bary.v /= sum;
		}

		findPath: function (startPosition, targetPosition, zone, group) {
		var proj = A.add(B.subtract(A).scale(bary.v).add(C.subtract(A).scale(bary.u)));

		var allNodes = this.zoneNodes[zone].groups[group];
		var vertices = this.zoneNodes[zone].vertices;
		return proj;
		},

		var closestNode = null;
		var distance = Infinity;
		findPath: function(startPosition, targetPosition, zone, group) {

		allNodes.forEach(function (node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, startPosition);
		if (measuredDistance < distance) {
		closestNode = node;
		distance = measuredDistance;
		}
		});
		var allNodes = this.zoneNodes[zone].groups[group];
		var vertices = this.zoneNodes[zone].vertices;

		var closestNode = null;
		var distance = Infinity;

		var farthestNode = null;
		distance = Infinity;
		allNodes.forEach(function(node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, startPosition);
		if (measuredDistance < distance) {
		closestNode = node;
		distance = measuredDistance;
		}
		});

		allNodes.forEach(function (node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, targetPosition);
		if (measuredDistance < distance &&
		this._isVectorInPolygon(targetPosition, node, vertices)) {
		farthestNode = node;
		distance = measuredDistance;
		}
		}.bind(this));

		// If we can't find any node, just go straight to the target
		if (!closestNode \|\| !farthestNode) {
		return null;
		}
		var farthestNode = null;
		distance = Infinity;

		var paths = this.astar.search(allNodes, closestNode, farthestNode);
		allNodes.forEach(function(node) {
		var measuredDistance = BABYLON.Vector3.DistanceSquared(node.centroid, targetPosition);
		if (measuredDistance < distance &&
		this._isVectorInPolygon(targetPosition, node, vertices)) {
		farthestNode = node;
		distance = measuredDistance;
		}
		}.bind(this));

		var getPortalFromTo = function (a, b) {
		for (var i = 0; i < a.neighbours.length; i++) {
		if (a.neighbours[i] === b.id) {
		return a.portals[i];
		}
		}
		};
		// If we can't find any node, just go straight to the target
		if (!closestNode \|\| !farthestNode) {
		return null;
		}

		// We got the corridor
		// Now pull the rope
		var paths = this.astar.search(allNodes, closestNode, farthestNode);

		var channel = new Channel();
		var getPortalFromTo = function(a, b) {
		for (var i = 0; i < a.neighbours.length; i++) {
		if (a.neighbours[i] === b.id) {
		return a.portals[i];
		}
		}
		};

		channel.push(startPosition);
		// We got the corridor
		// Now pull the rope

		for (var i = 0; i < paths.length; i++) {
		var polygon = paths[i];
		var channel = new Channel();

		var nextPolygon = paths[i + 1];
		channel.push(startPosition);

		if (nextPolygon) {
		var portals = getPortalFromTo(polygon, nextPolygon);
		channel.push(
		this.getVectorFrom(vertices, portals[0]),
		this.getVectorFrom(vertices, portals[1])
		);
		}
		for (var i = 0; i < paths.length; i++) {
		var polygon = paths[i];

		}
		var nextPolygon = paths[i + 1];

		channel.push(targetPosition);
		if (nextPolygon) {
		var portals = getPortalFromTo(polygon, nextPolygon);
		channel.push(
		this.getVectorFrom(vertices, portals[0]),
		this.getVectorFrom(vertices, portals[1])
		);
		}

		channel.stringPull();
		}

		channel.push(targetPosition);

		var vectors = [];
		channel.stringPull();

		channel.path.forEach(function (c) {
		var vec = new BABYLON.Vector3(c.x, c.y, c.z);

		// console.log(vec.clone().sub(startPosition).length());
		var vectors = [];

		// Ensure the intermediate steps aren't too close to the start position
		// var dist = vec.clone().sub(startPosition).lengthSq();
		// if (dist > 0.01 * 0.01) {
		vectors.push(vec);
		// }
		channel.path.forEach(function(c) {
		var vec = new BABYLON.Vector3(c.x, c.y, c.z);

		// console.log(vec.clone().sub(startPosition).length());

		});
		// Ensure the intermediate steps aren't too close to the start position
		// var dist = vec.clone().sub(startPosition).lengthSq();
		// if (dist > 0.01 * 0.01) {
		vectors.push(vec);
		// }

		// We don't need the first one, as we already know our start position
		vectors.shift();

		return vectors;
		},
		});

		_isPointInPoly: function (poly, pt) {
		for (var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
		((poly[i].z <= pt.z && pt.z < poly[j].z) \|\| (poly[j].z <= pt.z && pt.z < poly[i].z)) && (pt.x < (poly[j].x - poly[i].x) * (pt.z - poly[i].z) / (poly[j].z - poly[i].z) + poly[i].x) && (c = !c);
		return c;
		},
		// We don't need the first one, as we already know our start position
		vectors.shift();

		_isVectorInPolygon: function (vector, polygon, vertices) {
		return vectors;
		},

		// reference point will be the centroid of the polygon
		// We need to rotate the vector as well as all the points which the polygon uses
		_isPointInPoly: function(poly, pt) {
		for (var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
		((poly[i].z <= pt.z && pt.z < poly[j].z) \|\| (poly[j].z <= pt.z && pt.z < poly[i].z)) && (pt.x < (poly[j].x - poly[i].x) * (pt.z - poly[i].z) / (poly[j].z - poly[i].z) + poly[i].x) && (c = !c);
		return c;
		},

		var center = polygon.centroid;
		_isVectorInPolygon: function(vector, polygon, vertices) {

		var lowestPoint = 100000;
		var highestPoint = -100000;
		// reference point will be the centroid of the polygon
		// We need to rotate the vector as well as all the points which the polygon uses
		var lowestPoint = 100000;
		var highestPoint = -100000;

		var polygonVertices = [];
		var polygonVertices = [];

		_.each(polygon.vertexIds, function (vId) {
		var point = this.getVectorFrom(vertices, vId);
		lowestPoint = Math.min(point.y, lowestPoint);
		highestPoint = Math.max(point.y, highestPoint);
		polygonVertices.push(point);
		}.bind(this));
		_.each(polygon.vertexIds, function(vId) {
		var point = this.getVectorFrom(vertices, vId);
		lowestPoint = Math.min(point.y, lowestPoint);
		highestPoint = Math.max(point.y, highestPoint);
		polygonVertices.push(point);
		}.bind(this));

		if (vector.y < highestPoint + 0.5 && vector.y > lowestPoint - 0.5 &&
		this._isPointInPoly(polygonVertices, vector)) {
		return true;
		}
		return false;
		},
		if (vector.y < highestPoint + 0.5 && vector.y > lowestPoint - 0.5 &&
		this._isPointInPoly(polygonVertices, vector)) {
		return true;
		}
		return false;
		},

		_computeCentroids: function (geometry) {
		var f, fl, face;
		var centroids = [];
		var indices = geometry.getIndices();
		var vertices = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);
		var c = new BABYLON.Vector3(0, 0, 0);
		_computeCentroids: function(geometry) {
		var centroids = [];
		var indices = geometry.getIndices();
		var vertices = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);
		var c = new BABYLON.Vector3(0, 0, 0);

		for ( f = 0, fl = indices.length; f < fl; f += 3 ) {
		var p1 = this.getVectorFrom(vertices, indices[f]);
		var p2 = this.getVectorFrom(vertices, indices[f+1]);
		var p3 = this.getVectorFrom(vertices, indices[f+2]);
		for (var f = 0; f < indices.length; f += 3) {
		var p1 = this.getVectorFrom(vertices, indices[f]);
		var p2 = this.getVectorFrom(vertices, indices[f + 1]);
		var p3 = this.getVectorFrom(vertices, indices[f + 2]);

		c.copyFromFloats( 0, 0, 0 );
		c.copyFromFloats(0, 0, 0);

		c.addInPlace(p1);
		c.addInPlace(p2);
		c.addInPlace(p3);
		c.addInPlace(p1);
		c.addInPlace(p2);
		c.addInPlace(p3);

		c.scaleInPlace( 1/3 );
		c.scaleInPlace(1 / 3);

		centroids.push(c.clone());
		}
		geometry.centroids = centroids;
		},
		centroids.push(c.clone());
		}
		geometry.centroids = centroids;
		},


		_roundNumber: function (number, decimals) {
		var newnumber = new Number(number + '').toFixed(parseInt(decimals));
		return parseFloat(newnumber);
		},
		_roundNumber: function(number, decimals) {
		var newnumber = new Number(number + '').toFixed(parseInt(decimals));
		return parseFloat(newnumber);
		},

		_mergeVertexIds: function (aList, bList) {
		_mergeVertexIds: function(aList, bList) {

		var sharedVertices = [];
		var sharedVertices = [];

		aList.forEach(function (vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});
		aList.forEach(function(vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});

		if (sharedVertices.length < 2) return [];
		if (sharedVertices.length < 2) return [];

		// console.log("TRYING aList:", aList, ", bList:", bList, ", sharedVertices:", sharedVertices);
		// console.log("TRYING aList:", aList, ", bList:", bList, ", sharedVertices:", sharedVertices);

		if (_.includes(sharedVertices, aList[0]) && _.includes(sharedVertices, aList[aList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		aList.push(aList.shift());
		}
		if (_.includes(sharedVertices, aList[0]) && _.includes(sharedVertices, aList[aList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		aList.push(aList.shift());
		}

		if (_.includes(sharedVertices, bList[0]) && _.includes(sharedVertices, bList[bList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		bList.push(bList.shift());
		}
		if (_.includes(sharedVertices, bList[0]) && _.includes(sharedVertices, bList[bList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		bList.push(bList.shift());
		}

		// Again!
		sharedVertices = [];
		// Again!
		sharedVertices = [];

		aList.forEach(function (vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});
		aList.forEach(function(vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});

		var clockwiseMostSharedVertex = sharedVertices[1];
		var counterClockwiseMostSharedVertex = sharedVertices[0];
		var clockwiseMostSharedVertex = sharedVertices[1];
		var counterClockwiseMostSharedVertex = sharedVertices[0];


		var cList = _.clone(aList);
		while (cList[0] !== clockwiseMostSharedVertex) {
		cList.push(cList.shift());
		}
		var cList = _.clone(aList);
		while (cList[0] !== clockwiseMostSharedVertex) {
		cList.push(cList.shift());
		}

		var c = 0;
		var c = 0;

		var temp = _.clone(bList);
		while (temp[0] !== counterClockwiseMostSharedVertex) {
		temp.push(temp.shift());
		var temp = _.clone(bList);
		while (temp[0] !== counterClockwiseMostSharedVertex) {
		temp.push(temp.shift());

		if (c++ > 10) debugger;
		}
		if (c++ > 10) break;
		}

		// Shave
		temp.shift();
		temp.pop();
		// Shave
		temp.shift();
		temp.pop();

		cList = cList.concat(temp);
		cList = cList.concat(temp);

		// console.log("aList:", aList, ", bList:", bList, ", cList:", cList, ", sharedVertices:", sharedVertices);
		// console.log("aList:", aList, ", bList:", bList, ", cList:", cList, ", sharedVertices:", sharedVertices);

		return cList;
		},
		return cList;
		},

		_setPolygonCentroid: function (polygon, navigationMesh) {
		var sum = new BABYLON.Vector3(0, 0, 0);
		_setPolygonCentroid: function(polygon, navigationMesh) {
		var sum = new BABYLON.Vector3(0, 0, 0);

		var vertices = navigationMesh.vertices;
		var vertices = navigationMesh.vertices;

		_.each(polygon.vertexIds, function (vId) {
		sum.x += vertices[vId*3];
		sum.y += vertices[vId*3+1];
		sum.z += vertices[vId*3+2];
		});
		_.each(polygon.vertexIds, function(vId) {
		sum.x += vertices[vId * 3];
		sum.y += vertices[vId * 3 + 1];
		sum.z += vertices[vId * 3 + 2];
		});

		sum.scaleInPlace(1/polygon.vertexIds.length);
		sum.scaleInPlace(1 / polygon.vertexIds.length);

		polygon.centroid.copyFrom(sum);
		},
		polygon.centroid.copyFrom(sum);
		},

		getVectorFrom: function (vertices, id, _vector) {
		if (_vector) {
		_vector.copyFromFloats(vertices[id3], vertices[id3+1], vertices[id*3+2]);
		return _vector;
		}
		return new BABYLON.Vector3(vertices[id3], vertices[id3+1], vertices[id*3+2]);
		},
		getVectorFrom: function(vertices, id, _vector) {
		if (_vector) {
		_vector.copyFromFloats(vertices[id * 3], vertices[id * 3 + 1], vertices[id * 3 + 2]);
		return _vector;
		}
		return new BABYLON.Vector3(vertices[id * 3], vertices[id * 3 + 1], vertices[id * 3 + 2]);
		},

		_cleanPolygon: function (polygon, navigationMesh) {
		_cleanPolygon: function(polygon, navigationMesh) {

		var newVertexIds = [];
		var newVertexIds = [];

		var vertices = navigationMesh.vertices;
		var vertices = navigationMesh.vertices;

		for (var i = 0; i < polygon.vertexIds.length; i++) {
		for (var i = 0; i < polygon.vertexIds.length; i++) {

		var vertex = this.getVectorFrom(vertices, polygon.vertexIds[i]);
		var vertex = this.getVectorFrom(vertices, polygon.vertexIds[i]);

		var nextVertexId, previousVertexId;
		var nextVertex, previousVertex;
		var nextVertexId, previousVertexId;
		var nextVertex, previousVertex;

		// console.log("nextVertex: ", nextVertex);
		// console.log("nextVertex: ", nextVertex);

		if (i === 0) {
		nextVertexId = polygon.vertexIds[1];
		previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 1];
		} else if (i === polygon.vertexIds.length - 1) {
		nextVertexId = polygon.vertexIds[0];
		previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 2];
		} else {
		nextVertexId = polygon.vertexIds[i + 1];
		previousVertexId = polygon.vertexIds[i - 1];
		}
		if (i === 0) {
		nextVertexId = polygon.vertexIds[1];
		previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 1];
		} else if (i === polygon.vertexIds.length - 1) {
		nextVertexId = polygon.vertexIds[0];
		previousVertexId = polygon.vertexIds[polygon.vertexIds.length - 2];
		} else {
		nextVertexId = polygon.vertexIds[i + 1];
		previousVertexId = polygon.vertexIds[i - 1];
		}

		nextVertex = this.getVectorFrom(vertices, nextVertexId);
		previousVertex = this.getVectorFrom(vertices, previousVertexId);
		nextVertex = this.getVectorFrom(vertices, nextVertexId);
		previousVertex = this.getVectorFrom(vertices, previousVertexId);

		var a = nextVertex.clone().sub(vertex);
		var b = previousVertex.clone().sub(vertex);
		var a = nextVertex.clone().sub(vertex);
		var b = previousVertex.clone().sub(vertex);

		var angle = a.angleTo(b);
		var angle = a.angleTo(b);

		// console.log(angle);
		// console.log(angle);

		if (angle > Math.PI - 0.01 && angle < Math.PI + 0.01) {
		// Unneccesary vertex
		// console.log("Unneccesary vertex: ", polygon.vertexIds[i]);
		// console.log("Angle between "+previousVertexId+", "+polygon.vertexIds[i]+" "+nextVertexId+" was: ", angle);
		if (angle > Math.PI - 0.01 && angle < Math.PI + 0.01) {
		// Unneccesary vertex
		// console.log("Unneccesary vertex: ", polygon.vertexIds[i]);
		// console.log("Angle between "+previousVertexId+", "+polygon.vertexIds[i]+" "+nextVertexId+" was: ", angle);


		// Remove the neighbours who had this vertex
		var goodNeighbours = [];
		polygon.neighbours.forEach(function (neighbour) {
		if (!_.includes(neighbour.vertexIds, polygon.vertexIds[i])) {
		goodNeighbours.push(neighbour);
		}
		});
		polygon.neighbours = goodNeighbours;
		// Remove the neighbours who had this vertex
		var goodNeighbours = [];
		polygon.neighbours.forEach(function(neighbour) {
		if (!_.includes(neighbour.vertexIds, polygon.vertexIds[i])) {
		goodNeighbours.push(neighbour);
		}
		});
		polygon.neighbours = goodNeighbours;


		// TODO cleanup the list of vertices and rebuild vertexIds for all polygons
		} else {
		newVertexIds.push(polygon.vertexIds[i]);
		}
		// TODO cleanup the list of vertices and rebuild vertexIds for all polygons
		} else {
		newVertexIds.push(polygon.vertexIds[i]);
		}

		}
		}

		// console.log("New vertexIds: ", newVertexIds);
		// console.log("New vertexIds: ", newVertexIds);

		polygon.vertexIds = newVertexIds;
		polygon.vertexIds = newVertexIds;

		this._setPolygonCentroid(polygon, navigationMesh);
		this._setPolygonCentroid(polygon, navigationMesh);

		},
		},

		_isConvex: function (polygon, navigationMesh) {
		_isConvex: function(polygon, navigationMesh) {

		var vertices = navigationMesh.vertices;
		var vertices = navigationMesh.vertices;

		if (polygon.vertexIds.length < 3) return false;
		if (polygon.vertexIds.length < 3) return false;

		var convex = true;
		var convex = true;

		var total = 0;
		var total = 0;

		var results = [];
		var results = [];

		for (var i = 0; i < polygon.vertexIds.length; i++) {
		for (var i = 0; i < polygon.vertexIds.length; i++) {

		var vertex = this.getVectorFrom(vertices, polygon.vertexIds[i]);
		var vertex = this.getVectorFrom(vertices, polygon.vertexIds[i]);

		var nextVertex, previousVertex;
		var nextVertex, previousVertex;

		// console.log("nextVertex: ", nextVertex);
		// console.log("nextVertex: ", nextVertex);

		if (i === 0) {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[1]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[polygon.vertexIds.length - 1]);
		} else if (i === polygon.vertexIds.length - 1) {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[0]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[polygon.vertexIds.length - 2]);
		} else {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[i + 1]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[i - 1]);
		}
		if (i === 0) {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[1]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[polygon.vertexIds.length - 1]);
		} else if (i === polygon.vertexIds.length - 1) {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[0]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[polygon.vertexIds.length - 2]);
		} else {
		nextVertex = this.getVectorFrom(vertices, polygon.vertexIds[i + 1]);
		previousVertex = this.getVectorFrom(vertices, polygon.vertexIds[i - 1]);
		}

		var a = nextVertex.clone().sub(vertex);
		var b = previousVertex.clone().sub(vertex);
		var a = nextVertex.clone().sub(vertex);
		var b = previousVertex.clone().sub(vertex);

		var angle = a.angleTo(b);
		total += angle;
		var angle = a.angleTo(b);
		total += angle;

		// console.log(angle);
		if (angle === Math.PI \|\| angle === 0) return false;
		// console.log(angle);
		if (angle === Math.PI \|\| angle === 0) return false;

		var r = BABYLON.Vector3.Cross(a, b).y;
		results.push(r);
		// console.log("pushed: ", r);
		}
		var r = BABYLON.Vector3.Cross(a, b).y;
		results.push(r);
		// console.log("pushed: ", r);
		}

		// if ( total > (polygon.vertexIds.length-2)*Math.PI ) return false;
		// if ( total > (polygon.vertexIds.length-2)*Math.PI ) return false;

		results.forEach(function (r) {
		if (r === 0) convex = false;
		});
		results.forEach(function(r) {
		if (r === 0) convex = false;
		});

		if (results[0] > 0) {
		results.forEach(function (r) {
		if (r < 0) convex = false;
		});
		} else {
		results.forEach(function (r) {
		if (r > 0) convex = false;
		});
		}
		if (results[0] > 0) {
		results.forEach(function(r) {
		if (r < 0) convex = false;
		});
		} else {
		results.forEach(function(r) {
		if (r > 0) convex = false;
		});
		}

		// console.log("allowed: "+total+", max: "+(polygon.vertexIds.length-2)*Math.PI);
		// if ( total > (polygon.vertexIds.length-2)*Math.PI ) convex = false;
		// console.log("allowed: "+total+", max: "+(polygon.vertexIds.length-2)*Math.PI);
		// if ( total > (polygon.vertexIds.length-2)*Math.PI ) convex = false;

		// console.log("Convex: "+(convex ? "true": "false"));
		// console.log("Convex: "+(convex ? "true": "false"));



		return convex;
		},
		return convex;
		},

		_buildPolygonGroups: function (navigationMesh) {
		_buildPolygonGroups: function(navigationMesh) {

		var polygons = navigationMesh.polygons;
		var vertices = navigationMesh.vertices;
		var polygons = navigationMesh.polygons;

		var polygonGroups = [];
		var groupCount = 0;
		var polygonGroups = [];
		var groupCount = 0;

		var spreadGroupId = function (polygon) {
		_.each(polygon.neighbours, function (neighbour) {
		if (_.isUndefined(neighbour.group)) {
		neighbour.group = polygon.group;
		spreadGroupId(neighbour);
		}
		});
		};
		var spreadGroupId = function(polygon) {
		_.each(polygon.neighbours, function(neighbour) {
		if (_.isUndefined(neighbour.group)) {
		neighbour.group = polygon.group;
		spreadGroupId(neighbour);
		}
		});
		};

		_.each(polygons, function (polygon, i) {
		_.each(polygons, function(polygon) {

		if (_.isUndefined(polygon.group)) {
		polygon.group = groupCount++;
		// Spread it
		spreadGroupId(polygon);
		}
		if (_.isUndefined(polygon.group)) {
		polygon.group = groupCount++;
		// Spread it
		spreadGroupId(polygon);
		}

		if (!polygonGroups[polygon.group]) polygonGroups[polygon.group] = [];
		if (!polygonGroups[polygon.group]) polygonGroups[polygon.group] = [];

		polygonGroups[polygon.group].push(polygon);
		});
		polygonGroups[polygon.group].push(polygon);
		});

		console.log("Groups built: ", polygonGroups.length);
		console.log("Groups built: ", polygonGroups.length);

		return polygonGroups;
		},
		return polygonGroups;
		},

		_array_intersect: function() {
		var i, all, shortest, nShortest, n, len, ret = [],
		obj = {},
		nOthers;
		nOthers = arguments.length - 1;
		nShortest = arguments[0].length;
		shortest = 0;
		for (i = 0; i <= nOthers; i++) {
		n = arguments[i].length;
		if (n < nShortest) {
		shortest = i;
		nShortest = n;
		}
		}
		_array_intersect: function() {
		var i, shortest, nShortest, n, len, ret = [],
		obj = {},
		nOthers;
		nOthers = arguments.length - 1;
		nShortest = arguments[0].length;
		shortest = 0;
		for (i = 0; i <= nOthers; i++) {
		n = arguments[i].length;
		if (n < nShortest) {
		shortest = i;
		nShortest = n;
		}
		}

		for (i = 0; i <= nOthers; i++) {
		n = (i === shortest) ? 0 : (i \|\| shortest); //Read the shortest array first. Read the first array instead of the shortest
		len = arguments[n].length;
		for (var j = 0; j < len; j++) {
		var elem = arguments[n][j];
		if (obj[elem] === i - 1) {
		if (i === nOthers) {
		ret.push(elem);
		obj[elem] = 0;
		} else {
		obj[elem] = i;
		}
		} else if (i === 0) {
		obj[elem] = 0;
		}
		}
		}
		return ret;
		},
		for (i = 0; i <= nOthers; i++) {
		n = (i === shortest) ? 0 : (i \|\| shortest); //Read the shortest array first. Read the first array instead of the shortest
		len = arguments[n].length;
		for (var j = 0; j < len; j++) {
		var elem = arguments[n][j];
		if (obj[elem] === i - 1) {
		if (i === nOthers) {
		ret.push(elem);
		obj[elem] = 0;
		} else {
		obj[elem] = i;
		}
		} else if (i === 0) {
		obj[elem] = 0;
		}
		}
		}
		return ret;
		},

		_buildPolygonNeighbours: function (polygon, navigationMesh) {
		polygon.neighbours = [];
		_buildPolygonNeighbours: function(polygon, navigationMesh) {
		polygon.neighbours = [];

		// All other nodes that contain at least two of our vertices are our neighbours
		for (var i = 0, len = navigationMesh.polygons.length; i < len; i++) {
		if (polygon === navigationMesh.polygons[i]) continue;
		// All other nodes that contain at least two of our vertices are our neighbours
		for (var i = 0, len = navigationMesh.polygons.length; i < len; i++) {
		if (polygon === navigationMesh.polygons[i]) continue;

		// Don't check polygons that are too far, since the intersection tests take a long time
		if (BABYLON.Vector3.DistanceSquared(polygon.centroid, navigationMesh.polygons[i].centroid) > 100 * 100) continue;
		// Don't check polygons that are too far, since the intersection tests take a long time
		if (BABYLON.Vector3.DistanceSquared(polygon.centroid, navigationMesh.polygons[i].centroid) > 100 * 100) continue;

		var matches = this._array_intersect(polygon.vertexIds, navigationMesh.polygons[i].vertexIds);
		// var matches = _.intersection(polygon.vertexIds, navigationMesh.polygons[i].vertexIds);
		var matches = this._array_intersect(polygon.vertexIds, navigationMesh.polygons[i].vertexIds);
		// var matches = _.intersection(polygon.vertexIds, navigationMesh.polygons[i].vertexIds);

		if (matches.length >= 2) {
		polygon.neighbours.push(navigationMesh.polygons[i]);
		}
		}
		},
		if (matches.length >= 2) {
		polygon.neighbours.push(navigationMesh.polygons[i]);
		}
		}
		},

		_buildPolygonsFromGeometry: function (geometry) {
		_buildPolygonsFromGeometry: function(geometry) {

		var polygons = [];
		var vertices = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);
		var indices = geometry.getIndices();
		var polygonId = 1;
		var polygons = [];
		var vertices = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);
		var indices = geometry.getIndices();
		var polygonId = 1;

		console.log("Vertices:", vertices.length/3, "polygons:", indices.length/3);
		console.log("Vertices:", vertices.length / 3, "polygons:", indices.length / 3);

		// Convert the faces into a custom format that supports more than 3 vertices
		for (var i = 0; i < indices.length; i+=3) {
		// Convert the faces into a custom format that supports more than 3 vertices
		for (var i = 0; i < indices.length; i += 3) {

		var a = this.getVectorFrom(vertices, indices[i]);
		var b = this.getVectorFrom(vertices, indices[i+1]);
		var c = this.getVectorFrom(vertices, indices[i+2]);
		var normal = BABYLON.Vector3.Cross(b.subtract(a), b.subtract(c)).normalize();
		var a = this.getVectorFrom(vertices, indices[i]);
		var b = this.getVectorFrom(vertices, indices[i + 1]);
		var c = this.getVectorFrom(vertices, indices[i + 2]);
		var normal = BABYLON.Vector3.Cross(b.subtract(a), b.subtract(c)).normalize();

		polygons.push({
		id: polygonId++,
		vertexIds: [indices[i], indices[i+1], indices[i+2]],
		centroid: geometry.centroids[i/3],
		normal: normal,
		neighbours: []
		});
		}
		polygons.push({
		id: polygonId++,
		vertexIds: [indices[i], indices[i + 1], indices[i + 2]],
		centroid: geometry.centroids[i / 3],
		normal: normal,
		neighbours: []
		});
		}

		var navigationMesh = {
		polygons: polygons,
		vertices: vertices
		};
		var navigationMesh = {
		polygons: polygons,
		vertices: vertices
		};

		// Build a list of adjacent polygons
		_.each(polygons, function (polygon) {
		this._buildPolygonNeighbours(polygon, navigationMesh);
		}.bind(this));
		// Build a list of adjacent polygons
		_.each(polygons, function(polygon) {
		this._buildPolygonNeighbours(polygon, navigationMesh);
		}.bind(this));

		return navigationMesh;
		},
		return navigationMesh;
		},

		_cleanNavigationMesh: function (navigationMesh) {
		_cleanNavigationMesh: function(navigationMesh) {

		var polygons = navigationMesh.polygons;
		var vertices = navigationMesh.vertices;
		var polygons = navigationMesh.polygons;
		var vertices = navigationMesh.vertices;


		// Remove steep triangles
		var up = new BABYLON.Vector3(0, 1, 0);
		polygons = _.filter(polygons, function (polygon) {
		var angle = Math.acos(up.dot(polygon.normal));
		return angle < (Math.PI / 4);
		});
		// Remove steep triangles
		var up = new BABYLON.Vector3(0, 1, 0);
		polygons = _.filter(polygons, function(polygon) {
		var angle = Math.acos(BABYLON.Vector3.Dot(up, polygon.normal));
		return angle < (Math.PI / 4);
		});


		// Remove unnecessary edges using the Hertel-Mehlhorn algorithm
		// Remove unnecessary edges using the Hertel-Mehlhorn algorithm

		// 1. Find a pair of adjacent nodes (i.e., two nodes that share an edge between them)
		// whose normals are nearly identical (i.e., their surfaces face the same direction).
		// 1. Find a pair of adjacent nodes (i.e., two nodes that share an edge between them)
		// whose normals are nearly identical (i.e., their surfaces face the same direction).


		var newPolygons = [];
		var newPolygons = [];

		_.each(polygons, function (polygon) {
		_.each(polygons, function(polygon) {

		if (polygon.toBeDeleted) return;
		if (polygon.toBeDeleted) return;

		var keepLooking = true;
		var keepLooking = true;

		while (keepLooking) {
		keepLooking = false;
		while (keepLooking) {
		keepLooking = false;

		_.each(polygon.neighbours, function (otherPolygon) {
		_.each(polygon.neighbours, function(otherPolygon) {

		if (polygon === otherPolygon) return;
		if (polygon === otherPolygon) return;

		if (Math.acos(polygon.normal.dot(otherPolygon.normal)) < 0.01) {
		// That's pretty equal alright!
		if (Math.acos(BABYLON.Vector3.Dot(polygon.normal, otherPolygon.normal)) < 0.01) {
		// That's pretty equal alright!

		// Merge otherPolygon with polygon
		// Merge otherPolygon with polygon

		var testVertexIdList = [];
		var testPolygon = {
		vertexIds: this._mergeVertexIds(polygon.vertexIds, otherPolygon.vertexIds),
		neighbours: polygon.neighbours,
		normal: polygon.normal.clone(),
		centroid: polygon.centroid.clone()
		};

		var testPolygon = {
		vertexIds: mergeVertexIds(polygon.vertexIds, otherPolygon.vertexIds),
		neighbours: polygon.neighbours,
		normal: polygon.normal.clone(),
		centroid: polygon.centroid.clone()
		};
		this._cleanPolygon(testPolygon, navigationMesh);

		this._cleanPolygon(testPolygon, navigationMesh);
		if (this._isConvex(testPolygon, navigationMesh)) {
		otherPolygon.toBeDeleted = true;

		if (isConvex(testPolygon, navigationMesh)) {
		otherPolygon.toBeDeleted = true;

		// Inherit the neighbours from the to be merged polygon, except ourself
		_.each(otherPolygon.neighbours, function(otherPolygonNeighbour) {

		// Inherit the neighbours from the to be merged polygon, except ourself
		_.each(otherPolygon.neighbours, function (otherPolygonNeighbour) {
		// Set this poly to be merged to be no longer our neighbour
		otherPolygonNeighbour.neighbours = _.without(otherPolygonNeighbour.neighbours, otherPolygon);

		// Set this poly to be merged to be no longer our neighbour
		otherPolygonNeighbour.neighbours = _.without(otherPolygonNeighbour.neighbours, otherPolygon);
		if (otherPolygonNeighbour !== polygon) {
		// Tell the old Polygon's neighbours about the new neighbour who has merged
		otherPolygonNeighbour.neighbours.push(polygon);
		} else {
		// For ourself, we don't need to know about ourselves
		// But we inherit the old neighbours
		polygon.neighbours = polygon.neighbours.concat(otherPolygon.neighbours);
		polygon.neighbours = _.uniq(polygon.neighbours);

		if (otherPolygonNeighbour !== polygon) {
		// Tell the old Polygon's neighbours about the new neighbour who has merged
		otherPolygonNeighbour.neighbours.push(polygon);
		} else {
		// For ourself, we don't need to know about ourselves
		// But we inherit the old neighbours
		polygon.neighbours = polygon.neighbours.concat(otherPolygon.neighbours);
		polygon.neighbours = _.uniq(polygon.neighbours);
		// Without ourselves in it!
		polygon.neighbours = _.without(polygon.neighbours, polygon);
		}
		});

		// Without ourselves in it!
		polygon.neighbours = _.without(polygon.neighbours, polygon);
		}
		});
		polygon.vertexIds = this._mergeVertexIds(polygon.vertexIds, otherPolygon.vertexIds);

		polygon.vertexIds = mergeVertexIds(polygon.vertexIds, otherPolygon.vertexIds);
		this._cleanPolygon(polygon, navigationMesh);

		// console.log(polygon.vertexIds);
		// console.log("Merge!");
		keepLooking = true;
		}

		cleanPolygon(polygon, navigationMesh);
		}
		}.bind(this));
		}

		keepLooking = true;
		}

		}
		}.bind(this));
		}
		if (!polygon.toBeDeleted) {
		newPolygons.push(polygon);
		}

		});

		if (!polygon.toBeDeleted) {
		newPolygons.push(polygon);
		}
		var isUsed = function(vId) {
		var contains = false;
		_.each(newPolygons, function(p) {
		if (!contains && _.includes(p.vertexIds, vId)) {
		contains = true;
		}
		});
		return contains;
		};

		});
		// Clean vertices
		for (var i = 0; i < vertices.length; i++) {
		if (!isUsed(i)) {

		var isUsed = function (vId) {
		var contains = false;
		_.each(newPolygons, function (p) {
		if (!contains && _.includes(p.vertexIds, vId)) {
		contains = true;
		}
		});
		return contains;
		};
		// Decrement all vertices that are higher than i
		_.each(newPolygons, function(p) {
		for (var j = 0; j < p.vertexIds.length; j++) {
		if (p.vertexIds[j] > i) {
		p.vertexIds[j]--;
		}
		}
		});

		// Clean vertices
		var keepChecking = false;
		for (var i = 0; i < vertices.length; i++) {
		if (!isUsed(i)) {
		vertices.splice(i, 1);
		i--;
		}

		// Decrement all vertices that are higher than i
		_.each(newPolygons, function (p) {
		for (var j = 0; j < p.vertexIds.length; j++) {
		if (p.vertexIds[j] > i) {
		p.vertexIds[j] --;
		}
		}
		});
		}

		vertices.splice(i, 1);
		i--;
		}
		navigationMesh.polygons = newPolygons;
		navigationMesh.vertices = vertices;

		};
		},

		_buildNavigationMesh: function(geometry) {
		// Prepare geometry
		this._computeCentroids(geometry);

		navigationMesh.polygons = newPolygons;
		navigationMesh.vertices = vertices;
		this._mergeVertices(geometry);
		// BABYLON.GeometryUtils.triangulateQuads(geometry);

		},
		// console.log("vertices:", geometry.vertices.length, "polygons:", geometry.faces.length);

		_buildNavigationMesh: function (geometry) {
		// Prepare geometry
		this._computeCentroids(geometry);
		var navigationMesh = this._buildPolygonsFromGeometry(geometry);

		this._mergeVertices(geometry);
		// BABYLON.GeometryUtils.triangulateQuads(geometry);
		// cleanNavigationMesh(navigationMesh);
		// console.log("Pre-clean:", navigationMesh.polygons.length, "polygons,", navigationMesh.vertices.length, "vertices.");

		// console.log("vertices:", geometry.vertices.length, "polygons:", geometry.faces.length);
		// console.log("")
		// console.log("Vertices:", navigationMesh.vertices.length, "polygons,", navigationMesh.polygons.length, "vertices.");

		var navigationMesh = this._buildPolygonsFromGeometry(geometry);
		return navigationMesh;
		},

		// cleanNavigationMesh(navigationMesh);
		// console.log("Pre-clean:", navigationMesh.polygons.length, "polygons,", navigationMesh.vertices.length, "vertices.");
		_mergeVertices: function(geometry) {
		var verticesMap = {}; // Hashmap for looking up vertices by position coordinates (and making sure they are unique)
		var unique = [],
		changes = [];

		// console.log("")
		// console.log("Vertices:", navigationMesh.vertices.length, "polygons,", navigationMesh.polygons.length, "vertices.");
		var v, key;
		var precisionPoints = 4; // number of decimal points, e.g. 4 for epsilon of 0.0001
		var precision = Math.pow(10, precisionPoints);
		var indices;
		var ind = geometry.getIndices(),
		vert = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);

		return navigationMesh;
		},
		for (var i = 0; i < vert.length; i += 3) {

		_mergeVertices: function (geometry) {
		var verticesMap = {}; // Hashmap for looking up vertices by position coordinates (and making sure they are unique)
		var unique = [], changes = [];
		v = new BABYLON.Vector3(vert[i], vert[i + 1], vert[i + 2]);
		key = Math.round(v.x * precision) + '_' + Math.round(v.y * precision) + '_' + Math.round(v.z * precision);

		var v, key;
		var precisionPoints = 4; // number of decimal points, e.g. 4 for epsilon of 0.0001
		var precision = Math.pow( 10, precisionPoints );
		var i, il, face;
		var indices, j, jl;
		var ind = geometry.getIndices(),
		vert = geometry.getVerticesData(BABYLON.VertexBuffer.PositionKind);
		if (verticesMap[key] === undefined) {

		for ( i = 0, il = vert.length; i < il; i += 3 ) {
		verticesMap[key] = i / 3;
		unique.push(v.clone());
		changes[i / 3] = unique.length - 1;

		v = new BABYLON.Vector3(vert[ i ], vert[ i +1], vert[ i +2]);
		key = Math.round( v.x * precision ) + '_' + Math.round( v.y * precision ) + '_' + Math.round( v.z * precision );
		} else {

		if ( verticesMap[ key ] === undefined ) {
		//console.log('Duplicate vertex found. ', i, ' could be using ', verticesMap[key]);
		changes[i / 3] = changes[verticesMap[key]];

		verticesMap[ key ] = i/3;
		unique.push( v.clone() );
		changes[ i/3 ] = unique.length - 1;
		}

		} else {
		}

		//console.log('Duplicate vertex found. ', i, ' could be using ', verticesMap[key]);
		changes[ i/3 ] = changes[ verticesMap[ key ] ];

		}
		// if faces are completely degenerate after merging vertices, we
		// have to remove them from the geometry.
		var faceIndicesToRemove = [];

		}
		for (i = 0; i < ind.length; i += 3) {

		ind[i] = changes[ind[i]];
		ind[i + 1] = changes[ind[i + 1]];
		ind[i + 2] = changes[ind[i + 2]];

		// if faces are completely degenerate after merging vertices, we
		// have to remove them from the geometry.
		var faceIndicesToRemove = [];
		indices = [ind[i], ind[i + 1], ind[i + 2]];

		for ( i = 0, il = ind.length; i < il; i += 3 ) {
		var dupIndex = -1;

		ind[i] = changes[ ind[i] ];
		ind[i+1] = changes[ ind[i+1] ];
		ind[i+2] = changes[ ind[i+2] ];
		// if any duplicate vertices are found in a Face3
		// we have to remove the face as nothing can be saved
		for (var n = 0; n < 3; n++) {

		indices = [ ind[i], ind[i+1], ind[i+2] ];
		if (indices[n] === indices[(n + 1) % 3]) {

		var dupIndex = - 1;
		dupIndex = n;
		faceIndicesToRemove.push(i);
		break;

		// if any duplicate vertices are found in a Face3
		// we have to remove the face as nothing can be saved
		for ( var n = 0; n < 3; n ++ ) {
		}

		if ( indices[ n ] === indices[ ( n + 1 ) % 3 ] ) {
		}

		dupIndex = n;
		faceIndicesToRemove.push( i );
		break;
		}

		}
		for (i = faceIndicesToRemove.length - 1; i >= 0; i--) {

		}
		var idx = faceIndicesToRemove[i];

		}
		ind.splice(idx, 3);

		for ( i = faceIndicesToRemove.length - 1; i >= 0; i -- ) {
		}

		var idx = faceIndicesToRemove[ i ];
		// Use unique set of vertices

		ind.splice( idx, 3 );
		var diff = vert.length / 3 - unique.length;
		vert = [];
		for (i = 0; i < unique.length; i++) {
		vert.push(unique[i].x, unique[i].y, unique[i].z);
		}

		}
		geometry.setIndices(ind);
		geometry.setVerticesData(BABYLON.VertexBuffer.PositionKind, vert);

		// Use unique set of vertices
		return diff;
		},

		var diff = vert.length/3 - unique.length;
		vert = [];
		for (var i = 0; i < unique.length; i++) {
		vert.push(unique[i].x, unique[i].y, unique[i].z);
		}

		geometry.setIndices(ind);
		geometry.setVerticesData(BABYLON.VertexBuffer.PositionKind, vert);
		_getSharedVerticesInOrder: function(a, b) {

		return diff;
		},
		var aList = a.vertexIds;
		var bList = b.vertexIds;

		var sharedVertices = [];

		_getSharedVerticesInOrder: function (a, b) {
		_.each(aList, function(vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});

		var aList = a.vertexIds;
		var bList = b.vertexIds;
		if (sharedVertices.length < 2) return [];

		var sharedVertices = [];
		// console.log("TRYING aList:", aList, ", bList:", bList, ", sharedVertices:", sharedVertices);

		_.each(aList, function (vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});
		if (_.includes(sharedVertices, aList[0]) && _.includes(sharedVertices, aList[aList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		aList.push(aList.shift());
		}

		if (sharedVertices.length < 2) return [];
		if (_.includes(sharedVertices, bList[0]) && _.includes(sharedVertices, bList[bList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		bList.push(bList.shift());
		}

		// console.log("TRYING aList:", aList, ", bList:", bList, ", sharedVertices:", sharedVertices);
		// Again!
		sharedVertices = [];

		if (_.includes(sharedVertices, aList[0]) && _.includes(sharedVertices, aList[aList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		aList.push(aList.shift());
		}
		_.each(aList, function(vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});

		if (_.includes(sharedVertices, bList[0]) && _.includes(sharedVertices, bList[bList.length - 1])) {
		// Vertices on both edges are bad, so shift them once to the left
		bList.push(bList.shift());
		}
		return sharedVertices;
		},

		// Again!
		sharedVertices = [];
		_groupNavMesh: function(navigationMesh) {

		_.each(aList, function (vId) {
		if (_.includes(bList, vId)) {
		sharedVertices.push(vId);
		}
		});
		var saveObj = {};

		return sharedVertices;
		},
		_.each(navigationMesh.vertices, function(v) {
		v = this._roundNumber(v, 2);
		}.bind(this));

		_groupNavMesh: function (navigationMesh) {
		saveObj.vertices = navigationMesh.vertices;

		var saveObj = {};
		var groups = this._buildPolygonGroups(navigationMesh);

		_.each(navigationMesh.vertices, function (v) {
		v = this._roundNumber(v, 2);
		}.bind(this));
		saveObj.groups = [];

		saveObj.vertices = navigationMesh.vertices;
		var findPolygonIndex = function(group, p) {
		for (var i = 0; i < group.length; i++) {
		if (p === group[i]) return i;
		}
		};

		var groups = this._buildPolygonGroups(navigationMesh);
		_.each(groups, function(group) {

		saveObj.groups = [];
		var newGroup = [];

		var findPolygonIndex = function (group, p) {
		for (var i = 0; i < group.length; i++) {
		if (p === group[i]) return i;
		}
		};
		_.each(group, function(p) {

		_.each(groups, function (group) {
		var neighbours = [];

		var newGroup = [];
		_.each(p.neighbours, function(n) {
		neighbours.push(findPolygonIndex(group, n));
		});

		_.each(group, function (p) {

		var neighbours = [];
		// Build a portal list to each neighbour
		var portals = [];
		_.each(p.neighbours, function(n) {
		portals.push(this._getSharedVerticesInOrder(p, n));
		}.bind(this));

		_.each(p.neighbours, function (n) {
		neighbours.push(findPolygonIndex(group, n));
		});

		p.centroid.x = this._roundNumber(p.centroid.x, 2);
		p.centroid.y = this._roundNumber(p.centroid.y, 2);
		p.centroid.z = this._roundNumber(p.centroid.z, 2);

		// Build a portal list to each neighbour
		var portals = [];
		_.each(p.neighbours, function (n) {
		portals.push(this._getSharedVerticesInOrder(p, n));
		}.bind(this));
		newGroup.push({
		id: findPolygonIndex(group, p),
		neighbours: neighbours,
		vertexIds: p.vertexIds,
		centroid: p.centroid,
		portals: portals
		});

		}.bind(this));

		p.centroid.x = this._roundNumber(p.centroid.x, 2);
		p.centroid.y = this._roundNumber(p.centroid.y, 2);
		p.centroid.z = this._roundNumber(p.centroid.z, 2);
		saveObj.groups.push(newGroup);
		}.bind(this));

		newGroup.push({
		id: findPolygonIndex(group, p),
		neighbours: neighbours,
		vertexIds: p.vertexIds,
		centroid: p.centroid,
		portals: portals
		});

		}.bind(this));

		saveObj.groups.push(newGroup);
		}.bind(this));

		return saveObj;
		},
		return saveObj;
		},
		});

		module.exports = Navigation;
		module.exports = Navigation;

babylon-navigation-mesh - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics