Линейный алгоритм Xiaolin Wu - это алгоритм линейного сглаживания .
Техника сглаживания
Линейный алгоритм Сяолинь Ву был представлен в статье «Эффективная техника сглаживания» в июльском выпуске журнала Computer Graphics за 1991 год , а также в статье «Быстрое сглаживание» в июньском выпуске журнала доктора Добба 1992 года .
Алгоритм Брезенхема очень быстро рисует линии, но не выполняет сглаживание. Кроме того, он не может обрабатывать любые случаи, когда конечные точки линии не лежат точно в целых точках пиксельной сетки. Наивный подход к сглаживанию линии занял бы очень много времени. Алгоритм Ву сравнительно быстр, но все же медленнее, чем алгоритм Брезенхема. Алгоритм состоит из рисования пар пикселей, охватывающих линию, каждый из которых окрашен в соответствии с его расстоянием от линии. Пиксели на концах строк обрабатываются отдельно. Строки длиной менее одного пикселя обрабатываются как особый случай.
Расширение алгоритма рисования круга было представлено Xiaolin Wu в книге Graphics Gems II . Так же, как алгоритм рисования линий является заменой алгоритма рисования линий Брезенхема, алгоритм рисования кругов заменяет алгоритм рисования кругов Брезенхема.
Алгоритм
Функция участка ( х , у , с ) является участок на пиксель при ( х , у ) с яркостью с ( где 0 ≤ с ≤ 1 )// целая часть х функций параметрического ряда ( х ) является возврат пола ( х )функция round ( x ) - это return ipart ( x + 0.5 )// дробная часть х функции fpart ( х ) является возвращение х - пол ( х )Функция rfpart ( х ) является возврат 1 - fpart ( х )функция drawLine ( x0 , y0 , x1 , y1 ) является логической крутой : = abs ( y1 - y0 ) > abs ( x1 - x0 ) если крутой, то swap ( x0 , y0 ) swap ( x1 , y1 ) end if if x0 > x1 then swap ( x0 , x1 ) swap ( y0 , y1 ) end if dx : = x1 - x0 dy : = y1 - y0 gradient : = dy / dx if dx == 0.0 then gradient : = 1.0 end if // обрабатываем первую конечную точку xend : = round ( x0 ) yend : = y0 + gradient * ( xend - x0 ) xgap : = rfpart ( x0 + 0.5 ) xpxl1 : = xend // это будет использоваться в основном цикле ypxl1 : = part ( yend ) если крутой, то plot ( ypxl1 , xpxl1 , rfpart ( yend ) * xgap ) plot ( ypxl1 + 1 , xpxl1 , fpart ( yend ) * xgap ) else plot ( xpxl1 , ypxl1 , rfpart ( yend ) * xgap ) plot ( xpxl1 , ypxl1 + 1 , fpart ( yend ) * xgap ) end if intery : = yend + gradient // первое пересечение по оси Y для основного цикла // обрабатываем вторую конечную точку xend : = round ( x1 ) yend : = y1 + gradient * ( xend - x1 ) xgap : = fpart ( x1 + 0.5 ) xpxl2 : = xend // это будет использоваться в основном цикле ypxl2 : = part ( yend ) если круто, то plot ( ypxl2 , xpxl2 , rfpart ( yend ) * xgap ) plot ( ypxl2 + 1 , xpxl2 , fpart ( yend ) * xgap ) else plot ( xpxl2 , ypxl2 , rfpart ( yend ) * xgap ) plot ( xpxl2 , ypxl2 + 1 , fpart ( yend ) * xgap ) конец, если // основной цикл, если крутой, то для x от xpxl1 + 1 до xpxl2 - 1 действительно начинаем график ( ipart ( intery ) , x , rfpart ( intery )) plot ( ipart ( intery ) + 1 , x , fpart ( intery )) intery : = intery + gradient end else для x от xpxl1 + 1 до xpxl2 - 1 do begin plot ( x , ipart ( intery ) , rfpart ( intery )) plot ( x , ipart ( intery ) + 1 , fpart ( intery )) intery : = intery + gradient end end if end функция
Рекомендации
- Абраш, Майкл (июнь 1992 г.). «Быстрое сглаживание (столбец)» . Журнал доктора Добба . 17 (6): 139 (7).
- У, Сяолинь (июль 1991 г.). «Эффективная техника сглаживания» . Компьютерная графика . 25 (4): 143–152. DOI : 10.1145 / 127719.122734 . ISBN 0-89791-436-8.
- У, Сяолинь (1991). «Быстрая генерация сглаженных кругов». В Джеймсе Арво (ред.). Graphics Gems II . Сан-Франциско: Морган Кауфманн. С. 446–450. ISBN 0-12-064480-0.