House of Zodiac

Inspiration

Inspiration is from the anime series knights of zodiac and how humans used stars for navigation

What it does

You type 3 words from the judges 3000 list. That about 27 million possible list messages. The encoder draws the their sky and writes a file for a 3d printer: flat web of stars 84 mm across, with a frame, a ring and thin lines that hold the stars.

Up to four of the twelve constellations can be covered, broken or wrong and the words still come out, with a line such as "1 of 12 repaired". If more is missing, the reader says nothing. It never guesses. Both laptops are offline. Only the object carries the message from one to the other. The screen shows the world of the message: a small planet whose colours, hills, boulders and moons come from the same bytes as the stars, an astronaut who types the words, and a printer that builds the web layer by layer from the real print file.

How we built it

The three words are three positions in the list, 15 bits each. With three check bits they make 6 bytes, and Reed-Solomon coding adds 6 more. Each of the 12 bytes belongs to one constellation with 13 fixed places and says which three of them carry a star. A constellation always has exactly three stars, so the reader needs no brightness threshold: it takes the three strongest of thirteen. The places of the stars are irregular on purpose, so nothing looks like a grid. The lines that hold the stars are chosen by a minimum spanning tree over a Delaunay triangulation, with a cost that keeps lines away from places that must read as empty. That is why the web prints in one piece and still reads. The reader finds the square outline, flattens it, measures the 156 places in all 8 ways a square can lie, and lets the code pick the one that fits. Two of the six check bytes are never spent on repair, and that is what lets it refuse a bad read. If the outline is missing or slightly off, it finds the object from its four corner stars, or from the stars themselves. Reading is Python with OpenCV, NumPy and reedsolo. The design and the print file use SciPy, Shapely and trimesh. The scene in the browser is three.js, served by Python's standard library. Nothing uses the network while it runs. We wrote a software camera before we had a print. It photographs simulated objects with perspective, uneven light, blur, noise and faults such as a missing star oa broken line. Of 800 such photographs of ten kinds of object, 799 read and none read wrong. Of 3,000 random star patterns, none was accepted. The project has 292 automated tests.

Challenges we ran into

The shared printer queue grew to eight hours, so we could not count on a print for judging. We added a way to make the object by hand: the stars are shown as dots to trace onto paper. A hand-drawn square is rarely closed neatly, so the reader learned to find the sheet from its four corner stars alone. The reader has a second way to find the object when the outline is slightly wrong: it looks for the stars themselves. On the web this almost never worked, because the ring, the frame and every crossing of lines looked like stars. A new star finder that looks for round blobs fixed it. With every corner of the outline pushed 1.5 mm off, 20 of 20 webs now read where 2 to 6 of 20 read before. The judges' list starts with a header line. Left in, every word would have sat one place too far and the last word could not have been sent. In the first version of the scene the planet followed only the first word, because the first two bytes hold only that word. The world now comes from the six check bytes, which change with any of the three words. We have no printed web in hand yet. Every read rate above is from simulated photographs. A real camera has read the web shown on a phone screen, and that is all so far.

Accomplishments that we're proud of

No wrong answer in any test. The reader either gives the right three words or nothing. One design, several objects. The printed web, a solid plate, a picture on paper and a sheet traced by hand are all read by the same reader. It works offline from end to end, on two laptops that share nothing but the object. The page builds the real print file on its small printer, so what you see is the object you get.

What we learned

An error-correcting code can do more than repair. It lets the reader try every way the object can lie and trust only the one the code confirms. Design the object for its reader. Keeping the lines away from empty places did more than any tuning of the reader. A simulator let us work before the hardware existed, but it only tests the logic. It has no bent webs, no lens distortion and no cluttered desks. ave a fallback that needs no shared hardware. The traced sheet exists because of a queue.