foodmageddon/src/renderer/terrain/distance.ts

// Signed distance fields over a window of a solid/empty grid: the terrain is drawn from them,
// so its edges are smooth curves instead of the staircase of the material bitmap.

const INF = 1e20;

/** Scratch buffers for the 1D transform, grown on demand. */
let f = new Float64Array(0);
let d = new Float64Array(0);
let z = new Float64Array(0);
let v = new Int32Array(0);

function ensure(n: number): void {
  if (f.length >= n) return;
  f = new Float64Array(n);
  d = new Float64Array(n);
  z = new Float64Array(n + 1);
  v = new Int32Array(n);
}

/** Squared Euclidean distance transform of `grid` along one line (Felzenszwalb & Huttenlocher). */
function edt1d(grid: Float64Array, offset: number, stride: number, n: number): void {
  for (let q = 0; q < n; q++) f[q] = grid[offset + q * stride];
  let k = 0;
  v[0] = 0;
  z[0] = -INF;
  z[1] = INF;
  for (let q = 1; q < n; q++) {
    let s = (f[q] + q * q - (f[v[k]] + v[k] * v[k])) / (2 * q - 2 * v[k]);
    while (s <= z[k]) {
      k--;
      s = (f[q] + q * q - (f[v[k]] + v[k] * v[k])) / (2 * q - 2 * v[k]);
    }
    k++;
    v[k] = q;
    z[k] = s;
    z[k + 1] = INF;
  }
  k = 0;
  for (let q = 0; q < n; q++) {
    while (z[k + 1] < q) k++;
    const dq = q - v[k];
    d[q] = dq * dq + f[v[k]];
  }
  for (let q = 0; q < n; q++) grid[offset + q * stride] = d[q];
}

function edt2d(grid: Float64Array, w: number, h: number): void {
  ensure(Math.max(w, h));
  for (let x = 0; x < w; x++) edt1d(grid, x, w, h);
  for (let y = 0; y < h; y++) edt1d(grid, y * w, 1, w);
}

let inside = new Float64Array(0);
let outside = new Float64Array(0);

/**
 * Signed distance (in pixels, positive inside solid) from each pixel center of a w×h window to
 * the solid/empty boundary, which runs halfway between a solid pixel and an empty one.
 * Values are clamped to ±`clamp`.
 */
export function signedDistance(solid: (i: number) => boolean, w: number, h: number, out: Float32Array, clamp: number): void {
  const n = w * h;
  if (inside.length < n) {
    inside = new Float64Array(n);
    outside = new Float64Array(n);
  }
  for (let i = 0; i < n; i++) {
    const s = solid(i);
    inside[i] = s ? INF : 0;
    outside[i] = s ? 0 : INF;
  }
  edt2d(inside, w, h);
  edt2d(outside, w, h);
  for (let i = 0; i < n; i++) {
    const sd = inside[i] > 0 ? Math.sqrt(inside[i]) - 0.5 : 0.5 - Math.sqrt(outside[i]);
    out[i] = sd > clamp ? clamp : sd < -clamp ? -clamp : sd;
  }
}

/** Bilinear sample of a w×h grid of pixel-center values at window coordinates (u, v) (pixel units). */
export function sampleBilinear(grid: Float32Array, w: number, h: number, u: number, v: number): number {
  const x = u - 0.5;
  const y = v - 0.5;
  let ix = Math.floor(x);
  let iy = Math.floor(y);
  let fx = x - ix;
  let fy = y - iy;
  if (ix < 0) {
    ix = 0;
    fx = 0;
  } else if (ix >= w - 1) {
    ix = w - 2;
    fx = 1;
  }
  if (iy < 0) {
    iy = 0;
    fy = 0;
  } else if (iy >= h - 1) {
    iy = h - 2;
    fy = 1;
  }
  const i = iy * w + ix;
  const a = grid[i];
  const b = grid[i + 1];
  const c = grid[i + w];
  const e = grid[i + w + 1];
  return a + (b - a) * fx + (c - a) * fy + (a - b - c + e) * fx * fy;
}