Repository: NASA-AMMOS/3DTilesRendererJS (js)

Issue:
DebugTilesPlugin: Add option for enabling / disabling plugin to toggle performance
The traversal and updates of the fields and objects in debug plugin can cause some hiccups and slowness. It would be nice to be able to disable the function of the plugin so it doesn't impact performance. Things like tile updates can be deferred until their needed in the update function which can be paused for performance.

Pull request description:
DebugTilesPlugin: optimize performance and make it toggleable
This PR optimizes the `DebugTilesPlugin` by reducing its overhead, an makes it toggleable.

fix #647 

## Tree traversal optimizations

This PR optimizes (some) tree traversals by using a stack-based approach, rather than a recursive approach, that reduces overhead of recursion.

`traverseSet()` is modified from a recursive approach to a stack-based approach. ~`toggleTiles()` now uses this version.~

Note: other functions in `traverseFunctions.js` might also benefit from using this approach, but the migration is not as easy as for `toggleTiles()`, as the recursion logic is entangled with the callback logic.

## Disable/Enable the `DebugTilesPlugin` dynamically

Add the `enabled` property on the plugin. When toggled on, the plugin initializes its state from the current tile hierarchy. When toggled off, the existing helpers are removed, and all event listeners do nothing (except for `'dispose-model'`).

