1 /**
  2  * @author mrdoob / http://mrdoob.com/
  3  * @author alteredq / http://alteredqualia.com/
  4  */
  5 
  6 /**@namespace*/
  7 THREE.GeometryUtils = {
  8 
  9 	// Merge two geometries or geometry and geometry from object (using object's transform)
 10 
 11 	merge: function ( geometry1, object2 /* mesh | geometry */ ) {
 12 
 13 		var matrix, matrixRotation,
 14 		vertexOffset = geometry1.vertices.length,
 15 		uvPosition = geometry1.faceVertexUvs[ 0 ].length,
 16 		geometry2 = object2 instanceof THREE.Mesh ? object2.geometry : object2,
 17 		vertices1 = geometry1.vertices,
 18 		vertices2 = geometry2.vertices,
 19 		faces1 = geometry1.faces,
 20 		faces2 = geometry2.faces,
 21 		uvs1 = geometry1.faceVertexUvs[ 0 ],
 22 		uvs2 = geometry2.faceVertexUvs[ 0 ];
 23 
 24 		if ( object2 instanceof THREE.Mesh ) {
 25 
 26 			object2.matrixAutoUpdate && object2.updateMatrix();
 27 
 28 			matrix = object2.matrix;
 29 			matrixRotation = new THREE.Matrix4();
 30 			matrixRotation.extractRotation( matrix, object2.scale );
 31 
 32 		}
 33 
 34 		// vertices
 35 
 36 		for ( var i = 0, il = vertices2.length; i < il; i ++ ) {
 37 
 38 			var vertex = vertices2[ i ];
 39 
 40 			var vertexCopy = vertex.clone();
 41 
 42 			if ( matrix ) matrix.multiplyVector3( vertexCopy );
 43 
 44 			vertices1.push( vertexCopy );
 45 
 46 		}
 47 
 48 		// faces
 49 
 50 		for ( i = 0, il = faces2.length; i < il; i ++ ) {
 51 
 52 			var face = faces2[ i ], faceCopy, normal, color,
 53 			faceVertexNormals = face.vertexNormals,
 54 			faceVertexColors = face.vertexColors;
 55 
 56 			if ( face instanceof THREE.Face3 ) {
 57 
 58 				faceCopy = new THREE.Face3( face.a + vertexOffset, face.b + vertexOffset, face.c + vertexOffset );
 59 
 60 			} else if ( face instanceof THREE.Face4 ) {
 61 
 62 				faceCopy = new THREE.Face4( face.a + vertexOffset, face.b + vertexOffset, face.c + vertexOffset, face.d + vertexOffset );
 63 
 64 			}
 65 
 66 			faceCopy.normal.copy( face.normal );
 67 
 68 			if ( matrixRotation ) matrixRotation.multiplyVector3( faceCopy.normal );
 69 
 70 			for ( var j = 0, jl = faceVertexNormals.length; j < jl; j ++ ) {
 71 
 72 				normal = faceVertexNormals[ j ].clone();
 73 
 74 				if ( matrixRotation ) matrixRotation.multiplyVector3( normal );
 75 
 76 				faceCopy.vertexNormals.push( normal );
 77 
 78 			}
 79 
 80 			faceCopy.color.copy( face.color );
 81 
 82 			for ( var j = 0, jl = faceVertexColors.length; j < jl; j ++ ) {
 83 
 84 				color = faceVertexColors[ j ];
 85 				faceCopy.vertexColors.push( color.clone() );
 86 
 87 			}
 88 
 89 			faceCopy.materialIndex = face.materialIndex;
 90 
 91 			faceCopy.centroid.copy( face.centroid );
 92 			if ( matrix ) matrix.multiplyVector3( faceCopy.centroid );
 93 
 94 			faces1.push( faceCopy );
 95 
 96 		}
 97 
 98 		// uvs
 99 
100 		for ( i = 0, il = uvs2.length; i < il; i ++ ) {
101 
102 			var uv = uvs2[ i ], uvCopy = [];
103 
104 			for ( var j = 0, jl = uv.length; j < jl; j ++ ) {
105 
106 				uvCopy.push( new THREE.UV( uv[ j ].u, uv[ j ].v ) );
107 
108 			}
109 
110 			uvs1.push( uvCopy );
111 
112 		}
113 
114 	},
115 
116 	removeMaterials: function ( geometry, materialIndexArray ) {
117 
118 		var materialIndexMap = {};
119 
120 		for ( var i = 0, il = materialIndexArray.length; i < il; i ++ ) {
121 
122 			materialIndexMap[ materialIndexArray[i] ] = true;
123 
124 		}
125 
126 		var face, newFaces = [];
127 
128 		for ( var i = 0, il = geometry.faces.length; i < il; i ++ ) {
129 
130 			face = geometry.faces[ i ];
131 			if ( ! ( face.materialIndex in materialIndexMap ) ) newFaces.push( face );
132 
133 		}
134 
135 		geometry.faces = newFaces;
136 
137 	},
138 
139 	// Get random point in triangle (via barycentric coordinates)
140 	// 	(uniform distribution)
141 	// 	http://www.cgafaq.info/wiki/Random_Point_In_Triangle
142 
143 	randomPointInTriangle: function ( vectorA, vectorB, vectorC ) {
144 
145 		var a, b, c,
146 			point = new THREE.Vector3(),
147 			tmp = THREE.GeometryUtils.__v1;
148 
149 		a = THREE.GeometryUtils.random();
150 		b = THREE.GeometryUtils.random();
151 
152 		if ( ( a + b ) > 1 ) {
153 
154 			a = 1 - a;
155 			b = 1 - b;
156 
157 		}
158 
159 		c = 1 - a - b;
160 
161 		point.copy( vectorA );
162 		point.multiplyScalar( a );
163 
164 		tmp.copy( vectorB );
165 		tmp.multiplyScalar( b );
166 
167 		point.addSelf( tmp );
168 
169 		tmp.copy( vectorC );
170 		tmp.multiplyScalar( c );
171 
172 		point.addSelf( tmp );
173 
174 		return point;
175 
176 	},
177 
178 	// Get random point in face (triangle / quad)
179 	// (uniform distribution)
180 
181 	randomPointInFace: function ( face, geometry, useCachedAreas ) {
182 
183 		var vA, vB, vC, vD;
184 
185 		if ( face instanceof THREE.Face3 ) {
186 
187 			vA = geometry.vertices[ face.a ];
188 			vB = geometry.vertices[ face.b ];
189 			vC = geometry.vertices[ face.c ];
190 
191 			return THREE.GeometryUtils.randomPointInTriangle( vA, vB, vC );
192 
193 		} else if ( face instanceof THREE.Face4 ) {
194 
195 			vA = geometry.vertices[ face.a ];
196 			vB = geometry.vertices[ face.b ];
197 			vC = geometry.vertices[ face.c ];
198 			vD = geometry.vertices[ face.d ];
199 
200 			var area1, area2;
201 
202 			if ( useCachedAreas ) {
203 
204 				if ( face._area1 && face._area2 ) {
205 
206 					area1 = face._area1;
207 					area2 = face._area2;
208 
209 				} else {
210 
211 					area1 = THREE.GeometryUtils.triangleArea( vA, vB, vD );
212 					area2 = THREE.GeometryUtils.triangleArea( vB, vC, vD );
213 
214 					face._area1 = area1;
215 					face._area2 = area2;
216 
217 				}
218 
219 			} else {
220 
221 				area1 = THREE.GeometryUtils.triangleArea( vA, vB, vD ),
222 				area2 = THREE.GeometryUtils.triangleArea( vB, vC, vD );
223 
224 			}
225 
226 			var r = THREE.GeometryUtils.random() * ( area1 + area2 );
227 
228 			if ( r < area1 ) {
229 
230 				return THREE.GeometryUtils.randomPointInTriangle( vA, vB, vD );
231 
232 			} else {
233 
234 				return THREE.GeometryUtils.randomPointInTriangle( vB, vC, vD );
235 
236 			}
237 
238 		}
239 
240 	},
241 
242 	// Get uniformly distributed random points in mesh
243 	// 	- create array with cumulative sums of face areas
244 	//  - pick random number from 0 to total area
245 	//  - find corresponding place in area array by binary search
246 	//	- get random point in face
247 
248 	randomPointsInGeometry: function ( geometry, n ) {
249 
250 		var face, i,
251 			faces = geometry.faces,
252 			vertices = geometry.vertices,
253 			il = faces.length,
254 			totalArea = 0,
255 			cumulativeAreas = [],
256 			vA, vB, vC, vD;
257 
258 		// precompute face areas
259 
260 		for ( i = 0; i < il; i ++ ) {
261 
262 			face = faces[ i ];
263 
264 			if ( face instanceof THREE.Face3 ) {
265 
266 				vA = vertices[ face.a ];
267 				vB = vertices[ face.b ];
268 				vC = vertices[ face.c ];
269 
270 				face._area = THREE.GeometryUtils.triangleArea( vA, vB, vC );
271 
272 			} else if ( face instanceof THREE.Face4 ) {
273 
274 				vA = vertices[ face.a ];
275 				vB = vertices[ face.b ];
276 				vC = vertices[ face.c ];
277 				vD = vertices[ face.d ];
278 
279 				face._area1 = THREE.GeometryUtils.triangleArea( vA, vB, vD );
280 				face._area2 = THREE.GeometryUtils.triangleArea( vB, vC, vD );
281 
282 				face._area = face._area1 + face._area2;
283 
284 			}
285 
286 			totalArea += face._area;
287 
288 			cumulativeAreas[ i ] = totalArea;
289 
290 		}
291 
292 		// binary search cumulative areas array
293 
294 		function binarySearchIndices( value ) {
295 
296 			function binarySearch( start, end ) {
297 
298 				// return closest larger index
299 				// if exact number is not found
300 
301 				if ( end < start )
302 					return start;
303 
304 				var mid = start + Math.floor( ( end - start ) / 2 );
305 
306 				if ( cumulativeAreas[ mid ] > value ) {
307 
308 					return binarySearch( start, mid - 1 );
309 
310 				} else if ( cumulativeAreas[ mid ] < value ) {
311 
312 					return binarySearch( mid + 1, end );
313 
314 				} else {
315 
316 					return mid;
317 
318 				}
319 
320 			}
321 
322 			var result = binarySearch( 0, cumulativeAreas.length - 1 )
323 			return result;
324 
325 		}
326 
327 		// pick random face weighted by face area
328 
329 		var r, index,
330 			result = [];
331 
332 		var stats = {};
333 
334 		for ( i = 0; i < n; i ++ ) {
335 
336 			r = THREE.GeometryUtils.random() * totalArea;
337 
338 			index = binarySearchIndices( r );
339 
340 			result[ i ] = THREE.GeometryUtils.randomPointInFace( faces[ index ], geometry, true );
341 
342 			if ( ! stats[ index ] ) {
343 
344 				stats[ index ] = 1;
345 
346 			} else {
347 
348 				stats[ index ] += 1;
349 
350 			}
351 
352 		}
353 
354 		return result;
355 
356 	},
357 
358 	// Get triangle area (by Heron's formula)
359 	// 	http://en.wikipedia.org/wiki/Heron%27s_formula
360 
361 	triangleArea: function ( vectorA, vectorB, vectorC ) {
362 
363 		var s, a, b, c,
364 			tmp = THREE.GeometryUtils.__v1;
365 
366 		tmp.sub( vectorA, vectorB );
367 		a = tmp.length();
368 
369 		tmp.sub( vectorA, vectorC );
370 		b = tmp.length();
371 
372 		tmp.sub( vectorB, vectorC );
373 		c = tmp.length();
374 
375 		s = 0.5 * ( a + b + c );
376 
377 		return Math.sqrt( s * ( s - a ) * ( s - b ) * ( s - c ) );
378 
379 	},
380 
381 	// Center geometry so that 0,0,0 is in center of bounding box
382 
383 	center: function ( geometry ) {
384 
385 		geometry.computeBoundingBox();
386 
387 		var bb = geometry.boundingBox;
388 
389 		var offset = new THREE.Vector3();
390 
391 		offset.add( bb.min, bb.max );
392 		offset.multiplyScalar( -0.5 );
393 
394 		geometry.applyMatrix( new THREE.Matrix4().makeTranslation( offset.x, offset.y, offset.z ) );
395 		geometry.computeBoundingBox();
396 
397 		return offset;
398 
399 	},
400 
401 	// Normalize UVs to be from <0,1>
402 	// (for now just the first set of UVs)
403 
404 	normalizeUVs: function ( geometry ) {
405 
406 		var uvSet = geometry.faceVertexUvs[ 0 ];
407 
408 		for ( var i = 0, il = uvSet.length; i < il; i ++ ) {
409 
410 			var uvs = uvSet[ i ];
411 
412 			for ( var j = 0, jl = uvs.length; j < jl; j ++ ) {
413 
414 				// texture repeat
415 
416 				if( uvs[ j ].u !== 1.0 ) uvs[ j ].u = uvs[ j ].u - Math.floor( uvs[ j ].u );
417 				if( uvs[ j ].v !== 1.0 ) uvs[ j ].v = uvs[ j ].v - Math.floor( uvs[ j ].v );
418 
419 			}
420 
421 		}
422 
423 	},
424 
425 	triangulateQuads: function ( geometry ) {
426 
427 		var i, il, j, jl;
428 
429 		var faces = [];
430 		var faceUvs = [];
431 		var faceVertexUvs = [];
432 
433 		for ( i = 0, il = geometry.faceUvs.length; i < il; i ++ ) {
434 
435 			faceUvs[ i ] = [];
436 
437 		}
438 
439 		for ( i = 0, il = geometry.faceVertexUvs.length; i < il; i ++ ) {
440 
441 			faceVertexUvs[ i ] = [];
442 
443 		}
444 
445 		for ( i = 0, il = geometry.faces.length; i < il; i ++ ) {
446 
447 			var face = geometry.faces[ i ];
448 
449 			if ( face instanceof THREE.Face4 ) {
450 
451 				var a = face.a;
452 				var b = face.b;
453 				var c = face.c;
454 				var d = face.d;
455 
456 				var triA = new THREE.Face3();
457 				var triB = new THREE.Face3();
458 
459 				triA.color.copy( face.color );
460 				triB.color.copy( face.color );
461 
462 				triA.materialIndex = face.materialIndex;
463 				triB.materialIndex = face.materialIndex;
464 
465 				triA.a = a;
466 				triA.b = b;
467 				triA.c = d;
468 
469 				triB.a = b;
470 				triB.b = c;
471 				triB.c = d;
472 
473 				if ( face.vertexColors.length === 4 ) {
474 
475 					triA.vertexColors[ 0 ] = face.vertexColors[ 0 ].clone();
476 					triA.vertexColors[ 1 ] = face.vertexColors[ 1 ].clone();
477 					triA.vertexColors[ 2 ] = face.vertexColors[ 3 ].clone();
478 
479 					triB.vertexColors[ 0 ] = face.vertexColors[ 1 ].clone();
480 					triB.vertexColors[ 1 ] = face.vertexColors[ 2 ].clone();
481 					triB.vertexColors[ 2 ] = face.vertexColors[ 3 ].clone();
482 
483 				}
484 
485 				faces.push( triA, triB );
486 
487 				for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
488 
489 					if ( geometry.faceVertexUvs[ j ].length ) {
490 
491 						var uvs = geometry.faceVertexUvs[ j ][ i ];
492 
493 						var uvA = uvs[ 0 ];
494 						var uvB = uvs[ 1 ];
495 						var uvC = uvs[ 2 ];
496 						var uvD = uvs[ 3 ];
497 
498 						var uvsTriA = [ uvA.clone(), uvB.clone(), uvD.clone() ];
499 						var uvsTriB = [ uvB.clone(), uvC.clone(), uvD.clone() ];
500 
501 						faceVertexUvs[ j ].push( uvsTriA, uvsTriB );
502 
503 					}
504 
505 				}
506 
507 				for ( j = 0, jl = geometry.faceUvs.length; j < jl; j ++ ) {
508 
509 					if ( geometry.faceUvs[ j ].length ) {
510 
511 						var faceUv = geometry.faceUvs[ j ][ i ];
512 
513 						faceUvs[ j ].push( faceUv, faceUv );
514 
515 					}
516 
517 				}
518 
519 			} else {
520 
521 				faces.push( face );
522 
523 				for ( j = 0, jl = geometry.faceUvs.length; j < jl; j ++ ) {
524 
525 					faceUvs[ j ].push( geometry.faceUvs[ j ][ i ] );
526 
527 				}
528 
529 				for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
530 
531 					faceVertexUvs[ j ].push( geometry.faceVertexUvs[ j ][ i ] );
532 
533 				}
534 
535 			}
536 
537 		}
538 
539 		geometry.faces = faces;
540 		geometry.faceUvs = faceUvs;
541 		geometry.faceVertexUvs = faceVertexUvs;
542 
543 		geometry.computeCentroids();
544 		geometry.computeFaceNormals();
545 		geometry.computeVertexNormals();
546 
547 		if ( geometry.hasTangents ) geometry.computeTangents();
548 
549 	},
550 
551 	// Make all faces use unique vertices
552 	// so that each face can be separated from others
553 
554 	explode: function( geometry ) {
555 
556 		var vertices = [];
557 
558 		for ( var i = 0, il = geometry.faces.length; i < il; i ++ ) {
559 
560 			var n = vertices.length;
561 
562 			var face = geometry.faces[ i ];
563 
564 			if ( face instanceof THREE.Face4 ) {
565 
566 				var a = face.a;
567 				var b = face.b;
568 				var c = face.c;
569 				var d = face.d;
570 
571 				var va = geometry.vertices[ a ];
572 				var vb = geometry.vertices[ b ];
573 				var vc = geometry.vertices[ c ];
574 				var vd = geometry.vertices[ d ];
575 
576 				vertices.push( va.clone() );
577 				vertices.push( vb.clone() );
578 				vertices.push( vc.clone() );
579 				vertices.push( vd.clone() );
580 
581 				face.a = n;
582 				face.b = n + 1;
583 				face.c = n + 2;
584 				face.d = n + 3;
585 
586 			} else {
587 
588 				var a = face.a;
589 				var b = face.b;
590 				var c = face.c;
591 
592 				var va = geometry.vertices[ a ];
593 				var vb = geometry.vertices[ b ];
594 				var vc = geometry.vertices[ c ];
595 
596 				vertices.push( va.clone() );
597 				vertices.push( vb.clone() );
598 				vertices.push( vc.clone() );
599 
600 				face.a = n;
601 				face.b = n + 1;
602 				face.c = n + 2;
603 
604 			}
605 
606 		}
607 
608 		geometry.vertices = vertices;
609 		delete geometry.__tmpVertices;
610 
611 	},
612 
613 	// Break faces with edges longer than maxEdgeLength
614 	// - not recursive
615 
616 	tessellate: function ( geometry, maxEdgeLength ) {
617 
618 		var i, il, face,
619 		a, b, c, d,
620 		va, vb, vc, vd,
621 		dab, dbc, dac, dcd, dad,
622 		m, m1, m2,
623 		vm, vm1, vm2,
624 		vnm, vnm1, vnm2,
625 		vcm, vcm1, vcm2,
626 		triA, triB,
627 		quadA, quadB,
628 		edge;
629 
630 		var faces = [];
631 		var faceVertexUvs = [];
632 
633 		for ( i = 0, il = geometry.faceVertexUvs.length; i < il; i ++ ) {
634 
635 			faceVertexUvs[ i ] = [];
636 
637 		}
638 
639 		for ( i = 0, il = geometry.faces.length; i < il; i ++ ) {
640 
641 			face = geometry.faces[ i ];
642 
643 			if ( face instanceof THREE.Face3 ) {
644 
645 				a = face.a;
646 				b = face.b;
647 				c = face.c;
648 
649 				va = geometry.vertices[ a ];
650 				vb = geometry.vertices[ b ];
651 				vc = geometry.vertices[ c ];
652 
653 				dab = va.distanceTo( vb );
654 				dbc = vb.distanceTo( vc );
655 				dac = va.distanceTo( vc );
656 
657 				if ( dab > maxEdgeLength || dbc > maxEdgeLength || dac > maxEdgeLength ) {
658 
659 					m = geometry.vertices.length;
660 
661 					triA = face.clone();
662 					triB = face.clone();
663 
664 					if ( dab >= dbc && dab >= dac ) {
665 
666 						vm = va.clone();
667 						vm.lerpSelf( vb, 0.5 );
668 
669 						triA.a = a;
670 						triA.b = m;
671 						triA.c = c;
672 
673 						triB.a = m;
674 						triB.b = b;
675 						triB.c = c;
676 
677 						if ( face.vertexNormals.length === 3 ) {
678 
679 							vnm = face.vertexNormals[ 0 ].clone();
680 							vnm.lerpSelf( face.vertexNormals[ 1 ], 0.5 );
681 
682 							triA.vertexNormals[ 1 ].copy( vnm );
683 							triB.vertexNormals[ 0 ].copy( vnm );
684 
685 						}
686 
687 						if ( face.vertexColors.length === 3 ) {
688 
689 							vcm = face.vertexColors[ 0 ].clone();
690 							vcm.lerpSelf( face.vertexColors[ 1 ], 0.5 );
691 
692 							triA.vertexColors[ 1 ].copy( vcm );
693 							triB.vertexColors[ 0 ].copy( vcm );
694 
695 						}
696 
697 						edge = 0;
698 
699 					} else if ( dbc >= dab && dbc >= dac ) {
700 
701 						vm = vb.clone();
702 						vm.lerpSelf( vc, 0.5 );
703 
704 						triA.a = a;
705 						triA.b = b;
706 						triA.c = m;
707 
708 						triB.a = m;
709 						triB.b = c;
710 						triB.c = a;
711 
712 						if ( face.vertexNormals.length === 3 ) {
713 
714 							vnm = face.vertexNormals[ 1 ].clone();
715 							vnm.lerpSelf( face.vertexNormals[ 2 ], 0.5 );
716 
717 							triA.vertexNormals[ 2 ].copy( vnm );
718 
719 							triB.vertexNormals[ 0 ].copy( vnm );
720 							triB.vertexNormals[ 1 ].copy( face.vertexNormals[ 2 ] );
721 							triB.vertexNormals[ 2 ].copy( face.vertexNormals[ 0 ] );
722 
723 						}
724 
725 						if ( face.vertexColors.length === 3 ) {
726 
727 							vcm = face.vertexColors[ 1 ].clone();
728 							vcm.lerpSelf( face.vertexColors[ 2 ], 0.5 );
729 
730 							triA.vertexColors[ 2 ].copy( vcm );
731 
732 							triB.vertexColors[ 0 ].copy( vcm );
733 							triB.vertexColors[ 1 ].copy( face.vertexColors[ 2 ] );
734 							triB.vertexColors[ 2 ].copy( face.vertexColors[ 0 ] );
735 
736 						}
737 
738 						edge = 1;
739 
740 					} else {
741 
742 						vm = va.clone();
743 						vm.lerpSelf( vc, 0.5 );
744 
745 						triA.a = a;
746 						triA.b = b;
747 						triA.c = m;
748 
749 						triB.a = m;
750 						triB.b = b;
751 						triB.c = c;
752 
753 						if ( face.vertexNormals.length === 3 ) {
754 
755 							vnm = face.vertexNormals[ 0 ].clone();
756 							vnm.lerpSelf( face.vertexNormals[ 2 ], 0.5 );
757 
758 							triA.vertexNormals[ 2 ].copy( vnm );
759 							triB.vertexNormals[ 0 ].copy( vnm );
760 
761 						}
762 
763 						if ( face.vertexColors.length === 3 ) {
764 
765 							vcm = face.vertexColors[ 0 ].clone();
766 							vcm.lerpSelf( face.vertexColors[ 2 ], 0.5 );
767 
768 							triA.vertexColors[ 2 ].copy( vcm );
769 							triB.vertexColors[ 0 ].copy( vcm );
770 
771 						}
772 
773 						edge = 2;
774 
775 					}
776 
777 					faces.push( triA, triB );
778 					geometry.vertices.push( vm );
779 
780 					var j, jl, uvs, uvA, uvB, uvC, uvM, uvsTriA, uvsTriB;
781 
782 					for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
783 
784 						if ( geometry.faceVertexUvs[ j ].length ) {
785 
786 							uvs = geometry.faceVertexUvs[ j ][ i ];
787 
788 							uvA = uvs[ 0 ];
789 							uvB = uvs[ 1 ];
790 							uvC = uvs[ 2 ];
791 
792 							// AB
793 
794 							if ( edge === 0 ) {
795 
796 								uvM = uvA.clone();
797 								uvM.lerpSelf( uvB, 0.5 );
798 
799 								uvsTriA = [ uvA.clone(), uvM.clone(), uvC.clone() ];
800 								uvsTriB = [ uvM.clone(), uvB.clone(), uvC.clone() ];
801 
802 							// BC
803 
804 							} else if ( edge === 1 ) {
805 
806 								uvM = uvB.clone();
807 								uvM.lerpSelf( uvC, 0.5 );
808 
809 								uvsTriA = [ uvA.clone(), uvB.clone(), uvM.clone() ];
810 								uvsTriB = [ uvM.clone(), uvC.clone(), uvA.clone() ];
811 
812 							// AC
813 
814 							} else {
815 
816 								uvM = uvA.clone();
817 								uvM.lerpSelf( uvC, 0.5 );
818 
819 								uvsTriA = [ uvA.clone(), uvB.clone(), uvM.clone() ];
820 								uvsTriB = [ uvM.clone(), uvB.clone(), uvC.clone() ];
821 
822 							}
823 
824 							faceVertexUvs[ j ].push( uvsTriA, uvsTriB );
825 
826 						}
827 
828 					}
829 
830 				} else {
831 
832 					faces.push( face );
833 
834 					for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
835 
836 						faceVertexUvs[ j ].push( geometry.faceVertexUvs[ j ][ i ] );
837 
838 					}
839 
840 				}
841 
842 			} else {
843 
844 				a = face.a;
845 				b = face.b;
846 				c = face.c;
847 				d = face.d;
848 
849 				va = geometry.vertices[ a ];
850 				vb = geometry.vertices[ b ];
851 				vc = geometry.vertices[ c ];
852 				vd = geometry.vertices[ d ];
853 
854 				dab = va.distanceTo( vb );
855 				dbc = vb.distanceTo( vc );
856 				dcd = vc.distanceTo( vd );
857 				dad = va.distanceTo( vd );
858 
859 				if ( dab > maxEdgeLength || dbc > maxEdgeLength || dcd > maxEdgeLength || dad > maxEdgeLength ) {
860 
861 					m1 = geometry.vertices.length;
862 					m2 = geometry.vertices.length + 1;
863 
864 					quadA = face.clone();
865 					quadB = face.clone();
866 
867 					if ( ( dab >= dbc && dab >= dcd && dab >= dad ) || ( dcd >= dbc && dcd >= dab && dcd >= dad ) ) {
868 
869 						vm1 = va.clone();
870 						vm1.lerpSelf( vb, 0.5 );
871 
872 						vm2 = vc.clone();
873 						vm2.lerpSelf( vd, 0.5 );
874 
875 						quadA.a = a;
876 						quadA.b = m1;
877 						quadA.c = m2;
878 						quadA.d = d;
879 
880 						quadB.a = m1;
881 						quadB.b = b;
882 						quadB.c = c;
883 						quadB.d = m2;
884 
885 						if ( face.vertexNormals.length === 4 ) {
886 
887 							vnm1 = face.vertexNormals[ 0 ].clone();
888 							vnm1.lerpSelf( face.vertexNormals[ 1 ], 0.5 );
889 
890 							vnm2 = face.vertexNormals[ 2 ].clone();
891 							vnm2.lerpSelf( face.vertexNormals[ 3 ], 0.5 );
892 
893 							quadA.vertexNormals[ 1 ].copy( vnm1 );
894 							quadA.vertexNormals[ 2 ].copy( vnm2 );
895 
896 							quadB.vertexNormals[ 0 ].copy( vnm1 );
897 							quadB.vertexNormals[ 3 ].copy( vnm2 );
898 
899 						}
900 
901 						if ( face.vertexColors.length === 4 ) {
902 
903 							vcm1 = face.vertexColors[ 0 ].clone();
904 							vcm1.lerpSelf( face.vertexColors[ 1 ], 0.5 );
905 
906 							vcm2 = face.vertexColors[ 2 ].clone();
907 							vcm2.lerpSelf( face.vertexColors[ 3 ], 0.5 );
908 
909 							quadA.vertexColors[ 1 ].copy( vcm1 );
910 							quadA.vertexColors[ 2 ].copy( vcm2 );
911 
912 							quadB.vertexColors[ 0 ].copy( vcm1 );
913 							quadB.vertexColors[ 3 ].copy( vcm2 );
914 
915 						}
916 
917 						edge = 0;
918 
919 					} else {
920 
921 						vm1 = vb.clone();
922 						vm1.lerpSelf( vc, 0.5 );
923 
924 						vm2 = vd.clone();
925 						vm2.lerpSelf( va, 0.5 );
926 
927 						quadA.a = a;
928 						quadA.b = b;
929 						quadA.c = m1;
930 						quadA.d = m2;
931 
932 						quadB.a = m2;
933 						quadB.b = m1;
934 						quadB.c = c;
935 						quadB.d = d;
936 
937 						if ( face.vertexNormals.length === 4 ) {
938 
939 							vnm1 = face.vertexNormals[ 1 ].clone();
940 							vnm1.lerpSelf( face.vertexNormals[ 2 ], 0.5 );
941 
942 							vnm2 = face.vertexNormals[ 3 ].clone();
943 							vnm2.lerpSelf( face.vertexNormals[ 0 ], 0.5 );
944 
945 							quadA.vertexNormals[ 2 ].copy( vnm1 );
946 							quadA.vertexNormals[ 3 ].copy( vnm2 );
947 
948 							quadB.vertexNormals[ 0 ].copy( vnm2 );
949 							quadB.vertexNormals[ 1 ].copy( vnm1 );
950 
951 						}
952 
953 						if ( face.vertexColors.length === 4 ) {
954 
955 							vcm1 = face.vertexColors[ 1 ].clone();
956 							vcm1.lerpSelf( face.vertexColors[ 2 ], 0.5 );
957 
958 							vcm2 = face.vertexColors[ 3 ].clone();
959 							vcm2.lerpSelf( face.vertexColors[ 0 ], 0.5 );
960 
961 							quadA.vertexColors[ 2 ].copy( vcm1 );
962 							quadA.vertexColors[ 3 ].copy( vcm2 );
963 
964 							quadB.vertexColors[ 0 ].copy( vcm2 );
965 							quadB.vertexColors[ 1 ].copy( vcm1 );
966 
967 						}
968 
969 						edge = 1;
970 
971 					}
972 
973 					faces.push( quadA, quadB );
974 					geometry.vertices.push( vm1, vm2 );
975 
976 					var j, jl, uvs, uvA, uvB, uvC, uvD, uvM1, uvM2, uvsQuadA, uvsQuadB;
977 
978 					for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
979 
980 						if ( geometry.faceVertexUvs[ j ].length ) {
981 
982 							uvs = geometry.faceVertexUvs[ j ][ i ];
983 
984 							uvA = uvs[ 0 ];
985 							uvB = uvs[ 1 ];
986 							uvC = uvs[ 2 ];
987 							uvD = uvs[ 3 ];
988 
989 							// AB + CD
990 
991 							if ( edge === 0 ) {
992 
993 								uvM1 = uvA.clone();
994 								uvM1.lerpSelf( uvB, 0.5 );
995 
996 								uvM2 = uvC.clone();
997 								uvM2.lerpSelf( uvD, 0.5 );
998 
999 								uvsQuadA = [ uvA.clone(), uvM1.clone(), uvM2.clone(), uvD.clone() ];
1000 								uvsQuadB = [ uvM1.clone(), uvB.clone(), uvC.clone(), uvM2.clone() ];
1001 
1002 							// BC + AD
1003 
1004 							} else {
1005 
1006 								uvM1 = uvB.clone();
1007 								uvM1.lerpSelf( uvC, 0.5 );
1008 
1009 								uvM2 = uvD.clone();
1010 								uvM2.lerpSelf( uvA, 0.5 );
1011 
1012 								uvsQuadA = [ uvA.clone(), uvB.clone(), uvM1.clone(), uvM2.clone() ];
1013 								uvsQuadB = [ uvM2.clone(), uvM1.clone(), uvC.clone(), uvD.clone() ];
1014 
1015 							}
1016 
1017 							faceVertexUvs[ j ].push( uvsQuadA, uvsQuadB );
1018 
1019 						}
1020 
1021 					}
1022 
1023 				} else {
1024 
1025 					faces.push( face );
1026 
1027 					for ( j = 0, jl = geometry.faceVertexUvs.length; j < jl; j ++ ) {
1028 
1029 						faceVertexUvs[ j ].push( geometry.faceVertexUvs[ j ][ i ] );
1030 
1031 					}
1032 
1033 				}
1034 
1035 			}
1036 
1037 		}
1038 
1039 		geometry.faces = faces;
1040 		geometry.faceVertexUvs = faceVertexUvs;
1041 
1042 	}
1043 
1044 };
1045 
1046 THREE.GeometryUtils.random = THREE.Math.random16;
1047 
1048 THREE.GeometryUtils.__v1 = new THREE.Vector3();
1049