Originally published at getnobody.org.
A Cricut or a laser doesn't know what a pixel is. It follows paths: closed outlines, each one a loop the blade or beam can travel from start back to start. So the job of a tracer is to look at a grid of colored squares and write down where the edges are, in as few curves as it can without drifting from the picture.
I built one for Cutline, which turns a PNG or JPG into files for Cricut, Silhouette, Glowforge, LightBurn and vinyl plotters. It runs in the browser tab. Here is every step it takes, with real numbers from the sample badge on Cutline's home page: a 900 x 900 px drawing with paper grain, 40 dust specks and 10 pinholes, which is what a phone photo of a print looks like.
(Chart: see the original post.)
1. Quantize: 220 colors down to 5
The badge is drawn with five paints: paper, cream, ink, pine green and a mustard sun. But anti-aliased edges and paper grain mean the file actually holds 220 distinct RGB values. Vinyl comes in sheets of one color, so the first job is to decide which five colors the image "really" has, and which one each pixel belongs to.
I use k-means, with two changes that matter in a browser:
- Cluster a histogram, not pixels. Every pixel drops into one of 32,768 bins (5 bits per channel), and k-means runs over the bins weighted by their counts. A 4096 px image has 16 million pixels but never more than 32,768 bins, so the clustering costs the same at any size.
- Seed it the same way every time. The first center is the fullest bin, and each next one is the bin farthest from the centers picked so far, weighted by count. Random seeding would give a slightly different palette on every slider move, and the layers would flicker.
A light blur runs first so single grainy pixels don't vote for a color of their own. But the final layer color is the average of each cluster's unblurred pixels, because the blur shouldn't tint the vinyl.
On the badge this takes about 55 ms and finds paper, cream, ink, green and sun. Paper covers most of the image's border, so it becomes the background and gets dropped: nobody cuts the paper.
2. Masks and cleanup
Each remaining color becomes a mask: a grid of yes or no, one bit per pixel. Straight out of quantization, those masks are a mess:
(Chart: see the original post.)
A thousand pieces of sun would mean a thousand tiny cuts to weed by hand. So the cleanup finds connected regions (4-connected, so pixels touching only at a corner don't count as joined) and:
- removes specks: any region smaller than the speck size slider. On the sample that is anything under 146 pixels at preview size.
- fills pinholes: any hole that small, as long as it doesn't touch the image border.
- stacks the layers for layered vinyl: each layer also covers every layer above it, so the colors overlap a little instead of meeting edge to edge. Vinyl never lands exactly where you put it, and an exact butt joint shows the shirt through a hairline gap.
That last promise is where I found a bug.
The hairline gap
My first cut looked right in the color view. In the cut view, the bottom layer of the badge had two thin crescents running along the inside of the black ring: holes in a layer that should have been one solid disc.
The cause was the anti-aliasing. Where black meets cream, the edge pixels are a blend, and k-means doesn't always give a blend to either neighbor: some of them land closer to a third color. They formed thin, disconnected slivers of that color along the ring, each smaller than the speck size, so cleanup deleted them. Deleted pixels belong to no layer. Stacking can only OR together what exists, so the gap survived into the file.
My first fix was to merge every small region into whichever color surrounds most of it, instead of deleting it. That closed the gaps, but it wrecked the outer edge of the badge, where the same kind of slivers sit between the ink and the paper. Some merged outward and some merged inward, and the smooth circle came out bumpy:
(Chart: see the original post.)
The fix that stuck is narrower. After specks are removed, take the union of every kept color and look at its holes. A real hole, like the inside of a letter O, is background, so it holds background pixels. A gap left by deleted slivers holds none. So any enclosed hole with no background pixel in it is a gap, and it goes to the bottom layer. The badge's bottom layer is now one disc with no holes, and its outline is back to 20 segments.
3. Outline: marching squares
Now each mask is clean, and the tracer needs its edges. The tracing library I use, imagetracerjs (public domain, about 40,000 downloads a week), does this with a version of marching squares.
It slides a 2 x 2 window over the mask. The four pixels under the window are each in or out, so every position is one of 16 cases, stored as a 4-bit number. Case 0 (all out) and case 15 (all in) mean no edge passes here. Every other case says exactly which way the edge runs through that corner. Starting from any edge corner and following the cases, you walk around the shape and come back to where you started, which gives a closed loop for free.
(Chart: see the original post.)
On the badge's outer circle that loop has 3,192 points, one per pixel corner along the edge. A blade following it would stutter through three thousand tiny right angles.
Before fitting, the library moves each point to the midpoint of its edge step. That turns the staircase into an 8-direction path: diagonals where the pixels step evenly, straight runs where they don't.
4. Fit: lines first, then curves
The last step turns thousands of points into a few segments, with a greedy recursive fit:
- Cut the path into runs that only use two of the 8 directions.
- Try a straight line from the start of the run to its end. If every point is within the line tolerance, keep it.
- If not, find the point farthest from that line and fit a quadratic curve through the start, that point and the end. If every point is within the curve tolerance, keep the curve.
- If not, split the run at the worst point and do both halves again.
The two tolerances are the whole trade-off between faithful and smooth, and in Cutline they are the Detail and Smoothing sliders. Here is what Smoothing does to the badge's outer circle:
(Chart: see the original post.)
Past a point, more smoothing starts to round off corners you wanted sharp, like the peaks of the mountains. That's why it's a slider and not a constant.
Potrace is the classic alternative. It finds the polygon with the fewest sides that stays within a pixel of the edge, then decides corner by corner whether to round it with a Bezier curve. It often makes nicer curves, but it is GPL, and I wanted a permissively licensed library I could ship in a paid product without thinking about it.
5. Make it a file a machine accepts
The fitted segments go through a few more rules before anything is written:
- Every path is closed and ends exactly where it started, so the cutting app treats it as a shape and not a stray line.
- Coordinates go into a fixed 1000-unit box, rounded to 2 decimals, so the same design gives the same file.
- Holes stay with their shape: the inside of the ring is part of the ring's path, filled with the even-odd rule, so it cuts as a hole instead of a second piece.
The result for the badge: 4 layers, 6 shapes, 7 closed paths and 203 nodes, from 810,000 pixels. The whole preview trace takes about 170 ms on my laptop, which is fast enough to re-run on every slider move.
From there the output is just formatting. Cricut Design Space wants an SVG sized in inches with one group per color. Silhouette Studio's Basic Edition only reads DXF, which has no fills, so every outline becomes a polyline. A laser wants red hairline strokes for cutting and black fills for engraving. The tracing is the hard part; the file formats are bookkeeping.
If you have a logo or a drawing you'd like on vinyl, try it on Cutline. The preview and all the sliders are free, and the files are $2 per image, paid once.
