Linear Octree

A sparse, linear octree data structure. For a pointer-based implementation see sparse-octree.

Demo · Documentation

Installation

This library requires the peer dependency three.

npm install three linear-octree
Copy

Usage

import { KeyDesign, Octree } from "linear-octree";
import { Box3, Vector3 } from "three";

// Define the bit distribution for the X-, Y- and Z-axis.
const keyDesign = new KeyDesign(4, 4, 4); // Tree depth = 4, 2^12 leaf octants

// Define the octree world bounds.
const bounds = new Box3();
bounds.min.set(-1, -1, -1);
bounds.max.set(1, 1, 1);
// Alternatively, define the bounds based on a cell size.
const cellSize = new Vector3(1, 1, 1);
const bounds = keyDesign.calculateBounds(cellSize, new Box3());

// Create the octree (this one stores strings).
const octree = new Octree<string>(bounds, keyDesign);

// Octree operations expect Uint key coordinates.
const keyCoordinates = new Vector3();
const worldPosition = new Vector3(0.5, 0.5, 0.5);
octree.calculateKeyCoordinates(worldPosition, keyCoordinates);

// Set and retrieve data.
const level = 0; // Octants of every level can store data.
octree.set(keyCoordinates, level, "my data");
octree.get(keyCoordinates, level); // => "my data"
octree.delete(keyCoordinates, level);
octree.get(keyCoordinates, level); // => undefined
Copy

Key Design

// The largest uniform octree can contain 2^51 octants.
const keyDesign = new KeyDesign(17, 17, 17);
// Octrees can be non-uniform with uneven bit distributions.
const keyDesign = new KeyDesign(21, 11, 21);
// Bits can be set to zero to emulate a quad tree.
const keyDesign = new KeyDesign(26, 0, 26);
Copy

Features

• Linear structure
  • Packs positional data into numeric keys
  • Constant time access to octants, parents and neighbors at any depth level
  • Low memory usage (no explicit positional data stored in octants)
• Adheres to a common octant layout
• Supports raycasting
• Supports culling
• Can be extended to manage any data
• Fully customizable 3-dimensional subdivisions

Contributing

Maintain the existing coding style. Add unit tests for any new or changed functionality. Lint and test your code.