Алгоритм Ву

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

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

[править] Алгоритм

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

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

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

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

[править] Литература

• Майкл Абраш (июнь 1992). "Быстрое сглаживание". Dr. Dobb's Journal 17 (6): 139(7).
• У Сяолинь (июль 1991). "Эффективная техника сглаживания". Computer Graphics 25 (4): 143–152. ISBN 0-89791-436-8.

[править] См. также

• ClearType