Линейный алгоритм Сяолиня Ву

Алгоритм Сяолиня Ву — это алгоритм строк сглаживания .

Техника сглаживания

Линейный алгоритм Сяолиня Ву был представлен в статье «Эффективная техника сглаживания» в июльском выпуске журнала Computer Graphics за 1991 год , а также в статье «Быстрое сглаживание» в июньском выпуске журнала Dr. Dobb's Journal за 1992 год .

Алгоритм Брезенхэма рисует линии чрезвычайно быстро, но не выполняет сглаживание. Кроме того, он не может обрабатывать случаи, когда конечные точки линий не лежат точно в целочисленных точках пиксельной сетки. Наивный подход к сглаживанию линии занял бы чрезвычайно много времени. Алгоритм Ву сравнительно быстр, но все же медленнее алгоритма Брезенхема. Алгоритм состоит в рисовании пар пикселей, расположенных по обе стороны линии, каждый из которых окрашен в соответствии с расстоянием от линии. Пиксели на концах строк обрабатываются отдельно. Линии длиной менее одного пикселя обрабатываются как особый случай.

Расширение алгоритма рисования окружностей было представлено Сяолинем Ву в книге Graphics Gems II . Так же, как алгоритм рисования линий является заменой алгоритма рисования линий Брезенхема, алгоритм рисования кругов является заменой алгоритма рисования кругов Брезенхема.

Алгоритм

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

// integer part of x
function ipart(x) is
    return floor(x)

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

// fractional part of x
function fpart(x) is
    return x - ipart(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

    if dx == 0.0 then
        gradient := 1.0
    else
        gradient := dy / dx
    end if

    // handle first endpoint
    xend := round(x0)
    yend := y0 + gradient * (xend - x0)
    xgap := rfpart(x0 + 0.5)
    xpxl1 := xend // this will be used in the main loop
    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 // first y-intersection for the main loop
    
    // handle second endpoint
    xend := round(x1)
    yend := y1 + gradient * (xend - x1)
    xgap := fpart(x1 + 0.5)
    xpxl2 := xend //this will be used in the main loop
    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
    
    // main loop
    if steep then
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(ipart(intery)  , x, rfpart(intery))
                plot(ipart(intery)+1, x,  fpart(intery))
                intery := intery + gradient
           end
    else
        for x from xpxl1 + 1 to xpxl2 - 1 do
           begin
                plot(x, ipart(intery),  rfpart(intery))
                plot(x, ipart(intery)+1, fpart(intery))
                intery := intery + gradient
           end
    end if
end function

Ссылки

Абраш, Майкл (июнь 1992 г.). «Быстрое сглаживание (столбец)» . Журнал доктора Добба . 17 (6): 139 (7).
Ву, Сяолинь (июль 1991 г.). «Эффективная техника сглаживания» . ACM SIGGRAPH Компьютерная графика . 25 (4): 143–152. дои : 10.1145/127719.122734 . ISBN 0-89791-436-8 .
Ву, Сяолинь (1991). «Быстрое создание сглаженных кругов». У Джеймса Арво (ред.). Графические драгоценности II . Сан-Франциско: Морган Кауфманн. стр. 446–450. ISBN 0-12-064480-0 .

Внешние ссылки