Overview

This interactive 2D visualization demonstrates how the Quadtree from @hello-terrain/three works. Unlike the 3D scene, this simplified view lets you directly inspect the data structure.

Interaction

• Click on any cell to subdivide it into four children
• Hover over a cell to see its neighbors highlighted
• Use the Max Level dropdown to limit subdivision depth
• Click Reset to start over

Understanding Neighbors

The quadtree provides O(1) neighbor lookup using a spatial index. Each node can find its neighbors in all four cardinal directions:

Key features of neighbor finding:

• Cross-level neighbors: Finds neighbors even when they're at different levels of detail (coarser or finer)
• Boundary detection: Returns empty sentinel (0xFFFF) for edges of the quadtree
• Finer neighbors: When looking at a large tile whose neighbor has been subdivided, returns all the smaller tiles along the shared edge

Node Indexing

Each node displays its buffer index (the number in the center). The root node is always index 0. When a node subdivides, its four children are assigned consecutive indices in the order they're created:

This layout means siblings have internal neighbor relationships:

• Child 0's right neighbor is child 1
• Child 0's bottom neighbor is child 2
• Child 3's left neighbor is child 2
• Child 3's top neighbor is child 1

External neighbors (outside the parent's bounds) are only set when those nodes exist at the same or greater level of detail.

Code Example

import { Quadtree, Direction } from "@hello-terrain/three";

const quadtree = new Quadtree({
  maxLevel: 6,
  rootSize: 1,
  minNodeSize: 1 / 64,
  origin: { x: 0, y: 0, z: 0 },
  maxNodes: 4096,
});

// Update with a position to trigger subdivision
quadtree.update({ x: 0.1, y: 0, z: 0.2 });

// Find neighbors for a specific node (works across different levels)
const leftNeighbor = quadtree.findNeighbor(5, Direction.LEFT);
const rightNeighbor = quadtree.findNeighbor(5, Direction.RIGHT);

// Or get all neighbors at once
const allNeighbors = quadtree.findAllNeighbors(5);
console.log("Left:", allNeighbors.left);   // number | number[] | 0xFFFF
console.log("Right:", allNeighbors.right);
console.log("Top:", allNeighbors.top);
console.log("Bottom:", allNeighbors.bottom);

// Neighbors can be:
// - A single index (same or coarser level neighbor)
// - An array of indices (finer level neighbors along the edge)
// - 0xFFFF (EMPTY_SENTINEL_VALUE) if at boundary

Related

• Quadtree API Reference - Full documentation with 3D visualization
• TerrainGeometry - The geometry tiles used with quadtree LOD