Долгая М.В. Конспект лекций по дисциплине Основы компьютерной графики
Подождите немного. Документ загружается.
51
Рис. 10.8. Точка пересечения перед треугольником AВС
Если значения MIN и МАХ параметра λ указывают на точки пересечения I и J, как на рис.
10.2, тогда отрезок IJ будет невидимым, и:
• если точка Р находится вне пирамиды или перед плоскостью АВС, то отрезок РI
видимый;
• если точка Q находится вне пирамиды или перед плоскостью АВС, то отре
зок JQ
видимый;
Если точки Р и Q, обе одновременно, не находятся вне пирамиды, то точки I и J
совпадают. Это показано на рис. 10.9.
Во все
х предыдущих тестах при определении видимости отрезка ( по отношению к i
-му треугольнику) значение параметра j увеличивается на единицу. Затем проверяется
отношение отрезка прямой линии РQ с остальными треугольниками, если они еще есть, или
отрезок вычерчивается, если треугольников больше нет. Но в этом тесте могут появиться
два новых отрезка РI и JQ, которые должны бы
ть проверены на отношение с оставшимися
треугольниками. Здесь можно будет рекурсивно дважды обратиться к этому же алгоритму.
Рис8.9. Только одна точка пересечения
Для каждого рекурсивного обращения будем задавать концевые точки отрезка прямой
линии и номер j+1 треугольника, с которого должна начаться проверка.
52
ЛЕКЦИЯ 9. АЛГОРИТМ ПОСТРОЕНИЯ ПОВЕРХНОСТИ
ТИПА В-СП
ЛАЙНА
Точка на поверхности задаётся вектором
(
)
(
)
(
)
[
]
v,uz;v,uy;v,uxP
S
=
U, V – независимые параметры.
Для аппроксимации поверхности с помощью В–сплайна необходимо задать набор их nxm точек в
следующем виде:
Р
11
Р
12
. . . Р
1m
Р
21
Р
22
. . . .
. . . . . .
. . . . . .
. . . . . .
Р
n1
Р
n2
. . . Р
nm
Каждая точка в этой последовательности будет иметь номер
(
)
jm1ik
+
−
=
. Самая первая и
самая последняя точки не аппроксимируются. Это замечание относится и к точкам в каждом ряду
(как горизонтальном, так и вертикальном), т.е. не аппроксимируются точки в горизонтальных
рядах с номерами j=1 и j=m и в вертикальных с номерами i=1 и i=n.
Для вычисления сетки «четырёхугольника» нам потребуются по 4-е точки в каждом напр
авлении:
2j,2i1j,2ij,2i1j,2i
2j,1i1j,1ij,1i1j,1i
2j,i1j,ij,i1j,i
2j,1i1j,1ij,1i1j,1i
PPPP
PPPP
PPPP
PPPP
+++++−+
+++++−+
++−
+−+−−−−
(1)
Эти точки используются для аппроксимации «четырёхугольника», который будет поделен
на NxM малых элементов поверхности (т.е. N элементов по вертикали и M элементов по
горизонтали).
Для программы реализующей аппроксимацию поверхности методом В-сплайнов
необходимо подготовить файл входных данных, который будет содержать координаты точек
поверхности (опорных точек), т.е. массивы X, Y и Z.
Предполагают, чт
о в массивах точки образуют следующие сетки
1 2 . . . M
m+1 m+2 . . . 2m
2m+1 2m+2 . . . 3m
. . . . . .
. . . . . .
(n-1)m+1 (n-1)m+2 . . . nm
Причём значения n и m вводятся с клавиатуры, а в массиве должно быть количество
элементов соответствующее nxm (ни n ни m не может быть меньше 4).
Кроме того, при описании, т.е. формировании массивов (исходных) необходимо
продублировать первые и последние строки и столбцы, т.к. при аппро
ксимации не
аппроксимируются элементы с i=1 и i=n, а также j=1 и j=m, т.е. исходный массив должен
содержать одинаковые значения в 1, 2, n-1 и n строках и в 1, 2, n-1 и m столбцах.
Исходные массивы одномерные, т.е. элементы в них располагаются следующим образом:
1 2 3 . . . n*m
(2)
53
Схема алгоритма
(NB! Алгоритм укрупнён, в нём отсутствуют проверки, соответствует ли число элементов
значению nxm или реакция на ошибки при обращении к файлу и т.д.)
Рисунок 9.1, Лист1
Ввод N, M,
{Xi}, {Yi},
{Zi}
Начало
A=(m-3)*M+1
j = 2, m-2
B=(j-2)*M+1
Вычисление
коэфф-тов
h
00,
h
01,
h
02,
h
03
h
10,
h
11,
h
12, …
1
i = 2, n-2
Заполнение
матриц 4х4
Для координат X, Y, Z
фрагмента поверхности
а
00…
а
33
b
00…
b
33
c
00 …
c
33
А – количество
точек в строке
В – количество точек в
строке до начала
нового столбца
54
Рисунок 9.1, Лист 2
Для формирования матрицы (1) стр. 18, необходимо из исходного массива считать элементы,
индексы которых формируются по схеме (2). В блоке 5 вычисляют индексы следующим образом:
U=I/N
C=((i-2)N+I)A+B
Вычисление
Xk, Yk, Zk
V=J/M
K=C+J
В файл
Конец
J=(i==2?0:1),
M
J
I
j
i
I=(i==2?0:1),
N
1
Запись хk,
Yk, Zk в
файл
С – количество точек в
матрице до начала
обрабатываемой строки
К – индекс текущей
точки в выходном
массиве
55
()
;33033;23032;13031;2030
;32023;22022;12021;1020
;30003;20002;10001;1000
;31013;21012;11110
111
+=+=+=+=
+=+=+=+=
+=+=+=−=
+=+=−=
+⋅−=
hhhhhhmhh
hhhhhhmhh
hhhhhhmhh
hhhhhh
jmih
При помощи этой схемы из последовательности элементов выбирается сетка, соответствующая (2)
и (1), т.е. скажем, имеется исходный массив:
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35
36 37 38 39 40 41 42
Зелёным дублируемые фрагменты (строки и столбцы)
]33[33]33[33]33[33
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
]02[02]02[02]02[02
]01[01]01[01]01[01
...00]00[00]00[00
hzzhyyhxx
hzzhyyhxx
hzzhyyhxx
zhyyhxx
===
===
===
=
=
=
Формулы для вычисления коэффициентов:
(
)()
()()
()()()
()()()( )
36/1211*121012*422210201*32320000303
12/11*81210*42001*22220020002
12/1012*42220000201
36/11*1621121001*42220020000
xxxxxxxxxxxxa
xxxxxxxxxa
xxxxxxa
xxxxxxxxxa
−+−+−+−++−−=
−+++−+++=
−++−−=
+
+
+
+
++++=
(
)
(
)
()
()()
()()
12/22210102*32320030013
4/2101*22220020012
4/2220020011
12/2101*42220020010
xxxxxxxxa
xxxxxxa
xxxxa
xxxxxxa
−+−++−−=
−+++−−=
+−−=
+
−
+
+
+−−=
Для i=2 а j=3
будет выбрана
сетка
56
(
)
(
)()
()()
()()
()( )()( )
12/1112*622210201*31310*22320030023
114/21121001*22220020022
4/1210*22220000221
12/11*82101*41210*22220020020
xxxxxxxxxxxxa
xxxxxxxxxa
xxxxxxa
xxxxxxxxxa
−+−+−+−++−+−=
+−−−−++++=
−++−−=
−
+
+
+
−+++=
()
(
)( )( )
()()
()( )( )( )
()()( )
36/22211211*93231232013100201*33330030033
12/2111*622201210*33101*23230020032
12/22201210*33230020031
36/2111*123101*422201210*33230020030
xxxxxxxxxxxxxxxxa
xxxxxxxxxxxxa
xxxxxxxxa
xxxxxxxxxxxxa
+−−+−+−++−+−++−−=
+−+−−++−+++−−=
−++−++−−=
−
+
+
−
+
−
−
+
+++−−=
Для коэффициентов B
00
–B
33
и C
00
–C
33
формулы те же, но x заменяется y и z.
1 2 3 4 5 6 7 8 9 10 11
P P+1
P+A (P+A+1)
n m
1) n – строк в исходном массиве
m – столбцов
2) 1-ая и n-ая строки – идентичны 2-ой и n-1 соответственно. 1-ый и m-ый
столбец – 2-му и m-1.
3) Зелёные линии означают повторяющиеся строки и столбцы.
4) аппроксимируемых прямоугольников:
по горизонтали: m-3
по вертикали: n-3
т.е. m-2-1 и n-2-1
где 2 – это дополнительные точки в массиве (1-ая и m-ая)
5) N – числ
о разбиений по вертикали
M – число разбиений по горизонтали внутри каждого прямоугольника
6) Количество точек в горизонтальном ряду выходного массива
A = (m – 3)*M + 1
где m – 3 – число прямоугольников
M – количество разбиений
⎭
⎬
⎫
57
СОДЕРЖАНИЕ
Лекция 1. Геометрические преобразования объектов
на плоскости
3
Лекция 2. Геометрические преобразования объектов в трехмерном пространстве
8
Лекция 3. Преобразования проектирования
16
Лекция 4. Алгоритмы растровой графики
22
Лекция5. Разложение окружности в растр
27
Лекция 6.
Проблемы удаления невидимых поверхностей
30
Лекция7. Примеры алгоритмов удаления невидимых поверхностей.
38
Лекция 8 Алгоритм удаления невидимых поверхностей по Аммералу
41
Лекция 9 Алгоритм построения поверхности типа В-сплайна
52
58
ПЕРЕЧЕНЬ РЕКОМЕНДОВАННОЙ ЛИТЕРАТУРЫ
1 Кнут Д. Искусство программирования для ЭВМ: в 7-ми т./ Д. Кнут.-М., Мир, 1977.
2 Фолли Д., Дем А. Основи интерактивной машинной графики. ( в 2-х кн.)/ Д.Фолли, А.
Дем, М.: Мир, 1985.
3 Ньюмен В., Спрулл Р. Основи интерактивной машинной графики/ У.Ньюмен, Р.Спрулл.
М.: Мир, 1976.
4 Ам
мерал Л. Машинна графика в 4-х томах/ Л.Аммерал:. М. "Сол Систем", 1992.
5 Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистичные
изображения/ Е.В.Шикин, А.В.Боресков. - М.: МИФЕ диалога, 1995. -228с.
6 Ласло М. Обчислювальна геометрия и компьютерная графика на С++/ М.Ласло:Пер. с
англ. – М.: «Издательств
о БИНОМ»,1997.-304с.:ил.
7 РоджерсД.Ф. Алгоритмические основы машинной графики/ Д.Ф.Роджерс. М.:Мир,1989.
8 Иванов В.П., Батраков А.С. Трехмерная компьютерная графика/
В.П.Иванов, А.С.Батраков. М.: Мир, 1995.
9 Хейз Бы., Крамплер У. Художні приемы работы в PhotoShop./Б.Хейз, У.Крамплер: Пер. с
англ.-М.: Изд
ательский дом "Вильямс", 2003, -976с.:ил.
10 http//www.subscribe.ru/Уроки по AdobePhotoshop
11 Кирсанов Д. Веб-дизайн: книга Дмитрия Кирсанова./ Д.Кирсанов – СПб:Символ-Плюс,
1999-376с.
12 Чернишев О.В. Формальная композиция. Творческий практикум./ О.В.Чернишов –
Мн.:Харвест, 1999. – 312с.
13 Бейн Стив Использование CorelDraw. Специальное издание/ С.Бейн. –К.:Диалектика,
2000.-528с.
14 h
ttp//www.subscribe.ru/Уроки CorelDraw
15 http//www.AdobePhotoShop. Уроки AdobePhotoShop.
16 Айсман Кэтрин. Ретуширование обработка изображений в Adobe PhotoShop/ К.Айсман -
СПб:Вильямс, 2004. – 470с.:ил.