Xiaolin Wus Linienalgorithmus

Xiaolin Wus Linienalgorithmus

🌐 Read in English
📅 20.11.2026 ✍ Andreas Wittmann đŸ‘ïž ... algorithm graphics computer-graphics antialiasing

Bresenhams Linienalgorithmus wĂ€hlt in jeder Spalte das eine Pixel, das der echten Linie am nĂ€chsten liegt, und fĂ€rbt es voll ein. Das ist schnell und in seinem eigenen Sinne exakt, erzeugt bei schrĂ€gen Linien aber sichtbare Treppenstufen, oft „Jaggies“ genannt. Die echte Linie verlĂ€uft meistens zwischen den Pixelmitten, und ein Pixel kann nur an oder aus sein.

Xiaolin Wus Linienalgorithmus, 1991 veröffentlicht, behebt das mit einer einzigen Idee: Statt pro Spalte ein Pixel zu wĂ€hlen, fĂ€rbt er zwei ein und teilt die IntensitĂ€t zwischen ihnen danach auf, wie nah die echte Linie an jedem der beiden verlĂ€uft. Das Auge mittelt die beiden Helligkeiten, und die Linie wirkt glatt — als lĂ€ge sie an einer Position zwischen den Pixeln.

Die Idee

Man nehme eine flache Linie, also eine, die sich stĂ€rker in x als in y bewegt. In einer bestimmten Spalte verlĂ€uft die echte Linie durch eine Höhe wie y = 4,3. Bresenham wĂŒrde auf Zeile 4 runden und sie einfĂ€rben. Wu betrachtet die beiden Zeilen, zwischen denen die Linie verlĂ€uft, 4 und 5, und teilt die Farbe nach Abstand auf:

Der Nachkommaanteil von y entscheidet alles: Das untere Pixel bekommt 1 - Nachkommaanteil, das obere den Nachkommaanteil selbst. FĂŒr jede weitere Spalte wĂ€chst y einfach um die Steigung, genau wie der Fehlerterm in Bresenhams Algorithmus — die ganze Linie braucht also weiterhin nur einen Durchlauf mit einer Addition pro Spalte. Steile Linien werden genauso behandelt, nur mit vertauschtem x und y.

Implementierung

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

// A rectangular area of pixels. Each pixel stores how much of it is
// covered by lines, from 0 (background) to 1 (full line color).
struct Area {
    int x, y;        // position on screen
    int w, h;        // size in pixels
    int scale;       // drawn size of one pixel (1 = real size)
    float cover[200][280];
};

Area zoomBres = {20, 30, 28, 20, 10, {}};
Area zoomWu   = {340, 30, 28, 20, 10, {}};
Area fanBres  = {20, 260, 280, 200, 1, {}};
Area fanWu    = {340, 260, 280, 200, 1, {}};
Area* target;

void clear(Area& a) {
    for (int y = 0; y < a.h; y++)
        for (int x = 0; x < a.w; x++) a.cover[y][x] = 0;
}

// Add coverage c to a pixel. Where lines overlap, the new line covers
// part of whatever is still uncovered.
void plot(int x, int y, double c) {
    if (x < 0 || x >= target->w || y < 0 || y >= target->h) return;
    float& p = target->cover[y][x];
    p = p + (1 - p) * c;
}

// ---- Bresenham's line algorithm, as in the Bresenham article ----

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

    int dx = x1 - x0, 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) plot(y, x, 1); else plot(x, y, 1);
        error -= dy;
        if (error < 0) { y += ystep; error += dx; }
    }
}

// ---- Xiaolin Wu's line algorithm ----

double fpart(double v)  { return v - floor(v); }   // fractional part
double rfpart(double v) { return 1 - fpart(v); }   // 1 - fractional part

