Математический аппарат, положенный в основу компьютерной графики, называют «компьютерная геометрия». С помощью компьютерной геометрии мы можем изменять масштаб изображений, вращать последние, смещать и трансформировать для улучшения наглядности перспективного изображения. Все эти преобразования можно выполнить на основе математических методов.

3 Компьютер выводит на экран предварительно подготовленное изображение, и наблюдатель не может непосредственно управлять изображением, прежде чем оно появится на экране. В каждом конкретном случае изображение может быть либо таким простым, как, например, графики простых функций, либо столь сложным, как визуализация результатов моделирования процесса автоматического полета и посадки самолета или космического корабля. В динамической интерактивной графике компьютер используется для подготовки и визуализации графических данных. Однако интерактивная графика позволяет наблюдателю в реальном масштабе времени влиять на весь процесс представления изображения.

Например рассмотрим задачу вращения объемного изображения, состоящего из 1000 линий, со скоростью 15 град/с. Как мы увидим в дальнейшем, картинка из 1000 линий в большинстве случаев представляется матрицей 1000 х 4 однородных координат конечных точек линий. Вращение, как правило, представляется путем умножения этой матрицы на матрицу преобразования размером 4x4. Для проведения такого матричного умножения требуется выполнить 16 тыс. операций умножения, 12 тыс. операций сложения и 1 тыс. операций деления вещественных чисел. Если умножение осуществляется программно, то для того чтобы выполнить все операции вращения, может потребоваться значительное время.

Для того, чтобы картинка на экране начала двигаться, она должна перерисовываться не менее 30 раз в секунду, то становится очевидным, что в случае с данным примером картинка не сможет непрерывно перемещаться по экрану. Существует множество способов достижения реального интерактивного режима визуализации изображения: использование более мощного дополнительного компьютера или более тщательное программирование, уменьшающее время выполнения матричного умножения. Однако в любом случае обязательно будет достигнут момент, когда всякое дальнейшее улучшение станет уже невозможным.

Уменьшение сложности изображения также не даст нужного эффекта, так как при этом может оказаться неприемлемым качество картинки. Однако операция матричного умножения, необходимая для манипулирования изображением из нашего примера, для действительно очень сложных картинок может осуществляться на уровне микропрограмм или с помощью специализированных цифровых умножителей, применение которых всегда было наиболее эффективным и экономичным.

Конечным результатом машинной графики является изображение, поэтому важно разобрать следующие вопросы: представление изображений в машинной графике; подготовка изображений для вывода; визуализация предварительно подготовленных изображений; взаимодействие с изображением. Под термином мы будем понимать множество линий, точек, текстов и т.п., выводимых на графическое устройство.

Многие алгоритмы интерпретируют изображения как набор многоугольников или ребер, причем каждый многоугольник или ребро в свою очередь может быть представлен с помощью точек (вершин). Таким образом, точки являются основными строительными блоками изображения. Не менее важны также и алгоритмы размещения таких точек P 1 (0,0) P 2 (1,0) P 3 (1,1) P 4 (0,1) E1E1 E2E2 E3E3 E4E4 S1S1 Для получения единичного квадрата можно: 1)Соединить точки P 1 P 2 P 3 P 4 P 1 ; 2)C помощью 4-х его ребер: E 1 =P 1 P 2, E 2 =P 2 P 3, E 3 =P 3 P 4, E 4 =P 4 P 1 ; 3) Использовать либо точки, либо ребра: S 1 = P 1 P 2 P 3 P 4 P 1 ; S 1 =E 1 E 2 E 3 E 4.

В конечном счете изображение определяется точками и алгоритмом их вывода. Прежде чем информация об изображении будет использована для формирования картинки, она хранится в файле, называемом базой данных. Для представления очень сложных изображений нужны сложные базы данных, для которых предполагается использование сложных алгоритмов организации доступа к ним. Точки - основные строительные блоки графической базы данных, именно поэтому особый интерес представляют основные операции преобразования точек.

