BatchedMesh: insertion of many Geometries/Instances is slow after many deletions

[andreas-hilti]

Description

If you create a BatchedMesh, add many instances, then remove many of them and add again many instances, this is incredibly slow.

A similar effect can be observed for geometries.

Root cause seems to be the following:
BatchedMesh keeps track of the deleted ids in _availableInstanceIds or _availableGeometryIds, respectively.
For every (!) call of addInstance/addGeometry these arrays are sorted.
This implies if you delete n entities, and add n entities again, you have at least a complexity of n^2 (even ignoring the log n for now).
As a user, I would rather expect a complexity of roughly n log n for this scenario.

Reproduction steps

1. Add the tests below
2. Run them

On my laptop, each of the tests needs roughly 10s (for 50000 entities).
My estimate would be that this needs to be possible in less than roughly 0.1s.
(You can make it more extreme by increasing n.)

Code

QUnit.test( 'performance1', ( assert ) => {

	const box = new BoxGeometry( 1, 1, 1 );
	const material = new MeshBasicMaterial( { color: 0x00ff00 } );
	
	// initialize and add a geometry into the batched mesh
	const n = 50000;
	const batchedMesh = new BatchedMesh( n, 5000, 10000, material );
	const boxGeometryId = batchedMesh.addGeometry( box );
	
	// create instances of this geometry
	let boxInstanceIds = [];
	for (let i = 0; i < n; i++){
		boxInstanceIds.push( batchedMesh.addInstance( boxGeometryId ) );
	}
	
	// remove them
	for (let boxInstanceId of boxInstanceIds){
		batchedMesh.deleteInstance( boxInstanceId );
	}

	// add them again
	boxInstanceIds = [];
	for (let i = 0; i < n; i++){
		boxInstanceIds.push( batchedMesh.addInstance( boxGeometryId ) );
	}

	assert.ok( batchedMesh.instanceCount === n, 'wrong instance count' );

} );

QUnit.test( 'performance2', ( assert ) => {

	const box = new BoxGeometry( 1, 1, 1 );
	const material = new MeshBasicMaterial( { color: 0x00ff00 } );
	
	// initialize and add a geometry into the batched mesh
	const n = 50000;
	const batchedMesh = new BatchedMesh( n, 5000*n, 10000*n, material );
	
	// create instances of this geometry
	let boxInstanceIds = [];
	let boxGeometryIds = [];
	for (let i = 0; i < n; i++){
		const boxGeometryId = batchedMesh.addGeometry( box );
		boxGeometryIds.push(boxGeometryId);
		boxInstanceIds.push( batchedMesh.addInstance( boxGeometryId ) );
	}
	
	// remove them
	// this is slow:
	// for (let boxGeometryId of boxGeometryIds){
	// 	batchedMesh.deleteGeometry( boxGeometryId );
	// }
	// this is quicker:
	for (let boxInstanceId of boxInstanceIds){
		batchedMesh.deleteInstance( boxInstanceId );
   	}
	batchedMesh.setInstanceCount(1)
	batchedMesh.setInstanceCount(n)
	for (let boxGeometryId of boxGeometryIds){
	 	batchedMesh.deleteGeometry( boxGeometryId );
	}

	// add them again
	boxInstanceIds = [];
	boxGeometryIds = [];
	for (let i = 0; i < n; i++){
		const boxGeometryId = batchedMesh.addGeometry( box );
		boxGeometryIds.push(boxGeometryId);
		boxInstanceIds.push( batchedMesh.addInstance( boxGeometryId ) );
	}

	assert.ok( batchedMesh.instanceCount === n, 'wrong instance count' );

} );		

Live example

• jsfiddle-latest-release WebGLRenderer

Screenshots

No response

Version

dev

Device

No response

Browser

No response

OS

No response