Основы компьютерной графики

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

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

Лекция 4. Трехмерная компьютерная графика

4.1. Трехмерные примитивы

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

- точки в пространстве;

- пространственные линии и отрезки линий;

- поверхности;

- многогранники;

- геометрические тела сложной формы.

Для синтеза реалистичных изображений кроме геометрии объектов необходимо также моделировать распространение света, что заставляет задавать и использовать ряд физических свойств объектов и всей пространственной сцены. К ним относятся расположение и яркость источников света, цвета и степень зеркальности (гладкости) поверхностей объектов, коэффициенты преломления света на границах прозрачных сред, степень их прозрачности и др.

Геометрия трехмерных примитивов, как и двумерных, описывается алгебраическим и параметрическим методами. Ниже в качестве примитивов будут рассмотрены точки, линии, поверхности и многогранники.

Tочка P в пространстве задается своими координатами (x, y, z). В трехмерной компьютерной графике традиционно используют левостороннюю систему координат, показанную на рис. 4.1. Причем изображение строится на плоскости OXY, называемой картинной плоскостью. На нее проецируются изображаемые объекты.

На рис. 4.1 Pr (P) означает проекцию точки P на картинную плоскость. Часть этой плоскости, соответствующая экрану монитора, обозначена как Scr.

Для задания линий в пространстве используется алгебраическая и параметрическая формы.

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

(4.1)

Пространственные кривые в параметрической форме отличаются от плоских, рассмотренных в п. 2.3, 2.4, лишь тем, что изменение координаты z задается третьей функция z (t):

(4.2)

Формулы и выводы, приведенные в п. 2.3, 2.4, несложно модифицировать для описания кубических сплайнов и кривых Безье в пространстве.

Поверхности, как и линии, задаются в алгебраической и параметрической формах. Алгебраическая поверхность описывается уравнением вида F (x, y, z) = 0. Например, уравнение сферической поверхности с центром в начале координат и радиусом R имеет вид

x ² + y ² + z ² – R ² = 0. (4.3)

В параметрической форме задаются четырехугольные куски S (u,v)произвольных гладких поверхностей (рис. 4.2). Закон изменения каждой из координат поверхности должен быть описан своей функцией от двух параметров u и v:

(4.4)

Как и для параметрических кривых, в качестве области изменения параметров u и v обычно используют интервал [0, 1], т.е. 0 £ u £ 1, 0 £ v £ 1.

Рис. 4.2

При интерактивном синтезе параметрических поверхностей для функций x (u, v), y (u, v) и z (u, v) используют те же полиномиальные базисы, что и в двумерной графике. Разработаны математическая теория и алгоритмы для создания полиномиальных кубических поверхностей, поверхностей Безье и других видов полиномиальных сплайн-поверхностей [7, 8].

В то же время для задания некоторых видов поверхностей удобнее использовать другие базисы. Так, особым классом поверхностей являются поверхности вращения [7]. Поверхностью вращения называется поверхность, образованная вращением плоской кривой вокруг неподвижной оси, лежащей в одной плоскости с кривой. Например, функция

(4.5)

определяет поверхность, описанную вращением кривой P (u)= [ x (u) z (u)], заданной в плоскости OXZ, вокруг оси OZ (рис. 4.3).

Рис. 4.3

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

(4.6)

Отметим, что параметры u и v определяют на поверхности географическую систему координат, в которой u является долготой, а v – широтой. Полюса этой сферы расположены на оси OZ.

4.2. Аппроксимация криволинейных поверхностей

Представление криволинейной поверхности в параметрической форме S (u, v) позволяет визуализировать ее с любой точностью и детальностью. Однако прямые вычисления значений функций x (u, v), y (u, v) и z (u, v) в общем случае весьма трудоемки, поэтому при разработке быстрых алгоритмов визуализации параметрические поверхности предварительно подвергают полигональной аппроксимации, т.е. криволинейную поверхность заменяют многогранной поверхностью из плоских многоугольников. Общепринято аппроксимировать криволинейные поверхности плоскими треугольниками. На рис. 4.4 показан результат такой аппроксимации для поверхности, изображенной на рис. 4.2.