void wu_line(double x0, double y0, double x1, double y1) {
    bool steep = fabs(y1 - y0) > fabs(x1 - x0);
    if (steep) { double t = x0; x0 = y0; y0 = t; t = x1; x1 = y1; y1 = t; }
    if (x0 > x1) { double t = x0; x0 = x1; x1 = t; t = y0; y0 = y1; y1 = t; }

    double dx = x1 - x0, dy = y1 - y0;
    double gradient = (dx == 0) ? 1 : dy / dx;

    // Plot along x, but swap back for steep lines.
    #define PLOT(a, b, c) (steep ? plot(b, a, c) : plot(a, b, c))

    // First endpoint: only the part of the pixel the line actually
    // reaches into counts (xgap).
    int xstart = (int)floor(x0 + 0.5);
    double yend = y0 + gradient * (xstart - x0);
    double xgap = rfpart(x0 + 0.5);
    PLOT(xstart, (int)floor(yend),     rfpart(yend) * xgap);
    PLOT(xstart, (int)floor(yend) + 1, fpart(yend) * xgap);
    double y = yend + gradient;

    // Second endpoint, the same way.
    int xstop = (int)floor(x1 + 0.5);
    yend = y1 + gradient * (xstop - x1);
    xgap = fpart(x1 + 0.5);
    PLOT(xstop, (int)floor(yend),     rfpart(yend) * xgap);
    PLOT(xstop, (int)floor(yend) + 1, fpart(yend) * xgap);

    // Everything in between: two pixels per column, split by how close
    // the true line runs to each of them.
    for (int x = xstart + 1; x < xstop; x++) {
        PLOT(x, (int)floor(y),     rfpart(y));
        PLOT(x, (int)floor(y) + 1, fpart(y));
        y += gradient;
    }
    #undef PLOT
}

// ---- Drawing ----

// Mix the line color into the background by the pixel's coverage. In the
// zoomed areas, empty pixels are drawn slightly darker so the pixel grid
// itself is visible.
void draw(const Area& a) {
    int bg = (a.scale == 1) ? 250 : 236;
    for (int y = 0; y < a.h; y++) {
        for (int x = 0; x < a.w; x++) {
            double c = a.cover[y][x];
            PlotColor(bg + (30 - bg) * c, bg + (100 - bg) * c, bg + (200 - bg) * c);
            int sx = a.x + x * a.scale, sy = a.y + y * a.scale;
            if (a.scale == 1) {
                PlotPixel(sx, sy);
            } else {
                PlotFilledRectangle(sx, sy, sx + a.scale - 2, sy + a.scale - 2);
            }
        }
    }
}

void setup() {
    PlotCanvas(640, 480);

    // A fan of lines at real size, every 6 degrees from 0 to 90.
    for (int i = 0; i <= 15; i++) {
        double angle = i * 6 * M_PI / 180;
        double x1 = 5 + 270 * cos(angle), y1 = 195 - 190 * sin(angle);
        target = &fanBres; bresenham_line(5, 195, (int)floor(x1 + 0.5), (int)floor(y1 + 0.5));
        target = &fanWu;   wu_line(5, 195, x1, y1);
    }
}

void frame() {
    // The same slowly rotating line in both zoomed areas.
    double angle = g_current_frame * 0.004;
    double cx = 13.5, cy = 9.5, r = 8.5;
    double x0 = cx - r * cos(angle), y0 = cy - r * sin(angle);
    double x1 = cx + r * cos(angle), y1 = cy + r * sin(angle);

    clear(zoomBres);
    target = &zoomBres;
    bresenham_line((int)floor(x0 + 0.5), (int)floor(y0 + 0.5),
                   (int)floor(x1 + 0.5), (int)floor(y1 + 0.5));
    clear(zoomWu);
    target = &zoomWu;
    wu_line(x0, y0, x1, y1);

    PlotBackground(250, 250, 250);
    draw(zoomBres);
    draw(zoomWu);
    draw(fanBres);
    draw(fanWu);

    PlotColor(40, 44, 52);
    PlotText(20, 8, "Bresenham");
    PlotText(340, 8, "Wu");
    PlotText(20, 238, "Bresenham, real size");
    PlotText(340, 238, "Wu, real size");
}
Open in full editor →

