Desmos Quadtree Viewer: Draw and color-code quadtree boundaries in Desmos

!Desmos_Quadtree_Viewer.md

• Reveals the mechanism of Bernard (see an explanation in the Desmos Discord for more details)
• May be helpful in improving graph quality/performance
• To install, click on the Raw button to the right of desmos-quadtree-viewer.user.js with the TamperMonkey extension installed
  • This is incompatible with DesModder, so use Quadtree Viewer and DesModder in different browsers/profiles, or temporarily disable DesModder to allow Quadtree Viewer.
• Select an implicit equation to show its quadtree boundaries
• Designed for single-branch implicits in mind (i.e. not plotted via list of graphs). Multiple branches work but are hard to understand
• The graph must be visible for Desmos to plot it. If you just want to see the quadtree, set the graph line width to something small like 0.01 (and remember to select the expression or enable "show all")
• Note that Desmos tries to avoid using the implicit plotter whenever possible, so it can analytically solve equations such as y=sin(x) and x^2=cos(y); those are plotted more accurately without the implicit plotter, so no quad tree is generated

desmos-quadtree-viewer.user.js

// ==UserScript==
// @name        Desmos Quadtree Viewer
// @namespace   github.com/jared-hughes
// @match       *://www.desmos.com/calculator*
// @description Draw and color-code quadtree boundaries in Desmos. Disable when not needed.
// @grant       none
// @version     0.2.1
// @run-at      document-start
// @author      fireflame241 (Jared Hughes)
// ==/UserScript==

const legend = [
  ["2 - Quad is outside of the viewport.", "hsla(0,100%,50%,0.7)"],
  [
    "3 - Quad is smaller than a few pixels wide/tall.",
    "hsla(300,100%,50%,0.8)",
  ],
  [
    "4 - The function is undefined at all 4 vertices of the quad.",
    "hsla(0,0%,30%,0.5)",
  ],
  [
    "6 - The desired implicit curve probably does not pass through this quad, and the function has low curvature in this quad.",
    "hsla(241,100%,50%,0.5)",
  ],
  [
    "A - The maximum of 2<sup>14</sup> quads has been reached, but this quad is a lower depth.",
    "hsla(144,66%,33%,0.3)",
  ],
  [
    "B - The maximum of 2<sup>14</sup> quads has been reached with a quad at this depth.",
    "hsla(144,66%,33%,0.5)",
  ],
];

const legendDisplayString = `
<div id="quadtree-viewer-legend">
  <h3> Quadtree Viewer <a href="https://gist.github.com/jared-hughes/d9a27764c7f8a6e07ba7e2aa89fb5f10">(Usage Instructions)</a></h3>
  <input type="checkbox" id="quadtree-viewer-main-enable" name="quadtree-viewer-main-enable" checked/>
  <label for="quadtree-viewer-main-enable"> Main enable </label>
  <br/>
  <input type="checkbox" id="quadtree-viewer-show-all" name="quadtree-viewer-show-all"/>
  <label for="quadtree-viewer-show-all"> Show all unselected and in screenshots </label>
  <br/>
  <input type="checkbox" id="quadtree-viewer-fill-color" name="quadtree-viewer-fill-color" checked/>
  <label for="quadtree-viewer-fill-color"> Fill with colors </label>
  <br/>
  <input type="checkbox" id="quadtree-viewer-why-no-refine" name="quadtree-viewer-why-no-refine" checked/>
  <label for="quadtree-viewer-why-no-refine"> Why is a quad not refined? </label>
  <ul>
  ${legend
    .map(
      ([description, color]) =>
        `<li style="background-color:${color}">${description}</li>`
    )
    .join("")}
  </ul>
  <span>
  <a href="https://discord.com/channels/655972529030037504/853135943388626965/853136325989105714">More details</a>
  in the Desmos Discord.
  </span>
</div>

<style>
#quadtree-viewer-legend {
  padding: 10px;
  background: white;
  max-width: 100%;
  z-index: 99;
  font-size: 0.9em;
}
#quadtree-viewer-legend h3 {
  margin: 0 0 5px 0;
}
#quadtree-viewer-legend ul {
  padding-left: 0;
  list-style: none;
  margin: 0 0 5px 0;
}
#quadtree-viewer-legend li {
  padding: 5px;
}
.dcg-show-keypad {
  display: none;
}
#quadtree-viewer-main-enable:not(:checked) + label ~ *,
#quadtree-viewer-why-no-refine:not(:checked) + label ~ *,
#quadtree-viewer-fill-color:not(:checked) + label ~ * {
  display: none;
}
</style>
`;
const waitInterval = setInterval(() => {
  let container = document.querySelector(".dcg-template-expressioneach");
  if (window.require && container) {
    clearInterval(waitInterval);
    const $ = window.require("jquery");
    $(legendDisplayString).prependTo(container);
    $(
      "#quadtree-viewer-fill-color,#quadtree-viewer-main-enable,#quadtree-viewer-show-all"
    ).on("change", () => {
      Calc.controller.grapher.redrawAllLayers();
    });
  }
}, 50);

