9. Методы и алгоритмы пространственной графики

Понятие "трехмерная графика" в настоящее время можно считать наиболее распространенным для обозначения темы, которую мы рассмотрим (в литературе название часто сокращается до "ЗD-графики"). Однако необходимо отметить, что такое название не совсем точно, ибо речь пойдет о создании изображения на плоскости, а не в объеме. Истинно трехмерные способы отображения пока что не достаточно широко распространены.

Модели описания поверхностей

Рассмотрим, как можно представлять форму трехмерных объектов в системах КГ. Для описания формы поверхностей могут использоваться разнообразные методы. Сделаем обзор некоторых из них.

Аналитическая модель

Аналитической моделью будем называть описание поверхности математическими формулами. В КГ можно использовать много разновидностей такого описания. Например, в виде функции двух аргументов z = ∫ (х, у). Можно использовать уравнение F (х, у, z) = 0.

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

х = F_x(s, t)

y=F_y(s,t)

z = F_z(s, t)

где s и t— параметры, которые изменяются в определенном диапазоне, а функции F_X F_{y и} F_yz Сбудут определять форму поверхности.

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

В качестве примера рассмотрим аналитическое описание поверхности шара. Сначала как функцию двух аргументов:

Z=±√R²-x²-y²

Затем в виде уравнения: х² + у² + z² - R² = 0.

А также в параметрической форме:

х = R sin s cos t,

у = R sin s sin t,

z = R cos s.

Для описания сложных поверхностей часто используют сплайны. Сплайн — это специальная функция, более всего пригодная для аппроксимации отдельных фрагментов поверхности. Несколько сплайнов образовывают модель сложной поверхности. Другими словами, сплайн — эта тоже поверхность, но такая, для которой можно достаточно просто вычислять координаты ее точек. Обычно используют кубические сплайны. Почему именно кубические? Потому, что третья степень— наименьшая из степеней, позволяющих описывать любую форму, и при стыковке сплайнов можно обеспечить непрерывную первую производную — такая поверхность будет без изломов в местах стыка. Сплайны часто задают параметрически. Запишем формулу для компоненты x(s,t) кубического сплайна в виде многочлена третьей степени параметров s и t:

x(s,t) = A11   s3   t3 + A12  s3   t2 + A13   s3   t + A14  s3 + A21   s2   t3 + A22  s2   t2 + A23   s2   t + A24  s2 + A31   s   t3 + A32  s   t2 + A33   s   t + A34  s + A41   t3 + A42  t2 + A43   t + A44.

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

Координаты и преобразования

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

Далее большими буквами X, Y, Z будут обозначаться обычные декартовые координаты, а маленькие буквы x, y, z будут использоваться для обозначения т.н. однородных координат.

Двумерные преобразования

Преобразование сдвига в плоском случае имеет вид:

Xn = X + Tx, Yn = Y + Ty (9.1)

или в векторной форме:

Pn = P + T, (9.2)

где Pn = [XnYn] - вектор-строка преобразованных координат, где X,Y - исходные координаты точки,

Tx,Ty - величина сдвига по осям,

Xn,Yn - преобразованные координаты.

P = [X Y] - вектор-строка исходных координат,

Pn = [Xn Yn] - вектор-строка преобразованных координат,

T = [Tx Ty] - вектор-строка сдвига.

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

Xn = X ·Sx, Yn = Y ·Sy (9.3)

или в матричной форме:

Pn = P ·S, (9.4)

где Sx, Sy - коэффициенты масштабирования по осям, а

S = - матрица  масштабирования.

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

Xn = X ·cos- Y ·sin, Yn = X ·sin+ Y ·cos, (9.5)

или в матричной форме:

Pn = P ·R, (9.6)

где  - угол поворота, а

R = - матрица поворота.

Столбцы и строки матрицы поворота представляют собой взаимно ортогональные единичные векторы. В самом деле квадраты длин векторов-строк равны единице:

cos·cos+sin·sin = 1 и

(-sin) ·(-sin)+cos·cos = 1,

а скалярное произведение векторов-строк есть

cos·(-sin) + sin·cos = 0.

Так как скалярное произведение векторов A ·B = A ·B ·cos, где A - длина вектора A, B - длина вектора B, а  - наименьший положительный угол между ними, то из равенства 0 скалярного произведения двух векторов-строк длины 1 следует, что угол между ними равен 90^.

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

cos -sin  cos sin -sin cos 1 0

(9.7)

т.е. это единичный вектор вдоль оси X. Аналогично, произведение второго столбца на матрицу даст вектор [01]. Это позволяет сформировать матрицу, если известны результаты преобразования.

Двумерные преобразования в однородных координатах

Как видно из (2), (4) и (6) двумерные преобразования имеют различный вид. Сдвиг реализуется сложением, а масштабирование и поворот - умножением. Это различие затрудняет формирование суммарного преобразования и устраняется использованием двумерных однородных координат точки, имеющих вид:

[x y w].

Здесь w - произвольный множитель не равный 0.

Двумерные декартовые координаты точки получаются из однородных делением на множитель w:

X = x / w, Y = y / w. (9.8)

Однородные координаты можно представить как промасштабированные с коэффициентом w значения двумерных координат, расположенные в плоскости с Z = w.

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

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

