three-mesh-bvh - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

CHANGELOG.md

@@ -7,2 +7,9 @@ # Changelog
 
+## [0.1.3] - 2019-05-24
+### Added
+- Use the BufferGeometry bounding box if it exists and set it if it does not.
+
+### Changed
+- Use the center of the triangles bounding box instead of the average of the vertices as the triangles center when binning the polygons.
+
 ## [0.1.2] - 2019-03-17
@@ -9,0 +16,0 @@ ### Fixed

package.json

 {
   "name": "three-mesh-bvh",
-  "version": "0.1.2",
+  "version": "0.1.3",
   "description": "A BVH implementation to speed up raycasting against three.js meshes.",
@@ -18,2 +18,18 @@ "module": "src/index.js",
   ],
+  "keywords": [
+    "graphics",
+    "raycast",
+    "tree",
+    "bounds",
+    "threejs",
+    "three-js",
+    "bounds-hierarchy",
+    "performance",
+    "geometry",
+    "mesh",
+    "distance",
+    "intersection",
+    "acceleration",
+    "bvh"
+  ],
   "repository": {
@@ -50,5 +66,5 @@ "type": "git",
     "stats.js": "^0.17.0",
-    "three": "^0.102.1"
+    "three": "^0.104.0"
   },
   "dependencies": {}
 }

README.md

@@ -82,3 +82,3 @@ # three-mesh-bvh
 
-The generated attribute buffer based on the original mesh index in an order sorted for storing bounds triangles. The BVH will no longer work correctly if this buffer is modified.
+The generated attribute buffer based on the original mesh index in an order sorted for storing bounds triangles. The BVH construction will use the geometry's boundingBox if it exists or set it if it does not. The BVH will no longer work correctly if this buffer is modified.
 
@@ -85,0 +85,0 @@ #### constructor(geometry: BufferGeometry, options: Object)

src/BVHConstructionContext.js

@@ -7,12 +7,7 @@ import * as THREE from 'three';
 
-// precomputes data about each triangle required for quickly calculating tree splits:
-//
-// - bounds: an array of size tris.length * 6 where triangle i maps to a
-//   [x_min, x_max, y_min, y_max, z_min, z_max] tuple starting at index i * 6,
-//   representing the minimum and maximum extent in each dimension of triangle i
-//
-// - centroids: an array of size tris.length * 3 where triangle i maps to an [x, y, z] triplet
-//   starting at index i * 3, representing the centroid of triangle i
-//
-function computeTriangleData( geo ) {
+// 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 computeBounds( geo ) {
 
@@ -23,3 +18,2 @@ const verts = geo.attributes.position.array;
 	const bounds = new Float32Array( triCount * 6 );
-	const centroids = new Float32Array( triCount * 3 );
 
@@ -37,5 +31,7 @@ for ( let tri = 0; tri < triCount; tri ++ ) {
 			const c = verts[ ci + el ];
-			bounds[ tri * 6 + el * 2 + 0 ] = Math.min( a, b, c );
-			bounds[ tri * 6 + el * 2 + 1 ] = Math.max( a, b, c );
-			centroids[ tri * 3 + el ] = ( a + b + c ) / 3;
+			const min = Math.min( a, b, c );
+			const max = Math.max( a, b, c );
+			const halfExtents = ( max - min ) / 2;
+			bounds[ tri * 6 + el * 2 + 0 ] = min + halfExtents;
+			bounds[ tri * 6 + el * 2 + 1 ] = halfExtents;
 
@@ -46,3 +42,3 @@ }
 
-	return { bounds, centroids };
+	return bounds;
 
@@ -59,7 +55,4 @@ }
 		this.options = options;
+		this.bounds = computeBounds( geo );
 
-		const data = computeTriangleData( geo );
-		this.centroids = data.centroids;
-		this.bounds = data.bounds;
-
 		// SAH Initialization
@@ -75,3 +68,3 @@ this.sahplanes = null;
 
