( function () {

	/**
 * Utility class for sampling weighted random points on the surface of a mesh.
 *
 * Building the sampler is a one-time O(n) operation. Once built, any number of
 * random samples may be selected in O(logn) time. Memory usage is O(n).
 *
 * References:
 * - http://www.joesfer.com/?p=84
 * - https://stackoverflow.com/a/4322940/1314762
 */

	const _face = new THREE.Triangle();
	const _color = new THREE.Vector3();
	class MeshSurfaceSampler {

		constructor( mesh ) {

			let geometry = mesh.geometry;
			if ( ! geometry.isBufferGeometry || geometry.attributes.position.itemSize !== 3 ) {

				throw new Error( 'THREE.MeshSurfaceSampler: Requires BufferGeometry triangle mesh.' );

			}

			if ( geometry.index ) {

				console.warn( 'THREE.MeshSurfaceSampler: Converting geometry to non-indexed BufferGeometry.' );
				geometry = geometry.toNonIndexed();

			}

			this.geometry = geometry;
			this.randomFunction = Math.random;
			this.positionAttribute = this.geometry.getAttribute( 'position' );
			this.colorAttribute = this.geometry.getAttribute( 'color' );
			this.weightAttribute = null;
			this.distribution = null;

		}
		setWeightAttribute( name ) {

			this.weightAttribute = name ? this.geometry.getAttribute( name ) : null;
			return this;

		}
		build() {

			const positionAttribute = this.positionAttribute;
			const weightAttribute = this.weightAttribute;
			const faceWeights = new Float32Array( positionAttribute.count / 3 );

			// Accumulate weights for each mesh face.

			for ( let i = 0; i < positionAttribute.count; i += 3 ) {

				let faceWeight = 1;
				if ( weightAttribute ) {

					faceWeight = weightAttribute.getX( i ) + weightAttribute.getX( i + 1 ) + weightAttribute.getX( i + 2 );

				}

				_face.a.fromBufferAttribute( positionAttribute, i );
				_face.b.fromBufferAttribute( positionAttribute, i + 1 );
				_face.c.fromBufferAttribute( positionAttribute, i + 2 );
				faceWeight *= _face.getArea();
				faceWeights[ i / 3 ] = faceWeight;

			}

			// Store cumulative total face weights in an array, where weight index
			// corresponds to face index.

			this.distribution = new Float32Array( positionAttribute.count / 3 );
			let cumulativeTotal = 0;
			for ( let i = 0; i < faceWeights.length; i ++ ) {

				cumulativeTotal += faceWeights[ i ];
				this.distribution[ i ] = cumulativeTotal;

			}

			return this;

		}
		setRandomGenerator( randomFunction ) {

			this.randomFunction = randomFunction;
			return this;

		}
		sample( targetPosition, targetNormal, targetColor ) {

			const cumulativeTotal = this.distribution[ this.distribution.length - 1 ];
			const faceIndex = this.binarySearch( this.randomFunction() * cumulativeTotal );
			return this.sampleFace( faceIndex, targetPosition, targetNormal, targetColor );

		}
		binarySearch( x ) {

			const dist = this.distribution;
			let start = 0;
			let end = dist.length - 1;
			let index = - 1;
			while ( start <= end ) {

				const mid = Math.ceil( ( start + end ) / 2 );
				if ( mid === 0 || dist[ mid - 1 ] <= x && dist[ mid ] > x ) {

					index = mid;
					break;

				} else if ( x < dist[ mid ] ) {

					end = mid - 1;

				} else {

					start = mid + 1;

				}

			}

			return index;

		}
		sampleFace( faceIndex, targetPosition, targetNormal, targetColor ) {

			let u = this.randomFunction();
			let v = this.randomFunction();
			if ( u + v > 1 ) {

				u = 1 - u;
				v = 1 - v;

			}

			_face.a.fromBufferAttribute( this.positionAttribute, faceIndex * 3 );
			_face.b.fromBufferAttribute( this.positionAttribute, faceIndex * 3 + 1 );
			_face.c.fromBufferAttribute( this.positionAttribute, faceIndex * 3 + 2 );
			targetPosition.set( 0, 0, 0 ).addScaledVector( _face.a, u ).addScaledVector( _face.b, v ).addScaledVector( _face.c, 1 - ( u + v ) );
			if ( targetNormal !== undefined ) {

				_face.getNormal( targetNormal );

			}

			if ( targetColor !== undefined && this.colorAttribute !== undefined ) {

				_face.a.fromBufferAttribute( this.colorAttribute, faceIndex * 3 );
				_face.b.fromBufferAttribute( this.colorAttribute, faceIndex * 3 + 1 );
				_face.c.fromBufferAttribute( this.colorAttribute, faceIndex * 3 + 2 );
				_color.set( 0, 0, 0 ).addScaledVector( _face.a, u ).addScaledVector( _face.b, v ).addScaledVector( _face.c, 1 - ( u + v ) );
				targetColor.r = _color.x;
				targetColor.g = _color.y;
				targetColor.b = _color.z;

			}

			return this;

		}

	}

	THREE.MeshSurfaceSampler = MeshSurfaceSampler;

} )();