Алгоритм Ву

1. Алгоритм Ву

2. Описание

Алгоритм Ву — это алгоритм разложения отрезка в растр со
сглаживанием.
Алгоритм сочетает высококачественное устранение
ступенчатости и скорость, близкую к скорости алгоритма
Брезенхема без сглаживания.

3. Алгоритм

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

4.

На рисунках ниже показано, как мы выбираем из множества
пикселей пары. В нашем случае прямая лежит ближе к оси OX,
чем к OY, поэтому пары состоят из соседних по вертикали
элементов. Если бы прямая была ближе к оси OY, то мы бы
выбирали пары из соседей по горизонтали.
В зависимости от величины ошибки, которая показывает как
далеко ушли пиксели от идеальной линии по неосновной оси,
распределяется интенсивность между этими двумя точками.
Чем больше удалена точка от идеальной линии, тем меньше ее
интенсивность. Значения интенсивности двух пикселей всегда
дают в сумме единицу.

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

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

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

// 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)

8.

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