2 window.ThreeBSP = (
function() {
11 ThreeBSP =
function( geometry ) {
14 face, vertex, faceVertexUvs, uvs,
19 if ( geometry instanceof THREE.Geometry ) {
20 this.matrix =
new THREE.Matrix4;
21 }
else if ( geometry instanceof THREE.Mesh ) {
23 geometry.updateMatrix();
24 this.matrix = geometry.matrix.clone();
25 geometry = geometry.geometry;
26 }
else if ( geometry instanceof ThreeBSP.Node ) {
28 this.matrix =
new THREE.Matrix4;
31 throw 'ThreeBSP: Given geometry is unsupported';
34 for ( i = 0, _length_i = geometry.faces.length; i < _length_i; i++ ) {
35 face = geometry.faces[i];
37 polygon =
new ThreeBSP.Polygon;
39 if ( face instanceof THREE.Face3 ) {
40 vertex = geometry.vertices[ face.a ];
41 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[0].x, faceVertexUvs[0].y ) : null;
42 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[0], uvs );
43 vertex.applyMatrix4(this.matrix);
44 polygon.vertices.push( vertex );
46 vertex = geometry.vertices[ face.b ];
47 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[1].x, faceVertexUvs[1].y ) : null;
48 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[1], uvs );
49 vertex.applyMatrix4(this.matrix);
50 polygon.vertices.push( vertex );
52 vertex = geometry.vertices[ face.c ];
53 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[2].x, faceVertexUvs[2].y ) : null;
54 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[2], uvs );
55 vertex.applyMatrix4(this.matrix);
56 polygon.vertices.push( vertex );
57 }
else if ( typeof THREE.Face4 ) {
58 vertex = geometry.vertices[ face.a ];
59 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[0].x, faceVertexUvs[0].y ) : null;
60 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[0], uvs );
61 vertex.applyMatrix4(this.matrix);
62 polygon.vertices.push( vertex );
64 vertex = geometry.vertices[ face.b ];
65 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[1].x, faceVertexUvs[1].y ) : null;
66 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[1], uvs );
67 vertex.applyMatrix4(this.matrix);
68 polygon.vertices.push( vertex );
70 vertex = geometry.vertices[ face.c ];
71 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[2].x, faceVertexUvs[2].y ) : null;
72 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[2], uvs );
73 vertex.applyMatrix4(this.matrix);
74 polygon.vertices.push( vertex );
76 vertex = geometry.vertices[ face.d ];
77 uvs = faceVertexUvs ?
new THREE.Vector2( faceVertexUvs[3].x, faceVertexUvs[3].y ) : null;
78 vertex =
new ThreeBSP.Vertex( vertex.x, vertex.y, vertex.z, face.vertexNormals[3], uvs );
79 vertex.applyMatrix4(this.matrix);
80 polygon.vertices.push( vertex );
82 throw 'Invalid face type at index ' + i;
85 polygon.calculateProperties();
86 polygons.push( polygon );
89 this.tree =
new ThreeBSP.Node( polygons );
92 ThreeBSP.prototype.subtract =
function( other_tree ) {
93 var a = this.tree.clone(),
94 b = other_tree.tree.clone();
102 a.build( b.allPolygons() );
104 a =
new ThreeBSP( a );
105 a.matrix = this.matrix;
108 ThreeBSP.prototype.union =
function( other_tree ) {
109 var a = this.tree.clone(),
110 b = other_tree.tree.clone();
117 a.build( b.allPolygons() );
118 a =
new ThreeBSP( a );
119 a.matrix = this.matrix;
122 ThreeBSP.prototype.intersect =
function( other_tree ) {
123 var a = this.tree.clone(),
124 b = other_tree.tree.clone();
131 a.build( b.allPolygons() );
133 a =
new ThreeBSP( a );
134 a.matrix = this.matrix;
137 ThreeBSP.prototype.toGeometry =
function() {
139 matrix =
new THREE.Matrix4().getInverse( this.matrix ),
140 geometry =
new THREE.Geometry(),
141 polygons = this.tree.allPolygons(),
142 polygon_count = polygons.length,
143 polygon, polygon_vertice_count,
145 vertex_idx_a, vertex_idx_b, vertex_idx_c,
149 for ( i = 0; i < polygon_count; i++ ) {
150 polygon = polygons[i];
151 polygon_vertice_count = polygon.vertices.length;
153 for ( j = 2; j < polygon_vertice_count; j++ ) {
156 vertex = polygon.vertices[0];
157 verticeUvs.push(
new THREE.Vector2( vertex.uv.x, vertex.uv.y ) );
158 vertex =
new THREE.Vector3( vertex.x, vertex.y, vertex.z );
159 vertex.applyMatrix4(matrix);
161 if ( typeof vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] !==
'undefined' ) {
162 vertex_idx_a = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ];
164 geometry.vertices.push( vertex );
165 vertex_idx_a = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] = geometry.vertices.length - 1;
168 vertex = polygon.vertices[j-1];
169 verticeUvs.push(
new THREE.Vector2( vertex.uv.x, vertex.uv.y ) );
170 vertex =
new THREE.Vector3( vertex.x, vertex.y, vertex.z );
171 vertex.applyMatrix4(matrix);
172 if ( typeof vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] !==
'undefined' ) {
173 vertex_idx_b = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ];
175 geometry.vertices.push( vertex );
176 vertex_idx_b = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] = geometry.vertices.length - 1;
179 vertex = polygon.vertices[j];
180 verticeUvs.push(
new THREE.Vector2( vertex.uv.x, vertex.uv.y ) );
181 vertex =
new THREE.Vector3( vertex.x, vertex.y, vertex.z );
182 vertex.applyMatrix4(matrix);
183 if ( typeof vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] !==
'undefined' ) {
184 vertex_idx_c = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ];
186 geometry.vertices.push( vertex );
187 vertex_idx_c = vertice_dict[ vertex.x +
',' + vertex.y +
',' + vertex.z ] = geometry.vertices.length - 1;
190 face =
new THREE.Face3(
194 new THREE.Vector3( polygon.normal.x, polygon.normal.y, polygon.normal.z )
197 geometry.faces.push( face );
198 geometry.faceVertexUvs[0].push( verticeUvs );
204 ThreeBSP.prototype.toMesh =
function( material ) {
205 var geometry = this.toGeometry(),
206 mesh =
new THREE.Mesh( geometry, material );
208 mesh.position.setFromMatrixPosition( this.matrix );
209 mesh.rotation.setFromRotationMatrix( this.matrix );
215 ThreeBSP.Polygon =
function( vertices, normal, w ) {
216 if ( !( vertices instanceof Array ) ) {
220 this.vertices = vertices;
221 if ( vertices.length > 0 ) {
222 this.calculateProperties();
224 this.normal = this.w = undefined;
227 ThreeBSP.Polygon.prototype.calculateProperties =
function() {
228 var a = this.vertices[0],
229 b = this.vertices[1],
230 c = this.vertices[2];
232 this.normal = b.clone().subtract( a ).cross(
233 c.clone().subtract( a )
236 this.w = this.normal.clone().dot( a );
240 ThreeBSP.Polygon.prototype.clone =
function() {
241 var i, vertice_count,
242 polygon =
new ThreeBSP.Polygon;
244 for ( i = 0, vertice_count = this.vertices.length; i < vertice_count; i++ ) {
245 polygon.vertices.push( this.vertices[i].clone() );
247 polygon.calculateProperties();
252 ThreeBSP.Polygon.prototype.flip =
function() {
253 var i, vertices = [];
255 this.normal.multiplyScalar( -1 );
258 for ( i = this.vertices.length - 1; i >= 0; i-- ) {
259 vertices.push( this.vertices[i] );
261 this.vertices = vertices;
265 ThreeBSP.Polygon.prototype.classifyVertex =
function( vertex ) {
266 var side_value = this.normal.dot( vertex ) - this.w;
268 if ( side_value < -EPSILON ) {
270 }
else if ( side_value > EPSILON ) {
276 ThreeBSP.Polygon.prototype.classifySide =
function( polygon ) {
277 var i, vertex, classification,
280 vertice_count = polygon.vertices.length;
282 for ( i = 0; i < vertice_count; i++ ) {
283 vertex = polygon.vertices[i];
284 classification = this.classifyVertex( vertex );
285 if ( classification === FRONT ) {
287 }
else if ( classification === BACK ) {
292 if ( num_positive > 0 && num_negative === 0 ) {
294 }
else if ( num_positive === 0 && num_negative > 0 ) {
296 }
else if ( num_positive === 0 && num_negative === 0 ) {
302 ThreeBSP.Polygon.prototype.splitPolygon =
function( polygon, coplanar_front, coplanar_back, front, back ) {
303 var classification = this.classifySide( polygon );
305 if ( classification === COPLANAR ) {
307 ( this.normal.dot( polygon.normal ) > 0 ? coplanar_front : coplanar_back ).push( polygon );
309 }
else if ( classification === FRONT ) {
311 front.push( polygon );
313 }
else if ( classification === BACK ) {
315 back.push( polygon );
320 i, j, ti, tj, vi, vj,
325 for ( i = 0, vertice_count = polygon.vertices.length; i < vertice_count; i++ ) {
327 j = (i + 1) % vertice_count;
328 vi = polygon.vertices[i];
329 vj = polygon.vertices[j];
330 ti = this.classifyVertex( vi );
331 tj = this.classifyVertex( vj );
333 if ( ti != BACK ) f.push( vi );
334 if ( ti != FRONT ) b.push( vi );
335 if ( (ti | tj) === SPANNING ) {
336 t = ( this.w - this.normal.dot( vi ) ) / this.normal.dot( vj.clone().subtract( vi ) );
337 v = vi.interpolate( vj, t );
344 if ( f.length >= 3 ) front.push(
new ThreeBSP.Polygon( f ).calculateProperties() );
345 if ( b.length >= 3 ) back.push(
new ThreeBSP.Polygon( b ).calculateProperties() );
349 ThreeBSP.Vertex =
function( x, y, z, normal, uv ) {
353 this.normal = normal ||
new THREE.Vector3;
354 this.uv = uv ||
new THREE.Vector2;
356 ThreeBSP.Vertex.prototype.clone =
function() {
357 return new ThreeBSP.Vertex( this.x, this.y, this.z, this.normal.clone(), this.uv.clone() );
359 ThreeBSP.Vertex.prototype.add =
function( vertex ) {
365 ThreeBSP.Vertex.prototype.subtract =
function( vertex ) {
371 ThreeBSP.Vertex.prototype.multiplyScalar =
function( scalar ) {
377 ThreeBSP.Vertex.prototype.cross =
function( vertex ) {
382 this.x = y * vertex.z - z * vertex.y;
383 this.y = z * vertex.x - x * vertex.z;
384 this.z = x * vertex.y - y * vertex.x;
388 ThreeBSP.Vertex.prototype.normalize =
function() {
389 var length = Math.sqrt( this.x * this.x + this.y * this.y + this.z * this.z );
397 ThreeBSP.Vertex.prototype.dot =
function( vertex ) {
398 return this.x * vertex.x + this.y * vertex.y + this.z * vertex.z;
400 ThreeBSP.Vertex.prototype.lerp =
function( a, t ) {
402 a.clone().subtract(
this ).multiplyScalar( t )
406 a.normal.clone().sub( this.normal ).multiplyScalar( t )
410 a.uv.clone().sub( this.uv ).multiplyScalar( t )
415 ThreeBSP.Vertex.prototype.interpolate =
function( other, t ) {
416 return this.clone().lerp( other, t );
418 ThreeBSP.Vertex.prototype.applyMatrix4 =
function ( m ) {
422 var x = this.x, y = this.y, z = this.z;
426 this.x = e[0] * x + e[4] * y + e[8] * z + e[12];
427 this.y = e[1] * x + e[5] * y + e[9] * z + e[13];
428 this.z = e[2] * x + e[6] * y + e[10] * z + e[14];
435 ThreeBSP.Node =
function( polygons ) {
436 var i, polygon_count,
441 this.front = this.back = undefined;
443 if ( !(polygons instanceof Array) || polygons.length === 0 )
return;
445 this.divider = polygons[0].clone();
449 for ( i = 0, polygon_count = polygons.length; i < polygon_count; i++ ) {
450 this.divider.splitPolygon( polygons[i], this.polygons, this.polygons, front, back );
455 if ( front.length > 0 ) {
456 this.front =
new ThreeBSP.Node( front );
459 if ( back.length > 0 ) {
460 this.back =
new ThreeBSP.Node( back );
463 ThreeBSP.Node.isConvex =
function( polygons ) {
465 for ( i = 0; i < polygons.length; i++ ) {
466 for ( j = 0; j < polygons.length; j++ ) {
467 if ( i !== j && polygons[i].classifySide( polygons[j] ) !== BACK ) {
474 ThreeBSP.Node.prototype.build =
function( polygons ) {
475 var i, polygon_count,
479 if ( !this.divider ) {
480 this.divider = polygons[0].clone();
483 for ( i = 0, polygon_count = polygons.length; i < polygon_count; i++ ) {
484 this.divider.splitPolygon( polygons[i], this.polygons, this.polygons, front, back );
487 if ( front.length > 0 ) {
488 if ( !this.front ) this.front =
new ThreeBSP.Node();
489 this.front.build( front );
492 if ( back.length > 0 ) {
493 if ( !this.back ) this.back =
new ThreeBSP.Node();
494 this.back.build( back );
497 ThreeBSP.Node.prototype.allPolygons =
function() {
498 var polygons = this.polygons.slice();
499 if ( this.front ) polygons = polygons.concat( this.front.allPolygons() );
500 if ( this.back ) polygons = polygons.concat( this.back.allPolygons() );
503 ThreeBSP.Node.prototype.clone =
function() {
504 var node =
new ThreeBSP.Node();
506 node.divider = this.divider.clone();
507 node.polygons = this.polygons.map(
function( polygon ) {
return polygon.clone(); } );
508 node.front = this.front && this.front.clone();
509 node.back = this.back && this.back.clone();
513 ThreeBSP.Node.prototype.invert =
function() {
514 var i, polygon_count, temp;
516 for ( i = 0, polygon_count = this.polygons.length; i < polygon_count; i++ ) {
517 this.polygons[i].flip();
521 if ( this.front ) this.front.invert();
522 if ( this.back ) this.back.invert();
525 this.front = this.back;
530 ThreeBSP.Node.prototype.clipPolygons =
function( polygons ) {
531 var i, polygon_count,
534 if ( !this.divider )
return polygons.slice();
536 front = [], back = [];
538 for ( i = 0, polygon_count = polygons.length; i < polygon_count; i++ ) {
539 this.divider.splitPolygon( polygons[i], front, back, front, back );
542 if ( this.front ) front = this.front.clipPolygons( front );
543 if ( this.back ) back = this.back.clipPolygons( back );
546 return front.concat( back );
549 ThreeBSP.Node.prototype.clipTo =
function( node ) {
550 this.polygons = node.clipPolygons( this.polygons );
551 if ( this.front ) this.front.clipTo( node );
552 if ( this.back ) this.back.clipTo( node );