text: import { Vector3 } from "three";
  import { layout } from "sparse-octree";
  import { KeyDesign } from "./KeyDesign";
  import { WorldOctantIterator } from "./WorldOctantIterator";
  import { WorldOctantWrapper } from "./WorldOctantWrapper";
  import { WorldOctreeCSG } from "./WorldOctreeCSG";
  import { WorldOctreeRaycaster } from "./WorldOctreeRaycaster";
  
  /**
   * A vector.
   *
   * @type {Vector3}
   * @private
   */
  
  const v = new Vector3();
  
  /**
   * Recursively deletes octant children.
   *
   * @param {WorldOctree} world - A world octree.
   * @param {WorldOctant} octant - The current octant.
   * @param {Number} keyX - The X-coordinate of the current octant key.
   * @param {Number} keyY - The Y-coordinate of the current octant key.
   * @param {Number} keyZ - The Z-coordinate of the current octant key.
   * @param {Number} lod - The current LOD value.
   */
  
  function removeChildren(world, octant, keyX, keyY, keyZ, lod) {
  
  	let grid, keyDesign;
  	let children, child;
  	let offset, key, i;
  
  	// The octants from LOD zero have no children.
  	if(lod > 0) {
  
  		// Look at the next lower LOD.
  		--lod;
  
  		grid = world.getGrid(lod);
  		keyDesign = world.getKeyDesign();
  		children = octant.children;
  
  		// Translate the key coordinates to the next lower LOD.
  		keyX <<= 1; keyY <<= 1; keyZ <<= 1;
  
  		for(i = 0; i < 8; ++i) {
  
  			// Check if the child exists.
  			if((children & (1 << i)) !== 0) {
  
  				offset = layout[i];
  
  				v.set(
  					keyX + offset[0],
  					keyY + offset[1],
  					keyZ + offset[2]
  				);
  
  				key = keyDesign.packKey(v);
  
  				// Fetch the child and remove it from the grid.
  				child = grid.get(key);
  				grid.delete(key);
  
  				removeChildren(world, child, v.x, v.y, v.z, lod);
  
  			}
  
  		}
  
  		octant.children = 0;
  
  	}
  
  }
  
  /**
   * Recursively removes empty parent nodes.
   *
   * @param {WorldOctree} world - A world octree.
   * @param {Number} keyX - The X-coordinate of the deleted octant's key.
   * @param {Number} keyY - The Y-coordinate of the deleted octant's key.
   * @param {Number} keyZ - The Z-coordinate of the deleted octant's key.
   * @param {Number} lod - The current LOD value.
   */
  
  function prune(world, keyX, keyY, keyZ, lod) {
  
  	let grid, i, key, parent;
  
  	if(++lod < world.levels) {
  
  		// Look at the next higher LOD grid.
  		grid = world.getGrid(lod);
  
  		// Determine the position of the deleted octant relative to its parent.
  		i = WorldOctree.calculateOffsetIndex(keyX, keyY, keyZ);
  
  		// Translate the key coordinates to the next higher LOD.
  		v.set(keyX >>> 1, keyY >>> 1, keyZ >>> 1);
  
  		// The resulting coordinates identify the parent octant.
  		key = world.getKeyDesign().packKey(v);
  		parent = grid.get(key);
  
  		// Unset the existence flag of the deleted child.
  		parent.children &= ~(1 << i);
  
  		// Check if there are any children left.
  		if(parent.children === 0) {
  
  			// Remove the empty parent and recur.
  			grid.delete(key);
  			prune(world, v.x, v.y, v.z, lod);
  
  		}
  
  	}
  
  }
  
  /**
   * An octree that subdivides space for fast spatial searches.
   *
   * The purpose of this linear octree is to efficiently organise volume data. It
   * allows direct access to different LOD layers, octant neighbours and parents.
   *
   * The world octree is axis-aligned and cannot be rotated.
   */
  
  export class WorldOctree {
  
  	/**
  	 * Constructs a new world octree.
  	 *
  	 * Each octant can be uniquely identified by a 3D coordinate and a LOD value.
  	 * The individual values for X, Y and Z are combined into a 53-bit key.
  	 *
  	 * @param {Number} [cellSize=20] - The size of the smallest octants in LOD zero. Must be an integer i such that 0 < i < 2 ** (33 - levels).
  	 * @param {Number} [levels=8] - The amount of detail levels. Must be an integer i such that 0 < i < 33.
  	 * @param {KeyDesign} [keyDesign] - The bit allotments for the octant coordinates.
  	 */
  
  	constructor(cellSize = 20, levels = 8, keyDesign = new KeyDesign()) {
  
  		levels = Math.max(Math.min(Math.trunc(levels), 32), 1);
  
  		/**
  		 * The LOD zero cell size.
  		 *
  		 * @type {Number}
  		 * @private
  		 */
  
  		this.cellSize = Math.max(Math.min(Math.trunc(cellSize), Math.pow(2, 33 - levels) - 1), 1);
  
  		/**
  		 * The octant key design.
  		 *
  		 * @type {KeyDesign}
  		 * @private
  		 */
  
  		this.keyDesign = keyDesign;
  
  		/**
  		 * The octant LOD grids.
  		 *
  		 * @type {Map[]}
  		 * @private
  		 */
  
  		this.grids = [];
  
  		while(this.grids.length < levels) {
  
  			this.grids.push(new Map());
  
  		}
  
  		/**
  		 * An empty octant wrapper that merely holds the bounds of this world.
  		 *
  		 * @type {WorldOctantWrapper}
  		 * @private
  		 */
  
  		this.bounds = new WorldOctantWrapper();
  
  		this.bounds.min.copy(this.keyDesign.halfRange).multiplyScalar(-this.cellSize);
  		this.bounds.max.copy(this.keyDesign.halfRange).multiplyScalar(this.cellSize);
  
  	}
  
  	/**
  	 * The lower bounds of this world.
  	 *
  	 * @type {Vector3}
  	 */
  
  	get min() {
  
  		return this.bounds.min;
  
  	}
  
  	/**
  	 * The upper bounds of this world.
  	 *
  	 * @type {Vector3}
  	 */
  
  	get max() {
  
  		return this.bounds.max;
  
  	}
  
  	/**
  	 * The amount of detail levels. This value can not be changed.
  	 *
  	 * @type {Number}
  	 */
  
  	get levels() {
  
  		return this.grids.length;
  
  	}
  
  	/**
  	 * The LOD zero octant grid.
  	 *
  	 * @type {Number}
  	 */
  
  	get lodZero() {
  
  		return this.grids[0];
  
  	}
  
  	/**
  	 * Returns the key design.
  	 *
  	 * @return {KeyDesign} The key design.
  	 */
  
  	getKeyDesign() {
  
  		return this.keyDesign;
  
  	}
  
  	/**
  	 * Returns the size of the cells in the specified LOD grid.
  	 *
  	 * @param {Number} [lod=0] - The LOD. Must be an integer; fractions will be truncated.
  	 * @return {Number} The cell size.
  	 */
  
  	getCellSize(lod = 0) {
  
  		return (this.cellSize << lod) >>> 0;
  
  	}
  
  	/**
  	 * Computes the center of this world.
  	 *
  	 * @param {Vector3} [target] - A target vector. If none is provided, a new one will be created.
  	 * @return {Vector3} A vector that describes the center of this world.
  	 */
  
  	getCenter(target) {
  
  		return this.bounds.getCenter(target);
  
  	}
  
  	/**
  	 * Sets the center of this world.
  	 *
  	 * Keeping the center at (0, 0, 0) is recommended because a large offset can
  	 * lead to floating point coordinate imprecisions.
  	 *
  	 * @param {Vector3} center - The new center.
  	 */
  
  	setCenter(center) {
  
  		this.min.copy(this.keyDesign.halfRange).multiplyScalar(-this.cellSize).add(center);
  		this.max.copy(this.keyDesign.halfRange).multiplyScalar(this.cellSize).add(center);
  
  	}
  
  	/**
  	 * Computes the size of this world.
  	 *
  	 * @param {Vector3} [target] - A target vector. If none is provided, a new one will be created.
  	 * @return {Vector3} A vector that describes the size of this world.
  	 */
  
  	getDimensions(target) {
  
  		return this.bounds.getDimensions(target);
  
  	}
  
  	/**
  	 * The world octree depth is constant and corresponds to the amount of detail
  	 * levels.
  	 *
  	 * @return {Number} The octree depth.
  	 */
  
  	getDepth() {
  
  		return this.grids.length - 1;
  
  	}
  
  	/**
  	 * Returns a specific LOD grid.
  	 *
  	 * @param {Number} lod - The LOD of the grid.
  	 * @return {Map} The requested LOD grid or undefined if the given LOD is out of bounds.
  	 */
  
  	getGrid(lod) {
  
  		return (lod >= 0 && lod < this.grids.length) ? this.grids[lod] : undefined;
  
  	}
  
  	/**
  	 * Removes all octants.
  	 */
  
  	clear() {
  
  		let i, l;
  
  		for(i = 0, l = this.grids.length; i < l; ++i) {
  
  			this.grids[i].clear();
  
  		}
  
  	}
  
  	/**
  	 * Checks if the given point lies inside this octree's boundaries.
  	 *
  	 * @param {Vector3} point - A point.
  	 * @return {Boolean} Whether the given point lies inside this octree.
  	 */
  
  	containsPoint(point) {
  
  		return this.bounds.containsPoint(point);
  
  	}
  
  	/**
  	 * Fetches all octants of the specified LOD.
  	 *
  	 * @param {Number} level - The LOD.
  	 * @return {Iterable} A collection that contains the octants of the specified LOD.
  	 */
  
  	findOctantsByLevel(level) {
  
  		return this.octants(level);
  
  	}
  
  	/**
  	 * Calculates key coordinates based on a given position and LOD.
  	 *
  	 * @param {Vector3} position - A position.
  	 * @param {Number} lod - The target LOD.
  	 * @param {Vector3} [target] - A vector to store the result in. If none is provided, a new one will be created.
  	 * @return {Vector3} The key coordinates.
  	 */
  
  	calculateKeyCoordinates(position, lod, target = new Vector3()) {
  
  		const cellSize = this.cellSize << lod;
  
  		// Translate to the origin (zero-based unsigned coordinates).
  		v.subVectors(position, this.min);
  
  		target.set(
  			Math.trunc(v.x / cellSize),
  			Math.trunc(v.y / cellSize),
  			Math.trunc(v.z / cellSize)
  		);
  
  		return target;
  
  	}
  
  	/**
  	 * Retrieves the octant of a specific LOD that contains the given point.
  	 *
  	 * @param {Vector3} point - A point.
  	 * @param {Number} [lod=0] - A LOD value.
  	 * @return {WorldOctant} The octant that contains the point or undefined if it doesn't exist.
  	 */
  
  	getOctantByPoint(point, lod = 0) {
  
  		const keyDesign = this.keyDesign;
  		const grid = this.getGrid(lod);
  
  		let result;
  
  		if(grid !== undefined) {
  
  			if(this.containsPoint(point)) {
  
  				this.calculateKeyCoordinates(point, lod, v);
  				result = grid.get(keyDesign.packKey(v));
  
  			} else {
  
  				console.error("Position out of range", point);
  
  			}
  
  		} else {
  
  			console.error("Invalid LOD", lod);
  
  		}
  
  		return result;
  
  	}
  
  	/**
  	 * Removes a specific octant by a given key.
  	 *
  	 * Children and empty parent nodes will be removed as well.
  	 *
  	 * @param {Number} key - The key of the octant that should be removed.
  	 * @param {Number} [lod=0] - The LOD of the octant.
  	 */
  
  	removeOctant(key, lod = 0) {
  
  		const keyDesign = this.keyDesign;
  		const grid = this.getGrid(lod);
  
  		let keyX, keyY, keyZ;
  
  		if(grid !== undefined) {
  
  			if(grid.has(key)) {
  
  				// Note: v will be modified by removeChildren and prune.
  				keyDesign.unpackKey(key, v);
  				keyX = v.x; keyY = v.y; keyZ = v.z;
  
  				// Recursively delete all children in the lower LOD grids.
  				removeChildren(this, grid.get(key), keyX, keyY, keyZ, lod);
  
  				// Remove the octant.
  				grid.delete(key);
  
  				// Recursively delete empty parent nodes.
  				prune(this, keyX, keyY, keyZ, lod);
  
  			} else {
  
  				console.error("No octant found", key);
  
  			}
  
  		} else {
  
  			console.error("Invalid LOD", lod);
  
  		}
  
  	}
  
  	/**
  	 * Applies the given SDF to the affected octants.
  	 *
  	 * @param {SignedDistanceFunction} sdf - An SDF.
  	 */
  
  	applyCSG(sdf) {
  
  		WorldOctreeCSG.applyCSG(this, sdf);
  
  	}
  
  	/**
  	 * Finds the octants that intersect with the given ray. The intersecting
  	 * octants are sorted by distance, closest first. Empty octants will not be
  	 * included in the result.
  	 *
  	 * @param {Ray} ray - A ray.
  	 * @param {Array} [intersects] - An optional target list to be filled with the intersecting octants.
  	 * @return {WorldOctant[]} The intersecting octants.
  	 */
  
  	raycast(ray, intersects = []) {
  
  		return WorldOctreeRaycaster.intersectWorldOctree(this, ray, intersects);
  
  	}
  
  	/**
  	 * Returns a new world octant iterator.
  	 *
  	 * The octants returned by this iterator are augmented with explicit
  	 * positional information. See {@link WorldOctantWrapper} for more details.
  	 *
  	 * @param {Number} [lod=0] - The LOD grid to consider.
  	 * @return {WorldOctantIterator} An iterator.
  	 */
  
  	octants(lod = 0) {
  
  		return new WorldOctantIterator(this, lod);
  
  	}
  
  	/**
  	 * Calculates an offset index from octant key coordinates.
  	 *
  	 * The index identifies the octant's positional offset relative to its parent:
  	 *
  	 * ```text
  	 *  0: [0, 0, 0]
  	 *  1: [0, 0, 1]
  	 *  2: [0, 1, 0]
  	 *  3: [0, 1, 1]
  	 *  4: [1, 0, 0]
  	 *  5: [1, 0, 1]
  	 *  6: [1, 1, 0]
  	 *  7: [1, 1, 1]
  	 * ```
  	 *
  	 * Note: This binary pattern is defined by the external sparse-octree module.
  	 *
  	 * For more information on fast bitwise modulo with power of two divisors see:
  	 *  https://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy
  	 *
  	 * @param {Number} x - The X-coordinate of the octant key.
  	 * @param {Number} y - The Y-coordinate of the octant key.
  	 * @param {Number} z - The Z-coordinate of the octant key.
  	 * @return {Number} The index of the relative position offset. Range: [0, 7].
  	 */
  
  	static calculateOffsetIndex(x, y, z) {
  
  		// Bitwise modulo: n % (1 << s) = n & ((1 << s) - 1) for positive integers.
  		const offsetX = x & 1;
  		const offsetY = y & 1;
  		const offsetZ = z & 1;
  
  		// Use a reversed packing order for correct indexing (X * 4 + Y * 2 + Z).
  		return (offsetX << 2) + (offsetY << 1) + offsetZ;
  
  	}
  
  }
  