Алгоритм Ву

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Розподілення інтенсивності піксела в залежності від відстані до ідеальної лінії

Алгоритм Ву — алгоритм для малювання ліній зі згладжуванням, був представлений в статті Ефективна техніка згладжування у липневому випуску видання 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.

Див. також[ред.ред. код]

Література[ред.ред. код]