Существуют три типа операций, в которых точки используются как графические примитивы: во-первых, перемещение пера и курсора, след курсора, невидимая точка; во-вторых, изображение линии между двумя точками; в третьих, вывод точки в заданном месте. В общем случае местоположение точки можно описать двумя способами: с помощью абсолютных и относительных координат (позиция точки определяется путем задания ее положения относительно предыдущей точки).

Местоположения точки могут быть описаны с помощью вещественных или целых чисел. В случае применения целых чисел возникает множество проблем, связанных с ограниченной длиной слова компьютера. Для представления целых координат, как правило, используется полное машинное слово. Наибольшее целое число, занимающее полное машинное слово и необходимое для представления величин со знаком из положительного и отрицательного диапазонов, равно 2^(n -1) - 1, где n - количество битов в слове. Для 16 битового слова это число равно Для многих приложений этого бывает вполне достаточно, однако возникают серьезные проблемы, когда требуются большие числа, которые невозможно представить с помощью одного слова компьютера.

Эту трудность можно преодолеть, например, воспользовавшись однородными координатами, что вызывают некоторые усложнения (уменьшение скорости выполнения и понижение качества разрешения изображения). Однако все эти недостатки оправдываются преимуществами, которые дают возможность представления больших чисел на компьютерах с ограниченной длиной слова.

В системе однородных координат n-мерное пространство представляется n + 1 измерением, т.е. трехмерные координаты, однозначно задаваемые тройкой (х, у, z), выражаются через четыре координаты (hx, hy, hz, h), где h - произвольный множитель. Если все координатное пространство в 16-битовом компьютере представляется числами меньше , то h будет равно 1, а координаты будут представляться путем прямых преобразований. Однако если хотя бы одна из координат превышает число , например, х = , то преимущества использования однородных координат становятся очевидны. В данном случае мы установили h = 1/2 и координаты точки теперь можно представить в 16- битовом компьютере как (30 000, у/2, z/2, 1/2).

Данные, используемые для подготовки рисунка, как правило, не совпадают с данными, необходимыми для его визуализации. Выводимое изображение обычно формируется путем поворота, переноса, масштабирования и вычисления различных проекций. Эти преобразования обычно выполняются с помощью матричных операций (4 х 4) с данными, представленными в однородных координатах. Удаление невидимых линий или поверхностей, закраска, определение прозрачности, текстуры или световые эффекты - все эти операции могут быть выполнены еще до момента окончательной визуализации изображения.

Если выводимое изображение определено не на всей базе данных, в ней необходимо выделить некоторую часть, соответствующую этому изображению. Данный процесс называется отсечением. Отсечения бывают дву- и трехмерные. В ряде случаев окно и объем отсечения могут иметь отверстия или быть неправильной формы. Стандартное отсечение по границам дву- или трехмерных областей часто реализуется аппаратно.

Линия частично внутри окна: часть a-b выводится, часть b-с не выводится Линия полностью внутри окна: линия выводится целиком Линия частично внутри окна: часть b-с выводится, части a-b и c-d не выводятся Линия полностью вне окна: не выводится a b c d a b c Рис. Двумерное отсечение.

Рис. Трехмерная пирамида видимости. N F SR SB SL ST В трехмерном пространстве отсекающий объем представляет собой прямоугольный параллелепипед (брус) или, для перспективных видов, усеченную пирамиду (пирамиду видимо- видимости). На рис. показана типичная пирамида видимости, ближайшая к наблюдателю грань помечена символом N, наиболее удаленная - символом F, а стороны образованы гранями SL, SR, ST и SB.

После того как изображение на экране построено, возникает необходимость как-то взаимодействовать с ним или модифицировать его. Для этого был разработан ряд диалоговых устройств. Среди них можно назвать планшет, световое перо, рычаг, мышь, ручки для ввода скалярных величин, функциональные переключатели или кнопки и, алфавитно-цифровую клавиатуру.

Точка может задаваться в виде вектор-столбца: - в двумерном пространстве, - в трехмерном пространстве. Обычно задача ставится следующим образом: Но в машинной графике требуется определить элементы матрицы.

