- •Алгоритмы компьютерной графики
- •1 . Генерация векторов
- •1.1. Цифровой дифференциальный анализатор (цда)
- •1.2. Алгоритм Брезенхема
- •З адание на лабораторную работу № 1 "Генерация векторов"
- •2. Фильтрация. М одифицированный алгоритм Брезенхема
- •2 .1. Модифицированный алгоритм Брезенхема
- •2.2. Улучшение качества изображения фильтрацией
- •З адание на лабораторную работу № 2 "Фильтрация. Модифицированный алгоритм Брезенхема "
- •3 . Алгоритмы генерации окружности
- •3.1. Целочисленный алгоритм Брезенхема
- •3.2. Алгоритм Мичнера для построения окружности
- •З адание на лабораторную работу № 3 "Алгоритмы генерации окружности"
- •4. Алгоритмы построчного заполнения м ногоугольников
- •З адание на лабораторную работу № 4 "Алгоритмы построчного заполнения многоугольников"
- •5. Заливка области с затравкой
- •5 .1. Заливка области с затравкой
- •5.2. Простой алгоритм заливки
- •5.3 Построчный алгоритм заливки с затравкой
- •З адание на лабораторную работу № 5 "Заливка области с затравкой "
- •6 . Алгоритмы отсечения отрезков
- •6.1. Двумерный алгоритм Коэна-Сазерленда
- •6.2. Двумерный fc-алгоритм
- •6.3. Алгоритм Кируса-Бека
- •6.3.1. Определение факта выпуклости многоугольника
- •6.3.2. Вычисление уравнения внутренней нормали
- •З адание на лабораторную работу № 6 "Алгоритмы отсечения отрезков"
- •7 . Алгоритмы отсечения многоугольников
- •7.1 Алгоритм Сазерленда-Ходжмена
- •7.2. Алгоритм отсечения многоугольников Вейлера-Азертона
- •З адание на лабораторную работу № 7 "Алгоритмы отсечения многоугольников"
- •Заключение
- •Оглавление
3.2. Алгоритм Мичнера для построения окружности
В данном алгоритме окружность строится во втором октанте из начальной точки (0, R) по часовой стрелке. Остальные части окружности достраиваются по алгоритму, описанному выше. Т.к. построение ведется во втором октанте, то имеется только две приоритетные точки, по которым можно продолжать построение: (xi + 1, yi) и (xi + 1, yi – 1). В данном алгоритме рассматриваются две погрешности и их сумма:
;
;
.
Если ei > 0, то выбираем точку (xi+1, yi-1), иначе - точку (xi+1, yi).
Для итеративной организации алгоритма необходимо определить выражение для ei+1, оно зависит от выбора следующей точки:
для точки (xi+1, yi) - ei+1= ei+4*xi+6;
для точки (xi+1, yi-1) - ei+1= ei+4*(xi-yi)+10;
для начальной точки (R,0) e1=3-2*R.
З адание на лабораторную работу № 3 "Алгоритмы генерации окружности"
Центр окружности находится в середине экрана (как вариант, координаты центра окружности вводятся вручную).
На экране изображается сетка псевдопикселов.
Постройте окружность с заданным радиусом по целочисленному алгоритму Брезенхема, используя псевдопикселы.
Постройте другим цветом "настоящую" окружность.
Сравните полученные результаты. Сделайте выводы.
Вариант работы: использование алгоритма Мичнера или любого другого алгоритма построения окружности.
Назовите критерий выбора следующей точки в алгоритме Брезенхема.
Сравните два алгоритма.
4. Алгоритмы построчного заполнения м ногоугольников
Ц ель: Изучить алгоритмы построчного заполнения многоугольников
Простейший метод заполнения многоугольника – проверка на принадлежность к многоугольнику каждого элемента растра, но этот метод слишком неэффективен.
Следующий шаг – прямоугольная оболочка – наименьший прямоугольник, содержащий данную фигуру (рис. 4.1 а). Но в случае, изображенном на рис. 4.1 б) эффективность алгоритма тоже оставляет желать лучшего.
Рис. 4.1. Прямоугольная оболочка
Более эффективный метод заполнения состоит в следующем.
Для растровых устройств соседние пикселы в сканирующей строке, вероятно, имеют одинаковые характеристики. Они меняются только там, где ребро многоугольника пересекает сканирующую строку. Эти пересечения делят строку на области (рис. 4.2).
Рис. 4.2. Простейший метод заполнения многоугольника
Для строки Y = 2:
X < 1 – цвет закраски – фон;
1 ≤ X ≤ 8 – цвет закраски – цвет многоугольника;
X > 8 – цвет закраски – фон.
Для строки Y = 4:
X < 1 - цвет закраски – фон;
1 ≤ X ≤ 3 – цвет закраски – цвет многоугольника;
3 ≤ X < 5 – цвет закраски – фон;
5 ≤ X ≤ 8 – цвет закраски – цвет многоугольника;
X > 8 – цвет закраски – фон.
Для определения интенсивности и цвета пикселов рассматриваются пары отсортированных точек пересечения по возрастанию X.
Для строки Y = 2: 1, 8.
Для строки 4: 1, 3, 5, 8 и закрашивается область между парами, остальное – фон.
Трудности возникают при пересечении вершин (рис. 4.3).
Рис. 4.3. Пересечение вершин сканирующими строками
Для строки Y = 2 точки пересечения: 2, 2, 5, т.е. нечетное количество пересечений и, следовательно, необходимо учитывать только одну точку пересечения с ребрами (а именно 2, 5).
Однако, при использовании этого критерия, для строки Y = 6 получаем точки пересечения: 1, 4, 7, т.е. опять нечетное количество пересечений и, в данном случае, необходимо учитывать точку (1, 6) дважды – (1, 1, 4, 7).
Выход: если точка пересечения является локальным максимумом или минимумом, то учитываются две точки пересечения, иначе – одна. Для определения локальных максимумов и минимумов применяется следующий алгоритм: если координаты Y концов отрезка больше (меньше), чем у точки пересечения, то это локальный минимум (максимум) и учитывается две точки, иначе – одна.
Другой простой метод заполнения многоугольников – алгоритм заполнения по ребрам: для каждой сканирующей строки, пересекающей ребро многоугольника, инвертировать все пикселы, которые лежат справа от точки пересечения. Повторить для каждого ребра, кроме ребер, параллельных оси абсцисс (рис. 4.4). инверсия означает изменение цвета многоугольника на цвет фона и наоборот.
Исходный многоугольник изображен на рис. 4.4 а). Ребро P1 – P2 параллельно оси абсцисс и, следовательно, его не учитываем. Обработке ребра P2 – P3 соответствует рис. 4.4 б), ребра P3 – P4 – рис. 4.4 в), ребра P4 – P5 – рис. 4.4 г) и, наконец, ребра P5 – P1 – рис 4.4 д). Причем ребра многоугольника можно обрабатывать в произвольном порядке. Недостатком этого метода является многократная обработка "правых" пикселов.