Xiaolin Wus Linien-Algorithmus

Xiaolin Wus Linien-Algorithmus ist ein Algorithmus für das Darstellen von Linien mit Antialiasing (Kantenglättung), erstmals vorgestellt im Artikel An Efficient Antialiasing Technique in der Ausgabe von Computer Graphics im Juli 1991 sowie im Artikel Fast Antialiasing in Dr. Dobb’s Journal vom Juni 1992.

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Geglättete Linie aus Xiaolin Wu’s Linien-Algorithmus

Der Bresenham-Algorithmus ist bei der Darstellung von Linien zwar besonders schnell, unterstützt aber nicht die Glättung der Linien. Außerdem können nur Linien dargestellt werden, deren Endpunkt-Koordinaten ganzzahlig sind. Ein naiver Ansatz der Linienglättung wäre extrem langsam. Wus Algorithmus ist vergleichsweise schnell, aber immer noch langsamer als der Bresenham-Algorithmus. Wus Algorithmus zeichnet Pixel immer paarweise auf je einer Seite der Linie und färbt sie nach ihrem Abstand von der Linie. Gesondert behandelt werden die Pixel an den Linienenden sowie Linien mit einer Länge kürzer als ein Pixel.

Eine Erweiterung des Algorithmus zum Darstellen von Kreisen wurde von Xiaolin Wu im Buch Graphics Gems II vorgestellt. Genau wie sein Linien-Algorithmus ist er ein Ersatz eines bereits existierenden Algorithmus von Bresenham.

function plot(x, y, c) is
    plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)

// Ganzzahliger Teil von x
function ipart(x) is
    return int(x)

function round(x) is
    return ipart(x + 0.5)

// Bruchteil von x
function fpart(x) is
    if x < 0
        return 1 - (x - floor(x))
    // else:
    return x - floor(x)

function rfpart(x) is
    return 1 - fpart(x)

function drawLine(x0,y0,x1,y1) is
    boolean steep := abs(y1 - y0) > abs(x1 - x0)

    if steep then
        swap(x0, y0)
        swap(x1, y1)
    end if
    if x0 > x1 then
        swap(x0, x1)
        swap(y0, y1)
    end if

    dx := x1 - x0
    dy := y1 - y0
    gradient := dy / dx

    // Vorgehen fuer ersten Endpunkt
    xend := round(x0)
    yend := y0 + gradient * (xend - x0)
    xgap := rfpart(x0 + 0.5)
    xpxl1 := xend // fuer die Hauptschleife
    ypxl1 := ipart(yend)
    if steep then
        plot(ypxl1,   xpxl1, rfpart(yend) * xgap)
        plot(ypxl1+1, xpxl1,  fpart(yend) * xgap)
    else
        plot(xpxl1, ypxl1  , rfpart(yend) * xgap)
        plot(xpxl1, ypxl1+1,  fpart(yend) * xgap)
    end if
    intery := yend + gradient // erste y-Koordinate fuer die Hauptschleife

    // Vorgehen fuer ersten Endpunkt
    xend := round(x1)
    yend := y1 + gradient * (xend - x1)
    xgap := fpart(x1 + 0.5)
    xpxl2 := xend // fuer die Hauptschleife
    ypxl2 := ipart(yend)
    if steep then
        plot(ypxl2  , xpxl2, rfpart(yend) * xgap)
        plot(ypxl2+1, xpxl2,  fpart(yend) * xgap)
    else
        plot(xpxl2, ypxl2,  rfpart(yend) * xgap)
        plot(xpxl2, ypxl2+1, fpart(yend) * xgap)
    end if

    // Hauptschleife
    for x from xpxl1 + 1 to xpxl2 - 1 do
        begin
            if steep then
                plot(ipart(intery)  , x, rfpart(intery))
                plot(ipart(intery)+1, x,  fpart(intery))
            else
                plot(x, ipart(intery),  rfpart(intery))
                plot(x, ipart(intery)+1, fpart(intery))
            end if
            intery := intery + gradient
        end
end function

Siehe auch

Rasterung von Linien

Literatur

Abrash, Michael: Fast Antialiasing (Column). In: Dr. Dobb’s Journal. Band 17, Nr. 6, Juni 1992, S. 139(7) (gamedev.net).
Xiaolin Wu: An Efficient Antialiasing Technique. In: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques (= SIGGRAPH '91). ACM, New York, NY, USA 1991, ISBN 0-89791-436-8, S. 143–152, doi:10.1145/122718.122734 (acm.org [abgerufen am 3. August 2016]).
Wu, Xiaolin: Graphics Gems II. Hrsg.: James Arvo. Morgan Kaufmann, San Francisco 1991, ISBN 0-12-064480-0, Fast Anti-Aliased Circle Generation, S. 446–450.

Weblinks