Пусть у нас есть точка P с координатами (x,y), после преобразований мы получаем точку P с координатами (x,y ) * * * d=1, b=c=0 b=c=0 a=-1, d=1, b=c=0

a=1, d=-1, b=c=0 a=d=1, c=0 a=d=1, b=0 Недиагональные члены матрицы преобразования создают эффект сдвига координат вектора точки Р

Прямую линию можно определить с помощью двух векторов, задающих координаты ее конечных точек. Расположение и направление линии, соединяющей две эти точки, может изменяться в зависимости от положений векторов. Рис. Преобразование отрезков.

Поворот треугольника ABC на 90 градусов против часовой стрелки относительно начала координат Поворот треугольника ABC на угол против часовой стрелки относительно начала координат достигается путем следующих преобразований 180 градусов 270 градусов 90 градусов

Поворот вокруг точки начала координат на произвольный угол. длина вектора, угол между вектором и осью х.

Отражение представляет собой поворот на угол 180° в трехмерном пространстве и обратно на плоскость относительно оси, лежащей в плоскости ху. Отражение относительно прямой у = х осуществляется с помощью матрицы: Отражение относительно оси х (y=0) будет иметь вид: У 2-х последних матриц определитель равен -1. В общем случае, если определитель матрицы преобразования равен -1, то преобразование дает полное отражение. Отражение относительно оси y (x=0) будет иметь вид: Отражение относительно прямой у = -х осуществляется с помощью матрицы:

1) Отобразим треугольник ABC относительно оси х, а затем относительно прямой у = - х. 2) Повернем треугольник ABC относительно начала координат на угол 270° ABC= Если оба полных отражения осуществляются последовательно относительно прямых, проходящих через начало координат, то результатом будет полный поворот относительно начала координат.

Масштабирование Величина масштабирования определяется значением элементов исходной диагональной матрицы. Если матрица используется в качестве оператора воздействия на вершины треугольника, то имеет место расширение или равномерное масштабирование относительно точки начала координат. Если значения элементов не равны, то треугольник искажается, что проиллюстрировано на рис. Рис. Пропорциональное и непропорциональное масштабирование (искажение).

Рис. Пропорциональное масштабирование без явного перемещения. Масштабирование В общем случае При a=d, b=c=0, выполняется пропорциональное масштабирование; если а d, b=с=0, то масштабирование будет проведено непропорционально. В первом случае для а=d>1 происходит расширение, т. е. увеличение изображения. Если а=d

Возникает необходимость изменять положение начала координат, т.е. преобразовывать каждую точку на плоскости. Этого можно достичь путем перемещения точки начала координат или любой другой точки на плоскости х* = ах + су + m, у* = bx + dy + n. К сожалению, нельзя ввести константы перемещения m и n в (2 х 2)-матрицу преобразования, так как это не пространство! Данное затруднение можно преодолеть, используя однородные координаты.

Матрица преобразования для однородных координат имеет размер 3 х 3. В частности, где действие элементов а, b, с и d верхней части (2 х 2)-матрицы точно соответствует действиям, рассмотренным ранее. Элементы тип являются коэффициентами перемещения в направлениях х и у соответственно. Полная двумерная матрица преобразования имеет вид

Напомним, что a, b, с и d - коэффициенты масштабирования, вращения, отражения и сдвига соответственно. Элементы m и n задают перемещение. Ранее коэффициенты имели значения p = q = 0, s=1. Установим величины р и q не равными 0. Какой эффект мы получим?

Для отрезка АВ из рис. имеем р = q = 1, [А] = [1 3 1] и [В]=[4 1 1]. А В С D С*С* D* Рис. Преобразование из физической плоскости (h = 1) на плоскость h = 1 и проецирование обратно на физическую плоскость. h=1

Таким образом, [С] =[1 3 5] и [D] = [4 1 6] на плоскости h=x+y+1. Проецируя обратно на плоскость h = 1 путем деления на коэффициент однородных координат, проведем двумерное преобразование точек [С*]=[1 3 5] = [1/5 3/5 1], [D*] = [4 1 6] = [2/3 1/6 1].

