Loop Scheme Subdivision Modifier for Three.js (Draft 1)

LoopSubdivisionModifier.js

/*
 *	@author zz85 / http://twitter.com/blurspline / http://www.lab4games.net/zz85/blog 
 *
 *	Subdivision Geometry Modifier 
 *		using Loop Subdivision Scheme
 *
 *	References:
 *	http://graphics.stanford.edu/~mdfisher/subdivision.html
 *	http://www.holmes3d.net/graphics/subdivision/
 *	http://www.cs.rutgers.edu/~decarlo/readings/subdiv-sg00c.pdf
 *
 */


THREE.SubdivisionModifier = function ( subdivisions ) {

	this.subdivisions = (subdivisions === undefined ) ? 1 : subdivisions;

};

// Applies the "modify" pattern
THREE.SubdivisionModifier.prototype.modify = function ( geometry ) {

	var repeats = this.subdivisions;

	while ( repeats-- > 0 ) {
		this.smooth( geometry );
	}

	delete geometry.__tmpVertices;
	geometry.computeCentroids();
	geometry.computeFaceNormals();
	geometry.computeVertexNormals();

};

var tmp = new THREE.Vector3();


function getEdge( a, b, map ) {

	var vertexIndexA = Math.min( a, b );
	var vertexIndexB = Math.max( a, b );

	var key = vertexIndexA + "_" + vertexIndexB;

	return map[ key ];
}


function processEdge( a, b, vertices, map, face, metaVertices ) {

	var vertexIndexA = Math.min( a, b );
	var vertexIndexB = Math.max( a, b );

	var key = vertexIndexA + "_" + vertexIndexB;

	var edge;

	if ( key in map ) {
		edge = map[ key ];
	} else {
		var vertexA = vertices[ vertexIndexA ];
		var vertexB = vertices[ vertexIndexB ];

		edge = {

			a: vertexA, // pointer reference
			b: vertexB,
			newEdge: null,
			// aIndex: a, // numbered reference
			// bIndex: b,
			faces: [] // pointers to face

		};
	}

	edge.faces.push( face );

	map[ key ] = edge;

	metaVertices[ a ].edges.push( edge );
	metaVertices[ b ].edges.push( edge );
	

}

function generateLookups(vertices, faces, metaVertices, edges) {
	var i, il, face, vertex, edge;



	for (i=0, il=vertices.length; i < il; i++) {
		vertex = { ref: vertices[i], edges: [] }; // , faces: []
		metaVertices[ i ] = vertex;
	}
	
	for (i=0, il=faces.length; i < il; i++) {
		face = faces[i];

		processEdge( face.a, face.b, vertices, edges, face, metaVertices );
		processEdge( face.b, face.c, vertices, edges, face, metaVertices );
		processEdge( face.c, face.a, vertices, edges, face, metaVertices );

	}
}


/////////////////////////////

