Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

babylon-navigation-mesh

Package Overview
Dependencies
Maintainers
2
Versions
16
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

babylon-navigation-mesh - npm Package Compare versions

Comparing version 1.1.3 to 1.1.4

.jshintrc

2

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": {

4

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[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]);
},
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;
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc