Алгоритм линии Xiaolin Wus - Xiaolin Wus line algorithm

Демонстрация алгоритма Xiaolin Wu

Линейный алгоритм Сяолинь Ву является алгоритм для линии сглаживание.

Техника сглаживания

Линейный алгоритм Сяолинь Ву был представлен в статье «Эффективная техника сглаживания» в июльском выпуске журнала 1991 г. Компьютерная графика, а также в статье «Быстрое сглаживание» в июньском номере журнала Журнал доктора Добба.

Алгоритм Брезенхема рисует линии очень быстро, но не выполняет сглаживание. Кроме того, он не может обрабатывать любые случаи, когда конечные точки линии не лежат точно в целых точках пиксельной сетки. Наивный подход к сглаживанию линии занял бы очень много времени. Алгоритм Ву сравнительно быстр, но все же медленнее, чем алгоритм Брезенхема. Алгоритм состоит из рисования пар пикселей, охватывающих линию, каждый из которых окрашен в соответствии с его расстоянием от линии. Пиксели на концах строк обрабатываются отдельно. Строки длиной менее одного пикселя обрабатываются как особый случай.

Расширение алгоритма рисования круга было представлено Сяолинь Ву в книге Графика Самоцветы II. Подобно тому, как алгоритм рисования линий является заменой алгоритма рисования линий Брезенхэма, алгоритм рисования кругов заменяет алгоритм рисования кругов Брезенхема.

Алгоритм

функция участок(Икс, у, c) является    участок то пиксель в (Икс, у) с яркость c (куда 0 ≤ c ≤ 1)// целая часть xфункция ипарт(Икс) является    возвращаться этаж(Икс)функция круглый(Икс) является    возвращаться ипарт(Икс + 0.5)// дробная часть xфункция fpart(Икс) является    возвращаться Икс - этаж(Икс)функция rfpart(Икс) является    возвращаться 1 - fpart(Икс)функция drawLine(x0,y0,x1,y1) является    логический отвесный := пресс(y1 - y0) > пресс(x1 - x0)        если отвесный тогда        замена(x0, y0)        замена(x1, y1)    конец если    если x0 > x1 тогда        замена(x0, x1)        замена(y0, y1)    конец если        dx := x1 - x0    dy := y1 - y0    градиент := dy / dx    если dx == 0.0 тогда        градиент := 1.0    конец если    // обрабатываем первую конечную точку    xend := круглый(x0)    конец := y0 + градиент * (xend - x0)    xgap := rfpart(x0 + 0.5)    xpxl1 := xend // это будет использоваться в основном цикле    ypxl1 := ипарт(конец)    если отвесный тогда        участок(ypxl1,   xpxl1, rfpart(конец) * xgap)        участок(ypxl1+1, xpxl1,  fpart(конец) * xgap)    еще        участок(xpxl1, ypxl1  , rfpart(конец) * xgap)        участок(xpxl1, ypxl1+1,  fpart(конец) * xgap)    конец если    интерьер := конец + градиент // первое Y-пересечение основного цикла        // обрабатываем вторую конечную точку    xend := круглый(x1)    конец := y1 + градиент * (xend - x1)    xgap := fpart(x1 + 0.5)    xpxl2 := xend // это будет использоваться в основном цикле    ypxl2 := ипарт(конец)    если отвесный тогда        участок(ypxl2  , xpxl2, rfpart(конец) * xgap)        участок(ypxl2+1, xpxl2,  fpart(конец) * xgap)    еще        участок(xpxl2, ypxl2,  rfpart(конец) * xgap)        участок(xpxl2, ypxl2+1, fpart(конец) * xgap)    конец если        // основной цикл    если отвесный тогда        за Икс из xpxl1 + 1 к xpxl2 - 1 делать           начинать                участок(ипарт(интерьер)  , Икс, rfpart(интерьер))                участок(ипарт(интерьер)+1, Икс,  fpart(интерьер))                интерьер := интерьер + градиент           конец    еще        за Икс из xpxl1 + 1 к xpxl2 - 1 делать           начинать                участок(Икс, ипарт(интерьер),  rfpart(интерьер))                участок(Икс, ипарт(интерьер)+1, fpart(интерьер))                интерьер := интерьер + градиент           конец    конец есликонец функция

Рекомендации

  • Абраш, Майкл (июнь 1992 г.). «Быстрое сглаживание (столбец)». Журнал доктора Добба. 17 (6): 139(7).
  • У, Сяолинь (июль 1991 г.). «Эффективная техника антиалиасинга». Компьютерная графика (издание). 25 (4): 143–152. Дои:10.1145/127719.122734. ISBN  0-89791-436-8.
  • У, Сяолинь (1991). «Быстрая генерация сглаженных кругов». В Джеймсе Арво (ред.). Графика Gems II. Сан-Франциско: Морган Кауфманн. С. 446–450. ISBN  0-12-064480-0.

внешняя ссылка