Instantly share code, notes, and snippets.

@Mathias-Fuchs Mathias-Fuchs/tutte.js
Last active Feb 11, 2019

Embed
What would you like to do?
Deforming a random Delaunay triangulation into its Tutte embedding
var scene = new THREE.Scene();
var camera = new THREE.PerspectiveCamera(45, window.innerWidth / window.innerHeight, 0.1, 1000);
camera.position.z = 300;
var renderer = new THREE.WebGLRenderer();
renderer.setSize(window.innerWidth, window.innerHeight);
renderer.setClearColor( 0xffffff, 1 );
document.body.appendChild(renderer.domElement);
var material = new THREE.MeshBasicMaterial({
color: "white",
wireframe: true
});
var size = { x: 200, z: 200 };
var pointsCount = 30;
var points3d = [];
var vertices = new Float32Array(3 * pointsCount);
for (let i = 0; i < pointsCount; i++) {
let x = THREE.Math.randFloatSpread(size.x);
let y = THREE.Math.randFloatSpread(size.z);
points3d.push(new THREE.Vector3(x, y, 0));
vertices[3 * i] = x;
vertices[3 * i + 1] = y;
vertices[3 * i + 2] = 0;
}
var indexDelaunay = Delaunator.from(
points3d.map(v => {
return [v.x, v.y];
})
);
var indices = new Uint16Array(3 * indexDelaunay.triangles.length);
for (let i = 0; i < indexDelaunay.triangles.length; i++) indices[i] = indexDelaunay.triangles[i];
var v = pointsCount;
var _L = math.zeros(2 * v, 2 * v, "sparse");
var edges = {};
for (var i = 0; i < indexDelaunay.triangles.length / 3; i++) {
var a = indices[3 * i];
var b = indices[3 * i + 1];
if (a > b) {a += b; b = a - b; a -= b;}
if (isNaN(edges[[a, b]])) edges[[a, b]]= 0;
edges[[a, b]] += 1;
a = indices[3 * i + 1];
b = indices[3 * i + 2];
if (a > b) {a += b; b = a - b; a -= b;}
if (isNaN(edges[[a, b]])) edges[[a, b]]= 0;
edges[[a, b]] += 1;
a = indices[3 * i + 2];
b = indices[3 * i];
if (a > b) {a += b; b = a - b; a -= b;}
if (isNaN(edges[[a, b]])) edges[[a, b]]= 0;
edges[[a, b]] += 1;
}
var interior = new Array(v);
interior.fill(true);
for (var ed in edges) {
var str = ed.toString().split(",");
var a = parseInt(str[0]);
var b = parseInt(str[1]);
if (edges[ed] == 1) {interior[a] = false; interior[b] = false;}
}
for (var j = 0; j < 2 * v; j++) _L.set([j, j], 0);
for (var j = 0; j < indexDelaunay.triangles.length / 3; j++)
{
var a = indexDelaunay.triangles[3 * j];
var b = indexDelaunay.triangles[3 * j + 1];
var c = indexDelaunay.triangles[3 * j + 2];
if (interior[a])
{
_L.set([2 * a, 2 * b], -1);
_L.set([2 * a, 2 * c], -1);
_L.set([2 * a, 2 * a], _L.get([2 * a, 2 * a]) + 1);
_L.set([2 * a + 1, 2 * b + 1], -1);
_L.set([2 * a + 1, 2 * c + 1], -1);
_L.set([2 * a + 1, 2 * a + 1], _L.get([2 * a + 1, 2 * a + 1]) + 1);
}
else
{
_L.set([2 * a, 2 * a], 1);
_L.set([2 * a + 1, 2 * a + 1], 1);
}
if (interior[b])
{
_L.set([2 * b, 2 * a], -1);
_L.set([2 * b, 2 * c], -1);
_L.set([2 * b, 2 * b], _L.get([2 * b, 2 * b]) + 1);
_L.set([2 * b + 1, 2 * a + 1], -1);
_L.set([2 * b + 1, 2 * c + 1], -1);
_L.set([2 * b + 1, 2 * b + 1], _L.get([2 * b + 1, 2 * b + 1]) + 1);
}
else
{
_L.set([2 * b, 2 * b], 1);
_L.set([2 * b + 1, 2 * b + 1], 1);
}
if (interior[c])
{
_L.set([2 * c, 2 * a], -1);
_L.set([2 * c, 2 * b], -1);
_L.set([2 * c, 2 * c], _L.get([2 * c, 2 * c]) + 1);
_L.set([2 * c + 1, 2 * a + 1], -1);
_L.set([2 * c + 1, 2 * b + 1], -1);
_L.set([2 * c + 1, 2 * c + 1], _L.get([2 * c + 1, 2 * c + 1]) + 1);
}
else
{
_L.set([2 * c, 2 * c], 1);
_L.set([2 * c + 1, 2 * c + 1], 1);
}
}
_a = new Array(2 * v);
_a.fill(0);
for (var i = 0; i < v; i++)
{
if (!interior[i])
{
_a[2 * i] = vertices[3 * i];
_a[2 * i + 1] = vertices[3 * i + 1];
}
}
_x = math.lusolve(_L, _a);
var t = 0;
var render = function() {
while(scene.children.length > 0){
scene.remove(scene.children[0]);
}
t += .11;
var p = (Math.sin(t) + 1) /2;
var verticesDef = new Float32Array(3 * pointsCount);
for (var j = 0; j < v; j++) {
verticesDef[3 * j] = p * vertices[3 * j] + (1 - p ) * _x.get([2 * j, 0]);
verticesDef[3 * j + 1] = p * vertices[3 * j + 1] + (1 - p) * _x.get([2 * j + 1, 0]);
}
var geomDef = new THREE.BufferGeometry();
geomDef.addAttribute('position', new THREE.BufferAttribute( verticesDef, 3 ) );
geomDef.addAttribute( 'index', new THREE.BufferAttribute(indices, 3 ) );
var cloudDef = new THREE.Points(
geomDef,
new THREE.PointsMaterial({ color: "red", size: 10 })
);
scene.add(cloudDef);
var plDef = new THREE.Mesh(
geomDef,
new THREE.MeshLambertMaterial({color: "red", wireframe: true})
);
scene.add(plDef);
requestAnimationFrame(render);
renderer.render(scene, camera);
};
render();
@Mathias-Fuchs

This comment has been minimized.

Copy link
Owner Author

Mathias-Fuchs commented Feb 11, 2019

requires math.js, three.js, and delaunator.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment