Prioritize loading tiles near the center of the screen

[gkjohnson]

Related to #138

https://cesium.com/blog/2019/05/07/faster-3d-tiles/

[jo-chemla]

Directions from #496

We'd need a separate error metric on the tile that scales based based on distance to the center of the screen so it can be used to sort the tiles in the download and parse queue "priority callback". Adding something like a "load order" visualization to the DebugTilesRenderer would be helpful for understanding the impact of this kind of change, as well

Dropping some notes around an implementation for potentially drafting a PR

priorityCallback

TilesRendererBase priorityCallback :

3DTilesRendererJS/src/base/TilesRendererBase.js

Lines 14 to 46 in 70c3268

	const priorityCallback = ( a, b ) => {
	if ( a.__depth !== b.__depth ) {
	// load shallower tiles first
	return a.__depth > b.__depth ? - 1 : 1;
	} else if ( a.__inFrustum !== b.__inFrustum ) {
	// load tiles that are in the frustum at the current depth
	return a.__inFrustum ? 1 : - 1;
	} else if ( a.__used !== b.__used ) {
	// load tiles that have been used
	return a.__used ? 1 : - 1;
	} else if ( a.__error !== b.__error ) {
	// load the tile with the higher error
	return a.__error > b.__error ? 1 : - 1;
	} else if ( a.__distanceFromCamera !== b.__distanceFromCamera ) {
	// and finally visible tiles which have equal error (ex: if geometricError === 0)
	// should prioritize based on distance.
	return a.__distanceFromCamera > b.__distanceFromCamera ? - 1 : 1;
	}
	return 0;
	};

Could add something like this as a final check, but the if/else cascade might mean some tests are never tested against.

	} else if ( a.__distanceFromScreenCenter !== b.__distanceFromScreenCenter ) {

		// and finally tiles closest to the center should be prioritized for faster foveated rendering.
		return a.__distanceFromScreenCenter > b.__distanceFromScreenCenter ? - 1 : 1;

	}

Would that make sense to have some hard tests which return +1/-1 like originally, but hten the final tests would return a sum of +1/-1? Something like

if ( a.__depth !== b.__depth ) { ... } 
else if ( a.__inFrustum !== b.__inFrustum ) { ... } 
else if ( a.__used !== b.__used ) { ... } 
else if ( a.__error !== b.__error )
else if (test)  {
  return (a.__distanceFromCamera > b.__distanceFromCamera) + (a.__distanceFromScreenCenter > b.__distanceFromScreenCenter)
}

Compute __distanceFromScreenCenter

Where to compute this __distanceFromScreenCenter ? Should be done in the traverseFunction file, right? Somewhere like

3DTilesRendererJS/src/base/traverseFunctions.js

Line 77 in 70c3268

child.__depthFromRenderedParent = depthFromRenderedParent;

or probably better, within

3DTilesRendererJS/src/base/traverseFunctions.js

Line 140 in 70c3268

const inFrustum = renderer.tileInView( tile );

Where we could compute the __distanceFromScreenCenter similar to the way the

3DTilesRendererJS/src/three/TilesRenderer.js

Line 902 in 70c3268

tileInView( tile ) {

It would probably make sense to simply compute the distance of the tile boundingVolume center, projected onto the screen, and measure that distance to the screen center - rather than for example computing the tile bounding volume projection surface onto the screen, and decide that that metric should be the distance between that projection area and the screen center.

DebugTilesRenderer load order" viz

Probably exactly along the lines of

3DTilesRendererJS/src/three/DebugTilesRenderer.js

Lines 333 to 341 in 70c3268

	case DISTANCE: {
	// We don't update the distance if the geometric error is 0.0 so
	// it will always be black.
	const val = Math.min( tile.__distanceFromCamera / maxDistance, 1 );
	this.getDebugColor( val, c.material.color );
	break;
	}

[gkjohnson]

Could add something like this as a final check, but the if/else cascade might mean some tests are never tested against.

This is ok and it's already the case that most of the time the final conditions are not used.

	} else if ( a.__distanceFromScreenCenter !== b.__distanceFromScreenCenter ) {

  	// and finally tiles closest to the center should be prioritized for faster foveated rendering.
  	return a.__distanceFromScreenCenter > b.__distanceFromScreenCenter ? - 1 : 1;

  }

We should compute some adjustment of screenspace error here based distance to the center so high error tiles are still prioritized - just less so if they're off on the edge of the screen. As just an example, something like screenSpaceError + screenSpaceError * distanceToCenter * 1e-2. This deserves more thought, though. Cesium's implementation might be the approach to reference here.

[jo-chemla]

This is how the cesiumjs codebase merges into a single priority metric different priorities: They store it on a base10 number which is composed of (from the Cesium3DTile.js code):

preloadFlightDigits(1) | foveatedDeferDigits(1) | foveatedDigits(4) | preloadProgressiveResolutionDigits(1) | preferredSortingDigits(4) . depthDigits(the decimal digits)

It uses two priorities for the foveated rendering, a boolean priorityDeferred (false within the cone, true outside) and a float normalizedFoveatedFactor which is is the actual priority :

The most interesting bit are probably within the function isPriorityDeferred shows that actually, within a cone with radius given in screen space, tiles loading is not deferred, and then linearly increases between that cone limit and the screen limit.

PS: interesting note in the Cesium3DTilesetBaseTraversal.js file

An ancestor will hold the _foveatedFactor and _distanceToCamera for descendants between itself and its highest priority descendant. Siblings of a min children along the way use this ancestor as their priority holder as well.
Priority of all tiles that refer to the _foveatedFactor and _distanceToCamera stored in the common ancestor will be differentiated based on their _depth.

Plus all the foveated parameters on the Cesium3DTileset docs are interesting to understand how it's working under the hood.