Алгоритмы растеризации Алгоритмы двумерного отсечения, заполнения многоугольника, устранение ступенчатости, масштабирование. - презентация

1 Алгоритмы растеризации Алгоритмы двумерного отсечения, заполнения многоугольника, устранение ступенчатости, масштабирование

2 Литература Д. Роджерс. Алгоритмические основы машинной графики. – М. Мир, 1978.

3 Заполнение многоугольника 1.Отсечение многоугольника 2.Заполнение многоугольников Отсечение выпуклой многоугольной областью Отсечение невыпуклой областью 3.Определение выпуклости многоугольника Внутреннее и внешнее отсечение Отсечение прямоугольным окном

4 Отсечение многоугольника Отсечение выпуклой многоугольной областью Выпуклый многоугольник = пересечение полуплоскостей, образованных сторонами многоугольной области Алгоритм Сазерленда-Ходгмана { p[1..n] – многоугольник, sp – полуплоскость, inp(p,sp) – лежит ли точка p в полуплоскости sp, add – добавление вершины в новый многоугольник } p[0]:=p[n]; ci := inp(p[n],sp); for i:=1 to n do begin nci := inp(p[i],sp); if nci ci then begin newp:=intersect(p[i-1],p[i],sp); add(newp); end; if nci then add(p[i]); ci := nci; end;

5 Заполнение многоугольника Сканирующий алгоритм Заполнение выполняется построчно Возможны случаи: У строки нет точек пересечения со сторонами многоугольника Строка пересекается со сторонами в 2n различных точках Строка проходит через вершину многоугольника Обе стороны либо сверху, либо снизу сканирующей строки Одна сторона сверху, другая снизу сканирующей строки

6 Отсечение отрезков Отсечение прямоугольным окном Побитовое представление расположение точки Определение видимых, невидимых и частично видимых отрезков Внешний цикл – по отрезкам Если оба конца в окне – полностью видимый, если один в окне, другой – нет – частично видимый, если оба вне – дополнительный анализ Алгоритм Сазерленда-Коэна Алгоритм разбиения средней точкой

7 Алгоритм Сазерленда-Коэна Отрезок [P1, P2] 1. Определение видимых, невидимых и частично видимых отрезков 2. Если P1 внутри окна, поменять местами P1 и P2 3. Заменить P1 на точку пересечения со стороной окна

8 Устранение ступенчатости Использование полутонов Метод увеличения частоты выборки Модифицированный алгоритм Брезенхема

9 Масштабирование Цвет пикселя принимается равным цвету ближайшего пикселя исходного изображения Использование интерполяции