Для сдвига

xn yn wn = x y w · 1 0 0 0 1 0 Tx Ty 1 .

(9.9)

Для масштабирования

xn yn wn = x y w · Sx 0 0 0 Sy 0 0 0 1 .

(9.10)

Для поворота

xn yn wn = x y w · cos sin 0 -sin cos 0 0 0 1 .

(9.11)

Как видно из (9) - (11), wn = w, а матрица преобразования для двумерных однородных координат в общем случае имеет вид:

A B D E P Q L M S ,

(9.12)

где элементы A,   B,   D и E определяют изменение масштаба, поворот и смещение, а L и M определяют сдвиг. Покажем, что элемент S определяет общее изменение масштаба, а элементы P и Q определяют проецирование.

Рассмотрим вначале для этого преобразование

xn yn h = x y 1 · 1 0 0 0 1 0 0 0 S .

Легко видеть, что xn = x,   yn = y,   h = S. Таким образом двумерные декартовые координаты преобразованной точки

Xn = xn / h = x / S, Yn = yn / h = y / S,

т.е. такое преобразование задает изменение масштаба вектора положения точки. При S < 1 выполняется уменьшение, а при S > 1 - увеличение.

Для уяснения смысла третьего столбца матрицы преобразований (12) выполним преобразование

xn yn h = x y 1 · 1 0 P 0 1 Q 0 0 1 = x y (Px+Qy+1) .

Здесь xn = x,   yn = y,   h = Px + Qy + 1, т.е. переменная h, которая определяет плоскость, содержащую преобразованные точки, представленные в однородных координатах, образует теперь уравнение плоскости в трехмерном пространстве:

h = Px + Qy + 1. (9.13)

Получим результирующие двумерные декартовые координаты Xn, Yn для преобразованной точки

Xn = x Px + Qy + 1 , Yn = y Px + Qy + 1 .

Это соответствует вычислению их в плоскости Z = 1, т.е. проецированию из плоскости в плоскость Z = 1. Легко показать, что центр проецирования находится в начале координат. Рассмотрим для этого параметрические уравнения прямой, проходящей через точки (X₀, Y₀, 1) и (X, Y, (MX+NY+1) ):

X(t) = X0 + (X-X0) ×t = x/h + (x - x/h) ×t Y(t) = Y0 + (Y-Y0) ×t = y/h + (y - y/h) ×t Z(t) = 1 + (MX+NY) ×t = 1 + (h - 1) ×t .

(9.14)

Из условия X(t) = X₀ = 0 находим t = 1/(1 - h), подставляя это значение t в выражения для Y(t) и Z(t), получим:

Y₀ = y/h + (y - y/h)/(1-h) = y/h - y/h = 0.

Z₀ = 1 + (h-1)/(1-h) = 0

Итак, показано, что элементы P и Q матрицы (12) определяют проецирование с центром проекции в начале координат.

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

Декартовые точки с бесконечными координатами

Рассмотрим в декартовой системе линию, проходящую через начало координат и точку (X,Y). Однородные координаты этой точки - (x,y,h) = (hX, hY, h), где h имеет произвольное значение. Предел отношения x/y при h стремящимся к 0 равен X/Y, но при этом декартовые координаты стремятся к бесконечности. Таким образом, точка с однородными координатами

(x, y, 0)

(9.15)

задает в декартовой системе точку на бесконечности для рассмотренной прямой. В частности, точка с однородными координатами (1, 0, 0) задает бесконечную точку на декартовой оси X, а точка с однородными координатами (0, 1, 0) задает бесконечную точку на декартовой оси Y.

Параллельные прямые

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

Пусть две пересекающиеся прямые в декартовой системе координат заданы системой уравнений:

A1 ·X + B1 ·Y + C1 = 0 A2 ·X + B2 ·Y + C2 = 0.

(9.16)

Решая эту систему относительно X и Y, найдем координаты точки пересечения

X0 = C1 ·B2-C2 ·B1 A1 ·B2-A2 ·B1 .

Y0 = A1 ·C2-A2 ·C1 A1 ·B2-A2 ·B1 .

Запишем результат в однородных координатах

   C1 ·B2-C2 ·B1 A1 ·B2-A2 ·B1 ,  A1 ·C2-A2 ·C1 A1 ·B2-A2 ·B1 ,  1    .

В силу произвольности масштабного множителя, умножим значения координат на (A₁ ·B₂ - A₂ ·B₁)

(C₁ ·B₂-C₂ ·B₁,  A₁ ·C₂-A₂ ·C₁,  A₁ ·B₂-A₂ ·B₁).

Если прямые параллельны, то определитель системы (16) - (A₁ ·B₂-A₂ ·B₁) равен нулю. Учитывая это и обозначая x₀ = (C₁ ·B₂-C₂ ·B₁), y₀ = (A₁ ·C₂-A₂ ·C₁), получим координату пересечения параллельных прямых в однородной системе координат

( x0, y0, 0 ).

При этом точка пересечения лежит на прямой -y₀ ·x + x₀ ·y = 0 на бесконечности.

Композиция двумерных преобразований

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

