Мосин В.Г. Математические основы компьютерной графики: Монография
Подождите немного. Документ загружается.
Глава 1
Математика графических
преобразований
Любой процессор, даже самый продвинутый, умеет делать только две вещи:
складывать и умножать числа — и больше ничего.
Мы так привыкли к неограниченным возможностям современных компью-
теров, что уже вряд ли помним, что любое наше действие в пользователь-
ской среде — неважно, какой именно: это может быть и мощный графи-
ческий редактор, например, PhotoShop , и просто графический интерфейс
операционной среды Windows — сводится, в конечном счете, к арифмети-
ческим действиям с числами. Например, симметричное отражение изобра-
жения (см. рис. 1.1, стр. 12) или искривление текста (см. рис. 1.2, стр. 13).
В этой книге мы рассмотрим лишь некторые математические идеи, позво-
ляющие реализовать в численной форме некоторые графические операции:
линейные преобразования объектов и формирование кривых по заданным
характеристикам. Комбинирование этих приемов приводит к очень широ-
кому классу действий с графическими объектами. Однако следует иметь в
виду, что в целом компьютерная графика апеллирует к математике в гораз-
до более высокой степени, нежели это делаем мы в пределах нашего курса:
активно используются приемы фрактальной геометрии, методов вычисле-
ний и многое другое.
Многие из этих приемов описаны в детальной монографии Эдварда Эндже-
ла [E], к которой мы отошлем заинтересованных читателей.
1.1 Линейные задачи
Линейными мы будем считать преобразования объекта, которые не приво-
дят к его деформации
1
, такие, как поворот, смещение или отражение.
Рассмотрим, например, симметричное отражение какого-нибудь изображе-
ния (см. рис. 1.1, стр. 12). Изображение, которое мы используем для приме-
1
Разумеется, это не строгая формулировка — мы не определили термин “деформация”.
Корректное определение линейного преобразования будет дано в главе, посвященной
линейной алгебре (см. главу 2, стр. 17).
11
12 Глава 1. Математика графических преобразований
ра, является растровым (формат JPG), то есть — описывается попиксельно.
Каждый пиксел (точка изображения) обладает своими числовыми характе-
ристиками: цветом, яркостью, глубиной и, в числе прочего, координатами.
В результате отражения изменяются координаты точки, то есть, процессор
вычисляет новые координаты для каждого пиксела при помощи стандарт-
ного алгоритма
2
.
(a) Исходное изображение. (b) Отраженное изображение.
Рис. 1.1: Простейшая манипуляция с объектом: симметричное отражение.
Алгоритм состоит в выполнении матричного умножения, которое сводится
к арифметическим операциям умножения и сложения чисел (см. раздел 2.1,
стр. 18). Если предположить, что вертикальная ось системы координат на
плоскости монитора совпадает с левой границей рисунка, то процессор вы-
числяет новые координаты (x
,y
, 1) каждого пиксела в проективной форме
по следующей формуле:
x
y
1
=
−100
010
001
·
x
y
1
,
где (x, y, 1) — это старые проективные координаты пиксела
3
. Аналогично,
при помощи матричного умножения, можно получить алгоритм вертикаль-
ного отражения и, вообще — отражения относительно любой прямой на
плоскости.
Другие матрицы определяют другие преобразования плоскости: смещения,
масштабирования, повороты и их комбинации. Решениям таких задач по-
священа первая часть книги.
1.2 Нелинейные задачи
Если объект имеет сложную криволинейную форму, то его точное
4
описа-
ние получается путем интерполяции его границы в той или иной форме
2
Несмотря на то, что количество пикселов в достаточно крупном растровом изобра-
жении измеряется миллионами, PhotoShop выполняет эту операцию в доли секунды. Все
дело, разумеется, в быстродействии процессора. Те читатели, которые застали эпоху про-
цессоров до серии Pentium, помнят, что на прцессорах серии 486 работать в растровых
редакторах было практически невозможно.
3
О проективных координатах точек и векторов мы также расскажем в дальнейшем
(см. раздел 3.1, стр. 64).
4
То есть, исключающее аппроксимацию в виде мнгогзвеньевой ломаной.
1.2. Нелинейные задачи 13
(см. главу 6, стр. 139). Так, например, описываются кривые, формирующие
символы любого шрифта.
(a) Исходный текст. (b) Текст, направленный вдоль кривой.
Рис. 1.2: Использование криволинейных траекторий при работе с текстом.
Кроме того, кривые могут иметь самостоятельное значение, например, если
речь идет о криволинейной траектории движения объекта, или выполнять
вспомогательные функции, как, например, в случае с искривлением текста
(см. рис. 1.2, стр. 13). Рассмотрим более подробно этот пример.
Направляющие искривления были сформированы в векторном редакторе
при помощи инструмента “трехточечная кривая”. Для их построения про-
цессор использовал алгоритм точной интерполяции (см. раздел 6.1, стр. 139).
Имея в своем распоряжении координаты трех точек A(x
A
,y
A
), B(x
B
,y
B
) и
C(x
C
,y
C
), через которые проходит кривая, он вычислил коэффициенты a
ij
параметически заданной функции
5
p(u)=
a
10
+ a
11
u + a
12
u
2
a
20
+ a
21
u + a
22
u
2
путем следующих действий, состоящих опять-таки в выполнении матрич-
ного умножения:
a
10
a
11
a
12
=
100
−34−1
2 −42
x
A
x
B
x
C
,
a
20
a
21
a
22
=
100
−34−1
2 −42
y
A
y
B
y
C
.
После этого, путем пересчета значений функции с минимальным шагом
получил координаты всех точек кривой
6
.
Решению подобных задач посвящена вторая часть книги.
5
О функциях, заданных параметрически, мы расскажем во второй части книги (см.
раздел 4.1, стр. 87).
6
Всех с машинной точки зрения, а не с общетеоретической. Вообще точек на любом
участке любой кривой бесконечно много, но на экране монитора присутствует конечное
их число.
14 Глава 1. Математика графических преобразований
Часть I
Преобразования плоскости
15
Глава 2
Линейная алгебра
Основными объектами линейной алгебры
1
служат векторные пространства
и их линейные преобразования. В этой главе мы построим математический
аппарат, который позволит представлять точки простанств в виде векторов-
столбцов их координат (см. раздел 2.2, стр. 27) и осуществлять линейное
действие на пространство путем матричного умножения (см. раздел 2.3,
теор. 21, стр. 56).
Мы начинаем с изучения матричных действий (см. раздел 2.1, стр. 18),
уделяя основное внимание матричному умножению и матричному обраще-
нию. Это позволяет нам в дальнейшем при изучении линейных операторов
(см. раздел 2.3, стр. 44) установить взаимно-однозначное соответствие (или,
выражаясь математически — алгебраический изоморфизм) между двумя
множествами: множеством матриц, с одной стороны, и множеством линей-
ных операторов, действующих в векторном пространстве, с другой (см. раз-
дел 2.3, теор. 25, стр. 58).
Через всю главу мы проводим как генеральную линию серию геометри-
ческих примеров, особенно важных для дальнейших целей — построения
алгоритмов преобразований плоскости. К этим примерам относятся гео-
метрические примеры векторных пространств (см. раздел 2.2, стр. 27) и
примеры линейных операторов, действующих на плоскости: геометрически
(см. раздел 2.3.1, стр. 44) и в виде матриц (см. раздел 2.3.5, стр. 59).
Работая с этой главой, необходимо параллельно обращаться к приложе-
ниям, посвященным определителям
2
, матрицам и линейным системам (см.
1
Прежде всего, договоримся о терминах. Слово “алгебра” используется как минимум
в двух разных смыслах. Обычно под этим термином понимают раздел математики (на-
пример, в заголовке этой главы слово “алгебра” означает именно это). Но, кроме этого
значения, у него есть еще одно — сугубо математическое: термином “алгебра” в математи-
ке обозначают множества, обладающие определенными свойствами (см. опр. 6, стр. 21),
и в заголовке раздела 2.1 слово “алгебра” присутствует именно в смысле множества. Бо-
яться такой амбивалентности не следует. Вообще — это обычная ситуация в математике,
когда значение слова существенно зависит от контекста — слов мало, а математических
понятий очень много. Приходится довольствоваться малым и использовать то, что есть.
2
Причем, изучение определителей (см. приложение A.1, стр. 157) должно даже пред-
шествовать чтению. К сожалению, рамки курса невелики, и в них невозможно подробно
осветить все темы. Некоторые из них не включены в теоретический блок, а представлены
только в приложениях.
17
18 Глава 2. Линейная алгебра
приложение A, стр. 157), а также векторным пространствам (см. прило-
жение B, стр. 187). В этих приложениях подробно рассмотрено множество
примеров, где применяются самые разнообразные алгебраические методы,
полезные как на практике, так и при решении теоретических задач.
Разумеется, одна небольшая глава книги не может рассматриваться как по-
дробное руководство по линейной алгебре. Мы затрагиваем лишь ее неболь-
шую часть, необходимую для специфических приложений компьютерной
графики. Подробные курсы линейной алгебры можно найти в классических
книгах Б. Л. Ван-дер-Вардена [V], А. И. Мальцева [M], А. И. Кострикина
и Ю. И. Манина [KM] и др.
2.1 Полная матричная алгебра
В дальнейшем мы увидим (см. раздел 2.3.5, стр 59), что очень широкий
спектр преобразований плоскости реализуется в виде квадратных матриц,
причем композициям таких преобразований отвечает математическая ком-
бнинация соответствующих матриц.
В этом разделе мы рассмотрим матричные действия: сложение, скалярное
кратное, умножение (см. раздел 2.1.1, стр 18) и матричное обращение (см.
раздел 2.1.3, стр. 24) и установим их свойства (см. раздел 2.1.2, стр. 21).
Практические примеры, относящиеся к этому разделу, представлены в при-
ложениях (см. приложение A, стр. 157).
2.1.1 Матрицы
Определение 1 (матрицы) Матрицей называется прямоугольная табли-
ца чисел
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
... a
mn
.
Элементы, расположенные в этой таблице, называются матричными ком-
понентами. Они нумеруются двумя индексами: a
ij
, причем первый индекс
указывает на номер строки, а второй — на номер столбца, в котором распо-
ложено соответствующее число. Множество матриц, состоящих из m строк
и n столбцов, мы будем обозначать Matr
m×n
.
Если число строк в матрице совпадает с числом ее столбцов, то матри-
ца называется квадратной. Множество всех квадратных матриц порядка n
обозначается Matr
n
.
Пример 1 Рассмотрим несколько примеров. Вот — примеры прямоугольных мат-
риц:
2 −1
43
20
∈ Matr
3×2
,
112
531
∈ Matr
2×3
.
2.1. Полная матричная алгебра 19
А это – квадратные матрицы (отметим, что в дальнейшем именно квадратные
матрицы будут играть существенную роль):
0 −1
32
∈ Matr
2
212
6 −31
58−3
∈ Matr
3
.
Среди всего множества квадратных матриц выделяются так называемые
единичная и нулевая матрицы. Их свойства относительно матричных дей-
ствий аналогичны свойствам единицы и нуля на множестве чисел.
Определение 2 (единичная и нулевая матрицы) Единичной называ-
ется квадратная матрица, на главной диагонали которой расположены еди-
ницы, а на остальных местах — нули. Нулевой называется квадратная мат-
рица, все компоненты которой равны нулю.
Пример 2 Вот примеры единичных матриц порядка 2 и порядка 3:
10
01
∈ Matr
2×2
,
100
010
001
∈ Matr
3×3
.
А это — примеры соответствующих нулевых матриц:
00
00
∈ Matr
2×2
,
000
000
000
∈ Matr
3×3
.
С матрицами можно выполнять различные действия: сложение, умножение
и умножение на число (так называемое, скалярное кратное матрицы). Эти
действия мы рассмотрим в настоящем разделе
3
.
Определение 3 (сумма матриц) Пусть имеются две матрицы A и B од-
ного порядка: A, B ∈ Matr
m×n
. Их суммой называется прямоугольная мат-
рица C ∈ Matr
m×n
того же порядка, что и слагаемые, компоненты которой
вычисляются следующим образом:
c
ij
= a
ij
+ b
ij
.
Другими словами — сложение матриц осуществляется покомпонентно.
Пример 3 Пусть требуется сложить две матрицы порядка 2 × 3:
1 −13
110
+
213
011
=
306
121
.
Результат на первом-первом месте получился очень просто: 1+2=3. На осталь-
ных местах — точно так же.
Определение 4 (скалярное кратное матрицы) Пусть имеется матри-
ца A ∈ Matr
m×n
и число α. Тогда выражение αA означает матрицу B ∈
Matr
m×n
того же порядка, что и матрица A, компоненты которой вычис-
ляются следующим образом:
b
ij
= αa
ij
.
Другими словами — скалярное кратное матрицы вычисляется покомпонент-
но.
3
Еще одной матричной операции — матричному обращению — посвящен отдельный
раздел.
20 Глава 2. Линейная алгебра
Пример 4 Умножим матрицу на число:
2
1 −10
213
=
2 −20
426
.
Каждое место матрицы мы просто умножили на 2. Других комментариев к этому
действию не требуется.
Что же касается еще одной матричной операции — матричного умноже-
ния — здесь ситуация сложнее. Во-первых, далеко не каждую пару матриц
можно перемножить. Кроме того, сама операция умножения требует подчас
весьма громоздких вычислений.
Определение 5 (произведение матриц) Пусть имеется матрица A ∈
Matr
m×p
и матрица B ∈ Matr
p×n
. Тогда их произведением AB (именно
в этом порядке, а не наоборот) называется матрица C ∈ Matr
m×n
, компо-
ненты которой вычисляются по следующим формулам:
c
ij
= a
i1
b
1j
+ a
i2
b
2j
+ ···+ a
ip
b
pj
.
Другими словами — для того, чтобы вычислить компоненту произведения,
находящуюся на месте с номером ij,нужноi-ю сторку первого множителя
умножить на j-й столбец второго множителя.
Пример 5 Перемножим две матрицы: первая имеет порядок 2×3, вторая — 3×2.
Согласно определению, результирующая матрица должна иметь порядок 2 × 2.
1 −12
311
11
10
2 −1
=
4 −1
62
.
Первое-первое место в произведении получается умножением первой строки пер-
вого множителя на первый столбец второго множителя:
1 ·1+(−1) · 1+2· 2=1− 1+4=4.
На первом-втором месте мы умножаем первую строку первого множителя на вто-
рой столбец второго множителя:
1 ·1+(−1) · 0+2· (−1) = 1 −2=−1 .
Второе-первое место получается умножением второй строки первого множителя
на первый столбец второго множителя:
3 ·1+1· 1+1· 2=3+1+2=6.
Наконец, второе-второе место — это произведение второй строки первого множи-
теля и второго столбца второго множителя:
3 ·1+1· 0+1· (−1) = 3 − 1=2.
Как видите, матричное умножение — весьма специфичная операция. Оно
зависит от порядка следования множителей, легко можно привести приме-
ры, когда умножение двух матриц невозможно, и, более того: есть ситуации,
когда произведение матриц в одном порядке возможно, а в обратном — нет.