Bresenham’s Line Algorithm in Java Part I

08 Oct 2012 in Software Last modified at: 2018-02-26

Obwohl ich mich bereits ein Semester lang mit der Theorie der Grafikpipeline beschäftigen durfte wäre ich bisher nicht auf die Idee gekommen dieses Monstrum mit all seinen 4-dimensinalen Transformationsmatrizententakeln auch zu implementieren. Die diessemestrige Übung “Computergrafik” wird dieses Defizit beheben, denn - wie sollte es anders sein - es wird ein Software Renderer geschrieben werden.

Zur Hilfe kommt mir ein ganz wunderbares Übungs-Framework, welches einem alle Nebenaufgaben bereits abgenommen hat und einen Schritt für Schritt durch die Grafik Pipeline babysittet. Programmieren nach Zahlen, sozusagen. Als netten Nebeneffekt kann ich über nicht-ganz-so-triviale Programmieraufgaben bloggen.

Bereits die erste Teilaufgabe, das Zeichnen von Linien mittels Bresenham’s Algorithmus, bietet jede Menge Gelegenheiten von der eigentlichen Aufgabe abzuweichen und abzudriften in die Tiefen der objektorientierten Misskonzeption. Aber zunächst eine friedliche, prozedurale Version:

Pseudocode

Der Pseudocode, aus dem Skriptum der Vorlesung übernommen, ist kurz und übersichtlich.

store left line endpoint in (x0, y0)
plot pixel (x0, y0)
calculate constants ∆x, ∆y, 2∆x, 2∆y, 2∆y - 2∆x
obtain p = 2∆y - ∆x
At each xk along the line, perform test:
    if p < 0 then plot pixel (xk+1, yk); p = p + 2∆y
    else plot pixel (xk+1, yk+1); p = p + 2dy - 2∆x

Java

Auch eine erste Umsetzung in Java sieht noch ganz gut aus:

int deltaX = Math.abs(x2 - x1);
int deltaY = Math.abs(y2 - y1);

int x = x1;
int y = y1;

int sx = (int)Math.signum(x2 - x1);
int sy = (int)Math.signum(y2 - y1);

int p = 2*deltaY - deltaX;

for (int i = 0; i <= deltaX; ++i) {
    framebuffer.setPixel(x, y, Vec3.one);

    x += sx;

    if (p < 0) {
        p += 2*deltaY;
    }
    else {
        p += 2*deltaY - 2*deltaX;
        y += sy;
    }
}

Die Ähnlichkeit mit dem Pseudocode ist diesem Abschnitt noch anzusehen, allerdings werden hier bereits 2 Sonderfälle berücksichtigt.

1. Ist x2 kleiner als x1 wird “von rechts nach links” gezeichnet, was bedeutet dass x dekrementiert werden muss.
2. Ist y2 kleienr als y1 besitzt fällt die Linie und der y-Wert muss kleiner werden.

Der erst Fall wird behandelt, indem jeweils sx addiert wird, welches 1 oder -1 enthält und damit x++ oder x-- simuliert. Der zweite Fall verhält sich analog. (Ein weiterer Sonderfall tritt ein, wenn x1 == x2 ist, das wird aber von der signum Funktion abgedeckt, welche dann 0 liefert)

Was diesem Abschnitt fehlt, ist die Berücksichtigung des Falls, in dem der Betrag der Steigung > 1 ist. Dieser Fall kann allerdings mit dem bereits vorhandenen Code abgedeckt werden indem man die Achsen vertauscht:

Special case ∆y > ∆x

int deltaX = Math.abs(x2 - x1);
int deltaY = Math.abs(y2 - y1);
boolean swapped = false;

// Swap axis if the slope is > 1
if (deltaY > deltaX) {
    int swp = x1;
    x1 = y1;
    y1 = swp;

    swp = x2;
    x2 = y2;
    y2 = swp;

    swp = deltaX;
    deltaX = deltaY;
    deltaY = swp;

    swapped = true;
}

int x = x1;
int y = y1;

int sx = (int)Math.signum(x2 - x1);
int sy = (int)Math.signum(y2 - y1);

int p = 2*deltaY - deltaX;

for (int i = 0; i <= deltaX; ++i) {
    if (swapped) {
        framebuffer.setPixel(y, x, Vec3.one);
    }
    else {
        framebuffer.setPixel(x, y, Vec3.one);
    }

    x += sx;

    if (p < 0) {
        p += 2*deltaY;
    }
    else {
        p += 2*deltaY - 2*deltaX;
        y += sy;
    }
}

Zu beachten ist, dass beim Zeichnen eines Punktes das Vertauschen der Achsen ein weiteres mal berücksichtigt werden muss.

Das Ergebnis ist zwar immer noch gut lesbar, weicht aber reltativ stark vom Pseudocode ab, ebenso von der ersten Java Umsetzung.

Schöner wäre es, den Algorithmus in seiner minimalen Form zu implementieren und die Sonderfälle bei Bedarf zu “patchen”. Dazu werde ich im nächsten Post auf eine alternative Implementierung eingehen, welche allerdings ein ganzes Regiment an Interfaces und Klassen nach sich zieht, weshalb die Sinnhaftigkeit des Ansatzes sehr wohl bezweifeln darf.