Слайд 2
![План: 3.1. Общая характеристика алгоритмов машинной графики 3.2. Преобразования координат](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-1.jpg)
План:
3.1. Общая характеристика алгоритмов машинной графики
3.2. Преобразования координат
3.3. Методы растрирования в компьютерной
графике
3.4. Закрашивание фигур
3.5. Удаление невидимых линий
3.6. Триангуляция
Слайд 3
![Перенос Р(х, у) → Р'(х',у') x'=x+Dx y'=y+Dy [x' y']=[x y]](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-2.jpg)
Перенос
Р(х, у) → Р'(х',у')
x'=x+Dx
y'=y+Dy
[x' y']=[x y] + [Dx Dy]
P'=P+D
P(x,y)
P'(x',y')
Dx
Dy
Слайд 4
![Пример:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-3.jpg)
Слайд 5
![Пример: Перенос контура домика на расстояние (3, -4)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-4.jpg)
Пример:
Перенос контура домика на расстояние (3, -4)
Слайд 6
![Масштабирование Sx раз вдоль оси Ox Sy раз вдоль оси Oy x'=Sx·x y'=Sy·y](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-5.jpg)
Масштабирование
Sx раз вдоль оси Ox
Sy раз вдоль оси Oy
x'=Sx·x
y'=Sy·y
Слайд 7
![Пример:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-6.jpg)
Слайд 8
![Пример: Масштабирование контура домика: по оси Ох на (1/2); по](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-7.jpg)
Пример:
Масштабирование контура домика:
по оси Ох на (1/2);
по оси Оу на (2/3).
Масштабирование
контура домика:
по оси Ох на (1/2);
по оси Оу на (1/2).
Слайд 9
![Поворот x'=x·cosθ-y·sinθ y'=x·sinθ+y·cosθ θ R](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-8.jpg)
Поворот
x'=x·cosθ-y·sinθ
y'=x·sinθ+y·cosθ
θ
R
Слайд 10
![Пример: P(6,1) P'(3.5,4.9)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-9.jpg)
Слайд 11
![Пример: Поворот квадрата на угол 30°](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-10.jpg)
Пример:
Поворот квадрата на угол 30°
Слайд 12
![Преобразования в матричной форме: P'=P+D P'=P·S P'=P·R](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-11.jpg)
Преобразования в матричной форме:
P'=P+D
P'=P·S
P'=P·R
Слайд 13
![В однородных координатах](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-12.jpg)
Слайд 14
![Пример композиции](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-13.jpg)
Слайд 15
![Пример:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-14.jpg)
Слайд 16
![Растрирование прямых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-15.jpg)
Слайд 17
![Алгоритмы растрирования прямой алгоритм цифрового дифференциального анализатора (ЦДА); алгоритм Брезенхема.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-16.jpg)
Алгоритмы растрирования прямой
алгоритм цифрового дифференциального анализатора (ЦДА);
алгоритм Брезенхема.
Слайд 18
![Схемы цепочного кодирования: 8-точечная 4-точечная 0 1 2 3 4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-17.jpg)
Схемы цепочного кодирования:
8-точечная
4-точечная
0
1
2
3
4
5
6
7
0
1
2
3
Слайд 19
![Растрирование эллипса Цепочный код растрирования эллипса: =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-18.jpg)
Растрирование эллипса
Цепочный код растрирования эллипса:
<11000077554534433> = <120472524534232>
Слайд 20
![Алгоритм ЦДА (DDA – Digital Differential Analyzer)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-19.jpg)
Алгоритм ЦДА
(DDA – Digital Differential Analyzer)
Слайд 21
![Алгоритм ЦДА Основные расчетные формулы: Xi+1=Xi+Px Yi+1=Yi+Py где Py =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-20.jpg)
Алгоритм ЦДА
Основные расчетные формулы:
Xi+1=Xi+Px
Yi+1=Yi+Py
где Py = Yend-Ystart – приращение координат отрезка
по оси Y;
Px = Xend-Xstart – приращение координат отрезка по оси X.
Слайд 22
![Алгоритм симметричного ЦДА Вычисление Px, Py X1=Xstart Y1=Ystart Вывод точки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-21.jpg)
Алгоритм симметричного ЦДА
Вычисление Px, Py
X1=Xstart Y1=Ystart
Вывод точки с коорд. (X1,Y1)
X1X1=X1+Px/N; Y1=Y1+Py/N
Вывод
точки с коорд. (X1,Y1)
Да
Нет
Слайд 23
![Пример генерации отрезка симметричным ЦДА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-22.jpg)
Пример генерации отрезка симметричным ЦДА
Слайд 24
![Алгоритм несимметричного ЦДА для Px>Py X1=Xstart Y1=Ystart Вывод точки с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-23.jpg)
Алгоритм несимметричного ЦДА для Px>Py
X1=Xstart Y1=Ystart
Вывод точки с коорд. (X1,Y1)
X1X1=X1+1;
Y1=Y1+Py/Px
Вывод точки
Слайд 25
![Пример генерации отрезка несимметричным ЦДА](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-24.jpg)
Пример генерации отрезка несимметричным ЦДА
Слайд 26
![Алгоритм Брезенхема k k > 1/2 u v](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-25.jpg)
Алгоритм Брезенхема
k < 1/2
k > 1/2
u
v
Слайд 27
![Алгоритм Брезенхема d=2*v-u Вывод т. (X,Y) d X=X+1 d=d+2*v Вывод](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-26.jpg)
Алгоритм Брезенхема
d=2*v-u
Вывод т. (X,Y)
d<0
X=X+1
d=d+2*v
Вывод т. (X,Y)
Да
Нет
X=Xstart Y=Ystart
X=X+1; Y=Y+1
d=d+2*(v-u)
u>0
u=u1
Да
Нет
Слайд 28
![Пример генерации отрезка методом Брезенхема](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-27.jpg)
Пример генерации отрезка методом Брезенхема
Слайд 29
![Сравнение примеров для 2-х методов ЦДА Брезенхема](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-28.jpg)
Сравнение примеров для 2-х методов
ЦДА
Брезенхема
Слайд 30
![Методы заливки фигур: сканирование строк; затравочное заполнение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-29.jpg)
Методы заливки фигур:
сканирование строк;
затравочное заполнение
Слайд 31
![Метод сканирования строк](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-30.jpg)
Слайд 32
![Метод сканирования строк XMin, XMax N](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-31.jpg)
Метод сканирования строк
XMin, XMax
N
Слайд 33
![Алгоритм метода сканирования строк: XMax=0 XMin=N j=jmin..jmax i=i1..i3 XMax[j] XMax[j]=i](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-32.jpg)
Алгоритм метода сканирования строк:
XMax=0 XMin=N
j=jmin..jmax
i=i1..i3
XMax[j]
XMax[j]=i
XMin[j]>i
XMin[j]=i
да
да
нет
нет
Вывод отрезков
{(XMin[j],j), (XMax[j],j)}
Слайд 34
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-33.jpg)
Слайд 35
![Метод затравочного заполнения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-34.jpg)
Метод затравочного заполнения
Слайд 36
![Метод затравочного заполнения:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-35.jpg)
Метод затравочного заполнения:
Слайд 37
![Алгоритм затравочного заполнения Piзатр → стек Стек не пуст Извлечение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-36.jpg)
Алгоритм затравочного заполнения
Piзатр → стек
Стек не пуст
Извлечение Piсос
Вывод Pi на экран
Да
Нет
Стек
→ Pi, инициал. Pi
Piсос - гран., иниц.
Нет
Piсос → стек
Да
Слайд 38
![Удаление невидимых линий и поверхностей](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-37.jpg)
Удаление невидимых линий и поверхностей
Слайд 39
![Удаления невидимых линий: Метод Робертса; Метод Аппеля; Метод Варнока; Метод Вейлера-Азертона; метод Z-буфера; метод построчного сканирования](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-38.jpg)
Удаления невидимых линий:
Метод Робертса;
Метод Аппеля;
Метод Варнока;
Метод Вейлера-Азертона;
метод Z-буфера;
метод построчного сканирования
Слайд 40
![Метод Робертса](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-39.jpg)
Слайд 41
![Алгоритм Робертса: отбрасываются все ребра, обе образующие грани которых являются](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-40.jpg)
Алгоритм Робертса:
отбрасываются все ребра, обе образующие грани которых являются нелицевыми;
проверяется каждое
из оставшихся ребер со всеми гранями многогранника на закрывание. При этом возможны три случая:
Слайд 42
![Метод Варнока внешним, если он целиком находится вне окна; внутренним,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-41.jpg)
Метод Варнока
внешним, если он целиком находится вне окна;
внутренним, если он целиком
расположен внутри окна;
пересекающим, если он пересекает границу окна;
охватывающим, если окно целиком расположено внутри него.
Слайд 43
![Алгоритм Варнока (продолжение) Если все многоугольники сцены являются внешними по](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-42.jpg)
Алгоритм Варнока (продолжение)
Если все многоугольники сцены являются внешними по отношению к
окну, то оно пусто и изображается фоновым цветом.
Если только один многоугольник сцены является по отношению к окну внутренним, то оно заполняется фоновым цветом, а многоугольник заполняется своим цветом.
Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему пересекающим, то окно заполняется фоновым цветом, а часть многоугольника, принадлежащая окну, заполняется цветом многоугольника.
Слайд 44
![Алгоритм Варнока (продолжение) Если только один многоугольник охватывает окно и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-43.jpg)
Алгоритм Варнока (продолжение)
Если только один многоугольник охватывает окно и нет других
многоугольников, имеющих общие точки с окном, то окно заполняется цветом этого многоугольника.
Если существует хотя бы один многоугольник, охватывающий окно, то среди всех таких многоугольников выбирается тот, который расположен ближе всех многоугольников к точке наблюдения, и окно заполняется цветом этого многоугольника.
В противном случае производится новое разбиение окна.
Слайд 45
![Метод Аппеля](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-44.jpg)
Слайд 46
![Алгоритм Аппеля: Определяется количественная невидимость вершины. Просматривается изменение количественной невидимости](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-45.jpg)
Алгоритм Аппеля:
Определяется количественная невидимость вершины.
Просматривается изменение количественной невидимости вдоль каждого из
ребер, выходящих из данной вершины.
Выполняется переход к следующей вершине и возврат к п. 1).
Если ребро выходит из вершины, принадлежащей контурной линии, проверяется, не закрывается ли это ребро одной из граней.
Слайд 47
![Метод z-буфера](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-46.jpg)
Слайд 48
![Алгоритм Z-буфера: Заполнить буфер кадра фоновым значением интенсивности или цвета.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-47.jpg)
Алгоритм Z-буфера:
Заполнить буфер кадра фоновым значением интенсивности или цвета.
Заполнить z-буфер минимальным значением z.
Преобразовать
каждый многоугольник в растровую форму в произвольном порядке.
Для каждого Пиксел(x,y) в многоугольнике вычислить его глубину z(x,y).
Сравнить глубину z(х,у) со значением Zбуфер(х,у), хранящимся в z-буфере в этой же позиции.
Если z(х,у) > Zбуфер (х,у), то записать атрибут этого многоугольника в буфер кадра и заменить Zбуфер(х,у) на z(х,у). В противном случае никаких действий не производить.
Слайд 49
![Триангуляция Методы триангуляции: Делоне; Форчуна](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-48.jpg)
Триангуляция
Методы триангуляции:
Делоне;
Форчуна
Слайд 50
![Алгоритм триангуляции Берем три вершины A1, A2, A3 Проверяем образуют](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-49.jpg)
Алгоритм триангуляции
Берем три вершины A1, A2, A3
Проверяем образуют ли векторы A1A3,
A1A2 и их векторное произведение левую тройку векторов.
Проверяем нет ли внутри треугольника A1A2A3 какой-либо из оставшихся вершин многоугольника.
Слайд 51
![Алгоритм триангуляции Если оба условия выполняются, то строим треугольник A1A2A3,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/101842/slide-50.jpg)
Алгоритм триангуляции
Если оба условия выполняются, то строим треугольник A1A2A3, а вершину
A2 исключаем из многоугольника, не трогая вершину A1, сдвигаем вершины A2 (A2 на A3), A3 (A3 на A4)
Если хоть одно условие не выполняется, переходим к следующим трем вершинам.
Повторяем с 1 шага, пока не останется три вершины.