Оставшийся необъясненным элемент s (3 х 3)-матрицы преобразования соответствует пропорциональному масштабированию, при котором все компоненты вектора изменяются пропорционально. Покажем это, рассмотрев следующее преобразование: где X = х, Y = у и h = s. После нормализации получим X* = x/s и Y* = y/s. Таким образом, преобразование [х у 1] [T] = [x/s y/s 1] является равномерным масштабированием координатного вектора. Если s 1 - сжатие.

Рис. Геометрическая интерпретация пропорционального масштабирования.

Рассмотрим трехмерную декартовую систему координат. Известно, что точка в трехмерном пространстве описывается радиус-вектором r и координатами (x y z). Для реализации трехмерных преобразований с помощью матриц необходимо перейти к однородным координатам (x y z 1). Тогда матрица трехмерного преобразования А (переноса, масштабирования, поворота) в общем виде будет следующей:

где матрица B осуществляет линейное преобразование в виде изменения масштаба, сдвига и вращения, вектор производит перенос объекта, а вектор-столбец – преобразования в перспективе. Скалярный элемент выполняет общее изменение масштаба. Матрица трехмерного переноса при этом

Операция масштабирования (частичная) Трехмерный сдвиг Недиагональные элементы матрицы B осуществляют сдвиг в трех измерениях, т.е.

Трехмерное вращение Матрицы поворота вокруг осей координат имеют вид: OzOz Ox Oy

Обратные преобразования будут выражаться обратными матрицами. Для операции переноса надо лишь заменить знаки компонент вектора переноса на противоположные: для операции масштабирования – на обратные значения: для поворота – выбором отрицательного угла поворота: Результатом нескольких последовательных поворотов будет матрица Здесь верхняя матрица размером 3x3 является ортогональной. Матрицы поворота сохраняют длину и углы, а матрицы масштабирования и сдвига – нет.

Рассмотрим проблему ускорения вычислений в одной из самых трудоемких операций компьютерной графики – операции поворота точки относительно начала координат. Для выполнения этой операции необходимо произвести 4 операции умножения, 2 операции сложения, а также вычислить значения синуса и косинуса угла поворота: Среди наиболее часто встречающихся способов ускорения операции поворота – отказ от вычисления синуса и косинуса угла во время выполнения программы и использование их заранее подсчитанных значений, которые занесены в специальную таблицу (табличный поворот).

Дополнительным способом ускорения операции поворота является уменьшение количества операций умножения. Таким способом является применение формулы О. Бьюнемана, в которой поворот точки вокруг начала координат производится за 3 операции умножения и 3 операции сложения.

Рис. Растеризация отрезка прямой линии

Простейшие пошаговые алгоритмы построения отрезка с помощью известного уравнения прямой имеют ряд недостатков, связанных с выполнением операций с вещественными числами и накоплением ошибок округления. Эти недостатки устранены в следующем алгоритме Брезенхейма, в котором не используются вещественные числа, а требуются минимальные арифметические возможности: сложение, вычитание и умножения на 2 для сдвига влево. Рис. i-й шаг алгоритма по методу Брезенхема (а). Вид отрезка после переноса в начало координат (б) а) б)

Задача удаления невидимых линий и поверхностей является одной из наиболее сложных задач в компьютерной графике. Для решения данной задачи были разработаны специальные алгоритмы, целью которых является удаление тех линий ребер, поверхностей, граней или объемов, которые невидны наблюдателю. Идея алгоритмов удаления невидимых линий и поверхностей заключается в следующем: чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен другим, более близким к наблюдателю, объектом. После определения расстояний или приоритетов по глубине проводится сортировка по горизонтали и по вертикали, для выяснения, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения.

Выделяют три класса таких алгоритмов: Алгоритмы, работающие в пространстве объекта. Для определения видимости данной поверхности сравнивается ее взаимное расположение с остальными поверхностями объекта в трехмерной сцене. –Алгоритм Робертса. Алгоритмы, работающие в пространстве изображения (экрана). Они основаны на нахождении точки ближайшей поверхности, которую пересекает луч зрения, проходящий через заданную точку на растре. –Алгоритм плавающего горизонта; –Алгоритм Коэна – Сазерленда; –Модифицированный вариант алгоритма Коэна – Сазарленда;

