Repository: gkjohnson/three-mesh-bvh (js)

Issue:
MeshBVH index offset for merged geometries into one buffer
<!-- Ignoring this template may result in your feature request getting deleted -->

Hello gkjohnson, it's been a while :)

#### Is your feature request related to a problem? Please describe.

I'm trying to load a huge number of objects in a scene, with precomputed BVH trees, and I want to merge these objects to have one draw call (at least, less).

Let's say I have N different indexed geometries with their own BVH and that I merge these geometries into a big one (by concatenating index and position buffers).

Now, let's say, I don't keep individual geometries in memory, but only BVH trees. If I give to each BVH trees a reference to the merged geometry instead of the individual ones, I have no way of telling each BVH tree that the vertex indices it is interest in start at a certain offset in the buffer.

#### Describe the solution you'd like

Add a offset param to the MeshBVH to tell where the indice "0" really starts 

#### Describe alternatives you've

Alternative 1:
Keep individual geometries in memory to perform BVH operations.
con: memory cost

Alternative 2:
Generate a BVH for the merged geometry
con: computation cost for millions of triangles.






Pull request description:
feat: add range option to MeshBVH

- Adds a new range option that acts "as drawRange"
- Should allow multiple BVH on the same geometry with different ranges (useful for Three BatchedMesh)

Closes #513