Рассмотрим сдвиг точки P₀ на расстояние (Tx₁, Ty₁) в точку P₁, а затем сдвинем точку P₁ на расстояние (Tx₂, Ty₂) в точку P₂. Обозначая через T₁ и T₂ матрицы сдвига, в соответствии с (9) получим:

P₁ = P₀ ·T₁;  P₂ = P₁ ·T₂   =   (P₀ ·T₁) ·T₂   =   P₀ ·(T₁ ·T₂)   =  P₀ ·T.

Понятно, что сдвиг аддитивен, т.е. последовательное выполнение двух сдвигов должно быть эквивалентно одному сдвигу на расстояние (Tx₁+Tx₂, Ty₁+Ty₂). Для доказательства этого рассмотрим произведение матриц сдвига T₁ и T₂, равное

T =       1 0 0 0 1 0 Tx1 Ty1 1       ·       1 0 0 0 1 0 Tx2 Ty2 1       =

      1 0 0 0 1 0 Tx1+Tx2 Ty1+Ty2 1       .

Итак, получили, что результирующий сдвиг есть (Tx₁+Tx₂, Ty₁+Ty₂), т.е. суммарный сдвиг, вычисленный как произведение матриц, как и ожидалось, аддитивен.

Рассмотрим теперь последовательное выполнение масштабирований, первое с коэффициентами (Sx₁, Sy₁), второе с коэффициентами (Sx₂, Sy₂). Следует ожидать, что суммарное масштабирование будет мультипликативным. Обозначая через S₁ и S₂ матрицы масштабирования, в соответствии с (10) получим

P1 = P0 ·S1,   P2 = P1 ·S2   =  (P0 ·S1) ·S2   =   P0 ·(S1 ·S2) = P0 ·S.

Найдем значения элементов матрицы S

S =       Sx1 0 0 0 Sy1 0 0 0 1       ·       Sx2 0 0 0 Sy2 0 0 0 1       =       Sx1 ·Sx2 0 0 0 Sy1 ·Sy2 0 0 0 1       .

Итак, получили, что результирующее масштабирование есть (Sx₁ ·Sx₂,  Sy₁ ·Sy₂), т.е. суммарное масштабирование, вычисленное как произведение матриц, как и ожидалось, мультипликативно.

Аналогичным образом можно показать, что два последовательных поворота аддитивны.

Рассмотрим выполнение часто используемого поворота изображения на угол  относительно заданной точки P(X,Y). Это преобразование можно представить как перенос начала координат в точку (X,Y), поворот на угол  относительно начала координат и обратный перенос начала координат:

Pn = P ·T(-X,-Y) ·R() ·T(X,Y).

С использованием преобразований в однородных координатах, суммарное преобразование будет иметь простой вид:

      1 0 0 0 1 0 -X -Y 1       ·       cos sin 0 -sin cos 0 0 0 1       ·       1 0 0 0 1 0 X Y 1       .

Эффективность преобразований

Суммарная матрица двумерных преобразований в однородных координатах имеет вид:

      A B 0 D E 0 L M 1       ,

где элементы A,   B,   D и E, отвечающие за изменение масштаба, поворот и смещение, - объединенная матрица масштабирования и поворота, а L и M определяют суммарный сдвиг.

Вычисление преобразованных однородных координат точки P с непосредственным использованием T в выражении P ·T требует 9 операций умножения и 6 операций сложения. Но так как третья однородная координата может быть выбрана равной 1, а третий столбец T содержит единственный ненулевой элемент, равный 1, то преобразование декартовых координат может быть представлено в виде:

Xn = X ·A + Y ·D + L, Yn = X ·B + Y ·E + M,

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

Трехмерные координаты

Далее при рассмотрении трехмерных преобразований, в основном, используется общепринятая в векторной алгебре правая система координат. При этом, если смотреть со стороны положительной полуоси в центр координат, то поворот на +90^ (против часовой стрелке) переводит одну положительную ось в другую (направление движения расположенного вдоль оси и поворачивающегося против часовой стрелки правого винта и положительной полуоси совпадают). В некоторых, специально оговариваемых случаях, используется левая система координат. В левой системе координат положительными будут повороты по часовой стрелке, если смотреть с положительного конца полуоси. В трехмерной машинной графике более удобной является левая система координат. Тогда если, например, поверхность экрана совмещена с плоскостью XY, то большим удалениям от наблюдателя соответствую точки с большим значением Z.

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

Подобно тому как в двумерном случае точка в однородных координатах представляется трехмерным вектором [ x y w ], а матрицы преобразований имеют размер 3×3, для трехмерного случая точка представляется четырехмерным вектором [ x y z w ], где w не равно 0, а матрицы преобразований имеют размер 4×4. Если w не равно 1, то декартовые координаты точки (X,Y,Z) получаются из соотношения:

[  X  Y  Z  1  ] = [  (x/w)  (y/w)  (z/w)  1  ].

Преобразование в однородных координатах описывается соотношением [ xn yn zn wn  ] = [ x y z w ] ·T.

Матрица преобразования T в общем случае имеет вид

            A B C D E F I J K P Q R L M N S             .

Подматрица 3×3 определяет суммарные смещение, масштабирование и поворот. Подматрица-строка 1×3 - [ L M N ] задает сдвиг. Подматрица-столбец 3×1 - [ P Q R ] отвечает за преобразование в перспективе. Последний скалярный элемент - S определяет общее изменение масштаба.