// Performs an iteration of Catmull-Clark Subdivision
THREE.SubdivisionModifier.prototype.smooth = function ( oldGeometry ) {


	console.log( oldGeometry );
	// New set of vertices, faces and uvs
	// var newVertices = [], newFaces = [], newUVs = [];

	// var oldVertices, oldFaces;
	// var n, l, i, il, j, k;
	// var metaVertices, edges;

	// new stuff. sourceEdges, newEdgeVertices, newSourceVertices

	oldVertices = oldGeometry.vertices; // { x, y, z}
	oldFaces = oldGeometry.faces; // { a: oldVertex1, b: oldVertex2, c: oldVertex3 }

	// Generate edges Lookup

	metaVertices = new Array( oldVertices.length );
	edges = {}; // Edge => { oldVertex1, oldVertex2, faces[]  }

	generateLookups(oldVertices, oldFaces, metaVertices, edges);

	// 1. For each edge, create a new edgeVertex
	newEdgeVertices = [];
	sourceEdges = edges;
	var ABC = ['a', 'b', 'c'];

	for (i in sourceEdges) {
		var currentEdge = sourceEdges[i];
		newEdge = new THREE.Vector3();

		// check how many linked faces. 2 should be correct.
		if (currentEdge.faces.length==2) {
			newEdge.addVectors( currentEdge.a, currentEdge.b ).multiplyScalar( 3 / 8 );

			tmp.set( 0, 0, 0 );
			for (j = 0; j < currentEdge.faces.length; j++ ) {
				face = currentEdge.faces[ j ];

				var other;
				for (k = 0; k < 3; k++) {
					other = oldVertices[ face[ ABC[k] ] ];
					if (other !== currentEdge.a && other !== currentEdge.b ) break;
				}
				tmp.add( other );
			}

			tmp.multiplyScalar( 1 / 8 );
			newEdge.add( tmp );
		} else {
			// if 1 or 0, just take 1/2 of edges.
			newEdge.addVectors( currentEdge.a, currentEdge.b ).multiplyScalar( 0.5 );
			// if length > 2, warn I don't know what to do with it.
			console.warn('currentEdge.faces.length != 2', currentEdge.faces.length);
		}

		currentEdge.newEdge = newEdgeVertices.length;
		newEdgeVertices.push(newEdge);
		// console.log(currentEdge, newEdge);
	}

	newSourceVertices = [];

	// var n;

	// 2. Position new SourceVertex
	for (i=0, il=oldVertices.length; i < il; i++) {
		oldVertex = oldVertices[i];

		// find all connecting edges (using lookupTable)
		connectingEdges = metaVertices[ i ].edges
		n = connectingEdges.length
		var beta;

		if (n == 3) {
			beta = 3 / 16;
		} else if (n > 3) {
			beta = 3 / ( 8 * n ); // Warren's modified formula
		}
		
		// Loop's original beta formula
		// beta = 1 / n * ( 5/8 - Math.pow( 3/8 + 1/4 * Math.cos( 2 * Math. PI / n ), 2) );
		
		if (n <= 2) {
			// crease and boundary rules
			console.warn('crease and boundary rules');
			if (n == 1) {
				// warn dunno this?
			}
		} else {
		}
		
		newSourceVertex = oldVertex.clone().multiplyScalar( 1 - n * beta );

		tmp.set(0, 0, 0);

		for (j=0; j<n; j++) {
			connectingEdge = connectingEdges[ j ];
			other = connectingEdge.a !== oldVertex ? connectingEdge.a : connectingEdge.b;
			tmp.add( other );
		}

		tmp.multiplyScalar( beta );

		// for each connectingEdgeVertex
		newSourceVertex.add( tmp );
		
		newSourceVertices.push( newSourceVertex );
	}


						   
// 3. Create Faces

newVertices = newSourceVertices.concat( newEdgeVertices );
sl = newSourceVertices.length;
newFaces = [];

for (i=0, il=oldFaces.length; i < il; i++) {
	face = oldFaces[i];

	// find the 3 edges
	// create 4 faces.

	edge1 = getEdge( face.a, face.b, edges ).newEdge + sl;
	edge2 = getEdge( face.b, face.c, edges ).newEdge + sl;
	edge3 = getEdge( face.c, face.a, edges ).newEdge + sl;

	newFace( newFaces, edge1, edge2, edge3 );
	newFace( newFaces, face.a, edge1, edge3 );
	newFace( newFaces, face.b, edge2, edge1 );
	newFace( newFaces, face.c, edge3, edge2 );

}


	var newGeometry = oldGeometry; // Let's pretend the old geometry is now new :P

	newGeometry.vertices = newVertices;
	newGeometry.faces = newFaces;


	delete newGeometry.__tmpVertices; // makes __tmpVertices undefined :P

	newGeometry.computeCentroids();
	newGeometry.computeFaceNormals();
	// newGeometry.computeVertexNormals();
	console.log('done');

};

function newFace(newFaces, a, b, c) {
	newFaces.push( new THREE.Face3( a, b, c ) );
}