Tessellate Me
Draw a cat and the screen fills with interlocking cats.
Draw a closed outline in the box, or press Example.
Draw something with an outline: say, a cat with eyes and whiskers. When you stop, the outline bends into the nearest shape that tiles the plane, your lines ride along into every copy, and the screen fills with interlocking cats. Everything runs in your tab.
The science is not new. Fitting a tile to a drawing is Kaplan and Salesin’s Escherization (SIGGRAPH 2000). Koizumi and Sugihara turned the fit into an eigenvalue problem, and Nagata and Imahori made the search exhaustive over the 9 general isohedral families and published it as MIT code, EscherTiling, which is the solver here. EscherWeb, hogexcom’s エッシャー化 and CatsEye (Easterly and Jack, Bridges 2016) put versions of the idea in a browser first. What this one adds is your strokes, carried into every copy, on freehand doodles that were never drawn to be tiles.
The tile was right and the picture was wrong
An early spike ran the authors’ solver on 40 unpicked Quick, Draw! doodles. The tiles followed the outlines closely, yet tiled outlines mostly read as wavy stripes and blobs. With the doodle’s own strokes carried into each copy, they read as cats, rabbits and snails. That was a judgment by eye on 5 doodles, so before any browser code it was measured with an off-the-shelf Quick, Draw! classifier and a control, against a bar written down first: the tile carrying its strokes had to keep the doodle’s class for 70% of the doodles the classifier recognizes as drawn, and beat the outline alone by 20 points.
| Doodles | Strokes carried | Outline only | Gap |
|---|---|---|---|
| The spike’s 40 | 20 of 36, 55.6% | 6 of 36, 16.7% | +38.9 points |
| The 400-doodle corpus, the shipped pipeline | 224 of 333, 67.3% | 72 of 333, 21.6% | +45.6 points |
All measured, classifier only; a blind human check is built and has not run. The strokes make a large difference, and the 70% bar was still missed, also with 80 points per outline instead of 60 and with a re-rank of the candidates. So the claim here is the smaller one the data supports: your cat’s lines, in a tiling.
How it works
- Closing the doodle. Doodles are open strokes, not shapes. An integer image pipeline (rasterize, morphological closing by an exact distance transform, fill, largest component, marching squares, a fixed-point resample to 60 points) turns the strokes into a silhouette, with no Canvas2D and no floating-point decisions, so a share link rebuilds the same silhouette in every browser. A thickness test catches outlines that stayed open, and a “close it?” nudge offers the bridge that would enclose the most area.
- The search. The C++ solver is compiled to WebAssembly (169,366 bytes, 48,108 gzipped) and runs in four Web Workers, one family plan each, so each family keeps its own best tiles. Its output is bitwise identical to a native build of the same code, in Chromium, Firefox and WebKit, with four Workers or one.
- Carrying the strokes. Mean value coordinates map every stroke point from the silhouette into the tile. That map can fold, so every triangle of a mesh of the silhouette is checked, and a family whose warp folds gives way to the next best.
- Drawing it. Canvas2D, one transform per copy; reflected copies mirror their strokes for free.
Numbers
Measured on the cloud machine this was built on (a 4-core Xeon, headless browsers), not a laptop: the search over all 9 families finishes in about 250 ms at the median and 530 ms at p90, and a drawing tiles about 2.5 s after the last stroke. The app waits that long in case you are still drawing (“Tile it” goes sooner), and the search finishes well inside the wait. The “Info” panel in the app measures your own device. Laptop and phone numbers are still to be recorded.