Xiaolin Wu's line algorithm

from Wikipedia, the free encyclopedia
QS IT
 This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )
Smoothed line from Xiaolin Wu's line algorithm

Xiaolin Wu's line algorithm is an algorithm for displaying lines with antialiasing (anti-aliasing) , first presented in the article An Efficient Antialiasing Technique in the July 1991 issue of Computer Graphics and in the article Fast Antialiasing in Dr. Dobb's Journal , June 1992.

The Bresenham algorithm is particularly fast when displaying lines, but does not support the smoothing of the lines. In addition, only lines whose end point coordinates are integers can be displayed. A naive approach to line smoothing would be extremely slow. Wu's algorithm is comparatively fast, but still slower than the Bresenham algorithm. Wu's algorithm always draws pixels in pairs on each side of the line and colors them according to their distance from the line. The pixels at the line ends and lines with a length shorter than one pixel are treated separately.

An extension of the algorithm for displaying circles was presented by Xiaolin Wu in the book Graphics Gems II . Just like its line algorithm, it is a replacement for an existing Bresenham algorithm . 

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

See also

literature

Web links