Repository: gkjohnson/three-mesh-bvh
Pull request #626 (2024-01-27 08:19:22)

Small built tree cleanup
Merge some logic between single root and multiple roots

**TODO**
- perf test


Patch:
diff --git a/src/core/build/buildTree.js b/src/core/build/buildTree.js
index cac0056..52338c2 100644
--- a/src/core/build/buildTree.js
+++ b/src/core/build/buildTree.js
@@ -1,5 +1,5 @@
 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';
@@ -30,48 +30,34 @@ function buildTree( bvh, 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.
+	const {
+		maxDepth,
+		verbose,
+		maxLeafTris,
+		strategy,
+		onProgress,
+	} = 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 totalTriangles = getTriCount( geometry );
-	const indirectBuffer = bvh._indirectBuffer;
 	let reachedMaxDepth = false;
 
-	const fullBounds = new Float32Array( 6 );
 	const cacheCentroidBoundingData = new Float32Array( 6 );
-	const triangleBounds = computeTriangleBounds( geometry, fullBounds );
+	const triangleBounds = computeTriangleBounds( geometry );
 	const partionFunc = options.indirect ? partition_indirect : partition;
 
 	const roots = [];
 	const ranges = options.indirect ? getFullGeometryRange( geometry ) : getRootIndexRanges( geometry );
+	for ( let range of ranges ) {
 
-	if ( ranges.length === 1 ) {
-
-		const range = ranges[ 0 ];
 		const root = new MeshBVHNode();
-		root.boundingData = fullBounds;
-		getCentroidBounds( triangleBounds, range.offset, range.count, cacheCentroidBoundingData );
+		root.boundingData = new Float32Array( 6 );
+		getBounds( triangleBounds, range.offset, range.count, root.boundingData, 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;
diff --git a/src/core/build/computeBoundsUtils.js b/src/core/build/computeBoundsUtils.js
index a8c6afe..19b2617 100644
--- a/src/core/build/computeBoundsUtils.js
+++ b/src/core/build/computeBoundsUtils.js
@@ -1,11 +1,10 @@
 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 ) {
 
 	let minx = Infinity;
 	let miny = Infinity;
@@ -21,7 +20,6 @@ export function getBounds( triangleBounds, offset, count, target, centroidTarget
 	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 ];
@@ -30,8 +28,8 @@ export function getBounds( triangleBounds, offset, count, target, centroidTarget
 		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;
+		if ( cx < cminx ) cminx = cx;
+		if ( cx > cmaxx ) cmaxx = cx;
 
 		const cy = triangleBounds[ i + 2 ];
 		const hy = triangleBounds[ i + 3 ];
@@ -39,8 +37,8 @@ export function getBounds( triangleBounds, offset, count, target, centroidTarget
 		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;
+		if ( cy < cminy ) cminy = cy;
+		if ( cy > cmaxy ) cmaxy = cy;
 
 		const cz = triangleBounds[ i + 4 ];
 		const hz = triangleBounds[ i + 5 ];
@@ -48,8 +46,8 @@ export function getBounds( triangleBounds, offset, count, target, centroidTarget
 		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;
+		if ( cz < cminz ) cminz = cz;
+		if ( cz > cmaxz ) cmaxz = cz;
 
 	}
 
@@ -61,46 +59,6 @@ export function getBounds( triangleBounds, offset, count, target, centroidTarget
 	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.
-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;
 	centroidTarget[ 1 ] = cminy;
 	centroidTarget[ 2 ] = cminz;
@@ -111,15 +69,11 @@ export function getCentroidBounds( triangleBounds, offset, count, centroidTarget
 
 }
 
-
 // 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
-export function computeTriangleBounds( geo, fullBounds ) {
-
-	// clear the bounds to empty
-	makeEmptyBounds( fullBounds );
+export function computeTriangleBounds( geo ) {
 
 	const posAttr = geo.attributes.position;
 	const index = geo.index ? geo.index.array : null;
@@ -203,9 +157,6 @@ export function computeTriangleBounds( geo, fullBounds ) {
 			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;
-
 		}
 
 	}


Test patch:
diff --git a/test/MeshBVH.test.js b/test/MeshBVH.test.js
index 322b329..7101f66 100644
--- a/test/MeshBVH.test.js
+++ b/test/MeshBVH.test.js
@@ -37,7 +37,14 @@ describe( 'Bounds Tree', () => {
 		const box = new Box3();
 		bvh.getBoundingBox( box );
 
-		expect( box ).toEqual( geom.boundingBox );
+		// the bvh bounds are expanded slightly to accommodate flighting point error differences
+		expect( box.min.x ).toBeCloseTo( geom.boundingBox.min.x );
+		expect( box.min.y ).toBeCloseTo( geom.boundingBox.min.y );
+		expect( box.min.z ).toBeCloseTo( geom.boundingBox.min.z );
+
+		expect( box.max.x ).toBeCloseTo( geom.boundingBox.max.x );
+		expect( box.max.y ).toBeCloseTo( geom.boundingBox.max.y );
+		expect( box.max.z ).toBeCloseTo( geom.boundingBox.max.z );
 
 	} );