Repository: NASA-AMMOS/3DTilesRendererJS
Pull request #189 (2021-06-23 19:30:41)

[143] - Prioritize load of closer tiles
Proposal for #143 

Adjust the priority queue callback sig to allow direct comparing of tiles, in order to have tiles compare differently for different render states. Ex: Prefer tiles in view, if tiles are in view, prefer tiles with lower better error values, and if error values are the same, prefer by distance to the camera(s)

Adjust TilesRenderer.calculateError so that it will calculate distance/error even for tiles at 0 geometricError, to allow using those values to prioritize the parsing in addition to downloading tiles.

While thinking about it a little more, I want to make sure that the values needed to make a good default priority sort are documented in some way. (Because I want to make a slightly more MP specific sort in my usage !!). That said, I wasn't sure how to best document that, and wanted to try and capture it in the typedefs.

So there is a second changeset that starts to add some typscript type checking in the js files linked from #190 which I wasn't sure if you were interested enough in to include in this PR, but they could go into a followup pretty quickly.


Patch:
diff --git a/README.md b/README.md
index b35120a..4eb561e 100644
--- a/README.md
+++ b/README.md
@@ -586,7 +586,7 @@ The maximum number of jobs to be processing at once.
 ### .priorityCallback
 
 ```js
-priorityCallback = null : ( item ) => Number
+priorityCallback = null : ( itemA, itemB ) => Number
 ```
 
 Function to derive the job priority of the given item. Higher priority values get processed first.
diff --git a/src/base/TilesRendererBase.d.ts b/src/base/TilesRendererBase.d.ts
index cad9b71..303d1d0 100644
--- a/src/base/TilesRendererBase.d.ts
+++ b/src/base/TilesRendererBase.d.ts
@@ -30,3 +30,42 @@ export class TilesRendererBase {
 	dispose() : void;
 
 }
+
+/** Documented 3d-tile state managed by the TilesRenderer* / traverseFunctions! */
+export interface Tile {
+
+	/**
+	 * Hierarchy Depth from the TileGroup
+	 */
+	__depth : Number;
+	/**
+	 * The screen space error for this tile
+	 */
+	__error : Number;
+	/**
+	 * How far is this tiles bounds from the nearest active Camera.
+	 * Expected to be filled in during calculateError implementations.
+	 */
+	 __distanceFromCamera : Number;
+	/**
+	 * This tile is currently active if:
+	 *  1: Tile content is loaded and ready to be made visible if needed
+	 */
+	__active : Boolean;
+	/**
+	 * This tile is currently visible if:
+	 *  1: Tile content is loaded
+	 *  2: Tile is within a camera frustum
+	 *  3: Tile meets the SSE requirements
+	 */
+	 __visible : Boolean;
+	/**
+	 * Frame number that this tile was last used: active+visible
+	 */
+	 __lastFrameVisited : Number;
+	/**
+	 * TODO: Document this if it is useful enough to be the default property in the LRU sorting.
+	 */
+	 __depthFromRenderedParent : Number;
+
+}
diff --git a/src/base/TilesRendererBase.js b/src/base/TilesRendererBase.js
index 3c54530..3172661 100644
--- a/src/base/TilesRendererBase.js
+++ b/src/base/TilesRendererBase.js
@@ -5,8 +5,43 @@ import { PriorityQueue } from '../utilities/PriorityQueue.js';
 import { determineFrustumSet, toggleTiles, skipTraversal, markUsedSetLeaves, traverseSet } from './traverseFunctions.js';
 import { UNLOADED, LOADING, PARSING, LOADED, FAILED } from './constants.js';
 
