Skip to content

The OSINT investigator's workbench. One case, one folder, every tool. Local-first: your media and your investigations never leave your machine.

JavaScript
18.9 KB
Raw Blame
/**
 * Which tiles of the globe are drawn, and which are asked for, frame by frame.
 *
 * The tiles form a tree over the Web Mercator grid, from the four of zoom 1
 * down. A tile is split while one of its picture's pixels would cover more than
 * `sharpness` screen pixels at its nearest point, so the ground keeps about a
 * picture pixel per screen pixel near and far, whatever the tilt. A tile out of
 * the frame, or behind the curve of the Earth, is neither drawn nor split.
 *
 * Nothing ever opens a hole. A tile is drawn only once its mesh is held, and
 * over the quarter of each child in view not held yet it is drawn in that
 * child's place (`quarters`, a bit a child): the ground sharpens where it
 * stands, a quarter at a time, and a coarse tile never covers more than the
 * ground still waiting for a finer one. The asks go coarse first,
 * the frame's own before its margin, and a tile that will be split as soon as
 * it comes has its children asked with it, a few levels down, so a deep zoom
 * does not wait one level after another.
 *
 * What no frame has used for a while is let go past `budget` meshes, the
 * deepest first, so a tile is never let go while a child of it is held.
 *
 * The ground all round the eye is kept too, coarser (`ROUND_SHARPNESS`), so
 * what a quick turn or pan shows is already held a few levels short of sharp;
 * its tiles are asked after all of the frame's own (`round` lists the held
 * ones, whose pictures the caller may ask ahead the same way).
 *
 * Some ground has to be known though it is not in view: the ground under the
 * eye, which says how low it may go, and while an orbit lasts the ground round
 * its pivot that the eye can swing over (`knowGround`). Their tiles are asked
 * and kept like the frame's own, never drawn for it.
 *
 * Pure: the meshes are asked of `request` and handed back to `arrived`, and a
 * test drives it with a camera and no GPU.
 */
import { EARTH, MERC_LAT, RAD, dot, ecef, geodetic, length, sub } from './earth.js';
import { axes, focalOf } from './camera.js';
import { tileLat, tileLon } from '../horizon/mesh/geo.js';

/** The tree's roots: the four tiles of zoom 1. */
export const ROOT_Z = 1;
/** The deepest a tile may be split, whatever the imagery. */
export const MAX_Z = 21;
/** Picture pixels a screen pixel may show before a tile is split. */
export const SHARPNESS = 1.25;
/**
 * …and all round the eye, in view or not: the ground a quick turn or pan
 * brings into view is already held this sharp, a few levels short of the
 * frame's own, never a tile the size of a country.
 */
export const ROUND_SHARPNESS = 6;
/** Asks for the ground all round come after every ask for the frame's own. */
const ROUND_RANK = 1e12;
/** Heights a tile is assumed to span before its own are known: the Dead Sea to Everest. */
const UNKNOWN_LOW = -500;
const UNKNOWN_HIGH = 8900;
/** Below this zoom a tile is too big for the horizon test: it bulges between its points. */
const HORIZON_FROM_Z = 4;
/** Every quarter of a tile, a bit each in the order of its children. */
export const ALL = 15;
/** Levels a tile that will surely be split has its children asked ahead. */
const AHEAD = 3;
/** The finest ground kept known out of view, and the frames an orbit's ground is kept known for. */
const KNOWN_Z = 16;
const KNOWN_FRAMES = 600;

const keyOf = (z, x, y) => `${z}/${x}/${y}`;

/**
 * @param {object} o
 * @param {(asks: { key: string, z: number, x: number, y: number }[]) => void} o.request
 *   meshes to build, most wanted first
 * @param {(tile: object) => void} o.release a mesh let go (its GPU handle)
 * @param {number} [o.budget] meshes held at most
 * @param {number} [o.inFlight] meshes asked and not back yet, at most
 * @param {number} [o.round] the same for the ground all round the eye (`ROUND_SHARPNESS`)
 */
