three.js/examples/js/modifiers/SimplifyModifier.js

/*
 *	@author zz85 / http://twitter.com/blurspline / http://www.lab4games.net/zz85/blog
 *
 *	Simplification Geometry Modifier
 *    - based on code and technique
 *	  - by Stan Melax in 1998
 *	  - Progressive Mesh type Polygon Reduction Algorithm
 *    - http://www.melax.com/polychop/
 */

THREE.SimplifyModifier = function() {

};

(function() {

	var cb = new THREE.Vector3(), ab = new THREE.Vector3();

	function pushIfUnique( array, object ) {

		if ( array.indexOf( object ) === -1 ) array.push( object );

	}

	function removeFromArray( array, object ) {

		var k = array.indexOf( object );
		if ( k > -1 ) array.splice( k, 1 );

	}

	function computeEdgeCollapseCost( u, v ) {

		// if we collapse edge uv by moving u to v then how
		// much different will the model change, i.e. the "error".

		var edgelength = v.position.distanceTo( u.position );
		var curvature = 0;

		var sideFaces = [];
		var i, uFaces = u.faces, il = u.faces.length, face, sideFace;

		// find the "sides" triangles that are on the edge uv
		for ( i = 0 ; i < il; i ++ ) {

			face = u.faces[ i ];

			if ( face.hasVertex(v) ) {

				sideFaces.push( face );

			}

		}

		// use the triangle facing most away from the sides
		// to determine our curvature term
		for ( i = 0 ; i < il; i ++ ) {

			var minCurvature = 1;
			face = u.faces[ i ];

			for( var j = 0; j < sideFaces.length; j ++ ) {

				sideFace = sideFaces[ j ];
				// use dot product of face normals.
				var dotProd = face.normal.dot( sideFace.normal );
				minCurvature = Math.min( minCurvature, ( 1.001 - dotProd ) / 2);
			}

			curvature = Math.max( curvature, minCurvature );
		}

		// crude approach in attempt to preserve borders
		// though it seems not to be totally correct
		var borders = 0;
		if ( sideFaces.length < 2 ) {

			// we add some arbitrary cost for borders,
			// borders += 10;
			curvature = 1;
		}

		var amt = edgelength * curvature + borders;

		return amt;

	}

	function computeEdgeCostAtVertex( v ) {
		// compute the edge collapse cost for all edges that start
		// from vertex v.  Since we are only interested in reducing
		// the object by selecting the min cost edge at each step, we
		// only cache the cost of the least cost edge at this vertex
		// (in member variable collapse) as well as the value of the
		// cost (in member variable collapseCost).

		if ( v.neighbors.length === 0 ) {

			// collapse if no neighbors.
			v.collapseNeighbor = null;
			v.collapseCost = - 0.01;

			return;

		}

		v.collapseCost = 100000;
		v.collapseNeighbor = null;

		// search all neighboring edges for "least cost" edge
		for ( var i = 0; i < v.neighbors.length; i ++ ) {

			var collapseCost = computeEdgeCollapseCost( v, v.neighbors[ i ] );

			if ( !v.collapseNeighbor ) {
				v.collapseNeighbor = v.neighbors[ i ];
				v.collapseCost = collapseCost;
				v.minCost = collapseCost;
				v.totalCost = 0;
				v.costCount = 0;
			}

			v.costCount ++;
			v.totalCost += collapseCost;

			if ( collapseCost < v.minCost ) {

				v.collapseNeighbor = v.neighbors[ i ];
				v.minCost = collapseCost;

			}

		}

		// we average the cost of collapsing at this vertex
		v.collapseCost = v.totalCost / v.costCount;
		// v.collapseCost = v.minCost;

	}

	function removeVertex( v, vertices ) {

		console.assert( v.faces.length === 0 );

		while ( v.neighbors.length ) {

			var n = v.neighbors.pop();
			removeFromArray( n.neighbors, v );

		}

		removeFromArray( vertices, v );

	}

	function removeFace( f, faces ) {

		removeFromArray( faces, f );

		if ( f.v1 ) removeFromArray( f.v1.faces, f );
		if ( f.v2 ) removeFromArray( f.v2.faces, f );
		if ( f.v3 ) removeFromArray( f.v3.faces, f );

		// TODO optimize this!
		var vs = [ this.v1, this.v2, this.v3 ];
		var v1, v2;

		for( var i = 0 ; i < 3 ; i ++ ) {
			v1 = vs[ i ];
			v2 = vs[( i+1) % 3 ];

			if( !v1 || !v2 ) continue;
			v1.removeIfNonNeighbor( v2 );
			v2.removeIfNonNeighbor( v1 );
		}

	}

	function collapse( vertices, faces, u, v ) { // u and v are pointers to vertices of an edge

		// Collapse the edge uv by moving vertex u onto v

		if ( !v ) {

			// u is a vertex all by itself so just delete it..
			removeVertex( u, vertices );
			return;

		}

		var i;
		var tmpVertices = [];

		for( i = 0 ; i < u.neighbors.length; i ++ ) {

			tmpVertices.push( u.neighbors[ i ] );

		}


		// delete triangles on edge uv:
		for( i = u.faces.length - 1; i >= 0; i -- ) {

			if ( u.faces[ i ].hasVertex( v ) ) {

				removeFace( u.faces[ i ], faces );

			}

		}

		// update remaining triangles to have v instead of u
		for( i = u.faces.length -1 ; i >= 0; i -- ) {

			u.faces[i].replaceVertex( u, v );

		}


		removeVertex( u, vertices );

		// recompute the edge collapse costs in neighborhood
		for( i = 0; i < tmpVertices.length; i ++ ) {

			computeEdgeCostAtVertex( tmpVertices[ i ] );

		}

	}



	function minimumCostEdge( vertices ) {

		// O(n * n) approach. TODO optimize this

		var least = vertices[ 0 ];

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

			if ( vertices[ i ].collapseCost < least.collapseCost ) {

				least = vertices[ i ];

			}
		}

		return least;

	}

	// we use a triangle class to represent structure of face slightly differently

	function Triangle( v1, v2, v3, a, b, c ) {
		this.a = a;
		this.b = b;
		this.c = c;

		this.v1 = v1;
		this.v2 = v2;
		this.v3 = v3;

		this.normal = new THREE.Vector3();

		this.computeNormal();

		v1.faces.push( this );
		v1.addUniqueNeighbor( v2 );
		v1.addUniqueNeighbor( v3 );

		v2.faces.push( this );
		v2.addUniqueNeighbor( v1 );
		v2.addUniqueNeighbor( v3 );


		v3.faces.push( this );
		v3.addUniqueNeighbor( v1 );
		v3.addUniqueNeighbor( v2 );

	}

	Triangle.prototype.computeNormal = function() {

		var vA = this.v1.position;
		var vB = this.v2.position;
		var vC = this.v3.position;

		cb.subVectors( vC, vB );
		ab.subVectors( vA, vB );
		cb.cross( ab ).normalize();

		this.normal.copy( cb );

	};

	Triangle.prototype.hasVertex = function( v ) {

		return v === this.v1 || v === this.v2 || v === this.v3;

	};

	Triangle.prototype.replaceVertex = function( oldv, newv ) {

		if ( oldv === this.v1 ) this.v1 = newv;
		else if ( oldv === this.v2 ) this.v2 = newv;
		else if ( oldv === this.v3 ) this.v3 = newv;

		removeFromArray( oldv.faces, this );
		newv.faces.push( this );


		oldv.removeIfNonNeighbor( this.v1 );
		this.v1.removeIfNonNeighbor( oldv );

		oldv.removeIfNonNeighbor( this.v2 );
		this.v2.removeIfNonNeighbor( oldv );

		oldv.removeIfNonNeighbor( this.v3 );
		this.v3.removeIfNonNeighbor( oldv );

		this.v1.addUniqueNeighbor( this.v2 );
		this.v1.addUniqueNeighbor( this.v3 );

		this.v2.addUniqueNeighbor( this.v1 );
		this.v2.addUniqueNeighbor( this.v3 );

		this.v3.addUniqueNeighbor( this.v1 );
		this.v3.addUniqueNeighbor( this.v2 );

		this.computeNormal();

	};

	function Vertex( v, id ) {

		this.position = v;

		this.id = id; // old index id

		this.faces = []; // faces vertex is connected
		this.neighbors = []; // neighbouring vertices aka "adjacentVertices"

		// these will be computed in computeEdgeCostAtVertex()
		this.collapseCost = 0; // cost of collapsing this vertex, the less the better. aka objdist
		this.collapseNeighbor = null; // best candinate for collapsing

	}

	Vertex.prototype.addUniqueNeighbor = function( vertex ) {
		pushIfUnique(this.neighbors, vertex);
	};

	Vertex.prototype.removeIfNonNeighbor = function( n ) {

		var neighbors = this.neighbors;
		var faces = this.faces;

		var offset = neighbors.indexOf( n );
		if ( offset === -1 ) return;
		for ( var i = 0; i < faces.length; i ++ ) {

			if ( faces[ i ].hasVertex( n ) ) return;

		}

		neighbors.splice( offset, 1 );
	};

	THREE.SimplifyModifier.prototype.modify = function( geometry, count ) {

		if ( geometry instanceof THREE.BufferGeometry && !geometry.vertices && !geometry.faces ) {
			console.log('converting BufferGeometry to Geometry');
			geometry = new THREE.Geometry().fromBufferGeometry( geometry );
		}

		geometry.mergeVertices();

		var oldVertices = geometry.vertices; // Three Position
		var oldFaces = geometry.faces; // Three Face

		var newGeometry = new THREE.Geometry();

		// conversion
		var vertices = new Array( oldVertices.length ); // Simplify Custom Vertex Struct
		var faces = new Array( oldFaces.length ); // Simplify Custom Traignle Struct

		var i, il, face;

		//
		// put data of original geometry in different data structures
		//

		// add vertices
		for ( i = 0, il = oldVertices.length; i < il; i ++ ) {

			vertices[ i ] = new Vertex( oldVertices[ i ], i );

		}

		// add faces
		for ( i = 0, il = oldFaces.length; i < il; i ++ ) {

			face = oldFaces[ i ];
			faces[ i ] = new Triangle( vertices[ face.a ], vertices[ face.b ], vertices[ face.c ], face.a, face.b, face.c );

		}

		// compute all edge collapse costs
		for ( i = 0, il = vertices.length; i < il; i ++ ) {

			computeEdgeCostAtVertex( vertices[ i ] );

		}

		var permutation = new Array( vertices.length );
		var map = new Array( vertices.length );

		var nextVertex;

		var z = count;

		// console.time('z')
		// console.profile('zz');

		while( z-- ) {
			nextVertex = minimumCostEdge( vertices );
			if (!nextVertex) {
				console.log('no next vertex');
				break;
			}
			collapse( vertices, faces, nextVertex, nextVertex.collapseNeighbor );
		}

		// console.profileEnd('zz');
		// console.timeEnd('z')

		// TODO convert to buffer geometry.
		var newGeo = new THREE.Geometry();

		for ( i = 0; i < vertices.length; i ++ ) {

			var v = vertices[ i ];
			newGeo.vertices.push( v.position )

		}

		for ( i = 0; i < faces.length; i ++ ) {

			var tri = faces[ i ];
			newGeo.faces.push( new THREE.Face3(
				vertices.indexOf(tri.v1),
				vertices.indexOf(tri.v2),
				vertices.indexOf(tri.v3)
			) )

		}

		return newGeo;
	};
})();