Folk Computer

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== December 2023 newsletter ======

It's been a big year. Hard to believe that a year ago, there was exactly 1 Folk system in the world (the original one, folk0 at Hex House) & it ran about ten times slower than what we have now and could barely do anything besides display text and outlines. But there's still an enormous amount to do :-)

If you're in New York next month, we'd love to have you visit us at **[[https://partiful.com/e/aY32znMk7GWqEqI9t3KU|our next Folk open house]]**, in the evening on Wednesday, January 31.

We hope you enjoy this final newsletter of 2023 and have a great New Year's!

===== What we've been up to =====


==== Applications and demos ====

  * [[https://cristobal.space|Cristóbal Sciutto]] wrote a great [[notes:tableshots|piece about his camera slice->animation->tableshot work]], which doubles as an explanation of Folk.
    * {{notes:paper.gif?400}}
    * Omar: I [[https://twitter.com/rsnous/status/1737562049708749039|really like]] how there's, like, a printout of a PDF, and these stick figure drawings, and stuff like that, and the Folk programs operate on those, rather than being this purely synthetic AprilTag universe. We need more and deeper applications like that.

  * Andrés made a [[https://en.wikipedia.org/wiki/Hooke%27s_law|Hooke's law]] spring simulation in Folk:
    * {{newsletters:simulation.gif?0x300}}
    * Andrés and Charles collaborated on a Folk program that extends this to a ball that bounces around the table.

  * During the open house, a visitor asked Cristóbal if he could change the frame rate of his animation tool. It works splendidly:
    * {{newsletters:cris_animation.gif?400}}

  * [[https://twitter.com/naveenma|Naveen Michaud-Agrawal]] used the IMU of the M5StickC to publish a quaternion that rotates his bunny shader from last month:
    * {{newsletters:pxl_20231201_0459240022.gif?400}}


==== Other stuff ====

  * Our printer (Epson EC-C110) has really been acting up lately. Sometimes both lights turn on and it's just dead, no response on the network and no response to pressing buttons. Have to press Back+Power buttons to hard reset it
    * It once got in a state where I had to unplug it and power it down and reset it
    * It also often gets on the wrong Wi-Fi. Frustrating, especially when we're doing a demo (the moment of printing is when it all connects for visitors, so you want that to be really reliable)

  * We're still pretty pre-release and liable to break things, but we have a [[https://git.folk.computer/folk/|public mirror of the repo]] and have it under an open-source license now, which is nice (it means people can play around with it without getting our permission, and it means writeups like Cristóbal's can link directly to source code. I think it's important that people feel comfortable looking into the core of the system and seeing how things work)

  * Merged Cristóbal's [[https://github.com/FolkComputer/folk/pull/111|convex hull code from last month]] after he fixed some memory leak and convex hull algorithm issues
    * {{newsletters:img_9201.mp4?300}}

  * Cris has been working on [[https://github.com/FolkComputer/folk/pull/122|variable printed tag size and font size]], so you can start doing a bit of print design if you want your printed programs to have a specific form/look. You can print a program with a really big tag, for instance. I think this is really important for breaking down the current uniformity of Folk programs and creating new interactions.
    * {{:newsletters:pasted:20231230-211849.png?300}} {{:newsletters:pasted:20231230-211906.jpeg?300}}

  * Omar has been continuing to do a small amount of messing with an independent parallel Folk trie/evaluator in C. What do the lock-free/RCU data structures look like, can we decouple it from the Tcl heap and have a shared interprocess heap for everything, when do you have to copy, how does scheduling work...

==== Tabletop / in-system editor ====

  * Andrés has continued work on the in-system editor. There's now a save hotkey (''Ctrl + S''), separate regions for editing and previewing your program, and support for repeated key presses. There are a couple keyboard I/O management bugs Andrés is currently working through that will be addressed in January. Once those are ironed out the keyboard will be merged into the core Folk project and will be useful for teaching others how to make Folk programs without a laptop (think casual visits or multi-person workshops), editing the Folk system using Folk itself, and handling keyboard input in other Folk programs.
    * {{newsletters:charles_keyboard-medium.jpeg}}
    * Charles visited the studio this month and gave Andrés some great ideas for the editor for future releases.

==== Calibration ====

Omar: the new 3D calibration has been coming along. Here's a video of the current state of projector-camera calibration:

{{newsletters:img_2245.mp4}}


As you can see, calibration accuracy is actually very good in this area. Notice how it works in 3D, not just on the table plane, and how the projected outline is almost perfectly aligned with the tag. As we've said in previous newsletters, we're hoping that this (real-metric 3D space, 3D calibration) will open up a lot of new applications and sensor/actuator integrations.

Caveats:

  - this is near the center of an almost-coplanar projector-camera pair, so it's favorable conditions for the calibration
  - there is a fair amount of jitter each frame, which is pretty annoying and disruptive for real applications (especially if you extrapolate out from the tag itself into a larger page-sized region on its plane, as we would for labeling/outlining/other display)

Most or all of the improvement since last month comes from working on the nonlinear [[https://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm|Levenberg-Marquardt]] refinement -- we're still using the same kind of initial pose->linear pinhole estimate guess as before, then refining it with this iterative process.

The refinement now computes two radial distortion terms per lens (two for the projector, two for the camera, with initial guesses all 0s), which helps with accuracy toward the fringes of the projector/camera area. (I feel like the radial distortion applied is too conservative, it still gets pretty messed up at the fringe, 1cm+ error)

I learned about [[https://courses.cs.duke.edu/cps274/fall13/notes/rodrigues.pdf|three-degree-of-freedom vector representation of rotations]], which is a [[https://en.wikipedia.org/wiki/Rotation_formalisms_in_three_dimensions|surprisingly complicated subject]], with a lot of [[https://github.com/EgoMoose/Articles/blob/master/Rodrigues%27%20rotation/Rodrigues%27%20rotation.md#matrix-form|weird formulas you just have to implement]].

{{ :newsletters:pasted:20231230-005101.png?440 }}

I realized I had totally messed up how refinement deals with rotation -- you have to go from 9-degree rotation matrix to 3-degree vector, refine in that representation, then go back to 9-degree matrix when you're done. So I implemented those formulas and fixed that.

Rather than using [[https://people.cs.rutgers.edu/~elgammal/classes/cs534/lectures/CameraCalibration-book-chapter.pdf|Zhang]] and [[http://www.ok.sc.e.titech.ac.jp/res/PCS/research/procamcalib/|Audet]]'s technique of having separate 'camera calibrations' (basically calling OpenCV, incl. refinement) for the camera vs. for the projector, we now do a single joint end-to-end refinement for the entire system (including projector intrinsics, projector distortions, camera intrinsics, camera distortions, and camera-to-projector rigid motion), with the error function being the reprojection error of the training data AprilTags, like in the video above.

This end-to-end optimization produces much better results, as you might expect, although it's slow: it can take 1-4 minutes. It requires doing AprilTag pose estimation for every example tag at every iteration, and pose estimation is itself an iterative process that the AprilTag library does.

Next steps:

  * Work on backward compatibility so we can get it merged without breaking existing 2D programs for now. Probably record the table plane during calibration and downproject to 2D coordinates on it?
  * Performance analysis (Tcl profiling?) of calibration and of test, it's weirdly sluggish
  * Give on-system feedback during calibration (got pose 0, please move the board! got pose 1, please move the board! ... up to pose 9); maybe make it recenter tags after each pose to encourage wider coverage. Still unclear if our problems are best solved by improving training data vs. by improving calibration technique
  * Other ways to reduce error? Refinement takes total error from 16,000 to 1,400 but it should really be 0.
    * Tangential distortion
    * Test against existing calibration systems

Going to test offline and try projecting onto pose images to iterate faster, see distribution of error among poses.

(Worst comes to worst -- and this is another payoff of 3D calibration -- we can always just throw more cheap cameras at the problem, like have 2 or 3 or 4 cameras pointed at roughly the same space and integrate their observations...) (that's also nice because it gives us a way out of occlusion problems)

=== Jitter reduction ===

Cristóbal and I spent a day trying some tactics to reduce jitter, which I think might be the single biggest impediment to getting this thing merged and usable. The jitter is really noticeable in person.

The actual 2D AprilTag detection of corners in the camera image is actually very stable and reliable, and the images are clear, so that's not a source of jitter in our view. (We tried some moving-average smoothing stuff on the detected tag corners, but it didn't work that well, even if we made it really aggressive. We concluded that it has to be further on in the pipeline, not the input corners.)

So you have a stable input (locations of the corners in the camera image) and a pure function (camera corners -> 3D pose estimate -> reprojection corners), but somehow the output projection has jitter. So where is the jitter in the function?

We found two primary sources of jitter:

  - Instability in the AprilTag detector's tag plane->camera plane homography computation (which just uses 4 example points to compute a homography, (-1, -1), (1, 1), etc -> the 4 camera corners). this surprised us, since it's such a simple computation, pure linear algebra! this jitter is all over the place, the homography is very sensitive to subpixel changes in the corner points, it's like an overfitting kind of thing.
  - Instability in the AprilTag detector's iterative pose estimate. this is more expected, and it's more discrete, it often toggles between two distinct states where you might imagine there's some visual ambiguity; it probably ranks the possible states in different orders for different frames, leading to jitter

(See also [[https://github.com/AprilRobotics/apriltag/issues/122|this GitHub issue]] on the AprilTag repo.)

The homography jitter we were able to completely tamp down by forcing the homography to be affine (forcing the bottom-left elements to be zero), but that feels not right.

[[https://math.stackexchange.com/questions/2388259/differences-between-homography-and-transformation-matrix|{{newsletters:d37aa84f-a69d-4b6e-b614-f336f1f39f74-957-0001d76fcf0cf20b.png?500}}]]

But it works pretty well in practice, even under skew conditions. Weird.

As for the pose estimate jitter... well, we have some ideas and tactics we could try, we haven't gotten to it yet.


==== RFID refactor ====

Omar: the long-awaited RFID refactor is finally underway: [[https://social.omar.website/@omar/statuses/01HHE44PDWVG067GMBMT1Z47CX|I've made a lot of progress on it]] and have kind of broken through the previous point where I was stuck.

{{newsletters:a59286b1-d8a1-4055-b35d-eedc37c60fb6-957-0001d251ba77870d.png?450}}

I haven't caught up with our original branch on actual localization yet, but we now have **tag identities and checksums**, which is a capability we never had before. You can see above that we can carry out a back-and-forth and get that long reply from the tag (which tells us its ID).

{{newsletters:dd5cece8-5188-4cfb-9c04-0cd5468e8903-957-0001d43fe2718e9c.png?500}}

And here we query the tag a few times in a row and get a valid, checksum-passing ID response each time (although we're not printing the ID itself here, only the expected+received checksums):

{{:newsletters:pasted:20231229-170149.png?350}}

Checksum and identity are immediately useful in a few ways:

  * we now actually know that our signal is coming from the tag we want it to come from, much harder to get confused if a bunch of tags are accidentally in range / if we haven't cleaned the table properly

  * we have an end-to-end way to check channel estimate validity! we've always derived channel estimate from a tag reply packet, but we had no way to check that 1. that packet was legitimate and 2. our decoding of that packet was correct until now; now we can check that it got us a tag ID and that the tag ID passed checksum. this should help keep us from going off the rails with invalid data feeding into location estimate

and of course, you ultimately need tag identities to do any interesting application with RFID tags -- that's the point of them -- so we knew we needed to do this sooner or later. It's also the [[https://youtu.be/QKi1OH8Zstk?feature=shared&t=1090|hardest]] [[https://discourse.myriadrf.org/t/working-passive-uhf-rfid-reader-using-the-limesdr/2949/7|part]] of implementing an RFID reader on software-defined radio, because it's highly latency-sensitive (you need to decode entire tag packet and respond within 500 microseconds or so to get the tag ID), so it's a huge relief that we are able to do it and won't have to change approach to get it to work.



Some key things are:

  * compiling with -O3
  * enqueue and dequeue N items at once into/out of ring buffer
  * CRC (checksum) implementation -- I had CRC5 implemented for sending a QUERY to the tag, copied from [[https://github.com/zaphoxx/zuhf-rfid|zuhf-rfid]], but now I needed both CRC5 and CRC16, so I actually [[http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html|learned]] [[https://www.zlib.net/crc_v3.txt|how it works]]. in the end, I didn't implement it myself -- although it was very useful to know the basics and to even just know what type of function it is, what its inputs/outputs are, what parameters you need to read off the RFID spec -- I found this [[https://github.com/madler/crcany|crcany]] that can generate C code for CRC5 and CRC16 including the RFID ones and just vendored its output
  * I had [[https://social.omar.website/@omar/statuses/01HHE47788G4WVGG38RDDNA5CD|a nightmarish bug]] where [[https://www.amazon.com/RF-RFID-UHF-Practice/dp/0123945836|the RFID book]] literally gave the wrong command code to respond to the RFID tag and I spent days changing things to try to figure out why the tag wasn't responding! I had no way of figuring it out until I happened to read the relevant section of the RFID spec, I basically got lucky
    * {{newsletters:0144q4w3qyn7hczntqajd4hnwm.jpg?300}}

Next steps:

  * **working on making the new RFID system survive more than 1 or 2 tag conversations**: its state machine falls apart after a bit and it gets stuck or runs out of memory or whatever 
  * rebuilding the OOB side of the RFID system, getting bit boundary data to it in the right format, getting it synced up with pulses

==== Outreach and community ====

  * [[https://twitter.com/enjalot|Ian Johnson]] got [[https://discord.com/channels/956758212152025098/956758650700046366/1181391029564354621|his Folk system in Atlanta]] set up!
    * {{:newsletters:pasted:20231229-165810.png?300}} {{:newsletters:pasted:20231229-165725.png?300}}

=== Open house ===

We had another in-person open house on December 13 -- not long after the one at the end of November, but we like keeping up the pace. This one was more relaxed & a good opportunity to catch up with friends in the area.

{{newsletters:img_1865.jpeg?300}} {{newsletters:img_1881.jpeg?300}} {{:newsletters:pasted:20231229-165011.png?300}}

== Cart ==

The open house was a good push to follow up on [[newsletters:2023-11#outreach-and-new-systems|building folk-beads last month]]. This month, we built a cart for folk-beads, so we can wheel it in and out, since we only have it out during events (it's not a permanent system -- it uses shared space in Hex House):

{{newsletters:img_1812-2.mp4}} {{newsletters:img_1804.jpeg?300}}

The cart uses a cheap utility cart from Amazon and some two-foot quick clamps to keep the ultra-short-throw projector from falling over (and some blocks of wood we had lying around Hex House to raise the projector to table height while letting the HDMI and power cords jut down underneath). It's not the most stable thing ever -- you have to hold the projector while rolling it -- but it works well enough, and it's so nice that it's finally a self-contained unit.

(We probably also want it to have a longer power cable so we can wheel it around the space without unplugging and replugging. Ten feet is too short, I think.)

=== Folk User Group ===

We had a "user group" meeting in Discord on the evening of December 19, where we got on a call with people in the community (mostly people with running Folk systems). It was fun to see everyone again (the last one we did was a few months ago); we explained some recent and upcoming improvements to the system & we did some Q&A:

  * Andrés discussed editor, cart, CNC system, open-source
  * Naveen asked about system federation, wall-table (manipulation surface + larger display surface)
  * New calibration: We walked through the 3D calibration process live on camera (waving the calibration board around and watching it rewarp tags)
  * Omar gave a quick primer about how the evaluator works
    * Printed out and showed the key data structures (statements, trie, evaluator)
      * {{newsletters:08ad425f-9e76-4c77-bdda-9f373bd57c8c-957-00020653ba629c4a.png?200}} {{newsletters:e7b51111-74f1-4063-9367-d60e6cbaa2e8-957-00020606754ea101.png?200}} 
    * Daniel asked about events and event statements, so we talked a little about the semantic details there
    * Cris asked for a walk through a single evaluator step, so we did a whiteboard talk about the operations that go into the priority queue (Assert, Retract, Say, Unmatch, Collect) and how that queue gets drained each step
      * {{:newsletters:pasted:20231230-182016.png?300}} {{:newsletters:pasted:20231230-181955.png?200}}
    * Naveen asked about scaling properties: would it scale to thousands/millions of statements
      * (it should.. or at least adding a new statement shouldn't cost if it's not active)
      * Discussion of integrating Box2D or other engines/ways of resolving queries
  * Cris talked about tableshots
    * Omar: "I remember talking to Jacob about this -- how much every little weird capability addition actually opens up, where it's like, oh, we can crop images, or we can display images rotated, or we made a button, and each little thing opens up an entirely new class of applications and demo interactions. That's really exciting, especially as we have more of these things."
  * Ian asked about hand tracking, OCR, and other inputs besides AprilTags, how hard they would be to integrate
    * Andrés talked about the One Fact object recognizer model
    * Ian also asked about X11 or some other way to contain existing graphical applications in a page
  * Talked about next steps, board game format, documentation

We'll do another one in a few months, most likely.
===== What we'll be up to in January =====

  * **[[https://partiful.com/e/aY32znMk7GWqEqI9t3KU|Our next Folk open house]] will be on the evening of Wednesday, January 31, at our studio in East Williamsburg, Brooklyn.**

  * Omar is mostly out of town so may have to delay some of these, but:
    * improving the RFID error recovery / state machine; starting on sync and OOB
    * calibration accuracy improvement, some of this can be done on laptop from cached data/poses
    * maybe hacking on pure evaluator/Tcl/C stuff? a parallel Folk? variables/Observe?

  * Finishing up the tabletop editor and getting it merged, then follow-up to make virtual programs table-editable, other niceties like that to minimize laptop dependency

  * Potential laptop/phone integration work

===== Links we've enjoyed =====


==== Andrés ====
  * [[https://www.cofault.com/2022/08/3-lisp-infinite-tower-of-meta-circular.html | 3-lisp: an infinite tower of meta-circular interpreters. ]]
  * [[https://twitter.com/mietek/status/863560386053885955] | The Macintosh Core of Explanation: Four Comforting Thoughts]]
  * [[https://maggieappleton.com/tools-for-thought | Tools for Thought as Cultural Practices, not Computational Objects]]
==== Omar ====

  * [[https://myfriendpokey.tumblr.com/post/175137112840/my-friend-computer|my friend computer]]
  * [[https://wuffs.org/blog/free-software-needs-to-be-customisable|Free Software that you can't customise is not truly Free Software]]
  * [[https://www.zlib.net/crc_v3.txt|A painless guide to CRC error detection algorithms]]
    * [[http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html|Understanding and implementing CRC (Cyclic Redundancy Check) calculation]]
  * [[https://personalpages.manchester.ac.uk/staff/m.dodge/cybergeography/atlas/info_spaces.html|An Atlas of Cyberspaces: Three-Dimensional Information Spaces]]
  * [[https://arxiv.org/pdf/1707.06292.pdf|STag: A Stable Fiducial Marker System]]
  * [[https://www.otherstrangeness.com/2023/06/25/egregore/|Egregore]]
  * [[https://destevez.net/2023/02/maia-sdr/|Maia SDR]]