Source code of plot #065 back to plot

import * as G from "./lib/own/geo.js"
import {kdTree} from "./lib/thirdparty/kdTree.js"
import {rand_range, rand} from "./lib/own/random.js";
import {BlueRand} from "./lib/thirdparty/blue-noise.js";

const blueNoiseDim = 96;

export class SLGParams {
  constructor() {
    this.bounds = {
      left: 0,
      top: 0,
      right: 1480,
      bottom: 1050,
    };
    this.step = 1;
    this.startSep = 5;
    this.endRatio = 0.5;
    this.maxLightnessSep = 128;
    this.minLinePoints = 5 / this.step;
    this.densityMethod = SLDensityMethod.BlueNoisePrune;
    this.densityCheckNearestN = 256;
  }
}

export const SLDensityMethod = {
  NearbyContactShy: 0,
  NearbyContactOK: 1,
  BlueNoisePrune: 2,
}

export class SLGen {

  /**
   *
   * @param {SLGParams} params
   */
  constructor(params, field, luma) {
    this.params = params;
    this.field = field;
    this.luma = luma ?? (pt => 0);
    this.kdt = new kdTree([], (a, b) => Math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2), ["x", "y"]);
    this.kdtFiltered = new kdTree([], (a, b) => Math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2), ["x", "y"]);
    this.seedLineQueue = [];
    this.initialSeed = params.seed ?? new G.Vec2(
      rand_range(params.bounds.left, params.bounds.right),
      rand_range(params.bounds.top, params.bounds.bottom));
    if (params.densityMethod == SLDensityMethod.BlueNoisePrune)
      this.blue = new BlueRand(blueNoiseDim);
  }

  genNextLine() {
    while (true) {
      const startPt = getNextStartPt(this);
      if (startPt == null) return null;
      const pts = genLine(this, startPt);
      if (!pts) continue;
      this.seedLineQueue.push(new SeedLine(this, pts));
      return getVisiblePaths(this, pts);
    }
  }
}

class SeedLine {
  constructor(slGen, pts) {
    this.slGen = slGen;
    this.pts = pts;
    this.ix = 0;
    this.startSep = this.slGen.params.startSep;
  }

  next() {
    while (this.ix < 2 * this.pts.length) {
      const ix = this.ix % this.pts.length;
      const isSideA = this.ix < this.pts.length;
      ++this.ix;

      const pt = this.pts[ix];
      const fld = normField(this.slGen, pt, false);
      if (!fld) continue;

      // Off to one side by startSep
      const sidePt = pt.clone();
      if (isSideA) {
        sidePt.x -= fld.y * this.slGen.params.startSep;
        sidePt.y += fld.x * this.slGen.params.startSep;
      }
      else {
        sidePt.x += fld.y * this.slGen.params.startSep;
        sidePt.y -= fld.x * this.slGen.params.startSep;
      }

      if (isOutOfBounds(this.slGen, sidePt)) continue;
      const nearest = this.slGen.kdt.nearest(sidePt, 1);
      if (hasCloserThan(nearest, this.startSep)) continue;

      return sidePt;
    }
    return null;
  }
}

function getVisiblePaths(slGen, pts) {

  const stopDist = slGen.params.startSep * slGen.params.endRatio;
  const blue = slGen.blue ? slGen.blue.rand() : 0;
  const res = [];
  let curr = [];

  for (const pt of pts) {
    const lightHere = slGen.luma(pt);
    if (slGen.params.densityMethod == SLDensityMethod.BlueNoisePrune) {
      if (lightHere > 1) finishCurrent();
      else if (lightHere <= blue) curr.push(pt);
      else finishCurrent();
    }
    else {
      if (lightHere == 0) curr.push(pt);
      else if (lightHere > 1) finishCurrent();
      else {
        const distNeeded = calcNeededDistance(lightHere);
        const nearest = slGen.kdtFiltered.nearest(pt, slGen.params.densityCheckNearestN);
        if (isTooClose(nearest, distNeeded)) finishCurrent();
        else curr.push(pt);
      }
    }
  }
  finishCurrent();
  return res;

  function finishCurrent() {
    if (curr.length >= slGen.params.minLinePoints) {
      res.push(curr);
      for (const pt of curr) slGen.kdtFiltered.insert(pt);
    }
    curr = [];
  }

  function calcNeededDistance(light) {
    return stopDist + light * (slGen.params.maxLightnessSep - stopDist);
  }

  function isTooClose(nearest, distNeeded) {
    for (const itm of nearest) {
      const [pt, dist] = [itm[0], itm[1]];
      if (slGen.params.densityMethod == SLDensityMethod.NearbyContactShy) {
        if (dist < distNeeded) return true;
      }
      else if (slGen.params.densityMethod == SLDensityMethod.NearbyContactOK) {
        const lightThere = slGen.luma(pt);
        const distNeededThere = calcNeededDistance(lightThere);
        if (dist < distNeeded && dist < distNeededThere) return true;
      }
    }
    return false;
  }
}