Рис. 4.4

Основная процедура аппроксимации состоит в расчете узловых точек поверхности S (u, v), т.е. точек, которые будут использоваться в качестве вершин аппроксимирующих треугольников. Для этого выполняют табуляцию S (u, v) по обоим параметрам u и v. Шаги табуляции D u иD v чаще выбирают постоянными. В итоге заполняется двумерный массив V координат узловых точек. Элемент V [ i, j ] массива – это координаты (x, y, z) точки поверхности S (u, v), вычисленные для значений параметров u = i D u и v = j D v.

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

4.3. Многогранники и сложные объекты

Кусок параметрической поверхности S (u, v) может быть замкнутым. Примером может служить сфера. После аппроксимации замкнутой поверхности получится поверхность, ограничивающая геометрическое тело в виде многогранника. Многогранники часто выделяются в самостоятельный вид трехмерных примитивов. Произвольный многогранник Mg, ограниченный n гранями, описывается списком граней, т.е. плоских многоугольников:

Mg = (G ₁, G ₂, …, G_n).(4.7)

Каждая грань G_i в свою очередь задается упорядоченным списком вершин:

G_i = (P_{i 1}, P_{i 2}, …, P_im). (4.8)

Частным случаем многогранников являются правильные многогранники, т.е. многогранники с одинаковыми гранями в виде правильных многоугольников [4]. Примером правильных многогранников является гексаэдр, обычно называемый кубом
(рис. 4.5). Его геометрия задается одним параметром – длиной ребра.

Правильные многогранники вписываются в сферическую поверхность. Характеризуются количеством n граней и числом m сторон граней. Всего существует лишь пять видов правильных многогранников, называемых также Платоновыми телами: тетраэдр (n = 4, m = 3), гексаэдр (n = 6, m = 4), октаэдр (n = 8, m = 3), икосаэдр (n = 20, m = 3), додекаэдр (n = 12, m = 5). Для описания правильного многогранника достаточно задать координаты (x_c, y_c, z_c) центра и радиус R описанной сферической поверхности, а также значения m и n. Для каждого вида правильных многогранников существуют свои алгоритмы расчета координат вершин по этим данным [4].

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

Очевидным подходом к описанию сложного геометрического объекта по аналогии с многогранниками является представление его поверхности списком граней S = (G ₁, G ₂, …, G_m). Описание каждой грани G_i в свою очередь должно включать описание поверхности, частью которой является грань, и описание граничного контура, т.е. отрезков всех линий пересечения данной грани со смежными гранями. Однако независимое конструирование граней для сборки их в одну поверхность с гарантией их точного сопряжения трудно реализовать практически, что и ограничивает применение этого подхода.

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

4.4. Свет и цвет

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

Для правильного понимания физической сущности природы света кратко рассмотрим основные светотехнические величины и единицы измерения [1].

Световой поток F характеризует мощность светового излучения, проходящего на элемент поверхности площадью S, освещаемый источником света. Измеряется в люменах (лм). Полный световой поток F_c равен мощности светового излучения сквозь произвольную замкнутую поверхность, охватывающую источник света.

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

, (4.9)

где w – телесный угол с центром в источнике света.

Для точечного источника света, излучающего свет равномерно по всем направлениям, сила света находится как

. (4.10)

Единица измерения силы света называется канделла (кд, [кд] = [лм/ср]).

Освещенностью E элемента поверхности называется отношение приходящегося на нее светового потока dF к ее площади dS:

. (4.11)

Единица измерения освещенности называется люкс (лк, [лк] = [лм/м²]).

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

, (4.12)

где dS – площадь проекции элемента светящейся поверхности. Яркость измеряется в единицах кд/м².