const replacement_shouldDescend = function d(e, r, i) {
  if (e.depth < 5) return !0;
  if (
    (function (e, r) {
      return (
        e.vertices[0].x < r.xmin ||
        e.vertices[0].y > r.ymax ||
        e.vertices[2].x > r.xmax ||
        e.vertices[2].y < r.ymin
      );
    })(e, i)
  ) {
    e.stopReason = "outside-screen";
    return !1;
  }
  if (
    (function (e, r) {
      if (e.vertices[1].x - e.vertices[0].x < 10 * r.xtolerance) return !0;
      if (e.vertices[0].y - e.vertices[3].y < 10 * r.ytolerance) return !0;
      return !1;
    })(e, i)
  ) {
    e.stopReason = "too-small";
    return !1;
  }
  var n = e.vertices[0],
    t = e.vertices[1],
    c = e.vertices[2],
    a = e.vertices[3];
  if (isNaN(n.z) && isNaN(t.z) && isNaN(c.z) && isNaN(a.z)) {
    e.stopReason = "all-undefined";
    return !1;
  }
  if (isNaN(n.z) || isNaN(t.z) || isNaN(c.z) || isNaN(a.z)) return !0;
  var s = p(n, t, c, a, r, i),
    u = N(n, t, r, i),
    o = N(t, c, r, i),
    l = N(c, a, r, i),
    v = N(a, n, r, i);
  const shouldDescend =
    x(n, u, r) ||
    x(t, u, r) ||
    x(t, o, r) ||
    x(c, o, r) ||
    x(c, l, r) ||
    x(a, l, r) ||
    x(a, v, r) ||
    x(n, v, r) ||
    h(n, u, s, r, i) ||
    h(u, t, s, r, i) ||
    h(t, o, s, r, i) ||
    h(o, c, s, r, i) ||
    h(c, l, s, r, i) ||
    h(l, a, s, r, i) ||
    h(a, v, s, r, i) ||
    h(v, n, s, r, i);
  if (!shouldDescend) {
    e.stopReason = "low-curvature-and-no-crossing";
  }
  return shouldDescend;
};

const replacement_gridlayerRedrawToCtx = function (
  t,
  e,
  s,
  graphSketches,
  sketchOrder
) {
  var a, r;
  o.save(t, "graphpaper");
  var n = e.settings.showGrid;
  let quadTreeBranches = [];
  sketchOrder &&
    sketchOrder.forEach((sketchID) => {
      const sketch = graphSketches[sketchID];
      if (
        sketch &&
        (sketch.selected ||
          document.querySelector("#quadtree-viewer-show-all").checked) &&
        document.querySelector("#quadtree-viewer-main-enable").checked
      ) {
        for (const branch of sketch.branches) {
          if (branch.quadTree) {
            quadTreeBranches.push(branch);
          }
        }
      }
    });
  if (quadTreeBranches.length > 0) {
    this.drawQuadTreeGrid(t, e, quadTreeBranches);
  } else if (e.settings.polarMode && n)
    (a = i.polar(e)),
      o.save(t, "grid"),
      this.drawPolarGrid(t, e, a),
      o.restore(t),
      o.save(t, "axis"),
      this.drawAxes(t, e, s),
      (r = this.drawPolarStepNumbers(t, e, a)),
      this.drawLabels(t, e, r),
      o.restore(t);
  else {
    (a = i.cartesian(e)),
      n && (o.save(t, "grid"), this.drawCartesianGrid(t, e, a), o.restore(t));
    var h = !n;
    o.save(t, "axis"),
      this.drawAxes(t, e, s),
      (r = this.drawCartesianStepNumbers(t, e, a, h)),
      this.drawLabels(t, e, r),
      o.restore(t);
  }
  o.restore(t);
};

