Алгоритм Ву

Демонстрація алгоритму Ву. Артефакти стиснення в стандарті jpeg з його допомогою можливо зробити «чесними».

Малювання лінії зі згладжуванням із використання алгоритму Ву

Алгоритм Ву — алгоритм для малювання ліній зі згладжуванням, був представлений в статті Ефективна техніка згладжування у липневому випуску видання Computer Graphics, а також в статті Швидке згладжування в червні 1992 в випуску Dr. Dobb's Journal.

Алгоритм Брезенхейма малює відрізок дуже швидко, але він не виконує згладжування. В додаток, він не може обробити ситуацію коли кінцеві точки мають не цілочисельні координати. Наївна спроба малювання зі згладжуванням вимагає багато часу, в той час як алгоритм Ву дуже швидкий (хоча й повільніший за алгоритм Брезенхейма).

Алгоритм

Горизонтальні та вертикальні лінії не вимагають ніякого згладжування, через це їх малювання виконується окремо. Для решти ліній алгоритм Ву проходить їх уздовж основної осі, підбираючи координати за неосновною віссю аналогічно з алгоритмом Брезенхейма. Відмінність складається в тому, що в алгоритмі Ву на кожному кроці встановлюється не одна, а дві точки. Наприклад, якщо основної віссю є Х, тоді розглядаються точки з координатами (х, у) і (х, у+1). В залежності від величини похибки, яка вказує як далеко відійшли піксели від ідеальної лінії за неосновною віссю, розподіляється інтенсивність між цими двома точками. Чим більше віддалена точка від ідеальної лінії, тим менша її інтенсивність. Значення інтенсивності двох пікселів завжди в сумі дає одиницю, тобто це є інтенсивність одного піксела, який точно потрапив на ідеальну лінію. Таке розподілення придасть лінії однакову інтенсивність по всій її довжині, створюючи при цьому ілюзію, що точки розташовані уздовж лінії не по дві, а по одній.

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

function ipart(x) is
    return integer part of x

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

function fpart(x) is
    return fractional part of x

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

function drawLine(x1,y1,x2,y2) is
    dx = x2 - x1
    dy = y2 - y1
    if abs(dx) < abs(dy) then			
      swap x1, y1
      swap x2, y2
      swap dx, dy
    end if
    if x2 < x1
      swap x1, x2
      swap y1, y2
    end if
    gradient = dy / dx
    
    // handle first endpoint
    xend = round(x1)
    yend = y1 + gradient * (xend - x1)
    xgap = rfpart(x1 + 0.5)
    xpxl1 = xend  // this will be used in the main loop
    ypxl1 = ipart(yend)
    plot(xpxl1, ypxl1, rfpart(yend) * xgap)
    plot(xpxl1, ypxl1 + 1, fpart(yend) * xgap)
    intery = yend + gradient // first y-intersection for the main loop
    
    // handle second endpoint
    xend = round (x2)
    yend = y2 + gradient * (xend - x2)
    xgap = fpart(x2 + 0.5)
    xpxl2 = xend  // this will be used in the main loop
    ypxl2 = ipart (yend)
    plot (xpxl2, ypxl2, rfpart (yend) * xgap)
    plot (xpxl2, ypxl2 + 1, fpart (yend) * xgap)
    
    // main loop
    for x from xpxl1 + 1 to xpxl2 - 1 do
        plot (x, ipart (intery), rfpart (intery))
        plot (x, ipart (intery) + 1, fpart (intery))
        intery = intery + gradient
end function

Зауваження: якщо на початку виявляється, що abs(dx) < abs(dy), тоді всі точки мають відображатись з переставленими x і y.

Див. також

Література

Майкл Абраш (червень 1992). Швидке згладжування. Dr. Dobb's Journal. 17 (6): 139(7). Архів оригіналу за 1 березня 2010. Процитовано 31 липня 2010.
Ву Сяолінь (липень 1991). Ефективна техніка згладжування. Computer Graphics. 25 (4): 143—152. ISBN 0-89791-436-8.