В частности, матрица сдвига имеет вид:

T(Tx, Ty, Tz) =        1 0 0 0 0 1 0 0 0 0 1 0 Tx Ty Tz 1        .

Матрица обратного преобразования для сдвига получается путем смены знака у Tx, Ty и Tz.

Матрица масштабирования относительно центра координат имеет вид:

S(Sx, Sy, Sz) =        Sx 0 0 0 0 Sy 0 0 0 0 Sz 0 0 0 0 1        .

Матрица обратного преобразования для масштабирования формируется при замене Sx,   Sy и Sz на величины, обратные к ним. Ранее рассмотренная для двумерного случая матрица поворота является в то же время трехмерным поворотом вокруг оси Z. Так как при трехмерном повороте вокруг оси Z (поворот в плоскости XY) размеры вдоль оси Z неизменны, то все элементы третьей строки и третьего столбца равны 0, кроме диагонального, равного 1:

Rz(z) =        cosz sinz 0 0 -sinz cosz 0 0 0 0 1 0 0 0 0 1        .

При повороте вокруг оси X (в плоскости YZ) размеры вдоль оси X не меняются, поэтому все элементы первой строки и первого столбца равны 0, за исключением диагонального, равного 1:

Rx(x) =        1 0 0 0 0 cosx sinx 0 0 -sinx cosx 0 0 0 0 1        .

При повороте вокруг оси Y (в плоскости XZ) размеры вдоль оси Y не меняются, поэтому все элементы второй строки и второго столбца равны 0, за исключением диагонального, равного 1:

Ry(y) =        cosy 0 -siny 0 0 1 0 0 siny 0 cosy 0 0 0 0 1        .

Столбцы и строки подматриц 3×3 матриц поворота Rx,   Ry,   Rz, аналогично двумерному случаю, представляют собой взаимно ортогональные единичные векторы. Легко убедиться, что суммарная матрица преобразования для произвольной последовательности поворотов вокруг осей X,   Y и Z имеет вид:

R =        r1x r1y r1z 0 r2x r2y r2z 0 r3x r3y r3z 0 0 0 0 1       

причем столбцы (и строки) представляют собой взаимно ортогональные единичные векторы. Более того, векторы-столбцы при повороте, задаваемом матрицей, совмещаются с соответствующими осями координат. Матрица, столбцы (или строки) которой представляют собой взаимно ортогональные векторы, называется ортогональной. Для любой ортогональной матрицы М обратная матрица совпадает с транспонированной. Это обеспечивает простоту вычисления обратного преобразования для поворота. Причем не надо фактически выполнять транспонирование, а достаточно просто поменять местами индексы строк и столбцов.

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

Пример формирования матрицы преобразования (из [])

Пусть заданы три точки P₁,   P₂,   P₃. Найти матрицу преобразования такого, что после преобразования вектор P₁P₂ будет направлен вдоль оси Z, а вектор P₁P₃ будет лежать в плоскости YZ.

1. Вначале надо сместить начало координат в точку P₁ с помощью преобразования

T(-x₁, -y₁, -z₁).

2. Единичный вектор, который должен лечь вдоль оси Z

R_z = [r1_z  r2_z  r3_z] = P₁P₂ / P₁P₂.

3. Здесь P₁P₂ - длина вектора P₁P₂.

4. Вектор, перпендикулярный плоскости, построенной на векторах P₁P₂ и P₁P₃, должен быть направлен вдоль оси X, так как вектор P₁P₂ лежит вдоль оси Z, а вектор P₁P₃ лежит в плоскости YZ. Этот вектор задается векторным произведением

   Rx = [r1x  r2x  r3x] = P1P2 ×P1P3 P1P2 ·P1P3 .

5. Наконец, вдоль оси Y должен быть направлен вектор, перпендикулярный к векторам R_x и R_z:

R_y = [ r1_y r2_y r3_y  ] = R_z ×R_x.

6. Искомая матрица есть

M = T(-x1,-y1,-z1) ·        r1x r1y r1z 0 r2x r2y r2z 0 r3x r3y r3z 0 0 0 0 1        .

Проекции

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

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

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

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

По расположению центра проекции относительно плоскости проекции различаются центральная и параллельные проекции.

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

При ортогональной проекции проекторы перпендикулярны плоскости проекции, а плоскость проекции перпендикулярна главной оси. Т.е. проекторы параллельны главной оси.

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

• при прямоугольной аксонометрической проекции проекторы перпендикулярны плоскости проекции, которая расположена под углом к главной оси;

• при косоугольной аксонометрической проекции проекторы не перпендикулярны плоскости проекции, но плоскость проекции перпендикулярна к главной оси.

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

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

Параллельные проекции

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

Использование проекций в техническом черчении регламентируется стандартом ГОСТ 2.317-87. Наиболее широко, особенно, в САПР используются ортогональные проекции (виды). Вид - ортогональная проекция обращенной к наблюдателю видимой части поверхности предмета, расположенного между наблюдателем и плоскостью чертежа.

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

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

