three-mesh-bvh - npm Package Compare versions

Comparing version 0.7.0 to 0.7.1

package.json

 {
   "name": "three-mesh-bvh",
-  "version": "0.7.0",
+  "version": "0.7.1",
   "description": "A BVH implementation to speed up raycasting against three.js meshes.",
@@ -72,3 +72,3 @@ "module": "src/index.js",
     "jest": "^27.2.4",
-    "parcel": "^2.0.0",
+    "parcel": "^2.11.0",
     "preprocess": "^3.2.0",
@@ -75,0 +75,0 @@ "rollup": "^3.28.1",

README.md

@@ -188,3 +188,3 @@ # three-mesh-bvh
 
-_NOTE WebWorker syntax is inconsistently supported across bundlers and sometimes not supported at all so the GenerateMeshBVHWorker class is not exported from the package root. If needed the code from `src/worker` can be copied and modified to accomodate a particular build process._
+_NOTE WebWorker syntax is inconsistently supported across bundlers and sometimes not supported at all so the GenerateMeshBVHWorker class is not exported from the package root. If needed the code from `src/worker` can be copied and modified to accommodate a particular build process._
 
@@ -205,2 +205,18 @@ ```js
 
+_Parallel BVH generation is also supported using "ParallelMeshBVHWorker", which requires support for SharedArrayBuffer. If SharedArrayBuffer is not available it falls back to "GenerateMeshBVHWorker". It is recommended that geometry passed to this function have `position` and `index` with SharedArrayBuffer arrays, otherwise buffer copies must be made._
+
+```js
+import { ParallelMeshBVHWorker } from 'three-mesh-bvh/src/workers/ParallelMeshBVHWorker.js';
+
+// ...
+
+const geometry = new KnotBufferGeometry( 1, 0.5, 40, 10 );
+const worker = new ParallelMeshBVHWorker();
+worker.generate( geometry ).then( bvh => {
+
+    geometry.boundsTree = bvh;
+
+} );
+```
+
 ## BVH Queries in a Shader
@@ -207,0 +223,0 @@

src/core/build/buildTree.js

 import { ensureIndex, getFullGeometryRange, getRootIndexRanges, getTriCount, hasGroupGaps, } from './geometryUtils.js';
-import { getBounds, getCentroidBounds, computeTriangleBounds } from './computeBoundsUtils.js';
+import { getBounds, computeTriangleBounds } from './computeBoundsUtils.js';
 import { getOptimalSplit } from './splitUtils.js';
 import { MeshBVHNode } from '../MeshBVHNode.js';
-import { BYTES_PER_NODE, IS_LEAFNODE_FLAG } from '../Constants.js';
+import { BYTES_PER_NODE } from '../Constants.js';
 
 import { partition } from './sortUtils.generated.js';
 import { partition_indirect } from './sortUtils_indirect.generated.js';
+import { countNodes, populateBuffer } from './buildUtils.js';
 
-function generateIndirectBuffer( geometry, useSharedArrayBuffer ) {
+export function generateIndirectBuffer( geometry, useSharedArrayBuffer ) {
 
@@ -28,53 +29,28 @@ const triCount = ( geometry.index ? geometry.index.count : geometry.attributes.position.count ) / 3;
 
-function buildTree( bvh, options ) {
+export function buildTree( bvh, triangleBounds, offset, count, 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 geometry bounding box if it's available because it may be out of date.
+	// epxand variables
+	const {
+		maxDepth,
+		verbose,
+		maxLeafTris,
+		strategy,
+		onProgress,
+		indirect,
+	} = options;
+	const indirectBuffer = bvh._indirectBuffer;
 	const geometry = bvh.geometry;
 	const indexArray = geometry.index ? geometry.index.array : null;
-	const maxDepth = options.maxDepth;
-	const verbose = options.verbose;
-	const maxLeafTris = options.maxLeafTris;
-	const strategy = options.strategy;
-	const onProgress = options.onProgress;
+	const partionFunc = indirect ? partition_indirect : partition;
+
+	// generate intermediate variables
 	const totalTriangles = getTriCount( geometry );
-	const indirectBuffer = bvh._indirectBuffer;
+	const cacheCentroidBoundingData = new Float32Array( 6 );
 	let reachedMaxDepth = false;
 
-	const fullBounds = new Float32Array( 6 );
-	const cacheCentroidBoundingData = new Float32Array( 6 );
-	const triangleBounds = computeTriangleBounds( geometry, fullBounds );
-	const partionFunc = options.indirect ? partition_indirect : partition;
+	const root = new MeshBVHNode();
+	getBounds( triangleBounds, offset, count, root.boundingData, cacheCentroidBoundingData );
+	splitNode( root, offset, count, cacheCentroidBoundingData );
+	return root;
 
-	const roots = [];
-	const ranges = options.indirect ? getFullGeometryRange( geometry ) : getRootIndexRanges( geometry );
-
-	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 triggerProgress( trianglesProcessed ) {
@@ -145,3 +121,2 @@
 			node.left = left;
-			left.boundingData = new Float32Array( 6 );
 
@@ -156,3 +131,2 @@ getBounds( triangleBounds, lstart, lcount, left.boundingData, cacheCentroidBoundingData );
 			node.right = right;
-			right.boundingData = new Float32Array( 6 );
 
@@ -194,89 +168,16 @@ getBounds( triangleBounds, rstart, rcount, right.boundingData, cacheCentroidBoundingData );
 
-	// boundingData  				: 6 float32
-	// right / offset 				: 1 uint32
-	// splitAxis / isLeaf + count 	: 1 uint32 / 2 uint16
-	const roots = buildTree( bvh, 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 triangleBounds = computeTriangleBounds( geometry );
+	const geometryRanges = options.indirect ? getFullGeometryRange( geometry ) : getRootIndexRanges( geometry );
+	bvh._roots = geometryRanges.map( range => {
 
+		const root = buildTree( bvh, triangleBounds, range.offset, range.count, options );
+		const 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 );
+		populateBuffer( 0, root, buffer );
+		return buffer;
 
-	}
+	} );
 
-	bvh._roots = packedRoots;
-	return;
-
-	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;
-
-		}
-
-	}
-
 }

src/core/build/computeBoundsUtils.js

 import { FLOAT32_EPSILON } from '../Constants.js';
-import { makeEmptyBounds } from '../../utils/ArrayBoxUtilities.js';
 import { getTriCount } from './geometryUtils.js';
 
-// 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.
+// computes the union of the bounds of all of the given triangles and puts the resulting box in "target".
+// A bounding box is computed for the centroids of the triangles, as well, and placed in "centroidTarget".
 // These are computed together to avoid redundant accesses to bounds array.
-export function getBounds( triangleBounds, offset, count, target, centroidTarget = null ) {
+export function getBounds( triangleBounds, offset, count, target, centroidTarget ) {
 
@@ -24,3 +23,2 @@ let minx = Infinity;
 
-	const includeCentroid = centroidTarget !== null;
 	for ( let i = offset * 6, end = ( offset + count ) * 6; i < end; i += 6 ) {
@@ -34,4 +32,4 @@
 		if ( rx > maxx ) maxx = rx;
-		if ( includeCentroid && cx < cminx ) cminx = cx;
-		if ( includeCentroid && cx > cmaxx ) cmaxx = cx;
+		if ( cx < cminx ) cminx = cx;
+		if ( cx > cmaxx ) cmaxx = cx;
 
@@ -44,4 +42,4 @@ const cy = triangleBounds[ i + 2 ];
 		if ( ry > maxy ) maxy = ry;
-		if ( includeCentroid && cy < cminy ) cminy = cy;
-		if ( includeCentroid && cy > cmaxy ) cmaxy = cy;
+		if ( cy < cminy ) cminy = cy;
+		if ( cy > cmaxy ) cmaxy = cy;
 
@@ -54,4 +52,4 @@ const cz = triangleBounds[ i + 4 ];
 		if ( rz > maxz ) maxz = rz;
-		if ( includeCentroid && cz < cminz ) cminz = cz;
-		if ( includeCentroid && cz > cmaxz ) cmaxz = cz;
+		if ( cz < cminz ) cminz = cz;
+		if ( cz > cmaxz ) cmaxz = cz;
 
@@ -68,42 +66,2 @@ }
 
-	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.
-export 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;
@@ -119,3 +77,2 @@ centroidTarget[ 1 ] = cminy;
 
-
 // precomputes the bounding box for each triangle; required for quickly calculating tree splits.
@@ -125,13 +82,23 @@ // result is an array of size tris.length * 6 where triangle i maps to a
 // representing the center and half-extent in each dimension of triangle i
-export function computeTriangleBounds( geo, fullBounds ) {
+export function computeTriangleBounds( geo, target = null, offset = null, count = null ) {
 
-	// clear the bounds to empty
-	makeEmptyBounds( fullBounds );
-
 	const posAttr = geo.attributes.position;
 	const index = geo.index ? geo.index.array : null;
 	const triCount = getTriCount( geo );
-	const triangleBounds = new Float32Array( triCount * 6 );
 	const normalized = posAttr.normalized;
+	let triangleBounds;
+	if ( target === null ) {
 
+		triangleBounds = new Float32Array( triCount * 6 * 4 );
+		offset = 0;
+		count = triCount;
+
+	} else {
+
+		triangleBounds = target;
+		offset = offset || 0;
+		count = count || triCount;
+
+	}
+
 	// used for non-normalized positions
@@ -152,3 +119,3 @@ const posArr = posAttr.array;
 
-	for ( let tri = 0; tri < triCount; tri ++ ) {
+	for ( let tri = offset; tri < offset + count; tri ++ ) {
 
@@ -214,5 +181,2 @@ const tri3 = tri * 3;
 
-			if ( min < fullBounds[ el ] ) fullBounds[ el ] = min;
-			if ( max > fullBounds[ el + 3 ] ) fullBounds[ el + 3 ] = max;
-
 		}
@@ -219,0 +183,0 @@

src/core/MeshBVH.js

@@ -29,2 +29,12 @@ import { BufferAttribute, Box3, FrontSide } from 'three';
 const tempBox = /* @__PURE__ */ new Box3();
+export const DEFAULT_OPTIONS = {
+	strategy: CENTER,
+	maxDepth: 40,
+	maxLeafTris: 10,
+	useSharedArrayBuffer: false,
+	setBoundingBox: true,
+	onProgress: null,
+	indirect: false,
+	verbose: true,
+};
 
@@ -122,10 +132,3 @@ export class MeshBVH {
 
-			strategy: CENTER,
-			maxDepth: 40,
-			maxLeafTris: 10,
-			verbose: true,
-			useSharedArrayBuffer: false,
-			setBoundingBox: true,
-			onProgress: null,
-			indirect: false,
+			...DEFAULT_OPTIONS,
 
@@ -132,0 +135,0 @@ // undocumented options

src/core/MeshBVHNode.js

@@ -8,4 +8,6 @@ export class MeshBVHNode {
 
+		this.boundingData = new Float32Array( 6 );
+
 	}
 
 }

src/debug/Debug.js

@@ -195,8 +195,17 @@ import { Box3, Vector3 } from 'three';
 			// check triangles
-			for ( let i = offset * 3, l = ( offset + count ) * 3; i < l; i += 3 ) {
+			for ( let i = offset, l = offset + count; i < l; i ++ ) {
 
-				const i0 = index.getX( i );
-				const i1 = index.getX( i + 1 );
-				const i2 = index.getX( i + 2 );
+				const triIndex = bvh.resolveTriangleIndex( i );
+				let i0 = 3 * triIndex;
+				let i1 = 3 * triIndex + 1;
+				let i2 = 3 * triIndex + 2;
 
+				if ( index ) {
+
+					i0 = index.getX( i0 );
+					i1 = index.getX( i1 );
+					i2 = index.getX( i2 );
+
+				}
+
 				let isContained;
@@ -203,0 +212,0 @@

src/objects/MeshBVHHelper.js

@@ -58,3 +58,3 @@ import { LineBasicMaterial, BufferAttribute, Box3, Group, MeshBasicMaterial, Object3D, BufferGeometry } from 'three';
 
-				if ( depth === targetDepth || isLeaf ) {
+				if ( depth >= targetDepth || isLeaf ) {
 
@@ -77,3 +77,3 @@ boundsCount ++;
 
-				const terminate = depth === targetDepth || isLeaf;
+				const terminate = depth >= targetDepth || isLeaf;
 				if ( terminate || displayParents ) {
@@ -239,4 +239,4 @@
 
+			depth = bvh;
 			bvh = null;
-			depth = bvh;
 
@@ -243,0 +243,0 @@ }

src/utils/BufferUtils.js

@@ -6,1 +6,37 @@ export function isSharedArrayBufferSupported() {
 }
+
+export function convertToBufferType( array, BufferConstructor ) {
+
+	if ( array === null ) {
+
+		return array;
+
+	} else if ( array.buffer ) {
+
+		const buffer = array.buffer;
+		if ( buffer.constructor === BufferConstructor ) {
+
+			return array;
+
+		}
+
+		const ArrayConstructor = array.constructor;
+		const result = new ArrayConstructor( new BufferConstructor( buffer.byteLength ) );
+		result.set( array );
+		return result;
+
+	} else {
+
+		if ( array.constructor === BufferConstructor ) {
+
+			return array;
+
+		}
+
+		const result = new BufferConstructor( array.byteLength );
+		new Uint8Array( result ).set( new Uint8Array( array ) );
+		return result;
+
+	}
+
+}

src/workers/GenerateMeshBVHWorker.js

 import { Box3, BufferAttribute } from 'three';
 import { MeshBVH } from '../core/MeshBVH.js';
+import { WorkerBase } from './utils/WorkerBase.js';
 
-export class GenerateMeshBVHWorker {
+export class GenerateMeshBVHWorker extends WorkerBase {
 
 	constructor() {
 
-		this.running = false;
-		this.worker = new Worker( new URL( './generateAsync.worker.js', import.meta.url ), { type: 'module' } );
-		this.worker.onerror = e => {
+		const worker = new Worker( new URL( './generateMeshBVH.worker.js', import.meta.url ), { type: 'module' } );
+		super( worker );
+		this.name = 'GenerateMeshBVHWorker';
 
-			if ( e.message ) {
-
-				throw new Error( `GenerateMeshBVHWorker: Could not create Web Worker with error "${ e.message }"` );
-
-			} else {
-
-				throw new Error( 'GenerateMeshBVHWorker: Could not create Web Worker.' );
-
-			}
-
-		};
-
 	}
 
-	generate( geometry, options = {} ) {
+	runTask( worker, geometry, options = {} ) {
 
-		if ( this.running ) {
+		return new Promise( ( resolve, reject ) => {
 
-			throw new Error( 'GenerateMeshBVHWorker: Already running job.' );
+			if (
+				geometry.getAttribute( 'position' ).isInterleavedBufferAttribute ||
+				geometry.index && geometry.index.isInterleavedBufferAttribute
+			) {
 
-		}
+				throw new Error( 'GenerateMeshBVHWorker: InterleavedBufferAttribute are not supported for the geometry attributes.' );
 
-		if ( this.worker === null ) {
+			}
 
-			throw new Error( 'GenerateMeshBVHWorker: Worker has been disposed.' );
-
-		}
-
-		const { worker } = this;
-		this.running = true;
-
-		return new Promise( ( resolve, reject ) => {
-
 			worker.onerror = e => {
 
 				reject( new Error( `GenerateMeshBVHWorker: ${ e.message }` ) );
-				this.running = false;
 
@@ -54,3 +36,2 @@ };
 
-				this.running = false;
 				const { data } = e;
@@ -106,9 +87,2 @@
 			const position = geometry.attributes.position.array;
-
-			if ( position.isInterleavedBufferAttribute || index && index.isInterleavedBufferAttribute ) {
-
-				throw new Error( 'GenerateMeshBVHWorker: InterleavedBufferAttribute are not supported for the geometry attributes.' );
-
-			}
-
 			const transferable = [ position ];
@@ -138,9 +112,2 @@ if ( index ) {
 
-	dispose() {
-
-		this.worker.terminate();
-		this.worker = null;
-
-	}
-
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

1520587

increased by0.6%

Number of package files

74

increased by7.25%

Lines of code

17328

increased by2.24%

Number of lines in readme file

1134

increased by1.43%

No dependency changes