function genLine(slGen, startPt) {

  const stopDist = slGen.params.startSep * slGen.params.endRatio;
  const selfStopDist = slGen.params.step * 0.9;
  const linePtTree = new kdTree([], (a, b) => Math.sqrt((a.x-b.x)**2 + (a.y-b.y)**2), ["x", "y"]);
  const linePoints = [startPt];

  // Grow forward
  while (true) {
    const pt = grow(linePoints[linePoints.length-1], true);
    if (!pt) break;
    linePtTree.insert(pt);
    linePoints.push(pt);
  }
  // Grow backward
  while (true) {
    const pt = grow(linePoints[0], false);
    if (!pt) break;
    linePtTree.insert(pt);
    linePoints.unshift(pt);
  }

  for (const pt of linePoints) slGen.kdt.insert(pt);
  if (linePoints.length < 2) return null;
  return linePoints;

  function grow(pos, fwd) {
    const travel = rk4(pos, slGen.params.step, pt => normField(slGen, pt, !fwd));
    if (!travel)
      return null;
    const nextPt = pos.clone().add(travel);
    if (isOutOfBounds(slGen, nextPt))
      return null;
    const nearest = slGen.kdt.nearest(nextPt, 2);
    if (hasCloserThan(nearest, stopDist))
      return null;
    const nearestSelf = linePtTree.nearest(nextPt, 2);
    if (hasCloserThan(nearestSelf, selfStopDist))
      return null;
    return nextPt;
  }
}

function hasCloserThan(nearest, dist) {
  for (const itm of nearest) {
    if (itm[1] < dist) return true;
  }
  return false;
}

function normField(slGen, pt, reverse) {
  const v = slGen.field(pt);
  if (!v) return null;
  if (Number.isNaN(v.x) || Number.isNaN(v.y))
    return null;
  const sqLen = v.x * v.x + v.y * v.y;
  if (sqLen == 0) return null;
  const len = Math.sqrt(sqLen);
  if (reverse) v.mul(-1 / len);
  else v.mul(1 / len);
  return v;
}

function isOutOfBounds(slGen, pt) {
  const bounds = slGen.params.bounds;
  if (pt.x < bounds.left || pt.x > bounds.right) return true;
  if (pt.y < bounds.top || pt.y > bounds.bottom) return true;
  return false;
}

function getNextStartPt(slGen) {
  if (slGen.initialSeed) {
    const pt = slGen.initialSeed;
    slGen.initialSeed = null;
    return pt;
  }
  while (slGen.seedLineQueue.length > 0) {
    const pt = slGen.seedLineQueue[0].next();
    if (pt != null)
      return pt;
    slGen.seedLineQueue.shift();
  }
  return scanForSeed(slGen);
}

function scanForSeed(slGen) {
  // TO-DO
  return null;
}

function rk4(pt, step, fun) {
  // TODO: Refactor to eliminate allocations
  let k1 = fun(pt);
  if (!k1)
    return null;
  let k2 = fun(pt.clone().addMul(k1, step * 0.5));
  if (!k2)
    return null;
  let k3 = fun(pt.clone().addMul(k2, step * 0.5));
  if (!k3)
    return null;
  let k4 = fun(pt.clone().addMul(k3, step));
  if (!k4)
    return null;

  return k1.mul(step/6).add(k2.mul(step/3)).add(k3.mul(step/3)).add(k4.mul(step/6));
}