-					this.sahplanes[ el ][ tri ] = { p: this.centroids[ tri * 3 + el ], tri };
+					this.sahplanes[ el ][ tri ] = { p: this.bounds[ tri * 6 + el * 2 ], tri };
 
@@ -90,7 +83,7 @@ }
 		let avg = 0;
-		const centroids = this.centroids;
+		const bounds = this.bounds;
 
 		for ( let i = offset, end = offset + count; i < end; i ++ ) {
 
-			avg += centroids[ i * 3 + axis ];
+			avg += bounds[ i * 6 + axis * 2 ];
 
@@ -116,8 +109,14 @@ }
 
-			minx = Math.min( minx, bounds[ i * 6 + 0 ] );
-			maxx = Math.max( maxx, bounds[ i * 6 + 1 ] );
-			miny = Math.min( miny, bounds[ i * 6 + 2 ] );
-			maxy = Math.max( maxy, bounds[ i * 6 + 3 ] );
-			minz = Math.min( minz, bounds[ i * 6 + 4 ] );
-			maxz = Math.max( maxz, bounds[ i * 6 + 5 ] );
+			const cx = bounds[ i * 6 + 0 ];
+			const hx = bounds[ i * 6 + 1 ];
+			minx = Math.min( minx, cx - hx );
+			maxx = Math.max( maxx, cx + hx );
+			const cy = bounds[ i * 6 + 2 ];
+			const hy = bounds[ i * 6 + 3 ];
+			miny = Math.min( miny, cy - hy );
+			maxy = Math.max( maxy, cy + hy );
+			const cz = bounds[ i * 6 + 4 ];
+			const hz = bounds[ i * 6 + 5 ];
+			minz = Math.min( minz, cz - hz );
+			maxz = Math.max( maxz, cz + hz );
 
@@ -146,5 +145,4 @@ }
 		const pos = split.pos;
-		const axis = split.axis;
+		const axisOffset = split.axis * 2;
 		const index = this.geo.index.array;
-		const centroids = this.centroids;
 		const bounds = this.bounds;
@@ -156,3 +154,3 @@ const sahplanes = this.sahplanes;
 