При изометрических проекциях укорачивания вдоль всех координатных осей одинаковы, поэтому можно производить измерения вдоль направлений осей с одним и тем же масштабом (отсюда и название изометрия). При этой проекции плоскость проецирования наклонена ко всем главным координатным осям под одинаковым углом. Стандартом регламентируется коэффициент сжатия, равный 0.82, а также расположение и взаимные углы главных координатных осей, равные 120^. Обычно сжатие не делается.

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

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

Наиболее употребимы два вида косоугольной проекции - фронтальная (косоугольная) диметрия (проекция Kabinett - кабине) и горизонтальная (косоугольная) изометрия (проекция Kavalier - кавалье) или военная перспектива.

В случае фронтальной (косоугольной) диметрии при использовании правосторонней системы координат экрана плоскость проецирования перпендикулярна оси Z. Ось X направлена горизонтально вправо. Ось Z изображается по углом в 45^ относительно горизонтального направления. Допускается угол наклона в 30 и 60^. При этом отрезки, перпендикулярные плоскости проекции, при проецирования сокращаются до 1/2 их истинной длины. В случае же (аксонометрической косоугольной) горизонтальной изометрии, как следует из названия, плоскость проецирования перпендикулярна оси Y а укорачивания по всем осям одинаковы и равны 1. Угол поворота изображения оси X относительно горизонтального направления составляет 30^. Допускается 45 и 60^ при сохранении угла 90^ между изображениями осей X и Z. Выведем выражения для матриц преобразования, используя теперь левостороннюю систему координат более естественную для машинной графики.

Простейшее параллельное проецирование - ортогональное выполняется на плоскость, перпендикулярную какой-либо оси, т.е. при направлении проецирования вдоль этой оси. В частности, проецирование в XY-плоскость, заданную соотношением Z = Z₀, выполняется следующим образом:

  xn yn zn wn   =   x y z 1   ·        1 0 0 0 0 1 0 0 0 0 0 0 0 0 Z0 1        .

Рассмотрим теперь косоугольное проецирование, при котором плоскость проецирования перпендикулярна главной оси, а проекторы составляют с плоскостью проецирования угол не равный 90^. Матрица для этого преобразования может быть найдена исходя из значений угла проецирования и координат преобразованной точки.

Из рисунка видно, что проектором, идущим из точки P₀ в P₁, точка P₀(0,0,1) проецируется в P₁(L·cos, L·sin, 0).

Теперь проектором, параллельным рассмотренному, спроецируем некоторую точку (X,Y,Z) в точку (X_p,Y_p,Z_p).

Из подобия треугольников получаем:

(X_p-X)/Z = L·cos         Xp = X + Z·L·cos

(Y_p-Y)/Z = L·sin         Y_p = Y + Z·L·sin

Это соответствует следующему матричному выражению:

  xp yp zp 1   =   x y z 1   ·        1 1 0 0 0 0 0 0 L·cos L·sin 1 0 0 0 0 1        .

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

• вначале плоскости с заданной координатой Z₀ переносятся вдоль оси X на Z₀·L·cos и вдоль оси Y на Z₀·L·sin,

• затем производится проецирование в плоскость Z = 0.

Различные варианты параллельных проекций формируются из полученной подстановкой значений L и углов  и  В частности, для фронтальной косоугольной диметрии L = 1/2, следовательно, угол  между проекторами и плоскостью проецирования равен arctan2 = 63.4^. Угол же , равен 45^ и допускается 30 и 60^, как это сказано выше. (Обратите внимание, что в этой системе координат плоскость фронтальной проекции - плоскость XY, в отличие от системы координат технического черчения, где фронтальная проекция формируется в плоскости XZ).

Центральная проекция

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

Наиболее широко используется двухточечная центральная проекция.

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

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

Для координат (X1,Y1) точки P₁, полученной проецированием точки P₀(X,Y,Z) в плоскость Z = d (плоскость экрана) выполняются следующие соотношения:

X1 d = X Z , X1 d = X Z , X1 = X Z/d , Y1 = Y Z/d .

Такое преобразование может быть представлено матрицей 4×4

  x1 y1 z1 w1   =   x y z 1   ·        1 1 0 0 0 0 0 0 0 0 1 1/d 0 0 0 0        =

  x y z 1   ·Mц =   x y z z/d   .

Для перехода к декартовым координатам делим все на z/d и получаем:

[    X/(Z/d)     Y/(Z/d)     d     1     ].

Если же точка просмотра расположена в плоскости проекции, тогда центр проекции расположен в точке (    0,    0,    -d    ). Рассматривая подобные треугольники, аналогично вышеописанному, можем получить:

X1 = X Z/d + 1 ; Y1 = Y Z/d + 1 .

Матрица преобразования в этом случае имеет вид:

M0 =        1 0 0 0 0 1 0 0 0 0 0 1/d 0 0 0 1        .

Матрица M₀ может быть представлена в виде:

M₀      =     T(0, 0, d) ·M_ц ·T (0, 0, -d),

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

Стереоизображения

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

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

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

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

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

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

Геометрические преобразования растровых картин

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

Преобразование сдвига реализуется наиболее просто и заключается в переписывании части изображения (bitblt - операции Bit Block Transfer). При этом возможно исполнение некоторых операций над старым и новым пикселами с одинаковыми координатами.

