Made of little things.

// Frustum culling for the bent scene. three's own culling is off (bend.ts): it would test
// the flat, unbent bounds, which the shader moves somewhere else. Instead each object handed
// to the Culler gets a bounding sphere in its own frame, worked out once; every frame its
// centre goes through the same road bend as the shader (RoadFrames.bend), and before each
// render pass the objects outside that camera's view are hidden, then shown again.
import * as THREE from 'three';
import { MOUNTAIN_MIN_RADIUS, type RoadFrames } from './road.js';

/** A bounding sphere round an object's meshes, in its own frame. Meshes flagged `unbounded` are left out. */
export function boundsOf(root: THREE.Object3D): THREE.Sphere {
  root.updateMatrixWorld(true);
  const inv = root.matrixWorld.clone().invert();
  const box = new THREE.Box3(), part = new THREE.Box3(), m = new THREE.Matrix4();
  root.traverse((o) => {
    const mesh = o as THREE.Mesh;
    if (!mesh.isMesh || o.userData.unbounded) return;
    let bb: THREE.Box3 | null;
    if ((mesh as THREE.InstancedMesh).isInstancedMesh) {
      const inst = mesh as THREE.InstancedMesh;
      if (!inst.count) return;
      inst.computeBoundingBox();
      bb = inst.boundingBox;
    } else {
      if (!mesh.geometry.boundingBox) mesh.geometry.computeBoundingBox();
      bb = mesh.geometry.boundingBox;
    }
    if (bb) box.union(part.copy(bb).applyMatrix4(m.multiplyMatrices(inv, o.matrixWorld)));
  });
  return box.isEmpty() ? new THREE.Sphere(new THREE.Vector3(), 0) : box.getBoundingSphere(new THREE.Sphere());
}

interface Item {
  obj: THREE.Object3D;
  centre: THREE.Vector3; // bent, in the world
  radius: number;
}

export class Culler {
  private bounds = new WeakMap<THREE.Object3D, THREE.Sphere>();
  private items: Item[] = [];
  private used = 0;
  private hidden: THREE.Object3D[] = [];
  private frames!: RoadFrames;
  private originS = 0;
  private frustum = new THREE.Frustum();
  private m = new THREE.Matrix4();
  private v = new THREE.Vector3();
  private sphere = new THREE.Sphere();
  private bent = { x: 0, y: 0, z: 0 };

  /** Start this frame's list. */
  begin(frames: RoadFrames, originS: number): void {
    this.restore();
    this.frames = frames;
    this.originS = originS;
    this.used = 0;
  }

  /**
   * Cull `obj` this frame (call after it is placed). `local` is its bounding sphere in its own
   * frame; by default one is worked out from its meshes the first time it is seen.
   */
  add(obj: THREE.Object3D, local?: THREE.Sphere): void {
    if (!obj.visible) return;
    let s = local ?? this.bounds.get(obj);
    if (!s) this.bounds.set(obj, (s = boundsOf(obj)));
    if (s.radius <= 0) return;
    // Into the flat render space, through each parent's transform (cheaper than matrixWorld,
    // which isn't up to date until the renderer runs).
    const v = this.v.copy(s.center);
    let scale = 1;
    for (let o: THREE.Object3D | null = obj; o && o.parent; o = o.parent) {
      v.multiply(o.scale).applyQuaternion(o.quaternion).add(o.position);
      scale *= Math.max(Math.abs(o.scale.x), Math.abs(o.scale.y), Math.abs(o.scale.z));
    }
    const r = s.radius * scale;
    // Flat render space has z = -(s - originS); bend it onto the road. The bend can move the
    // ends of a long object off the line of its centre: allow for the tightest curve and
    // the steepest change of grade.
    const b = this.frames.bend(v.x, v.y, this.originS - v.z, this.bent);
    let item = this.items[this.used];
    if (!item) this.items.push((item = { obj, centre: new THREE.Vector3(), radius: 0 }));
    item.obj = obj;
    item.centre.set(b.x, b.y, b.z);
    item.radius = r + (r * r) / (2 * MOUNTAIN_MIN_RADIUS) + r * 0.1 + 1;
    this.used++;
  }

  /** Hide what `camera` can't see, until the next cull or restore. */
  cull(camera: THREE.Camera): void {
    this.restore();
    camera.updateMatrixWorld();
    this.frustum.setFromProjectionMatrix(this.m.multiplyMatrices(camera.projectionMatrix, camera.matrixWorldInverse));
    for (let i = 0; i < this.used; i++) {
      const it = this.items[i];
      this.sphere.center.copy(it.centre);
      this.sphere.radius = it.radius;
      if (it.obj.visible && !this.frustum.intersectsSphere(this.sphere)) {
        it.obj.visible = false;
        this.hidden.push(it.obj);
      }
    }
  }

  /** Show everything cull() hid. */
  restore(): void {
    for (const o of this.hidden) o.visible = true;
    this.hidden.length = 0;
  }
}