-			while ( left <= right && centroids[ left * 3 + axis ] < pos ) {
+			while ( left <= right && bounds[ left * 6 + axisOffset ] < pos ) {
 
@@ -163,3 +161,3 @@ left ++;
 
-			while ( left <= right && centroids[ right * 3 + axis ] >= pos ) {
+			while ( left <= right && bounds[ right * 6 + axisOffset ] >= pos ) {
 
@@ -173,3 +171,3 @@ 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 centroids, the bounds,
+				// left and right; that's the verts in the geometry index, the bounds,
 				// and perhaps the SAH planes
@@ -182,13 +180,8 @@
 					index[ right * 3 + i ] = t0;
-
-					let t1 = centroids[ left * 3 + i ];
-					centroids[ left * 3 + i ] = centroids[ right * 3 + i ];
-					centroids[ right * 3 + i ] = t1;
-
-					let t2 = bounds[ left * 6 + i * 2 + 0 ];
+					let t1 = bounds[ left * 6 + i * 2 + 0 ];
 					bounds[ left * 6 + i * 2 + 0 ] = bounds[ right * 6 + i * 2 + 0 ];
-					bounds[ right * 6 + i * 2 + 0 ] = t2;
-					let t3 = bounds[ left * 6 + i * 2 + 1 ];
+					bounds[ right * 6 + i * 2 + 0 ] = t1;
+					let t2 = bounds[ left * 6 + i * 2 + 1 ];
 					bounds[ left * 6 + i * 2 + 1 ] = bounds[ right * 6 + i * 2 + 1 ];
-					bounds[ right * 6 + i * 2 + 1 ] = t3;
+					bounds[ right * 6 + i * 2 + 1 ] = t2;
 
@@ -195,0 +188,0 @@ }

src/MeshBVH.js

 import * as THREE from 'three';
 import MeshBVHNode from './MeshBVHNode.js';
 import BVHConstructionContext from './BVHConstructionContext.js';
+import { arrayToBox, boxToArray } from './Utils/ArrayBoxUtilities.js';
 import { CENTER } from './Constants.js';
@@ -170,14 +171,29 @@
 
-		for ( let range of ranges ) {
+		if ( ranges.length === 1 ) {
 
 			const root = new MeshBVHNode();
-			root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+			const range = ranges[ 0 ];
+
+			if ( geo.boundingBox != null ) {
+
+				root.boundingData = boxToArray( geo.boundingBox );
+
+			} else {
+
+				root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+
+			}
+
 			splitNode( root, range.offset, range.count );
 			roots.push( root );
 
-			if ( reachedMaxDepth && options.verbose ) {
+		} else {
 
-				console.warn( `MeshBVH: Max depth of ${ options.maxDepth } reached when generating BVH. Consider increasing maxDepth.` );
-				console.warn( this, geo );
+			for ( let range of ranges ) {
 
+				const root = new MeshBVHNode();
+				root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+				splitNode( root, range.offset, range.count );
+				roots.push( root );
+
 			}
@@ -187,2 +203,25 @@
 
+		if ( reachedMaxDepth && options.verbose ) {
+
+			console.warn( `MeshBVH: Max depth of ${ options.maxDepth } reached when generating BVH. Consider increasing maxDepth.` );
+			console.warn( this, geo );
+
+		}
+
+		// if the geometry doesn't have a bounding box, then let's politely populate it using
+		// the work we did to determine the BVH root bounds
+
+		if ( geo.boundingBox == null ) {
+
+			const rootBox = new THREE.Box3();
+			geo.boundingBox = new THREE.Box3();
+
+			for ( let root of roots ) {
+
+				geo.boundingBox.union( arrayToBox( root.boundingData, rootBox ) );
+
+			}
+
+		}
+
 		return roots;
@@ -189,0 +228,0 @@

src/MeshBVHNode.js

@@ -215,4 +215,5 @@
 
+			const isC1Leaf = ! ! c1.count;
 			const c1Intersection =
-				intersectsBoundsFunc( box1, ! ! c1.count, score1 ) &&
+				intersectsBoundsFunc( box1, isC1Leaf, score1, c1 ) &&
 				c1.shapecast( mesh, intersectsBoundsFunc, intersectsTriangleFunc, nodeScoreFunc );
@@ -230,4 +231,5 @@
 
+			const isC2Leaf = ! ! c2.count;
 			const c2Intersection =
-				intersectsBoundsFunc( box2, ! ! c2.count, score2 ) &&
+				intersectsBoundsFunc( box2, isC2Leaf, score2, c2 ) &&
 				c2.shapecast( mesh, intersectsBoundsFunc, intersectsTriangleFunc, nodeScoreFunc );
@@ -234,0 +236,0 @@

umd/index.js

@@ -1338,4 +1338,5 @@ (function (global, factory) {
 
+				const isC1Leaf = ! ! c1.count;
 				const c1Intersection =
-					intersectsBoundsFunc( box1, ! ! c1.count, score1 ) &&
+					intersectsBoundsFunc( box1, isC1Leaf, score1, c1 ) &&
 					c1.shapecast( mesh, intersectsBoundsFunc, intersectsTriangleFunc, nodeScoreFunc );
@@ -1353,4 +1354,5 @@
 
+				const isC2Leaf = ! ! c2.count;
 				const c2Intersection =
-					intersectsBoundsFunc( box2, ! ! c2.count, score2 ) &&
+					intersectsBoundsFunc( box2, isC2Leaf, score2, c2 ) &&
 					c2.shapecast( mesh, intersectsBoundsFunc, intersectsTriangleFunc, nodeScoreFunc );
@@ -1653,12 +1655,7 @@
 
-	// precomputes data about each triangle required for quickly calculating tree splits:
-	//
-	// - bounds: an array of size tris.length * 6 where triangle i maps to a
-	//   [x_min, x_max, y_min, y_max, z_min, z_max] tuple starting at index i * 6,
-	//   representing the minimum and maximum extent in each dimension of triangle i
-	//
-	// - centroids: an array of size tris.length * 3 where triangle i maps to an [x, y, z] triplet
-	//   starting at index i * 3, representing the centroid of triangle i
-	//
-	function computeTriangleData( geo ) {
+	// 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 computeBounds( geo ) {
 
@@ -1669,3 +1666,2 @@ const verts = geo.attributes.position.array;
 		const bounds = new Float32Array( triCount * 6 );
-		const centroids = new Float32Array( triCount * 3 );
 
@@ -1683,5 +1679,7 @@ for ( let tri = 0; tri < triCount; tri ++ ) {
 				const c = verts[ ci + el ];
-				bounds[ tri * 6 + el * 2 + 0 ] = Math.min( a, b, c );
-				bounds[ tri * 6 + el * 2 + 1 ] = Math.max( a, b, c );
-				centroids[ tri * 3 + el ] = ( a + b + c ) / 3;
+				const min = Math.min( a, b, c );
+				const max = Math.max( a, b, c );
+				const halfExtents = ( max - min ) / 2;
+				bounds[ tri * 6 + el * 2 + 0 ] = min + halfExtents;
+				bounds[ tri * 6 + el * 2 + 1 ] = halfExtents;
 
@@ -1692,3 +1690,3 @@ }
 
-		return { bounds, centroids };
+		return bounds;
 
@@ -1705,7 +1703,4 @@ }
 			this.options = options;
+			this.bounds = computeBounds( geo );
 
-			const data = computeTriangleData( geo );
-			this.centroids = data.centroids;
-			this.bounds = data.bounds;
-
 			// SAH Initialization
@@ -1721,3 +1716,3 @@ this.sahplanes = null;
 
-						this.sahplanes[ el ][ tri ] = { p: this.centroids[ tri * 3 + el ], tri };
+						this.sahplanes[ el ][ tri ] = { p: this.bounds[ tri * 6 + el * 2 ], tri };
 
@@ -1736,7 +1731,7 @@ }
 			let avg = 0;
-			const centroids = this.centroids;
+			const bounds = this.bounds;
 
 			for ( let i = offset, end = offset + count; i < end; i ++ ) {
 
-				avg += centroids[ i * 3 + axis ];
+				avg += bounds[ i * 6 + axis * 2 ];
 
@@ -1762,8 +1757,14 @@ }
 
-				minx = Math.min( minx, bounds[ i * 6 + 0 ] );
-				maxx = Math.max( maxx, bounds[ i * 6 + 1 ] );
-				miny = Math.min( miny, bounds[ i * 6 + 2 ] );
-				maxy = Math.max( maxy, bounds[ i * 6 + 3 ] );
-				minz = Math.min( minz, bounds[ i * 6 + 4 ] );
-				maxz = Math.max( maxz, bounds[ i * 6 + 5 ] );
+				const cx = bounds[ i * 6 + 0 ];
+				const hx = bounds[ i * 6 + 1 ];
+				minx = Math.min( minx, cx - hx );
+				maxx = Math.max( maxx, cx + hx );
+				const cy = bounds[ i * 6 + 2 ];
+				const hy = bounds[ i * 6 + 3 ];
+				miny = Math.min( miny, cy - hy );
+				maxy = Math.max( maxy, cy + hy );
+				const cz = bounds[ i * 6 + 4 ];
+				const hz = bounds[ i * 6 + 5 ];
+				minz = Math.min( minz, cz - hz );
+				maxz = Math.max( maxz, cz + hz );
 
@@ -1792,5 +1793,4 @@ }
 			const pos = split.pos;
-			const axis = split.axis;
+			const axisOffset = split.axis * 2;
 			const index = this.geo.index.array;
-			const centroids = this.centroids;
 			const bounds = this.bounds;
@@ -1802,3 +1802,3 @@ const sahplanes = this.sahplanes;
 
-				while ( left <= right && centroids[ left * 3 + axis ] < pos ) {
+				while ( left <= right && bounds[ left * 6 + axisOffset ] < pos ) {
 
@@ -1809,3 +1809,3 @@ left ++;
 
-				while ( left <= right && centroids[ right * 3 + axis ] >= pos ) {
+				while ( left <= right && bounds[ right * 6 + axisOffset ] >= pos ) {
 
@@ -1819,3 +1819,3 @@ 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 centroids, the bounds,
+					// left and right; that's the verts in the geometry index, the bounds,
 					// and perhaps the SAH planes
@@ -1828,13 +1828,8 @@
 						index[ right * 3 + i ] = t0;
-
-						let t1 = centroids[ left * 3 + i ];
-						centroids[ left * 3 + i ] = centroids[ right * 3 + i ];
-						centroids[ right * 3 + i ] = t1;
-
-						let t2 = bounds[ left * 6 + i * 2 + 0 ];
+						let t1 = bounds[ left * 6 + i * 2 + 0 ];
 						bounds[ left * 6 + i * 2 + 0 ] = bounds[ right * 6 + i * 2 + 0 ];
-						bounds[ right * 6 + i * 2 + 0 ] = t2;
-						let t3 = bounds[ left * 6 + i * 2 + 1 ];
+						bounds[ right * 6 + i * 2 + 0 ] = t1;
+						let t2 = bounds[ left * 6 + i * 2 + 1 ];
 						bounds[ left * 6 + i * 2 + 1 ] = bounds[ right * 6 + i * 2 + 1 ];
-						bounds[ right * 6 + i * 2 + 1 ] = t3;
+						bounds[ right * 6 + i * 2 + 1 ] = t2;
 
@@ -2201,14 +2196,29 @@ }
 
-			for ( let range of ranges ) {
+			if ( ranges.length === 1 ) {
 
 				const root = new MeshBVHNode();
-				root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+				const range = ranges[ 0 ];
+
+				if ( geo.boundingBox != null ) {
+
+					root.boundingData = boxToArray( geo.boundingBox );
+
+				} else {
+
+					root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+
+				}
+
 				splitNode( root, range.offset, range.count );
 				roots.push( root );
 
-				if ( reachedMaxDepth && options.verbose ) {
+			} else {
 
-					console.warn( `MeshBVH: Max depth of ${ options.maxDepth } reached when generating BVH. Consider increasing maxDepth.` );
-					console.warn( this, geo );
+				for ( let range of ranges ) {
 
+					const root = new MeshBVHNode();
+					root.boundingData = ctx.getBounds( range.offset, range.count, new Float32Array( 6 ) );
+					splitNode( root, range.offset, range.count );
+					roots.push( root );
+
 				}
@@ -2218,2 +2228,25 @@
 
+			if ( reachedMaxDepth && options.verbose ) {
+
+				console.warn( `MeshBVH: Max depth of ${ options.maxDepth } reached when generating BVH. Consider increasing maxDepth.` );
+				console.warn( this, geo );
+
+			}
+
+			// if the geometry doesn't have a bounding box, then let's politely populate it using
+			// the work we did to determine the BVH root bounds
+
+			if ( geo.boundingBox == null ) {
+
+				const rootBox = new THREE.Box3();
+				geo.boundingBox = new THREE.Box3();
+
+				for ( let root of roots ) {
+
+					geo.boundingBox.union( arrayToBox( root.boundingData, rootBox ) );
+
+				}
+
+			}
+
 			return roots;
@@ -2220,0 +2253,0 @@

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

277403

increased by0.51%

Lines of code

3309

increased by1.19%

No dependency changes