Fast line hiding with a WebGL shader for pen plots

November 11, 2022 Creative Coding

You don’t need to worry much about Javascript’s performance if you can offload your heaviest computations onto the GPU using WebGL. Here’s how I sped up my canvas-based line hiding algorithm from 300 seconds to 30 msec to render beautiful 3D images with the pen plotter.

The appeal of line hiding

A lot of my pen plotter work plays with things hiding other things. Sometimes it’s two-dimensional shapes blocking other shapes; sometimes it’s a pattern filling only the inside of a closed shape; sometimes it’s three-dimensional objects blocking parts of each other from view.

The root of this fascination with line hiding is the fact that in a pen drawing, once you’ve drawn a line your cannot make it disappear by painting over it. You must know in advance what’s visible and what’s not. When you paint on a canvas, you can work your way up from the background and paint over things. In a pen plot, you must figure out exactly what parts of the background will be visible and what must not get drawn.

Black-and-white pen plotter drawing of thin glass blades on soil, with a glimpse of the sky in the background.
Generative grass: the blades are simple outlines that block each other and hide the strokes of the background. © Gábor Ugray

Existing tools

I haven’t come across many tools that address this with vector graphics. One fascinating example is “ln,”[1] Michael Fogleman’s sweet and sharp tool written in Go that generates the visible lines of 3D geometric shapes. I have heard that Blender[2] can export plottable SVG files from 3D scenes. In my own Javascript work I started using the Paper.js[3] library precisely because it comes with a powerful bag of polygon intersection methods.

None of these are an optimal match for my own creative process. “ln” won’t work simply because it’s not in Javascript, which is where I have built out my environment. I work in a very code-centric way, and in that context Blender is just an extra tool that I would need to learn and integrate. Paper.js doesn’t help with 3D shapes, and its performance hits a wall if I have complicated 2D shapes, or simply too many shapes.

[Update: tca@genart.social points out that Trammell Hudson's Plotter Vision[11] does something similar for STL meshes. It uses a geometric approach, and the crisp and clear source code is really worth studying.]

Plot of six tumbling cubic shapes, seen from an isometric perspective in front of a dithered background.
The tumbling cubic shapes are in front of each other, blocking from view others as well as the background. The outlines and hatch fills have a wobbly effect defined in the paper’s 2D space to create a hand-drawn impression. © Gábor Ugray

Sampling canvas pixels

To avoid the complexity of calculating polygon intersections, I opted for a brutally simple approach. I keep a regular canvas around where I draw shapes with a solid fill, and use these shapes as either a positive or a negative mask to decide what parts of my lines are visible. For the composition above, the canvas with the masks looks something like this:

Colored mask used in the plot of tumbling cubic shapes.

A few details about this method:

The beauty of this approach is that it works with 3D shapes too. I can use Three.js[4] to build a real three-dimensional scene. I render the composition onto the canvas, and project vertices into the same 2D space. I can then walk an edge between two projected vertices and test its points. The 3D rendering engine has taken care of what’s visible and what’s hidden without me needing to calculate intersections or trace rays.

Although Three.js renders with WebGL, this is not yet the part of my method where I use WebGL to speed things up. Keep reading!

Hack or not?

But first, a brief aside...

There’s a point to be made that this is really just a hack and not a real solution. It doesn’t calculate precise vector coordinates through a closed formula or at least a numerical method. It just steals information from a rasterized image.

To which I say: if it’s good enough for zancan[5], it’s good enough for me! Here’s the Twitter conversation[6] from April 2021 where he shared his approach. I screenshotted it for posterity :)

Screenshot of tweet by Zancan Screenshot of tweet by Zancan

Optimizing on the CPU

Once I had a naive implementation of the pixel testing approach working reliably, I wanted to put it through its paces on something complicated. I remembered seeing Reinder’s recreation[7] of Escher’s original Cubic Space Division[8] on Turtletoy and decided to try and plot it myself.

Cubic Space Division by Escher
Escher’s 1953 Cubic Space Division. Fair use. Source: WikiArt.
Cubic Space Division by Escher
The rendered 3D image (right), and all the edges in it without line hiding.

