Home Reference Source

src/octree/world/WorldOctree.js

  1. import { Vector3 } from "three";
  2. import { layout } from "sparse-octree";
  3. import { KeyDesign } from "./KeyDesign";
  4. import { WorldOctantIterator } from "./WorldOctantIterator";
  5. import { WorldOctantWrapper } from "./WorldOctantWrapper";
  6. import { WorldOctreeCSG } from "./WorldOctreeCSG";
  7. import { WorldOctreeRaycaster } from "./WorldOctreeRaycaster";
  8.  
  9. /**
  10.  * A vector.
  11.  *
  12.  * @type {Vector3}
  13.  * @private
  14.  */
  15.  
  16. const v = new Vector3();
  17.  
  18. /**
  19.  * Recursively deletes octant children.
  20.  *
  21.  * @param {WorldOctree} world - A world octree.
  22.  * @param {WorldOctant} octant - The current octant.
  23.  * @param {Number} keyX - The X-coordinate of the current octant key.
  24.  * @param {Number} keyY - The Y-coordinate of the current octant key.
  25.  * @param {Number} keyZ - The Z-coordinate of the current octant key.
  26.  * @param {Number} lod - The current LOD value.
  27.  */
  28.  
  29. function removeChildren(world, octant, keyX, keyY, keyZ, lod) {
  30.  
  31. 	let grid, keyDesign;
  32. 	let children, child;
  33. 	let offset, key, i;
  34.  
  35. 	// The octants from LOD zero have no children.
  36. 	if(lod > 0) {
  37.  
  38. 		// Look at the next lower LOD.
  39. 		--lod;
  40.  
  41. 		grid = world.getGrid(lod);
  42. 		keyDesign = world.getKeyDesign();
  43. 		children = octant.children;
  44.  
  45. 		// Translate the key coordinates to the next lower LOD.
  46. 		keyX <<= 1; keyY <<= 1; keyZ <<= 1;
  47.  
  48. 		for(i = 0; i < 8; ++i) {
  49.  
  50. 			// Check if the child exists.
  51. 			if((children & (1 << i)) !== 0) {
  52.  
  53. 				offset = layout[i];
  54.  
  55. 				v.set(
  56. 					keyX + offset[0],
  57. 					keyY + offset[1],
  58. 					keyZ + offset[2]
  59. 				);
  60.  
  61. 				key = keyDesign.packKey(v);
  62.  
  63. 				// Fetch the child and remove it from the grid.
  64. 				child = grid.get(key);
  65. 				grid.delete(key);
  66.  
  67. 				removeChildren(world, child, v.x, v.y, v.z, lod);
  68.  
  69. 			}
  70.  
  71. 		}
  72.  
  73. 		octant.children = 0;
  74.  
  75. 	}
  76.  
  77. }
  78.  
  79. /**
  80.  * Recursively removes empty parent nodes.
  81.  *
  82.  * @param {WorldOctree} world - A world octree.
  83.  * @param {Number} keyX - The X-coordinate of the deleted octant's key.
  84.  * @param {Number} keyY - The Y-coordinate of the deleted octant's key.
  85.  * @param {Number} keyZ - The Z-coordinate of the deleted octant's key.
  86.  * @param {Number} lod - The current LOD value.
  87.  */
  88.  
  89. function prune(world, keyX, keyY, keyZ, lod) {
  90.  
  91. 	let grid, i, key, parent;
  92.  
  93. 	if(++lod < world.levels) {
  94.  
  95. 		// Look at the next higher LOD grid.
  96. 		grid = world.getGrid(lod);
  97.  
  98. 		// Determine the position of the deleted octant relative to its parent.
  99. 		i = WorldOctree.calculateOffsetIndex(keyX, keyY, keyZ);
  100.  
  101. 		// Translate the key coordinates to the next higher LOD.
  102. 		v.set(keyX >>> 1, keyY >>> 1, keyZ >>> 1);
  103.  
  104. 		// The resulting coordinates identify the parent octant.
  105. 		key = world.getKeyDesign().packKey(v);
  106. 		parent = grid.get(key);
  107.  
  108. 		// Unset the existence flag of the deleted child.
  109. 		parent.children &= ~(1 << i);
  110.  
  111. 		// Check if there are any children left.
  112. 		if(parent.children === 0) {
  113.  
  114. 			// Remove the empty parent and recur.
  115. 			grid.delete(key);
  116. 			prune(world, v.x, v.y, v.z, lod);
  117.  
  118. 		}
  119.  
  120. 	}
  121.  
  122. }
  123.  
  124. /**
  125.  * An octree that subdivides space for fast spatial searches.
  126.  *
  127.  * The purpose of this linear octree is to efficiently organise volume data. It
  128.  * allows direct access to different LOD layers, octant neighbours and parents.
  129.  *
  130.  * The world octree is axis-aligned and cannot be rotated.
  131.  */
  132.  
  133. export class WorldOctree {
  134.  
  135. 	/**
  136. 	 * Constructs a new world octree.
  137. 	 *
  138. 	 * Each octant can be uniquely identified by a 3D coordinate and a LOD value.
  139. 	 * The individual values for X, Y and Z are combined into a 53-bit key.
  140. 	 *
  141. 	 * @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).
  142. 	 * @param {Number} [levels=8] - The amount of detail levels. Must be an integer i such that 0 < i < 33.
  143. 	 * @param {KeyDesign} [keyDesign] - The bit allotments for the octant coordinates.
  144. 	 */
  145.  
  146. 	constructor(cellSize = 20, levels = 8, keyDesign = new KeyDesign()) {
  147.  
  148. 		levels = Math.max(Math.min(Math.trunc(levels), 32), 1);
  149.  
  150. 		/**
  151. 		 * The LOD zero cell size.
  152. 		 *
  153. 		 * @type {Number}
  154. 		 * @private
  155. 		 */
  156.  
  157. 		this.cellSize = Math.max(Math.min(Math.trunc(cellSize), Math.pow(2, 33 - levels) - 1), 1);
  158.  
  159. 		/**
  160. 		 * The octant key design.
  161. 		 *
  162. 		 * @type {KeyDesign}
  163. 		 * @private
  164. 		 */
  165.  
  166. 		this.keyDesign = keyDesign;
  167.  
  168. 		/**
  169. 		 * The octant LOD grids.
  170. 		 *
  171. 		 * @type {Map[]}
  172. 		 * @private
  173. 		 */
  174.  
  175. 		this.grids = [];
  176.  
  177. 		while(this.grids.length < levels) {
  178.  
  179. 			this.grids.push(new Map());
  180.  
  181. 		}
  182.  
  183. 		/**
  184. 		 * An empty octant wrapper that merely holds the bounds of this world.
  185. 		 *
  186. 		 * @type {WorldOctantWrapper}
  187. 		 * @private
  188. 		 */
  189.  
  190. 		this.bounds = new WorldOctantWrapper();
  191.  
  192. 		this.bounds.min.copy(this.keyDesign.halfRange).multiplyScalar(-this.cellSize);
  193. 		this.bounds.max.copy(this.keyDesign.halfRange).multiplyScalar(this.cellSize);
  194.  
  195. 	}
  196.  
  197. 	/**
  198. 	 * The lower bounds of this world.
  199. 	 *
  200. 	 * @type {Vector3}
  201. 	 */
  202.  
  203. 	get min() {
  204.  
  205. 		return this.bounds.min;
  206.  
  207. 	}
  208.  
  209. 	/**
  210. 	 * The upper bounds of this world.
  211. 	 *
  212. 	 * @type {Vector3}
  213. 	 */
  214.  
  215. 	get max() {
  216.  
  217. 		return this.bounds.max;
  218.  
  219. 	}
  220.  
  221. 	/**
  222. 	 * The amount of detail levels. This value can not be changed.
  223. 	 *
  224. 	 * @type {Number}
  225. 	 */
  226.  
  227. 	get levels() {
  228.  
  229. 		return this.grids.length;
  230.  
  231. 	}
  232.  
  233. 	/**
  234. 	 * The LOD zero octant grid.
  235. 	 *
  236. 	 * @type {Number}
  237. 	 */
  238.  
  239. 	get lodZero() {
  240.  
  241. 		return this.grids[0];
  242.  
  243. 	}
  244.  
  245. 	/**
  246. 	 * Returns the key design.
  247. 	 *
  248. 	 * @return {KeyDesign} The key design.
  249. 	 */
  250.  
  251. 	getKeyDesign() {
  252.  
  253. 		return this.keyDesign;
  254.  
  255. 	}
  256.  
  257. 	/**
  258. 	 * Returns the size of the cells in the specified LOD grid.
  259. 	 *
  260. 	 * @param {Number} [lod=0] - The LOD. Must be an integer; fractions will be truncated.
  261. 	 * @return {Number} The cell size.
  262. 	 */
  263.  
  264. 	getCellSize(lod = 0) {
  265.  
  266. 		return (this.cellSize << lod) >>> 0;
  267.  
  268. 	}
  269.  
  270. 	/**
  271. 	 * Computes the center of this world.
  272. 	 *
  273. 	 * @param {Vector3} [target] - A target vector. If none is provided, a new one will be created.
  274. 	 * @return {Vector3} A vector that describes the center of this world.
  275. 	 */
  276.  
  277. 	getCenter(target) {
  278.  
  279. 		return this.bounds.getCenter(target);
  280.  
  281. 	}
  282.  
  283. 	/**
  284. 	 * Sets the center of this world.
  285. 	 *
  286. 	 * Keeping the center at (0, 0, 0) is recommended because a large offset can
  287. 	 * lead to floating point coordinate imprecisions.
  288. 	 *
  289. 	 * @param {Vector3} center - The new center.
  290. 	 */
  291.  
  292. 	setCenter(center) {
  293.  
  294. 		this.min.copy(this.keyDesign.halfRange).multiplyScalar(-this.cellSize).add(center);
  295. 		this.max.copy(this.keyDesign.halfRange).multiplyScalar(this.cellSize).add(center);
  296.  
  297. 	}
  298.  
  299. 	/**
  300. 	 * Computes the size of this world.
  301. 	 *
  302. 	 * @param {Vector3} [target] - A target vector. If none is provided, a new one will be created.
  303. 	 * @return {Vector3} A vector that describes the size of this world.
  304. 	 */
  305.  
  306. 	getDimensions(target) {
  307.  
  308. 		return this.bounds.getDimensions(target);
  309.  
  310. 	}
  311.  
  312. 	/**
  313. 	 * The world octree depth is constant and corresponds to the amount of detail
  314. 	 * levels.
  315. 	 *
  316. 	 * @return {Number} The octree depth.
  317. 	 */
  318.  
  319. 	getDepth() {
  320.  
  321. 		return this.grids.length - 1;
  322.  
  323. 	}
  324.  
  325. 	/**
  326. 	 * Returns a specific LOD grid.
  327. 	 *
  328. 	 * @param {Number} lod - The LOD of the grid.
  329. 	 * @return {Map} The requested LOD grid or undefined if the given LOD is out of bounds.
  330. 	 */
  331.  
  332. 	getGrid(lod) {
  333.  
  334. 		return (lod >= 0 && lod < this.grids.length) ? this.grids[lod] : undefined;
  335.  
  336. 	}
  337.  
  338. 	/**
  339. 	 * Removes all octants.
  340. 	 */
  341.  
  342. 	clear() {
  343.  
  344. 		let i, l;
  345.  
  346. 		for(i = 0, l = this.grids.length; i < l; ++i) {
  347.  
  348. 			this.grids[i].clear();
  349.  
  350. 		}
  351.  
  352. 	}
  353.  
  354. 	/**
  355. 	 * Checks if the given point lies inside this octree's boundaries.
  356. 	 *
  357. 	 * @param {Vector3} point - A point.
  358. 	 * @return {Boolean} Whether the given point lies inside this octree.
  359. 	 */
  360.  
  361. 	containsPoint(point) {
  362.  
  363. 		return this.bounds.containsPoint(point);
  364.  
  365. 	}
  366.  
  367. 	/**
  368. 	 * Fetches all octants of the specified LOD.
  369. 	 *
  370. 	 * @param {Number} level - The LOD.
  371. 	 * @return {Iterable} A collection that contains the octants of the specified LOD.
  372. 	 */
  373.  
  374. 	findOctantsByLevel(level) {
  375.  
  376. 		return this.octants(level);
  377.  
  378. 	}
  379.  
  380. 	/**
  381. 	 * Calculates key coordinates based on a given position and LOD.
  382. 	 *
  383. 	 * @param {Vector3} position - A position.
  384. 	 * @param {Number} lod - The target LOD.
  385. 	 * @param {Vector3} [target] - A vector to store the result in. If none is provided, a new one will be created.
  386. 	 * @return {Vector3} The key coordinates.
  387. 	 */
  388.  
  389. 	calculateKeyCoordinates(position, lod, target = new Vector3()) {
  390.  
  391. 		const cellSize = this.cellSize << lod;
  392.  
  393. 		// Translate to the origin (zero-based unsigned coordinates).
  394. 		v.subVectors(position, this.min);
  395.  
  396. 		target.set(
  397. 			Math.trunc(v.x / cellSize),
  398. 			Math.trunc(v.y / cellSize),
  399. 			Math.trunc(v.z / cellSize)
  400. 		);
  401.  
  402. 		return target;
  403.  
  404. 	}
  405.  
  406. 	/**
  407. 	 * Retrieves the octant of a specific LOD that contains the given point.
  408. 	 *
  409. 	 * @param {Vector3} point - A point.
  410. 	 * @param {Number} [lod=0] - A LOD value.
  411. 	 * @return {WorldOctant} The octant that contains the point or undefined if it doesn't exist.
  412. 	 */
  413.  
  414. 	getOctantByPoint(point, lod = 0) {
  415.  
  416. 		const keyDesign = this.keyDesign;
  417. 		const grid = this.getGrid(lod);
  418.  
  419. 		let result;
  420.  
  421. 		if(grid !== undefined) {
  422.  
  423. 			if(this.containsPoint(point)) {
  424.  
  425. 				this.calculateKeyCoordinates(point, lod, v);
  426. 				result = grid.get(keyDesign.packKey(v));
  427.  
  428. 			} else {
  429.  
  430. 				console.error("Position out of range", point);
  431.  
  432. 			}
  433.  
  434. 		} else {
  435.  
  436. 			console.error("Invalid LOD", lod);
  437.  
  438. 		}
  439.  
  440. 		return result;
  441.  
  442. 	}
  443.  
  444. 	/**
  445. 	 * Removes a specific octant by a given key.
  446. 	 *
  447. 	 * Children and empty parent nodes will be removed as well.
  448. 	 *
  449. 	 * @param {Number} key - The key of the octant that should be removed.
  450. 	 * @param {Number} [lod=0] - The LOD of the octant.
  451. 	 */
  452.  
  453. 	removeOctant(key, lod = 0) {
  454.  
  455. 		const keyDesign = this.keyDesign;
  456. 		const grid = this.getGrid(lod);
  457.  
  458. 		let keyX, keyY, keyZ;
  459.  
  460. 		if(grid !== undefined) {
  461.  
  462. 			if(grid.has(key)) {
  463.  
  464. 				// Note: v will be modified by removeChildren and prune.
  465. 				keyDesign.unpackKey(key, v);
  466. 				keyX = v.x; keyY = v.y; keyZ = v.z;
  467.  
  468. 				// Recursively delete all children in the lower LOD grids.
  469. 				removeChildren(this, grid.get(key), keyX, keyY, keyZ, lod);
  470.  
  471. 				// Remove the octant.
  472. 				grid.delete(key);
  473.  
  474. 				// Recursively delete empty parent nodes.
  475. 				prune(this, keyX, keyY, keyZ, lod);
  476.  
  477. 			} else {
  478.  
  479. 				console.error("No octant found", key);
  480.  
  481. 			}
  482.  
  483. 		} else {
  484.  
  485. 			console.error("Invalid LOD", lod);
  486.  
  487. 		}
  488.  
  489. 	}
  490.  
  491. 	/**
  492. 	 * Applies the given SDF to the affected octants.
  493. 	 *
  494. 	 * @param {SignedDistanceFunction} sdf - An SDF.
  495. 	 */
  496.  
  497. 	applyCSG(sdf) {
  498.  
  499. 		WorldOctreeCSG.applyCSG(this, sdf);
  500.  
  501. 	}
  502.  
  503. 	/**
  504. 	 * Finds the octants that intersect with the given ray. The intersecting
  505. 	 * octants are sorted by distance, closest first. Empty octants will not be
  506. 	 * included in the result.
  507. 	 *
  508. 	 * @param {Ray} ray - A ray.
  509. 	 * @param {Array} [intersects] - An optional target list to be filled with the intersecting octants.
  510. 	 * @return {WorldOctant[]} The intersecting octants.
  511. 	 */
  512.  
  513. 	raycast(ray, intersects = []) {
  514.  
  515. 		return WorldOctreeRaycaster.intersectWorldOctree(this, ray, intersects);
  516.  
  517. 	}
  518.  
  519. 	/**
  520. 	 * Returns a new world octant iterator.
  521. 	 *
  522. 	 * The octants returned by this iterator are augmented with explicit
  523. 	 * positional information. See {@link WorldOctantWrapper} for more details.
  524. 	 *
  525. 	 * @param {Number} [lod=0] - The LOD grid to consider.
  526. 	 * @return {WorldOctantIterator} An iterator.
  527. 	 */
  528.  
  529. 	octants(lod = 0) {
  530.  
  531. 		return new WorldOctantIterator(this, lod);
  532.  
  533. 	}
  534.  
  535. 	/**
  536. 	 * Calculates an offset index from octant key coordinates.
  537. 	 *
  538. 	 * The index identifies the octant's positional offset relative to its parent:
  539. 	 *
  540. 	 * ```text
  541. 	 *  0: [0, 0, 0]
  542. 	 *  1: [0, 0, 1]
  543. 	 *  2: [0, 1, 0]
  544. 	 *  3: [0, 1, 1]
  545. 	 *  4: [1, 0, 0]
  546. 	 *  5: [1, 0, 1]
  547. 	 *  6: [1, 1, 0]
  548. 	 *  7: [1, 1, 1]
  549. 	 * ```
  550. 	 *
  551. 	 * Note: This binary pattern is defined by the external sparse-octree module.
  552. 	 *
  553. 	 * For more information on fast bitwise modulo with power of two divisors see:
  554. 	 *  https://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy
  555. 	 *
  556. 	 * @param {Number} x - The X-coordinate of the octant key.
  557. 	 * @param {Number} y - The Y-coordinate of the octant key.
  558. 	 * @param {Number} z - The Z-coordinate of the octant key.
  559. 	 * @return {Number} The index of the relative position offset. Range: [0, 7].
  560. 	 */
  561.  
  562. 	static calculateOffsetIndex(x, y, z) {
  563.  
  564. 		// Bitwise modulo: n % (1 << s) = n & ((1 << s) - 1) for positive integers.
  565. 		const offsetX = x & 1;
  566. 		const offsetY = y & 1;
  567. 		const offsetZ = z & 1;
  568.  
  569. 		// Use a reversed packing order for correct indexing (X * 4 + Y * 2 + Z).
  570. 		return (offsetX << 2) + (offsetY << 1) + offsetZ;
  571.  
  572. 	}
  573.  
  574. }