Der Bresenham-Linienalgorithmus

Eine gerade Linie auf Papier ist trivial — auf einem Pixelraster nicht. Pixel sitzen auf ganzzahligen Koordinaten, aber eine Linie von (0, 0) nach (5, 3) hat eine Steigung von 0.6, und außer den Endpunkten liegt kein Pixel exakt auf diesem Pfad. Irgendetwas muss für jede Spalte entscheiden, welche Zeile am nächsten liegt.

Der naive Ansatz wertet y = mx + b für jedes x mit Gleitkomma-Arithmetik aus. Das funktioniert, aber Gleitkomma-Multiplikation und -Rundung sind langsamer, als es für eine Operation nötig wäre, die pro Frame Millionen Mal laufen kann. Bresenhams Algorithmus, 1965 von Jack Bresenham bei IBM veröffentlicht, liefert das identische Ergebnis nur mit Ganzzahl-Addition, -Subtraktion und Bit-Shifts — keine Multiplikation, keine Division, keine Rundung.

Die Idee

Betrachte eine Linie mit einer Steigung zwischen 0 und 1, von (x0, y0) nach (x1, y1). Da die Steigung flach ist, rückt die Linie bei jedem Schritt um genau ein Pixel in x vor, und y bleibt entweder gleich oder erhöht sich um eins. Der Algorithmus muss den reellwertigen y-Wert nie kennen — er muss bei jedem Schritt nur entscheiden, ob y erhöht wird oder nicht.

Diese Entscheidung wird über einen Fehlerterm getroffen: eine laufende Summe, wie weit die ideale (reellwertige) Linie von der aktuellen Pixelzeile abgedriftet ist. Jeder Schritt addiert die Steigung zum Fehler. Übersteigt der Fehler ein halbes Pixel, wechselt der Algorithmus in die nächste Zeile und zieht ein volles Pixel wieder ab. All das lässt sich mit Ganzzahlen ausdrücken, indem man den Fehlerterm mit 2 * dx skaliert — daher kommen die charakteristischen Konstanten 2*dy und 2*dy - 2*dx in der Implementierung.

Implementierung

Die Version unten behandelt alle Steigungen und Richtungen, indem zuerst der Oktant normalisiert wird: Sie vertauscht x/y bei steilen Linien und die Endpunkte bei Linien, die von rechts nach links verlaufen, und schreitet danach immer nach demselben einfachen Muster voran.

#include "plot.hpp"
#include <stdlib.h>

void bresenham_line(int x0, int y0, int x1, int y1) {
    int steep = abs(y1 - y0) > abs(x1 - x0);

    if (steep) {
        int tmp = x0; x0 = y0; y0 = tmp;
        tmp = x1; x1 = y1; y1 = tmp;
    }
    if (x0 > x1) {
        int tmp = x0; x0 = x1; x1 = tmp;
        tmp = y0; y0 = y1; y1 = tmp;
    }

    int dx = x1 - x0;
    int dy = abs(y1 - y0);
    int error = dx / 2;
    int ystep = (y0 < y1) ? 1 : -1;
    int y = y0;

    for (int x = x0; x <= x1; x++) {
        if (steep) {
            PlotPixel(y, x);
        } else {
            PlotPixel(x, y);
        }
        error -= dy;
        if (error < 0) {
            y += ystep;
            error += dx;
        }
    }
}

void frame() {
    PlotBackground(250, 250, 250);
    PlotColor(30, 100, 200);
    bresenham_line(50, 400, 600, 80);
}

frame() ruft den Algorithmus einfach mit PlotPixel als Zeichenprimitive auf, statt mit printf. Bearbeite den Code oben und drücke "Compile & Run", um selbst andere Endpunkte auszuprobieren.

error ist hier der klassische Bresenham-Fehlerterm, um den Faktor zwei kleiner skaliert als in manchen Lehrbuchversionen (dx/2 statt 2*dy - dx) — beide sind äquivalent, diese Form vermeidet nur eine Multiplikation zu Beginn.

Schritt für Schritt durchgerechnet

Für die Linie von (0, 0) nach (5, 3): dx = 5, dy = 3, ystep = 1, error startet bei 2.

Die resultierenden Pixel sind (0,0) (1,1) (2,1) (3,2) (4,2) (5,3) — eine vernünftige treppenförmige Annäherung an die ideale Linie, nie mehr als ein halbes Pixel vom wahren Pfad entfernt.

Warum das immer noch wichtig ist

Moderne GPUs rasterisieren Dreiecke, nicht einzelne Linien, und verwenden ihre eigenen Festkomma-Rasterisierungsregeln. Aber Bresenhams Algorithmus — und seine Erweiterungen für Kreise und allgemeine Kegelschnitte — taucht überall dort auf, wo Linien ohne GPU gezeichnet werden müssen: Terminal- UIs, eingebettete Displays, Plotting-Bibliotheken, Retro-Spiele und jeder Software-Rasterizer, der zu Lernzwecken oder für eingeschränkte Hardware geschrieben wird. Es ist außerdem ein gutes Beispiel für einen wiederkehrenden Trick in Low-Level-Grafikcode: eine reellwertige Berechnung durch eine äquivalente Ganzzahl-Berechnung zu ersetzen, indem man den akkumulierten Fehler statt des Werts selbst verfolgt.

Fazit

Bresenhams Algorithmus verwandelt die Frage "welches Pixel liegt am nächsten an dieser Linie" in einen laufenden Ganzzahl-Vergleich, der pro Schritt nur eine Addition und gelegentlich eine Subtraktion aktualisiert. Es ist ein kleines Stück Code, aber ein gutes Beispiel dafür, wie viel man gewinnen kann, wenn man vor dem Schreiben der Schleife die richtige Darstellung für ein Problem wählt.