истемы координат: мировая, объектная, наблюдателя и экранная.

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

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

Рис. 1 Объектная система координат и система координат наблюдателя

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

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

Рис.2 Картинная плоскость и экран

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

2. Отсечение (клиппирование) геометрических примитивов. Коды Сазерланда — Коэна. В компьютерной графике часто приходится решать задачу выделения некоторой области изображаемой сцены, причем задача эта может решаться как в применении к плоской области (если сцена уже спроецирована на картинную плоскость), так и к трехмерной. Алгоритмы отсечения применяются для удаления невидимых поверхностей и линий, для построения теней, при формировании текстур. Отсекаемая область может быть как правильной формы (прямоугольник или параллелепипед со сторонами, параллельными осям координат или координатным плоскостям), так и неправильной (произвольный многоугольник или многогранник). Для того чтобы эти алгоритмы можно было использовать в задачах изображения динамичных сцен, они должны быть эффективными в отношении времени вычислений. Мы рассмотрим несколько наиболее часто применяемых алгоритмов. Алгоритм Сазерленда-Коэна отсечения прямоугольной областью. Рассмотрим плоскую сцену, состоящую из отрезков различной длины и направлений, в которой надо выделить часть, находящуюся внутри прямоугольника. Прямоугольник задан списком ребер: <top>, <bottom>, <left>, <right>, отрезки также задаются координатами концевых точек. Область, отсекаемая окном (с учетом его границы), состоит из точек , удовлетворяющих соотношениям

(5.1)

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

Рис.1. Коды Сазерленда-Коэна для областей

Отрезок полностью невидим, если оба его конца лежат

1. справа от ребра ;
2. слева от ребра ;
3. снизу от ребра ;
4. сверху от ребра .

Во всех остальных случаях отрезок может (но не обязан) пересекать прямоугольное окно.

Для выполнения анализа полной видимости или невидимости отрезка А.Сазерленд и Д.Коэн предложили следующий алгоритм. Прямые, которым принадлежат ребра прямоугольника, разбивают плоскость на девять областей, каждой из которых присваивается четырехразрядный код. Каждый бит этого кода "отвечает" за одну из прямых: 1-й (старший) бит - за прямую , 2-й - за прямую , 3-й - за , 4-й - за . Если в коде области какой-либо бит установлен в 1, то это означает, что она отделена от окна соответствующей прямой. Схема идентификации областей приведена на рис.1.

Концевым точкам отрезков сцены теперь можно присвоить коды в зависимости от расположения точек. Ясно, что если коды обоих концов отрезка равны нулю, то отрезок полностью лежит внутри окна. Для дальнейшего анализа воспользуемся операцией логического умножения кодов (поразрядное логическое "И"). Тогда таблица истинности для кодов, согласно схеме на рис.1, будет выглядеть следующим образом:

Таблица1. Значения истинности для логического умножения кодов областей
	T	F	F	F	T	T	F	F
	F	T	F	F	F	F	T	T
	F	F	T	F	T	F	T	F
	F	F	F	T	F	T	F	T
	T	F	T	F	T	T	T	F
	T	F	F	T	T	T	F	T
	F	T	T	F	T	F	T	T
	F	T	F	T	F	T	T	T

Из сопоставления таблицы с рисунком видно, что если произведение кодов концов отрезка принимает значение T<rue>, то отрезок целиком лежит по одну сторону какой-то из прямых, причем внешнюю сторону по отношению к окну, следовательно, он полностью невидим. Во всех остальных случаях отрезок может частично лежать внутри окна, поэтому для определения их видимой части надо решать задачу о пересечении отрезков с ребрами окна. При этом желательно по возможности сократить число перебираемых пар "отрезок-ребро".

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

 

Клиппирование многоугольников

От задачи отсечения отрезков можно перейти к более сложной: клиппирование произвольных многоугольников. Если многоугольник невыпуклый, то в результате пересечения даже с прямоугольным окном может получиться несколько не связанных между собой фигур, как это показано на рис.8.

