4. Растровые алгоритмы компьютерной графики. Антиалисинг, сглаживание, дизеринг. Алгоритмы рисования окружности и отрезка. Инкрементный алгоритм Брезенхема. Алгоритмы закрашивания.

Разрешающая способность характеризует расстояние между соседними точками растрового изображения и измеряется обычно в dpi (dots per inch)

Связность – соседство двух пикселей в растровом изображении

Сгла́живание(Антиалисинг) — технология, использующаяся в обработке изображений с целью делать границы кривых линий более гладкими, убирая «зубцы», возникающие на краях объектов. Сглаживание было придумано в 1972 в Массачусетском технологическом институте в Architecture Machine Group, которая позже стала основной частью Media Lab.

Основной принцип сглаживания — использование возможностей устройства вывода для показа оттенков цвета, которым нарисована кривая. В этом случае пиксели, соседние с граничным пикселем изображения, принимают промежуточное значение между цветом изображения и цветом фона, создавая градиент и размывая границу.

) Устранение ступенчатого эффекта – антиалиасинг (antialiasing).

Представим растр в виде плотно прижатых друг к другу квадратных ячеек-пикселей, каждая из которых имеет площадь S. Для того, чтобы растровое изображение линии выглядело более гладким, можно цвет угловых пикселей заменить на некоторый оттенок, промежуточный между цветом объекта и цветом фона. Будем вычислять цвет пропорционально части площади ячейки растра S_x, покрываемой идеальным контуром объекта. Формула для расчёта цвета такова:

(III.1)

З десь C – одна из компонент цвета линии, C_f – аналогичная компонента цвета фона. На рис. показано увеличенное растровое изображение толстой прямой линии с включенным эффектом антиалиасинга, на которое для сравнения наложен идеальный контур исходной линии. Формула применяется ко всем трём компонентам цвета, например, в палитре RGB.

Сглаживающие фильтры (smothing) – предназначены для обработки уже нарисованного изображения. Для сглаживания растровых изображений обычно используют алгоритмы цифровой фильтрации. Один из таких алгоритмов – локальная фильтрация. Она осуществляется путём взвешенного суммирования яркостей пикселей, расположенных в некоторой (квадратной) окрестности текущего обрабатываемого пикселя (окошко, движущееся по растру). Базовую операцию такого фильтра можно представить так:

(III.2)

где P – значение компоненты цвета текущего пикселя, F – новое значение цвета пикселя, К – нормирующий коэффициент, М – двумерный массив коэффициентов, который определяет свойства фильтра (обычно этот массив называют маской). Размеры окна фильтра (j_max-j_min+1) по горизонтали и (i_max-i_min+1) по вертикали. Если в ходе обработки новые значение цвета пикселей записываются в исходный растр, то они вовлекаются в вычисления для очередных пикселей и такую фильтрацию называют рекурсивной. При нерекурсивной фильтрации просчитываются только исходные значения компонент цвета пикселей.

Дизеринг — техника, используемая в компьютерной графике для создания иллюзии глубины цвета для изображений с относительно небольшим количеством цветов в палитре. Отсутствующие цвета составляются из имеющихся путем их «перемешивания» (например, если необходимо получить отсутствующий в палитре фиолетовый цвет, его можно получить, разместив красные и синие пиксели в шахматном порядке).При оптимизации изображений путем уменьшения количества цветов, применение дизеринга приводит к визуальному улучшению изображения, однако для отдельных сжатых форматов (например, PNG), увеличивает его размер. При регулярном расположении одинаковых ячеек образуются паразитные текстуры, муар. Поэтому наряду с ячейками с фиксированным рисунком используются методы частотно-модулированного дизеринга (равномерное псевдослучайное распределение пикселей по ячейке) и диффузного дизеринга (распределение в каждой ячейке создаётся случайным образом).

Эмуляция оттенков цвета – дизеринг (dithering).