Round 1: Naive and dumb approach

Below is the first, rather thoughtless version of my line hiding function. Running this on the scene from the image above took about 5 minutes, or 300 seconds.

function get3JSMaskedLine(pt1, pt2, pixels, clr1, clr2) {

  // Build points: short segments of the requested length
  const lineVect = pt2.subtract(pt1);
  const lineLength = lineVect.length;
  const nSegs = Math.max(2, Math.round(lineLength / segLen));
  const segVect = lineVect.divide(nSegs);
  const pts = [];
  for (let i = 0; i <= nSegs; ++i) {
    pts.push(pt1.add(segVect.multiply(i)));
  }
  let orto = pt2.subtract(pt1).rotate(90);
  orto.length = 1;

  let visibleLines = [];
  let firstVisible = null
  for (let i = 0; i < pts.length; ++i) {

    let pt = pts[i];
    let clrHere = getPixel(pixels, pt.x, pt.y);
    let isVisible = clrEq(clrHere, clr1);
    if (!isVisible) isVisible = clrEq(clrHere, clr2);
    if (!isVisible) {
      clrHere = getPixel(pixels, pt.x + orto.x, pt.y + orto.y);
      isVisible = clrEq(clrHere, clr1);
      if (!isVisible) isVisible = clrEq(clrHere, clr2);
    }
    if (!isVisible) {
      clrHere = getPixel(pixels, pt.x - orto.x, pt.y - orto.y);
      isVisible = clrEq(clrHere, clr1);
      if (!isVisible) isVisible = clrEq(clrHere, clr2);
    }

    if (isVisible && firstVisible == null) firstVisible = pts[i];
    else if (!isVisible && firstVisible != null) {
      if (firstVisible != pts[i - 1]) visibleLines.push([firstVisible, pts[i - 1]]);
      firstVisible = null;
    }
  }
  if (firstVisible != null && firstVisible != pts[pts.length - 1]) visibleLines.push([firstVisible, pts[pts.length - 1]]);
  return visibleLines;
}

A few remarks:

Round 2: Naive and less dumb

In the previous round, the code calling the function above tested a lot of unnecessary points. A large part of the 3D scene is not visible on the canvas: entire edges are off to the side, or even behind the camera. Because these tend to be close to the camera, they are also very long lines, which meant a lot of points to be tested.

After adding a simple filter that threw out lines that are trivially not visible, what remained were about 155 million points to be tested on 37 thousand lines. That took 50 seconds with the code above.

Round 3: Fewer allocations

Taking a critical look at the function above, my instinct was to eliminate allocations. Looking at the process explorer confirmed that Firefox was allocating and releasing a lot of RAM, so it was reasonable to assume that GC pressure was a major drag on performance here.

One needless allocation is the array of points to be tested. The other happens here, where the tested pixel’s color is returned as an object:

let clrHere = getPixel(pixels, pt.x, pt.y);

An improved version that avoids allocating the array and the points in it looks like this:

function get3JSMaskedLineNoAlloc(pt1, pt2, pixels, clr1, clr2) {

  const deltaX = pt2.x - pt1.x;
  const deltaY = pt2.y - pt1.y;
  const lineLength = Math.sqrt(deltaX ** 2 + deltaY ** 2);
  const nSegs = Math.max(2, Math.round(lineLength / segLen));
  testedPoints += nSegs + 1;

  let orto = pt2.subtract(pt1).rotate(90);
  orto.length = 1;

  let visibleLines = [];
  let firstVisible = null;
  let pt = new Point();
  let prevPt = new Point();

  for (let i = 0; i <= nSegs; ++i) {

    pt.x = pt1.x + i / nSegs * deltaX;
    pt.y = pt1.y + i / nSegs * deltaY;

    let clrHere = getPixel(pixels, pt.x, pt.y);
    let isVisible = clrEq(clrHere, clr1);
    if (!isVisible) isVisible = clrEq(clrHere, clr2);
    if (!isVisible) {
      clrHere = getPixel(pixels, pt.x + orto.x, pt.y + orto.y);
      isVisible = clrEq(clrHere, clr1);
      if (!isVisible) isVisible = clrEq(clrHere, clr2);
    }
    if (!isVisible) {
      clrHere = getPixel(pixels, pt.x - orto.x, pt.y - orto.y);
      isVisible = clrEq(clrHere, clr1);
      if (!isVisible) isVisible = clrEq(clrHere, clr2);
    }

    if (isVisible && firstVisible == null) {
      firstVisible = pt.clone();
    }
    else if (!isVisible && firstVisible != null) {
      if (!firstVisible.equals(prevPt)) visibleLines.push([firstVisible, prevPt.clone()]);
      firstVisible = null;
    }

    prevPt.x = pt.x;
    prevPt.y = pt.y;
  }
  if (firstVisible != null && !firstVisible.equals(pt2)) visibleLines.push([firstVisible, pt2.clone()]);
  return visibleLines;
}