-// Function for sorting the evicted LRU items. We should evict the shallowest depth first.
-const priorityCallback = tile => 1 / ( tile.__depthFromRenderedParent + 1 );
+/**
+ * Function for provided to sort all tiles for prioritizing loading/unloading.
+ *
+ * @param {Tile} a
+ * @param {Tile} b
+ * @returns number
+ */
+const priorityCallback = ( a, b ) => {
+
+	if ( a.__lastFrameVisited !== b.__lastFrameVisited ) {
+
+		// the lastFrameVisited tracks the last frame where a tile was used
+		return a.__lastFrameVisited - b.__lastFrameVisited;
+
+	} else if ( a.__error !== b.__error ) {
+
+		// tiles which have greater error next
+		return a.__error - b.__error;
+
+	} 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;
+
+	}
+
+	return 0;
+
+};
+
+/**
+ * Function for sorting the evicted LRU items. We should evict the shallowest depth first.
+ * @param {Tile} tile
+ * @returns number
+ */
+const lruPriorityCallback = ( tile ) => 1 / ( tile.__depthFromRenderedParent + 1 );
 
 export class TilesRendererBase {
 
@@ -42,7 +77,7 @@ export class TilesRendererBase {
 		this.preprocessURL = null;
 
 		const lruCache = new LRUCache();
-		lruCache.unloadPriorityCallback = priorityCallback;
+		lruCache.unloadPriorityCallback = lruPriorityCallback;
 
 		const downloadQueue = new PriorityQueue();
 		downloadQueue.maxJobs = 4;
@@ -185,7 +220,10 @@ export class TilesRendererBase {
 
 		}
 
-		tile.__error = 0.0;
+		// Expected to be set during calculateError()
+		tile.__distanceFromCamera = Infinity;
+		tile.__error = Infinity;
+
 		tile.__inFrustum = false;
 		tile.__isLeaf = false;
 
@@ -420,17 +458,17 @@ export class TilesRendererBase {
 
 		if ( isExternalTileSet ) {
 
-			downloadQueue.add( tile, tile => {
+			downloadQueue.add( tile, tileCb => {
 
 				// if it has been unloaded then the tile has been disposed
-				if ( tile.__loadIndex !== loadIndex ) {
+				if ( tileCb.__loadIndex !== loadIndex ) {
 
 					return Promise.resolve();
 
 				}
 
-				const uri = this.preprocessURL ? this.preprocessURL( tile.content.uri ) : tile.content.uri;
-				return this.fetchTileSet( uri, Object.assign( { signal }, this.fetchOptions ), tile );
+				const uri = this.preprocessURL ? this.preprocessURL( tileCb.content.uri ) : tileCb.content.uri;
+				return this.fetchTileSet( uri, Object.assign( { signal }, this.fetchOptions ), tileCb );
 
 			} )
 				.then( json => {
@@ -453,15 +491,15 @@ export class TilesRendererBase {
 
 		} else {
 
-			downloadQueue.add( tile, tile => {
+			downloadQueue.add( tile, downloadTile => {
 
-				if ( tile.__loadIndex !== loadIndex ) {
+				if ( downloadTile.__loadIndex !== loadIndex ) {
 
 					return Promise.resolve();
 
 				}
 
-				const uri = this.preprocessURL ? this.preprocessURL( tile.content.uri ) : tile.content.uri;
+				const uri = this.preprocessURL ? this.preprocessURL( downloadTile.content.uri ) : downloadTile.content.uri;
 				return fetch( uri, Object.assign( { signal }, this.fetchOptions ) );
 
 			} )
@@ -498,19 +536,19 @@ export class TilesRendererBase {
 					tile.__loadAbort = null;
 					tile.__loadingState = PARSING;
 
-					return parseQueue.add( tile, tile => {
+					return parseQueue.add( tile, parseTile => {
 
 						// if it has been unloaded then the tile has been disposed
-						if ( tile.__loadIndex !== loadIndex ) {
+						if ( parseTile.__loadIndex !== loadIndex ) {
 
 							return Promise.resolve();
 
 						}
 
-						const uri = tile.content.uri;
+						const uri = parseTile.content.uri;
 						const extension = uri.split( /\./g ).pop();
 
-						return this.parseTile( buffer, tile, extension );
+						return this.parseTile( buffer, parseTile, extension );
 
 					} );
 
diff --git a/src/base/traverseFunctions.js b/src/base/traverseFunctions.js
index 9a11b62..a783c4e 100644
--- a/src/base/traverseFunctions.js
+++ b/src/base/traverseFunctions.js
@@ -24,7 +24,8 @@ function resetFrameState( tile, frameCount ) {
 		tile.__isLeaf = false;
 		tile.__visible = false;
 		tile.__active = false;
-		tile.__error = 0;
+		tile.__error = Infinity;
+		tile.__distanceFromCamera = Infinity;
 		tile.__childrenWereVisible = false;
 		tile.__allChildrenLoaded = false;
 
diff --git a/src/three/DebugTilesRenderer.js b/src/three/DebugTilesRenderer.js
index 41d0596..76ed4ae 100644
--- a/src/three/DebugTilesRenderer.js
+++ b/src/three/DebugTilesRenderer.js
@@ -115,7 +115,7 @@ export class DebugTilesRenderer extends TilesRenderer {
 
 			return {
 
-				distanceToCamera: targetTile.cached.distance,
+				distanceToCamera: targetTile.__distanceFromCamera,
 				geometricError: targetTile.geometricError,
 				screenSpaceError: targetTile.__error,
 				depth: targetTile.__depth,
@@ -274,7 +274,7 @@ export class DebugTilesRenderer extends TilesRenderer {
 
 							// We don't update the distance if the geometric error is 0.0 so
 							// it will always be black.
-							const val = Math.min( tile.cached.distance / maxDistance, 1 );
+							const val = Math.min( tile.__distanceFromCamera / maxDistance, 1 );
 							c.material.color.setRGB( val, val, val );
 							break;
 
diff --git a/src/three/TilesRenderer.js b/src/three/TilesRenderer.js
index adee21e..eeff1c9 100644
--- a/src/three/TilesRenderer.js
+++ b/src/three/TilesRenderer.js
@@ -767,12 +767,6 @@ export class TilesRenderer extends TilesRendererBase {
 
 	calculateError( tile ) {
 
-		if ( tile.geometricError === 0.0 ) {
-
-			return 0.0;
-
-		}
-
 		const cached = tile.cached;
 		const inFrustum = cached.inFrustum;
 		const cameras = this.cameras;
@@ -787,6 +781,7 @@ export class TilesRenderer extends TilesRendererBase {
 
 			let maxError = - Infinity;
 			let minDistance = Infinity;
+
 			for ( let i = 0, l = cameras.length; i < l; i ++ ) {
 
 				if ( ! inFrustum[ i ] ) {
@@ -823,7 +818,8 @@ export class TilesRenderer extends TilesRendererBase {
 
 			}
 
-			tile.cached.distance = minDistance;
+			tile.__distanceFromCamera = minDistance;
+			tile.__error = maxError;
 
 			return maxError;
 
diff --git a/src/utilities/PriorityQueue.d.ts b/src/utilities/PriorityQueue.d.ts
index 3e7b828..e226f21 100644
--- a/src/utilities/PriorityQueue.d.ts
+++ b/src/utilities/PriorityQueue.d.ts
@@ -2,7 +2,7 @@ export class PriorityQueue {
 
 	maxJobs : Number;
 	autoUpdate : Boolean;
-	priorityCallback : ( item : any ) => Number;
+	priorityCallback : ( itemA : any , itemB : any ) => Number;
 
 	sort() : void;
 	add( item : any, callback : ( item : any ) => any ) : Promise< any >;
diff --git a/src/utilities/PriorityQueue.js b/src/utilities/PriorityQueue.js
index 6aff904..421f870 100644
--- a/src/utilities/PriorityQueue.js
+++ b/src/utilities/PriorityQueue.js
@@ -23,11 +23,7 @@ class PriorityQueue {
 
 		const priorityCallback = this.priorityCallback;
 		const items = this.items;
-		items.sort( ( a, b ) => {
-
-			return priorityCallback( a ) - priorityCallback( b );
-
-		} );
+		items.sort( priorityCallback );
 
 	}
 


Test patch:
diff --git a/test/PriorityQueue.test.js b/test/PriorityQueue.test.js
index c9ed1ae..dfaf4d4 100644
--- a/test/PriorityQueue.test.js
+++ b/test/PriorityQueue.test.js
@@ -8,7 +8,7 @@ describe( 'PriorityQueue', () => {
 
 		const queue = new PriorityQueue();
 		queue.maxJobs = 6;
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 		queue.add( { priority: 6 }, () => new Promise( () => {} ) );
 		queue.add( { priority: 3 }, () => new Promise( () => {} ) );
 		queue.add( { priority: 4 }, () => new Promise( () => {} ) );
@@ -36,7 +36,7 @@ describe( 'PriorityQueue', () => {
 
 		const queue = new PriorityQueue();
 		queue.maxJobs = 1;
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 		queue.add( { priority: 6 }, cb );
 		queue.add( { priority: 3 }, cb );
 		queue.add( { priority: 4 }, cb );
@@ -65,7 +65,7 @@ describe( 'PriorityQueue', () => {
 		const C = { priority: 2 };
 		const D = { priority: 3 };
 		const queue = new PriorityQueue();
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 		queue.add( A, () => new Promise( () => {} ) );
 		queue.add( B, () => new Promise( () => {} ) );
 		queue.add( C, () => new Promise( () => {} ) );
@@ -95,7 +95,7 @@ describe( 'PriorityQueue', () => {
 		let resolveFunc = null;
 		const queue = new PriorityQueue();
 		queue.maxJobs = 1;
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 
 		queue.add( { priority: 1 }, () => new Promise( resolve => {
 
@@ -134,7 +134,7 @@ describe( 'PriorityQueue', () => {
 
 		const A = { priority: 100 };
 		const queue = new PriorityQueue();
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 
 		queue.add( A, item => new Promise( () => {
 
@@ -149,7 +149,7 @@ describe( 'PriorityQueue', () => {
 	it( 'should return a promise that resolves from the add function.', async () => {
 
 		const queue = new PriorityQueue();
-		queue.priorityCallback = item => item.priority;
+		queue.priorityCallback = ( itemA, itemB ) => itemA.priority - itemB.priority;
 
 		let result = null;
 		queue.add( { priority: 0 }, item => Promise.resolve( 1000 ) ).then( res => result = res );