Quadtree

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

const quadtree = new Quadtree(config, subdivisionStrategy?, nodeView?);

const closestLeafIndex = quadtree.update(position);

const leaves = quadtree.getLeafNodes();
// [{ level: 0, x: 0, y: 0 }, { level: 2, x: 1, y: 3 }, ...]

const { indices, count } = quadtree.getActiveLeafNodeIndices();
// indices: Uint16Array, count: number of valid entries

import { screenSpaceSubdivision } from "@hello-terrain/three";

quadtree.subdivisionStrategy = screenSpaceSubdivision({
  targetTrianglePixels: 6,
  getScreenSpaceInfo: () => screenInfo,
});

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

const leftNeighbor = quadtree.findNeighbor(nodeIndex, Direction.LEFT);
const rightNeighbor = quadtree.findNeighbor(nodeIndex, Direction.RIGHT);

const neighbors = quadtree.findAllNeighbors(nodeIndex);
console.log(neighbors.left);   // number | number[]
console.log(neighbors.right);  // number | number[]
console.log(neighbors.top);    // number | number[]
console.log(neighbors.bottom); // number | number[]

const spatialIndex = quadtree.getSpatialIndex();
const { keys, values, size } = spatialIndex.getBuffers();
// keys: Uint32Array, values: Uint16Array

import { distanceBasedSubdivision } from "@hello-terrain/three";

// Subdivide when distance < nodeSize * factor
const strategy = distanceBasedSubdivision(2); // factor = 2

import { screenSpaceSubdivision, computeScreenSpaceInfo } from "@hello-terrain/three";

const strategy = screenSpaceSubdivision({
  targetTrianglePixels: 6,
  tileSegments: 13,
  getScreenSpaceInfo: () => {
    const fovRadians = camera.fov * Math.PI / 180;
    return computeScreenSpaceInfo(fovRadians, renderer.domElement.height);
  },
});

import type { SubdivisionStrategy } from "@hello-terrain/three";

const customStrategy: SubdivisionStrategy = (
  qt,         // quadtree instance
  distance,   // distance from position to node center
  level,      // current quadtree level (0 = root)
  nodeSize,   // world-space size of the node
  minNodeSize // minimum allowed node size
  // ... additional parameters: rootSize, nodeX, nodeY, minX, minY, worldX, worldY
) => {  
  // Return true to subdivide, false to keep as leaf
  return distance < nodeSize * 1.5 && nodeSize > minNodeSize;
};

import * as THREE from "three";
import type { SubdivisionStrategy } from "@hello-terrain/three";

// Factory function that creates a strategy with frustum access
function createFrustumCullingStrategy(
  frustum: THREE.Frustum,
  factor = 2
): SubdivisionStrategy {
  const tempBox = new THREE.Box3();
  const tempMin = new THREE.Vector3();
  const tempMax = new THREE.Vector3();

  return (
    qt,
    distance,
    level,
    nodeSize,
    minNodeSize,
    rootSize,
    nodeX,
    nodeY,
    minX,
    minY,  // This is world Z coordinate
    worldX,
    worldY // This is world Z center
  ) => {
    const config = qt.getConfig();
    
    // Build bounding box for this node
    // minX/minY are world X/Z minimums, nodeSize is the edge length
    const altitude = config.rootSize; // Approximate vertical extent
    tempMin.set(minX, config.origin.y - altitude, minY);
    tempMax.set(minX + nodeSize, config.origin.y + altitude, minY + nodeSize);
    tempBox.set(tempMin, tempMax);

    // Skip nodes outside frustum
    if (!frustum.intersectsBox(tempBox)) {
      return false;
    }

    // Normal distance-based subdivision for nodes in frustum
    if (nodeSize <= minNodeSize) {
      return false;
    }
    return distance < nodeSize * factor;
  };
}

// Usage in render loop:
const frustum = new THREE.Frustum();
const projScreenMatrix = new THREE.Matrix4();

function updateQuadtree() {
  projScreenMatrix.multiplyMatrices(
    camera.projectionMatrix,
    camera.matrixWorldInverse
  );
  frustum.setFromProjectionMatrix(projScreenMatrix);
  
  // Update strategy with current frustum
  quadtree.subdivisionStrategy = createFrustumCullingStrategy(frustum, 2);
  quadtree.update(camera.position);
}

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

Direction.LEFT   // 0 - Adjacent cell to the left (−X)
Direction.RIGHT  // 1 - Adjacent cell to the right (+X)
Direction.TOP    // 2 - Adjacent cell above (−Z)
Direction.BOTTOM // 3 - Adjacent cell below (+Z)

const neighbors = quadtree.findAllNeighbors(leafIndex);

if (Array.isArray(neighbors.left)) {
  // Multiple finer neighbors - need to stitch to all of them
  console.log(`${neighbors.left.length} smaller tiles on left edge`);
} else if (neighbors.left === 0xFFFF) {
  // At boundary - no neighbor exists
} else {
  // Single neighbor (same or coarser level)
  const neighborLevel = nodeView.getLevel(neighbors.left);
}

const spatialIndex = quadtree.getSpatialIndex();

// Get raw buffers for GPU upload
const { keys, values, size } = spatialIndex.getBuffers();
// keys: Uint32Array - packed (level, x, y) coordinates
// values: Uint16Array - node indices
// size: number - hash table size

// Manual lookup (usually not needed)
const nodeIndex = spatialIndex.lookup(level, x, y);

import { useMemo } from "react";
import { useFrame, useThree } from "@react-three/fiber";
import { Quadtree } from "@hello-terrain/three";

function TerrainLOD() {
  const { camera } = useThree();
  
  const quadtree = useMemo(() => new Quadtree({
    maxLevel: 8,
    rootSize: 1000,
    minNodeSize: 10,
    origin: { x: 0, y: 0, z: 0 },
    maxNodes: 4096,
  }), []);
  
  useFrame(() => {
    // Update quadtree with camera position
    quadtree.update(camera.position);
    
    // Get leaf nodes for rendering
    const leaves = quadtree.getLeafNodes();
    // Use leaves to position terrain tile instances...
  });
  
  return null;
}

import * as THREE from "three";
import { Quadtree, screenSpaceSubdivision, computeScreenSpaceInfo } from "@hello-terrain/three";

// Create quadtree - origin can be a plain object or THREE.Vector3
const quadtree = new Quadtree({
  maxLevel: 8,
  rootSize: 1000,
  minNodeSize: 10,
  origin: { x: 0, y: 0, z: 0 },
  maxNodes: 4096,
});

// Use screen-space subdivision for consistent visual quality
quadtree.subdivisionStrategy = screenSpaceSubdivision({
  targetTrianglePixels: 6,
  getScreenSpaceInfo: () => {
    const fovRadians = camera.fov * Math.PI / 180;
    return computeScreenSpaceInfo(fovRadians, renderer.domElement.height);
  },
});

// In render loop
function animate() {
  // Update quadtree with camera position
  quadtree.update(camera.position);
  
  // Get active leaves for instanced rendering
  const { indices, count } = quadtree.getActiveLeafNodeIndices();
  
  // Use indices to update instance matrices...
  requestAnimationFrame(animate);
}

const nodeView = quadtree.getNodeView();
const buffers = nodeView.getBuffers();