–Алгоритм с использованием z-буфера; –Метод трассировки лучей; –Алгоритм Варнока; –Алгоритм Вейлера – Азертона. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих системах координат (объекта и изображения). –Алгоритм Ньюэла – Ньюэла–Санча (алгоритм удаления невидимых граней методом сортировки по глубине;)

Алгоритм Робертса удаляет из каждого тела те ребра или грани, которые скрываются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, скрываются этими телами. При этом вычислительная трудоемкость алгоритма Робертса растет теоретически, как квадрат числа объектов. При этом математические методы, используемые в этом алгоритме, просты, мощны и точны.

Алгоритм плавающего горизонта чаше всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде F(x, у, z) = 0. Идея метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координаты z. Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т.е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y. Если на текущей плоскости при некотором заданном значении x соответствующее значение у на кривой больше значения y для всех предыдущих кривых при этом значении x, то текущая кривая видима в этой точке; в противном случае она невидима.

Алгоритм Коэна – Сазерленда предназначен для отсечения отрезков. Он был разработан Дэном Коэном и Айвеном Сазерлендом в Гарварде в 1966–1968 гг. Алгоритм разделяет плоскость на девять частей прямыми, которые образуют стороны прямоугольника. Каждой из девяти частей присваивается четырехбитный код. Окну присваивается код Конечным точкам отрезка приписывается 4-битный код вне/внутри в зависимости от нахождения отрезка в соответствующей подобласти. Каждому биту присваивается значение 1 в соответствии со следующим правилом. Бит 1 – точка находится выше окна; Бит 2 – точка находится ниже окна; Бит 3 – точка находится справа от окна; Бит 4 – точка находится слева от окна; Иначе биту присваивается нулевое значение.

Алгоритм определяет код конечных точек отрезка. Если оба кода равны нулю И, то отрезок полностью находится в прямоугольнике. Если битовое И кодов не равно нулю, то отрезок не пересекает прямоугольник (так как это значит, что обе конечные точки отрезка находятся с одной стороны прямоугольника). В прочих случаях алгоритм выбирает конечную точку, находящуюся вне прямоугольника, находит ближайшую к ней точку пересечения отрезка с одной из линий, образующей стороны прямоугольника, и использует эту точку пересечения как новую конечную точку отрезка. Укороченный отрезок снова пропускается через алгоритм. Рис. Разбиение на подобласти в методе Коэна – Сазерленда

Рассмотрим алгоритм удаления невидимых граней с использованием z-буфера, который является одним из наиболее часто используемых в современных приложениях компьютерной графики. Впервые он был предложен Кэтмулом. Он работает в пространстве изображения и применяется в таких популярных графических библиотеках, как OpenGL и Direct3D. Алгоритм работает в параллельной проекции. Пусть размеры окна вывода или экрана составляют X точек в ширину и Y точек в высоту. В качестве z-буфера заведем двумерный прямоугольный массив чисел по размерности совпадающий с окном вывода или экрана, т.е. XxY. В z-буфере будут храниться текущие значения z-координат каждого пиксела.

В начале работы алгоритма в z-буфер заносятся значения, соответствующие бесконечности. Каждая грань трехмерного объекта, представленная в виде многоугольника, преобразуется в растровую форму. При разложении в растр для каждой точки многоугольника вычисляется значение ее z-координаты. Если z- координата оказалась меньше, чем текущее значение в z- буфере, то в z-буфер заносится z-координата точки, и на экране рисуется точка цветом текущего многоугольника. После разложения в растр всех многоугольников изображение трехмерной сцены построено. Рассмотрим способ ускоренного вычисления z-координат при разложении многоугольников в растр. Запишем уравнение плоскости, образуемой многоугольником в пространстве:

Выразим z-координату точки:. Пусть. Найдем z-координату для соседней точки Для соседнего пиксела на экране, тогда, отсюда следует, что. Таким образом, вычисление z-координаты соседнего пиксела сводится к одной операции вычитания.