Наиболее употребимыми являются:

 замена - новый пиксел просто заменяет старый,

 исключающее ИЛИ - в видеопамять заносится результат операции XOR над старым и новым кодами пикселов. Эта операция обычно используется дважды - вначале для занесения некоторого изображения, например, перекрестия и повторного его занесения для восстановления исходной картины.

Кроме этого, для реализации техники "акварель", т.е. техники работы с прозрачными цветами, в видеопамять заносится результат цветовой интерполяции между старым и новым оттенками пикселов. Эта операция всегда точно реализуема в полноцветных дисплеях, хранящих значения R, G и B в каждом пикселе. В дисплеях с таблицей цветности возможно получение не совсем правильных результатов.

Преобразование масштабирования

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

 целочисленное - zoom,

 произвольное, когда коэффициент масштабирования не обязательно целое число, - transfocation.

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

Преобразование поворота

Определенные проблемы, связанные с дискретных характером изображения, возникают и при повороте растровой картины на угол не кратный 90^. Здесь возможны два подхода:

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

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

Физические принципы формирования оттенков

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

Для самосветящихся объектов используется аддитивное формирование оттенков, когда требуемый цвет формируется за счет смешения трех основных оттенков цветов. В этом случае удобно использование модели смешения RGB (Red, Green, Blue - красный, зеленый, синий).

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

Цвета одной модели являются дополнительными к цветам другой модели. Дополнительный цвет - цвет, дополняющий данный до белого. Дополнительный для красного - голубой (зеленый+синий), дополнительный для зеленого - пурпурный (красный+синий), дополнительный для синего - желтый (красный+зеленый) и т.д.

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

Рисунок 1.5 - Цвет несамосветящегося объекта

Цветовые модели

Назначение цветовой модели - дать средства описания цвета в пределах некоторого цветового охвата, в том числе и для выполнения интерполяции цветов. Наиболее часто в компьютерной графике используются модели RGB, CMY, YIQ, HSV и HLS.

RGB (Red, Green, Blue - красный, зеленый, синий) - аппаратно-ориентированная модель, используемая в дисплеях для аддитивного формирования оттенков самосветящихся объектов (пикселов экрана). Система координат RGB - куб с началом отсчета (0,0,0), соответствующим черному цвету. Максимальное значение RGB - (1,1,1) соответствует белому цвету.

Рисунок 1.6 - Цветовой куб модели RGB

CMY (Cyan, Magenta, Yellow - голубой, пурпурный, желтый) - аппаратно-ориентированная модель, используемая в полиграфии для субтрактивного формирования оттенков, основанного на вычитании слоем краски части падающего светового потока. Цвета модели CMY являются дополнительными к цветам модели RGB, т.е. дополняющими их до белого. Таким образом система координат CMY - тот же куб, что и для RGB, но с началом отсчета в точке с RGB координатами (1,1,1), соответствующей белому цвету. Цветовой куб модели CMY показан на рисунке 9.7

Рисунок 9.7 - Цветовой куб модели CMY

Преобразования между пространствами RGB и CMY определяются следующим образом:

[ R G B ]   =   [ 1 1 1 ]  -  [ C M Y ]

Причем единичный вектор-строка в модели RGB - представление белого цвета, а в модели CMY - черного.

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

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

По вертикальной оси конуса задается V - светлота, меняющаяся от 0 до 1. Значению V = 0 соответствует вершина конуса, значению V = 1 - основание конуса; цвета при этом наиболее интенсивны.

Цветовой тон H задается углом, отсчитываемым вокруг вертикальной оси. В частности, 0^ - красный, 60^ - желтый, 120^ - зеленый, 180^ - голубой, 240^ - синий, 300^ - пурпурный, т.е. дополнительные цвета расположены друг против друга (отличаются на 180^).

Насыщенность S определяет насколько близок цвет к "чистому" пигменту и меняется от 0 на вертикальной оси V до 1 на боковых гранях шестигранного конуса.

Точка V = 0, в которой находится вершина конуса, соответствует черному цвету. Значение S при этом может быть любым в диапазоне 0-1. Точка с координатами V = 1, S = 0 - центр основания конуса соответствует белому цвету. Промежуточные значения координаты V при S=0, т.е. на оси конуса, соответствуют серым цветам. Если S = 0, то значение оттенка H считается неопределенным.

Подпрограммы перехода от RGB к HSV и обратно приведены в Приложении 1.

Рисунок1.8 - Цветовая модель HSV

HLS (Hue, Lightness, Saturation - цветовой тон, светлота, насыщенность) - модель ориентированная на человека и обеспечивающая возможность явного задания требуемого оттенка цвета. Эта модель образует подпространство, представляющее собой двойной конус, в котором черный цвет задается вершиной нижнего конуса и соответствует значению L = 0, белый цвет максимальной интенсивности задается вершиной верхнего конуса и соответствует значению L = 1. Максимально интенсивные цветовые тона соответствуют основанию конусов с L = 0.5, что не совсем удобно.

Цветовой тон H, аналогично системе HSV, задается углом поворота.

Насыщенность S меняется в пределах от 0 до 1 и задается расстоянием от вертикальной оси L до боковой поверхности конуса. Т.е. максимально насыщенные цветовые цвета располагаются при L=0.5, S=1.