const new_drawQuadTreeGrid = function (ctx, e, quadTreeBranches) {
  ctx.save();
  for (let branch of quadTreeBranches) {
    const quadsByDepth = [];
    const quadTree = branch.quadTree;
    let quadQueue = [];
    let nextDepthQueue = [quadTree];
    while (nextDepthQueue.length > 0) {
      quadsByDepth.push([]);
      // [quadQueue, nextDepthQueue] = [nextDepthQueue, quadQueue]
      const i = nextDepthQueue;
      nextDepthQueue = quadQueue;
      quadQueue = i;
      let quad;
      while ((quad = quadQueue.pop())) {
        quad.pixelVertices = quad.vertices.map((p) =>
          e.mathToPixels.mapPoint(p)
        );
        quadsByDepth[quadsByDepth.length - 1].push(quad);
        if (quad.children) {
          // recurse breadth-first
          nextDepthQueue.push(...quad.children);
        }
      }
    }

    // draw the fill first
    const maxDepth = quadsByDepth.length - 1;
    if (document.querySelector("#quadtree-viewer-fill-color")?.checked) {
      for (let depth = 0; depth <= maxDepth; depth++) {
        for (let quad of quadsByDepth[depth]) {
          if (!quad.children) {
            const fillColor = {
              "outside-screen": "hsla(0,100%,50%,0.7)",
              "too-small": "hsla(300,100%,50%,0.8)",
              "all-undefined": "hsla(0,0%,30%,0.5)",
              "low-curvature-and-no-crossing": "hsla(241,100%,50%,0.5)",
              "leaf-quad-limit-bernard": "hsla(144,66%,33%,0.5)",
              "leaf-quad-limit": "hsla(144,66%,33%,0.3)",
            }[
              quad.stopReason ??
                (depth < maxDepth
                  ? "leaf-quad-limit"
                  : "leaf-quad-limit-bernard")
            ];
            const [a, b, c, d] = quad.pixelVertices;
            ctx.beginPath();
            ctx.rect(a.x, a.y, c.x - a.x, c.y - a.y);
            ctx.fillStyle = fillColor;
            ctx.fill();
          }
        }
      }
    }
    // now draw the lines (centered)
    for (let depth = 0; depth <= maxDepth; depth++) {
      if (depth <= 4) {
        ctx.lineWidth = e.settings.axisLineWidth;
        ctx.strokeStyle = `rgba(0,0,0,${e.settings.axisOpacity * 1.1})`;
      } else if (depth == 5) {
        ctx.lineWidth = 1;
        ctx.strokeStyle = `rgba(0,0,0,${e.settings.majorAxisOpacity * 1.1})`;
      } else {
        ctx.lineWidth = 1;
        ctx.strokeStyle = `rgba(0,0,0,${e.settings.minorAxisOpacity * 1.1})`;
      }
      ctx.beginPath();
      for (let quad of quadsByDepth[depth]) {
        if (quad.children) {
          const [a, b, c, d] = quad.pixelVertices;
          ctx.moveTo((a.x + b.x) / 2, (a.y + b.y) / 2);
          ctx.lineTo((c.x + d.x) / 2, (c.y + d.y) / 2);
          ctx.moveTo((b.x + c.x) / 2, (b.y + c.y) / 2);
          ctx.lineTo((d.x + a.x) / 2, (d.y + a.y) / 2);
        }
      }
      ctx.stroke();
    }
  }
  ctx.restore();
};

