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

Понятие "трехмерная графика" в настоящее время можно считать наиболее распространенным для обозначения темы, которую мы рассмотрим (в литературе название часто сокращается до "З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, 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 ·cosf- Y ·sinf, Yn = X ·sinf+ Y ·cosf, (9.5)

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

Pn = P ·R, (9.6)

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

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

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

cosf·cosf+sinf·sinf = 1 и

(-sinf) ·(-sinf)+cosf·cosf = 1,

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

cosf·(-sinf) + sinf·cosf = 0.

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

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

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

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

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

[x y w].

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

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

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

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

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

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

Для сдвига

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

Для поворота

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

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

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

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

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

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

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

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

h = Px + Qy + 1. (9.13)

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

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

Из условия 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, но при этом декартовые координаты стремятся к бесконечности. Таким образом, точка с однородными координатами

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

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

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

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

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

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

В силу произвольности масштабного множителя, умножим значения координат на (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₁), получим координату пересечения параллельных прямых в однородной системе координат

При этом точка пересечения лежит на прямой -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₂, равное

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

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

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

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

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

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

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

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

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

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

где элементы 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 в общем случае имеет вид

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

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

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

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

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

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

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

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

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

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

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

Пусть заданы три точки 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. Этот вектор задается векторным произведением

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

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

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