Patch:
diff --git a/.gitignore b/.gitignore
index 945f210..8aa61a4 100644
--- a/.gitignore
+++ b/.gitignore
@@ -66,3 +66,5 @@ example/dev-bundle
 *.generated.js
 
 build/**
+
+.vscode
diff --git a/README.md b/README.md
index 93da3c8..a41a0f8 100644
--- a/README.md
+++ b/README.md
@@ -354,6 +354,10 @@ Constructs the bounds tree for the given geometry and produces a new index attri
     // Print out warnings encountered during tree construction.
     verbose: true,
 
+		// If given, the MeshBVH will be computed for the given range on the geometry.
+		// Default range is { start: 0, count: Infinity }
+		range: { start: number, count: number }
+
 }
 ```
 
diff --git a/src/core/MeshBVH.js b/src/core/MeshBVH.js
index e0d9e8e..259b104 100644
--- a/src/core/MeshBVH.js
+++ b/src/core/MeshBVH.js
@@ -35,6 +35,7 @@ export const DEFAULT_OPTIONS = {
 	onProgress: null,
 	indirect: false,
 	verbose: true,
+	range: { start: 0, count: Infinity }
 };
 
 export class MeshBVH {
diff --git a/src/core/build/buildTree.js b/src/core/build/buildTree.js
index 702bf0a..daa9d69 100644
--- a/src/core/build/buildTree.js
+++ b/src/core/build/buildTree.js
@@ -165,7 +165,7 @@ export function buildPackedTree( bvh, options ) {
 	const BufferConstructor = options.useSharedArrayBuffer ? SharedArrayBuffer : ArrayBuffer;
 
 	const triangleBounds = computeTriangleBounds( geometry );
-	const geometryRanges = options.indirect ? getFullGeometryRange( geometry ) : getRootIndexRanges( geometry );
+	const geometryRanges = options.indirect ? getFullGeometryRange( geometry, options.range ) : getRootIndexRanges( geometry, options.range );
 	bvh._roots = geometryRanges.map( range => {
 
 		const root = buildTree( bvh, triangleBounds, range.offset, range.count, options );
diff --git a/src/core/build/geometryUtils.js b/src/core/build/geometryUtils.js
index 4a6aa29..0342f8b 100644
--- a/src/core/build/geometryUtils.js
+++ b/src/core/build/geometryUtils.js
@@ -57,12 +57,18 @@ export function ensureIndex( geo, options ) {
 //                      g1 = [16, 40]           g2 = [41, 60]
 //
 // we would need four BVH roots: [0, 15], [16, 20], [21, 40], [41, 60].
-export function getFullGeometryRange( geo ) {
+export function getFullGeometryRange( geo, range ) {
 
 	const triCount = getTriCount( geo );
-	const drawRange = geo.drawRange;
-	const start = drawRange.start / 3;
-	const end = ( drawRange.start + drawRange.count ) / 3;
+	let workingRange = geo.drawRange;
+	if ( range ) {
+
+		workingRange = getRangesIntersection( workingRange, range );
+
+	}
+
+	const start = workingRange.start / 3;
+	const end = ( workingRange.start + workingRange.count ) / 3;
 
 	const offset = Math.max( 0, start );
 	const count = Math.min( triCount, end ) - offset;
@@ -73,26 +79,32 @@ export function getFullGeometryRange( geo ) {
 
 }
 
-export function getRootIndexRanges( geo ) {
+export function getRootIndexRanges( geo, range ) {
 
 	if ( ! geo.groups || ! geo.groups.length ) {
 
-		return getFullGeometryRange( geo );
+		return getFullGeometryRange( geo, range );
 
 	}
 
 	const ranges = [];
 	const rangeBoundaries = new Set();
 
-	const drawRange = geo.drawRange;
-	const drawRangeStart = drawRange.start / 3;
-	const drawRangeEnd = ( drawRange.start + drawRange.count ) / 3;
+	let workingRange = geo.drawRange;
+	if ( range ) {
+
+		workingRange = getRangesIntersection( workingRange, range );
+
+	}
+
+	const workingRangeStart = workingRange.start / 3;
+	const workingRangeEnd = ( workingRange.start + workingRange.count ) / 3;
 	for ( const group of geo.groups ) {
 
 		const groupStart = group.start / 3;
 		const groupEnd = ( group.start + group.count ) / 3;
-		rangeBoundaries.add( Math.max( drawRangeStart, groupStart ) );
-		rangeBoundaries.add( Math.min( drawRangeEnd, groupEnd ) );
+		rangeBoundaries.add( Math.max( workingRangeStart, groupStart ) );
+		rangeBoundaries.add( Math.min( workingRangeEnd, groupEnd ) );
 
 	}
 
@@ -135,3 +147,15 @@ export function hasGroupGaps( geometry ) {
 	return vertexCount !== total;
 
 }
+
+
+export function getRangesIntersection( range1, range2 ) {
+
+	return {
+
+		start: Math.max( range1.start, range2.start ),
+		count: Math.min( range1.count, range2.count )
+
+	};
+
+}
diff --git a/src/index.d.ts b/src/index.d.ts
index 8bd9888..17e8312 100644
--- a/src/index.d.ts
+++ b/src/index.d.ts
@@ -20,6 +20,11 @@ export interface HitPointInfo {
   faceIndex: number;
 }
 
+export interface BufferRange {
+  start: number;
+  count: number;
+}
+
 export interface MeshBVHOptions {
   strategy?: SplitStrategy;
   maxDepth?: number;
@@ -28,6 +33,7 @@ export interface MeshBVHOptions {
   useSharedArrayBuffer?: boolean;
   verbose?: boolean;
   onProgress?: ( progress: number ) => void;
+  range?: BufferRange;
 }
 
 export interface MeshBVHSerializeOptions {


Test patch:
diff --git a/test/MeshBVH.options.test.js b/test/MeshBVH.options.test.js
index ac24b61..7bb4f16 100644
--- a/test/MeshBVH.options.test.js
+++ b/test/MeshBVH.options.test.js
@@ -273,4 +273,68 @@ describe( 'Options', () => {
 
 	} );
 
+	describe( 'range', () => {
+
+		let geometry;
+		beforeEach( () => {
+
+			geometry = new TorusGeometry( 5, 5, 400, 100 );
+
+		} );
+
+		it( 'should respect the range option without groups.', () => {
+
+			const bvh = new MeshBVH( geometry, { range: { start: 300, count: 600 } } );
+			let start = Infinity;
+			let end = 0;
+			bvh.traverse( ( depth, isLeaf, box, offset, count ) => {
+
+				if ( isLeaf ) {
+
+					start = Math.min( start, offset );
+					end = Math.max( end, offset + count );
+
+				}
+
+			} );
+
+			expect( start ).toBe( 100 );
+			expect( end ).toBe( 300 );
+
+		} );
+
+		it( 'should respect the range option with groups.', () => {
+
+			geometry.addGroup( 150, 300 );
+			geometry.addGroup( 450, 300 );
+
+			const bvh = new MeshBVH( geometry, { range: { start: 300, count: 600 } } );
+			let start = Infinity;
+			let end = 0;
+
+			for ( let i = 0, l = 2; i < l; i ++ ) {
+
+				bvh.traverse( ( depth, isLeaf, box, offset, count ) => {
+
+					if ( isLeaf ) {
+
+						start = Math.min( start, offset );
+						end = Math.max( end, offset + count );
+
+					}
+
+				}, i );
+
+			}
+
+			// groups from 50-150, 150-250
+			// draw range from 100-300
+			// final is 100-250
+			expect( start ).toBe( 100 );
+			expect( end ).toBe( 250 );
+
+		} );
+
+	} );
+
 } );