Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Ву

Распределение интенсивности пикселя в зависимости от расстояния до идеальной линии

это алгоритм разложения отрезка в растр со сглаживанием. Был предложен У Сяолинем в статье, опубликованной журналом Computer Graphics в июле 1991 года. Алгоритм сочетает высококачественное устранение ступенчатости и скорость, близкую к скорости алгоритма Брезенхема без сглаживания.

Алгоритм

Горизонтальные и вертикальные линии не требуют никакого сглаживания, поэтому их рисование выполняется отдельно. Для остальных линий алгоритм Ву проходит их вдоль основной оси, подбирая координаты по неосновной оси аналогично алгоритму Брезенхема. Отличие состоит в том, что в алгоритме Ву на каждом шаге устанавливается не одна, а две точки. Например, если основной осью является Х, то рассматриваются точки с координатами и . В зависимости от величины ошибки, которая показывает как далеко ушли пиксели от идеальной линии по неосновной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше ее интенсивность. Значения интенсивности двух пикселей всегда дают в сумме единицу, то есть это интенсивность одного пикселя, в точности попавшего на идеальную линию. Такое распределение придаст линии одинаковую интенсивность на всем ее протяжении, создавая при этом иллюзию, что точки расположены вдоль линии не по две, а по одной.

Результат работы алгоритма

Реализация в псевдокоде:

function plot is
    // рисует точку с координатами
    // и яркостью c

function ipart is
    return целая часть от x

function round is
    return ipart // округление до ближайшего целого

function fpart is
    return дробная часть x

function draw_line is
   if x2 < x1 then
       swap
       swap
   end if
  
   dx := x2 - x1
   dy := y2 - y1
   gradient := dy ÷ dx
  
   // обработать начальную точку
   xend := round 
   yend := y1 + gradient ×
   xgap := 1 - fpart
   xpxl1 := xend  // будет использоваться в основном цикле
   ypxl1 := ipart
   plot × xgap)
   plot × xgap)
   intery := yend + gradient // первое y-пересечение для цикла
        
   // обработать конечную точку
   xend := round
   yend := y2 + gradient ×
   xgap := fpart
   xpxl2 := xend  // будет использоваться в основном цикле
   ypxl2 := ipart
   plot × xgap)
   plot × xgap)
     
   // основной цикл
   for x from xpxl1 + 1 to xpxl2 - 1 do
           plot, 1 - fpart)
           plot + 1, fpart)
           intery := intery + gradient
   repeat
end function