View source for Theory and Practice of Sprixels

[[File:Pixel-orca.png|thumb|right|orcas on segways]]

'''[[Dankblog|dankblog!]] 2021-03-29, 0524 EDT at [[Viewpoint|the danktower]]'''

<blockquote>Our ordinary language has no means for describing a particular shade of color.—Ludwig Wittgenstein</blockquote>

I've spent significant time over the past few weeks adding "sprixel" support to [[Notcurses]], culminating (thus far) in yesterday's [https://github.com/dankamongmen/notcurses/releases/tag/v2.2.4 2.2.4 release]. What's a sprixel? Numerous [https://github.com/dankamongmen/notcurses/blob/master/TERMINALS.md terminal emulators] support one or another "graphic protocol" by which bitmaps of arbitrary size can be written to the glyph-based viewing area. Showing that dynamic control of the font <b>is not</b> even approximately equivalent in power to such graphic protocols is left as an exercise for the reader (or you can scroll to the end).

==Sprixel flavors==
There are at least four major methods:
* the venerable DEC [[Sixel]] protocol, introduced on the VT125, and also present on at least the VT240 and VT 330. Implemented by at least XTerm, Mlterm, and foot
** with patches out for at least VTE, alacritty, and Windows Terminal.
* Kitty's protocol, advanced by Kovid Goyal.
* The "1337" iTerm2 protocol, also implemented by wezterm.
* You can shit <i>con brio</i> all over the Linux framebuffer directly when in a framebuffer console.

Sixel is both the oldest and the most widely supported, though the majority of this support has come in the past year. Unfortunately, while passable for controlling early-Eighties nine-pin color dot matrix printers like the DEC LA50, it's pretty undesirable from a console bitmap standpoint. Nonetheless, combined with "sprite", it has loaned its name to "sprixels".

These protocols differ from each other in fundamental, important ways, and forming an abstraction from them isn't trivial. Integrating them wholly into the z-ordered semantics of Notcurses was still more difficult. Notcurses works via <i>piles</i> (rendering contexts) of <i>planes</i> (drawing surfaces), totally ordered on a z axis. Higher planes obscure or blend with lower ones. When Notcurses <i>renders</i> a pile, it projects these planes down onto a single plane, solving a single surface; it <i>rasterizes</i> this virtual surface to the physical viewing area by encoding it as a set of terminal escape codes and UTF-8 data. Only cells which have changed need to be rasterized, and eliding unchanged cells is a critical optimization, usually cutting the output size down by 90% or more. Every output byte is multiplied several times before becoming visible (we must copy it to a kernel buffer, the terminal must read it from a kernel buffer, and the terminal must display the resulting cell), so trading some computation for fewer output bytes is well worth it.

The elegant model of planes of fixed-width, independent cells solving for a single cell matrix already breaks down in the presence of [[Unicode]] wide glyphs, perhaps foremost among them U+FDFD ARABIC LIGATURE BISMILLAH AR-RAHMAN AR-RAHEEM ﷽, a single glyph occupying anywhere from one to who-knows (I've seen 9) cells, depending on font, font engine, and terminal emulator. Wide characters cannot be printed in part, and printing another character anywhere atop a wide character obliterates all of the old character. Even restricting ourselves to characters two cells wide, a single character can annihilate four columns containing two characters:

* column 0: left side of character A
* column 1: right side of character A
* column 2: left side of character B
* column 3: right side of character B

Print a wide character C at column 1, and we end up with

* column 0: space
* column 1: left side of character C
* column 2: right side of character C
* column 3: space

This isn't a problem with a single virtual plane, but imagine we have two planes, P0 and P1, with P0 above P1. They are of equal size, and P0 is transparent by default. P0 has a wide character at column 1. P1 has a wide character at column 0. What do we render? It's impossible to render the first half of P1, despite that being the logical render. Allah, the All-Powerful, has fucked us again!

This difficulty is ratcheted up significantly in the case of sprixels. In the most complicated case, a single sprixel might need to be both "under" (obscured by) and "over" (partially obscuring) text, and the set of cells obscuring and being obscured can change every frame. Imagine, for instance, that we have the following friendly octopus (512x357px, and note that it has a transparent channel):

[[File:Octopus-transparent.png|frameless|200px]]

Let's assume a cell geometry of 11x20, which just happens to be my current cell geometry. 512 pixels then occupy a little over 46 columns (512 == 46 * 11 + 6), while 357 pixels occupy just about 18 rows (357 == 17 * 20 + 17). We want to be able to draw this happy fellow atop a background of text:

[[File:Octopus-transparent-bg.png|frameless|200px]]

Note that the text "underneath" the octopus can change while the octopus is present, and this change must be reflected if the text is visible. We also want to draw on top of the octopus, and this text too can change while the octopus is displayed, or even go away, in which case the octopus must be restored.

[[File:Octopus-transparent-bg-fg.png|frameless|200px]]

We might want to write atop the sprixel, but with a transparent background. Unfortunately, this is only really possible with Kitty (I'm excluding ideas like sampling the glyph and interpolating an RGB background for the text cell), where we can place an image at "z=-1" in the internal kitty image Z-axis to place it underneath text. Here I've done so, placing the sprixel underneath the layer of 'a's, but still annihilating the sprixel with some other text.

[[File:Octopus-transparent-kitty.png|frameless|200px]]

Sixel doesn't really provide this capability; writing text over a sixel graphic will annihilate affected cells in their entirety. Here we come to the most meaningful difference between Sixel and Kitty/iTerm: the former is <i>temporal</i>, the latter <i>positional</i>.

===Temporal vs Positional===
Sixel writes the provided glyph as a unit, starting at the current cursor position (assuming we've entered DECSDM aka "Sixel Display Mode", which we always do—otherwise all sixels are emitted at the upper left corner of the display). Bits not specified in the sixel are transparent (assuming the Device Control String has used the value 2 for parameter <tt>P2</tt>), and transparent pixels leave undisturbed whatever was already present at the time of emission. Writing an entirely transparent region is a no-op. Writing a new character (or new Sixel pixels) anywhere in the graphic's region will wipe out the entirety of that cell. The Sixel data thus annihilated is not recoverable. This means that updating the text underneath a Sixel will blow the obscuring graphics away, requiring that the affected Sixel pixels be rerendered. In the event of stacked sprixels, we would potentially need to rerender the entire stack. In a naive implementation, changing one text cell "underneath" the octopus could result in painting 781 cells (the text cell actually being changed, and the 780 cells of the octopus). This is plainly undesirable.

With Kitty, a graphic is positional. All text is assumed to be at z=0. Graphics with non-negative coordinates obscure text. Graphics with negative coordinates sit underneath text. Note that this means we must choose whether a Kitty sprixel is going to have text above it, or under it, but no arbitrary single sprixel can do both.

===Cell wiping===
Thankfully, unlike Sixel, we have the ability to delete graphics in the Kitty protocol (Sixel graphics can only be cleared along with a larger screen region, or entirely obscured by other output), so we can "cut" chunks out of our bitmap, delete the visible sprixel, and load the new one; doing so effectively allows us to make text underneath a "z=-1" sprixel dynamically available. We cut the chunk out by setting the [https://en.wikipedia.org/wiki/Alpha_compositing α (alpha)] parameter to 0 across the breadth of the affected RGBA region. This function, <tt>sprite_kitty_cell_wipe()</tt>, can be found in [https://github.com/dankamongmen/notcurses/blob/master/src/lib/kitty.c src/lib/kitty.c]. Easy peasy. We must keep the original α values somewhere, in case the damage need be recovered (we needn't duplicate the RGB values; we leave those as they are). Since we normalize the α values on input to either 0 or 255, we only need to keep one bit of state for each pixel, and map back that bit times 0xff. For a 1024x1024 pixel image (4MiB), this would be be a maximum 1Mb bit vector, representing 3.125% overhead.

===Color quantization===
The Kitty protocol accepts arbitrary RGBA 32-bit words in the sRGB color space; our natural internal format is 24bpp RGB plus two bits of alpha, so that's great—our colorspaces match. Sixel is a palette-indexed format. Common sizes are 16-, 256-, and 1024-entry palettes (in XTerm, this is controlled with the <tt>numColorRegisters</tt> X resource. Palettes are independent unless the <tt>privateColorRegisters</tt> resource is enabled). A color quantization step is thus necessary (note that this these quantizations can be performed in perfect parallelism when split across multiple frames/images, but not necessarily within a single frame). There are five essential color quantization algorithms:

[[File:Penrosetiling.png|thumb|200px|right|These images throw libsixel for a loop; <tt>img2sixel</tt> chugs along, and then generates no output.]]

* Uniform chunking aka popularity algorithms / [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi clustering]. Any child can come up with this scheme. Autumn Lamonte's [https://jexer.sourceforge.io/ Jexer] uses a clever variant on this. Very fast, but the least accurate on difficult images.
* [https://en.wikipedia.org/wiki/Median_cut Median cut], with or without a histogram. [https://web.archive.org/web/20050606233131/http://citeseer.ist.psu.edu/rd/0%2C238914%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/10961/http:zSzzSzwww.isse.gmu.eduzSz~njohnsonzSzSteganographyzSzbibzSzpubzSzheckbert82.pdf/heckbert80color.pdf Heckbert in SIGGRAPH 1982]. Used by [https://github.com/saitoha/libsixel libsixel] by way of [http://netpbm.sourceforge.net/ netpbm].
* [https://en.wikipedia.org/wiki/Octree octrees], introduced by [https://sci-hub.do/10.1007/978-3-642-83492-9_20 Gervautz and Purgathofer] in 1988.
* Kohonen neural nets as introduced by [https://www.researchgate.net/profile/Anthony-Dekker/publication/232079905_Kohonen_neural_networks_for_optimal_colour_quantization/links/09e4150ba8346d8ce9000000/Kohonen-neural-networks-for-optimal-colour-quantization.pdf Dekker in NeuQuant]. Used by the [https://lib.rs/crates/color_quant color_quant crate].
* K-means clustering, perhaps best known from [https://exoticorn.github.io/exoquant-rs/exoquant/ exoquant].

Notcurses uses my own take on Voronoi, a scheme I call "relaxation", as seen in the <tt>refine_colors()</tt> function in [https://github.com/dankamongmen/notcurses/blob/master/src/lib/sixel.c src/lib/sixel.c]. I'll likely be changing this up, though. In the meantime, it's very robust, working properly on images that trip up libsixel. For heavy-duty testing, the fascinating images at [https://allrgb.com/ AllRGB] have been invaluable.

===The T-A Matrix===
Associated with a sprixel (technically with the plane on which the sixel is blitted, so it can be reused across frames) is a "transparency-annihilation matrix" having dimensions equivalent to the sprixel's area in cells. These matrix entries are loaded when the sprixel is first encoded, as either 0 (a wholly <b>opaque</b> cell) or 1 (a cell region with at least one <b>transparent</b> pixel). These values are used to determine whether or not a cell <i>underneath</i> the sprixel needs be updated to reflect a change in the render; if the cell is entirely obscured by the sprixel, there's no need to change the text in the cell (and this saves us an expensive redraw when using Sixel). When we cut out a cell, the T-A matrix takes the value 2 (<b>annihilation</b>). Only with Kitty do we actually cut the cell out of the encoded glyph (which we then delete and replay), but we always want to track this, because we often reuse the T-A matrix across frames. When we encode an image with a preseeded T-A matrix in hand, we implicitly drop the annihilated pixels. Using this method, we never obscure text atop a series of frames, eliminating flicker we would otherwise suffer.

As you might have already guessed, the cut vector mentioned above is hung off the T-A matrix (though it must be refreshed on each frame change). When an annihilated cell is uncovered, it must be reconstructed; the T-A matrix value is changed to 4 (<b>anastasis</b>). At render time, the resurrected cell can either be rebuilt using the cut vector directly into the image (Kitty), or the Sixel-based sprixel can be reconstructed <i>in toto</i>. It might be desirable to revive into cell-sized sprixels, but see below. Either way, following reconstruction, the TAM entry returns to 0 or 1.

As noted, the T-A matrix would seem to be a property of a sprixel, but is really a property of the sprixel-plane (it must sometimes have lifetime beyond the sprixel, but we must check its suitability for further sprixels). The T-A matrix is absolutely key to getting decent flicker-free performance while supporting arbitrary damage to sprixels.

===A False Path: Mosaics===
All of this complexity arises from two things:
* Sprixels are large, potentially covering many cells in a row, and even a rectilinear area across multiple rows. The mere presence of atomic wide characters is enough to disturb the model of perfect, independent cells. Sprixels destroy the illusion entirely.
* Painting sprixels tends to be slow, and is prone to flicker. We very much want to avoid sprixel repaints.
Give this problem to a ten year old, and they'll come back eventually, pointing out that things would be greatly simplified by drawing sprixels as "swarms" of cell-sized sprixels. At this point, we can just reuse our proven Z-ordered TUI painting algorithm, with the additional rule that a solved sprixel cell containing transparency should print the glyph, and then (in sixel) print the sprixel cell. in kitty, we'd need only reprint the glyph (generalizing a stack of sprixel cells is left as an exercise for the reader)! Printing atop a sprixel would mean simply deleting the sprixel cell (in kitty), and printing the glyph. No computationally intensive "cuts", nothing difficult at all, really.

As a bonus, your color quantization pretty much goes away, since you're now doing a set a palette per cell. For a 10x20px cell, a 256-entry palette can decay to no-lookahead RGB. At the 1024-entry paint, only pathological cell sizes require quantization.

One downside would be that with Sixel, you're dealing with 1x6 column sets of pixels (hence the name). Assuming a 20px high cell, this requires 4 sixels per column, with the bottom 4 bits transparent (active mask of 0x03). This would mean 20% overhead (generally, for a cell Hpx high, overhead would be (6 - H % 6) / H for H ≆ 0 mod 6). This would be unacceptable, but thanks to Sixel's RLE functionality, the transparent excess could be encoded efficiently, in five bytes. Five bytes per <i>cell</i>, however, still represents significant overhead, but only on the order of kilobytes
for a 1024x1024px sprixel, comfortably less than 1% overhead.

Sounds great, right? Alas, with a Flaming-Sword-of-the-Most-High-like strike, Allah dashes your plans. Emitting more than a small number (fewer than ten) will bring at least XTerm to an absolutely unusable crawl. [https://en.wikipedia.org/wiki/Slaughterhouse-Five So it goes].

<blockquote>My memory, sir, is like a garbage disposal.—Jorge Luis Borges</blockquote>

===A False Path: Font reprogramming===
"But dank," you ask, "what if we were to seize the means of glyph production, aka the font?" Not only is that a non-portable unholy fucking mess, you still only get two colors in a stream-written glyph. Colors matter as much if not more than resolution. The NES and the SNES had basically the same resolution; the main reason why Super Mario World looked so much better than Super Mario Bros was because it had a much wider palette.

==External Links==
* The [https://vt100.net/docs/vt3xx-gp/chapter14.html VT330/VT340 Programmer Reference Manual Volume 2: Graphics Programming] from vt100.net
* The [https://sw.kovidgoyal.net/kitty/graphics-protocol.html Kitty graphics protocol]
* The [https://iterm2.com/documentation-images.html iTerm2 graphics protocol]
* Thomas Dickey's [https://invisible-island.net/xterm/ctlseqs/ctlseqs.html XTerm Control Sequences] document
* [https://gitlab.com/klamonte/jexer/blob/master/README.md Jexer], Autumn Lamonte's Java library inspired by Borland's "Turbo" line of produts, is the only thing that comes close AFAIK

'''previously: "[[Spooky_tmux_at_a_Distance|spooky tmux at a distance]]" 2021-02-20'''

[[Category:Blog]]