Алгоритм линии Сяолиня У
 | В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения )
|
Линейный алгоритм Сяолиня У — это алгоритм сглаживания линий .
Метод сглаживания
Алгоритм линий Сяолиня У был представлен в статье «Эффективный метод сглаживания» в июльском номере журнала Computer Graphics за 1991 год , а также в статье «Быстрое сглаживание» в июньском номере журнала Dr. Dobb's Journal за 1992 год .
Алгоритм Брезенхэма рисует линии очень быстро, но не выполняет сглаживание. Кроме того, он не может обрабатывать случаи, когда конечные точки линии не лежат точно на целых точках пиксельной сетки. Наивный подход к сглаживанию линии занял бы очень много времени. Алгоритм Ву сравнительно быстр, но все равно медленнее алгоритма Брезенхэма. Алгоритм состоит из рисования пар пикселей, расположенных по обе стороны линии, каждый из которых окрашен в соответствии с его расстоянием от линии. Пиксели на концах линии обрабатываются отдельно. Линии длиной менее одного пикселя обрабатываются как особый случай.
Расширение алгоритма рисования окружностей было представлено Сяолинем Ву в книге Graphics Gems II . Так же, как алгоритм рисования линий является заменой алгоритма рисования линий Брезенхэма, алгоритм рисования окружностей является заменой алгоритма рисования окружностей Брезенхэма.
Алгоритм
График функции ( x , y , c ) имеет вид начертите пиксель в точке ( x , y ) с яркостью c ( где 0 ≤ c ≤ 1 ) // целая часть xФункция ipart ( x ) — это обратный этаж ( x ) Функция round ( x ) есть вернуть ipart ( x + 0.5 ) // дробная часть xФункция fpart ( x ) — это вернуть x - ipart ( x ) функция rfpart ( x ) — это возврат 1 - fpart ( x ) Функция drawLine ( x0 , y0 , x1 , y1 ) — это булев крутой := abs ( y1 - y0 ) > abs ( x1 - x0 ) если крутой то поменять местами ( x0 , y0 ) своп ( x1 , y1 ) конец, если если х0 > х1, то обмен ( x0 , x1 ) поменять местами ( y0 , y1 ) конец, если дх := х1 - х0 dy := y1 - y0 если dx == 0,0 тогда градиент := 1.0 еще градиент := dy / dx конец, если // обработать первую конечную точку xend := раунд ( x0 ) yend := y0 + градиент * ( xend - x0 ) xgap := rfpart ( x0 + 0.5 ) xpxl1 := xend // это будет использовано в основном цикле ypxl1 := ipart ( yend ) если крутой то участок ( ypxl1 , xpxl1 , rfpart ( yend ) * xgap ) участок ( ypxl1 + 1 , xpxl1 , fpart ( yend ) * xgap ) еще участок ( xpxl1 , ypxl1 , rfpart ( yend ) * xgap ) участок ( xpxl1 , ypxl1 + 1 , fpart ( yend ) * xgap ) конец, если intery := yend + градиент // первое пересечение по оси y для основного цикла // обработать вторую конечную точку xend := раунд ( x1 ) yend := y1 + градиент * ( xend - x1 ) xgap := fpart ( x1 + 0,5 ) xpxl2 := xend //это будет использовано в основном цикле ypxl2 := ipart ( yend ) если крутой то участок ( ypxl2 , xpxl2 , rfpart ( yend ) * xgap ) участок ( ypxl2 + 1 , xpxl2 , fpart ( yend ) * xgap ) еще участок ( xpxl2 , ypxl2 , rfpart ( yend ) * xgap ) участок ( xpxl2 , ypxl2 + 1 , fpart ( yend ) * xgap ) конец, если // основной цикл если крутой то для x от xpxl1 + 1 до xpxl2 - 1 сделать начинать сюжет ( ipart ( intery ) , x , rfpart ( intery )) сюжет ( ipart ( intery ) + 1 , x , fpart ( intery )) интери := интери + градиент конец еще для x от xpxl1 + 1 до xpxl2 - 1 сделать начинать сюжет ( x , ipart ( intery ) , rfpart ( intery )) сюжет ( x , ipart ( intery ) + 1 , fpart ( intery )) интери := интери + градиент конец конец, если конечная функция Ссылки
- Абраш, Майкл (июнь 1992 г.). «Быстрое сглаживание (столбец)». Журнал доктора Добба . 17 (6): 139 (7).
- Wu, Xiaolin (июль 1991). "Эффективный метод сглаживания". ACM SIGGRAPH Computer Graphics . 25 (4): 143– 152. doi :10.1145/127719.122734. ISBN 0-89791-436-8.
- Ву, Сяолинь (1991). «Быстрое создание сглаженных кругов». У Джеймса Арво (ред.). Графические драгоценности II . Сан-Франциско: Морган Кауфманн. стр. 446–450 . ISBN. 0-12-064480-0.
Внешние ссылки
- Домашняя страница Сяолинь У
- Домашняя страница Сяолинь У в Университете Макмастера