Die obere HĂ€lfte zeigt zweimal dieselbe, langsam rotierende Linie, so vergrĂ¶ĂŸert, dass jedes Pixel sichtbar ist: links mit Bresenhams Algorithmus gezeichnet, genau wie im Bresenham-Artikel, rechts mit dem von Wu. Die untere HĂ€lfte zeichnet einen FĂ€cher von Linien in OriginalgrĂ¶ĂŸe — dort sieht man, wie der Unterschied bei normalem Betrachtungsabstand tatsĂ€chlich aussieht.

Die IntensitĂ€t eines Pixels gibt hier an, wie viel davon die Linie bedeckt, von 0 bis 1. Um daraus eine Farbe zu machen, mischt das Sample die Linienfarbe um genau diesen Anteil in die Hintergrundfarbe. Wo sich zwei Linien kreuzen, etwa nahe der FĂ€chermitte, bedeckt eine neue Linie nur einen Teil dessen, was noch unbedeckt ist — ĂŒberlappende Pixel werden so dunkler, ohne jemals ĂŒber die volle Linienfarbe hinauszugehen.

wu_line selbst folgt der klassischen Formulierung. Die Schleife in der Mitte ist die ganze Idee von oben: zwei PLOT-Aufrufe pro Spalte, mit rfpart(y) und fpart(y) als IntensitÀten. Der zusÀtzliche Code vor der Schleife behandelt die beiden Endpunkte. Eine Linie, die genau in einer Pixelmitte endet, bedeckt dieses Pixel nur zur HÀlfte, daher bekommen die Endpixel nur einen Teil der Farbe (der Faktor xgap). Bei ganzzahligen Endpunkten, wie im FÀcher, ist das immer genau die HÀlfte: Die Enden jeder Linie werden absichtlich mit halber IntensitÀt gezeichnet, nicht aus Versehen.

Wus ursprĂŒngliche Version rechnete mit ganzzahliger Festkomma-Arithmetik, ganz im Geist von Bresenhams Algorithmus. Diese hier verwendet double, damit die Idee leicht nachvollziehbar bleibt.

Der Zusammenhang mit Bresenham

GeprĂŒft an 20.000 zufĂ€lligen Linien gelten fĂŒr die Spalten zwischen den Endpunkten immer drei Eigenschaften:

Der letzte Punkt macht den Zusammenhang sehr direkt: Wus Algorithmus ist Bresenhams Linie plus ein Nachbarpixel pro Spalte, das den Anteil der Farbe erhÀlt, den das Hauptpixel nicht bekommen hat.

Der Kompromiss

Antialiasing tauscht SchĂ€rfe gegen GlĂ€tte. Am deutlichsten wird das, wenn die Linie genau auf halber Höhe zwischen zwei Reihen von Pixelmitten verlĂ€uft. Im ersten Frame der Animation liegt die rotierende Linie fast genau waagrecht bei y ≈ 9,5: Bresenham zeichnet eine scharfe, ein Pixel dicke Linie (mit einer einzigen Stufe in der Mitte, wo seine Rundung von einer Zeile zur nĂ€chsten kippt), wĂ€hrend Wu zwei Reihen mit jeweils fast halber IntensitĂ€t zeichnet, was breiter und blasser wirkt. WĂ€hrend sich die Linie dreht, verschiebt sich die Aufteilung stĂ€ndig, und bei den meisten Winkeln sieht das Ergebnis weit glatter aus als Bresenhams Stufen. Eine perfekt waagrechte oder senkrechte Linie, die genau auf den Pixelmitten liegt, ist mit vollen Pixeln aber immer noch am schĂ€rfsten.

Fazit

Xiaolin Wus Algorithmus behĂ€lt alles, was Bresenhams Algorithmus schnell macht — einen Durchlauf entlang der Linie und eine Addition pro Schritt — und steckt den kleinen Mehraufwand in ein zweites Pixel pro Spalte. Das Ergebnis ist eine Linie, die irgendwo zwischen den Pixeln liegen kann, und das fast ohne Mehrkosten. Deshalb wurde er zu einem der bekanntesten Verfahren, um geglĂ€ttete Linien in Software zu zeichnen.