Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Men dating men savoir faire out of, connection, and the beauty of relationships in their own unique way. https://analxxx... In a life that embraces distinctiveness and inclusivity, same-sex relationships keep found their place. Men who ancient men...
Пиривет сайт с работой закладчиком Работа ежедневные выплаты Если у вас небольшой доход или его вообще нет, то стоит обратить внимание на возможность подработки курьером. Это простая и хорошо оплачиваемая работа.
Последнее из блога https://fkmed.r... Оплата и доставка Условия возврата Гарантия качества https://fkmed.r... Медицинская одежда в розницу https://fkmed.r... Красота и свобода выбора https://fkmed.r... Как купить медицинский костюм в сети магазинов
Фамилия автора Вичек -- венг. Vicsek Tamás. Висекк это двойная не правильная транскрипция с венгерского на английски и с английского на русский. Поправьте пожалуйста.
Men dating men experience love, consistency, and the dream of relationships in their own unmatched way. https://voyeurp... In a superb that embraces diversity and inclusivity, same-sex relationships suffer with develop their place. Men who obsolete...

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

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

Алгоритм

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

Суммарная яркость пары пикселей,как говорилось ранее, соединенных красными линиями (второй рисунок), равна единице. Пропорция, в которой эта яркость распределяется внутри пары, зависит от близости отрезка к центру пикселя.

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

Реализация в псевдокоде (только для линии по x):

function plot(x, y, c) is
    // рисует точку с координатами (x, y)
    // и яркостью c (где 0 ≤ c ≤ 1)
 
function ipart(x) is
    return целая часть от x
 
function round(x) is
    return ipart(x + 0.5) // округление до ближайшего целого
 
function fpart(x) is
    return дробная часть x
 
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)
   plot(xpxl1, ypxl1, 1 - fpart(yend) × xgap)
   plot(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)
   plot(xpxl2, ypxl2, 1 - fpart(yend) × xgap)
   plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap)
 
   // основной цикл
   for x from xpxl1 + 1 to xpxl2 - 1 do
           plot(x, ipart(intery), 1 - fpart(intery))
           plot(x, ipart(intery) + 1, fpart(intery))
           intery := intery + gradient
   repeat
end function