В общем, систему HLS можно представить как полученную из HSV "вытягиванием" точки V=1, S=0, задающей белый цвет, вверх для образования верхнего конуса.

Рисунок 1.9 - Цветовая модель HLS

Каркасная визуализация

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

Показ с удалением невидимых точек

Здесь мы будем рассматривать поверхности в виде многогранников или полигональных сеток. Известны такие методы показа с удалением невидимых точек: сортировка граней по глубине, метод плавающего горизонта, метод Z-буфера.

Сортировка граней по глубине. Это означает рисование полигонов граней в порядке от самых дальних к самым близким. Этот метод не является универсальным, ибо иногда нельзя четко различить, какая грань ближе. Известны модификации этого метода, которые позволяют корректно рисовать такие грани. Метод сортировки по глубине эффективен для показа поверхностей, заданных функциями z =f(x,y)

Метод плавающего горизонта. В отличие от предыдущего метода при методе плавающего горизонта грани выводятся в последовательности от ближайших к самым дальним. На каждом шаге границы граней образовывают две ломаные линии — верхний горизонт и нижний горизонт. Во время вывода каждой новой грани рисуется только то, что выше верхнего горизонта, и то, что ниже нижнего горизонта. Соответственно, каждая новая грань поднимает верхний и опускает нижний горизонты. Этот метод часто используют для показа поверхностей, которые описываются функциями z=f(x,y).

Метод Z-буфера. Метод основывается на использовании дополнительного массива, буфера в памяти, в котором сохраняются координаты Z для каждого пиксела растра. Координата Z отвечает расстоянию точек пространственных объектов до плоскости проецирования. Например, она может быть экранной координатой Z в системе экранных координат (X,Y,Z), если Z перпендикулярна плоскости экрана.

Рассмотрим алгоритм рисования объектов согласно этому методу. Пусть, чем ближе точка в пространстве к плоскости проецирования, тем больше значение Z. Тогда сначала Z-буфер заполняется минимальными значениями. Потом начинается вывод всех объектов. Причем не имеет значение порядок вывода объектов. Для каждого объекта выводятся все его пикселы в любом порядке. Во время вывода каждого пиксела по его координатам (X,Y) находится текущее значение Z в Z-буфере. Если рисуемый пиксел имеет большее значение Z, чем значение в Z-буфере, то это означает, что эта точка ближе к объекту. В этом случае пиксел действительно рисуется, а его Z-координата записывается в Z-буфер. Таким образом, после рисования всех пикселов всех объектов растровое изображение будет состоять из пикселов, которые соответствуют точкам объектов с самыми большими значениями координат Z, то есть видимые точки — ближе всех к нам.

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

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

Закрашивание поверхностей

В этом разделе мы рассмотрим методы, которые позволяют получить более-менее реалистичные изображения для объектов, моделируемых многогранниками и полигональными сетками. Эти методы достаточно подробно описаны в [9, 28, 32], а также в [58, 60].

Модели отражения света

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

Преломление света

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

Модель идеального преломления. Согласно этой модели луч отклоняется на границе двух сред, причем падающий луч, преломленный луч и нормаль лежат в одной плоскости (в этой же плоскости лежит и зеркально отраженный луч). Обозначим угол между падающим лучом и нормалью как а_ь а угол между нормалью и преломленным лучом как а2- Для этих углов известен закон Снеллиуса, согласно которому n1sina1=n2sina2 где n1 и n2 — абсолютные показатели преломления соответствующих сред. В данном случае границами раздела сред являются две параллельные плоскости, например, при прохождении луча через толстое стекло. Очевидно, что угол а1 равен углу a₄, а угол a₂ равен углу a₃. Иными словами, после прохождения сквозь стекло луч параллельно смещается. Это смещение зависит от толщины стекла и соотношения показателей преломления сред. Возможно, это самый простой пример преломления. Вы наверняка уже наблюдали и более сложные объекты, например треугольную призму. Для нее границами сред являются непараллельные плоскости. Прозрачные объекты могут иметь и криволинейные поверхности, например линзы в разнообразных оптических приборах.

Рис 9.3 Преломление луча

Принято считать, что для вакуума абсолютный показатель преломления равен единице. Для воздуха он составляет 1.00029, для воды — 1.33, для стекла разных сортов: 1.52 (легкий крон), 1.65 (тяжелый крон) . Показатель преломления зависит от состояния вещества, например, от температуры. На практике обычно используют отношение показателей преломления двух сред (7?! / п₂), называемое относительным показателем преломления.

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

Чем меньше длина волны, тем больше отклоняется луч при преломлении. Благодаря этому свойству преломления мы и наблюдаем радугу. Фиолетовый (Х=0.4 мкм) луч отклоняется больше всего, а красный (Х=0.7 мкм) — меньше всего. Например, для стекла показатель преломления в видимом спектре изменяется от 1.53 до 1.51.

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

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

Трассировка лучей

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

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

излучают;

отражают и поглощают;

пропускают сквозь себя.

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

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

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

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

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

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

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

