search

dankamongmen / notcurses

blingful character graphics/TUI library. definitely not curses.
https://nick-black.com/dankwiki/index.php/Notcurses
Other
3.49k stars 112 forks source link

Program optimal palettes, when applicable, for RGB-native ccc terminals #371

Open dankamongmen opened 4 years ago

dankamongmen commented 4 years ago

This is very similar to #370, and will use much of its infrastructure. Even on RGB-native terminals, we don't necessarily want to be using RGB escapes. Such an escape is about 60% heavier, bytes-wise, than its palette-indexed equivalent. Even if we have to emit a palette-programming escape, that beats the RGB as soon as it's used for more than a single cell in a single frame (an RGB value used once, and never again, beats out the palette program plus palette index by about 50%, something important to remember).

Whenever a frame uses fewer than 255 colors, we can represent it perfectly using custom-programmed palette-indexed color. Given that a terminal using fewer than 255 colors must be using at least some color more than once (or be smaller than 80x4, heh), it's almost certain that palette-indexed color is a win for such frames, even if it's reprogrammed each frame. The only way it wouldn't be is if you had a small number of colors being used for most of the screen, and a large number of colors used for a single cell each, in which case the optimal choice is a hybrid...oh shit. There's the general solution :D :D :D <3 <3 <3.

On RGB-native terminals with the can_change capability, track the colors being used. Any color used more than once (contiguous regions count as a single use) is a candidate for palette replacement. If there are more than 254 candidates, take the 254 most frequently used candidates. Program the palette with them (either at beginning of frame render or before first use). Use them via palette-based indexing. Specify the others directly.

This wins on every single case, assuming the cost of the lookups to notcurses is less than the cost of sending the extra data up through the stack. But that's just a matter of being clever.

The difference between this bug and #370 is that on #370, we must consider how RGB-specified cells will be mapped to our palette, and perhaps optimize for best visualization. Here, we can simply optimize for combinatorics. I much prefer combinatorics :D.

fucking badass!!!!!!!!!!!!!!!! i am the master! <3 LET'S DO IT.

dankamongmen commented 4 years ago

One interesting aspect here is that one must take undamaged cells into account for reprogramming. If you just flip their palette index underneath them, they're going to change color.