sixel: fix some weird artifacts

Since getColor's color assignment eagerly fills in holes with the
nearest neighbor of the first such observed node, it is prone to falling
into a local minimum where dithering ends up switching between a few
very wrong colors.

Ensure this doesn't happen by always allocating at least 4 nodes of the
octree branch. (Allocating all 7 seems to result in a heavy performance
hit; just 4 means at worst 4096 extra nodes, but likely a lot less, and
I don't see a difference in either output or performance.)

1 files changed, 13 insertions, 0 deletions

diff --git a/adapter/img/sixel.nim b/adapter/img/sixel.nim
index 3eeacaf1..b124e235 100644
--- a/adapter/img/sixel.nim
+++ b/adapter/img/sixel.nim
@@ -261,6 +261,19 @@ proc getColor(root: var NodeChildren; c: ARGBColor; nodes: seq[Node];
     let child = children[idx]
     if child == nil:
       let child = nodes.getColor(c, diff)
+      # No child found in this corner of the octree. This is caused by
+      # dithering.
+      # Allocate at least 4 ancestors, so that other colors with the
+      # same initial bits don't end up using something wildly different
+      # than the dither intended.
+      while level < 4:
+        let idx = RGBColor(c).getIdx(level)
+        let node = cast[Node](alloc0(sizeof(NodeObj)))
+        node.idx = -1
+        children[idx] = node
+        children = addr node.u.children
+        inc level
+      let idx = RGBColor(c).getIdx(level)
       children[idx] = child
       return child.idx
     if child.idx != -1: