Wie Ausmalbilder technisch gespeichert werden
Keine Vektoren und kein Farbeimer zur Laufzeit. Gespeichert wird ein zweites Bild, dessen Pixelwerte Flächennummern sind, dazu ein winziger Farbstreifen und ein Shader, der beides zusammenrechnet.
Ein Ausmalbild mit tausend Flächen wirft eine Frage auf, die von außen unsichtbar bleibt: Woher weiß die Software beim Tippen, welche der tausend Flächen getroffen wurde, und zwar in weniger als einer Bildwiederholung? Die naheliegenden Antworten sind alle falsch, und die richtige ist einfacher, als man erwarten würde.
Interessant ist das nicht nur für Leute, die selbst etwas bauen. Fast alles, was beim Ausmalen als Eigenart auffällt, folgt direkt aus dieser Speicherform: die harten Kanten ohne jede Weichzeichnung, das verschwinden der Ziffern beim Herauszoomen, die Tatsache, dass der Fortschritt auch nach Monaten noch da ist, und die winzige Dateigröße eines Spielstands.
Warum keine Vektoren
Der erste Gedanke ist eine Vektorgrafik: jede Fläche ein Pfad, wie in einer Zeichendatei. Technisch ginge das, praktisch ist es die schlechteste der verfügbaren Möglichkeiten. Um herauszufinden, in welcher Fläche ein Fingertipp liegt, müsste für jeden Pfad ein Punkt-in-Polygon-Test laufen, und ein Motiv mit dichter Ornamentik hat schnell mehrere tausend Pfade mit jeweils hunderten Stützpunkten. Dazu kommt, dass benachbarte Pfade sich eine Kante teilen und diese Kante in zwei getrennten Datensätzen doppelt beschrieben ist, was Rundungsfehler und haarfeine Lücken zwischen zwei gefüllten Nachbarflächen praktisch garantiert.
Vektoren sind für Skalierbarkeit gebaut, und Skalierbarkeit ist hier kein Vorteil, weil das Motiv ohnehin für eine bekannte maximale Vergrößerung ausgelegt wird. Bezahlt würde also für eine Eigenschaft, die niemand braucht, mit einer Trefferabfrage, die niemand haben will.
Warum kein Farbeimer
Der zweite Gedanke ist das Füllwerkzeug aus Bildbearbeitungsprogrammen: ein Klick, ein Flutfüllalgorithmus läuft von dort aus nach außen und stoppt an den schwarzen Linien. Das scheitert an zwei Stellen. Erstens kostet jede Füllung Rechenzeit proportional zur Fläche, was ausgerechnet die großen, angenehmen Flächen zu den langsamsten macht. Zweitens, und schwerwiegender, sind die Umrisslinien in einer normal gerenderten Bilddatei kantengeglättet, also mit weichen Übergängen versehen. Ein Flutfüller braucht aber eine eindeutige Grenze. Wo der Übergang zwischen Linie und Fläche über drei Pixel verläuft, sickert die Füllung entweder durch oder lässt einen grauen Saum stehen.
Man kann das mit Toleranzwerten notdürftig reparieren, aber jede Reparatur verlagert das Problem nur an eine andere Stelle. Das eigentliche Missverständnis liegt darin, zur Laufzeit etwas herausfinden zu wollen, das man auch vorher wissen kann.
Was tatsächlich gespeichert wird
Gespeichert wird ein zweites Bild, gleich groß wie das sichtbare, das nie jemand zu sehen bekommt. Es enthält keine Farben im üblichen Sinn, sondern in jedem Pixel eine Zahl: die Nummer der Fläche, zu der dieses Pixel gehört. Diese Indexkarte ist das eigentliche Dokument. Alles andere lässt sich daraus ableiten.
Die Trefferabfrage schrumpft damit auf einen einzigen Lesezugriff. Der Fingertipp liefert eine Koordinate, die Koordinate wird auf die Indexkarte umgerechnet, und der dort abgelegte Wert ist die Flächennummer. Kein Suchen, keine Schleife, keine Abhängigkeit von der Anzahl der Flächen. Ein Motiv mit dreitausend Flächen antwortet exakt so schnell wie eines mit dreißig.
Weil eine Zahl pro Pixel abgelegt werden muss und Bildformate mit drei oder vier Kanälen arbeiten, wird die Flächennummer üblicherweise über mehrere Kanäle verteilt: der niedrige Teil in einen, der hohe in einen zweiten. Damit reichen zwei Kanäle für gut fünfundsechzigtausend unterscheidbare Flächen, weit mehr als je gebraucht wird. Der Alphakanal ist für diesen Zweck untauglich, weil Bildpipelines ihn mit Vormultiplikation und Farbraumumrechnungen verändern dürfen, ohne dass das als Fehler gilt.
Der Palettenstreifen und der Shader
Neben der Indexkarte liegt ein zweites, lächerlich kleines Bild: ein Streifen von vielleicht zwölf oder vierundzwanzig Pixeln Breite und einem Pixel Höhe, in dem jedes Pixel genau einen Farbton der Palette enthält. Farbe Nummer sieben steht an Position sieben. Der gesamte Farbvorrat eines Bildes ist damit ein paar Dutzend Byte groß.
Das dritte Stück ist der Zustand: eine schlichte Liste, ein Eintrag pro Fläche, in dem steht, ob diese Fläche bereits gefüllt ist. Aus diesen drei Teilen setzt ein Fragmentshader auf der Grafikeinheit das sichtbare Bild bei jedem Einzelbild neu zusammen. Für jedes Pixel liest er die Flächennummer aus der Indexkarte, schlägt im Zustand nach, ob diese Fläche gefüllt ist, und gibt entweder die zugehörige Farbe aus dem Palettenstreifen aus oder Weiß mit der Umrisslinie. Das ist wenig Arbeit pro Pixel, und die Grafikeinheit erledigt Millionen davon parallel.
Aus dieser Konstruktion folgt unmittelbar, warum es keine weichen Kanten gibt. Ein kantengeglättetes Pixel wäre ein Pixel, das anteilig zu zwei Flächen gehört, und die Indexkarte kann pro Pixel nur eine Nummer aufnehmen. Mehrdeutigkeit ist hier keine hübschere Darstellung, sondern eine falsche Antwort.
Was dabei nebenbei billig wird
Weil das Bild jederzeit neu berechnet wird, muss es nie gespeichert werden. Ein Spielstand besteht aus der Zustandsliste, also aus wenigen hundert bis wenigen tausend Byte, unabhängig davon, wie groß das Motiv ist. Ein Zurücknehmen ist ein einzelner geänderter Eintrag. Und ein Wechsel des gesamten Farbschemas ist ein Austausch des Palettenstreifens, während Indexkarte und Fortschritt unverändert bleiben.
Die Ziffern selbst sind in dieser Architektur der unbequemste Teil, weil sie weder in die Indexkarte noch in die Palette passen. Sie werden entweder als eigene Ebene mitgeliefert oder zur Laufzeit an einer vorab berechneten Position in die jeweilige Fläche gezeichnet. Wie diese Position bestimmt wird, ist ein eigenes und überraschend widerspenstiges Problem.
Häufige Fragen
Warum liegen Ausmalbilder nicht als Vektorgrafik vor?
Weil die entscheidende Operation die Trefferabfrage ist und Vektoren dafür ungeeignet sind: Jeder Tipp bräuchte Punkt-in-Polygon-Tests über tausende Pfade. Eine Indexkarte beantwortet dieselbe Frage mit einem einzigen Speicherzugriff, unabhängig von der Zahl der Flächen.
Was ist eine Indexkarte in diesem Zusammenhang?
Ein zweites Bild in derselben Auflösung wie das sichtbare, dessen Pixelwerte keine Farben sind, sondern Flächennummern. Es wird nie angezeigt. Aus ihm ergibt sich sowohl, welche Fläche getroffen wurde, als auch, welche Pixel beim Füllen ihre Farbe wechseln.
Warum sehen die Kanten so hart aus?
Weil jedes Pixel der Indexkarte genau einer Fläche zugeordnet sein muss. Kantenglättung würde bedeuten, dass ein Pixel anteilig zu zwei Flächen gehört, und dafür ist in dieser Datenstruktur kein Platz. Die harten Kanten sind eine Folge des Aufbaus, kein Qualitätsmangel.
Auf einer echten Fläche ausprobieren
Numbrush ist Malen nach Zahlen für Erwachsene: Mandalas, Rosettenfenster und geometrische Ornamentik, zwölf Farben pro Bild, eine Lupe für die engen Stellen und keinerlei Strafe für einen danebengesetzten Tipp. Kostenlos, offline, ohne Werbung und ohne Konto.