Port of Evan Wallace's csg.js to Three.js

ThreeBSP.js

THREE.Vector3.prototype.lerp = function ( a, t ) {
	return this.clone().addSelf( a.clone().subSelf( this ).multiplyScalar( t ) );
};

THREE.Vertex.prototype.interpolate = function( other, t ) {
	var v = new THREE.Vertex( this.position.lerp( other.position, t ) );
	v.normal = this.normal.clone();
	return v;
};

THREE.Vertex.prototype.clone = function() {
	var vertex = new THREE.Vertex( this.position.clone() );
	if ( this.normal ) {
		vertex.normal = this.normal.clone();
	}
	return vertex;
};

THREE.Face3.prototype.clone = function() {
	return new THREE.Face3( this.a, this.b, this.c, this.normal.clone(), this.color.clone(), this.materialIndex );
};

THREE.Face3.prototype.flip = function() {
	this.normal.negate();
	
	var t = this.a;
	this.a = this.c;
	this.c = t;
	this.a.normal.negate();
	this.b.normal.negate();
	this.c.normal.negate();
};



THREE.BSPTree = {};
THREE.BSPTree.EPSILON = 1e-5;

THREE.BSPTree.Plane = function( normal, w ) {
	this.normal = normal;
	this.w = w;
};

THREE.BSPTree.Plane.prototype.clone = function() {
	return new THREE.BSPTree.Plane(this.normal.clone(), this.w);
};

THREE.BSPTree.Plane.prototype.flip = function() {
	this.normal = this.normal.clone().negate();
	this.w = -this.w;
};

THREE.BSPTree.Plane.prototype.splitPolygon = function( polygon, coplanarFront, coplanarBack, front, back ) {
	var COPLANAR = 0,
	FRONT = 1,
	BACK = 2,
	SPANNING = 3;
	
	// Classify each point as well as the entire polygon into one of the above
	// four classes.
	var polygonType = 0,
		types = [],
		vertices = [polygon.a, polygon.b, polygon.c],
		t, type, face;
	
	for (var i = 0; i < vertices.length; i++) {
		t = this.normal.dot( vertices[i].position ) - this.w;
		type = ( t < -THREE.BSPTree.EPSILON ) ? BACK : (t > THREE.BSPTree.EPSILON) ? FRONT : COPLANAR;
		polygonType |= type;
		types.push( type );
	}
	
	// Put the polygon in the correct list, splitting it when necessary.
	switch ( polygonType ) {
		case COPLANAR:
			( this.normal.dot( polygon.normal ) > 0 ? coplanarFront : coplanarBack ).push( polygon );
			break;
		case FRONT:
			front.push( polygon );
			break;
		case BACK:
			back.push( polygon );
			break;
		case SPANNING:
			var f = [], b = [];
			for (var i = 0; i < vertices.length; i++) {
				var j = (i + 1) % vertices.length;
				var ti = types[i], tj = types[j];
				var vi = vertices[i], vj = vertices[j];
				if (ti != BACK) f.push( vi );
				if (ti != FRONT) b.push( ti != BACK ? vi.clone() : vi );
				if ((ti | tj) == SPANNING) {
					var t = ( this.w - this.normal.dot( vi.position ) ) / this.normal.dot( vj.position.clone().subSelf( vi.position ) );
					var v = vi.interpolate( vj, t );
					f.push( v.clone() );
					b.push( v.clone() );
				}
			}
			
			if (f.length >= 3) {
				for ( i = 2; i < f.length; i++ ) {
					face = new THREE.Face3(
						f[0], f[i-1], f[i],
						f[0].normal
					);
					front.push( face );
				}
			}
			
			if (b.length >= 3) {
				for ( i = 2; i < b.length; i++ ) {
					face = new THREE.Face3(
						b[0], b[i-1], b[i],
						b[0].normal
					);
					back.push( face );
				}
			}
			
			break;
	}
};

THREE.BSPTree.Node = function ( source, options ) {
	this.plane = null;
	this.front = null;
	this.back = null;
	this.polygons = [];
	
	if ( source ) {
		this.build( source, options );
	}
};

THREE.BSPTree.Node.prototype.clone = function( ) {
	var node = new THREE.BSPTree.Node();
	node.plane = this.plane && this.plane.clone();
	node.front = this.front && this.front.clone();
	node.back = this.back && this.back.clone();
	node.polygons = this.polygons.map( function(p) { return p.clone(); } );
	return node;
};


THREE.BSPTree.Node.prototype.invert = function( ) {
	for (var i = 0; i < this.polygons.length; i++) {
	  this.polygons[i].flip();
	}
	this.plane.flip();
	if (this.front) this.front.invert();
	if (this.back) this.back.invert();
	var temp = this.front;
	this.front = this.back;
	this.back = temp;
};

THREE.BSPTree.Node.prototype.clipPolygons = function( polygons ) {
	var front = [], back = [];
	for (var i = 0; i < polygons.length; i++) {
	  this.plane.splitPolygon( polygons[i], front, back, front, back );
	}
	if (this.front) {
		front = this.front.clipPolygons( front );
	}
	if (this.back) {
		back = this.back.clipPolygons( back );
	} else {
		back = [];
	}
	return front.concat( back );
};

THREE.BSPTree.Node.prototype.clipTo = function( bsp ) {
	this.polygons = bsp.clipPolygons( this.polygons );
	if ( this.front ) this.front.clipTo( bsp );
	if ( this.back ) this.back.clipTo( bsp );
};

