1/**
2 * @author mrdoob / http://mrdoob.com/
3 * @author supereggbert / http://www.paulbrunt.co.uk/
4 * @author julianwa / https://github.com/julianwa
5 */
6
7THREE.RenderableObject = function () {
8
9	this.id = 0;
10
11	this.object = null;
12	this.z = 0;
13	this.renderOrder = 0;
14
15};
16
17//
18
19THREE.RenderableFace = function () {
20
21	this.id = 0;
22
23	this.v1 = new THREE.RenderableVertex();
24	this.v2 = new THREE.RenderableVertex();
25	this.v3 = new THREE.RenderableVertex();
26
27	this.normalModel = new THREE.Vector3();
28
29	this.vertexNormalsModel = [ new THREE.Vector3(), new THREE.Vector3(), new THREE.Vector3() ];
30	this.vertexNormalsLength = 0;
31
32	this.color = new THREE.Color();
33	this.material = null;
34	this.uvs = [ new THREE.Vector2(), new THREE.Vector2(), new THREE.Vector2() ];
35
36	this.z = 0;
37	this.renderOrder = 0;
38
39};
40
41//
42
43THREE.RenderableVertex = function () {
44
45	this.position = new THREE.Vector3();
46	this.positionWorld = new THREE.Vector3();
47	this.positionScreen = new THREE.Vector4();
48
49	this.visible = true;
50
51};
52
53THREE.RenderableVertex.prototype.copy = function ( vertex ) {
54
55	this.positionWorld.copy( vertex.positionWorld );
56	this.positionScreen.copy( vertex.positionScreen );
57
58};
59
60//
61
62THREE.RenderableLine = function () {
63
64	this.id = 0;
65
66	this.v1 = new THREE.RenderableVertex();
67	this.v2 = new THREE.RenderableVertex();
68
69	this.vertexColors = [ new THREE.Color(), new THREE.Color() ];
70	this.material = null;
71
72	this.z = 0;
73	this.renderOrder = 0;
74
75};
76
77//
78
79THREE.RenderableSprite = function () {
80
81	this.id = 0;
82
83	this.object = null;
84
85	this.x = 0;
86	this.y = 0;
87	this.z = 0;
88
89	this.rotation = 0;
90	this.scale = new THREE.Vector2();
91
92	this.material = null;
93	this.renderOrder = 0;
94
95};
96
97//
98
99THREE.Projector = function () {
100
101	var _object, _objectCount, _objectPool = [], _objectPoolLength = 0,
102		_vertex, _vertexCount, _vertexPool = [], _vertexPoolLength = 0,
103		_face, _faceCount, _facePool = [], _facePoolLength = 0,
104		_line, _lineCount, _linePool = [], _linePoolLength = 0,
105		_sprite, _spriteCount, _spritePool = [], _spritePoolLength = 0,
106
107		_renderData = { objects: [], lights: [], elements: [] },
108
109		_vector3 = new THREE.Vector3(),
110		_vector4 = new THREE.Vector4(),
111
112		_clipBox = new THREE.Box3( new THREE.Vector3( - 1, - 1, - 1 ), new THREE.Vector3( 1, 1, 1 ) ),
113		_boundingBox = new THREE.Box3(),
114		_points3 = new Array( 3 ),
115
116		_viewMatrix = new THREE.Matrix4(),
117		_viewProjectionMatrix = new THREE.Matrix4(),
118
119		_modelMatrix,
120		_modelViewProjectionMatrix = new THREE.Matrix4(),
121
122		_normalMatrix = new THREE.Matrix3(),
123
124		_frustum = new THREE.Frustum(),
125
126		_clippedVertex1PositionScreen = new THREE.Vector4(),
127		_clippedVertex2PositionScreen = new THREE.Vector4();
128
129	//
130
131	this.projectVector = function ( vector, camera ) {
132
133		console.warn( 'THREE.Projector: .projectVector() is now vector.project().' );
134		vector.project( camera );
135
136	};
137
138	this.unprojectVector = function ( vector, camera ) {
139
140		console.warn( 'THREE.Projector: .unprojectVector() is now vector.unproject().' );
141		vector.unproject( camera );
142
143	};
144
145	this.pickingRay = function () {
146
147		console.error( 'THREE.Projector: .pickingRay() is now raycaster.setFromCamera().' );
148
149	};
150
151	//
152
153	var RenderList = function () {
154
155		var normals = [];
156		var colors = [];
157		var uvs = [];
158
159		var object = null;
160		var material = null;
161
162		var normalMatrix = new THREE.Matrix3();
163
164		function setObject( value ) {
165
166			object = value;
167			material = object.material;
168
169			normalMatrix.getNormalMatrix( object.matrixWorld );
170
171			normals.length = 0;
172			colors.length = 0;
173			uvs.length = 0;
174
175		}
176
177		function projectVertex( vertex ) {
178
179			var position = vertex.position;
180			var positionWorld = vertex.positionWorld;
181			var positionScreen = vertex.positionScreen;
182
183			positionWorld.copy( position ).applyMatrix4( _modelMatrix );
184			positionScreen.copy( positionWorld ).applyMatrix4( _viewProjectionMatrix );
185
186			var invW = 1 / positionScreen.w;
187
188			positionScreen.x *= invW;
189			positionScreen.y *= invW;
190			positionScreen.z *= invW;
191
192			vertex.visible = positionScreen.x >= - 1 && positionScreen.x <= 1 &&
193					 positionScreen.y >= - 1 && positionScreen.y <= 1 &&
194					 positionScreen.z >= - 1 && positionScreen.z <= 1;
195
196		}
197
198		function pushVertex( x, y, z ) {
199
200			_vertex = getNextVertexInPool();
201			_vertex.position.set( x, y, z );
202
203			projectVertex( _vertex );
204
205		}
206
207		function pushNormal( x, y, z ) {
208
209			normals.push( x, y, z );
210
211		}
212
213		function pushColor( r, g, b ) {
214
215			colors.push( r, g, b );
216
217		}
218
219		function pushUv( x, y ) {
220
221			uvs.push( x, y );
222
223		}
224
225		function checkTriangleVisibility( v1, v2, v3 ) {
226
227			if ( v1.visible === true || v2.visible === true || v3.visible === true ) return true;
228
229			_points3[ 0 ] = v1.positionScreen;
230			_points3[ 1 ] = v2.positionScreen;
231			_points3[ 2 ] = v3.positionScreen;
232
233			return _clipBox.intersectsBox( _boundingBox.setFromPoints( _points3 ) );
234
235		}
236
237		function checkBackfaceCulling( v1, v2, v3 ) {
238
239			return ( ( v3.positionScreen.x - v1.positionScreen.x ) *
240				    ( v2.positionScreen.y - v1.positionScreen.y ) -
241				    ( v3.positionScreen.y - v1.positionScreen.y ) *
242				    ( v2.positionScreen.x - v1.positionScreen.x ) ) < 0;
243
244		}
245
246		function pushLine( a, b ) {
247
248			var v1 = _vertexPool[ a ];
249			var v2 = _vertexPool[ b ];
250
251			// Clip
252
253			v1.positionScreen.copy( v1.position ).applyMatrix4( _modelViewProjectionMatrix );
254			v2.positionScreen.copy( v2.position ).applyMatrix4( _modelViewProjectionMatrix );
255
256			if ( clipLine( v1.positionScreen, v2.positionScreen ) === true ) {
257
258				// Perform the perspective divide
259				v1.positionScreen.multiplyScalar( 1 / v1.positionScreen.w );
260				v2.positionScreen.multiplyScalar( 1 / v2.positionScreen.w );
261
262				_line = getNextLineInPool();
263				_line.id = object.id;
264				_line.v1.copy( v1 );
265				_line.v2.copy( v2 );
266				_line.z = Math.max( v1.positionScreen.z, v2.positionScreen.z );
267				_line.renderOrder = object.renderOrder;
268
269				_line.material = object.material;
270
271				if ( object.material.vertexColors === THREE.VertexColors ) {
272
273					_line.vertexColors[ 0 ].fromArray( colors, a * 3 );
274					_line.vertexColors[ 1 ].fromArray( colors, b * 3 );
275
276				}
277
278				_renderData.elements.push( _line );
279
280			}
281
282		}
283
284		function pushTriangle( a, b, c ) {
285
286			var v1 = _vertexPool[ a ];
287			var v2 = _vertexPool[ b ];
288			var v3 = _vertexPool[ c ];
289
290			if ( checkTriangleVisibility( v1, v2, v3 ) === false ) return;
291
292			if ( material.side === THREE.DoubleSide || checkBackfaceCulling( v1, v2, v3 ) === true ) {
293
294				_face = getNextFaceInPool();
295
296				_face.id = object.id;
297				_face.v1.copy( v1 );
298				_face.v2.copy( v2 );
299				_face.v3.copy( v3 );
300				_face.z = ( v1.positionScreen.z + v2.positionScreen.z + v3.positionScreen.z ) / 3;
301				_face.renderOrder = object.renderOrder;
302
303				// use first vertex normal as face normal
304
305				_face.normalModel.fromArray( normals, a * 3 );
306				_face.normalModel.applyMatrix3( normalMatrix ).normalize();
307
308				for ( var i = 0; i < 3; i ++ ) {
309
310					var normal = _face.vertexNormalsModel[ i ];
311					normal.fromArray( normals, arguments[ i ] * 3 );
312					normal.applyMatrix3( normalMatrix ).normalize();
313
314					var uv = _face.uvs[ i ];
315					uv.fromArray( uvs, arguments[ i ] * 2 );
316
317				}
318
319				_face.vertexNormalsLength = 3;
320
321				_face.material = object.material;
322
323				_renderData.elements.push( _face );
324
325			}
326
327		}
328
329		return {
330			setObject: setObject,
331			projectVertex: projectVertex,
332			checkTriangleVisibility: checkTriangleVisibility,
333			checkBackfaceCulling: checkBackfaceCulling,
334			pushVertex: pushVertex,
335			pushNormal: pushNormal,
336			pushColor: pushColor,
337			pushUv: pushUv,
338			pushLine: pushLine,
339			pushTriangle: pushTriangle
340		};
341
342	};
343
344	var renderList = new RenderList();
345
346	function projectObject( object ) {
347
348		if ( object.visible === false ) return;
349
350		if ( object instanceof THREE.Light ) {
351
352			_renderData.lights.push( object );
353
354		} else if ( object instanceof THREE.Mesh || object instanceof THREE.Line || object instanceof THREE.Points ) {
355
356			if ( object.material.visible === false ) return;
357			if ( object.frustumCulled === true && _frustum.intersectsObject( object ) === false ) return;
358
359			addObject( object );
360
361		} else if ( object instanceof THREE.Sprite ) {
362
363			if ( object.material.visible === false ) return;
364			if ( object.frustumCulled === true && _frustum.intersectsSprite( object ) === false ) return;
365
366			addObject( object );
367
368		}
369
370		var children = object.children;
371
372		for ( var i = 0, l = children.length; i < l; i ++ ) {
373
374			projectObject( children[ i ] );
375
376		}
377
378	}
379
380	function addObject( object ) {
381
382		_object = getNextObjectInPool();
383		_object.id = object.id;
384		_object.object = object;
385
386		_vector3.setFromMatrixPosition( object.matrixWorld );
387		_vector3.applyMatrix4( _viewProjectionMatrix );
388		_object.z = _vector3.z;
389		_object.renderOrder = object.renderOrder;
390
391		_renderData.objects.push( _object );
392
393	}
394
395	this.projectScene = function ( scene, camera, sortObjects, sortElements ) {
396
397		_faceCount = 0;
398		_lineCount = 0;
399		_spriteCount = 0;
400
401		_renderData.elements.length = 0;
402
403		if ( scene.autoUpdate === true ) scene.updateMatrixWorld();
404		if ( camera.parent === null ) camera.updateMatrixWorld();
405
406		_viewMatrix.copy( camera.matrixWorldInverse );
407		_viewProjectionMatrix.multiplyMatrices( camera.projectionMatrix, _viewMatrix );
408
409		_frustum.setFromMatrix( _viewProjectionMatrix );
410
411		//
412
413		_objectCount = 0;
414
415		_renderData.objects.length = 0;
416		_renderData.lights.length = 0;
417
418		projectObject( scene );
419
420		if ( sortObjects === true ) {
421
422			_renderData.objects.sort( painterSort );
423
424		}
425
426		//
427
428		var objects = _renderData.objects;
429
430		for ( var o = 0, ol = objects.length; o < ol; o ++ ) {
431
432			var object = objects[ o ].object;
433			var geometry = object.geometry;
434
435			renderList.setObject( object );
436
437			_modelMatrix = object.matrixWorld;
438
439			_vertexCount = 0;
440
441			if ( object instanceof THREE.Mesh ) {
442
443				if ( geometry instanceof THREE.BufferGeometry ) {
444
445					var attributes = geometry.attributes;
446					var groups = geometry.groups;
447
448					if ( attributes.position === undefined ) continue;
449
450					var positions = attributes.position.array;
451
452					for ( var i = 0, l = positions.length; i < l; i += 3 ) {
453
454						renderList.pushVertex( positions[ i ], positions[ i + 1 ], positions[ i + 2 ] );
455
456					}
457
458					if ( attributes.normal !== undefined ) {
459
460						var normals = attributes.normal.array;
461
462						for ( var i = 0, l = normals.length; i < l; i += 3 ) {
463
464							renderList.pushNormal( normals[ i ], normals[ i + 1 ], normals[ i + 2 ] );
465
466						}
467
468					}
469
470					if ( attributes.uv !== undefined ) {
471
472						var uvs = attributes.uv.array;
473
474						for ( var i = 0, l = uvs.length; i < l; i += 2 ) {
475
476							renderList.pushUv( uvs[ i ], uvs[ i + 1 ] );
477
478						}
479
480					}
481
482					if ( geometry.index !== null ) {
483
484						var indices = geometry.index.array;
485
486						if ( groups.length > 0 ) {
487
488							for ( var g = 0; g < groups.length; g ++ ) {
489
490								var group = groups[ g ];
491
492								for ( var i = group.start, l = group.start + group.count; i < l; i += 3 ) {
493
494									renderList.pushTriangle( indices[ i ], indices[ i + 1 ], indices[ i + 2 ] );
495
496								}
497
498							}
499
500						} else {
501
502							for ( var i = 0, l = indices.length; i < l; i += 3 ) {
503
504								renderList.pushTriangle( indices[ i ], indices[ i + 1 ], indices[ i + 2 ] );
505
506							}
507
508						}
509
510					} else {
511
512						for ( var i = 0, l = positions.length / 3; i < l; i += 3 ) {
513
514							renderList.pushTriangle( i, i + 1, i + 2 );
515
516						}
517
518					}
519
520				} else if ( geometry instanceof THREE.Geometry ) {
521
522					var vertices = geometry.vertices;
523					var faces = geometry.faces;
524					var faceVertexUvs = geometry.faceVertexUvs[ 0 ];
525
526					_normalMatrix.getNormalMatrix( _modelMatrix );
527
528					var material = object.material;
529
530					var isMultiMaterial = Array.isArray( material );
531
532					for ( var v = 0, vl = vertices.length; v < vl; v ++ ) {
533
534						var vertex = vertices[ v ];
535
536						_vector3.copy( vertex );
537
538						if ( material.morphTargets === true ) {
539
540							var morphTargets = geometry.morphTargets;
541							var morphInfluences = object.morphTargetInfluences;
542
543							for ( var t = 0, tl = morphTargets.length; t < tl; t ++ ) {
544
545								var influence = morphInfluences[ t ];
546
547								if ( influence === 0 ) continue;
548
549								var target = morphTargets[ t ];
550								var targetVertex = target.vertices[ v ];
551
552								_vector3.x += ( targetVertex.x - vertex.x ) * influence;
553								_vector3.y += ( targetVertex.y - vertex.y ) * influence;
554								_vector3.z += ( targetVertex.z - vertex.z ) * influence;
555
556							}
557
558						}
559
560						renderList.pushVertex( _vector3.x, _vector3.y, _vector3.z );
561
562					}
563
564					for ( var f = 0, fl = faces.length; f < fl; f ++ ) {
565
566						var face = faces[ f ];
567
568						material = isMultiMaterial === true
569							 ? object.material[ face.materialIndex ]
570							 : object.material;
571
572						if ( material === undefined ) continue;
573
574						var side = material.side;
575
576						var v1 = _vertexPool[ face.a ];
577						var v2 = _vertexPool[ face.b ];
578						var v3 = _vertexPool[ face.c ];
579
580						if ( renderList.checkTriangleVisibility( v1, v2, v3 ) === false ) continue;
581
582						var visible = renderList.checkBackfaceCulling( v1, v2, v3 );
583
584						if ( side !== THREE.DoubleSide ) {
585
586							if ( side === THREE.FrontSide && visible === false ) continue;
587							if ( side === THREE.BackSide && visible === true ) continue;
588
589						}
590
591						_face = getNextFaceInPool();
592
593						_face.id = object.id;
594						_face.v1.copy( v1 );
595						_face.v2.copy( v2 );
596						_face.v3.copy( v3 );
597
598						_face.normalModel.copy( face.normal );
599
600						if ( visible === false && ( side === THREE.BackSide || side === THREE.DoubleSide ) ) {
601
602							_face.normalModel.negate();
603
604						}
605
606						_face.normalModel.applyMatrix3( _normalMatrix ).normalize();
607
608						var faceVertexNormals = face.vertexNormals;
609
610						for ( var n = 0, nl = Math.min( faceVertexNormals.length, 3 ); n < nl; n ++ ) {
611
612							var normalModel = _face.vertexNormalsModel[ n ];
613							normalModel.copy( faceVertexNormals[ n ] );
614
615							if ( visible === false && ( side === THREE.BackSide || side === THREE.DoubleSide ) ) {
616
617								normalModel.negate();
618
619							}
620
621							normalModel.applyMatrix3( _normalMatrix ).normalize();
622
623						}
624
625						_face.vertexNormalsLength = faceVertexNormals.length;
626
627						var vertexUvs = faceVertexUvs[ f ];
628
629						if ( vertexUvs !== undefined ) {
630
631							for ( var u = 0; u < 3; u ++ ) {
632
633								_face.uvs[ u ].copy( vertexUvs[ u ] );
634
635							}
636
637						}
638
639						_face.color = face.color;
640						_face.material = material;
641
642						_face.z = ( v1.positionScreen.z + v2.positionScreen.z + v3.positionScreen.z ) / 3;
643						_face.renderOrder = object.renderOrder;
644
645						_renderData.elements.push( _face );
646
647					}
648
649				}
650
651			} else if ( object instanceof THREE.Line ) {
652
653				_modelViewProjectionMatrix.multiplyMatrices( _viewProjectionMatrix, _modelMatrix );
654
655				if ( geometry instanceof THREE.BufferGeometry ) {
656
657					var attributes = geometry.attributes;
658
659					if ( attributes.position !== undefined ) {
660
661						var positions = attributes.position.array;
662
663						for ( var i = 0, l = positions.length; i < l; i += 3 ) {
664
665							renderList.pushVertex( positions[ i ], positions[ i + 1 ], positions[ i + 2 ] );
666
667						}
668
669						if ( attributes.color !== undefined ) {
670
671							var colors = attributes.color.array;
672
673							for ( var i = 0, l = colors.length; i < l; i += 3 ) {
674
675								renderList.pushColor( colors[ i ], colors[ i + 1 ], colors[ i + 2 ] );
676
677							}
678
679						}
680
681						if ( geometry.index !== null ) {
682
683							var indices = geometry.index.array;
684
685							for ( var i = 0, l = indices.length; i < l; i += 2 ) {
686
687								renderList.pushLine( indices[ i ], indices[ i + 1 ] );
688
689							}
690
691						} else {
692
693							var step = object instanceof THREE.LineSegments ? 2 : 1;
694
695							for ( var i = 0, l = ( positions.length / 3 ) - 1; i < l; i += step ) {
696
697								renderList.pushLine( i, i + 1 );
698
699							}
700
701						}
702
703					}
704
705				} else if ( geometry instanceof THREE.Geometry ) {
706
707					var vertices = object.geometry.vertices;
708
709					if ( vertices.length === 0 ) continue;
710
711					v1 = getNextVertexInPool();
712					v1.positionScreen.copy( vertices[ 0 ] ).applyMatrix4( _modelViewProjectionMatrix );
713
714					var step = object instanceof THREE.LineSegments ? 2 : 1;
715
716					for ( var v = 1, vl = vertices.length; v < vl; v ++ ) {
717
718						v1 = getNextVertexInPool();
719						v1.positionScreen.copy( vertices[ v ] ).applyMatrix4( _modelViewProjectionMatrix );
720
721						if ( ( v + 1 ) % step > 0 ) continue;
722
723						v2 = _vertexPool[ _vertexCount - 2 ];
724
725						_clippedVertex1PositionScreen.copy( v1.positionScreen );
726						_clippedVertex2PositionScreen.copy( v2.positionScreen );
727
728						if ( clipLine( _clippedVertex1PositionScreen, _clippedVertex2PositionScreen ) === true ) {
729
730							// Perform the perspective divide
731							_clippedVertex1PositionScreen.multiplyScalar( 1 / _clippedVertex1PositionScreen.w );
732							_clippedVertex2PositionScreen.multiplyScalar( 1 / _clippedVertex2PositionScreen.w );
733
734							_line = getNextLineInPool();
735
736							_line.id = object.id;
737							_line.v1.positionScreen.copy( _clippedVertex1PositionScreen );
738							_line.v2.positionScreen.copy( _clippedVertex2PositionScreen );
739
740							_line.z = Math.max( _clippedVertex1PositionScreen.z, _clippedVertex2PositionScreen.z );
741							_line.renderOrder = object.renderOrder;
742
743							_line.material = object.material;
744
745							if ( object.material.vertexColors === THREE.VertexColors ) {
746
747								_line.vertexColors[ 0 ].copy( object.geometry.colors[ v ] );
748								_line.vertexColors[ 1 ].copy( object.geometry.colors[ v - 1 ] );
749
750							}
751
752							_renderData.elements.push( _line );
753
754						}
755
756					}
757
758				}
759
760			} else if ( object instanceof THREE.Points ) {
761
762				_modelViewProjectionMatrix.multiplyMatrices( _viewProjectionMatrix, _modelMatrix );
763
764				if ( geometry instanceof THREE.Geometry ) {
765
766					var vertices = object.geometry.vertices;
767
768					for ( var v = 0, vl = vertices.length; v < vl; v ++ ) {
769
770						var vertex = vertices[ v ];
771
772						_vector4.set( vertex.x, vertex.y, vertex.z, 1 );
773						_vector4.applyMatrix4( _modelViewProjectionMatrix );
774
775						pushPoint( _vector4, object, camera );
776
777					}
778
779				} else if ( geometry instanceof THREE.BufferGeometry ) {
780
781					var attributes = geometry.attributes;
782
783					if ( attributes.position !== undefined ) {
784
785						var positions = attributes.position.array;
786
787						for ( var i = 0, l = positions.length; i < l; i += 3 ) {
788
789							_vector4.set( positions[ i ], positions[ i + 1 ], positions[ i + 2 ], 1 );
790							_vector4.applyMatrix4( _modelViewProjectionMatrix );
791
792							pushPoint( _vector4, object, camera );
793
794						}
795
796					}
797
798				}
799
800			} else if ( object instanceof THREE.Sprite ) {
801
802				_vector4.set( _modelMatrix.elements[ 12 ], _modelMatrix.elements[ 13 ], _modelMatrix.elements[ 14 ], 1 );
803				_vector4.applyMatrix4( _viewProjectionMatrix );
804
805				pushPoint( _vector4, object, camera );
806
807			}
808
809		}
810
811		if ( sortElements === true ) {
812
813			_renderData.elements.sort( painterSort );
814
815		}
816
817		return _renderData;
818
819	};
820
821	function pushPoint( _vector4, object, camera ) {
822
823		var invW = 1 / _vector4.w;
824
825		_vector4.z *= invW;
826
827		if ( _vector4.z >= - 1 && _vector4.z <= 1 ) {
828
829			_sprite = getNextSpriteInPool();
830			_sprite.id = object.id;
831			_sprite.x = _vector4.x * invW;
832			_sprite.y = _vector4.y * invW;
833			_sprite.z = _vector4.z;
834			_sprite.renderOrder = object.renderOrder;
835			_sprite.object = object;
836
837			_sprite.rotation = object.rotation;
838
839			_sprite.scale.x = object.scale.x * Math.abs( _sprite.x - ( _vector4.x + camera.projectionMatrix.elements[ 0 ] ) / ( _vector4.w + camera.projectionMatrix.elements[ 12 ] ) );
840			_sprite.scale.y = object.scale.y * Math.abs( _sprite.y - ( _vector4.y + camera.projectionMatrix.elements[ 5 ] ) / ( _vector4.w + camera.projectionMatrix.elements[ 13 ] ) );
841
842			_sprite.material = object.material;
843
844			_renderData.elements.push( _sprite );
845
846		}
847
848	}
849
850	// Pools
851
852	function getNextObjectInPool() {
853
854		if ( _objectCount === _objectPoolLength ) {
855
856			var object = new THREE.RenderableObject();
857			_objectPool.push( object );
858			_objectPoolLength ++;
859			_objectCount ++;
860			return object;
861
862		}
863
864		return _objectPool[ _objectCount ++ ];
865
866	}
867
868	function getNextVertexInPool() {
869
870		if ( _vertexCount === _vertexPoolLength ) {
871
872			var vertex = new THREE.RenderableVertex();
873			_vertexPool.push( vertex );
874			_vertexPoolLength ++;
875			_vertexCount ++;
876			return vertex;
877
878		}
879
880		return _vertexPool[ _vertexCount ++ ];
881
882	}
883
884	function getNextFaceInPool() {
885
886		if ( _faceCount === _facePoolLength ) {
887
888			var face = new THREE.RenderableFace();
889			_facePool.push( face );
890			_facePoolLength ++;
891			_faceCount ++;
892			return face;
893
894		}
895
896		return _facePool[ _faceCount ++ ];
897
898
899	}
900
901	function getNextLineInPool() {
902
903		if ( _lineCount === _linePoolLength ) {
904
905			var line = new THREE.RenderableLine();
906			_linePool.push( line );
907			_linePoolLength ++;
908			_lineCount ++;
909			return line;
910
911		}
912
913		return _linePool[ _lineCount ++ ];
914
915	}
916
917	function getNextSpriteInPool() {
918
919		if ( _spriteCount === _spritePoolLength ) {
920
921			var sprite = new THREE.RenderableSprite();
922			_spritePool.push( sprite );
923			_spritePoolLength ++;
924			_spriteCount ++;
925			return sprite;
926
927		}
928
929		return _spritePool[ _spriteCount ++ ];
930
931	}
932
933	//
934
935	function painterSort( a, b ) {
936
937		if ( a.renderOrder !== b.renderOrder ) {
938
939			return a.renderOrder - b.renderOrder;
940
941		} else if ( a.z !== b.z ) {
942
943			return b.z - a.z;
944
945		} else if ( a.id !== b.id ) {
946
947			return a.id - b.id;
948
949		} else {
950
951			return 0;
952
953		}
954
955	}
956
957	function clipLine( s1, s2 ) {
958
959		var alpha1 = 0, alpha2 = 1,
960
961		// Calculate the boundary coordinate of each vertex for the near and far clip planes,
962		// Z = -1 and Z = +1, respectively.
963
964			bc1near = s1.z + s1.w,
965			bc2near = s2.z + s2.w,
966			bc1far = - s1.z + s1.w,
967			bc2far = - s2.z + s2.w;
968
969		if ( bc1near >= 0 && bc2near >= 0 && bc1far >= 0 && bc2far >= 0 ) {
970
971			// Both vertices lie entirely within all clip planes.
972			return true;
973
974		} else if ( ( bc1near < 0 && bc2near < 0 ) || ( bc1far < 0 && bc2far < 0 ) ) {
975
976			// Both vertices lie entirely outside one of the clip planes.
977			return false;
978
979		} else {
980
981			// The line segment spans at least one clip plane.
982
983			if ( bc1near < 0 ) {
984
985				// v1 lies outside the near plane, v2 inside
986				alpha1 = Math.max( alpha1, bc1near / ( bc1near - bc2near ) );
987
988			} else if ( bc2near < 0 ) {
989
990				// v2 lies outside the near plane, v1 inside
991				alpha2 = Math.min( alpha2, bc1near / ( bc1near - bc2near ) );
992
993			}
994
995			if ( bc1far < 0 ) {
996
997				// v1 lies outside the far plane, v2 inside
998				alpha1 = Math.max( alpha1, bc1far / ( bc1far - bc2far ) );
999
1000			} else if ( bc2far < 0 ) {
1001
1002				// v2 lies outside the far plane, v2 inside
1003				alpha2 = Math.min( alpha2, bc1far / ( bc1far - bc2far ) );
1004
1005			}
1006
1007			if ( alpha2 < alpha1 ) {
1008
1009				// The line segment spans two boundaries, but is outside both of them.
1010				// (This can't happen when we're only clipping against just near/far but good
1011				//  to leave the check here for future usage if other clip planes are added.)
1012				return false;
1013
1014			} else {
1015
1016				// Update the s1 and s2 vertices to match the clipped line segment.
1017				s1.lerp( s2, alpha1 );
1018				s2.lerp( s1, 1 - alpha2 );
1019
1020				return true;
1021
1022			}
1023
1024		}
1025
1026	}
1027
1028};