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

Презентация:



Advertisements
Похожие презентации
Алгоритмы трёхмерной графики Алгоритмы трёхмерного отсечения, алгоритм плавающего горизонта.
Advertisements

Алгоритмы растеризации Алгоритмы Брезенхема рисования отрезка и окружности.
Компьютерная геометрия и графика. Лекция 2. План занятия: Проверка многоугольника на выпуклость. Нахождение площади произвольного многоугольника. Принадлежность.
Компьютерная геометрия и графика. Лекция 3. План занятия: Задача о пересечении двух выпуклых многоугольников. Задача о пересечении двух произвольных многоугольников.
Компьютерная геометрия и графика. Лекция 9. План занятия: Алгоритм построчного сканирования. Основная идея метода. Алгоритм построчного сканирования с.
Многоугольники Изучение нового материала. Все ли фигуры являются многоугольниками? агб в д еж з.
Ломаные Ломаной называется … фигура, образованная конечным набором отрезков, расположенных так, что … Сами отрезки называются…сторонами ломаной, а их концы.
Двумерные массивы Обработка относительно диагоналей.
Ломанная. Многоугольник. Ломаная линия геометрическая фигура, состоящая из отрезков, последовательно соединенных своими концами. Отрезки, из которых состоит.
Параллельность прямой и плоскости. Если две точки прямой лежат в данной плоскости, то вся прямая лежит в этой плоскости. Тогда возможны три случая взаимного.
Ломаные Ломаной называется … Сами отрезки называются…сторонами ломаной, а их концы – конец первого является началом второго, конец второго – началом третьего.
Многоугольники Вершины ломаной называются вершинами многоугольника. Стороны ломаной называются сторонами многоугольника. Углы, образованные соседними сторонами.
МНОГОУГОЛЬНИКИ Ломаная. Выпуклые многоугольники. Учитель математики ГБОУ ЦО 354 Попельнюк Г.Н.
Алгоритмические структуры 1.Линейный 2.Ветвление 3.Цикл.
Многоугольники. Выпуклые многоугольники. Определение. Элементы многоугольника. Свойства.
const n=10; var a:array[1..n] of integer; i,j,c,b,k:integer; begin randomize; for i:=1 to n do begin a[i]:=random(11)-5;write(a[i]:5) end;writeln;
Отрезки, соединяющие не соседние вершины многоугольника, называются диагоналями многоугольника. А4А4 А2А2 А5А5 А1А1 А3А3 Рассмотрим простую ломаную А.
Параллельность прямой и плоскости. Возможны три случая взаимного расположения прямой и плоскости в пространстве Прямая лежит в плоскости; Прямая и плоскость.
3. Дана прямоугольная матрица, элементами которой являются целые числа. Поменять местами ее строки следующим образом: первую строку с последней, вторую.
M-чередующаяся декомпозиция Лекция 10. Нечетная декомпозиция Теорема 9.7 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда.
Транксрипт:

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

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

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

Отсечение многоугольника Отсечение выпуклой многоугольной областью Выпуклый многоугольник = пересечение полуплоскостей, образованных сторонами многоугольной области Алгоритм Сазерленда-Ходгмана { 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;

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

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

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

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

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