Skip to content
1        10        20        30        40        50        60        70        80        90        100       110       120       130       140       150       160       170       180       190       200       210       220       230       2401import {2	BufferAttribute,3	BufferGeometry,4	Float32BufferAttribute,5	InstancedBufferAttribute,6	InterleavedBuffer,7	InterleavedBufferAttribute,8	MathUtils,9	TriangleFanDrawMode,10	TriangleStripDrawMode,11	TrianglesDrawMode,12	Vector3,13} from 'three';1415/**16 * @module BufferGeometryUtils17 * @three_import import * as BufferGeometryUtils from 'three/addons/utils/BufferGeometryUtils.js';18 */1920/**21 * Computes vertex tangents using the MikkTSpace algorithm. MikkTSpace generates the same tangents consistently,22 * and is used in most modelling tools and normal map bakers. Use MikkTSpace for materials with normal maps,23 * because inconsistent tangents may lead to subtle visual issues in the normal map, particularly around mirrored24 * UV seams.25 *26 * In comparison to this method, {@link BufferGeometry#computeTangents} (a custom algorithm) generates tangents that27 * probably will not match the tangents in other software. The custom algorithm is sufficient for general use with a28 * custom material, and may be faster than MikkTSpace.29 *30 * Returns the original BufferGeometry. Indexed geometries will be de-indexed. Requires position, normal, and uv attributes.31 * Tangents are stored like the normals: normalized Int8 or Int16 when the normals are, Float32 otherwise.32 *33 * @param {BufferGeometry} geometry - The geometry to compute tangents for.34 * @param {Object} MikkTSpace - Instance of `examples/jsm/libs/mikktspace.module.js`, or `mikktspace` npm package.35 * The bundled JavaScript implementation is ready immediately. Await `MikkTSpace.ready` before using a WebAssembly implementation.36 * @param {boolean} [negateSign=true] - Whether to negate the sign component (.w) of each tangent.37 * Required for normal map conventions in some formats, including glTF.38 * @return {BufferGeometry} The updated geometry.39 */40function computeMikkTSpaceTangents( geometry, MikkTSpace, negateSign = true ) {4142	if ( ! MikkTSpace || ! MikkTSpace.isReady ) {4344		throw new Error( 'THREE.BufferGeometryUtils: Initialized MikkTSpace library required.' );4546	}4748	if ( ! geometry.hasAttribute( 'position' ) || ! geometry.hasAttribute( 'normal' ) || ! geometry.hasAttribute( 'uv' ) ) {4950		throw new Error( 'THREE.BufferGeometryUtils: Tangents require "position", "normal", and "uv" attributes.' );5152	}5354	function getAttributeArray( attribute ) {5556		if ( attribute.normalized || attribute.isInterleavedBufferAttribute ) {5758			const dstArray = new Float32Array( attribute.count * attribute.itemSize );5960			for ( let i = 0, j = 0; i < attribute.count; i ++ ) {6162				dstArray[ j ++ ] = attribute.getX( i );63				dstArray[ j ++ ] = attribute.getY( i );6465				if ( attribute.itemSize > 2 ) {6667					dstArray[ j ++ ] = attribute.getZ( i );6869				}7071			}7273			return dstArray;7475		}7677		if ( attribute.array instanceof Float32Array ) {7879			return attribute.array;8081		}8283		return new Float32Array( attribute.array );8485	}8687	// MikkTSpace algorithm requires non-indexed input.8889	const _geometry = geometry.index ? geometry.toNonIndexed() : geometry;9091	// Compute vertex tangents.9293	const tangents = MikkTSpace.generateTangents(9495		getAttributeArray( _geometry.attributes.position ),96		getAttributeArray( _geometry.attributes.normal ),97		getAttributeArray( _geometry.attributes.uv )9899	);100101	// Texture coordinate convention of glTF differs from the apparent102	// default of the MikkTSpace library; .w component must be flipped.103104	if ( negateSign ) {105106		for ( let i = 3; i < tangents.length; i += 4 ) {107108			tangents[ i ] *= - 1;109110		}111112	}113114	//115116	// Quantized normals get tangents of the same precision.117118	const normal = _geometry.attributes.normal;119	const normalArray = normal.array;120121	if ( normal.normalized && ( normalArray instanceof Int8Array || normalArray instanceof Int16Array ) ) {122123		const quantized = new normalArray.constructor( tangents.length );124125		for ( let i = 0; i < tangents.length; i ++ ) {126127			quantized[ i ] = MathUtils.normalize( tangents[ i ], quantized );128129		}130131		_geometry.setAttribute( 'tangent', new BufferAttribute( quantized, 4, true ) );132133	} else {134135		_geometry.setAttribute( 'tangent', new BufferAttribute( tangents, 4 ) );136137	}138139	if ( geometry !== _geometry ) {140141		geometry.copy( _geometry );142143	}144145	return geometry;146147}148149/**150 * Merges a set of geometries into a single instance. All geometries must have compatible attributes.151 *152 * @param {Array<BufferGeometry>} geometries - The geometries to merge.153 * @param {boolean} [useGroups=false] - Whether to use groups or not.154 * @return {?BufferGeometry} The merged geometry. Returns `null` if the merge does not succeed.155 */156function mergeGeometries( geometries, useGroups = false ) {157158	const isIndexed = geometries[ 0 ].index !== null;159160	const attributesUsed = new Set( Object.keys( geometries[ 0 ].attributes ) );161	const morphAttributesUsed = new Set( Object.keys( geometries[ 0 ].morphAttributes ) );162163	const attributes = {};164	const morphAttributes = {};165166	const morphTargetsRelative = geometries[ 0 ].morphTargetsRelative;167168	const mergedGeometry = new BufferGeometry();169	mergedGeometry.morphTargetsRelative = morphTargetsRelative;170171	let offset = 0;172173	for ( let i = 0; i < geometries.length; ++ i ) {174175		const geometry = geometries[ i ];176		let attributesCount = 0;177		let morphAttributesCount = 0;178179		// ensure that all geometries are indexed, or none180181		if ( isIndexed !== ( geometry.index !== null ) ) {182183			console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. All geometries must have compatible attributes; make sure index attribute exists among all geometries, or in none of them.' );184			return null;185186		}187188		// gather attributes, exit early if they're different189190		for ( const name in geometry.attributes ) {191192			if ( ! attributesUsed.has( name ) ) {193194				console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. All geometries must have compatible attributes; make sure "' + name + '" attribute exists among all geometries, or in none of them.' );195				return null;196197			}198199			if ( attributes[ name ] === undefined ) attributes[ name ] = [];200201			attributes[ name ].push( geometry.attributes[ name ] );202203			attributesCount ++;204205		}206207		// ensure geometries have the same number of attributes208209		if ( attributesCount !== attributesUsed.size ) {210211			console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. Make sure all geometries have the same number of attributes.' );212			return null;213214		}215216		// gather morph attributes, exit early if they're different217218		if ( morphTargetsRelative !== geometry.morphTargetsRelative ) {219220			console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. .morphTargetsRelative must be consistent throughout all geometries.' );221			return null;222223		}224225		for ( const name in geometry.morphAttributes ) {226227			if ( ! morphAttributesUsed.has( name ) ) {228229				console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '.  .morphAttributes must be consistent throughout all geometries.' );230				return null;231232			}233234			if ( geometry.morphAttributes[ name ].length !== geometries[ 0 ].morphAttributes[ name ].length ) {235236				console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. All geometries must have the same number of morph targets for the "' + name + '" morph attribute.' );237				return null;238239			}240241			if ( morphAttributes[ name ] === undefined ) morphAttributes[ name ] = [];242243			morphAttributes[ name ].push( geometry.morphAttributes[ name ] );244245			morphAttributesCount ++;246247		}248249		// ensure geometries have the same number of morph attributes250251		if ( morphAttributesCount !== morphAttributesUsed.size ) {252253			console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. Make sure all geometries have the same number of morph attributes.' );254			return null;255256		}257258		if ( useGroups ) {259260			let count;261262			if ( isIndexed ) {263264				count = geometry.index.count;265266			} else if ( geometry.attributes.position !== undefined ) {267268				count = geometry.attributes.position.count;269270			} else {271272				console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' + i + '. The geometry must have either an index or a position attribute' );273				return null;274275			}276277			mergedGeometry.addGroup( offset, count, i );278279			offset += count;280281		}282283	}284285	// merge indices286287	if ( isIndexed ) {288289		let indexOffset = 0;290		const mergedIndex = [];291292		for ( let i = 0; i < geometries.length; ++ i ) {293294			const index = geometries[ i ].index;295296			for ( let j = 0; j < index.count; ++ j ) {297298				mergedIndex.push( index.getX( j ) + indexOffset );299300			}301302			indexOffset += geometries[ i ].attributes.position.count;303304		}305306		mergedGeometry.setIndex( mergedIndex );307308	}309310	// merge attributes311312	for ( const name in attributes ) {313314		const mergedAttribute = mergeAttributes( attributes[ name ] );315316		if ( ! mergedAttribute ) {317318			console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed while trying to merge the ' + name + ' attribute.' );319			return null;320321		}322323		mergedGeometry.setAttribute( name, mergedAttribute );324325	}326327	// merge morph attributes328329	for ( const name in morphAttributes ) {330331		const numMorphTargets = morphAttributes[ name ][ 0 ].length;332		if ( numMorphTargets === 0 ) continue;333334		mergedGeometry.morphAttributes = mergedGeometry.morphAttributes || {};335		mergedGeometry.morphAttributes[ name ] = [];336337		for ( let i = 0; i < numMorphTargets; ++ i ) {338339			const morphAttributesToMerge = [];340341			for ( let j = 0; j < morphAttributes[ name ].length; ++ j ) {342343				morphAttributesToMerge.push( morphAttributes[ name ][ j ][ i ] );344345			}346347			const mergedMorphAttribute = mergeAttributes( morphAttributesToMerge );348349			if ( ! mergedMorphAttribute ) {350351				console.error( 'THREE.BufferGeometryUtils: .mergeGeometries() failed while trying to merge the ' + name + ' morphAttribute.' );352				return null;353354			}355356			mergedGeometry.morphAttributes[ name ].push( mergedMorphAttribute );357358		}359360	}361362	return mergedGeometry;363364}365366/**367 * Merges a set of attributes into a single instance. All attributes must have compatible properties and types.368 * Instances of {@link InterleavedBufferAttribute} are not supported.369 *370 * @param {Array<BufferAttribute>} attributes - The attributes to merge.371 * @return {?BufferAttribute} The merged attribute. Returns `null` if the merge does not succeed.372 */373function mergeAttributes( attributes ) {374375	let TypedArray;376	let itemSize;377	let normalized;378	let gpuType = - 1;379	let arrayLength = 0;380381	for ( let i = 0; i < attributes.length; ++ i ) {382383		const attribute = attributes[ i ];384385		if ( TypedArray === undefined ) TypedArray = attribute.array.constructor;386		if ( TypedArray !== attribute.array.constructor ) {387388			console.error( 'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.array must be of consistent array types across matching attributes.' );389			return null;390391		}392393		if ( itemSize === undefined ) itemSize = attribute.itemSize;394		if ( itemSize !== attribute.itemSize ) {395396			console.error( 'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.itemSize must be consistent across matching attributes.' );397			return null;398399		}400401		if ( normalized === undefined ) normalized = attribute.normalized;402		if ( normalized !== attribute.normalized ) {403404			console.error( 'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.normalized must be consistent across matching attributes.' );405			return null;406407		}408409		if ( gpuType === - 1 ) gpuType = attribute.gpuType;410		if ( gpuType !== attribute.gpuType ) {411412			console.error( 'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.gpuType must be consistent across matching attributes.' );413			return null;414415		}416417		arrayLength += attribute.count * itemSize;418419	}420421	const array = new TypedArray( arrayLength );422	const result = new BufferAttribute( array, itemSize, normalized );423	let offset = 0;424425	for ( let i = 0; i < attributes.length; ++ i ) {426427		const attribute = attributes[ i ];428		if ( attribute.isInterleavedBufferAttribute ) {429430			const tupleOffset = offset / itemSize;431			for ( let j = 0, l = attribute.count; j < l; j ++ ) {432433				for ( let c = 0; c < itemSize; c ++ ) {434435					const value = attribute.getComponent( j, c );436					result.setComponent( j + tupleOffset, c, value );437438				}439440			}441442		} else {443444			array.set( attribute.array, offset );445446		}447448		offset += attribute.count * itemSize;449450	}451452	if ( gpuType !== undefined ) {453454		result.gpuType = gpuType;455456	}457458	return result;459460}461462/**463 * Performs a deep clone of the given buffer attribute.464 *465 * @param {BufferAttribute} attribute - The attribute to clone.466 * @return {BufferAttribute} The cloned attribute.467 */468function deepCloneAttribute( attribute ) {469470	if ( attribute.isInstancedInterleavedBufferAttribute || attribute.isInterleavedBufferAttribute ) {471472		return deinterleaveAttribute( attribute );473474	}475476	if ( attribute.isInstancedBufferAttribute ) {477478		return new InstancedBufferAttribute().copy( attribute );479480	}481482	return new BufferAttribute().copy( attribute );483484}485486/**487 * Interleaves a set of attributes and returns a new array of corresponding attributes that share a488 * single {@link InterleavedBuffer} instance. All attributes must have compatible types.489 *490 * @param {Array<BufferAttribute>} attributes - The attributes to interleave.491 * @return {?Array<InterleavedBufferAttribute>} An array of interleaved attributes. If interleave does not succeed, the method returns `null`.492 */493function interleaveAttributes( attributes ) {494495	// Interleaves the provided attributes into an InterleavedBuffer and returns496	// a set of InterleavedBufferAttributes for each attribute497	let TypedArray;498	let arrayLength = 0;499	let stride = 0;500501	// calculate the length and type of the interleavedBuffer502	for ( let i = 0, l = attributes.length; i < l; ++ i ) {503504		const attribute = attributes[ i ];505506		if ( TypedArray === undefined ) TypedArray = attribute.array.constructor;507		if ( TypedArray !== attribute.array.constructor ) {508509			console.error( 'AttributeBuffers of different types cannot be interleaved' );510			return null;511512		}513514		arrayLength += attribute.array.length;515		stride += attribute.itemSize;516517	}518519	// Create the set of buffer attributes520	const interleavedBuffer = new InterleavedBuffer( new TypedArray( arrayLength ), stride );521	let offset = 0;522	const res = [];523	const getters = [ 'getX', 'getY', 'getZ', 'getW' ];524	const setters = [ 'setX', 'setY', 'setZ', 'setW' ];525526	for ( let j = 0, l = attributes.length; j < l; j ++ ) {527528		const attribute = attributes[ j ];529		const itemSize = attribute.itemSize;530		const count = attribute.count;531		const iba = new InterleavedBufferAttribute( interleavedBuffer, itemSize, offset, attribute.normalized );532		res.push( iba );533534		offset += itemSize;535536		// Move the data for each attribute into the new interleavedBuffer537		// at the appropriate offset538		for ( let c = 0; c < count; c ++ ) {539540			for ( let k = 0; k < itemSize; k ++ ) {541542				iba[ setters[ k ] ]( c, attribute[ getters[ k ] ]( c ) );543544			}545546		}547548	}549550	return res;551552}553554/**555 * Returns a new, non-interleaved version of the given attribute.556 *557 * @param {InterleavedBufferAttribute} attribute - The interleaved attribute.558 * @return {BufferAttribute} The non-interleaved attribute.559 */560function deinterleaveAttribute( attribute ) {561562	const cons = attribute.data.array.constructor;563	const count = attribute.count;564	const itemSize = attribute.itemSize;565	const normalized = attribute.normalized;566567	const array = new cons( count * itemSize );568	let newAttribute;569	if ( attribute.isInstancedInterleavedBufferAttribute ) {570571		newAttribute = new InstancedBufferAttribute( array, itemSize, normalized, attribute.meshPerAttribute );572573	} else {574575		newAttribute = new BufferAttribute( array, itemSize, normalized );576577	}578579	for ( let i = 0; i < count; i ++ ) {580581		newAttribute.setX( i, attribute.getX( i ) );582583		if ( itemSize >= 2 ) {584585			newAttribute.setY( i, attribute.getY( i ) );586587		}588589		if ( itemSize >= 3 ) {590591			newAttribute.setZ( i, attribute.getZ( i ) );592593		}594595		if ( itemSize >= 4 ) {596597			newAttribute.setW( i, attribute.getW( i ) );598599		}600601	}602603	return newAttribute;604605}606607/**608 * Deinterleaves all attributes on the given geometry.609 *610 * @param {BufferGeometry} geometry - The geometry to deinterleave.611 */612function deinterleaveGeometry( geometry ) {613614	const attributes = geometry.attributes;615	const morphAttributes = geometry.morphAttributes;616	const attrMap = new Map();617618	for ( const key in attributes ) {619620		const attr = attributes[ key ];621		if ( attr.isInterleavedBufferAttribute ) {622623			if ( ! attrMap.has( attr ) ) {624625				attrMap.set( attr, deinterleaveAttribute( attr ) );626627			}628629			attributes[ key ] = attrMap.get( attr );630631		}632633	}634635	for ( const key in morphAttributes ) {636637		const morphAttribute = morphAttributes[ key ];638639		for ( let i = 0, l = morphAttribute.length; i < l; i ++ ) {640641			const attr = morphAttribute[ i ];642			if ( attr.isInterleavedBufferAttribute ) {643644				if ( ! attrMap.has( attr ) ) {645646					attrMap.set( attr, deinterleaveAttribute( attr ) );647648				}649650				morphAttribute[ i ] = attrMap.get( attr );651652			}653654		}655656	}657658}659660/**661 * Returns the amount of bytes used by all attributes to represent the geometry.662 *663 * @param {BufferGeometry} geometry - The geometry.664 * @return {number} The estimate bytes used.665 */666function estimateBytesUsed( geometry ) {667668	// Return the estimated memory used by this geometry in bytes669	// Calculate using itemSize, count, and BYTES_PER_ELEMENT to account670	// for InterleavedBufferAttributes.671	let mem = 0;672	for ( const name in geometry.attributes ) {673674		const attr = geometry.getAttribute( name );675		mem += attr.count * attr.itemSize * attr.array.BYTES_PER_ELEMENT;676677	}678679	const indices = geometry.getIndex();680	mem += indices ? indices.count * indices.itemSize * indices.array.BYTES_PER_ELEMENT : 0;681	return mem;682683}684685/**686 * Returns a new geometry with vertices for which all similar vertex attributes (within tolerance) are merged.687 *688 * @param {BufferGeometry} geometry - The geometry to merge vertices for.689 * @param {number} [tolerance=1e-4] - The tolerance value.690 * @return {BufferGeometry} - The new geometry with merged vertices.691 */692function mergeVertices( geometry, tolerance = 1e-4 ) {693694	tolerance = Math.max( tolerance, Number.EPSILON );695696	// Generate an index buffer if the geometry doesn't have one, or optimize it697	// if it's already available.698	const hashToIndex = {};699	const indices = geometry.getIndex();700	const positions = geometry.getAttribute( 'position' );701	const vertexCount = indices ? indices.count : positions.count;702703	// next value for triangle indices704	let nextIndex = 0;705706	// attributes and new attribute arrays707	const attributeNames = Object.keys( geometry.attributes );708	const sourceIndices = [];709	const buffers = new Map();710	const newIndices = [];711	const getters = [ 'getX', 'getY', 'getZ', 'getW' ];712713	// convert the error tolerance to an amount of decimal places to truncate to714	const halfTolerance = tolerance * 0.5;715	const exponent = Math.log10( 1 / tolerance );716	const hashMultiplier = Math.pow( 10, exponent );717	const hashAdditive = halfTolerance * hashMultiplier;718	for ( let i = 0; i < vertexCount; i ++ ) {719720		const index = indices ? indices.getX( i ) : i;721722		// Generate a hash for the vertex attributes at the current index 'i'723		let hash = '';724		for ( let j = 0, l = attributeNames.length; j < l; j ++ ) {725726			const name = attributeNames[ j ];727			const attribute = geometry.getAttribute( name );728			const itemSize = attribute.itemSize;729730			for ( let k = 0; k < itemSize; k ++ ) {731732				// Math.trunc() preserves the full Number range, ~~ would wrap to int32733				hash += `${ Math.trunc( attribute[ getters[ k ] ]( index ) * hashMultiplier + hashAdditive ) },`;734735			}736737		}738739		// Add another reference to the vertex if it's already740		// used by another index741		if ( hash in hashToIndex ) {742743			newIndices.push( hashToIndex[ hash ] );744745		} else {746747			sourceIndices.push( index );748749			hashToIndex[ hash ] = nextIndex;750			newIndices.push( nextIndex );751			nextIndex ++;752753		}754755	}756757	// generate result BufferGeometry758	const result = geometry.clone();759	for ( const name in geometry.attributes ) {760761		result.setAttribute( name, remapAttribute( geometry.attributes[ name ], sourceIndices, buffers ) );762763	}764765	for ( const name in geometry.morphAttributes ) {766767		result.morphAttributes[ name ] = geometry.morphAttributes[ name ].map( attribute => remapAttribute( attribute, sourceIndices, buffers ) );768769	}770771	// indices772773	result.setIndex( newIndices );774775	return result;776777}778779/**780 * Converts the given geometry to the `TrianglesDrawMode` draw mode, which781 * corresponds to the `gl.TRIANGLES` primitive in WebGL. The conversion only782 * rewrites the index, so the geometry is modified in place and returned.783 *784 * @param {BufferGeometry} geometry - The geometry to convert.785 * @param {number} drawMode - The current draw mode.786 * @return {BufferGeometry} The converted geometry using `TrianglesDrawMode`.787 */788function toTrianglesDrawMode( geometry, drawMode ) {789790	if ( drawMode === TrianglesDrawMode ) {791792		console.warn( 'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Geometry already defined as triangles.' );793		return geometry;794795	}796797	if ( drawMode === TriangleFanDrawMode || drawMode === TriangleStripDrawMode ) {798799		let index = geometry.getIndex();800801		// generate index if not present802803		if ( index === null ) {804805			const indices = [];806807			const position = geometry.getAttribute( 'position' );808809			if ( position !== undefined ) {810811				for ( let i = 0; i < position.count; i ++ ) {812813					indices.push( i );814815				}816817				geometry.setIndex( indices );818				index = geometry.getIndex();819820			} else {821822				console.error( 'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Undefined position attribute. Processing not possible.' );823				return geometry;824825			}826827		}828829		//830831		const numberOfTriangles = index.count - 2;832		const newIndices = [];833834		if ( drawMode === TriangleFanDrawMode ) {835836			// gl.TRIANGLE_FAN837838			for ( let i = 1; i <= numberOfTriangles; i ++ ) {839840				newIndices.push( index.getX( 0 ) );841				newIndices.push( index.getX( i ) );842				newIndices.push( index.getX( i + 1 ) );843844			}845846		} else {847848			// gl.TRIANGLE_STRIP849850			for ( let i = 0; i < numberOfTriangles; i ++ ) {851852				if ( i % 2 === 0 ) {853854					newIndices.push( index.getX( i ) );855					newIndices.push( index.getX( i + 1 ) );856					newIndices.push( index.getX( i + 2 ) );857858				} else {859860					newIndices.push( index.getX( i + 2 ) );861					newIndices.push( index.getX( i + 1 ) );862					newIndices.push( index.getX( i ) );863864				}865866			}867868		}869870		if ( ( newIndices.length / 3 ) !== numberOfTriangles ) {871872			console.error( 'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Unable to generate correct amount of triangles.' );873874		}875876		// updated indices877878		geometry.setIndex( newIndices );879		geometry.clearGroups();880881		return geometry;882883	} else {884885		console.error( 'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Unknown draw mode:', drawMode );886		return geometry;887888	}889890}891892/**893 * Calculates the morphed attributes of a morphed/skinned BufferGeometry.894 *895 * Helpful for Raytracing or Decals (i.e. a `DecalGeometry` applied to a morphed Object with a `BufferGeometry`896 * will use the original `BufferGeometry`, not the morphed/skinned one, generating an incorrect result.897 * Using this function to create a shadow `Object3`D the `DecalGeometry` can be correctly generated).898 *899 * @param {Mesh|Line|Points} object - The 3D object to compute morph attributes for.900 * @return {Object} An object with original position/normal attributes and morphed ones.901 */902function computeMorphedAttributes( object ) {903904	const _vA = new Vector3();905	const _vB = new Vector3();906	const _vC = new Vector3();907908	const _tempA = new Vector3();909	const _tempB = new Vector3();910	const _tempC = new Vector3();911912	const _morphA = new Vector3();913	const _morphB = new Vector3();914	const _morphC = new Vector3();915916	function _calculateMorphedAttributeData(917		object,918		attribute,919		morphAttribute,920		morphTargetsRelative,921		a,922		b,923		c,924		modifiedAttributeArray925	) {926927		_vA.fromBufferAttribute( attribute, a );928		_vB.fromBufferAttribute( attribute, b );929		_vC.fromBufferAttribute( attribute, c );930931		const morphInfluences = object.morphTargetInfluences;932933		if ( morphAttribute && morphInfluences ) {934935			_morphA.set( 0, 0, 0 );936			_morphB.set( 0, 0, 0 );937			_morphC.set( 0, 0, 0 );938939			for ( let i = 0, il = morphAttribute.length; i < il; i ++ ) {940941				const influence = morphInfluences[ i ];942				const morph = morphAttribute[ i ];943944				if ( influence === 0 ) continue;945946				_tempA.fromBufferAttribute( morph, a );947				_tempB.fromBufferAttribute( morph, b );948				_tempC.fromBufferAttribute( morph, c );949950				if ( morphTargetsRelative ) {951952					_morphA.addScaledVector( _tempA, influence );953					_morphB.addScaledVector( _tempB, influence );954					_morphC.addScaledVector( _tempC, influence );955956				} else {957958					_morphA.addScaledVector( _tempA.sub( _vA ), influence );959					_morphB.addScaledVector( _tempB.sub( _vB ), influence );960					_morphC.addScaledVector( _tempC.sub( _vC ), influence );961962				}963964			}965966			_vA.add( _morphA );967			_vB.add( _morphB );968			_vC.add( _morphC );969970		}971972		if ( object.isSkinnedMesh ) {973974			object.applyBoneTransform( a, _vA );975			object.applyBoneTransform( b, _vB );976			object.applyBoneTransform( c, _vC );977978		}979980		modifiedAttributeArray[ a * 3 + 0 ] = _vA.x;981		modifiedAttributeArray[ a * 3 + 1 ] = _vA.y;982		modifiedAttributeArray[ a * 3 + 2 ] = _vA.z;983		modifiedAttributeArray[ b * 3 + 0 ] = _vB.x;984		modifiedAttributeArray[ b * 3 + 1 ] = _vB.y;985		modifiedAttributeArray[ b * 3 + 2 ] = _vB.z;986		modifiedAttributeArray[ c * 3 + 0 ] = _vC.x;987		modifiedAttributeArray[ c * 3 + 1 ] = _vC.y;988		modifiedAttributeArray[ c * 3 + 2 ] = _vC.z;989990	}991992	const geometry = object.geometry;993	const material = object.material;994995	let a, b, c;996	const index = geometry.index;997	const positionAttribute = geometry.attributes.position;998	const morphPosition = geometry.morphAttributes.position;999	const morphTargetsRelative = geometry.morphTargetsRelative;1000	const normalAttribute = geometry.attributes.normal;1001	const morphNormal = geometry.morphAttributes.normal;10021003	const groups = geometry.groups;1004	const drawRange = geometry.drawRange;1005	let i, j, il, jl;1006	let group;1007	let start, end;10081009	const modifiedPosition = new Float32Array( positionAttribute.count * positionAttribute.itemSize );1010	const modifiedNormal = new Float32Array( normalAttribute.count * normalAttribute.itemSize );10111012	if ( index !== null ) {10131014		// indexed buffer geometry10151016		if ( Array.isArray( material ) ) {10171018			for ( i = 0, il = groups.length; i < il; i ++ ) {10191020				group = groups[ i ];10211022				start = Math.max( group.start, drawRange.start );1023				end = Math.min( ( group.start + group.count ), ( drawRange.start + drawRange.count ) );10241025				for ( j = start, jl = end; j < jl; j += 3 ) {10261027					a = index.getX( j );1028					b = index.getX( j + 1 );1029					c = index.getX( j + 2 );10301031					_calculateMorphedAttributeData(1032						object,1033						positionAttribute,1034						morphPosition,1035						morphTargetsRelative,1036						a, b, c,1037						modifiedPosition1038					);10391040					_calculateMorphedAttributeData(1041						object,1042						normalAttribute,1043						morphNormal,1044						morphTargetsRelative,1045						a, b, c,1046						modifiedNormal1047					);10481049				}10501051			}10521053		} else {10541055			start = Math.max( 0, drawRange.start );1056			end = Math.min( index.count, ( drawRange.start + drawRange.count ) );10571058			for ( i = start, il = end; i < il; i += 3 ) {10591060				a = index.getX( i );1061				b = index.getX( i + 1 );1062				c = index.getX( i + 2 );10631064				_calculateMorphedAttributeData(1065					object,1066					positionAttribute,1067					morphPosition,1068					morphTargetsRelative,1069					a, b, c,1070					modifiedPosition1071				);10721073				_calculateMorphedAttributeData(1074					object,1075					normalAttribute,1076					morphNormal,1077					morphTargetsRelative,1078					a, b, c,1079					modifiedNormal1080				);10811082			}10831084		}10851086	} else {10871088		// non-indexed buffer geometry10891090		if ( Array.isArray( material ) ) {10911092			for ( i = 0, il = groups.length; i < il; i ++ ) {10931094				group = groups[ i ];10951096				start = Math.max( group.start, drawRange.start );1097				end = Math.min( ( group.start + group.count ), ( drawRange.start + drawRange.count ) );10981099				for ( j = start, jl = end; j < jl; j += 3 ) {11001101					a = j;1102					b = j + 1;1103					c = j + 2;11041105					_calculateMorphedAttributeData(1106						object,1107						positionAttribute,1108						morphPosition,1109						morphTargetsRelative,1110						a, b, c,1111						modifiedPosition1112					);11131114					_calculateMorphedAttributeData(1115						object,1116						normalAttribute,1117						morphNormal,1118						morphTargetsRelative,1119						a, b, c,1120						modifiedNormal1121					);11221123				}11241125			}11261127		} else {11281129			start = Math.max( 0, drawRange.start );1130			end = Math.min( positionAttribute.count, ( drawRange.start + drawRange.count ) );11311132			for ( i = start, il = end; i < il; i += 3 ) {11331134				a = i;1135				b = i + 1;1136				c = i + 2;11371138				_calculateMorphedAttributeData(1139					object,1140					positionAttribute,1141					morphPosition,1142					morphTargetsRelative,1143					a, b, c,1144					modifiedPosition1145				);11461147				_calculateMorphedAttributeData(1148					object,1149					normalAttribute,1150					morphNormal,1151					morphTargetsRelative,1152					a, b, c,1153					modifiedNormal1154				);11551156			}11571158		}11591160	}11611162	const morphedPositionAttribute = new Float32BufferAttribute( modifiedPosition, 3 );1163	const morphedNormalAttribute = new Float32BufferAttribute( modifiedNormal, 3 );11641165	return {11661167		positionAttribute: positionAttribute,1168		normalAttribute: normalAttribute,1169		morphedPositionAttribute: morphedPositionAttribute,1170		morphedNormalAttribute: morphedNormalAttribute11711172	};11731174}11751176/**1177 * Merges the {@link BufferGeometry#groups} for the given geometry.1178 *1179 * @param {BufferGeometry} geometry - The geometry to modify.1180 * @return {BufferGeometry} - The updated geometry1181 */1182function mergeGroups( geometry ) {11831184	if ( geometry.groups.length === 0 ) {11851186		console.warn( 'THREE.BufferGeometryUtils.mergeGroups(): No groups are defined. Nothing to merge.' );1187		return geometry;11881189	}11901191	let groups = geometry.groups;11921193	// sort groups by material index11941195	groups = groups.sort( ( a, b ) => {11961197		if ( a.materialIndex !== b.materialIndex ) return a.materialIndex - b.materialIndex;11981199		return a.start - b.start;12001201	} );12021203	// create index for non-indexed geometries12041205	if ( geometry.getIndex() === null ) {12061207		const positionAttribute = geometry.getAttribute( 'position' );1208		const indices = [];12091210		for ( let i = 0; i < positionAttribute.count; i += 3 ) {12111212			indices.push( i, i + 1, i + 2 );12131214		}12151216		geometry.setIndex( indices );12171218	}12191220	// sort index12211222	const index = geometry.getIndex();12231224	const newIndices = [];12251226	for ( let i = 0; i < groups.length; i ++ ) {12271228		const group = groups[ i ];12291230		if ( group.count === Infinity ) group.count = index.count - group.start;12311232		const groupStart = group.start;1233		const groupLength = groupStart + group.count;12341235		for ( let j = groupStart; j < groupLength; j ++ ) {12361237			newIndices.push( index.getX( j ) );12381239		}12401241	}12421243	geometry.dispose(); // Required to force buffer recreation1244	geometry.setIndex( newIndices );12451246	// update groups indices12471248	let start = 0;12491250	for ( let i = 0; i < groups.length; i ++ ) {12511252		const group = groups[ i ];12531254		group.start = start;1255		start += group.count;12561257	}12581259	// merge groups12601261	let currentGroup = groups[ 0 ];12621263	geometry.groups = [ currentGroup ];12641265	for ( let i = 1; i < groups.length; i ++ ) {12661267		const group = groups[ i ];12681269		if ( currentGroup.materialIndex === group.materialIndex ) {12701271			currentGroup.count += group.count;12721273		} else {12741275			currentGroup = group;1276			geometry.groups.push( currentGroup );12771278		}12791280	}12811282	return geometry;12831284}12851286/**1287 * Modifies the supplied geometry if it is non-indexed, otherwise creates a new,1288 * non-indexed geometry. Returns the geometry with smooth normals everywhere except1289 * faces that meet at an angle greater than the crease angle.1290 *1291 * @param {BufferGeometry} geometry - The geometry to modify.1292 * @param {number} [creaseAngle=Math.PI/3] - The crease angle in radians.1293 * @return {BufferGeometry} - The updated geometry1294 */1295function toCreasedNormals( geometry, creaseAngle = Math.PI / 3 /* 60 degrees */ ) {12961297	// BufferGeometry.toNonIndexed() warns if the geometry is non-indexed1298	// and returns the original geometry1299	const resultGeometry = geometry.index ? geometry.toNonIndexed() : geometry;1300	const posAttr = resultGeometry.attributes.position;1301	const vertexCount = posAttr.count;13021303	let positions;13041305	if ( posAttr.isBufferAttribute === true && posAttr.itemSize === 3 && posAttr.normalized === false ) {13061307		positions = posAttr.array;13081309	} else {13101311		// flatten the position buffer so the math below operates on plain numbers1312		positions = new Float64Array( vertexCount * 3 );13131314		for ( let i = 0; i < vertexCount; i ++ ) {13151316			positions[ 3 * i + 0 ] = posAttr.getX( i );1317			positions[ 3 * i + 1 ] = posAttr.getY( i );1318			positions[ 3 * i + 2 ] = posAttr.getZ( i );13191320		}13211322	}13231324	const creaseDot = Math.cos( creaseAngle );1325	const hashMultiplier = ( 1 + 1e-10 ) * 1e2;1326	const faceCount = vertexCount / 3;13271328	// compute the normal of each face1329	const faceNormals = new Float64Array( faceCount * 3 );1330	for ( let f = 0; f < faceCount; f ++ ) {13311332		const f9 = 9 * f;1333		const ax = positions[ f9 + 0 ], ay = positions[ f9 + 1 ], az = positions[ f9 + 2 ];1334		const bx = positions[ f9 + 3 ], by = positions[ f9 + 4 ], bz = positions[ f9 + 5 ];1335		const cx = positions[ f9 + 6 ], cy = positions[ f9 + 7 ], cz = positions[ f9 + 8 ];13361337		const v1x = cx - bx, v1y = cy - by, v1z = cz - bz;1338		const v2x = ax - bx, v2y = ay - by, v2z = az - bz;13391340		const nx = v1y * v2z - v1z * v2y;1341		const ny = v1z * v2x - v1x * v2z;1342		const nz = v1x * v2y - v1y * v2x;13431344		const invLength = 1 / ( Math.sqrt( nx * nx + ny * ny + nz * nz ) || 1 );1345		faceNormals[ 3 * f + 0 ] = nx * invLength;1346		faceNormals[ 3 * f + 1 ] = ny * invLength;1347		faceNormals[ 3 * f + 2 ] = nz * invLength;13481349	}13501351	// assign an id to each vertex, sharing the id between vertices with the same1352	// quantized position via an open-addressed hash table (slots hold id + 1, 0 means empty)1353	const vertexIds = new Int32Array( vertexCount );1354	const quantized = new Float64Array( vertexCount * 3 );13551356	let tableSize = 1;1357	while ( tableSize < vertexCount * 2 ) tableSize <<= 1;1358	const tableMask = tableSize - 1;1359	const table = new Int32Array( tableSize );13601361	let uniqueCount = 0;1362	for ( let i = 0; i < vertexCount; i ++ ) {13631364		const i3 = 3 * i;1365		const qx = Math.trunc( positions[ i3 + 0 ] * hashMultiplier );1366		const qy = Math.trunc( positions[ i3 + 1 ] * hashMultiplier );1367		const qz = Math.trunc( positions[ i3 + 2 ] * hashMultiplier );13681369		let slot = ( Math.imul( qx, 73856093 ) ^ Math.imul( qy, 19349663 ) ^ Math.imul( qz, 83492791 ) ) & tableMask;13701371		while ( true ) {13721373			const id = table[ slot ];13741375			if ( id === 0 ) {13761377				const q3 = 3 * uniqueCount;1378				quantized[ q3 + 0 ] = qx;1379				quantized[ q3 + 1 ] = qy;1380				quantized[ q3 + 2 ] = qz;13811382				table[ slot ] = uniqueCount + 1;1383				vertexIds[ i ] = uniqueCount ++;1384				break;13851386			}13871388			const q3 = 3 * ( id - 1 );13891390			if ( quantized[ q3 + 0 ] === qx && quantized[ q3 + 1 ] === qy && quantized[ q3 + 2 ] === qz ) {13911392				vertexIds[ i ] = id - 1;1393				break;13941395			}13961397			slot = ( slot + 1 ) & tableMask;13981399		}14001401	}14021403	// bucket the faces surrounding each unique vertex position1404	const bucketOffsets = new Int32Array( uniqueCount + 1 );1405	for ( let i = 0; i < vertexCount; i ++ ) bucketOffsets[ vertexIds[ i ] + 1 ] ++;1406	for ( let i = 0; i < uniqueCount; i ++ ) bucketOffsets[ i + 1 ] += bucketOffsets[ i ];14071408	const bucketFaces = new Int32Array( vertexCount );1409	const bucketCursors = bucketOffsets.slice( 0, uniqueCount );1410	for ( let f = 0; f < faceCount; f ++ ) {14111412		const f3 = 3 * f;1413		bucketFaces[ bucketCursors[ vertexIds[ f3 + 0 ] ] ++ ] = f;1414		bucketFaces[ bucketCursors[ vertexIds[ f3 + 1 ] ] ++ ] = f;1415		bucketFaces[ bucketCursors[ vertexIds[ f3 + 2 ] ] ++ ] = f;14161417	}14181419	// average the normals of the faces surrounding each vertex if they are within the1420	// provided crease threshold1421	const normalArray = new Float32Array( vertexCount * 3 );1422	for ( let f = 0; f < faceCount; f ++ ) {14231424		const f3 = 3 * f;1425		const nx = faceNormals[ f3 + 0 ];1426		const ny = faceNormals[ f3 + 1 ];1427		const nz = faceNormals[ f3 + 2 ];14281429		for ( let n = 0; n < 3; n ++ ) {14301431			const i = f3 + n;1432			const id = vertexIds[ i ];14331434			let sumX = 0, sumY = 0, sumZ = 0;14351436			for ( let k = bucketOffsets[ id ], end = bucketOffsets[ id + 1 ]; k < end; k ++ ) {14371438				const o3 = 3 * bucketFaces[ k ];1439				const ox = faceNormals[ o3 + 0 ];1440				const oy = faceNormals[ o3 + 1 ];1441				const oz = faceNormals[ o3 + 2 ];14421443				if ( nx * ox + ny * oy + nz * oz > creaseDot ) {14441445					sumX += ox;1446					sumY += oy;1447					sumZ += oz;14481449				}14501451			}14521453			const invLength = 1 / ( Math.sqrt( sumX * sumX + sumY * sumY + sumZ * sumZ ) || 1 );1454			normalArray[ 3 * i + 0 ] = sumX * invLength;1455			normalArray[ 3 * i + 1 ] = sumY * invLength;1456			normalArray[ 3 * i + 2 ] = sumZ * invLength;14571458		}14591460	}14611462	resultGeometry.setAttribute( 'normal', new BufferAttribute( normalArray, 3, false ) );1463	return resultGeometry;14641465}14661467/**1468 * Copies attribute entries in the order specified by the source vertex indices.1469 * Preserves raw values, attribute type and metadata. Reuse the same buffer map1470 * across calls to preserve shared interleaved buffers for the same mapping.1471 *1472 * @param {BufferAttribute|InterleavedBufferAttribute} attribute - The source attribute.1473 * @param {Array<number>|TypedArray} sourceIndices - The source index for each output vertex.1474 * @param {Map<InterleavedBuffer, InterleavedBuffer>} [buffers] - Shared interleaved buffer copies.1475 * @return {BufferAttribute|InterleavedBufferAttribute} The remapped attribute.1476 */1477function remapAttribute( attribute, sourceIndices, buffers = new Map() ) {14781479	const interleaved = attribute.isInterleavedBufferAttribute;1480	const source = interleaved ? attribute.data : attribute;1481	const stride = interleaved ? source.stride : attribute.itemSize;1482	let data = interleaved ? buffers.get( source ) : undefined;14831484	if ( data === undefined ) {14851486		const array = new source.array.constructor( sourceIndices.length * stride );1487		for ( let i = 0; i < sourceIndices.length; i ++ ) {14881489			for ( let j = 0; j < stride; j ++ ) array[ i * stride + j ] = source.array[ sourceIndices[ i ] * stride + j ];14901491		}14921493		data = interleaved1494			? new source.constructor( array, stride, source.meshPerAttribute )1495			: new attribute.constructor( array, attribute.itemSize, attribute.normalized, attribute.meshPerAttribute );1496		data.setUsage( source.usage );1497		if ( interleaved ) buffers.set( source, data );14981499	}15001501	const result = interleaved ? new attribute.constructor( data, attribute.itemSize, attribute.offset, attribute.normalized ) : data;1502	result.name = attribute.name;1503	if ( ! interleaved ) result.gpuType = attribute.gpuType;1504	return result;15051506}15071508export {1509	computeMikkTSpaceTangents,1510	mergeGeometries,1511	mergeAttributes,1512	deepCloneAttribute,1513	deinterleaveAttribute,1514	deinterleaveGeometry,1515	interleaveAttributes,1516	estimateBytesUsed,1517	mergeVertices,1518	remapAttribute,1519	toTrianglesDrawMode,1520	computeMorphedAttributes,1521	mergeGroups,1522	toCreasedNormals1523};