В компьютерной графике наиболее популярной моделью представления света является аддитивная модель, сокращенно обозначаемая как RGB [3]. Это обозначение образуется начальными буквами трех основных цветов: красного (r ed), зеленого (g reen) и синего (b lue). В аддитивной модели считается, что любой свет образуется за счет смешения трех основных цветовых составляющих – красной, зеленой и синей. Отметим, что смешение света трех основных цветов используется и при формировании изображения на экране мониторов.

При использовании RGB модели обозначать яркость источника света, как и в физике, буквой B неудобно, поскольку она же используется для обозначения синего цвета, поэтому, как и в большинстве публикаций по компьютерной графике, для обозначения яркости в дальнейшем будем использовать букву E. Тогда в аддитивной модели источник света будет характеризоваться цветовыми составляющими – красной E_R, зеленой E_G и синей E_B. Яркость источника белого света можно задавать одной величиной E. При этом считается, что яркости всех трех цветовых компонент белого света равны друг другу.

Основными видами идеализированных источников света являются точечный и бесконечно удаленный.

Точечный источник света помимо цветовых компонент яркости характеризуется еще координатами (x_e, y_e, z_e) его расположения. В этом случае для всякой точки (x, y, z) освещаемой поверхности направление излучаемого света определяется координатами источника и этой точки. Бесконечно удаленный источник света излучает параллельные лучи света, направление которых всюду определяется вектором V_e = (v_xe, v_ye, v_ze).

Еще одно отличие компьютерной графики от физики состоит в том, что яркость моделируемых источников света, как правило, задается не в физических, а в относительных единицах. Обычно используется ограниченный диапазон целых чисел, например 0..255, используемый при кодировании компонент цвета в RGB модели.

Зрение основано на том, что свет от источников освещает поверхности предметов, которые частично отражают его. Часть отраженного света попадает в глаз, что позволяет сформировать представление о геометрии предметов и цвете их поверхностей. Этот же принцип используется в фото– и видеоаппаратуре, а также при машинном синтезе изображений виртуальных сцен, поэтому для компьютерной графики наиболее важной физической характеристикой поверхности является ее цвет, который характеризует отражательную способность поверхности в разных областях спектра белого света. В цветовой модели RGB цвет поверхности также задается цветовыми компонентами R, G и B, но, в отличие от света, значения R, G и B характеризуют отражательную способность поверхности соответственно для красной, зеленой и синей составляющих света. В компьютерных программах значения R, G и B для вычислений удобнее задавать в диапазоне от 0 до 1 или в процентах.

Кроме RGB используются и иные цветовые модели с другими методами образования необходимых цветов из фиксированного набора основных. Так, в субтрактивной модели CMY тоже используются три основных цвета – голубой (c yan), пурпурный (m agenta) и желтый (y ellow) [1, 3]. Эти цвета считаются дополнительными соответственно к красному, зеленому и синему цветам модели RGB, т.е. могут быть получены вычитанием из белого соответственно красного, зеленого и синего цветов. Модель CMY первоначально использовалась в полиграфии при печати цветных изображений на белой бумаге, поскольку она хорошо отражает получение новых цветов при смешивании красок.

Модификацией CMY является расширенная субтрактивная модель, обозначаемая как CMYK. В этой модели используется еще один цвет – черный, а буква K в обозначении соответствует последней букве в слове black – черный. Добавление черного цвета связано с тем, что смешиванием красок трех дополнительных цветов трудно добиться чисто черного цвета.

Существуют соотношения, позволяющие преобразовывать CMYK -модель в RGB и наоборот [1].

4.5. Диффузная модель распространения света

Диффузная модель распространения света [6, 8] является одной из наиболее простых. В ней поверхности тел рассматриваются как идеальные рассеиватели света, рассеивающие падающий на них свет равномерно по всем направлениям. Тогда согласно закону Ламберта (закон косинусов) яркость света, отражаемого в направлении плоскости проекции (в направлении наблюдателя), пропорциональна косинусу угла между нормальным вектором N к поверхности и вектором L направления на источник света (рис. 4.7).

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