Рис.8. Отсечение невыпуклого многоугольника

Когда стоит задача штрихования замкнутой области одновременно с задачей отсечения, то важно правильно определить принадлежность вновь полученных фигур внутренней или внешней части исходного многоугольника. Пусть исходный многоугольник задан упорядоченным списком вершин , соответствующих ребрам . Для отсечения такого многоугольника прямоугольным окном можно применить алгоритм, предложенный Сазерлендом и Ходжменом. Идея его заключается в последовательном отсечении части многоугольника прямыми, соответствующими сторонам окна. Результатом его работы является упорядоченный список вершин, лежащих в видимой части окна. На каждом шаге алгоритма образуется некоторая промежуточная фигура, также представленная упорядоченным списком вершин и ребер. Пример таких последовательных отсечений показан на рис.9. В процессе отсечения последовательно обходится список вершин, причем каждая очередная точка за исключением первой рассматривается как конечная точка ребра, начальной точкой которого является предшествующая точка из списка. Порядок, в котором рассматриваются стороны окна, не имеет значения. В процессе обхода формируется список новых вершин многоугольника.

Рис.9. Последовательные шаги клиппирования произвольного многоугольника

астровое преобразование графических примитивов. Алгоритмы Брезенхема. Экран растрового дисплея можно рассматривать как матрицу дискретных элементов, или пикселей. Процесс определения пикселей, наилучшим образом аппроксимирующих некоторую геометрическую фигуру, называется разложением в растр, или построением растрового образа фигуры. Построчная визуализация растрового образа называется растровой разверткой данной фигуры. Алгоритм Брезенхема растровой дискретизации отрезкаПри построении растрового образа отрезка необходимо, прежде всего, установить критерии "хорошей" аппроксимации. Первое требование состоит в том, что отрезок должен начинаться и кончаться в заданных точках и при этом выглядеть сплошным и прямым (при достаточно высоком разрешении дисплея этого можно добиться). Кроме того, яркость вдоль отрезка должна быть одинаковой и не зависеть от наклона отрезка и его длины. Это требование выполнить сложнее, поскольку горизонтальные и вертикальные отрезки всегда будут ярче наклонных, а постоянная яркость вдоль отрезка опять же достигается на вертикальных, горизонтальных и наклоненных под углом в 45° линиях. И, наконец, алгоритм должен работать быстро. Для этого необходимо по возможности исключить операции с вещественными числами. С целью ускорения работы алгоритма можно также реализовать его на аппаратном уровне.

Рис. 1. Растровый образ отрезка

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

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

Теперь, считая, что - координаты текущей точки растрового образа, а - точное значение координаты точки отрезка, можно построить следующую точку:

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

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

Рис. 2. Связь углового коэффициента с выбором пикселя

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

Алгоритмы Брезенхема растровой дискретизации окружности и эллипса

Алгоритм изображения окружности несколько сложнее, чем построение отрезка. Мы рассмотрим его для случая окружности радиуса с центром в начале координат. Перенесение его на случай произвольного центра не составляет труда. При построении растровой развертки окружности можно воспользоваться ее симметрией относительно координатных осей и прямых . Необходимо сгенерировать лишь одну восьмую часть окружности, а остальные ее части можно получить путем отображений симметрии. За основу можно взять часть окружности от 0 до 45° в направлении по часовой стрелке с исходной точкой построения . В этом случае координата окружности является монотонно убывающей функцией координаты .

Рис. 7. Ближайший пиксель при движении по окружности

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

4. Закрашивание. Модели освещения.

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

Рис. 1. Эффекты восприятия изображения

Глаз адаптируется к средней яркости рассматриваемой сцены, поэтому при смене фона изменяется восприятие сцены. Например, однородно окрашенная область на более темном фоне будет казаться более яркой, чем на светлом. Кроме того, она будет восприниматься как более обширная (рис. 1).

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

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

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

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

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

Рис. 9.2. Освещение точечным источником

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

(1)

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

(2)

