(function (global, factory) {
	typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('three')) :
	typeof define === 'function' && define.amd ? define(['exports', 'three'], factory) :
	(global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.MeshBVHLib = global.MeshBVHLib || {}, global.THREE));
})(this, (function (exports, three) { 'use strict';

	// Split strategy constants
	const CENTER = 0;
	const AVERAGE = 1;
	const SAH = 2;

	// Traversal constants
	const NOT_INTERSECTED = 0;
	const INTERSECTED = 1;
	const CONTAINED = 2;

	// SAH cost constants
	// TODO: hone these costs more. The relative difference between them should be the
	// difference in measured time to perform a triangle intersection vs traversing
	// bounds.
	const TRIANGLE_INTERSECT_COST = 1.25;
	const TRAVERSAL_COST = 1;


	// Build constants
	const BYTES_PER_NODE = 6 * 4 + 4 + 4;
	const IS_LEAFNODE_FLAG = 0xFFFF;

	// EPSILON for computing floating point error during build
	// https://en.wikipedia.org/wiki/Machine_epsilon#Values_for_standard_hardware_floating_point_arithmetics
	const FLOAT32_EPSILON = Math.pow( 2, - 24 );

	class MeshBVHNode {

		constructor() {

			// internal nodes have boundingData, left, right, and splitAxis
			// leaf nodes have offset and count (referring to primitives in the mesh geometry)

		}

	}

	function arrayToBox( nodeIndex32, array, target ) {

		target.min.x = array[ nodeIndex32 ];
		target.min.y = array[ nodeIndex32 + 1 ];
		target.min.z = array[ nodeIndex32 + 2 ];

		target.max.x = array[ nodeIndex32 + 3 ];
		target.max.y = array[ nodeIndex32 + 4 ];
		target.max.z = array[ nodeIndex32 + 5 ];

		return target;

	}

	function getLongestEdgeIndex( bounds ) {

		let splitDimIdx = - 1;
		let splitDist = - Infinity;

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

			const dist = bounds[ i + 3 ] - bounds[ i ];
			if ( dist > splitDist ) {

				splitDist = dist;
				splitDimIdx = i;

			}

		}

		return splitDimIdx;

	}

	// copys bounds a into bounds b
	function copyBounds( source, target ) {

		target.set( source );

	}

	// sets bounds target to the union of bounds a and b
	function unionBounds( a, b, target ) {

		let aVal, bVal;
		for ( let d = 0; d < 3; d ++ ) {

			const d3 = d + 3;

			// set the minimum values
			aVal = a[ d ];
			bVal = b[ d ];
			target[ d ] = aVal < bVal ? aVal : bVal;

			// set the max values
			aVal = a[ d3 ];
			bVal = b[ d3 ];
			target[ d3 ] = aVal > bVal ? aVal : bVal;

		}

	}

	// expands the given bounds by the provided triangle bounds
	function expandByTriangleBounds( startIndex, triangleBounds, bounds ) {

		for ( let d = 0; d < 3; d ++ ) {

			const tCenter = triangleBounds[ startIndex + 2 * d ];
			const tHalf = triangleBounds[ startIndex + 2 * d + 1 ];

			const tMin = tCenter - tHalf;
			const tMax = tCenter + tHalf;

			if ( tMin < bounds[ d ] ) {

				bounds[ d ] = tMin;

			}

			if ( tMax > bounds[ d + 3 ] ) {

				bounds[ d + 3 ] = tMax;

			}

		}

	}

	// compute bounds surface area
	function computeSurfaceArea( bounds ) {

		const d0 = bounds[ 3 ] - bounds[ 0 ];
		const d1 = bounds[ 4 ] - bounds[ 1 ];
		const d2 = bounds[ 5 ] - bounds[ 2 ];

		return 2 * ( d0 * d1 + d1 * d2 + d2 * d0 );

	}

	function ensureIndex( geo, options ) {

		if ( ! geo.index ) {

			const vertexCount = geo.attributes.position.count;
			const BufferConstructor = options.useSharedArrayBuffer ? SharedArrayBuffer : ArrayBuffer;
			let index;
			if ( vertexCount > 65535 ) {

				index = new Uint32Array( new BufferConstructor( 4 * vertexCount ) );

			} else {

				index = new Uint16Array( new BufferConstructor( 2 * vertexCount ) );

			}

			geo.setIndex( new three.BufferAttribute( index, 1 ) );

			for ( let i = 0; i < vertexCount; i ++ ) {

				index[ i ] = i;

			}

		}

	}

	// Computes the set of { offset, count } ranges which need independent BVH roots. Each
	// region in the geometry index that belongs to a different set of material groups requires
	// a separate BVH root, so that triangles indices belonging to one group never get swapped
	// with triangle indices belongs to another group. For example, if the groups were like this:
	//
	// [-------------------------------------------------------------]
	// |__________________|
	//   g0 = [0, 20]  |______________________||_____________________|
	//                      g1 = [16, 40]           g2 = [41, 60]
	//
	// we would need four BVH roots: [0, 15], [16, 20], [21, 40], [41, 60].
	function getRootIndexRanges( geo ) {

		if ( ! geo.groups || ! geo.groups.length ) {

			return [ { offset: 0, count: geo.index.count / 3 } ];

		}

		const ranges = [];
		const rangeBoundaries = new Set();
		for ( const group of geo.groups ) {

			rangeBoundaries.add( group.start );
			rangeBoundaries.add( group.start + group.count );

		}

		// note that if you don't pass in a comparator, it sorts them lexicographically as strings :-(
		const sortedBoundaries = Array.from( rangeBoundaries.values() ).sort( ( a, b ) => a - b );
		for ( let i = 0; i < sortedBoundaries.length - 1; i ++ ) {

			const start = sortedBoundaries[ i ], end = sortedBoundaries[ i + 1 ];
			ranges.push( { offset: ( start / 3 ), count: ( end - start ) / 3 } );

		}

		return ranges;

	}

	// computes the union of the bounds of all of the given triangles and puts the resulting box in target. If
	// centroidTarget is provided then a bounding box is computed for the centroids of the triangles, as well.
	// These are computed together to avoid redundant accesses to bounds array.
	function getBounds( triangleBounds, offset, count, target, centroidTarget = null ) {

		let minx = Infinity;
		let miny = Infinity;
		let minz = Infinity;
		let maxx = - Infinity;
		let maxy = - Infinity;
		let maxz = - Infinity;

		let cminx = Infinity;
		let cminy = Infinity;
		let cminz = Infinity;
		let cmaxx = - Infinity;
		let cmaxy = - Infinity;
		let cmaxz = - Infinity;

		const includeCentroid = centroidTarget !== null;
		for ( let i = offset * 6, end = ( offset + count ) * 6; i < end; i += 6 ) {

			const cx = triangleBounds[ i + 0 ];
			const hx = triangleBounds[ i + 1 ];
			const lx = cx - hx;
			const rx = cx + hx;
			if ( lx < minx ) minx = lx;
			if ( rx > maxx ) maxx = rx;
			if ( includeCentroid && cx < cminx ) cminx = cx;
			if ( includeCentroid && cx > cmaxx ) cmaxx = cx;

			const cy = triangleBounds[ i + 2 ];
			const hy = triangleBounds[ i + 3 ];
			const ly = cy - hy;
			const ry = cy + hy;
			if ( ly < miny ) miny = ly;
			if ( ry > maxy ) maxy = ry;
			if ( includeCentroid && cy < cminy ) cminy = cy;
			if ( includeCentroid && cy > cmaxy ) cmaxy = cy;

			const cz = triangleBounds[ i + 4 ];
			const hz = triangleBounds[ i + 5 ];
			const lz = cz - hz;
			const rz = cz + hz;
			if ( lz < minz ) minz = lz;
			if ( rz > maxz ) maxz = rz;
			if ( includeCentroid && cz < cminz ) cminz = cz;
			if ( includeCentroid && cz > cmaxz ) cmaxz = cz;

		}

		target[ 0 ] = minx;
		target[ 1 ] = miny;
		target[ 2 ] = minz;

		target[ 3 ] = maxx;
		target[ 4 ] = maxy;
		target[ 5 ] = maxz;

		if ( includeCentroid ) {

			centroidTarget[ 0 ] = cminx;
			centroidTarget[ 1 ] = cminy;
			centroidTarget[ 2 ] = cminz;

			centroidTarget[ 3 ] = cmaxx;
			centroidTarget[ 4 ] = cmaxy;
			centroidTarget[ 5 ] = cmaxz;

		}

	}

	// A stand alone function for retrieving the centroid bounds.
	function getCentroidBounds( triangleBounds, offset, count, centroidTarget ) {

		let cminx = Infinity;
		let cminy = Infinity;
		let cminz = Infinity;
		let cmaxx = - Infinity;
		let cmaxy = - Infinity;
		let cmaxz = - Infinity;

		for ( let i = offset * 6, end = ( offset + count ) * 6; i < end; i += 6 ) {

			const cx = triangleBounds[ i + 0 ];
			if ( cx < cminx ) cminx = cx;
			if ( cx > cmaxx ) cmaxx = cx;

			const cy = triangleBounds[ i + 2 ];
			if ( cy < cminy ) cminy = cy;
			if ( cy > cmaxy ) cmaxy = cy;

			const cz = triangleBounds[ i + 4 ];
			if ( cz < cminz ) cminz = cz;
			if ( cz > cmaxz ) cmaxz = cz;

		}

		centroidTarget[ 0 ] = cminx;
		centroidTarget[ 1 ] = cminy;
		centroidTarget[ 2 ] = cminz;

		centroidTarget[ 3 ] = cmaxx;
		centroidTarget[ 4 ] = cmaxy;
		centroidTarget[ 5 ] = cmaxz;

	}


	// reorders `tris` such that for `count` elements after `offset`, elements on the left side of the split
	// will be on the left and elements on the right side of the split will be on the right. returns the index
	// of the first element on the right side, or offset + count if there are no elements on the right side.
	function partition( index, triangleBounds, offset, count, split ) {

		let left = offset;
		let right = offset + count - 1;
		const pos = split.pos;
		const axisOffset = split.axis * 2;

		// hoare partitioning, see e.g. https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
		while ( true ) {

			while ( left <= right && triangleBounds[ left * 6 + axisOffset ] < pos ) {

				left ++;

			}


			// if a triangle center lies on the partition plane it is considered to be on the right side
			while ( left <= right && triangleBounds[ right * 6 + axisOffset ] >= pos ) {

				right --;

			}

			if ( left < right ) {

				// we need to swap all of the information associated with the triangles at index
				// left and right; that's the verts in the geometry index, the bounds,
				// and perhaps the SAH planes

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

					let t0 = index[ left * 3 + i ];
					index[ left * 3 + i ] = index[ right * 3 + i ];
					index[ right * 3 + i ] = t0;

					let t1 = triangleBounds[ left * 6 + i * 2 + 0 ];
					triangleBounds[ left * 6 + i * 2 + 0 ] = triangleBounds[ right * 6 + i * 2 + 0 ];
					triangleBounds[ right * 6 + i * 2 + 0 ] = t1;

					let t2 = triangleBounds[ left * 6 + i * 2 + 1 ];
					triangleBounds[ left * 6 + i * 2 + 1 ] = triangleBounds[ right * 6 + i * 2 + 1 ];
					triangleBounds[ right * 6 + i * 2 + 1 ] = t2;

				}

				left ++;
				right --;

			} else {

				return left;

			}

		}

	}

	const BIN_COUNT = 32;
	const binsSort = ( a, b ) => a.candidate - b.candidate;
	const sahBins = new Array( BIN_COUNT ).fill().map( () => {

		return {

			count: 0,
			bounds: new Float32Array( 6 ),
			rightCacheBounds: new Float32Array( 6 ),
			leftCacheBounds: new Float32Array( 6 ),
			candidate: 0,

		};

	} );
	const leftBounds = new Float32Array( 6 );

	function getOptimalSplit( nodeBoundingData, centroidBoundingData, triangleBounds, offset, count, strategy ) {

		let axis = - 1;
		let pos = 0;

		// Center
		if ( strategy === CENTER ) {

			axis = getLongestEdgeIndex( centroidBoundingData );
			if ( axis !== - 1 ) {

				pos = ( centroidBoundingData[ axis ] + centroidBoundingData[ axis + 3 ] ) / 2;

			}

		} else if ( strategy === AVERAGE ) {

			axis = getLongestEdgeIndex( nodeBoundingData );
			if ( axis !== - 1 ) {

				pos = getAverage( triangleBounds, offset, count, axis );

			}

		} else if ( strategy === SAH ) {

			const rootSurfaceArea = computeSurfaceArea( nodeBoundingData );
			let bestCost = TRIANGLE_INTERSECT_COST * count;

			// iterate over all axes
			const cStart = offset * 6;
			const cEnd = ( offset + count ) * 6;
			for ( let a = 0; a < 3; a ++ ) {

				const axisLeft = centroidBoundingData[ a ];
				const axisRight = centroidBoundingData[ a + 3 ];
				const axisLength = axisRight - axisLeft;
				const binWidth = axisLength / BIN_COUNT;

				// If we have fewer triangles than we're planning to split then just check all
				// the triangle positions because it will be faster.
				if ( count < BIN_COUNT / 4 ) {

					// initialize the bin candidates
					const truncatedBins = [ ...sahBins ];
					truncatedBins.length = count;

					// set the candidates
					let b = 0;
					for ( let c = cStart; c < cEnd; c += 6, b ++ ) {

						const bin = truncatedBins[ b ];
						bin.candidate = triangleBounds[ c + 2 * a ];
						bin.count = 0;

						const {
							bounds,
							leftCacheBounds,
							rightCacheBounds,
						} = bin;
						for ( let d = 0; d < 3; d ++ ) {

							rightCacheBounds[ d ] = Infinity;
							rightCacheBounds[ d + 3 ] = - Infinity;

							leftCacheBounds[ d ] = Infinity;
							leftCacheBounds[ d + 3 ] = - Infinity;

							bounds[ d ] = Infinity;
							bounds[ d + 3 ] = - Infinity;

						}

						expandByTriangleBounds( c, triangleBounds, bounds );

					}

					truncatedBins.sort( binsSort );

					// remove redundant splits
					let splitCount = count;
					for ( let bi = 0; bi < splitCount; bi ++ ) {

						const bin = truncatedBins[ bi ];
						while ( bi + 1 < splitCount && truncatedBins[ bi + 1 ].candidate === bin.candidate ) {

							truncatedBins.splice( bi + 1, 1 );
							splitCount --;

						}

					}

					// find the appropriate bin for each triangle and expand the bounds.
					for ( let c = cStart; c < cEnd; c += 6 ) {

						const center = triangleBounds[ c + 2 * a ];
						for ( let bi = 0; bi < splitCount; bi ++ ) {

							const bin = truncatedBins[ bi ];
							if ( center >= bin.candidate ) {

								expandByTriangleBounds( c, triangleBounds, bin.rightCacheBounds );

							} else {

								expandByTriangleBounds( c, triangleBounds, bin.leftCacheBounds );
								bin.count ++;

							}

						}

					}

					// expand all the bounds
					for ( let bi = 0; bi < splitCount; bi ++ ) {

						const bin = truncatedBins[ bi ];
						const leftCount = bin.count;
						const rightCount = count - bin.count;

						// check the cost of this split
						const leftBounds = bin.leftCacheBounds;
						const rightBounds = bin.rightCacheBounds;

						let leftProb = 0;
						if ( leftCount !== 0 ) {

							leftProb = computeSurfaceArea( leftBounds ) / rootSurfaceArea;

						}

						let rightProb = 0;
						if ( rightCount !== 0 ) {

							rightProb = computeSurfaceArea( rightBounds ) / rootSurfaceArea;

						}

						const cost = TRAVERSAL_COST + TRIANGLE_INTERSECT_COST * (
							leftProb * leftCount + rightProb * rightCount
						);

						if ( cost < bestCost ) {

							axis = a;
							bestCost = cost;
							pos = bin.candidate;

						}

					}

				} else {

					// reset the bins
					for ( let i = 0; i < BIN_COUNT; i ++ ) {

						const bin = sahBins[ i ];
						bin.count = 0;
						bin.candidate = axisLeft + binWidth + i * binWidth;

						const bounds = bin.bounds;
						for ( let d = 0; d < 3; d ++ ) {

							bounds[ d ] = Infinity;
							bounds[ d + 3 ] = - Infinity;

						}

					}

					// iterate over all center positions
					for ( let c = cStart; c < cEnd; c += 6 ) {

						const triCenter = triangleBounds[ c + 2 * a ];
						const relativeCenter = triCenter - axisLeft;

						// in the partition function if the centroid lies on the split plane then it is
						// considered to be on the right side of the split
						let binIndex = ~ ~ ( relativeCenter / binWidth );
						if ( binIndex >= BIN_COUNT ) binIndex = BIN_COUNT - 1;

						const bin = sahBins[ binIndex ];
						bin.count ++;

						expandByTriangleBounds( c, triangleBounds, bin.bounds );

					}

					// cache the unioned bounds from right to left so we don't have to regenerate them each time
					const lastBin = sahBins[ BIN_COUNT - 1 ];
					copyBounds( lastBin.bounds, lastBin.rightCacheBounds );
					for ( let i = BIN_COUNT - 2; i >= 0; i -- ) {

						const bin = sahBins[ i ];
						const nextBin = sahBins[ i + 1 ];
						unionBounds( bin.bounds, nextBin.rightCacheBounds, bin.rightCacheBounds );

					}

					let leftCount = 0;
					for ( let i = 0; i < BIN_COUNT - 1; i ++ ) {

						const bin = sahBins[ i ];
						const binCount = bin.count;
						const bounds = bin.bounds;

						const nextBin = sahBins[ i + 1 ];
						const rightBounds = nextBin.rightCacheBounds;

						// dont do anything with the bounds if the new bounds have no triangles
						if ( binCount !== 0 ) {

							if ( leftCount === 0 ) {

								copyBounds( bounds, leftBounds );

							} else {

								unionBounds( bounds, leftBounds, leftBounds );

							}

						}

						leftCount += binCount;

						// check the cost of this split
						let leftProb = 0;
						let rightProb = 0;

						if ( leftCount !== 0 ) {

							leftProb = computeSurfaceArea( leftBounds ) / rootSurfaceArea;

						}

						const rightCount = count - leftCount;
						if ( rightCount !== 0 ) {

							rightProb = computeSurfaceArea( rightBounds ) / rootSurfaceArea;

						}

						const cost = TRAVERSAL_COST + TRIANGLE_INTERSECT_COST * (
							leftProb * leftCount + rightProb * rightCount
						);

						if ( cost < bestCost ) {

							axis = a;
							bestCost = cost;
							pos = bin.candidate;

						}

					}

				}

			}

		} else {

			console.warn( `MeshBVH: Invalid build strategy value ${ strategy } used.` );

		}

		return { axis, pos };

	}

	// returns the average coordinate on the specified axis of the all the provided triangles
	function getAverage( triangleBounds, offset, count, axis ) {

		let avg = 0;
		for ( let i = offset, end = offset + count; i < end; i ++ ) {

			avg += triangleBounds[ i * 6 + axis * 2 ];

		}

		return avg / count;

	}

	// precomputes the bounding box for each triangle; required for quickly calculating tree splits.
	// result is an array of size tris.length * 6 where triangle i maps to a
	// [x_center, x_delta, y_center, y_delta, z_center, z_delta] tuple starting at index i * 6,
	// representing the center and half-extent in each dimension of triangle i
	function computeTriangleBounds( geo, fullBounds ) {

		const posAttr = geo.attributes.position;
		const posArr = posAttr.array;
		const index = geo.index.array;
		const triCount = index.length / 3;
		const triangleBounds = new Float32Array( triCount * 6 );

		// support for an interleaved position buffer
		const bufferOffset = posAttr.offset || 0;
		let stride = 3;
		if ( posAttr.isInterleavedBufferAttribute ) {

			stride = posAttr.data.stride;

		}

		for ( let tri = 0; tri < triCount; tri ++ ) {

			const tri3 = tri * 3;
			const tri6 = tri * 6;
			const ai = index[ tri3 + 0 ] * stride + bufferOffset;
			const bi = index[ tri3 + 1 ] * stride + bufferOffset;
			const ci = index[ tri3 + 2 ] * stride + bufferOffset;

			for ( let el = 0; el < 3; el ++ ) {

				const a = posArr[ ai + el ];
				const b = posArr[ bi + el ];
				const c = posArr[ ci + el ];

				let min = a;
				if ( b < min ) min = b;
				if ( c < min ) min = c;

				let max = a;
				if ( b > max ) max = b;
				if ( c > max ) max = c;

				// Increase the bounds size by float32 epsilon to avoid precision errors when
				// converting to 32 bit float. Scale the epsilon by the size of the numbers being
				// worked with.
				const halfExtents = ( max - min ) / 2;
				const el2 = el * 2;
				triangleBounds[ tri6 + el2 + 0 ] = min + halfExtents;
				triangleBounds[ tri6 + el2 + 1 ] = halfExtents + ( Math.abs( min ) + halfExtents ) * FLOAT32_EPSILON;

				if ( min < fullBounds[ el ] ) fullBounds[ el ] = min;
				if ( max > fullBounds[ el + 3 ] ) fullBounds[ el + 3 ] = max;

			}

		}

		return triangleBounds;

	}

	function buildTree( geo, options ) {

		function triggerProgress( trianglesProcessed ) {

			if ( onProgress ) {

				onProgress( trianglesProcessed / totalTriangles );

			}

		}

		// either recursively splits the given node, creating left and right subtrees for it, or makes it a leaf node,
		// recording the offset and count of its triangles and writing them into the reordered geometry index.
		function splitNode( node, offset, count, centroidBoundingData = null, depth = 0 ) {

			if ( ! reachedMaxDepth && depth >= maxDepth ) {

				reachedMaxDepth = true;
				if ( verbose ) {

					console.warn( `MeshBVH: Max depth of ${ maxDepth } reached when generating BVH. Consider increasing maxDepth.` );
					console.warn( geo );

				}

			}

			// early out if we've met our capacity
			if ( count <= maxLeafTris || depth >= maxDepth ) {

				triggerProgress( offset );
				node.offset = offset;
				node.count = count;
				return node;

			}

			// Find where to split the volume
			const split = getOptimalSplit( node.boundingData, centroidBoundingData, triangleBounds, offset, count, strategy );
			if ( split.axis === - 1 ) {

				triggerProgress( offset );
				node.offset = offset;
				node.count = count;
				return node;

			}

			const splitOffset = partition( indexArray, triangleBounds, offset, count, split );

			// create the two new child nodes
			if ( splitOffset === offset || splitOffset === offset + count ) {

				triggerProgress( offset );
				node.offset = offset;
				node.count = count;

			} else {

				node.splitAxis = split.axis;

				// create the left child and compute its bounding box
				const left = new MeshBVHNode();
				const lstart = offset;
				const lcount = splitOffset - offset;
				node.left = left;
				left.boundingData = new Float32Array( 6 );

				getBounds( triangleBounds, lstart, lcount, left.boundingData, cacheCentroidBoundingData );
				splitNode( left, lstart, lcount, cacheCentroidBoundingData, depth + 1 );

				// repeat for right
				const right = new MeshBVHNode();
				const rstart = splitOffset;
				const rcount = count - lcount;
				node.right = right;
				right.boundingData = new Float32Array( 6 );

				getBounds( triangleBounds, rstart, rcount, right.boundingData, cacheCentroidBoundingData );
				splitNode( right, rstart, rcount, cacheCentroidBoundingData, depth + 1 );

			}

			return node;

		}

		ensureIndex( geo, options );

		// Compute the full bounds of the geometry at the same time as triangle bounds because
		// we'll need it for the root bounds in the case with no groups and it should be fast here.
		// We can't use the geometrying bounding box if it's available because it may be out of date.
		const fullBounds = new Float32Array( 6 );
		const cacheCentroidBoundingData = new Float32Array( 6 );
		const triangleBounds = computeTriangleBounds( geo, fullBounds );
		const indexArray = geo.index.array;
		const maxDepth = options.maxDepth;
		const verbose = options.verbose;
		const maxLeafTris = options.maxLeafTris;
		const strategy = options.strategy;
		const onProgress = options.onProgress;
		const totalTriangles = geo.index.count / 3;
		let reachedMaxDepth = false;

		const roots = [];
		const ranges = getRootIndexRanges( geo );

		if ( ranges.length === 1 ) {

			const range = ranges[ 0 ];
			const root = new MeshBVHNode();
			root.boundingData = fullBounds;
			getCentroidBounds( triangleBounds, range.offset, range.count, cacheCentroidBoundingData );

			splitNode( root, range.offset, range.count, cacheCentroidBoundingData );
			roots.push( root );

		} else {

			for ( let range of ranges ) {

				const root = new MeshBVHNode();
				root.boundingData = new Float32Array( 6 );
				getBounds( triangleBounds, range.offset, range.count, root.boundingData, cacheCentroidBoundingData );

				splitNode( root, range.offset, range.count, cacheCentroidBoundingData );
				roots.push( root );

			}

		}

		return roots;

	}

	function buildPackedTree( geo, options ) {

		// boundingData  				: 6 float32
		// right / offset 				: 1 uint32
		// splitAxis / isLeaf + count 	: 1 uint32 / 2 uint16
		const roots = buildTree( geo, options );

		let float32Array;
		let uint32Array;
		let uint16Array;
		const packedRoots = [];
		const BufferConstructor = options.useSharedArrayBuffer ? SharedArrayBuffer : ArrayBuffer;
		for ( let i = 0; i < roots.length; i ++ ) {

			const root = roots[ i ];
			let nodeCount = countNodes( root );

			const buffer = new BufferConstructor( BYTES_PER_NODE * nodeCount );
			float32Array = new Float32Array( buffer );
			uint32Array = new Uint32Array( buffer );
			uint16Array = new Uint16Array( buffer );
			populateBuffer( 0, root );
			packedRoots.push( buffer );

		}

		return packedRoots;

		function countNodes( node ) {

			if ( node.count ) {

				return 1;

			} else {

				return 1 + countNodes( node.left ) + countNodes( node.right );

			}

		}

		function populateBuffer( byteOffset, node ) {

			const stride4Offset = byteOffset / 4;
			const stride2Offset = byteOffset / 2;
			const isLeaf = ! ! node.count;
			const boundingData = node.boundingData;
			for ( let i = 0; i < 6; i ++ ) {

				float32Array[ stride4Offset + i ] = boundingData[ i ];

			}

			if ( isLeaf ) {

				const offset = node.offset;
				const count = node.count;
				uint32Array[ stride4Offset + 6 ] = offset;
				uint16Array[ stride2Offset + 14 ] = count;
				uint16Array[ stride2Offset + 15 ] = IS_LEAFNODE_FLAG;
				return byteOffset + BYTES_PER_NODE;

			} else {

				const left = node.left;
				const right = node.right;
				const splitAxis = node.splitAxis;

				let nextUnusedPointer;
				nextUnusedPointer = populateBuffer( byteOffset + BYTES_PER_NODE, left );

				if ( ( nextUnusedPointer / 4 ) > Math.pow( 2, 32 ) ) {

					throw new Error( 'MeshBVH: Cannot store child pointer greater than 32 bits.' );

				}

				uint32Array[ stride4Offset + 6 ] = nextUnusedPointer / 4;
				nextUnusedPointer = populateBuffer( nextUnusedPointer, right );

				uint32Array[ stride4Offset + 7 ] = splitAxis;
				return nextUnusedPointer;

			}

		}

	}

	class SeparatingAxisBounds {

		constructor() {

			this.min = Infinity;
			this.max = - Infinity;

		}

		setFromPointsField( points, field ) {

			let min = Infinity;
			let max = - Infinity;
			for ( let i = 0, l = points.length; i < l; i ++ ) {

				const p = points[ i ];
				const val = p[ field ];
				min = val < min ? val : min;
				max = val > max ? val : max;

			}

			this.min = min;
			this.max = max;

		}

		setFromPoints( axis, points ) {

			let min = Infinity;
			let max = - Infinity;
			for ( let i = 0, l = points.length; i < l; i ++ ) {

				const p = points[ i ];
				const val = axis.dot( p );
				min = val < min ? val : min;
				max = val > max ? val : max;

			}

			this.min = min;
			this.max = max;

		}

		isSeparated( other ) {

			return this.min > other.max || other.min > this.max;

		}

	}

	SeparatingAxisBounds.prototype.setFromBox = ( function () {

		const p = new three.Vector3();
		return function setFromBox( axis, box ) {

			const boxMin = box.min;
			const boxMax = box.max;
			let min = Infinity;
			let max = - Infinity;
			for ( let x = 0; x <= 1; x ++ ) {

				for ( let y = 0; y <= 1; y ++ ) {

					for ( let z = 0; z <= 1; z ++ ) {

						p.x = boxMin.x * x + boxMax.x * ( 1 - x );
						p.y = boxMin.y * y + boxMax.y * ( 1 - y );
						p.z = boxMin.z * z + boxMax.z * ( 1 - z );

						const val = axis.dot( p );
						min = Math.min( val, min );
						max = Math.max( val, max );

					}

				}

			}

			this.min = min;
			this.max = max;

		};

	} )();

	const areIntersecting = ( function () {

		const cacheSatBounds = new SeparatingAxisBounds();
		return function areIntersecting( shape1, shape2 ) {

			const points1 = shape1.points;
			const satAxes1 = shape1.satAxes;
			const satBounds1 = shape1.satBounds;

			const points2 = shape2.points;
			const satAxes2 = shape2.satAxes;
			const satBounds2 = shape2.satBounds;

			// check axes of the first shape
			for ( let i = 0; i < 3; i ++ ) {

				const sb = satBounds1[ i ];
				const sa = satAxes1[ i ];
				cacheSatBounds.setFromPoints( sa, points2 );
				if ( sb.isSeparated( cacheSatBounds ) ) return false;

			}

			// check axes of the second shape
			for ( let i = 0; i < 3; i ++ ) {

				const sb = satBounds2[ i ];
				const sa = satAxes2[ i ];
				cacheSatBounds.setFromPoints( sa, points1 );
				if ( sb.isSeparated( cacheSatBounds ) ) return false;

			}

		};

	} )();

	const closestPointLineToLine = ( function () {

		// https://github.com/juj/MathGeoLib/blob/master/src/Geometry/Line.cpp#L56
		const dir1 = new three.Vector3();
		const dir2 = new three.Vector3();
		const v02 = new three.Vector3();
		return function closestPointLineToLine( l1, l2, result ) {

			const v0 = l1.start;
			const v10 = dir1;
			const v2 = l2.start;
			const v32 = dir2;

			v02.subVectors( v0, v2 );
			dir1.subVectors( l1.end, l2.start );
			dir2.subVectors( l2.end, l2.start );

			// float d0232 = v02.Dot(v32);
			const d0232 = v02.dot( v32 );

			// float d3210 = v32.Dot(v10);
			const d3210 = v32.dot( v10 );

			// float d3232 = v32.Dot(v32);
			const d3232 = v32.dot( v32 );

			// float d0210 = v02.Dot(v10);
			const d0210 = v02.dot( v10 );

			// float d1010 = v10.Dot(v10);
			const d1010 = v10.dot( v10 );

			// float denom = d1010*d3232 - d3210*d3210;
			const denom = d1010 * d3232 - d3210 * d3210;

			let d, d2;
			if ( denom !== 0 ) {

				d = ( d0232 * d3210 - d0210 * d3232 ) / denom;

			} else {

				d = 0;

			}

			d2 = ( d0232 + d * d3210 ) / d3232;

			result.x = d;
			result.y = d2;

		};

	} )();

	const closestPointsSegmentToSegment = ( function () {

		// https://github.com/juj/MathGeoLib/blob/master/src/Geometry/LineSegment.cpp#L187
		const paramResult = new three.Vector2();
		const temp1 = new three.Vector3();
		const temp2 = new three.Vector3();
		return function closestPointsSegmentToSegment( l1, l2, target1, target2 ) {

			closestPointLineToLine( l1, l2, paramResult );

			let d = paramResult.x;
			let d2 = paramResult.y;
			if ( d >= 0 && d <= 1 && d2 >= 0 && d2 <= 1 ) {

				l1.at( d, target1 );
				l2.at( d2, target2 );

				return;

			} else if ( d >= 0 && d <= 1 ) {

				// Only d2 is out of bounds.
				if ( d2 < 0 ) {

					l2.at( 0, target2 );

				} else {

					l2.at( 1, target2 );

				}

				l1.closestPointToPoint( target2, true, target1 );
				return;

			} else if ( d2 >= 0 && d2 <= 1 ) {

				// Only d is out of bounds.
				if ( d < 0 ) {

					l1.at( 0, target1 );

				} else {

					l1.at( 1, target1 );

				}

				l2.closestPointToPoint( target1, true, target2 );
				return;

			} else {

				// Both u and u2 are out of bounds.
				let p;
				if ( d < 0 ) {

					p = l1.start;

				} else {

					p = l1.end;

				}

				let p2;
				if ( d2 < 0 ) {

					p2 = l2.start;

				} else {

					p2 = l2.end;

				}

				const closestPoint = temp1;
				const closestPoint2 = temp2;
				l1.closestPointToPoint( p2, true, temp1 );
				l2.closestPointToPoint( p, true, temp2 );

				if ( closestPoint.distanceToSquared( p2 ) <= closestPoint2.distanceToSquared( p ) ) {

					target1.copy( closestPoint );
					target2.copy( p2 );
					return;

				} else {

					target1.copy( p );
					target2.copy( closestPoint2 );
					return;

				}

			}

		};

	} )();


	const sphereIntersectTriangle = ( function () {

		// https://stackoverflow.com/questions/34043955/detect-collision-between-sphere-and-triangle-in-three-js
		const closestPointTemp = new three.Vector3();
		const projectedPointTemp = new three.Vector3();
		const planeTemp = new three.Plane();
		const lineTemp = new three.Line3();
		return function sphereIntersectTriangle( sphere, triangle ) {

			const { radius, center } = sphere;
			const { a, b, c } = triangle;

			// phase 1
			lineTemp.start = a;
			lineTemp.end = b;
			const closestPoint1 = lineTemp.closestPointToPoint( center, true, closestPointTemp );
			if ( closestPoint1.distanceTo( center ) <= radius ) return true;

			lineTemp.start = a;
			lineTemp.end = c;
			const closestPoint2 = lineTemp.closestPointToPoint( center, true, closestPointTemp );
			if ( closestPoint2.distanceTo( center ) <= radius ) return true;

			lineTemp.start = b;
			lineTemp.end = c;
			const closestPoint3 = lineTemp.closestPointToPoint( center, true, closestPointTemp );
			if ( closestPoint3.distanceTo( center ) <= radius ) return true;

			// phase 2
			const plane = triangle.getPlane( planeTemp );
			const dp = Math.abs( plane.distanceToPoint( center ) );
			if ( dp <= radius ) {

				const pp = plane.projectPoint( center, projectedPointTemp );
				const cp = triangle.containsPoint( pp );
				if ( cp ) return true;

			}

			return false;

		};

	} )();

	class SeparatingAxisTriangle extends three.Triangle {

		constructor( ...args ) {

			super( ...args );

			this.isSeparatingAxisTriangle = true;
			this.satAxes = new Array( 4 ).fill().map( () => new three.Vector3() );
			this.satBounds = new Array( 4 ).fill().map( () => new SeparatingAxisBounds() );
			this.points = [ this.a, this.b, this.c ];
			this.sphere = new three.Sphere();
			this.plane = new three.Plane();
			this.needsUpdate = false;

		}

		intersectsSphere( sphere ) {

			return sphereIntersectTriangle( sphere, this );

		}

		update() {

			const a = this.a;
			const b = this.b;
			const c = this.c;
			const points = this.points;

			const satAxes = this.satAxes;
			const satBounds = this.satBounds;

			const axis0 = satAxes[ 0 ];
			const sab0 = satBounds[ 0 ];
			this.getNormal( axis0 );
			sab0.setFromPoints( axis0, points );

			const axis1 = satAxes[ 1 ];
			const sab1 = satBounds[ 1 ];
			axis1.subVectors( a, b );
			sab1.setFromPoints( axis1, points );

			const axis2 = satAxes[ 2 ];
			const sab2 = satBounds[ 2 ];
			axis2.subVectors( b, c );
			sab2.setFromPoints( axis2, points );

			const axis3 = satAxes[ 3 ];
			const sab3 = satBounds[ 3 ];
			axis3.subVectors( c, a );
			sab3.setFromPoints( axis3, points );

			this.sphere.setFromPoints( this.points );
			this.plane.setFromNormalAndCoplanarPoint( axis0, a );
			this.needsUpdate = false;

		}

	}

	SeparatingAxisTriangle.prototype.closestPointToSegment = ( function () {

		const point1 = new three.Vector3();
		const point2 = new three.Vector3();
		const edge = new three.Line3();

		return function distanceToSegment( segment, target1 = null, target2 = null ) {

			const { start, end } = segment;
			const points = this.points;
			let distSq;
			let closestDistanceSq = Infinity;

			// check the triangle edges
			for ( let i = 0; i < 3; i ++ ) {

				const nexti = ( i + 1 ) % 3;
				edge.start.copy( points[ i ] );
				edge.end.copy( points[ nexti ] );

				closestPointsSegmentToSegment( edge, segment, point1, point2 );

				distSq = point1.distanceToSquared( point2 );
				if ( distSq < closestDistanceSq ) {

					closestDistanceSq = distSq;
					if ( target1 ) target1.copy( point1 );
					if ( target2 ) target2.copy( point2 );

				}

			}

			// check end points
			this.closestPointToPoint( start, point1 );
			distSq = start.distanceToSquared( point1 );
			if ( distSq < closestDistanceSq ) {

				closestDistanceSq = distSq;
				if ( target1 ) target1.copy( point1 );
				if ( target2 ) target2.copy( start );

			}

			this.closestPointToPoint( end, point1 );
			distSq = end.distanceToSquared( point1 );
			if ( distSq < closestDistanceSq ) {

				closestDistanceSq = distSq;
				if ( target1 ) target1.copy( point1 );
				if ( target2 ) target2.copy( end );

			}

			return Math.sqrt( closestDistanceSq );

		};

	} )();

	SeparatingAxisTriangle.prototype.intersectsTriangle = ( function () {

		const saTri2 = new SeparatingAxisTriangle();
		const arr1 = new Array( 3 );
		const arr2 = new Array( 3 );
		const cachedSatBounds = new SeparatingAxisBounds();
		const cachedSatBounds2 = new SeparatingAxisBounds();
		const cachedAxis = new three.Vector3();
		const dir1 = new three.Vector3();
		const dir2 = new three.Vector3();
		const tempDir = new three.Vector3();
		const edge = new three.Line3();
		const edge1 = new three.Line3();
		const edge2 = new three.Line3();

		// TODO: If the triangles are coplanar and intersecting the target is nonsensical. It should at least
		// be a line contained by both triangles if not a different special case somehow represented in the return result.
		return function intersectsTriangle( other, target = null ) {

			if ( this.needsUpdate ) {

				this.update();

			}

			if ( ! other.isSeparatingAxisTriangle ) {

				saTri2.copy( other );
				saTri2.update();
				other = saTri2;

			} else if ( other.needsUpdate ) {

				other.update();

			}

			const satBounds1 = this.satBounds;
			const satAxes1 = this.satAxes;
			arr2[ 0 ] = other.a;
			arr2[ 1 ] = other.b;
			arr2[ 2 ] = other.c;
			for ( let i = 0; i < 4; i ++ ) {

				const sb = satBounds1[ i ];
				const sa = satAxes1[ i ];
				cachedSatBounds.setFromPoints( sa, arr2 );
				if ( sb.isSeparated( cachedSatBounds ) ) return false;

			}

			const satBounds2 = other.satBounds;
			const satAxes2 = other.satAxes;
			arr1[ 0 ] = this.a;
			arr1[ 1 ] = this.b;
			arr1[ 2 ] = this.c;
			for ( let i = 0; i < 4; i ++ ) {

				const sb = satBounds2[ i ];
				const sa = satAxes2[ i ];
				cachedSatBounds.setFromPoints( sa, arr1 );
				if ( sb.isSeparated( cachedSatBounds ) ) return false;

			}

			// check crossed axes
			for ( let i = 0; i < 4; i ++ ) {

				const sa1 = satAxes1[ i ];
				for ( let i2 = 0; i2 < 4; i2 ++ ) {

					const sa2 = satAxes2[ i2 ];
					cachedAxis.crossVectors( sa1, sa2 );
					cachedSatBounds.setFromPoints( cachedAxis, arr1 );
					cachedSatBounds2.setFromPoints( cachedAxis, arr2 );
					if ( cachedSatBounds.isSeparated( cachedSatBounds2 ) ) return false;

				}

			}

			if ( target ) {

				const plane1 = this.plane;
				const plane2 = other.plane;

				if ( Math.abs( plane1.normal.dot( plane2.normal ) ) > 1.0 - 1e-10 ) {

					// TODO find two points that intersect on the edges and make that the result
					console.warn( 'SeparatingAxisTriangle.intersectsTriangle: Triangles are coplanar which does not support an output edge. Setting edge to 0, 0, 0.' );
					target.start.set( 0, 0, 0 );
					target.end.set( 0, 0, 0 );

				} else {

					// find the edge that intersects the other triangle plane
					const points1 = this.points;
					let found1 = false;
					for ( let i = 0; i < 3; i ++ ) {

						const p1 = points1[ i ];
						const p2 = points1[ ( i + 1 ) % 3 ];

						edge.start.copy( p1 );
						edge.end.copy( p2 );

						if ( plane2.intersectLine( edge, found1 ? edge1.start : edge1.end ) ) {

							if ( found1 ) {

								break;

							}

							found1 = true;

						}

					}

					// find the other triangles edge that intersects this plane
					const points2 = other.points;
					let found2 = false;
					for ( let i = 0; i < 3; i ++ ) {

						const p1 = points2[ i ];
						const p2 = points2[ ( i + 1 ) % 3 ];

						edge.start.copy( p1 );
						edge.end.copy( p2 );

						if ( plane1.intersectLine( edge, found2 ? edge2.start : edge2.end ) ) {

							if ( found2 ) {

								break;

							}

							found2 = true;

						}

					}

					// find swap the second edge so both lines are running the same direction
					edge1.delta( dir1 );
					edge2.delta( dir2 );


					if ( dir1.dot( dir2 ) < 0 ) {

						let tmp = edge2.start;
						edge2.start = edge2.end;
						edge2.end = tmp;

					}

					tempDir.subVectors( edge1.start, edge2.start );
					if ( tempDir.dot( dir1 ) > 0 ) {

						target.start.copy( edge1.start );

					} else {

						target.start.copy( edge2.start );

					}

					tempDir.subVectors( edge1.end, edge2.end );
					if ( tempDir.dot( dir1 ) < 0 ) {

						target.end.copy( edge1.end );

					} else {

						target.end.copy( edge2.end );

					}

				}

			}

			return true;

		};

	} )();


	SeparatingAxisTriangle.prototype.distanceToPoint = ( function () {

		const target = new three.Vector3();
		return function distanceToPoint( point ) {

			this.closestPointToPoint( point, target );
			return point.distanceTo( target );

		};

	} )();


	SeparatingAxisTriangle.prototype.distanceToTriangle = ( function () {

		const point = new three.Vector3();
		const point2 = new three.Vector3();
		const cornerFields = [ 'a', 'b', 'c' ];
		const line1 = new three.Line3();
		const line2 = new three.Line3();

		return function distanceToTriangle( other, target1 = null, target2 = null ) {

			const lineTarget = target1 || target2 ? line1 : null;
			if ( this.intersectsTriangle( other, lineTarget ) ) {

				if ( target1 || target2 ) {

					if ( target1 ) lineTarget.getCenter( target1 );
					if ( target2 ) lineTarget.getCenter( target2 );

				}

				return 0;

			}

			let closestDistanceSq = Infinity;

			// check all point distances
			for ( let i = 0; i < 3; i ++ ) {

				let dist;
				const field = cornerFields[ i ];
				const otherVec = other[ field ];
				this.closestPointToPoint( otherVec, point );

				dist = otherVec.distanceToSquared( point );

				if ( dist < closestDistanceSq ) {

					closestDistanceSq = dist;
					if ( target1 ) target1.copy( point );
					if ( target2 ) target2.copy( otherVec );

				}


				const thisVec = this[ field ];
				other.closestPointToPoint( thisVec, point );

				dist = thisVec.distanceToSquared( point );

				if ( dist < closestDistanceSq ) {

					closestDistanceSq = dist;
					if ( target1 ) target1.copy( thisVec );
					if ( target2 ) target2.copy( point );

				}

			}

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

				const f11 = cornerFields[ i ];
				const f12 = cornerFields[ ( i + 1 ) % 3 ];
				line1.set( this[ f11 ], this[ f12 ] );
				for ( let i2 = 0; i2 < 3; i2 ++ ) {

					const f21 = cornerFields[ i2 ];
					const f22 = cornerFields[ ( i2 + 1 ) % 3 ];
					line2.set( other[ f21 ], other[ f22 ] );

					closestPointsSegmentToSegment( line1, line2, point, point2 );

					const dist = point.distanceToSquared( point2 );
					if ( dist < closestDistanceSq ) {

						closestDistanceSq = dist;
						if ( target1 ) target1.copy( point );
						if ( target2 ) target2.copy( point2 );

					}

				}

			}

			return Math.sqrt( closestDistanceSq );

		};

	} )();

	class OrientedBox extends three.Box3 {

		constructor( ...args ) {

			super( ...args );

			this.isOrientedBox = true;
			this.matrix = new three.Matrix4();
			this.invMatrix = new three.Matrix4();
			this.points = new Array( 8 ).fill().map( () => new three.Vector3() );
			this.satAxes = new Array( 3 ).fill().map( () => new three.Vector3() );
			this.satBounds = new Array( 3 ).fill().map( () => new SeparatingAxisBounds() );
			this.alignedSatBounds = new Array( 3 ).fill().map( () => new SeparatingAxisBounds() );
			this.needsUpdate = false;

		}

		set( min, max, matrix ) {

			super.set( min, max );
			this.matrix = matrix;
			this.needsUpdate = true;

		}

		copy( other ) {

			super.copy( other );
			this.matrix.copy( other.matrix );
			this.needsUpdate = true;

		}

	}

	OrientedBox.prototype.update = ( function () {

		return function update() {

			const matrix = this.matrix;
			const min = this.min;
			const max = this.max;

			const points = this.points;
			for ( let x = 0; x <= 1; x ++ ) {

				for ( let y = 0; y <= 1; y ++ ) {

					for ( let z = 0; z <= 1; z ++ ) {

						const i = ( ( 1 << 0 ) * x ) | ( ( 1 << 1 ) * y ) | ( ( 1 << 2 ) * z );
						const v = points[ i ];
						v.x = x ? max.x : min.x;
						v.y = y ? max.y : min.y;
						v.z = z ? max.z : min.z;

						v.applyMatrix4( matrix );

					}

				}

			}

			const satBounds = this.satBounds;
			const satAxes = this.satAxes;
			const minVec = points[ 0 ];
			for ( let i = 0; i < 3; i ++ ) {

				const axis = satAxes[ i ];
				const sb = satBounds[ i ];
				const index = 1 << i;
				const pi = points[ index ];

				axis.subVectors( minVec, pi );
				sb.setFromPoints( axis, points );

			}

			const alignedSatBounds = this.alignedSatBounds;
			alignedSatBounds[ 0 ].setFromPointsField( points, 'x' );
			alignedSatBounds[ 1 ].setFromPointsField( points, 'y' );
			alignedSatBounds[ 2 ].setFromPointsField( points, 'z' );

			this.invMatrix.copy( this.matrix ).invert();
			this.needsUpdate = false;

		};

	} )();

	OrientedBox.prototype.intersectsBox = ( function () {

		const aabbBounds = new SeparatingAxisBounds();
		return function intersectsBox( box ) {

			// TODO: should this be doing SAT against the AABB?
			if ( this.needsUpdate ) {

				this.update();

			}

			const min = box.min;
			const max = box.max;
			const satBounds = this.satBounds;
			const satAxes = this.satAxes;
			const alignedSatBounds = this.alignedSatBounds;

			aabbBounds.min = min.x;
			aabbBounds.max = max.x;
			if ( alignedSatBounds[ 0 ].isSeparated( aabbBounds ) ) return false;

			aabbBounds.min = min.y;
			aabbBounds.max = max.y;
			if ( alignedSatBounds[ 1 ].isSeparated( aabbBounds ) ) return false;

			aabbBounds.min = min.z;
			aabbBounds.max = max.z;
			if ( alignedSatBounds[ 2 ].isSeparated( aabbBounds ) ) return false;

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

				const axis = satAxes[ i ];
				const sb = satBounds[ i ];
				aabbBounds.setFromBox( axis, box );
				if ( sb.isSeparated( aabbBounds ) ) return false;

			}

			return true;

		};

	} )();

	OrientedBox.prototype.intersectsTriangle = ( function () {

		const saTri = new SeparatingAxisTriangle();
		const pointsArr = new Array( 3 );
		const cachedSatBounds = new SeparatingAxisBounds();
		const cachedSatBounds2 = new SeparatingAxisBounds();
		const cachedAxis = new three.Vector3();
		return function intersectsTriangle( triangle ) {

			if ( this.needsUpdate ) {

				this.update();

			}

			if ( ! triangle.isSeparatingAxisTriangle ) {

				saTri.copy( triangle );
				saTri.update();
				triangle = saTri;

			} else if ( triangle.needsUpdate ) {

				triangle.update();

			}

			const satBounds = this.satBounds;
			const satAxes = this.satAxes;

			pointsArr[ 0 ] = triangle.a;
			pointsArr[ 1 ] = triangle.b;
			pointsArr[ 2 ] = triangle.c;

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

				const sb = satBounds[ i ];
				const sa = satAxes[ i ];
				cachedSatBounds.setFromPoints( sa, pointsArr );
				if ( sb.isSeparated( cachedSatBounds ) ) return false;

			}

			const triSatBounds = triangle.satBounds;
			const triSatAxes = triangle.satAxes;
			const points = this.points;
			for ( let i = 0; i < 3; i ++ ) {

				const sb = triSatBounds[ i ];
				const sa = triSatAxes[ i ];
				cachedSatBounds.setFromPoints( sa, points );
				if ( sb.isSeparated( cachedSatBounds ) ) return false;

			}

			// check crossed axes
			for ( let i = 0; i < 3; i ++ ) {

				const sa1 = satAxes[ i ];
				for ( let i2 = 0; i2 < 4; i2 ++ ) {

					const sa2 = triSatAxes[ i2 ];
					cachedAxis.crossVectors( sa1, sa2 );
					cachedSatBounds.setFromPoints( cachedAxis, pointsArr );
					cachedSatBounds2.setFromPoints( cachedAxis, points );
					if ( cachedSatBounds.isSeparated( cachedSatBounds2 ) ) return false;

				}

			}

			return true;

		};

	} )();

	OrientedBox.prototype.closestPointToPoint = ( function () {

		return function closestPointToPoint( point, target1 ) {

			if ( this.needsUpdate ) {

				this.update();

			}

			target1
				.copy( point )
				.applyMatrix4( this.invMatrix )
				.clamp( this.min, this.max )
				.applyMatrix4( this.matrix );

			return target1;

		};

	} )();

	OrientedBox.prototype.distanceToPoint = ( function () {

		const target = new three.Vector3();
		return function distanceToPoint( point ) {

			this.closestPointToPoint( point, target );
			return point.distanceTo( target );

		};

	} )();

	OrientedBox.prototype.distanceToBox = ( function () {

		const xyzFields = [ 'x', 'y', 'z' ];
		const segments1 = new Array( 12 ).fill().map( () => new three.Line3() );
		const segments2 = new Array( 12 ).fill().map( () => new three.Line3() );

		const point1 = new three.Vector3();
		const point2 = new three.Vector3();

		// early out if we find a value below threshold
		return function distanceToBox( box, threshold = 0, target1 = null, target2 = null ) {

			if ( this.needsUpdate ) {

				this.update();

			}

			if ( this.intersectsBox( box ) ) {

				if ( target1 || target2 ) {

					box.getCenter( point2 );
					this.closestPointToPoint( point2, point1 );
					box.closestPointToPoint( point1, point2 );

					if ( target1 ) target1.copy( point1 );
					if ( target2 ) target2.copy( point2 );

				}

				return 0;

			}

			const threshold2 = threshold * threshold;
			const min = box.min;
			const max = box.max;
			const points = this.points;


			// iterate over every edge and compare distances
			let closestDistanceSq = Infinity;

			// check over all these points
			for ( let i = 0; i < 8; i ++ ) {

				const p = points[ i ];
				point2.copy( p ).clamp( min, max );

				const dist = p.distanceToSquared( point2 );
				if ( dist < closestDistanceSq ) {

					closestDistanceSq = dist;
					if ( target1 ) target1.copy( p );
					if ( target2 ) target2.copy( point2 );

					if ( dist < threshold2 ) return Math.sqrt( dist );

				}

			}

			// generate and check all line segment distances
			let count = 0;
			for ( let i = 0; i < 3; i ++ ) {

				for ( let i1 = 0; i1 <= 1; i1 ++ ) {

					for ( let i2 = 0; i2 <= 1; i2 ++ ) {

						const nextIndex = ( i + 1 ) % 3;
						const nextIndex2 = ( i + 2 ) % 3;

						// get obb line segments
						const index = i1 << nextIndex | i2 << nextIndex2;
						const index2 = 1 << i | i1 << nextIndex | i2 << nextIndex2;
						const p1 = points[ index ];
						const p2 = points[ index2 ];
						const line1 = segments1[ count ];
						line1.set( p1, p2 );


						// get aabb line segments
						const f1 = xyzFields[ i ];
						const f2 = xyzFields[ nextIndex ];
						const f3 = xyzFields[ nextIndex2 ];
						const line2 = segments2[ count ];
						const start = line2.start;
						const end = line2.end;

						start[ f1 ] = min[ f1 ];
						start[ f2 ] = i1 ? min[ f2 ] : max[ f2 ];
						start[ f3 ] = i2 ? min[ f3 ] : max[ f2 ];

						end[ f1 ] = max[ f1 ];
						end[ f2 ] = i1 ? min[ f2 ] : max[ f2 ];
						end[ f3 ] = i2 ? min[ f3 ] : max[ f2 ];

						count ++;

					}

				}

			}

			// check all the other boxes point
			for ( let x = 0; x <= 1; x ++ ) {

				for ( let y = 0; y <= 1; y ++ ) {

					for ( let z = 0; z <= 1; z ++ ) {

						point2.x = x ? max.x : min.x;
						point2.y = y ? max.y : min.y;
						point2.z = z ? max.z : min.z;

						this.closestPointToPoint( point2, point1 );
						const dist = point2.distanceToSquared( point1 );
						if ( dist < closestDistanceSq ) {

							closestDistanceSq = dist;
							if ( target1 ) target1.copy( point1 );
							if ( target2 ) target2.copy( point2 );

							if ( dist < threshold2 ) return Math.sqrt( dist );

						}

					}

				}

			}

			for ( let i = 0; i < 12; i ++ ) {

				const l1 = segments1[ i ];
				for ( let i2 = 0; i2 < 12; i2 ++ ) {

					const l2 = segments2[ i2 ];
					closestPointsSegmentToSegment( l1, l2, point1, point2 );
					const dist = point1.distanceToSquared( point2 );
					if ( dist < closestDistanceSq ) {

						closestDistanceSq = dist;
						if ( target1 ) target1.copy( point1 );
						if ( target2 ) target2.copy( point2 );

						if ( dist < threshold2 ) return Math.sqrt( dist );

					}

				}

			}

			return Math.sqrt( closestDistanceSq );

		};

	} )();

	// Ripped and modified From THREE.js Mesh raycast
	// https://github.com/mrdoob/three.js/blob/0aa87c999fe61e216c1133fba7a95772b503eddf/src/objects/Mesh.js#L115
	const vA = /* @__PURE__ */ new three.Vector3();
	const vB = /* @__PURE__ */ new three.Vector3();
	const vC = /* @__PURE__ */ new three.Vector3();

	const uvA = /* @__PURE__ */ new three.Vector2();
	const uvB = /* @__PURE__ */ new three.Vector2();
	const uvC = /* @__PURE__ */ new three.Vector2();

	const intersectionPoint = /* @__PURE__ */ new three.Vector3();
	function checkIntersection( ray, pA, pB, pC, point, side ) {

		let intersect;
		if ( side === three.BackSide ) {

			intersect = ray.intersectTriangle( pC, pB, pA, true, point );

		} else {

			intersect = ray.intersectTriangle( pA, pB, pC, side !== three.DoubleSide, point );

		}

		if ( intersect === null ) return null;

		const distance = ray.origin.distanceTo( point );

		return {

			distance: distance,
			point: point.clone(),

		};

	}

	function checkBufferGeometryIntersection( ray, position, uv, a, b, c, side ) {

		vA.fromBufferAttribute( position, a );
		vB.fromBufferAttribute( position, b );
		vC.fromBufferAttribute( position, c );

		const intersection = checkIntersection( ray, vA, vB, vC, intersectionPoint, side );

		if ( intersection ) {

			if ( uv ) {

				uvA.fromBufferAttribute( uv, a );
				uvB.fromBufferAttribute( uv, b );
				uvC.fromBufferAttribute( uv, c );

				intersection.uv = three.Triangle.getUV( intersectionPoint, vA, vB, vC, uvA, uvB, uvC, new three.Vector2( ) );

			}

			const face = {
				a: a,
				b: b,
				c: c,
				normal: new three.Vector3(),
				materialIndex: 0
			};

			three.Triangle.getNormal( vA, vB, vC, face.normal );

			intersection.face = face;
			intersection.faceIndex = a;

		}

		return intersection;

	}

	// https://github.com/mrdoob/three.js/blob/0aa87c999fe61e216c1133fba7a95772b503eddf/src/objects/Mesh.js#L258
	function intersectTri( geo, side, ray, tri, intersections ) {

		const triOffset = tri * 3;
		const a = geo.index.getX( triOffset );
		const b = geo.index.getX( triOffset + 1 );
		const c = geo.index.getX( triOffset + 2 );

		const intersection = checkBufferGeometryIntersection( ray, geo.attributes.position, geo.attributes.uv, a, b, c, side );

		if ( intersection ) {

			intersection.faceIndex = tri;
			if ( intersections ) intersections.push( intersection );
			return intersection;

		}

		return null;

	}

	function intersectTris( geo, side, ray, offset, count, intersections ) {

		for ( let i = offset, end = offset + count; i < end; i ++ ) {

			intersectTri( geo, side, ray, i, intersections );

		}

	}

	function intersectClosestTri( geo, side, ray, offset, count ) {

		let dist = Infinity;
		let res = null;
		for ( let i = offset, end = offset + count; i < end; i ++ ) {

			const intersection = intersectTri( geo, side, ray, i );
			if ( intersection && intersection.distance < dist ) {

				res = intersection;
				dist = intersection.distance;

			}

		}

		return res;

	}

	// converts the given BVH raycast intersection to align with the three.js raycast
	// structure (include object, world space distance and point).
	function convertRaycastIntersect( hit, object, raycaster ) {

		if ( hit === null ) {

			return null;

		}

		hit.point.applyMatrix4( object.matrixWorld );
		hit.distance = hit.point.distanceTo( raycaster.ray.origin );
		hit.object = object;

		if ( hit.distance < raycaster.near || hit.distance > raycaster.far ) {

			return null;

		} else {

			return hit;

		}

	}

	// sets the vertices of triangle `tri` with the 3 vertices after i
	function setTriangle( tri, i, index, pos ) {

		const ta = tri.a;
		const tb = tri.b;
		const tc = tri.c;

		let i0 = i;
		let i1 = i + 1;
		let i2 = i + 2;
		if ( index ) {

			i0 = index.getX( i );
			i1 = index.getX( i + 1 );
			i2 = index.getX( i + 2 );

		}

		ta.x = pos.getX( i0 );
		ta.y = pos.getY( i0 );
		ta.z = pos.getZ( i0 );

		tb.x = pos.getX( i1 );
		tb.y = pos.getY( i1 );
		tb.z = pos.getZ( i1 );

		tc.x = pos.getX( i2 );
		tc.y = pos.getY( i2 );
		tc.z = pos.getZ( i2 );

	}

	function iterateOverTriangles(
		offset,
		count,
		geometry,
		intersectsTriangleFunc,
		contained,
		depth,
		triangle
	) {

		const index = geometry.index;
		const pos = geometry.attributes.position;
		for ( let i = offset, l = count + offset; i < l; i ++ ) {

			setTriangle( triangle, i * 3, index, pos );
			triangle.needsUpdate = true;

			if ( intersectsTriangleFunc( triangle, i, contained, depth ) ) {

				return true;

			}

		}

		return false;

	}

	const tempV1 = /* @__PURE__ */ new three.Vector3();
	const tempV2 = /* @__PURE__ */ new three.Vector3();
	const tempV3 = /* @__PURE__ */ new three.Vector3();
	const tempUV1 = /* @__PURE__ */ new three.Vector2();
	const tempUV2 = /* @__PURE__ */ new three.Vector2();
	const tempUV3 = /* @__PURE__ */ new three.Vector2();

	function getTriangleHitPointInfo( point, geometry, triangleIndex, target ) {

		const indices = geometry.getIndex().array;
		const positions = geometry.getAttribute( 'position' );
		const uvs = geometry.getAttribute( 'uv' );

		const a = indices[ triangleIndex * 3 ];
		const b = indices[ triangleIndex * 3 + 1 ];
		const c = indices[ triangleIndex * 3 + 2 ];

		tempV1.fromBufferAttribute( positions, a );
		tempV2.fromBufferAttribute( positions, b );
		tempV3.fromBufferAttribute( positions, c );

		// find the associated material index
		let materialIndex = 0;
		const groups = geometry.groups;
		const firstVertexIndex = triangleIndex * 3;
		for ( let i = 0, l = groups.length; i < l; i ++ ) {

			const group = groups[ i ];
			const { start, count } = group;
			if ( firstVertexIndex >= start && firstVertexIndex < start + count ) {

				materialIndex = group.materialIndex;
				break;

			}

		}

		// extract uvs
		let uv = null;
		if ( uvs ) {

			tempUV1.fromBufferAttribute( uvs, a );
			tempUV2.fromBufferAttribute( uvs, b );
			tempUV3.fromBufferAttribute( uvs, c );

			if ( target && target.uv ) uv = target.uv;
			else uv = new three.Vector2();

			three.Triangle.getUV( point, tempV1, tempV2, tempV3, tempUV1, tempUV2, tempUV3, uv );

		}

		// adjust the provided target or create a new one
		if ( target ) {

			if ( ! target.face ) target.face = { };
			target.face.a = a;
			target.face.b = b;
			target.face.c = c;
			target.face.materialIndex = materialIndex;
			if ( ! target.face.normal ) target.face.normal = new three.Vector3();
			three.Triangle.getNormal( tempV1, tempV2, tempV3, target.face.normal );

			if ( ! target.uv ) target.uv = new three.Vector2();
			target.uv.copy( uv );

			return target;

		} else {

			return {
				face: {
					a: a,
					b: b,
					c: c,
					materialIndex: materialIndex,
					normal: three.Triangle.getNormal( tempV1, tempV2, tempV3, new three.Vector3() )
				},
				uv: uv
			};

		}

	}

	class PrimitivePool {

		constructor( getNewPrimitive ) {

			this._getNewPrimitive = getNewPrimitive;
			this._primitives = [];

		}

		getPrimitive() {

			const primitives = this._primitives;
			if ( primitives.length === 0 ) {

				return this._getNewPrimitive();

			} else {

				return primitives.pop();

			}

		}

		releasePrimitive( primitive ) {

			this._primitives.push( primitive );

		}

	}

	function IS_LEAF( n16, uint16Array ) {

		return uint16Array[ n16 + 15 ] === 0xFFFF;

	}

	function OFFSET( n32, uint32Array ) {

		return uint32Array[ n32 + 6 ];

	}

	function COUNT( n16, uint16Array ) {

		return uint16Array[ n16 + 14 ];

	}

	function LEFT_NODE( n32 ) {

		return n32 + 8;

	}

	function RIGHT_NODE( n32, uint32Array ) {

		return uint32Array[ n32 + 6 ];

	}

	function SPLIT_AXIS( n32, uint32Array ) {

		return uint32Array[ n32 + 7 ];

	}

	function BOUNDING_DATA_INDEX( n32 ) {

		return n32;

	}

	const boundingBox$1 = new three.Box3();
	const boxIntersection = new three.Vector3();
	const xyzFields = [ 'x', 'y', 'z' ];

	function raycast( nodeIndex32, geometry, side, ray, intersects ) {

		let nodeIndex16 = nodeIndex32 * 2, float32Array = _float32Array, uint16Array = _uint16Array, uint32Array = _uint32Array;

		const isLeaf = IS_LEAF( nodeIndex16, uint16Array );
		if ( isLeaf ) {

			const offset = OFFSET( nodeIndex32, uint32Array );
			const count = COUNT( nodeIndex16, uint16Array );

			intersectTris( geometry, side, ray, offset, count, intersects );

		} else {

			const leftIndex = LEFT_NODE( nodeIndex32 );
			if ( intersectRay( leftIndex, float32Array, ray, boxIntersection ) ) {

				raycast( leftIndex, geometry, side, ray, intersects );

			}

			const rightIndex = RIGHT_NODE( nodeIndex32, uint32Array );
			if ( intersectRay( rightIndex, float32Array, ray, boxIntersection ) ) {

				raycast( rightIndex, geometry, side, ray, intersects );

			}

		}

	}

	function raycastFirst( nodeIndex32, geometry, side, ray ) {

		let nodeIndex16 = nodeIndex32 * 2, float32Array = _float32Array, uint16Array = _uint16Array, uint32Array = _uint32Array;

		const isLeaf = IS_LEAF( nodeIndex16, uint16Array );
		if ( isLeaf ) {

			const offset = OFFSET( nodeIndex32, uint32Array );
			const count = COUNT( nodeIndex16, uint16Array );
			return intersectClosestTri( geometry, side, ray, offset, count );

		} else {

			// consider the position of the split plane with respect to the oncoming ray; whichever direction
			// the ray is coming from, look for an intersection among that side of the tree first
			const splitAxis = SPLIT_AXIS( nodeIndex32, uint32Array );
			const xyzAxis = xyzFields[ splitAxis ];
			const rayDir = ray.direction[ xyzAxis ];
			const leftToRight = rayDir >= 0;

			// c1 is the child to check first
			let c1, c2;
			if ( leftToRight ) {

				c1 = LEFT_NODE( nodeIndex32 );
				c2 = RIGHT_NODE( nodeIndex32, uint32Array );

			} else {

				c1 = RIGHT_NODE( nodeIndex32, uint32Array );
				c2 = LEFT_NODE( nodeIndex32 );

			}

			const c1Intersection = intersectRay( c1, float32Array, ray, boxIntersection );
			const c1Result = c1Intersection ? raycastFirst( c1, geometry, side, ray ) : null;

			// if we got an intersection in the first node and it's closer than the second node's bounding
			// box, we don't need to consider the second node because it couldn't possibly be a better result
			if ( c1Result ) {

				// check if the point is within the second bounds
				// "point" is in the local frame of the bvh
				const point = c1Result.point[ xyzAxis ];
				const isOutside = leftToRight ?
					point <= float32Array[ c2 + splitAxis ] : // min bounding data
					point >= float32Array[ c2 + splitAxis + 3 ]; // max bounding data

				if ( isOutside ) {

					return c1Result;

				}

			}

			// either there was no intersection in the first node, or there could still be a closer
			// intersection in the second, so check the second node and then take the better of the two
			const c2Intersection = intersectRay( c2, float32Array, ray, boxIntersection );
			const c2Result = c2Intersection ? raycastFirst( c2, geometry, side, ray ) : null;

			if ( c1Result && c2Result ) {

				return c1Result.distance <= c2Result.distance ? c1Result : c2Result;

			} else {

				return c1Result || c2Result || null;

			}

		}

	}

	const shapecast = ( function () {

		let _box1, _box2;
		const boxStack = [];
		const boxPool = new PrimitivePool( () => new three.Box3() );

		return function shapecast( ...args ) {

			_box1 = boxPool.getPrimitive();
			_box2 = boxPool.getPrimitive();
			boxStack.push( _box1, _box2 );

			const result = shapecastTraverse( ...args );

			boxPool.releasePrimitive( _box1 );
			boxPool.releasePrimitive( _box2 );
			boxStack.pop();
			boxStack.pop();

			const length = boxStack.length;
			if ( length > 0 ) {

				_box2 = boxStack[ length - 1 ];
				_box1 = boxStack[ length - 2 ];

			}

			return result;

		};

		function shapecastTraverse(
			nodeIndex32,
			geometry,
			intersectsBoundsFunc,
			intersectsRangeFunc,
			nodeScoreFunc = null,
			nodeIndexByteOffset = 0, // offset for unique node identifier
			depth = 0
		) {

			// Define these inside the function so it has access to the local variables needed
			// when converting to the buffer equivalents
			function getLeftOffset( nodeIndex32 ) {

				let nodeIndex16 = nodeIndex32 * 2, uint16Array = _uint16Array, uint32Array = _uint32Array;

				// traverse until we find a leaf
				while ( ! IS_LEAF( nodeIndex16, uint16Array ) ) {

					nodeIndex32 = LEFT_NODE( nodeIndex32 );
					nodeIndex16 = nodeIndex32 * 2;

				}

				return OFFSET( nodeIndex32, uint32Array );

			}

			function getRightEndOffset( nodeIndex32 ) {

				let nodeIndex16 = nodeIndex32 * 2, uint16Array = _uint16Array, uint32Array = _uint32Array;

				// traverse until we find a leaf
				while ( ! IS_LEAF( nodeIndex16, uint16Array ) ) {

					// adjust offset to point to the right node
					nodeIndex32 = RIGHT_NODE( nodeIndex32, uint32Array );
					nodeIndex16 = nodeIndex32 * 2;

				}

				// return the end offset of the triangle range
				return OFFSET( nodeIndex32, uint32Array ) + COUNT( nodeIndex16, uint16Array );

			}

			let nodeIndex16 = nodeIndex32 * 2, float32Array = _float32Array, uint16Array = _uint16Array, uint32Array = _uint32Array;

			const isLeaf = IS_LEAF( nodeIndex16, uint16Array );
			if ( isLeaf ) {

				const offset = OFFSET( nodeIndex32, uint32Array );
				const count = COUNT( nodeIndex16, uint16Array );
				arrayToBox( BOUNDING_DATA_INDEX( nodeIndex32 ), float32Array, _box1 );
				return intersectsRangeFunc( offset, count, false, depth, nodeIndexByteOffset + nodeIndex32, _box1 );

			} else {

				const left = LEFT_NODE( nodeIndex32 );
				const right = RIGHT_NODE( nodeIndex32, uint32Array );
				let c1 = left;
				let c2 = right;

				let score1, score2;
				let box1, box2;
				if ( nodeScoreFunc ) {

					box1 = _box1;
					box2 = _box2;

					// bounding data is not offset
					arrayToBox( BOUNDING_DATA_INDEX( c1 ), float32Array, box1 );
					arrayToBox( BOUNDING_DATA_INDEX( c2 ), float32Array, box2 );

					score1 = nodeScoreFunc( box1 );
					score2 = nodeScoreFunc( box2 );

					if ( score2 < score1 ) {

						c1 = right;
						c2 = left;

						const temp = score1;
						score1 = score2;
						score2 = temp;

						box1 = box2;
						// box2 is always set before use below

					}

				}

				// Check box 1 intersection
				if ( ! box1 ) {

					box1 = _box1;
					arrayToBox( BOUNDING_DATA_INDEX( c1 ), float32Array, box1 );

				}

				const isC1Leaf = IS_LEAF( c1 * 2, uint16Array );
				const c1Intersection = intersectsBoundsFunc( box1, isC1Leaf, score1, depth + 1, nodeIndexByteOffset + c1 );

				let c1StopTraversal;
				if ( c1Intersection === CONTAINED ) {

					const offset = getLeftOffset( c1 );
					const end = getRightEndOffset( c1 );
					const count = end - offset;

					c1StopTraversal = intersectsRangeFunc( offset, count, true, depth + 1, nodeIndexByteOffset + c1, box1 );

				} else {

					c1StopTraversal =
						c1Intersection &&
						shapecastTraverse(
							c1,
							geometry,
							intersectsBoundsFunc,
							intersectsRangeFunc,
							nodeScoreFunc,
							nodeIndexByteOffset,
							depth + 1
						);

				}

				if ( c1StopTraversal ) return true;

				// Check box 2 intersection
				// cached box2 will have been overwritten by previous traversal
				box2 = _box2;
				arrayToBox( BOUNDING_DATA_INDEX( c2 ), float32Array, box2 );

				const isC2Leaf = IS_LEAF( c2 * 2, uint16Array );
				const c2Intersection = intersectsBoundsFunc( box2, isC2Leaf, score2, depth + 1, nodeIndexByteOffset + c2 );

				let c2StopTraversal;
				if ( c2Intersection === CONTAINED ) {

					const offset = getLeftOffset( c2 );
					const end = getRightEndOffset( c2 );
					const count = end - offset;

					c2StopTraversal = intersectsRangeFunc( offset, count, true, depth + 1, nodeIndexByteOffset + c2, box2 );

				} else {

					c2StopTraversal =
						c2Intersection &&
						shapecastTraverse(
							c2,
							geometry,
							intersectsBoundsFunc,
							intersectsRangeFunc,
							nodeScoreFunc,
							nodeIndexByteOffset,
							depth + 1
						);

				}

				if ( c2StopTraversal ) return true;

				return false;

			}

		}

	} )();

	const intersectsGeometry = ( function () {

		const triangle = new SeparatingAxisTriangle();
		const triangle2 = new SeparatingAxisTriangle();
		const invertedMat = new three.Matrix4();

		const obb = new OrientedBox();
		const obb2 = new OrientedBox();

		return function intersectsGeometry( nodeIndex32, geometry, otherGeometry, geometryToBvh, cachedObb = null ) {

			let nodeIndex16 = nodeIndex32 * 2, float32Array = _float32Array, uint16Array = _uint16Array, uint32Array = _uint32Array;

			if ( cachedObb === null ) {

				if ( ! otherGeometry.boundingBox ) {

					otherGeometry.computeBoundingBox();

				}

				obb.set( otherGeometry.boundingBox.min, otherGeometry.boundingBox.max, geometryToBvh );
				cachedObb = obb;

			}

			const isLeaf = IS_LEAF( nodeIndex16, uint16Array );
			if ( isLeaf ) {

				const thisGeometry = geometry;
				const thisIndex = thisGeometry.index;
				const thisPos = thisGeometry.attributes.position;

				const index = otherGeometry.index;
				const pos = otherGeometry.attributes.position;

				const offset = OFFSET( nodeIndex32, uint32Array );
				const count = COUNT( nodeIndex16, uint16Array );

				// get the inverse of the geometry matrix so we can transform our triangles into the
				// geometry space we're trying to test. We assume there are fewer triangles being checked
				// here.
				invertedMat.copy( geometryToBvh ).invert();

				if ( otherGeometry.boundsTree ) {

					arrayToBox( BOUNDING_DATA_INDEX( nodeIndex32 ), float32Array, obb2 );
					obb2.matrix.copy( invertedMat );
					obb2.needsUpdate = true;

					const res = otherGeometry.boundsTree.shapecast( {

						intersectsBounds: box => obb2.intersectsBox( box ),

						intersectsTriangle: tri => {

							tri.a.applyMatrix4( geometryToBvh );
							tri.b.applyMatrix4( geometryToBvh );
							tri.c.applyMatrix4( geometryToBvh );
							tri.needsUpdate = true;

							for ( let i = offset * 3, l = ( count + offset ) * 3; i < l; i += 3 ) {

								// this triangle needs to be transformed into the current BVH coordinate frame
								setTriangle( triangle2, i, thisIndex, thisPos );
								triangle2.needsUpdate = true;
								if ( tri.intersectsTriangle( triangle2 ) ) {

									return true;

								}

							}

							return false;

						}

					} );

					return res;

				} else {

					for ( let i = offset * 3, l = ( count + offset * 3 ); i < l; i += 3 ) {

						// this triangle needs to be transformed into the current BVH coordinate frame
						setTriangle( triangle, i, thisIndex, thisPos );
						triangle.a.applyMatrix4( invertedMat );
						triangle.b.applyMatrix4( invertedMat );
						triangle.c.applyMatrix4( invertedMat );
						triangle.needsUpdate = true;

						for ( let i2 = 0, l2 = index.count; i2 < l2; i2 += 3 ) {

							setTriangle( triangle2, i2, index, pos );
							triangle2.needsUpdate = true;

							if ( triangle.intersectsTriangle( triangle2 ) ) {

								return true;

							}

						}

					}

				}

			} else {

				const left = nodeIndex32 + 8;
				const right = uint32Array[ nodeIndex32 + 6 ];

				arrayToBox( BOUNDING_DATA_INDEX( left ), float32Array, boundingBox$1 );
				const leftIntersection =
					cachedObb.intersectsBox( boundingBox$1 ) &&
					intersectsGeometry( left, geometry, otherGeometry, geometryToBvh, cachedObb );

				if ( leftIntersection ) return true;

				arrayToBox( BOUNDING_DATA_INDEX( right ), float32Array, boundingBox$1 );
				const rightIntersection =
					cachedObb.intersectsBox( boundingBox$1 ) &&
					intersectsGeometry( right, geometry, otherGeometry, geometryToBvh, cachedObb );

				if ( rightIntersection ) return true;

				return false;

			}

		};

	} )();

	function intersectRay( nodeIndex32, array, ray, target ) {

		arrayToBox( nodeIndex32, array, boundingBox$1 );
		return ray.intersectBox( boundingBox$1, target );

	}

	const bufferStack = [];
	let _prevBuffer;
	let _float32Array;
	let _uint16Array;
	let _uint32Array;
	function setBuffer( buffer ) {

		if ( _prevBuffer ) {

			bufferStack.push( _prevBuffer );

		}

		_prevBuffer = buffer;
		_float32Array = new Float32Array( buffer );
		_uint16Array = new Uint16Array( buffer );
		_uint32Array = new Uint32Array( buffer );

	}

	function clearBuffer() {

		_prevBuffer = null;
		_float32Array = null;
		_uint16Array = null;
		_uint32Array = null;

		if ( bufferStack.length ) {

			setBuffer( bufferStack.pop() );

		}

	}

	const SKIP_GENERATION = Symbol( 'skip tree generation' );

	const aabb = /* @__PURE__ */ new three.Box3();
	const aabb2 = /* @__PURE__ */ new three.Box3();
	const tempMatrix = /* @__PURE__ */ new three.Matrix4();
	const obb = /* @__PURE__ */ new OrientedBox();
	const obb2 = /* @__PURE__ */ new OrientedBox();
	const temp = /* @__PURE__ */ new three.Vector3();
	const temp1 = /* @__PURE__ */ new three.Vector3();
	const temp2 = /* @__PURE__ */ new three.Vector3();
	const temp3 = /* @__PURE__ */ new three.Vector3();
	const temp4 = /* @__PURE__ */ new three.Vector3();
	const tempBox = /* @__PURE__ */ new three.Box3();
	const trianglePool = /* @__PURE__ */ new PrimitivePool( () => new SeparatingAxisTriangle() );

	class MeshBVH {

		static serialize( bvh, options = {} ) {

			if ( options.isBufferGeometry ) {

				console.warn( 'MeshBVH.serialize: The arguments for the function have changed. See documentation for new signature.' );

				return MeshBVH.serialize(
					arguments[ 0 ],
					{
						cloneBuffers: arguments[ 2 ] === undefined ? true : arguments[ 2 ],
					}
				);

			}

			options = {
				cloneBuffers: true,
				...options,
			};

			const geometry = bvh.geometry;
			const rootData = bvh._roots;
			const indexAttribute = geometry.getIndex();
			let result;
			if ( options.cloneBuffers ) {

				result = {
					roots: rootData.map( root => root.slice() ),
					index: indexAttribute.array.slice(),
				};

			} else {

				result = {
					roots: rootData,
					index: indexAttribute.array,
				};

			}

			return result;

		}

		static deserialize( data, geometry, options = {} ) {

			if ( typeof options === 'boolean' ) {

				console.warn( 'MeshBVH.deserialize: The arguments for the function have changed. See documentation for new signature.' );

				return MeshBVH.deserialize(
					arguments[ 0 ],
					arguments[ 1 ],
					{
						setIndex: arguments[ 2 ] === undefined ? true : arguments[ 2 ],
					}
				);

			}

			options = {
				setIndex: true,
				...options,
			};

			const { index, roots } = data;
			const bvh = new MeshBVH( geometry, { ...options, [ SKIP_GENERATION ]: true } );
			bvh._roots = roots;

			if ( options.setIndex ) {

				const indexAttribute = geometry.getIndex();
				if ( indexAttribute === null ) {

					const newIndex = new three.BufferAttribute( data.index, 1, false );
					geometry.setIndex( newIndex );

				} else if ( indexAttribute.array !== index ) {

					indexAttribute.array.set( index );
					indexAttribute.needsUpdate = true;

				}

			}

			return bvh;

		}

		constructor( geometry, options = {} ) {

			if ( ! geometry.isBufferGeometry ) {

				throw new Error( 'MeshBVH: Only BufferGeometries are supported.' );

			} else if ( geometry.index && geometry.index.isInterleavedBufferAttribute ) {

				throw new Error( 'MeshBVH: InterleavedBufferAttribute is not supported for the index attribute.' );

			}

			// default options
			options = Object.assign( {

				strategy: CENTER,
				maxDepth: 40,
				maxLeafTris: 10,
				verbose: true,
				useSharedArrayBuffer: false,
				setBoundingBox: true,
				onProgress: null,

				// undocumented options

				// Whether to skip generating the tree. Used for deserialization.
				[ SKIP_GENERATION ]: false,

			}, options );

			if ( options.useSharedArrayBuffer && typeof SharedArrayBuffer === 'undefined' ) {

				throw new Error( 'MeshBVH: SharedArrayBuffer is not available.' );

			}

			this._roots = null;
			if ( ! options[ SKIP_GENERATION ] ) {

				this._roots = buildPackedTree( geometry, options );

				if ( ! geometry.boundingBox && options.setBoundingBox ) {

					geometry.boundingBox = this.getBoundingBox( new three.Box3() );

				}

			}

			// retain references to the geometry so we can use them it without having to
			// take a geometry reference in every function.
			this.geometry = geometry;

		}

		refit( nodeIndices = null ) {

			if ( nodeIndices && Array.isArray( nodeIndices ) ) {

				nodeIndices = new Set( nodeIndices );

			}

			const geometry = this.geometry;
			const indexArr = geometry.index.array;
			const posAttr = geometry.attributes.position;
			const posArr = posAttr.array;

			// support for an interleaved position buffer
			const bufferOffset = posAttr.offset || 0;
			let stride = 3;
			if ( posAttr.isInterleavedBufferAttribute ) {

				stride = posAttr.data.stride;

			}

			let buffer, uint32Array, uint16Array, float32Array;
			let byteOffset = 0;
			const roots = this._roots;
			for ( let i = 0, l = roots.length; i < l; i ++ ) {

				buffer = roots[ i ];
				uint32Array = new Uint32Array( buffer );
				uint16Array = new Uint16Array( buffer );
				float32Array = new Float32Array( buffer );

				_traverse( 0, byteOffset );
				byteOffset += buffer.byteLength;

			}

			function _traverse( node32Index, byteOffset, force = false ) {

				const node16Index = node32Index * 2;
				const isLeaf = uint16Array[ node16Index + 15 ] === IS_LEAFNODE_FLAG;
				if ( isLeaf ) {

					const offset = uint32Array[ node32Index + 6 ];
					const count = uint16Array[ node16Index + 14 ];

					let minx = Infinity;
					let miny = Infinity;
					let minz = Infinity;
					let maxx = - Infinity;
					let maxy = - Infinity;
					let maxz = - Infinity;
					for ( let i = 3 * offset, l = 3 * ( offset + count ); i < l; i ++ ) {

						const index = indexArr[ i ] * stride + bufferOffset;
						const x = posArr[ index + 0 ];
						const y = posArr[ index + 1 ];
						const z = posArr[ index + 2 ];

						if ( x < minx ) minx = x;
						if ( x > maxx ) maxx = x;

						if ( y < miny ) miny = y;
						if ( y > maxy ) maxy = y;

						if ( z < minz ) minz = z;
						if ( z > maxz ) maxz = z;

					}

					if (
						float32Array[ node32Index + 0 ] !== minx ||
						float32Array[ node32Index + 1 ] !== miny ||
						float32Array[ node32Index + 2 ] !== minz ||

						float32Array[ node32Index + 3 ] !== maxx ||
						float32Array[ node32Index + 4 ] !== maxy ||
						float32Array[ node32Index + 5 ] !== maxz
					) {

						float32Array[ node32Index + 0 ] = minx;
						float32Array[ node32Index + 1 ] = miny;
						float32Array[ node32Index + 2 ] = minz;

						float32Array[ node32Index + 3 ] = maxx;
						float32Array[ node32Index + 4 ] = maxy;
						float32Array[ node32Index + 5 ] = maxz;

						return true;

					} else {

						return false;

					}

				} else {

					const left = node32Index + 8;
					const right = uint32Array[ node32Index + 6 ];

					// the identifying node indices provided by the shapecast function include offsets of all
					// root buffers to guarantee they're unique between roots so offset left and right indices here.
					const offsetLeft = left + byteOffset;
					const offsetRight = right + byteOffset;
					let forceChildren = force;
					let includesLeft = false;
					let includesRight = false;

					if ( nodeIndices ) {

						// if we see that neither the left or right child are included in the set that need to be updated
						// then we assume that all children need to be updated.
						if ( ! forceChildren ) {

							includesLeft = nodeIndices.has( offsetLeft );
							includesRight = nodeIndices.has( offsetRight );
							forceChildren = ! includesLeft && ! includesRight;

						}

					} else {

						includesLeft = true;
						includesRight = true;

					}

					const traverseLeft = forceChildren || includesLeft;
					const traverseRight = forceChildren || includesRight;

					let leftChange = false;
					if ( traverseLeft ) {

						leftChange = _traverse( left, byteOffset, forceChildren );

					}

					let rightChange = false;
					if ( traverseRight ) {

						rightChange = _traverse( right, byteOffset, forceChildren );

					}

					const didChange = leftChange || rightChange;
					if ( didChange ) {

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

							const lefti = left + i;
							const righti = right + i;
							const minLeftValue = float32Array[ lefti ];
							const maxLeftValue = float32Array[ lefti + 3 ];
							const minRightValue = float32Array[ righti ];
							const maxRightValue = float32Array[ righti + 3 ];

							float32Array[ node32Index + i ] = minLeftValue < minRightValue ? minLeftValue : minRightValue;
							float32Array[ node32Index + i + 3 ] = maxLeftValue > maxRightValue ? maxLeftValue : maxRightValue;

						}

					}

					return didChange;

				}

			}

		}

		traverse( callback, rootIndex = 0 ) {

			const buffer = this._roots[ rootIndex ];
			const uint32Array = new Uint32Array( buffer );
			const uint16Array = new Uint16Array( buffer );
			_traverse( 0 );

			function _traverse( node32Index, depth = 0 ) {

				const node16Index = node32Index * 2;
				const isLeaf = uint16Array[ node16Index + 15 ] === IS_LEAFNODE_FLAG;
				if ( isLeaf ) {

					const offset = uint32Array[ node32Index + 6 ];
					const count = uint16Array[ node16Index + 14 ];
					callback( depth, isLeaf, new Float32Array( buffer, node32Index * 4, 6 ), offset, count );

				} else {

					// TODO: use node functions here
					const left = node32Index + BYTES_PER_NODE / 4;
					const right = uint32Array[ node32Index + 6 ];
					const splitAxis = uint32Array[ node32Index + 7 ];
					const stopTraversal = callback( depth, isLeaf, new Float32Array( buffer, node32Index * 4, 6 ), splitAxis );

					if ( ! stopTraversal ) {

						_traverse( left, depth + 1 );
						_traverse( right, depth + 1 );

					}

				}

			}

		}

		/* Core Cast Functions */
		raycast( ray, materialOrSide = three.FrontSide ) {

			const roots = this._roots;
			const geometry = this.geometry;
			const intersects = [];
			const isMaterial = materialOrSide.isMaterial;
			const isArrayMaterial = Array.isArray( materialOrSide );

			const groups = geometry.groups;
			const side = isMaterial ? materialOrSide.side : materialOrSide;
			for ( let i = 0, l = roots.length; i < l; i ++ ) {

				const materialSide = isArrayMaterial ? materialOrSide[ groups[ i ].materialIndex ].side : side;
				const startCount = intersects.length;

				setBuffer( roots[ i ] );
				raycast( 0, geometry, materialSide, ray, intersects );
				clearBuffer();

				if ( isArrayMaterial ) {

					const materialIndex = groups[ i ].materialIndex;
					for ( let j = startCount, jl = intersects.length; j < jl; j ++ ) {

						intersects[ j ].face.materialIndex = materialIndex;

					}

				}

			}

			return intersects;

		}

		raycastFirst( ray, materialOrSide = three.FrontSide ) {

			const roots = this._roots;
			const geometry = this.geometry;
			const isMaterial = materialOrSide.isMaterial;
			const isArrayMaterial = Array.isArray( materialOrSide );

			let closestResult = null;

			const groups = geometry.groups;
			const side = isMaterial ? materialOrSide.side : materialOrSide;
			for ( let i = 0, l = roots.length; i < l; i ++ ) {

				const materialSide = isArrayMaterial ? materialOrSide[ groups[ i ].materialIndex ].side : side;

				setBuffer( roots[ i ] );
				const result = raycastFirst( 0, geometry, materialSide, ray );
				clearBuffer();

				if ( result != null && ( closestResult == null || result.distance < closestResult.distance ) ) {

					closestResult = result;
					if ( isArrayMaterial ) {

						result.face.materialIndex = groups[ i ].materialIndex;

					}

				}

			}

			return closestResult;

		}

		intersectsGeometry( otherGeometry, geomToMesh ) {

			const geometry = this.geometry;
			let result = false;
			for ( const root of this._roots ) {

				setBuffer( root );
				result = intersectsGeometry( 0, geometry, otherGeometry, geomToMesh );
				clearBuffer();

				if ( result ) {

					break;

				}

			}

			return result;

		}

		shapecast( callbacks, _intersectsTriangleFunc, _orderNodesFunc ) {

			const geometry = this.geometry;
			if ( callbacks instanceof Function ) {

				if ( _intersectsTriangleFunc ) {

					// Support the previous function signature that provided three sequential index buffer
					// indices here.
					const originalTriangleFunc = _intersectsTriangleFunc;
					_intersectsTriangleFunc = ( tri, index, contained, depth ) => {

						const i3 = index * 3;
						return originalTriangleFunc( tri, i3, i3 + 1, i3 + 2, contained, depth );

					};


				}

				callbacks = {

					boundsTraverseOrder: _orderNodesFunc,
					intersectsBounds: callbacks,
					intersectsTriangle: _intersectsTriangleFunc,
					intersectsRange: null,

				};

				console.warn( 'MeshBVH: Shapecast function signature has changed and now takes an object of callbacks as a second argument. See docs for new signature.' );

			}

			const triangle = trianglePool.getPrimitive();
			let {
				boundsTraverseOrder,
				intersectsBounds,
				intersectsRange,
				intersectsTriangle,
			} = callbacks;

			if ( intersectsRange && intersectsTriangle ) {

				const originalIntersectsRange = intersectsRange;
				intersectsRange = ( offset, count, contained, depth, nodeIndex ) => {

					if ( ! originalIntersectsRange( offset, count, contained, depth, nodeIndex ) ) {

						return iterateOverTriangles( offset, count, geometry, intersectsTriangle, contained, depth, triangle );

					}

					return true;

				};

			} else if ( ! intersectsRange ) {

				if ( intersectsTriangle ) {

					intersectsRange = ( offset, count, contained, depth ) => {

						return iterateOverTriangles( offset, count, geometry, intersectsTriangle, contained, depth, triangle );

					};

				} else {

					intersectsRange = ( offset, count, contained ) => {

						return contained;

					};

				}

			}

			let result = false;
			let byteOffset = 0;
			for ( const root of this._roots ) {

				setBuffer( root );
				result = shapecast( 0, geometry, intersectsBounds, intersectsRange, boundsTraverseOrder, byteOffset );
				clearBuffer();

				if ( result ) {

					break;

				}

				byteOffset += root.byteLength;

			}

			trianglePool.releasePrimitive( triangle );

			return result;

		}

		bvhcast( otherBvh, matrixToLocal, callbacks ) {

			// BVHCast function for intersecting two BVHs against each other. Ultimately just uses two recursive shapecast calls rather
			// than an approach that walks down the tree (see bvhcast.js file for more info).

			let {
				intersectsRanges,
				intersectsTriangles,
			} = callbacks;

			const indexAttr = this.geometry.index;
			const positionAttr = this.geometry.attributes.position;

			const otherIndexAttr = otherBvh.geometry.index;
			const otherPositionAttr = otherBvh.geometry.attributes.position;

			tempMatrix.copy( matrixToLocal ).invert();

			const triangle = trianglePool.getPrimitive();
			const triangle2 = trianglePool.getPrimitive();

			if ( intersectsTriangles ) {

				function iterateOverDoubleTriangles( offset1, count1, offset2, count2, depth1, index1, depth2, index2 ) {

					for ( let i2 = offset2, l2 = offset2 + count2; i2 < l2; i2 ++ ) {

						setTriangle( triangle2, i2 * 3, otherIndexAttr, otherPositionAttr );
						triangle2.a.applyMatrix4( matrixToLocal );
						triangle2.b.applyMatrix4( matrixToLocal );
						triangle2.c.applyMatrix4( matrixToLocal );
						triangle2.needsUpdate = true;

						for ( let i1 = offset1, l1 = offset1 + count1; i1 < l1; i1 ++ ) {

							setTriangle( triangle, i1 * 3, indexAttr, positionAttr );
							triangle.needsUpdate = true;

							if ( intersectsTriangles( triangle, triangle2, i1, i2, depth1, index1, depth2, index2 ) ) {

								return true;

							}

						}

					}

					return false;

				}

				if ( intersectsRanges ) {

					const originalIntersectsRanges = intersectsRanges;
					intersectsRanges = function ( offset1, count1, offset2, count2, depth1, index1, depth2, index2 ) {

						if ( ! originalIntersectsRanges( offset1, count1, offset2, count2, depth1, index1, depth2, index2 ) ) {

							return iterateOverDoubleTriangles( offset1, count1, offset2, count2, depth1, index1, depth2, index2 );

						}

						return true;

					};

				} else {

					intersectsRanges = iterateOverDoubleTriangles;

				}

			}

			this.getBoundingBox( aabb2 );
			aabb2.applyMatrix4( matrixToLocal );
			const result = this.shapecast( {

				intersectsBounds: box => aabb2.intersectsBox( box ),

				intersectsRange: ( offset1, count1, contained, depth1, nodeIndex1, box ) => {

					aabb.copy( box );
					aabb.applyMatrix4( tempMatrix );
					return otherBvh.shapecast( {

						intersectsBounds: box => aabb.intersectsBox( box ),

						intersectsRange: ( offset2, count2, contained, depth2, nodeIndex2 ) => {

							return intersectsRanges( offset1, count1, offset2, count2, depth1, nodeIndex1, depth2, nodeIndex2 );

						},

					} );

				}

			} );

			trianglePool.releasePrimitive( triangle );
			trianglePool.releasePrimitive( triangle2 );
			return result;

		}

		/* Derived Cast Functions */
		intersectsBox( box, boxToMesh ) {

			obb.set( box.min, box.max, boxToMesh );
			obb.needsUpdate = true;

			return this.shapecast(
				{
					intersectsBounds: box => obb.intersectsBox( box ),
					intersectsTriangle: tri => obb.intersectsTriangle( tri )
				}
			);

		}

		intersectsSphere( sphere ) {

			return this.shapecast(
				{
					intersectsBounds: box => sphere.intersectsBox( box ),
					intersectsTriangle: tri => tri.intersectsSphere( sphere )
				}
			);

		}

		closestPointToGeometry( otherGeometry, geometryToBvh, target1 = { }, target2 = { }, minThreshold = 0, maxThreshold = Infinity ) {

			if ( ! otherGeometry.boundingBox ) {

				otherGeometry.computeBoundingBox();

			}

			obb.set( otherGeometry.boundingBox.min, otherGeometry.boundingBox.max, geometryToBvh );
			obb.needsUpdate = true;

			const geometry = this.geometry;
			const pos = geometry.attributes.position;
			const index = geometry.index;
			const otherPos = otherGeometry.attributes.position;
			const otherIndex = otherGeometry.index;
			const triangle = trianglePool.getPrimitive();
			const triangle2 = trianglePool.getPrimitive();

			let tempTarget1 = temp1;
			let tempTargetDest1 = temp2;
			let tempTarget2 = null;
			let tempTargetDest2 = null;

			if ( target2 ) {

				tempTarget2 = temp3;
				tempTargetDest2 = temp4;

			}

			let closestDistance = Infinity;
			let closestDistanceTriIndex = null;
			let closestDistanceOtherTriIndex = null;
			tempMatrix.copy( geometryToBvh ).invert();
			obb2.matrix.copy( tempMatrix );
			this.shapecast(
				{

					boundsTraverseOrder: box => {

						return obb.distanceToBox( box, Math.min( closestDistance, maxThreshold ) );

					},

					intersectsBounds: ( box, isLeaf, score ) => {

						if ( score < closestDistance && score < maxThreshold ) {

							// if we know the triangles of this bounds will be intersected next then
							// save the bounds to use during triangle checks.
							if ( isLeaf ) {

								obb2.min.copy( box.min );
								obb2.max.copy( box.max );
								obb2.needsUpdate = true;

							}

							return true;

						}

						return false;

					},

					intersectsRange: ( offset, count ) => {

						if ( otherGeometry.boundsTree ) {

							// if the other geometry has a bvh then use the accelerated path where we use shapecast to find
							// the closest bounds in the other geometry to check.
							return otherGeometry.boundsTree.shapecast( {
								boundsTraverseOrder: box => {

									return obb2.distanceToBox( box, Math.min( closestDistance, maxThreshold ) );

								},

								intersectsBounds: ( box, isLeaf, score ) => {

									return score < closestDistance && score < maxThreshold;

								},

								intersectsRange: ( otherOffset, otherCount ) => {

									for ( let i2 = otherOffset * 3, l2 = ( otherOffset + otherCount ) * 3; i2 < l2; i2 += 3 ) {

										setTriangle( triangle2, i2, otherIndex, otherPos );
										triangle2.a.applyMatrix4( geometryToBvh );
										triangle2.b.applyMatrix4( geometryToBvh );
										triangle2.c.applyMatrix4( geometryToBvh );
										triangle2.needsUpdate = true;

										for ( let i = offset * 3, l = ( offset + count ) * 3; i < l; i += 3 ) {

											setTriangle( triangle, i, index, pos );
											triangle.needsUpdate = true;

											const dist = triangle.distanceToTriangle( triangle2, tempTarget1, tempTarget2 );
											if ( dist < closestDistance ) {

												tempTargetDest1.copy( tempTarget1 );

												if ( tempTargetDest2 ) {

													tempTargetDest2.copy( tempTarget2 );

												}

												closestDistance = dist;
												closestDistanceTriIndex = i / 3;
												closestDistanceOtherTriIndex = i2 / 3;

											}

											// stop traversal if we find a point that's under the given threshold
											if ( dist < minThreshold ) {

												return true;

											}

										}

									}

								},
							} );

						} else {

							// If no bounds tree then we'll just check every triangle.
							const triCount = otherIndex ? otherIndex.count : otherPos.count;
							for ( let i2 = 0, l2 = triCount; i2 < l2; i2 += 3 ) {

								setTriangle( triangle2, i2, otherIndex, otherPos );
								triangle2.a.applyMatrix4( geometryToBvh );
								triangle2.b.applyMatrix4( geometryToBvh );
								triangle2.c.applyMatrix4( geometryToBvh );
								triangle2.needsUpdate = true;

								for ( let i = offset * 3, l = ( offset + count ) * 3; i < l; i += 3 ) {

									setTriangle( triangle, i, index, pos );
									triangle.needsUpdate = true;

									const dist = triangle.distanceToTriangle( triangle2, tempTarget1, tempTarget2 );
									if ( dist < closestDistance ) {

										tempTargetDest1.copy( tempTarget1 );

										if ( tempTargetDest2 ) {

											tempTargetDest2.copy( tempTarget2 );

										}

										closestDistance = dist;
										closestDistanceTriIndex = i / 3;
										closestDistanceOtherTriIndex = i2 / 3;

									}

									// stop traversal if we find a point that's under the given threshold
									if ( dist < minThreshold ) {

										return true;

									}

								}

							}

						}

					},

				}

			);

			trianglePool.releasePrimitive( triangle );
			trianglePool.releasePrimitive( triangle2 );

			if ( closestDistance === Infinity ) return null;

			if ( ! target1.point ) target1.point = tempTargetDest1.clone();
			else target1.point.copy( tempTargetDest1 );
			target1.distance = closestDistance,
			target1.faceIndex = closestDistanceTriIndex;

			if ( target2 ) {

				if ( ! target2.point ) target2.point = tempTargetDest2.clone();
				else target2.point.copy( tempTargetDest2 );
				target2.point.applyMatrix4( tempMatrix );
				tempTargetDest1.applyMatrix4( tempMatrix );
				target2.distance = tempTargetDest1.sub( target2.point ).length();
				target2.faceIndex = closestDistanceOtherTriIndex;

			}

			return target1;

		}

		closestPointToPoint( point, target = { }, minThreshold = 0, maxThreshold = Infinity ) {

			// early out if under minThreshold
			// skip checking if over maxThreshold
			// set minThreshold = maxThreshold to quickly check if a point is within a threshold
			// returns Infinity if no value found
			const minThresholdSq = minThreshold * minThreshold;
			const maxThresholdSq = maxThreshold * maxThreshold;
			let closestDistanceSq = Infinity;
			let closestDistanceTriIndex = null;
			this.shapecast(

				{

					boundsTraverseOrder: box => {

						temp.copy( point ).clamp( box.min, box.max );
						return temp.distanceToSquared( point );

					},

					intersectsBounds: ( box, isLeaf, score ) => {

						return score < closestDistanceSq && score < maxThresholdSq;

					},

					intersectsTriangle: ( tri, triIndex ) => {

						tri.closestPointToPoint( point, temp );
						const distSq = point.distanceToSquared( temp );
						if ( distSq < closestDistanceSq ) {

							temp1.copy( temp );
							closestDistanceSq = distSq;
							closestDistanceTriIndex = triIndex;

						}

						if ( distSq < minThresholdSq ) {

							return true;

						} else {

							return false;

						}

					},

				}

			);

			if ( closestDistanceSq === Infinity ) return null;

			const closestDistance = Math.sqrt( closestDistanceSq );

			if ( ! target.point ) target.point = temp1.clone();
			else target.point.copy( temp1 );
			target.distance = closestDistance,
			target.faceIndex = closestDistanceTriIndex;

			return target;

		}

		getBoundingBox( target ) {

			target.makeEmpty();

			const roots = this._roots;
			roots.forEach( buffer => {

				arrayToBox( 0, new Float32Array( buffer ), tempBox );
				target.union( tempBox );

			} );

			return target;

		}

	}

	// Deprecation
	const originalRaycast = MeshBVH.prototype.raycast;
	MeshBVH.prototype.raycast = function ( ...args ) {

		if ( args[ 0 ].isMesh ) {

			console.warn( 'MeshBVH: The function signature and results frame for "raycast" has changed. See docs for new signature.' );
			const [
				mesh, raycaster, ray, intersects,
			] = args;

			const results = originalRaycast.call( this, ray, mesh.material );
			results.forEach( hit => {

				hit = convertRaycastIntersect( hit, mesh, raycaster );
				if ( hit ) {

					intersects.push( hit );

				}

			} );

			return intersects;

		} else {

			return originalRaycast.apply( this, args );

		}

	};

	const originalRaycastFirst = MeshBVH.prototype.raycastFirst;
	MeshBVH.prototype.raycastFirst = function ( ...args ) {

		if ( args[ 0 ].isMesh ) {

			console.warn( 'MeshBVH: The function signature and results frame for "raycastFirst" has changed. See docs for new signature.' );
			const [
				mesh, raycaster, ray,
			] = args;

			return convertRaycastIntersect( originalRaycastFirst.call( this, ray, mesh.material ), mesh, raycaster );

		} else {

			return originalRaycastFirst.apply( this, args );

		}

	};

	const originalClosestPointToPoint = MeshBVH.prototype.closestPointToPoint;
	MeshBVH.prototype.closestPointToPoint = function ( ...args ) {


		if ( args[ 0 ].isMesh ) {

			console.warn( 'MeshBVH: The function signature and results frame for "closestPointToPoint" has changed. See docs for new signature.' );

			args.unshift();

			const target = args[ 1 ];
			const result = {};
			args[ 1 ] = result;

			originalClosestPointToPoint.apply( this, args );

			if ( target ) {

				target.copy( result.point );

			}

			return result.distance;

		} else {

			return originalClosestPointToPoint.apply( this, args );

		}

	};

	const originalClosestPointToGeometry = MeshBVH.prototype.closestPointToGeometry;
	MeshBVH.prototype.closestPointToGeometry = function ( ...args ) {

		const target1 = args[ 2 ];
		const target2 = args[ 3 ];
		if ( target1 && target1.isVector3 || target2 && target2.isVector3 ) {

			console.warn( 'MeshBVH: The function signature and results frame for "closestPointToGeometry" has changed. See docs for new signature.' );

			const result1 = {};
			const result2 = {};
			const geometryToBvh = args[ 1 ];
			args[ 2 ] = result1;
			args[ 3 ] = result2;

			originalClosestPointToGeometry.apply( this, args );

			if ( target1 ) {

				target1.copy( result1.point );

			}

			if ( target2 ) {

				target2.copy( result2.point ).applyMatrix4( geometryToBvh );

			}

			return result1.distance;

		} else {

			return originalClosestPointToGeometry.apply( this, args );

		}

	};

	const originalRefit = MeshBVH.prototype.refit;
	MeshBVH.prototype.refit = function ( ...args ) {

		const nodeIndices = args[ 0 ];
		const terminationIndices = args[ 1 ];
		if ( terminationIndices && ( terminationIndices instanceof Set || Array.isArray( terminationIndices ) ) ) {

			console.warn( 'MeshBVH: The function signature for "refit" has changed. See docs for new signature.' );

			const newNodeIndices = new Set();
			terminationIndices.forEach( v => newNodeIndices.add( v ) );
			if ( nodeIndices ) {

				nodeIndices.forEach( v => newNodeIndices.add( v ) );

			}

			originalRefit.call( this, newNodeIndices );

		} else {

			originalRefit.apply( this, args );

		}

	};

	[
		'intersectsGeometry',
		'shapecast',
		'intersectsBox',
		'intersectsSphere',
	].forEach( name => {

		const originalFunc = MeshBVH.prototype[ name ];
		MeshBVH.prototype[ name ] = function ( ...args ) {

			if ( args[ 0 ] === null || args[ 0 ].isMesh ) {

				args.shift();
				console.warn( `MeshBVH: The function signature for "${ name }" has changed and no longer takes Mesh. See docs for new signature.` );

			}

			return originalFunc.apply( this, args );

		};

	} );

	const boundingBox = /* @__PURE__ */ new three.Box3();
	class MeshBVHRootVisualizer extends three.Object3D {

		get isMesh() {

			return ! this.displayEdges;

		}

		get isLineSegments() {

			return this.displayEdges;

		}

		get isLine() {

			return this.displayEdges;

		}

		constructor( mesh, material, depth = 10, group = 0 ) {

			super();

			this.material = material;
			this.geometry = new three.BufferGeometry();
			this.name = 'MeshBVHRootVisualizer';
			this.depth = depth;
			this.displayParents = false;
			this.mesh = mesh;
			this.displayEdges = true;
			this._group = group;

		}

		raycast() {}

		update() {

			const geometry = this.geometry;
			const boundsTree = this.mesh.geometry.boundsTree;
			const group = this._group;
			geometry.dispose();
			this.visible = false;
			if ( boundsTree ) {

				// count the number of bounds required
				const targetDepth = this.depth - 1;
				const displayParents = this.displayParents;
				let boundsCount = 0;
				boundsTree.traverse( ( depth, isLeaf ) => {

					if ( depth === targetDepth || isLeaf ) {

						boundsCount ++;
						return true;

					} else if ( displayParents ) {

						boundsCount ++;

					}

				}, group );

				// fill in the position buffer with the bounds corners
				let posIndex = 0;
				const positionArray = new Float32Array( 8 * 3 * boundsCount );
				boundsTree.traverse( ( depth, isLeaf, boundingData ) => {

					const terminate = depth === targetDepth || isLeaf;
					if ( terminate || displayParents ) {

						arrayToBox( 0, boundingData, boundingBox );

						const { min, max } = boundingBox;
						for ( let x = - 1; x <= 1; x += 2 ) {

							const xVal = x < 0 ? min.x : max.x;
							for ( let y = - 1; y <= 1; y += 2 ) {

								const yVal = y < 0 ? min.y : max.y;
								for ( let z = - 1; z <= 1; z += 2 ) {

									const zVal = z < 0 ? min.z : max.z;
									positionArray[ posIndex + 0 ] = xVal;
									positionArray[ posIndex + 1 ] = yVal;
									positionArray[ posIndex + 2 ] = zVal;

									posIndex += 3;

								}

							}

						}

						return terminate;

					}

				}, group );

				let indexArray;
				let indices;
				if ( this.displayEdges ) {

					// fill in the index buffer to point to the corner points
					indices = new Uint8Array( [
						// x axis
						0, 4,
						1, 5,
						2, 6,
						3, 7,

						// y axis
						0, 2,
						1, 3,
						4, 6,
						5, 7,

						// z axis
						0, 1,
						2, 3,
						4, 5,
						6, 7,
					] );

				} else {

					indices = new Uint8Array( [

						// X-, X+
						0, 1, 2,
						2, 1, 3,

						4, 6, 5,
						6, 7, 5,

						// Y-, Y+
						1, 4, 5,
						0, 4, 1,

						2, 3, 6,
						3, 7, 6,

						// Z-, Z+
						0, 2, 4,
						2, 6, 4,

						1, 5, 3,
						3, 5, 7,

					] );

				}

				if ( positionArray.length > 65535 ) {

					indexArray = new Uint32Array( indices.length * boundsCount );

				} else {

					indexArray = new Uint16Array( indices.length * boundsCount );

				}

				const indexLength = indices.length;
				for ( let i = 0; i < boundsCount; i ++ ) {

					const posOffset = i * 8;
					const indexOffset = i * indexLength;
					for ( let j = 0; j < indexLength; j ++ ) {

						indexArray[ indexOffset + j ] = posOffset + indices[ j ];

					}

				}

				// update the geometry
				geometry.setIndex(
					new three.BufferAttribute( indexArray, 1, false ),
				);
				geometry.setAttribute(
					'position',
					new three.BufferAttribute( positionArray, 3, false ),
				);
				this.visible = true;

			}

		}

	}

	class MeshBVHVisualizer extends three.Group {

		get color() {

			return this.edgeMaterial.color;

		}

		get opacity() {

			return this.edgeMaterial.opacity;

		}

		set opacity( v ) {

			this.edgeMaterial.opacity = v;
			this.meshMaterial.opacity = v;

		}

		constructor( mesh, depth = 10 ) {

			super();

			this.name = 'MeshBVHVisualizer';
			this.depth = depth;
			this.mesh = mesh;
			this.displayParents = false;
			this.displayEdges = true;
			this._roots = [];

			const edgeMaterial = new three.LineBasicMaterial( {
				color: 0x00FF88,
				transparent: true,
				opacity: 0.3,
				depthWrite: false,
			} );

			const meshMaterial = new three.MeshBasicMaterial( {
				color: 0x00FF88,
				transparent: true,
				opacity: 0.3,
				depthWrite: false,
			} );

			meshMaterial.color = edgeMaterial.color;

			this.edgeMaterial = edgeMaterial;
			this.meshMaterial = meshMaterial;

			this.update();

		}

		update() {

			const bvh = this.mesh.geometry.boundsTree;
			const totalRoots = bvh ? bvh._roots.length : 0;
			while ( this._roots.length > totalRoots ) {

				this._roots.pop();

			}

			for ( let i = 0; i < totalRoots; i ++ ) {

				if ( i >= this._roots.length ) {

					const root = new MeshBVHRootVisualizer( this.mesh, this.edgeMaterial, this.depth, i );
					this.add( root );
					this._roots.push( root );

				}

				const root = this._roots[ i ];
				root.depth = this.depth;
				root.mesh = this.mesh;
				root.displayParents = this.displayParents;
				root.displayEdges = this.displayEdges;
				root.material = this.displayEdges ? this.edgeMaterial : this.meshMaterial;
				root.update();

			}

		}

		updateMatrixWorld( ...args ) {

			this.position.copy( this.mesh.position );
			this.rotation.copy( this.mesh.rotation );
			this.scale.copy( this.mesh.scale );

			super.updateMatrixWorld( ...args );

		}

		copy( source ) {

			this.depth = source.depth;
			this.mesh = source.mesh;

		}

		clone() {

			return new MeshBVHVisualizer( this.mesh, this.depth );

		}

		dispose() {

			this.edgeMaterial.dispose();
			this.meshMaterial.dispose();

			const children = this.children;
			for ( let i = 0, l = children.length; i < l; i ++ ) {

				children[ i ].geometry.dispose();

			}

		}

	}

	const _box1 = /* @__PURE__ */ new three.Box3();
	const _box2 = /* @__PURE__ */ new three.Box3();
	const _vec = /* @__PURE__ */ new three.Vector3();

	// https://stackoverflow.com/questions/1248302/how-to-get-the-size-of-a-javascript-object
	function getPrimitiveSize( el ) {

		switch ( typeof el ) {

			case 'number':
				return 8;
			case 'string':
				return el.length * 2;
			case 'boolean':
				return 4;
			default:
				return 0;

		}

	}

	function isTypedArray( arr ) {

		const regex = /(Uint|Int|Float)(8|16|32)Array/;
		return regex.test( arr.constructor.name );

	}

	function getRootExtremes( bvh, group ) {

		const result = {
			nodeCount: 0,
			leafNodeCount: 0,

			depth: {
				min: Infinity, max: - Infinity
			},
			tris: {
				min: Infinity, max: - Infinity
			},
			splits: [ 0, 0, 0 ],
			surfaceAreaScore: 0,
		};

		bvh.traverse( ( depth, isLeaf, boundingData, offsetOrSplit, count ) => {

			const l0 = boundingData[ 0 + 3 ] - boundingData[ 0 ];
			const l1 = boundingData[ 1 + 3 ] - boundingData[ 1 ];
			const l2 = boundingData[ 2 + 3 ] - boundingData[ 2 ];

			const surfaceArea = 2 * ( l0 * l1 + l1 * l2 + l2 * l0 );

			result.nodeCount ++;
			if ( isLeaf ) {

				result.leafNodeCount ++;

				result.depth.min = Math.min( depth, result.depth.min );
				result.depth.max = Math.max( depth, result.depth.max );

				result.tris.min = Math.min( count, result.tris.min );
				result.tris.max = Math.max( count, result.tris.max );

				result.surfaceAreaScore += surfaceArea * TRIANGLE_INTERSECT_COST * count;

			} else {

				result.splits[ offsetOrSplit ] ++;

				result.surfaceAreaScore += surfaceArea * TRAVERSAL_COST;

			}

		}, group );

		// If there are no leaf nodes because the tree hasn't finished generating yet.
		if ( result.tris.min === Infinity ) {

			result.tris.min = 0;
			result.tris.max = 0;

		}

		if ( result.depth.min === Infinity ) {

			result.depth.min = 0;
			result.depth.max = 0;

		}

		return result;

	}

	function getBVHExtremes( bvh ) {

		return bvh._roots.map( ( root, i ) => getRootExtremes( bvh, i ) );

	}

	function estimateMemoryInBytes( obj ) {

		const traversed = new Set();
		const stack = [ obj ];
		let bytes = 0;

		while ( stack.length ) {

			const curr = stack.pop();
			if ( traversed.has( curr ) ) {

				continue;

			}

			traversed.add( curr );

			for ( let key in curr ) {

				if ( ! curr.hasOwnProperty( key ) ) {

					continue;

				}

				bytes += getPrimitiveSize( key );

				const value = curr[ key ];
				if ( value && ( typeof value === 'object' || typeof value === 'function' ) ) {

					if ( isTypedArray( value ) ) {

						bytes += value.byteLength;

					} else if ( value instanceof ArrayBuffer ) {

						bytes += value.byteLength;

					} else {

						stack.push( value );

					}

				} else {

					bytes += getPrimitiveSize( value );

				}


			}

		}

		return bytes;

	}

	function validateBounds( bvh ) {

		const geometry = bvh.geometry;
		const depthStack = [];
		const index = geometry.index;
		const position = geometry.getAttribute( 'position' );
		let passes = true;

		bvh.traverse( ( depth, isLeaf, boundingData, offset, count ) => {

			const info = {
				depth,
				isLeaf,
				boundingData,
				offset,
				count,
			};
			depthStack[ depth ] = info;

			arrayToBox( 0, boundingData, _box1 );
			const parent = depthStack[ depth - 1 ];

			if ( isLeaf ) {

				// check triangles
				for ( let i = offset * 3, l = ( offset + count ) * 3; i < l; i += 3 ) {

					const i0 = index.getX( i );
					const i1 = index.getX( i + 1 );
					const i2 = index.getX( i + 2 );

					let isContained;

					_vec.fromBufferAttribute( position, i0 );
					isContained = _box1.containsPoint( _vec );

					_vec.fromBufferAttribute( position, i1 );
					isContained = isContained && _box1.containsPoint( _vec );

					_vec.fromBufferAttribute( position, i2 );
					isContained = isContained && _box1.containsPoint( _vec );

					console.assert( isContained, 'Leaf bounds does not fully contain triangle.' );
					passes = passes && isContained;

				}

			}

			if ( parent ) {

				// check if my bounds fit in my parents
				arrayToBox( 0, boundingData, _box2 );

				const isContained = _box2.containsBox( _box1 );
				console.assert( isContained, 'Parent bounds does not fully contain child.' );
				passes = passes && isContained;

			}

		} );

		return passes;

	}

	// Returns a simple, human readable object that represents the BVH.
	function getJSONStructure( bvh ) {

		const depthStack = [];

		bvh.traverse( ( depth, isLeaf, boundingData, offset, count ) => {

			const info = {
				bounds: arrayToBox( 0, boundingData, new three.Box3() ),
			};

			if ( isLeaf ) {

				info.count = count;
				info.offset = offset;

			} else {

				info.left = null;
				info.right = null;

			}

			depthStack[ depth ] = info;

			// traversal hits the left then right node
			const parent = depthStack[ depth - 1 ];
			if ( parent ) {

				if ( parent.left === null ) {

					parent.left = info;

				} else {

					parent.right = info;

				}

			}

		} );

		return depthStack[ 0 ];

	}

	const ray = /* @__PURE__ */ new three.Ray();
	const tmpInverseMatrix = /* @__PURE__ */ new three.Matrix4();
	const origMeshRaycastFunc = three.Mesh.prototype.raycast;

	function acceleratedRaycast( raycaster, intersects ) {

		if ( this.geometry.boundsTree ) {

			if ( this.material === undefined ) return;

			tmpInverseMatrix.copy( this.matrixWorld ).invert();
			ray.copy( raycaster.ray ).applyMatrix4( tmpInverseMatrix );

			const bvh = this.geometry.boundsTree;
			if ( raycaster.firstHitOnly === true ) {

				const hit = convertRaycastIntersect( bvh.raycastFirst( ray, this.material ), this, raycaster );
				if ( hit ) {

					intersects.push( hit );

				}

			} else {

				const hits = bvh.raycast( ray, this.material );
				for ( let i = 0, l = hits.length; i < l; i ++ ) {

					const hit = convertRaycastIntersect( hits[ i ], this, raycaster );
					if ( hit ) {

						intersects.push( hit );

					}

				}

			}

		} else {

			origMeshRaycastFunc.call( this, raycaster, intersects );

		}

	}

	function computeBoundsTree( options ) {

		this.boundsTree = new MeshBVH( this, options );
		return this.boundsTree;

	}

	function disposeBoundsTree() {

		this.boundsTree = null;

	}

	function countToStringFormat( count ) {

		switch ( count ) {

			case 1: return 'R';
			case 2: return 'RG';
			case 3: return 'RGBA';
			case 4: return 'RGBA';

		}

		throw new Error();

	}

	function countToFormat( count ) {

		switch ( count ) {

			case 1: return three.RedFormat;
			case 2: return three.RGFormat;
			case 3: return three.RGBAFormat;
			case 4: return three.RGBAFormat;

		}

	}

	function countToIntFormat( count ) {

		switch ( count ) {

			case 1: return three.RedIntegerFormat;
			case 2: return three.RGIntegerFormat;
			case 3: return three.RGBAIntegerFormat;
			case 4: return three.RGBAIntegerFormat;

		}

	}

	class VertexAttributeTexture extends three.DataTexture {

		constructor() {

			super();
			this.minFilter = three.NearestFilter;
			this.magFilter = three.NearestFilter;
			this.generateMipmaps = false;
			this.overrideItemSize = null;
			this._forcedType = null;

		}

		updateFrom( attr ) {

			const overrideItemSize = this.overrideItemSize;
			const originalItemSize = attr.itemSize;
			const originalCount = attr.count;
			if ( overrideItemSize !== null ) {

				if ( ( originalItemSize * originalCount ) % overrideItemSize !== 0.0 ) {

					throw new Error( 'VertexAttributeTexture: overrideItemSize must divide evenly into buffer length.' );

				}

				attr.itemSize = overrideItemSize;
				attr.count = originalCount * originalItemSize / overrideItemSize;

			}

			const itemSize = attr.itemSize;
			const count = attr.count;
			const normalized = attr.normalized;
			const originalBufferCons = attr.array.constructor;
			const byteCount = originalBufferCons.BYTES_PER_ELEMENT;
			let targetType = this._forcedType;
			let finalStride = itemSize;

			// derive the type of texture this should be in the shader
			if ( targetType === null ) {

				switch ( originalBufferCons ) {

					case Float32Array:
						targetType = three.FloatType;
						break;

					case Uint8Array:
					case Uint16Array:
					case Uint32Array:
						targetType = three.UnsignedIntType;
						break;

					case Int8Array:
					case Int16Array:
					case Int32Array:
						targetType = three.IntType;
						break;

				}

			}

			// get the target format to store the texture as
			let type, format, normalizeValue, targetBufferCons;
			let internalFormat = countToStringFormat( itemSize );
			switch ( targetType ) {

				case three.FloatType:
					normalizeValue = 1.0;
					format = countToFormat( itemSize );

					if ( normalized && byteCount === 1 ) {

						targetBufferCons = originalBufferCons;
						internalFormat += '8';

						if ( originalBufferCons === Uint8Array ) {

							type = three.UnsignedByteType;

						} else {

							type = three.ByteType;
							internalFormat += '_SNORM';

						}

					} else {

						targetBufferCons = Float32Array;
						internalFormat += '32F';
						type = three.FloatType;

					}

					break;

				case three.IntType:
					internalFormat += byteCount * 8 + 'I';
					normalizeValue = normalized ? Math.pow( 2, originalBufferCons.BYTES_PER_ELEMENT * 8 - 1 ) : 1.0;
					format = countToIntFormat( itemSize );

					if ( byteCount === 1 ) {

						targetBufferCons = Int8Array;
						type = three.ByteType;

					} else if ( byteCount === 2 ) {

						targetBufferCons = Int16Array;
						type = three.ShortType;

					} else {

						targetBufferCons = Int32Array;
						type = three.IntType;

					}

					break;

				case three.UnsignedIntType:
					internalFormat += byteCount * 8 + 'UI';
					normalizeValue = normalized ? Math.pow( 2, originalBufferCons.BYTES_PER_ELEMENT * 8 - 1 ) : 1.0;
					format = countToIntFormat( itemSize );

					if ( byteCount === 1 ) {

						targetBufferCons = Uint8Array;
						type = three.UnsignedByteType;

					} else if ( byteCount === 2 ) {

						targetBufferCons = Uint16Array;
						type = three.UnsignedShortType;

					} else {

						targetBufferCons = Uint32Array;
						type = three.UnsignedIntType;

					}

					break;

			}

			// there will be a mismatch between format length and final length because
			// RGBFormat and RGBIntegerFormat was removed
			if ( finalStride === 3 && ( format === three.RGBAFormat || format === three.RGBAIntegerFormat ) ) {

				finalStride = 4;

			}

			// copy the data over to the new texture array
			const dimension = Math.ceil( Math.sqrt( count ) );
			const length = finalStride * dimension * dimension;
			const dataArray = new targetBufferCons( length );
			for ( let i = 0; i < count; i ++ ) {

				const ii = finalStride * i;
				dataArray[ ii ] = attr.getX( i ) / normalizeValue;

				if ( itemSize >= 2 ) {

					dataArray[ ii + 1 ] = attr.getY( i ) / normalizeValue;

				}

				if ( itemSize >= 3 ) {

					dataArray[ ii + 2 ] = attr.getZ( i ) / normalizeValue;

					if ( finalStride === 4 ) {

						dataArray[ ii + 3 ] = 1.0;

					}

				}

				if ( itemSize >= 4 ) {

					dataArray[ ii + 3 ] = attr.getW( i ) / normalizeValue;

				}

			}

			this.internalFormat = internalFormat;
			this.format = format;
			this.type = type;
			this.image.width = dimension;
			this.image.height = dimension;
			this.image.data = dataArray;
			this.needsUpdate = true;

			attr.itemSize = originalItemSize;
			attr.count = originalCount;

		}

	}

	class UIntVertexAttributeTexture extends VertexAttributeTexture {

		constructor() {

			super();
			this._forcedType = three.UnsignedIntType;

		}

	}

	class IntVertexAttributeTexture extends VertexAttributeTexture {

		constructor() {

			super();
			this._forcedType = three.IntType;

		}


	}

	class FloatVertexAttributeTexture extends VertexAttributeTexture {

		constructor() {

			super();
			this._forcedType = three.FloatType;

		}

	}

	function bvhToTextures( bvh, boundsTexture, contentsTexture ) {

		const roots = bvh._roots;

		if ( roots.length !== 1 ) {

			throw new Error( 'MeshBVHUniformStruct: Multi-root BVHs not supported.' );

		}

		const root = roots[ 0 ];
		const uint16Array = new Uint16Array( root );
		const uint32Array = new Uint32Array( root );
		const float32Array = new Float32Array( root );

		// Both bounds need two elements per node so compute the height so it's twice as long as
		// the width so we can expand the row by two and still have a square texture
		const nodeCount = root.byteLength / BYTES_PER_NODE;
		const boundsDimension = 2 * Math.ceil( Math.sqrt( nodeCount / 2 ) );
		const boundsArray = new Float32Array( 4 * boundsDimension * boundsDimension );

		const contentsDimension = Math.ceil( Math.sqrt( nodeCount ) );
		const contentsArray = new Uint32Array( 2 * contentsDimension * contentsDimension );

		for ( let i = 0; i < nodeCount; i ++ ) {

			const nodeIndex32 = i * BYTES_PER_NODE / 4;
			const nodeIndex16 = nodeIndex32 * 2;
			const boundsIndex = BOUNDING_DATA_INDEX( nodeIndex32 );
			for ( let b = 0; b < 3; b ++ ) {

				boundsArray[ 8 * i + 0 + b ] = float32Array[ boundsIndex + 0 + b ];
				boundsArray[ 8 * i + 4 + b ] = float32Array[ boundsIndex + 3 + b ];

			}

			if ( IS_LEAF( nodeIndex16, uint16Array ) ) {

				const count = COUNT( nodeIndex16, uint16Array );
				const offset = OFFSET( nodeIndex32, uint32Array );

				const mergedLeafCount = 0xffff0000 | count;
				contentsArray[ i * 2 + 0 ] = mergedLeafCount;
				contentsArray[ i * 2 + 1 ] = offset;

			} else {

				const rightIndex = 4 * RIGHT_NODE( nodeIndex32, uint32Array ) / BYTES_PER_NODE;
				const splitAxis = SPLIT_AXIS( nodeIndex32, uint32Array );

				contentsArray[ i * 2 + 0 ] = splitAxis;
				contentsArray[ i * 2 + 1 ] = rightIndex;

			}

		}

		boundsTexture.image.data = boundsArray;
		boundsTexture.image.width = boundsDimension;
		boundsTexture.image.height = boundsDimension;
		boundsTexture.format = three.RGBAFormat;
		boundsTexture.type = three.FloatType;
		boundsTexture.internalFormat = 'RGBA32F';
		boundsTexture.minFilter = three.NearestFilter;
		boundsTexture.magFilter = three.NearestFilter;
		boundsTexture.generateMipmaps = false;
		boundsTexture.needsUpdate = true;

		contentsTexture.image.data = contentsArray;
		contentsTexture.image.width = contentsDimension;
		contentsTexture.image.height = contentsDimension;
		contentsTexture.format = three.RGIntegerFormat;
		contentsTexture.type = three.UnsignedIntType;
		contentsTexture.internalFormat = 'RG32UI';
		contentsTexture.minFilter = three.NearestFilter;
		contentsTexture.magFilter = three.NearestFilter;
		contentsTexture.generateMipmaps = false;
		contentsTexture.needsUpdate = true;

	}

	class MeshBVHUniformStruct {

		constructor() {

			this.autoDispose = true;
			this.index = new UIntVertexAttributeTexture();
			this.position = new FloatVertexAttributeTexture();
			this.bvhBounds = new three.DataTexture();
			this.bvhContents = new three.DataTexture();

			this.index.overrideItemSize = 3;

		}

		updateFrom( bvh ) {

			const { geometry } = bvh;

			bvhToTextures( bvh, this.bvhBounds, this.bvhContents );

			this.index.updateFrom( geometry.index );
			this.position.updateFrom( geometry.attributes.position );

		}

		dispose() {

			const { index, position, bvhBounds, bvhContents } = this;

			if ( index ) index.dispose();
			if ( position ) position.dispose();
			if ( bvhBounds ) bvhBounds.dispose();
			if ( bvhContents ) bvhContents.dispose();

		}

	}

	const shaderStructs = /* glsl */`
#ifndef TRI_INTERSECT_EPSILON
#define TRI_INTERSECT_EPSILON 1e-5
#endif

#ifndef INFINITY
#define INFINITY 1e20
#endif

struct BVH {

	usampler2D index;
	sampler2D position;

	sampler2D bvhBounds;
	usampler2D bvhContents;

};

// Note that a struct cannot be used for the hit record including faceIndices, faceNormal, barycoord,
// side, and dist because on some mobile GPUS (such as Adreno) numbers are afforded less precision specifically
// when in a struct leading to inaccurate hit results. See KhronosGroup/WebGL#3351 for more details.
`;

	const shaderIntersectFunction = /* glsl */`

uvec4 uTexelFetch1D( usampler2D tex, uint index ) {

	uint width = uint( textureSize( tex, 0 ).x );
	uvec2 uv;
	uv.x = index % width;
	uv.y = index / width;

	return texelFetch( tex, ivec2( uv ), 0 );

}

ivec4 iTexelFetch1D( isampler2D tex, uint index ) {

	uint width = uint( textureSize( tex, 0 ).x );
	uvec2 uv;
	uv.x = index % width;
	uv.y = index / width;

	return texelFetch( tex, ivec2( uv ), 0 );

}

vec4 texelFetch1D( sampler2D tex, uint index ) {

	uint width = uint( textureSize( tex, 0 ).x );
	uvec2 uv;
	uv.x = index % width;
	uv.y = index / width;

	return texelFetch( tex, ivec2( uv ), 0 );

}

vec4 textureSampleBarycoord( sampler2D tex, vec3 barycoord, uvec3 faceIndices ) {

	return
		barycoord.x * texelFetch1D( tex, faceIndices.x ) +
		barycoord.y * texelFetch1D( tex, faceIndices.y ) +
		barycoord.z * texelFetch1D( tex, faceIndices.z );

}

void ndcToCameraRay(
	vec2 coord, mat4 cameraWorld, mat4 invProjectionMatrix,
	out vec3 rayOrigin, out vec3 rayDirection
) {

	// get camera look direction and near plane for camera clipping
	vec4 lookDirection = cameraWorld * vec4( 0.0, 0.0, - 1.0, 0.0 );
	vec4 nearVector = invProjectionMatrix * vec4( 0.0, 0.0, - 1.0, 1.0 );
	float near = abs( nearVector.z / nearVector.w );

	// get the camera direction and position from camera matrices
	vec4 origin = cameraWorld * vec4( 0.0, 0.0, 0.0, 1.0 );
	vec4 direction = invProjectionMatrix * vec4( coord, 0.5, 1.0 );
	direction /= direction.w;
	direction = cameraWorld * direction - origin;

	// slide the origin along the ray until it sits at the near clip plane position
	origin.xyz += direction.xyz * near / dot( direction, lookDirection );

	rayOrigin = origin.xyz;
	rayDirection = direction.xyz;

}

float intersectsBounds( vec3 rayOrigin, vec3 rayDirection, vec3 boundsMin, vec3 boundsMax ) {

	// https://www.reddit.com/r/opengl/comments/8ntzz5/fast_glsl_ray_box_intersection/
	// https://tavianator.com/2011/ray_box.html
	vec3 invDir = 1.0 / rayDirection;

	// find intersection distances for each plane
	vec3 tMinPlane = invDir * ( boundsMin - rayOrigin );
	vec3 tMaxPlane = invDir * ( boundsMax - rayOrigin );

	// get the min and max distances from each intersection
	vec3 tMinHit = min( tMaxPlane, tMinPlane );
	vec3 tMaxHit = max( tMaxPlane, tMinPlane );

	// get the furthest hit distance
	vec2 t = max( tMinHit.xx, tMinHit.yz );
	float t0 = max( t.x, t.y );

	// get the minimum hit distance
	t = min( tMaxHit.xx, tMaxHit.yz );
	float t1 = min( t.x, t.y );

	// set distance to 0.0 if the ray starts inside the box
	float dist = max( t0, 0.0 );

	return t1 >= dist ? dist : INFINITY;

}

bool intersectsTriangle(
	vec3 rayOrigin, vec3 rayDirection, vec3 a, vec3 b, vec3 c,
	out vec3 barycoord, out vec3 norm, out float dist, out float side
) {

	// https://stackoverflow.com/questions/42740765/intersection-between-line-and-triangle-in-3d
	vec3 edge1 = b - a;
	vec3 edge2 = c - a;
	norm = cross( edge1, edge2 );

	float det = - dot( rayDirection, norm );
	float invdet = 1.0 / det;

	vec3 AO = rayOrigin - a;
	vec3 DAO = cross( AO, rayDirection );

	vec4 uvt;
	uvt.x = dot( edge2, DAO ) * invdet;
	uvt.y = - dot( edge1, DAO ) * invdet;
	uvt.z = dot( AO, norm ) * invdet;
	uvt.w = 1.0 - uvt.x - uvt.y;

	// set the hit information
	barycoord = uvt.wxy; // arranged in A, B, C order
	dist = uvt.z;
	side = sign( det );
	norm = side * normalize( norm );

	// add an epsilon to avoid misses between triangles
	uvt += vec4( TRI_INTERSECT_EPSILON );

	return all( greaterThanEqual( uvt, vec4( 0.0 ) ) );

}

bool intersectTriangles(
	BVH bvh, vec3 rayOrigin, vec3 rayDirection, uint offset, uint count,
	inout float minDistance,

	// output variables
	out uvec4 faceIndices, out vec3 faceNormal, out vec3 barycoord,
	out float side, out float dist
) {

	bool found = false;
	vec3 localBarycoord, localNormal;
	float localDist, localSide;
	for ( uint i = offset, l = offset + count; i < l; i ++ ) {

		uvec3 indices = uTexelFetch1D( bvh.index, i ).xyz;
		vec3 a = texelFetch1D( bvh.position, indices.x ).rgb;
		vec3 b = texelFetch1D( bvh.position, indices.y ).rgb;
		vec3 c = texelFetch1D( bvh.position, indices.z ).rgb;

		if (
			intersectsTriangle( rayOrigin, rayDirection, a, b, c, localBarycoord, localNormal, localDist, localSide )
			&& localDist < minDistance
		) {

			found = true;
			minDistance = localDist;

			faceIndices = uvec4( indices.xyz, i );
			faceNormal = localNormal;

			side = localSide;
			barycoord = localBarycoord;
			dist = localDist;

		}

	}

	return found;

}

float intersectsBVHNodeBounds( vec3 rayOrigin, vec3 rayDirection, BVH bvh, uint currNodeIndex ) {

	vec3 boundsMin = texelFetch1D( bvh.bvhBounds, currNodeIndex * 2u + 0u ).xyz;
	vec3 boundsMax = texelFetch1D( bvh.bvhBounds, currNodeIndex * 2u + 1u ).xyz;
	return intersectsBounds( rayOrigin, rayDirection, boundsMin, boundsMax );

}

bool bvhIntersectFirstHit(
	BVH bvh, vec3 rayOrigin, vec3 rayDirection,

	// output variables
	out uvec4 faceIndices, out vec3 faceNormal, out vec3 barycoord,
	out float side, out float dist
) {

	// stack needs to be twice as long as the deepest tree we expect because
	// we push both the left and right child onto the stack every traversal
	int ptr = 0;
	uint stack[ 60 ];
	stack[ 0 ] = 0u;

	float triangleDistance = 1e20;
	bool found = false;
	while ( ptr > - 1 && ptr < 60 ) {

		uint currNodeIndex = stack[ ptr ];
		ptr --;

		// check if we intersect the current bounds
		float boundsHitDistance = intersectsBVHNodeBounds( rayOrigin, rayDirection, bvh, currNodeIndex );
		if ( boundsHitDistance == INFINITY || boundsHitDistance > triangleDistance ) {

			continue;

		}

		uvec2 boundsInfo = uTexelFetch1D( bvh.bvhContents, currNodeIndex ).xy;
		bool isLeaf = bool( boundsInfo.x & 0xffff0000u );

		if ( isLeaf ) {

			uint count = boundsInfo.x & 0x0000ffffu;
			uint offset = boundsInfo.y;

			found = intersectTriangles(
				bvh, rayOrigin, rayDirection, offset, count, triangleDistance,
				faceIndices, faceNormal, barycoord, side, dist
			) || found;

		} else {

			uint leftIndex = currNodeIndex + 1u;
			uint splitAxis = boundsInfo.x & 0x0000ffffu;
			uint rightIndex = boundsInfo.y;

			bool leftToRight = rayDirection[ splitAxis ] >= 0.0;
			uint c1 = leftToRight ? leftIndex : rightIndex;
			uint c2 = leftToRight ? rightIndex : leftIndex;

			// set c2 in the stack so we traverse it later. We need to keep track of a pointer in
			// the stack while we traverse. The second pointer added is the one that will be
			// traversed first
			ptr ++;
			stack[ ptr ] = c2;

			ptr ++;
			stack[ ptr ] = c1;

		}

	}

	return found;

}

`;

	exports.AVERAGE = AVERAGE;
	exports.CENTER = CENTER;
	exports.CONTAINED = CONTAINED;
	exports.FloatVertexAttributeTexture = FloatVertexAttributeTexture;
	exports.INTERSECTED = INTERSECTED;
	exports.IntVertexAttributeTexture = IntVertexAttributeTexture;
	exports.MeshBVH = MeshBVH;
	exports.MeshBVHUniformStruct = MeshBVHUniformStruct;
	exports.MeshBVHVisualizer = MeshBVHVisualizer;
	exports.NOT_INTERSECTED = NOT_INTERSECTED;
	exports.SAH = SAH;
	exports.UIntVertexAttributeTexture = UIntVertexAttributeTexture;
	exports.VertexAttributeTexture = VertexAttributeTexture;
	exports.acceleratedRaycast = acceleratedRaycast;
	exports.computeBoundsTree = computeBoundsTree;
	exports.disposeBoundsTree = disposeBoundsTree;
	exports.estimateMemoryInBytes = estimateMemoryInBytes;
	exports.getBVHExtremes = getBVHExtremes;
	exports.getJSONStructure = getJSONStructure;
	exports.getTriangleHitPointInfo = getTriangleHitPointInfo;
	exports.shaderIntersectFunction = shaderIntersectFunction;
	exports.shaderStructs = shaderStructs;
	exports.validateBounds = validateBounds;

	Object.defineProperty(exports, '__esModule', { value: true });

}));
//# sourceMappingURL=index.umd.cjs.map