Patch:
diff --git a/.eslintrc.json b/.eslintrc.json
index 58390a8..a7a8005 100644
--- a/.eslintrc.json
+++ b/.eslintrc.json
@@ -41,6 +41,7 @@
 		"parser": "@typescript-eslint/parser",
 		"plugins": [ "@typescript-eslint" ],
 		"rules": {
+			"no-undef": "off",
 			"no-unused-vars": [ "error", { "args": "none" } ],
 			"indent": [ "error", "tab" ],
 			"no-dupe-class-members": "off",
diff --git a/example/index.js b/example/index.js
index 86a4a64..470942c 100644
--- a/example/index.js
+++ b/example/index.js
@@ -71,6 +71,7 @@ const params = {
 	resolutionScale: 1.0,
 
 	up: hashUrl ? '+Z' : '+Y',
+	enableDebug: true,
 	displayBoxBounds: false,
 	displaySphereBounds: false,
 	displayRegionBounds: false,
@@ -271,6 +272,7 @@ function init() {
 	tileOptions.open();
 
 	const debug = gui.addFolder( 'Debug Options' );
+	debug.add( params, 'enableDebug' );
 	debug.add( params, 'displayBoxBounds' );
 	debug.add( params, 'displaySphereBounds' );
 	debug.add( params, 'displayRegionBounds' );
@@ -485,6 +487,7 @@ function animate() {
 
 	// update plugin
 	const plugin = tiles.getPluginByName( 'DEBUG_TILES_PLUGIN' );
+	plugin.enabled = params.enableDebug;
 	plugin.displayBoxBounds = params.displayBoxBounds;
 	plugin.displaySphereBounds = params.displaySphereBounds;
 	plugin.displayRegionBounds = params.displayRegionBounds;
diff --git a/src/base/traverseFunctions.js b/src/base/traverseFunctions.js
index 38af26b..8aafb13 100644
--- a/src/base/traverseFunctions.js
+++ b/src/base/traverseFunctions.js
@@ -134,32 +134,57 @@ function canTraverse( tile, renderer ) {
 
 }
 
-// Helper function for recursively traversing a tile set. If `beforeCb` returns `true` then the
+// Helper function for traversing a tile set. If `beforeCb` returns `true` then the
 // traversal will end early.
-export function traverseSet( tile, beforeCb = null, afterCb = null, parent = null, depth = 0 ) {
+export function traverseSet( tile, beforeCb = null, afterCb = null ) {
 
-	if ( beforeCb && beforeCb( tile, parent, depth ) ) {
+	const stack = [];
 
-		if ( afterCb ) {
+	// A stack-based, depth-first traversal, storing
+	// triplets (tile, parent, depth) in the stack array.
 
-			afterCb( tile, parent, depth );
+	stack.push( tile );
+	stack.push( null );
+	stack.push( 0 );
+
+	while ( stack.length > 0 ) {
+
+		const depth = stack.pop();
+		const parent = stack.pop();
+		const tile = stack.pop();
+
+		if ( beforeCb && beforeCb( tile, parent, depth ) ) {
+
+			if ( afterCb ) {
+
+				afterCb( tile, parent, depth );
+
+			}
+
+			return;
 
 		}
 
-		return;
+		const children = tile.children;
 
-	}
+		// Children might be undefined if the tile has not been preprocessed yet
+		if ( children ) {
 
-	const children = tile.children;
-	for ( let i = 0, l = children.length; i < l; i ++ ) {
+			for ( let i = children.length - 1; i >= 0; i -- ) {
 
-		traverseSet( children[ i ], beforeCb, afterCb, tile, depth + 1 );
+				stack.push( children[ i ] );
+				stack.push( tile );
+				stack.push( depth + 1 );
 
-	}
+			}
 
-	if ( afterCb ) {
+		}
 
-		afterCb( tile, parent, depth );
+		if ( afterCb ) {
+
+			afterCb( tile, parent, depth );
+
+		}
 
 	}
 
diff --git a/src/plugins/three/DebugTilesPlugin.d.ts b/src/plugins/three/DebugTilesPlugin.d.ts
index 1f4cf0e..fc00cd8 100644
--- a/src/plugins/three/DebugTilesPlugin.d.ts
+++ b/src/plugins/three/DebugTilesPlugin.d.ts
@@ -14,6 +14,8 @@ export const RANDOM_NODE_COLOR: ColorMode;
 export const CUSTOM_COLOR: ColorMode;
 export class DebugTilesPlugin {
 
+	enabled: boolean;
+
 	displayBoxBounds : boolean;
 	displaySphereBounds : boolean;
 	displayRegionBounds : boolean;
diff --git a/src/plugins/three/DebugTilesPlugin.js b/src/plugins/three/DebugTilesPlugin.js
index c1c69e0..f721338 100644
--- a/src/plugins/three/DebugTilesPlugin.js
+++ b/src/plugins/three/DebugTilesPlugin.js
@@ -1,6 +1,7 @@
 import { Box3Helper, Group, MeshStandardMaterial, PointsMaterial, Sphere, Color } from 'three';
 import { SphereHelper } from './objects/SphereHelper.js';
 import { EllipsoidRegionLineHelper } from './objects/EllipsoidRegionHelper.js';
+import { traverseSet } from '../../base/traverseFunctions.js';
 
 const ORIGINAL_MATERIAL = Symbol( 'ORIGINAL_MATERIAL' );
 const HAS_RANDOM_COLOR = Symbol( 'HAS_RANDOM_COLOR' );
@@ -59,6 +60,8 @@ export class DebugTilesPlugin {
 		this.name = 'DEBUG_TILES_PLUGIN';
 		this.tiles = null;
 
+		this._enabled = true;
+
 		this.extremeDebugDepth = - 1;
 		this.extremeDebugError = - 1;
 		this.boxGroup = null;
@@ -83,6 +86,36 @@ export class DebugTilesPlugin {
 
 	}
 
+	get enabled() {
+
+		return this._enabled;
+
+	}
+
+	set enabled( v ) {
+
+		if ( v !== this._enabled ) {
+
+			this._enabled = v;
+
+			if ( this._enabled ) {
+
+				if ( this.tiles ) {
+
+					this.init( this.tiles );
+
+				}
+
+			} else {
+
+				this.dispose();
+
+			}
+
+		}
+
+	}
+
 	// initialize the groups for displaying helpers, register events, and initialize existing tiles
 	init( tiles ) {
 
@@ -142,6 +175,8 @@ export class DebugTilesPlugin {
 		tiles.addEventListener( 'update-after', this._onUpdateAfterCB );
 		tiles.addEventListener( 'tile-visibility-change', this._onTileVisibilityChangeCB );
 
+		this._initExtremes();
+
 		// initialize an already-loaded tiles
 		tiles.traverse( tile => {
 
@@ -214,17 +249,21 @@ export class DebugTilesPlugin {
 
 	_initExtremes() {
 
-		// initialize the extreme values of the hierarchy
-		let maxDepth = - 1;
-		this.tiles.traverse( tile => {
+		if ( ! ( this.tiles && this.tiles.root ) ) {
 
-			maxDepth = Math.max( maxDepth, tile.__depth );
+			return;
 
-		} );
+		}
 
+		// initialize the extreme values of the hierarchy
+		let maxDepth = - 1;
 		let maxError = - 1;
-		this.tiles.traverse( tile => {
 
+		// Note that we are not using this.tiles.traverse()
+		// as we don't want to pay the cost of preprocessing tiles.
+		traverseSet( this.tiles.root, null, ( tile, _, depth ) => {
+
+			maxDepth = Math.max( maxDepth, depth );
 			maxError = Math.max( maxError, tile.geometricError );
 
 		} );
@@ -652,25 +691,30 @@ export class DebugTilesPlugin {
 	dispose() {
 
 		const tiles = this.tiles;
-		tiles.removeEventListener( 'load-tile-set', this._onLoadTileSetCB );
-		tiles.removeEventListener( 'load-model', this._onLoadModelCB );
-		tiles.removeEventListener( 'dispose-model', this._onDisposeModelCB );
-		tiles.removeEventListener( 'update-after', this._onUpdateAfterCB );
 
-		// reset all materials
-		this.colorMode = NONE;
-		this._onUpdateAfter();
+		if ( tiles ) {
 
-		// dispose of all helper objects
-		tiles.traverse( tile => {
+			tiles.removeEventListener( 'load-tile-set', this._onLoadTileSetCB );
+			tiles.removeEventListener( 'load-model', this._onLoadModelCB );
+			tiles.removeEventListener( 'dispose-model', this._onDisposeModelCB );
+			tiles.removeEventListener( 'update-after', this._onUpdateAfterCB );
 
-			this._onDisposeModel( tile );
+			// reset all materials
+			this.colorMode = NONE;
+			this._onUpdateAfter();
 
-		} );
+			// dispose of all helper objects
+			tiles.traverse( tile => {
+
+				this._onDisposeModel( tile );
+
+			} );
+
+		}
 
-		this.boxGroup.removeFromParent();
-		this.sphereGroup.removeFromParent();
-		this.regionGroup.removeFromParent();
+		this.boxGroup?.removeFromParent();
+		this.sphereGroup?.removeFromParent();
+		this.regionGroup?.removeFromParent();
 
 	}
 


Test patch:
diff --git a/test/traverseFunctions.test.js b/test/traverseFunctions.test.js
new file mode 100644
index 0000000..bc0d82d
--- /dev/null
+++ b/test/traverseFunctions.test.js
@@ -0,0 +1,101 @@
+import { traverseSet } from '../src/base/traverseFunctions.js';
+
+describe( 'traverseSet', () => {
+
+	function makeTile( name, ...children ) {
+
+		return { name, children };
+
+	}
+
+	it( 'should visit all tiles in depth-first order', () => {
+
+		/**
+		 *             root
+		 *          /   |   \
+		 *         a    b    c
+		 *       / | \      /
+		 *      d  e  f    g
+		 *               / | \
+		 *              h  i  j
+		 */
+
+
+		const h = makeTile( 'h' );
+		const i = makeTile( 'i' );
+		const j = makeTile( 'j' );
+
+		const d = makeTile( 'd' );
+		const e = makeTile( 'e' );
+		const f = makeTile( 'f' );
+
+		const b = makeTile( 'b' );
+		const a = makeTile( 'a', d, e, f );
+
+		const g = makeTile( 'g', h, i, j );
+
+		const c = makeTile( 'c', g );
+
+		const root = makeTile( 'root', a, b, c );
+
+
+		const visited = [];
+
+		traverseSet( root, null, ( tile, parent, depth ) => visited.push( `${tile.name}-${depth}-${parent?.name ?? 'none'}` ) );
+
+		expect( visited ).toHaveLength( 11 );
+		expect( visited ).toEqual( [ 'root-0-none', 'a-1-root', 'd-2-a', 'e-2-a', 'f-2-a', 'b-1-root', 'c-1-root', 'g-2-c', 'h-3-g', 'i-3-g', 'j-3-g' ] );
+
+	} );
+
+	it( 'should exit traversal if beforeCb returns true', () => {
+
+		/**
+		 *             root
+		 *          /   |   \
+		 *         a    b    c
+		 *       / | \      /
+		 *      d  e  f    g
+		 *               / | \
+		 *              h  i  j
+		 */
+
+
+		const h = makeTile( 'h' );
+		const i = makeTile( 'i' );
+		const j = makeTile( 'j' );
+
+		const d = makeTile( 'd' );
+		const e = makeTile( 'e' );
+		const f = makeTile( 'f' );
+
+		const b = makeTile( 'b' );
+		const a = makeTile( 'a', d, e, f );
+
+		const g = makeTile( 'g', h, i, j );
+
+		const c = makeTile( 'c', g );
+
+		const root = makeTile( 'root', a, b, c );
+
+
+		const visited = [];
+
+		const beforeCb = ( tile ) => {
+
+			if ( tile.name === 'c' ) {
+
+				return true;
+
+			}
+
+		};
+
+		traverseSet( root, beforeCb, t => visited.push( t.name ) );
+
+		expect( visited ).toHaveLength( 7 );
+		expect( visited ).toEqual( [ 'root', 'a', 'd', 'e', 'f', 'b', 'c' ] );
+
+	} );
+
+} );