где - коэффициент диффузного отражения рассеянного света, - коэффициент диффузного отражения падающего света, .

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

(3)

где - расстояние до центра проекции, а - произвольная постоянная. Если центр проекции находится на бесконечности, т. е. при параллельном проецировании, то в качестве можно взять расстояние до объекта, наиболее близкого к наблюдателю.

Рис. 9.3. Зеркальное отражение

В отличие от диффузного, зеркальное отражение является направленным. Идеальное зеркало отражает лучи по принципу "отраженный и падающий лучи лежат в одной плоскости, причем угол падения равен углу отражения" (имеется в виду угол между направлением луча и нормалью к поверхности). Если поверхность не идеально зеркальная, то лучи отражаются в различных направлениях, но с разной интенсивностью, а функция изменения интенсивности имеет четко выраженный максимум. Поскольку физические свойства зеркального отражения довольно сложны, то в компьютерной графике используется эмпирическая модель Фонга. Суть ее заключается в том, что для глаза наблюдателя интенсивность зеркально отраженного луча зависит от угла между идеально отраженным лучом и направлением к наблюдателю (рис.3a). Кроме того, поскольку зеркальное отражение зависит еще и от длины волны, это также будем учитывать в формуле для вычисления интенсивности. Модель Фонга описывается соотношением

(4)

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

Рис. 4. Зеркальное отражение

Теперь модель освещенности, учитывающую зеркальное и диффузное отражения, можно описать формулой

(5)

Используя единичные векторы (направление к источнику) и (внешняя нормаль), косинус угла можно вычислить через скалярное произведение: . Для расчета интенсивности зеркального отражения сначала надо определить отраженный вектор . Из рис. 3b видно, что . С другой стороны является диагональю ромба , поэтому . Учитывая все эти соотношения, получаем формулу

(6)

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

Закраска граней плоское закрашивание

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

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

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

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

Рис. 5. Интерполяция интенсивности

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

(7)

После этого интенсивность в точке получаем путем интерполяции значений на концах отрезка:

(8)

К недостаткам метода Гуро следует отнести то, что он хорошо работает только с диффузной моделью отражения. Форма бликов на поверхности и их расположение не могут быть адекватно воспроизведены при интерполяции на многоугольниках. Кроме того, есть проблема построения нормалей к поверхности. В алгоритме Гуро нормаль в вершине многогранника вычисляется путем усреднения нормалей к граням, примыкающим к этой вершине. Такое построение сильно зависит от характера разбиения. Закраска методом Фонга Фонг предложил вместо интерполяции интенсивностей произвести интерполяцию вектора нормали к поверхности на сканирующей строке. Этот метод требует больших вычислительных затрат, поскольку формулы интерполяции (6)–(7) применяются к трем компонентам вектора нормали, но зато дает лучшую аппроксимацию кривизны поверхности. Поэтому зеркальные свойства поверхности воспроизводятся гораздо лучше.

Нормали к поверхности в вершинах многогранника вычисляются так же, как и в методе Гуро. А затем выполняется билинейная интерполяция в сочетании с построчным сканированием. После построения вектора нормали в очередной точке вычисляется интенсивность.

 

Рис.6. Три способа закрашивания

Этот метод позволяет устранить ряд недостатков метода Гуро, но не все. В частности, эффект полос Маха в отдельных случаях в методе Фонга бывает даже сильнее, хотя в подавляющем большинстве случаев аппроксимация Фонга дает лучшие результаты. На рис.6 приведены результаты закрашивания поверхности вращения, аппроксимированной многогранником, который составлен из треугольных граней: a) - плоское закрашивание, b) - закрашивание по методу Гуро, c) - закрашивание по методу Фонга. Первый из вариантов дает изображение ребристой поверхности с очень контрастными переходами от одной грани к другой. Вторая модель дает более гладкое изображение, но в районе бликов отчетливо наблюдаются линии ребер, хотя и сглаженные. Третий вариант получился наиболее гладким, зеркальные блики имеют достаточно реалистичную форму.