export function createTree({ request, release, budget = 700, inFlight = 48, maxZ = MAX_Z, sharpness = SHARPNESS, round: roundSharpness = ROUND_SHARPNESS }) {
  const nodes = new Map();
  let loading = 0;
  let frameNo = 0;
  let held = 0;

  function node(z, x, y, parent = null) {
    const key = keyOf(z, x, y);
    let n = nodes.get(key);
    if (!n) {
      n = {
        key,
        z,
        x,
        y,
        parent,
        kids: null,
        state: 'idle',
        mesh: null,
        heights: null,
        low: null,
        high: null,
        used: 0,
        lat0: tileLat(y + 1, z),
        lat1: tileLat(y, z),
        lon0: tileLon(x, z),
        lon1: tileLon(x + 1, z),
        bound: null,
      };
      nodes.set(key, n);
    }
    return n;
  }

  const roots = [];
  for (let y = 0; y < 2 ** ROOT_Z; y += 1) for (let x = 0; x < 2 ** ROOT_Z; x += 1) roots.push(node(ROOT_Z, x, y));

  // areas whose ground must be known out of view: `{ lat, lon, radius, until }`
  const kept = [];

  const kidsOf = (n) =>
    (n.kids ??= [
      [0, 0],
      [1, 0],
      [0, 1],
      [1, 1],
    ].map(([dx, dy]) => node(n.z + 1, 2 * n.x + dx, 2 * n.y + dy, n)));

  /** The heights a tile spans: its own once built, else its nearest built ancestor's. */
  function rangeOf(n) {
    for (let at = n; at; at = at.parent) if (at.low != null) return [at.low, at.high];
    return [UNKNOWN_LOW, UNKNOWN_HIGH];
  }

  /**
   * Points that hold the tile between them, at its lowest and highest ground:
   * its corners, the middle of its edges and its centre. Cached per range.
   */
  function boundOf(n, exaggeration) {
    const [low, high] = rangeOf(n);
    const lo = low * exaggeration;
    const hi = high * exaggeration;
    if (n.bound && n.bound.lo === lo && n.bound.hi === hi) return n.bound;
    const lats = [n.lat0, (n.lat0 + n.lat1) / 2, n.lat1];
    const lons = [n.lon0, (n.lon0 + n.lon1) / 2, n.lon1];
    const top = [];
    const points = [];
    for (const la of lats) {
      for (const lo2 of lons) {
        const p = ecef(la, lo2, hi);
        top.push(p);
        points.push(p, ecef(la, lo2, lo));
      }
    }
    const mid = ecef((n.lat0 + n.lat1) / 2, (n.lon0 + n.lon1) / 2, (lo + hi) / 2);
    let radius = 0;
    for (const p of points) radius = Math.max(radius, length(sub(p, mid)));
    // a big tile curves away between its points; its sphere grows by how much
    if (n.z < HORIZON_FROM_Z) radius += EARTH * (1 - Math.cos(((n.lon1 - n.lon0) / 4) * RAD));
    n.bound = { lo, hi, mid, radius, top };
    return n.bound;
  }

  /** The ground of the tile nearest the eye, and how far it is in metres. */
  function nearest(n, eyeAt, eye, exaggeration) {
    const [low, high] = rangeOf(n);
    const lat = Math.min(Math.max(eyeAt.lat, n.lat0), n.lat1);
    // the eye's longitude taken round to the tile's side of the antimeridian
    const mid = (n.lon0 + n.lon1) / 2;
    const lonEye = eyeAt.lon + Math.round((mid - eyeAt.lon) / 360) * 360;
    const lon = Math.min(Math.max(lonEye, n.lon0), n.lon1);
    const h = Math.min(Math.max(eyeAt.h, low * exaggeration), high * exaggeration);
    return { d: length(sub(ecef(lat, lon, h), eye)), lat, lon };
  }

  /** Whether the line from the eye to `p` passes through the sphere of radius `r` before reaching it. */
  function hidden(eye, p, r) {
    const d = sub(p, eye);
    const t = -dot(eye, d) / dot(d, d);
    if (t <= 0 || t >= 1) return false;
    const c = [eye[0] + d[0] * t, eye[1] + d[1] * t, eye[2] + d[2] * t];
    return length(c) < r;
  }

  /**
   * The frame's view: the camera's axes, its lens and the planes it is cut by.
   * `size` in CSS pixels.
   */
  function viewOf(camera, size, exaggeration) {
    const ax = axes(camera);
    const f = focalOf(size.height);
    const halfX = Math.atan(size.width / 2 / f);
    const halfY = Math.atan(size.height / 2 / f);
    const eyeAt = geodetic(camera.eye);
    return { ...ax, eye: camera.eye, eyeAt, f, halfX, halfY, exaggeration, occluder: EARTH - 1000 };
  }

  function inFrustum(n, v) {
    const b = boundOf(n, v.exaggeration);
    const rel = sub(b.mid, v.eye);
    const z = dot(rel, v.forward);
    if (z < -b.radius) return false;
    const x = dot(rel, v.right);
    const y = dot(rel, v.up);
    const side = (along, half) => along * Math.cos(half) - z * Math.sin(half) <= b.radius;
    return side(x, v.halfX) && side(-x, v.halfX) && side(y, v.halfY) && side(-y, v.halfY);
  }

  /**
   * Whether the curve of the Earth hides the whole tile: its corners, the
   * middles of its edges, its centre and its ground nearest the eye, all at
   * its highest, each behind the sphere a kilometre under the sea. The nearest
   * ground counts because a big tile can hold the eye's own ground while all
   * its other points lie past the horizon.
   */
  function behindHorizon(n, v, from = HORIZON_FROM_Z) {
    if (n.z < from) return false;
    const b = boundOf(n, v.exaggeration);
    if (!b.top.every((p) => hidden(v.eye, p, v.occluder))) return false;
    const { lat, lon } = nearest(n, v.eyeAt, v.eye, v.exaggeration);
    return hidden(v.eye, ecef(lat, lon, b.hi), v.occluder);
  }

  const seen = (n, v) => inFrustum(n, v) && !behindHorizon(n, v);

  /** Screen pixels a picture pixel of the tile covers at its nearest point. */
  function pixelsOf(n, v) {
    const { d, lat } = nearest(n, v.eyeAt, v.eye, v.exaggeration);
    const texel = (2 * Math.PI * EARTH * Math.cos(lat * RAD)) / (256 * 2 ** n.z);
    return { pixels: (texel * v.f) / Math.max(d, 1), d };
  }

  /**
   * One frame: the tiles to draw, and the asks it leaves. `limit` caps how deep
   * tiles are split (the imagery's own last level, a terrain-only view…), and
   * `sharp` how sharp they are wanted, the tree's own unless said (a capture).
   */
  function frame(camera, size, { exaggeration = 1, limit = maxZ, sharp = sharpness } = {}) {
    frameNo += 1;
    const v = viewOf(camera, size, exaggeration);
    const ceiling = Math.min(limit, maxZ);
    const drawn = [];
    const wanted = [];
    let waiting = 0;

    const want = (n, d, inside, depth = 0) => {
      if (n.state !== 'idle') return;
      wanted.push({ n, priority: n.z * 1e9 + (inside ? 0 : 5e8) + d + depth });
    };
    const splits = (n) => {
      if (n.z >= ceiling) return false;
      return pixelsOf(n, v).pixels > sharp;
    };
    /** The children of a tile not held yet that will be split as soon as it comes, asked with it. */
    const ahead = (n, depth) => {
      n.used = frameNo;
      if (depth > AHEAD || !splits(n)) return;
      for (const c of kidsOf(n)) {
        if (!seen(c, v)) continue;
        c.used = frameNo;
        if (c.state === 'idle') want(c, pixelsOf(c, v).d, true, depth);
        if (c.state !== 'failed') ahead(c, depth + 1);
      }
    };
    const draw = (n, quarters) => {
      n.quarters = quarters;
      drawn.push(n);
    };
    const visit = (n) => {
      n.used = frameNo;
      if (!splits(n)) {
        draw(n, ALL);
        return;
      }
      // each child in view is drawn once held; until then, and for good where
      // it could not be built, this tile is drawn over its quarter alone
      let quarters = 0;
      kidsOf(n).forEach((c, q) => {
        c.used = frameNo;
        if (!seen(c, v)) return;
        if (c.state === 'ready') {
          visit(c);
          return;
        }
        quarters |= 1 << q;
        if (c.state === 'idle') {
          want(c, pixelsOf(c, v).d, true);
          waiting += 1;
        } else if (c.state === 'loading') waiting += 1;
        if (c.state !== 'failed') ahead(c, 1);
      });
      if (quarters) draw(n, quarters);
    };
    for (const r of roots) {
      r.used = frameNo;
      if (!seen(r, v)) continue;
      if (r.state === 'ready') visit(r);
      else {
        want(r, 0, true);
        waiting += 1;
        if (r.state !== 'failed') ahead(r, 1);
      }
    }
    // roots are asked whether in view or not: they are the ground everything stands on
    for (const r of roots) if (r.state === 'idle') want(r, 0, false);
    // the ground all round, coarser, after everything the frame itself asks
    const round = [];
    const roundSplits = (n) => n.z < ceiling && pixelsOf(n, v).pixels > roundSharpness;
    const aroundEye = (n) => {
      n.used = frameNo;
      if (!roundSplits(n)) {
        round.push(n);
        return;
      }
      for (const c of kidsOf(n)) {
        // a big tile can bulge past its points, but ground merely asked ahead may be missed
        if (behindHorizon(c, v, 2)) continue;
        c.used = frameNo;
        if (c.state === 'ready') aroundEye(c);
        else if (c.state === 'idle') wanted.push({ n: c, priority: ROUND_RANK + c.z * 1e9 + pixelsOf(c, v).d });
      }
    };
    for (const r of roots) if (r.state === 'ready') aroundEye(r);
    // and the ground under the eye, and round an orbit's pivot, down to its level
    const above = Math.max(0, v.eyeAt.h - (groundAt(v.eyeAt.lat, v.eyeAt.lon)?.h ?? 0) * exaggeration);
    const areas = [{ lat: v.eyeAt.lat, lon: v.eyeAt.lon, radius: Math.max(300, above) }];
    for (let i = kept.length - 1; i >= 0; i -= 1) {
      if (kept[i].until < frameNo) kept.splice(i, 1);
      else areas.push(kept[i]);
    }
    for (const area of areas) keepKnown(area, want);
    ask(wanted);
    letGo();
    return { drawn, waiting, view: v, round };
  }

  /**
   * The tiles under an area, at the level whose tiles are about its radius
   * wide (at most three a side), asked with every tile above them: the ground
   * is read down from the roots, through held tiles only.
   */
  function keepKnown({ lat, lon, radius }, want) {
    if (Math.abs(lat) > MERC_LAT) return;
    const width = 2 * Math.PI * EARTH * Math.cos(lat * RAD);
    const z = Math.max(ROOT_Z, Math.min(KNOWN_Z, maxZ, Math.floor(Math.log2(width / Math.max(radius, 1)))));
    const dLat = radius / 111320;
    const dLon = radius / (111320 * Math.max(Math.cos(lat * RAD), 0.01));
    const n = 2 ** z;
    const toX = (lo) => Math.floor((((lo + 180) / 360) % 1 + 1) % 1 * n);
    const toY = (la) => {
      const s = Math.sin(Math.max(-MERC_LAT, Math.min(MERC_LAT, la)) * RAD);
      return Math.min(n - 1, Math.max(0, Math.floor((0.5 - Math.log((1 + s) / (1 - s)) / (4 * Math.PI)) * n)));
    };
    const xs = new Set([toX(lon - dLon), toX(lon), toX(lon + dLon)]);
    for (let y = toY(lat + dLat); y <= toY(lat - dLat); y += 1) {
      for (const x of xs) {
        // down from the root over it, each tile on the way kept and asked
        let at = nodes.get(keyOf(ROOT_Z, x >> (z - ROOT_Z), y >> (z - ROOT_Z)));
        while (at) {
          at.used = frameNo;
          if (at.state === 'idle') want(at, 0, true);
          if (at.z >= z) break;
          const up = z - at.z - 1;
          at = kidsOf(at).find((c) => c.x === x >> up && c.y === y >> up);
        }
      }
    }
  }

  function ask(list) {
    if (!list.length || loading >= inFlight) return;
    list.sort((a, b) => a.priority - b.priority);
    const asks = [];
    for (const { n } of list) {
      if (loading >= inFlight) break;
      if (n.state !== 'idle') continue;
      n.state = 'loading';
      loading += 1;
      asks.push({ key: n.key, z: n.z, x: n.x, y: n.y });
    }
    if (asks.length) request(asks);
  }

  /**
   * Past the budget, down to nine tenths of it: leaves first, since a tile
   * with a held child stays or the child could not be reached, the least
   * recently used and deepest first. A tile let go forgets its children that
   * hold nothing, so the tree itself stays the size of what is held.
   */
  function letGo() {
    if (held <= budget) return;
    const leaves = [];
    for (const n of nodes.values()) {
      if (n.state === 'ready' && n.z > ROOT_Z && n.used < frameNo && !(n.kids ?? []).some((c) => c.state === 'ready')) leaves.push(n);
    }
    leaves.sort((a, b) => a.used - b.used || b.z - a.z);
    const floor = Math.floor(budget * 0.9);
    for (const n of leaves) {
      if (held <= floor) break;
      release(n);
      n.mesh = null;
      n.heights = null;
      n.state = 'idle';
      held -= 1;
      forgetKids(n);
    }
  }

  /** The children of a tile, gone from the tree when nothing of theirs is held or on its way. */
  function forgetKids(n) {
    if (!n.kids || n.kids.some((c) => c.state === 'ready' || c.state === 'loading' || c.kids)) return;
    for (const c of n.kids) nodes.delete(c.key);
    n.kids = null;
  }

  /**
   * The ground's height at a point, from the finest held tile over it, and that
   * tile's zoom; null where no tile is held yet. Heights at their real scale.
   */
  function groundAt(lat, lon) {
    if (Math.abs(lat) > MERC_LAT) return null;
    const X = (lon + 180) / 360 - Math.floor((lon + 180) / 360);
    const s = Math.sin(lat * RAD);
    const Y = 0.5 - Math.log((1 + s) / (1 - s)) / (4 * Math.PI);
    let best = null;
    // down through the children, which are the tree's own tiles in the order `kidsOf` made them:
    // asked every frame for every mark, a key a level would be most of the cost
    let n = nodes.get(keyOf(ROOT_Z, Math.floor(X * 2 ** ROOT_Z), Math.floor(Y * 2 ** ROOT_Z)));
    while (n && n.state === 'ready') {
      best = n;
      if (!n.kids) break;
      const z = n.z + 1;
      n = n.kids[Math.floor(X * 2 ** z) - 2 * n.x + 2 * (Math.floor(Y * 2 ** z) - 2 * n.y)];
    }
    if (!best?.heights) return null;
    const side = Math.round(Math.sqrt(best.heights.length));
    const seg = side - 1;
    const fx = Math.min(Math.max((X * 2 ** best.z - best.x) * seg, 0), seg);
    const fy = Math.min(Math.max((Y * 2 ** best.z - best.y) * seg, 0), seg);
    const i = Math.min(Math.floor(fx), seg - 1);
    const j = Math.min(Math.floor(fy), seg - 1);
    const tx = fx - i;
    const ty = fy - j;
    const h = (a, b) => best.heights[b * side + a];
    const top = h(i, j) * (1 - tx) + h(i + 1, j) * tx;
    const bottom = h(i, j + 1) * (1 - tx) + h(i + 1, j + 1) * tx;
    return { h: top * (1 - ty) + bottom * ty, z: best.z };
  }

  return {
    frame,
    groundAt,
    /** Keep the ground within `radius` metres of a point known for a while, though it is out of view. */
    knowGround(lat, lon, radius) {
      kept.push({ lat, lon, radius, until: frameNo + KNOWN_FRAMES });
    },
    /** A mesh a worker built (null when it could not be), with its heights. */
    arrived(key, built) {
      const n = nodes.get(key);
      loading = Math.max(0, loading - 1);
      if (!n || n.state !== 'loading') {
        if (built?.mesh) release({ mesh: built.mesh });
        return;
      }
      if (!built) {
        n.state = 'failed';
        return;
      }
      held += 1;
      n.state = 'ready';
      n.mesh = built.mesh;
      n.heights = built.heights;
      n.centre = built.centre;
      n.low = built.low;
      n.high = built.high;
      n.bound = null;
      // the children measured against this tile's range know it better now
      for (const c of n.kids ?? []) c.bound = null;
    },
    /** Tiles that failed are asked again (the app was not reached). */
    retry() {
      for (const n of nodes.values()) if (n.state === 'failed') n.state = 'idle';
    },
    /** Everything let go. */
    dispose() {
      for (const n of nodes.values()) if (n.state === 'ready') release(n);
      nodes.clear();
      held = 0;
    },
    get loading() {
      return loading;
    },
    get held() {
      return held;
    },
    /** A tile by key, for a test. */
    node: (key) => nodes.get(key) ?? null,
  };
}