Рассмотрим далее алгоритм удаления невидимых граней методом сортировки по глубине (авторы: Ньюэлл, Ньюэлл, Санча). Часть этого метода работает в пространстве объекта, а часть в пространстве изображения. Он также работает для параллельной проекции, то есть с учетом того, что произведено перспективное преобразование. Введем определение пространственной оболочки. Пространственной оболочкой трехмерного объекта называется минимальный прямоугольный параллелепипед, целиком содержащий внутри себя данный объект. Аналогично можно определить двумерную и одномерную пространственные оболочки.

Метод состоит из трех основных шагов: 1.Упорядочение всех многоугольников в соответствии с их наибольшими z-координатами. 2.Разрешение всех неопределенностей, которые возникают при перекрытии z-оболочек многоугольников. 3.Преобразование каждого из многоугольников в растровую форму, производимое в порядке уменьшения их наибольшей z- координаты. Ближайшие многоугольники преобразуются в растровую форму последними и закрывают более отдаленные многоугольники, так как изображаются поверх предыдущих.

В компьютерной графике для расчета освещенности граней объектов применяется цветовая модель RGB. Интенсивность отраженного света точек объектов вычисляют отдельно для каждой их трех составляющих цветовых компонент, а затем объединяют в результирующую тройку цветов. При расчете освещенности граней применяют следующие типы освещения и отражения света от поверхностей. 1.рассеянное; 2.диффузное; 3.зеркальное. Рис. Расчет интенсивности отраженного света

Матовые поверхности обладают свойством диффузного отражения, т. е. равномерного по всем направлениям рассеивания света. Поэтому кажется, что поверхности имеют одинаковую яркость независимо от угла обзора. Зеркальное отражение можно получить от любой блестящей поверхности. Но блестящие поверхности отражают свет неодинаково по всем направлениям. От идеального зеркала свет отражается только в том направлении, для которого углы падения и отражения совпадают. Это означает, что наблюдатель сможет увидеть зеркально отраженный свет только в том случае, если угол (рис.) равен нулю. Для неидеальных отражающих поверхностей, таких как яблоко, интенсивность отраженного света резко падает с ростом.

Интенсивность освещения граней трехмерных объектов рассеянным светом считается постоянной в любой точке пространства. Она обусловлена множественными отражениями света от всех объектов в пространстве. При освещении трехмерного объекта рассеянным светом интенсивность отраженного света вычисляется как, где – интенсивность падающего света, - коэффициент рассеянного отражения, зависит от отражающих свойств материала грани. Для расчета интенсивности диффузного отражения света может применяться закон косинусов Ламберта:, где – угол падения, рассчитывается как угол между направлением на источник света и нормалью к поверхности. Пусть направление на источник света представлено единичным вектором, а – единичный вектор нормали. Тогда – скалярное произведение векторов. Тогда, где – коэффициент диффузного отражения.

Вычисление зеркально отраженного света производится также с помощью различных эмпирических моделей, которые позволяют учитывать реальную шероховатость поверхностей. Например, в модели, предложенной Фонгом, интенсивность зеркально отраженного света рассчитывается в зависимости от степени отклонения от истинного значения вектора зеркально отраженного луча света. Пусть – вектор зеркально отраженного луча света, а – вектор, определяющий направление на наблюдателя. Тогда интенсивность зеркально отраженного света по модели Фонга рассчитывается так: где – угол между векторами и. Константа n – может принимать значения от 1 до 200, в зависимости от отражающей способности материала. Большим значениям n соответствует большая степень гладкости или зеркальности поверхности. Если векторы и – нормированы, то формула преобразуется к виду:

Интенсивность отраженного света уменьшается обратно пропорционально квадрату расстояния от источника до наблюдателя. Поэтому можно записать формулу расчета интенсивности отраженного луча света для трех составляющих: рассеянного, диффузного и зеркального отражения с учетом расстояния: где r – расстояние от точки отражения до наблюдателя, а – некоторая константа. Иногда, для ускорения вычислений, берут не вторую, а первую степень расстояния r.