Если рассматривается бесконечно удаленный источник света, то L = – V_e. При точечном источнике света вектор L для каждой точки P поверхности S приходится рассчитывать через координаты этой точки и координаты источника.

Косинус угла между нормальным вектором N к поверхности и вектором L можно найти как скалярное произведение этих векторов после приведения их к единичной длине (нормирования).

Нормальный вектор N к поверхности, заданной уравнением
F (x, y, z) = 0,находится с помощью частных производных:

(4.13)

Выполним его нормирование:

(4.14)

Здесь d – евклидова норма (длина) вектора N, которая находится следующим образом:

(4.15)

Будем считать, что вектор L уже нормирован. Скалярное произведение векторов N' и L обозначается как (N' ∙ L) и вычисляется по формуле

(4.16)

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

(4.17)

(4.18)

(4.19)

Переменная E ₀ в формулах (4.17) – (4.19) обозначает яркость рассеянного белого света. В данной модели она упрощенно учитывает тот факт, что в реальной действительности кроме направленных лучей света, падающих от источников, всегда присутствует свет, равномерно рассеянный по разным направлениям. Рассеяние света происходит как в среде распространения света (обычно в воздухе), так и за счет многократного отражения света от поверхностей окружающих предметов. Составляющая E ₀позволяет регулировать контрастность формируемого изображения.

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

E_re = E /(d + c), (4.20)

где c – постоянная, задаваемая опытным путем. Формула применима как для белого, так и для компонент цветного света.

Следует отметить, что при разработке программ значения E, E_R, E_G, E_B, E ₀ можно задавать как реальные физические величины в соответствующих единицах измерения яркости, но при выводе изображения вычисленные величины I_R, I_G, I_B должны быть приведены путем нормирования к диапазону значений в используемой цветовой палитре компьютера. В силу сказанного в программах трехмерной графики яркости источников и рассеянного света чаще задают в условных единицах.

4.6. Зеркальное отражение света

В диффузной модели предполагалось, что свет, падающий от источников на поверхности объектов, отражается равномерно по всем направлениям, в том числе и в направлении плоскости проекций. Эта модель хорошо соответствует реальным объектам с матовой поверхностью, однако поверхности многих предметов, особенно металлических, обладают ярко выраженными зеркальными свойствами. Для них наибольшая доля света рассеивается от поверхности в соответствии с законом зеркального отражения: угол падения равен углу отражения (рис. 4.8). Модели распространения света, учитывающие зеркальные свойства поверхностей, называются рефлексными [8].

На рис. 4.8 L – вектор направления на источник света; N – нормальный вектор к поверхности.

Рис. 4.8

Яркость света, отраженного в направлении V плоскости проекции, зависит от величины угла α между вектором V_r направления зеркального отражения и вектором V. Эта зависимость различна для разных материалов и гладкости их поверхности. Для реальных материалов она определяется экспериментально. При машинном же синтезе изображений виртуальных объектов для качественного моделирования зеркальности чаще используют эмпирические модели. Так, в рефлексной модели, предложенной Фонгом [1, 5], интенсивность света, отраженного в направлении вектора V, считается пропорциональной величине сos ⁿ α, где n – коэффициент зеркальности. На практике значение n выбирают в диапазоне 1 – 200.

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

(4.21)

(4.22)

(4.23)

Формулы (4.21) – (4.23) отражают обе модели распространения света – диффузную и рефлексную.

4.7. Трехмерные геометрические преобразования

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

В общем виде линейное трехмерное преобразование с матрицей W в однородных координатах x, y, z, v представляется следующим образом:

(4.24)