Если графическое устройство не способно воссоздавать достаточное количество цветов, тогда используют растрирование – независимо от того, растровое это устройство или нет (как например в полиграфии). Известно, что если смотреть на разноцветные точки с размерами меньше разрешающей способности глаза, то их цвет воспринимается как усреднённый цвет пикселя, создаваемого этими точками (телевидение).

Обычно для дизеринга используют квадратные ячейки размером 2х2 (5 градаций цвета для двухцветного изображения), 3х3 (10 градаций, рис. III.3) и 5х5 (25 градаций). Для ячейки с размерами n x n можно получить n²+1 различных градаций.

Расчёт цвета, соответствующего одной из комбинаций пикселей в ячейке площадью S, имеющих только цвета C₁ и С₂, проводится так:

, (III.3)

где S₁ и S₂ – части площади, занятые пикселями цветов C₁ и C₂ соответственно. Если ячейку представить в виде плотно прижатых квадратных пикселей, то от площадей легко перейдём к количеству пикселей соответствующего цвета в ячейке:

,

г де m₁+m₂ = n². Можно считать, что ячейки размером n x n образовывают растр с разрешающей способностью в n раз меньшей, чем у исходного растра, а глубина цвета возрастает пропорционально n².

В случае вышеприведенного растра на изображении видна достаточно чёткая «квадратная» структура. Для улучшения восприятия можно использовать диагональное расположение ячеек, сдвигая чётные строки ячеек или записывая структуру в квадратные ячейки по примеру рис. III.4.

Однако при регулярном расположении одинаковых ячеек образуются паразитные текстуры, муар, лишние контуры. Поэтому наряду с ячейками с фиксированным рисунком используются методы частотно-модулированного дизеринга (равномерное псевдослучайное распределение пикселей по ячейке) и диффузного дизеринга (распределение в каждой ячейке создаётся случайным образом).

Алгоритм Брезенхэ́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхэмом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.

Инкрементный – т.е. последовательно вычисляются координаты соседних пикселей путём добавления приращений координат. Основной целью для разработки таких алгоритмов было построение циклов вычисления координат на основе только целочисленных операций сложения/вычитания без использования умножения и деления (т.к. вплоть до недавнего времени процессоры выполняли целочисленные операции гораздо быстрее, чем операции с плавающей точкой).

В 1965 году Брезенхемом предложен алгоритм растрового построения отрезка. В алгоритме используется управляющая переменная d_i, которая на каждом шаге пропорциональна разности между s и t (см. рис. III.6). На рисунке приведен i-ый шаг, когда пиксель P_i-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселей должен быть установлен следующим: T_i или S_i.

Е сли s<t, то S_i ближе к отрезку и необходимо выбрать его; в противном случае ближе будет T_i. Другими словами, если s-t<0, то выбирается S_i; в противном случае выбирается T_i.

Изображаемый отрезок проводится из точки (x₁, y₁) в точку (x₂, y₂). Пусть первая точка находится ближе к началу координат, тогда перенесем её в начало координат, и тогда конечная точка окажется в (x, y), где x= x₂ - x₁ , y= y₂ - y₁. Уравнение прямой теперь имеет вид y = xy/x.

Алгоритмы для рисования окружности и эллипса. Для упрощения возьмём эллипс с полуосями a и b, совпадающими с вертикалью и горизонталью экрана. Пусть центр эллипса имеет координаты (0,0). Уравнение такого эллипса имеет вид: b²x² + a²y² – a²b² = 0. Существуют различные алгоритмы рисования эллипса и его частного случая – окружности: по вышеприведенной формуле (нерационально – большое количество действий с вещественными числами, в том числе и операция вычисления квадратного корня) и инкрементные (Брезенхема – используются операции целочисленной арифметики, но алгоритм достаточно сложен). Во всех случаях для уменьшения количества действий следует учесть, что рисовать надо не весь эллипс, а только 1/4 его часть (например, в первом квадранте). Остальные пиксели симметрично расставляются в том же цикле. Для окружности достаточно рисовать лишь её 1/8 (от 90º до 45º), т.е. в одном цикле сразу ставятся восемь пикселей. Рассмотрим самый простой алгоритм рисования окружности – инкрементный алгоритм Хардебурга. Здесь внутри цикла используются операции с вещественными числами, однако по количеству действий алгоритм оптимизирован. Основное уравнение: y² = r² – x² (r – радиус окружности). Постоянно инкрементируется значение х; Зная y² = r² в начальной точке, в каждой следующей точке y² вычисляется так: y² = y² – (2x + 1). Алгоритм выполняет построение 1/8 окружности, т.е. до того как x станет равным y.