With this function the crazy RAM usage was gone, and the execution time went down to about 16 seconds.

Round 3: Bare metal

Next I wanted to see what was the penalty of running this in Javascript, as opposed to running on bare metal. I added some helpers to download the canvas’s pixels and the lines to be tested as a text file with lots of numbers. I then implemented the same function as a small program in Go, which is my favorite language these days when I want to compile to machine code.

I’m sharing this program as a Gist: line-masker.go. It crunches the same lines in about 2.1 seconds in my environment.

Testing pixels in a shader

Getting from 300 seconds to 50 seconds to 16 seconds in Javascript was not bad, but I really wanted to see if this could be offloaded to the GPU for a dramatic improvement. This was my rough idea at the start:

There are two aspects of this that mean it only works on WebGL2, not WebGL. One is the need for textures with 32-bit float values. The other is the need for a dynamic loop.

I’ve uploaded the two shaders as a Gist, and I also uploaded the full Javascript file with the code that drives these shaders here: webgl-canvas-masker.js. (It includes some boilerplate code from WebGL2 Fundamentals[9].)

With this approach the line hiding calculations for my Cubic Space Division scene take about 30 msec.

A few remarks:

A failed attempt at depth testing

The face coloring approach’s performance is remarkable, but it does have a few downsides:

In the hope of avoiding these problems I attempted to derive a slightly different approach based on depth values. Those are written by fragment shaders (the real ones, used for rendering) into the W values in the output texture. It is possible to retrieve depth values when using Three.js with a trick involving two render passes, as shown in the depth texture example.[10] I hoped I could compare depth values with the distance from the camera plane of each point along an edge to decide if that point of the edge is visible or not.

I managed to make this work under some circumstances, but not reliably. Somehow the resolution of the retrieved depth values seems to be too small, even if I specify a 24-bit depth texture. I gave up on this after a long fruitless struggle, but if you can make it work, I would love to see the result!

It’s a wrap!

This text ended up being way too long already... As a concise summary, here are my measurements again from the different methods.

Approach Time
Javascript, naive, lots of superfluous calculations 300 sec
Javascript, naive, avoiding trivially invisible lines 50 sec
Javascript, reduced allocations 16 sec
Bare metal (Go) 2.1 sec
WebGL 30 msec

To wrap it all up, here’s another composition enabled by the fast WebGL-based line hiding method. This is the output of a cloth simulation based on Verlet integration. The veil is a 120x120 grid of squares, each made up of two triangles. It is also my most recent plot :)

A mesh representing a veil. Each triangular face has a different random color.
The veil as a colored mesh
A veil hiding something. We'll never find out what.
The veil, plotted on paper. © Gábor Ugray

References

[1] github.com/fogleman/ln

[2] blender.org

[3] paperjs.org

[4] threejs.org

[5] fxhash.xyz/u/zancan

[6] web.archive.org/web/20210429082853/https://twitter.com/zancan/status/1387685194468110337

[7] turtletoy.net/turtle/25b7bc4d43

[8] wikiart.org/en/m-c-escher/cubic-space-division

[9] webgl2fundamentals.org

[10] threejs.org/examples/?q=depth#webgl_depth_texture

[11] trmm.net/Plotter-Vision; source: github.com/osresearch/plotter-vision