Здесь C = [ x y z 1] – матрица исходных координат; C’ = [ x' y' z' v ] – матрица новых координат после преобразования.

Важно иметь в виду, что значение координаты v остается равным 1 только в таких преобразованиях, для которых w ₁₄, w ₂₄, w ₃₄ = 0 и
w ₄₄ = 1. В противном случае для перехода к обычной системе координат необходимо выполнить пересчет:

x = x' / v; y = y' / v; z = z' / v. (4.25)

Приведем формулы для основных видов геометрических преобразований в пространстве.

Преобразование перемещения

(4.26)

Здесь m_x, m_y, m_z – составляющие перемещения по соответствующим осям.

Преобразование масштабирования относительно начала координат

(4.27)

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

Преобразование поворота относительно оси OX на угол φ

(4.28)

Преобразование поворота относительно оси OY на угол φ

(4.29)

Преобразование поворота относительно оси OZ на угол φ

(4.30)

Стоит отметить, что формула (4.5) в п. 4.1 для поверхности вращения получена путем применения преобразования вращения вокруг оси OZ к кривой, заданной параметрической функцией P (u).

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

4.8. Проецирование трехмерных объектов

Целью визуализации является синтез изображения в виде проекции объектов пространственной сцены, поэтому проецирование является важным этапом процесса визуализации. Это преобразование каждой точке P поверхности ставит в соответствие ее проекцию, т.е. точку Pr (P) на плоскости проекций.

Обычно используют один из двух следующих видов проецирования – параллельное и центральное (перспективное).

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

В системе однородных координат ортогональное проецирование на плоскость OXY представляется как преобразование координат C = [ x y z 1] с вырожденной матрицей преобразования:

(4.31)

Рис. 4.9

Практически же, как это следует из (4.31), для получения координат C' точек Pr (P) проекции в данном случае достаточно отбросить координаты z проецируемых точек P.

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

Центральное проецирование применяется при синтезе изображений пространственных сцен большой протяженности. В этом виде проецирования учитывается то, что в реальном мире видимые размеры объектов уменьшаются при удалении от наблюдателя пропорционально расстоянию (рис. 4. 10).

Центральное проецирование состоит из двух преобразований – перспективного преобразования и преобразования ортогонального проецирования. На рис. 4.10 показаны результат перспективного преобразования параллелепипеда с точкой P¢ и последующее ортогональное проецирование его на плоскость OXY.

Рис. 4.10

Перспективное преобразование приводит к фактическому сокращению размеров объектов с удалением их от наблюдателя. В однородных координатах перспективное преобразование с осью проецирования OZ представляется следующим образом:

(4.32)

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

В данном случае перевод однородных координат в обычные требует деления на значение координаты v. В итоге обычными координатами точки P' будут (x /(k z + 1), y /(k z + 1), z /(k z + 1)).

Чтобы определить координаты точки схода, вычислим пределы:

(4.33)

(4.34)

(4.35)

Таким образом, для преобразования (4.32) P_c = (0, 0, 1/ k). Если требуется построить центральную проекцию с точкой схода, координаты x_c и y_c которой отличны от нуля (например должны соответствовать центру области вывода), то используют тот же прием, что и при выполнении геометрических преобразований относительно заданного центра. В данном случае сначала необходимо выполнить преобразование смещения по x и y на - x_c и - y_c соответственно, затем перспективное преобразование, а в заключение – обратное преобразование смещения.

Преобразование ортогонального проецирования после перспективного необходимо для получения проекций объектов на картинную плоскость.

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

Более подробный материал по видам проецирования и их свойствам можно найти в [4, 7].

4.9. Ориентация и потенциальная видимость
поверхностей

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

Формально стороны поверхности можно различать по направлению нормального вектора к ней. Для определенности примем правило, согласно которому внешней стороной поверхности геометрического тела будет считаться та, со стороны которой располагаются нормальные векторы к поверхности, рассчитанные аналитически. Выше уже говорилось, что для поверхности с уравнением F (x, y, z) = 0 нормальный вектор в любой ее точке находится как .