Алгоримы закрашивания. Рассмотрим алгоритмы закрашивания произвольного контура, который уже нарисован в растре. Сначала находится пиксель внутри контура фигуры. Цвет этого пикселя изменяем на нужный цвет заполнения. Потом проводится анализ цвета всех соседних пикселей. Если цвет некоторого соседнего пикселя не равен цвету границы контура или цвету заполнения, то цвет этого пикселя изменяется на цвет заполнения.

Простое рекурсивное заполнение. В закрашиваемой области указывается затравочная точка (рис. III.8). Область может содержать полости и быть сколь угодно сложной формы. Необходимо лишь, чтобы внешняя граница и границы полостей были 8-связны и их цвет отличался от цвета заполнения. Этот алгоритм не оптимизирован относительно использования стековой памяти и является одним из самых медленных алгоритмов закрашивания (в среднем только один из четырёх вызовов используется для закрашивания). Алгоритм не может заполнить области, ограниченные цветом заполнения. Можно построить подобный алгоритм и без рекурсии, если вместо стека использовать массивы. Алгоритм закрашивания линиями.

Данный алгоритм получил широкое распространение в компьютерной графике. От приведенного ранее он отличается тем, что на каждом шаге закрашивания рисуется горизонтальная линия, которая размещается между пикселями контура. Данный алгоритм также рекурсивный, однако количество вложенных вызовов гораздо меньше (пропорционально длине линии). Схема алгоритма такова (рис. III.9):

1. Имеется затравочная точка с координатами (x_st, y_st) и начальное направление действия рекурсивных вызовов dir=1. Параметры левой и правой границы вначале совпадают с координатой затравочной точки: x_PL = x_st, x_PR = x_st. Вызывается процедура LineFill, в которой:

2. Находятся x_L и x_R – левая и правая границы, между которыми проводится текущая горизонтальная линия.

3. Делается приращение у=у+dir и, между x_L и x_R, анализируется цвет пикселей над линией. Если он не совпадает с цветом заполнения, процедура LineFill вызывается рекурсивно с dir = 1 и x_PL = x_L, x_PR = x_R.

4. Делается приращение y=y–dir и, начиная от x_L до предыдущего значения x_PL анализируется цвет пикселей под линией. Если цвет пикселя отличается от цвета заполнения, процедура вызывается рекурсивно с dir = –1 и x_PL = x_L, x_PR = x_R.

5. Продолжая по той же горизонтали от предыдущего x_PR до x_R анализируется цвет под линией. Если цвет какого-либо пикселя отличается от цвета заполнения, процедура вызывается рекурсивно с dir = –1 и x_PL = x_L, x_PR = x_R.

рисование окружностей и эллипсов

void Circle(int Xc,int Yc,int radius,int c)

{ int x,y,d;

d = 3 - ( radius << 1);

x = 0; y = radius;

While ( x < y ) { Set8Pixels( Xc, Yc, x, y, c );

If ( d > 0 ) { d = d + ( x << 2 ) + 6; }

else { d = d + ( (x-y) << 2 ) + 10; y--; } x++; } }

5.Кривые в компьютерной графике. Параметрическое представление. Кривые Безье и их свойства. Кусочно-полиномиальные кривые: B-сплайн, рациональный B-сплайн, ?-сплайн, NURBS: свойства и применение. Фрактальные кривые.

Параметрически заданной кривой называется множество точек M(x,y,z), координаты которых определяются соотношениями x = x(t), y = y(t), z = z(t), t=[0,1].Кривая называется регулярной, если в каждой точке кривой существует касательная, положение которой меняется непрерывно вдоль кривой.