THREE.BSPTree.Node.prototype.allPolygons = function( ) {
	var polygons = this.polygons.slice();
	if ( this.front ) polygons = polygons.concat( this.front.allPolygons() );
	if ( this.back ) polygons = polygons.concat( this.back.allPolygons() );
	return polygons;
};

THREE.BSPTree.Node.prototype.build = function( source, options ) {
	var i, faces,
		face1, face2;
	
	options = options || {};
	options.offset = options.offset || {x: 0, y: 0, z:0};
	options.rotation = options.rotation || {x: 0, y: 0, z:0};
	
	if ( source instanceof THREE.Geometry ) {
		faces = source.faces;
		for ( i = 0; i < faces.length; i++ ) {
			
			// Convert any Face4 objects to Face3 so we don't go insane later
			if ( faces[i] instanceof THREE.Face4 ) {
				face1 = new THREE.Face3( source.vertices[faces[i].a].clone(), source.vertices[faces[i].b].clone(), source.vertices[faces[i].d].clone(), faces[i].normal );
				face1.vertexNormals.push(
					faces[i].vertexNormals[0],
					faces[i].vertexNormals[1],
					faces[i].vertexNormals[3]
				);
				
				face2 = new THREE.Face3( source.vertices[faces[i].b].clone(), source.vertices[faces[i].c].clone(), source.vertices[faces[i].d].clone(), faces[i].normal );
				face2.vertexNormals.push(
					faces[i].vertexNormals[1],
					faces[i].vertexNormals[2],
					faces[i].vertexNormals[3]
				);
				faces.splice( i, 1, face1, face2 );
			} else if ( !(faces[i].a instanceof THREE.Vertex) ) {
				faces[i].a = source.vertices[faces[i].a].clone();
				faces[i].b = source.vertices[faces[i].b].clone();
				faces[i].c = source.vertices[faces[i].c].clone();
			}
			
			faces[i].a.normal = faces[i].vertexNormals[0];
			faces[i].b.normal = faces[i].vertexNormals[1];
			faces[i].c.normal = faces[i].vertexNormals[2];
			
			// Apply offset
			faces[i].a.position.addSelf( options.offset );
			faces[i].b.position.addSelf( options.offset );
			faces[i].c.position.addSelf( options.offset );
		}
	} else if ( source instanceof Array ) {
		// Assume it's the correct kind of data
		faces = source;
	} else {
		// No idea what to do with this data
		return;
	}
	
	if (!this.plane) {
		var n = faces[0].b.position.clone().subSelf(
			faces[0].a.position
		).crossSelf(
			faces[0].c.position.clone().subSelf( faces[0].a.position )
		).normalize();
		this.plane = new THREE.BSPTree.Plane(
			n,
			n.clone().dot( faces[0].a.position )
		);
	}
	
	var front = [], back = [];
	for (var i = 0; i < faces.length; i++) {
		this.plane.splitPolygon( faces[i], this.polygons, this.polygons, front, back);
	}
	
	if (front.length) {
		if (!this.front) this.front = new THREE.BSPTree.Node();
		this.front.build( front, options );
	}
	if (back.length) {
		if (!this.back) this.back = new THREE.BSPTree.Node();
		this.back.build( back, options );
	}
};

THREE.BSPTree.Node.prototype.toGeometry = function( ) {
	var i, face,
		geometry = new THREE.Geometry(),
		polygons = this.allPolygons();
	
	for ( i = 0; i < polygons.length; i++ ) {
		// @todo, avoid overlapping vertices
		
		geometry.vertices.push( polygons[i].a, polygons[i].b, polygons[i].c );
		face = polygons[i];
		face.a = geometry.vertices.length - 3;
		face.b = geometry.vertices.length - 2;
		face.c = geometry.vertices.length - 1;
		geometry.faces.push( face );
		
		geometry.faceVertexUvs[0].push( new THREE.UV( ), new THREE.UV( ), new THREE.UV( ) );
	}
	
	geometry.computeBoundingBox();
	
	return geometry;
};

THREE.BSPTree.Node.prototype.union = function( bsp ) {
	var a = this.clone(), b = bsp.clone();
	a.clipTo(b);
	b.clipTo(a);
	b.invert();
	b.clipTo(a);
	b.invert();
	a.build(b.allPolygons());
	return a;
};

THREE.BSPTree.Node.prototype.subtract = function( bsp ) {
	var a = this.clone(), b = bsp.clone();
	a.invert();
	a.clipTo(b);
	b.clipTo(a);
	b.invert();
	b.clipTo(a);
	b.invert();
	a.build(b.allPolygons());
	a.invert();
	return a;	
};

THREE.BSPTree.Node.prototype.intersect = function( bsp ) {
	var a = this.clone(), b = bsp.clone();
	a.invert();
	b.clipTo(a);
	b.invert();
	a.clipTo(b);
	b.clipTo(a);
	a.build(b.allPolygons());
	a.invert();
	return a;
};

Hi Chandler. I'm new to using BSP trees and I am looking at using one for a terrain splatting project I'm doing. At the moment I'm not sure what would be the best approach to speeding up my scene and after doing some reading on the subject I think my best bet would be to use a BSP tree. Would the code you have created be applicable? Could it be used, for example, to speed up the rendering of a big THREE.Plane? I saw from your example you can use it to create geometries with differences and unions, but don't quite understand how that can be used outside of that context? Would be very grateful if you could perhaps point me in the right direction?

Many thanks
Mat

Wow great bsp structure like Quake or Half-Life bsp I will try to improve stronger bsp three

This is great, however, it doesnt cover several materials that the meshes might have had.
I'm trying to get my head around this, did anyone did something similar before?