Непосредственная реализация данной лучевой модели формирования изображения представляется затруднительной. Можно попробовать построить алгоритм построения изображения указанным способом. В таком алгоритме необходимо предусмотреть перебор всех первичных лучей и определить те из них, которые попадают в объекты и в камеру. Затем выполнить перебор всех вторичных лучей, и также учесть только те, которые попадают в объекты и в камеру. И так далее. Можно назвать такой метод прямой трассировкой лучей. Практическая ценность такого метода вызывает сомнения. В самом деле, как учитывать бесконечное множество лучей, идущих во все стороны? Очевидно, | что полный перебор бесконечного числа лучей в принципе невозможен. Даже ^: если каким-то образом свести это к конечному числу операций (например, разделить всю сферу направлений на угловые секторы и оперировать уже не бесконечно тонкими линиями, а секторами), все равно остается главный не достаток метода— много лишних операций, связанных с расчетом лучей, которые затем не используются. Так, во всяком случае, это представляется в настоящее время.

Метод обратной трассировки лучей позволяет значительно сократить перебор световых лучей. Метод разработан в 80-х годах, основополагающими считаются работы Уиттеда и Кэя [28]. Согласно этому методу отслеживание лучей производится не от источников света, а в обратном направлении — от точки наблюдения. Так учитываются только те лучи, которые вносят вклад в формирование изображения.

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

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

Для идеального зеркала достаточно затем проследить лишь очередную точку пересечения вторичного луча с некоторым объектом. Что означает термин "идеальное зеркало"? Будем полагать, что у такого зеркала идеально ровная отполированная поверхность, поэтому одному отраженному лучу соответствует только один падающий луч. Зеркало может быть затемненным, то есть поглощать часть световой энергии, но все равно остается правило: один лучпадает — один отражается. Можно рассматривать также "неидеальное зеркало". Это будет означать, что поверхность неровная. Направлению отраженного луча будет соответствовать несколько падающих лучей (или наоборот, один падающий луч порождает несколько отраженных лучей), образующих некоторый конус, возможно, несимметричный, с осью вдоль линии падающего луча идеального зеркала. Конус соответствует некоторому закону распределения интенсивностей, простейший из которых описывается моделью Фонга — косинус угла, возведенный в некоторую степень. Неидеальное зеркало резко усложняет трассировку — нужно проследить не один, а множество падающих лучей, учитывать вклад излучения от других видимых из данной точки объектов.

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

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

Когда выясняется, что текущий луч обратной трассировки не пересекает какой-либо объект, а уходит в свободное пространство, то на этом трассировка для этого луча заканчивается.

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

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

1. Среди всех типов объектов выделим некоторые, которые назовем источниками света. Источники света могут только излучать свет, но не могут его отражать или преломлять. Будем рассматривать только точечные источники света.

2. Свойства отражающих поверхностей описываются суммой двух компонент — диффузной и зеркальной.

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

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

5 Для прозрачных (transparent) объектов обычно не учитывается зависимость коэффициента преломления от длины волны. Иногда прозрачность вообще моделируют без преломления, то есть направление преломленного луча t совпадает с направлением падающего луча.

6 Для учета освещенности объектов светом, рассеиваемым другими объектами, вводится фоновая составляющая (ambient).

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

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

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

Если точек пересечения луча с объектами несколько, то выбирается ближайшая точка по направлению текущего луча.

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

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

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

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

Для упрощения некоторых операций, выполняемых в ходе обратной трассировки, можно использовать следующий способ. Он разработан автором этой книги и заключается в следующем. В ходе трассировки лучей с каждым лучом связывается локальная система координат. Центр этой трехмерной декартовой системы располагается в точке, из которой направляется текущий луч трассировки. Ось Z направлена противоположно лучу, расположение осей безразлично. Таким образом, координаты Хи Уточки пересечения луча с объектами всегда равны нулю. Это позволяет упростить нахождение координат точки пересечения луча, поскольку направления луча всегда одно и то же, и вычислять нужно только координату Z. Для плоских полигональных граней это можно сделать с помощью линейной интерполяции координат Z соответствующих вершин. Кроме того, упрощаются и некоторые другие операции. В частности, для отбора ближайшей точки пересечения достаточно анализировать только координату Z. Следует заметить, что упрощение отдельных операций достигается за счет усложнения других— например, необходимо вычислять коэффициенты преобразования координат для каждой , локальной системы, а также выполнять преобразования координат объектов.

А теперь сделаем общие выводы по методу обратной трассировки лучей. Положительные черты:

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

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

3. Все преобразования координат (если таковые есть) линейны, поэтому достаточно просто работать с текстурами.

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

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

Недостатки:

1. Проблемы с моделированием диффузного отражения и преломления.

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

Вопросы для самопроверки

1. Как можно представлять форму трехмерных объектов в компьютерной графике?

2. Какие преимущества дает параметрическое описание?

3. Перечислите способы двоичного преобразования координат, в общем, и матричном виде.

4. Какие особенности двумерных преобразований в однородных координатах?

5. Декартовые точки с бесконечными координатами.

6. Какая система координат используется для трехмерных преобразований?

7. Назовите основные модели цветов?

8. Как можно произвести преобразование одной модели цветов в другую?

9. Опишите методы показа с удалением невидимых точек.

10. Дайте определение методам трассировки лучей.

11. Перечислите известные подходы для преобразования поворота.