const workerInject = `const defineOverrides = {
  "core/math/implicit-plotter": (definition) =>
    eval(
      "_makeFunctionStatement=" +
        definition
          .toString()
          .replace(
            /function d\\(e,r,i\\)\\{.*?\\}(function h\\(e,i)/,
            \`${replacement_shouldDescend.toString()}$1\`
          )
          .replace(
            "resolved:i.quadTree.resolved",
            "$$&, quadTree:i.quadTree.root"
          )
    ),
  "core/math/plotter": (definition) =>
    eval(
      "_makeFunctionStatement=" +
        definition
          .toString()
          .replace("resolved:i.resolved", "$$&, quadTree:i.quadTree")
    ),
};

const oldDefine = define;

function newDefine(moduleName, dependencies, definition) {
  if (moduleName in defineOverrides) {
    const override = defineOverrides[moduleName](definition, dependencies);
    definition = override.definition ?? override;
    dependencies = override.dependencies ?? dependencies;
  }
  return oldDefine(moduleName, dependencies, definition);
}
newDefine.amd = {
  jQuery: true,
};

define = newDefine;`;

const defineOverrides = {
  // replace the first newline (which should be immediately after the definition of define and require)
  // (inject the above worker code)
  "text!worker_src_underlying": (definition) => () =>
    definition().replace("\n", `${workerInject}\n`),
  "graphing/gridlayer": (definition) =>
    eval(
      "_makeFunctionStatement=" +
        definition
          .toString()
          .replace(
            /t.redrawToCtx=function.*\},t.addTextShadow=/,
            `t.redrawToCtx=${replacement_gridlayerRedrawToCtx.toString()},t.drawQuadTreeGrid=${new_drawQuadTreeGrid.toString()},t.addTextShadow=`
          )
    ),
  "graphing/grapher": (definition) =>
    eval(
      "_makeFunctionStatement=" +
        definition
          .toString()
          .replace(
            "this.gridLayer.redrawToCtx(this.canvasLayer.ctx,this.getProjection(),this.scaleAxis)",
            "this.gridLayer.redrawToCtx(this.canvasLayer.ctx,this.getProjection(),this.scaleAxis,this.graphSketches,this.__sketchOrder)"
          )
          .replace(
            "this.gridLayer.redrawToCtx(a,o)",
            "this.gridLayer.redrawToCtx(a,o,this.scaleAxis,this.graphSketches,this.__sketchOrder)"
          )
    ),
};

let oldDefine = null;

function newDefine(moduleName, dependencies, definition) {
  if (moduleName in defineOverrides) {
    // override should either be `{dependencies, definition}` or just `definition`
    const override = defineOverrides[moduleName](definition, dependencies);
    definition = override.definition ?? override;
    dependencies = override.dependencies ?? dependencies;
  }
  return oldDefine(moduleName, dependencies, definition);
}
// without this, you get Error: touchtracking missing jquery
newDefine.amd = {
  jQuery: true,
};

window.ALMOND_OVERRIDES = new Proxy(
  {},
  {
    get(target, prop, receiver) {
      if (prop === "define") {
        oldDefine = window.define;
        return newDefine;
      } else {
        return Reflect.get(...arguments);
      }
    },
  }
);

To zoom in to see the full padded quad, run

const canvas = document.querySelector("canvas.dcg-graph-inner");
const ctx = canvas.getContext("2d");
ctx._clearRect = ctx.clearRect;
ctx.clearRect = function (x, y, w, h) {
  ctx.save();
  ctx.setTransform(1, 0, 0, 1, 0, 0);
  ctx._clearRect(x, y, w, h);
  ctx.restore();
};
function setGraphScale(s, cx=null, cy=null) {
  cx = cx ?? canvas.width/2;
  cy = cy ?? canvas.height/2;
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  ctx.setTransform(s, 0, 0, s, (1 - s) * cx, (1 - s) * cy);
  Calc.controller.grapher.redrawAllLayers()
}
setGraphScale(0.8)

After running that, you can play around with the scale by e.g. using setGraphScale(0.5, 0, canvas.height/2) to zoom out about the center of the left edge or setGraphScale(2.5, -0.15*canvas.width, 0.7*canvas.height) to zoom in on Bernard.