Компьютерная Графика и Мультимедиа Сетевой журнал

Однородные координаты - мощный математический инструмент, находящий свое применения в различных разделах компьютерной графики - геометрическом моделировании, визуализации, машинном зрении и т.д. Однородные координаты явно или неявно используются в любом графическом пакете на этапах преобразования и затенения геометрии. Например, в OpenGL[4,1] или DirectX. В данной статье дается определение и некоторые интересные свойства однородных координат.
1. Введение  
2. Однородные координаты  
3. Геометрическая интерпретация  
4. Свойства  
    4.1. Точка в бесконечности  
    4.2. Различие между точками и векторами  
    4.3. Унифицированная запись аффинных преобразований  
    4.4. Проективные преобразования  
5. Заключение  

1  Введение

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

• В декартовых координатах невозможно описать бесконечно удаленную точку. А многие математические и геометрические концепции значительно упрощаются, если в них используется понятие бесконечности. Например, "бесконечно удаленный источник света".
  
  
• С точки зрения алгебраических операций, декартовы координаты не позволяют провести различия межу точками и векторами в пространстве. Действительно, (1,-2,5) - это направление или точка?
  
  
• Невозможно использовать унифицированный механизм работы с матрицами для выражения преобразований точек. С помощью матриц 3x3 можно описать вращение и масштабирование, однако описать смещение (xў=x+a) нельзя.
  
  
• Аналогично, декартовы координаты не позволяют использовать матричную запись для задания перспективного преобразования (проекции) точек.
  
  

Для решения этих проблем используются однородные координаты.

2  Однородные координаты

Существуют различные способы определения однородных координат. Мы будем исходить из задачи унифицированного представления координат точек в пространстве, включающего бесконечно удаленные точки. Пусть заданы действительных числа, a и w. Рассмотрим их отношение a/w. Зафиксируем значение a, и будем варьировать значение w. При уменьшении w, значение a/w будет увеличиваться. Заметим, что если w стремится к нулю, то a/w стремится к бесконечности. Таким образом, чтобы включить в рассмотрение понятие бесконечности, для представления значения v используется пара чисел (a,w), таких, что v=a/w. Если w № 0, значение v в точности равно a/w. В противном случае v=a/0, т.е. равно бесконечности. Таким образом, координаты трехмерной точки v=(x,y) можно представить через координаты (wx,wy,w). При w=1 эти координаты описывают точку с конечными координатами (x,y), а при w=0 - точку, бесконечно удаленную в направлении (x,y). Как было сказано выше, обычным представлением через декартовы коодинаты (x,y) это сделать невозможно. Рассмотрим двумерную плоскость, некоторую точку (x,y) на ней и заданную функцию f(x,y). Если заменить x и y на x/w и y/w, то выражение f(x,y)=0 заменится на f(x/w,y/w)=0. Если f(x,y) - многочлен, то его умножение на wⁿ (n - степень многочлена) уберет все знаменатели. Например, пусть имеется прямая

Ax + By + C = 0

Замена x и y на x/w и y/w дает A(x/w) + B(y/w) + C = 0. Умножая на w, получаем

Ax + By + Cw = 0

(1)

Другой пример. Пусть задан многочлен 2-го порядка

Ax2 + Bxy + Cy2 + 2Ey + F = 0

После замены x и y на x/w и y/w, соответственно, и умножения на w², получаем

Ax2 + 2Bxy + Cy2 + 2Dxw + 2Eyw + Fw2 = 0

(2)

Если внимательно посмотреть на многочлены (1) и (2), можно заметить, что степени при всех членах равны. В случае многочлена 1-го порядка, это степень 1, тогда как для многочлена 2-й степени, все члены (т.е. x², xy, y², xw, yw и w²) имеют степень 2. Следовательно, для данного многочлена n-го порядка, после введения координаты w все члены будут иметь степень n. Такие многочлены называются однородными, а координаты (x,y,w) называются однородными координатами (homogenous coordinates). Приведенные рассуждения остаются верными и в случае трехмерного пространства. Координаты (x,y,z) заменяются на (x/w, y/w, z/w) и после умножения на w в соответствующей степени n дают однородный многочлен. Однородные координаты требуют три компоненты для представления точки на плоскости (и четыре компоненты для точки в пространстве). Какие же однородные координаты соответствуют точке с координатами (x,y)? Легко видеть, что это будет (x,y,1), т.е. w полагается равной 1. В общем случае, это преобразование не однозначно. Однородные координаты точки (x,y) равны (xw, yw,w) для любого ненулевого w. Аналогично в трехмерном пространстве: точке (x,y,z) соответствуют координаты (xw, yw,zw, w). В то же время, преобразование из однородных координат в евклидовы однозначно: точке (x,y,w) соответствует точка (x/w, y/w). Приведем более формальное определение. Определение 1 Однородными координатами точки P=(x₁,..,x_n),P О Rⁿ называются координаты P_hom=(wx₁,wx₂,..,wx_n,w),P_hom О Rⁿ⁺¹, причем хотя бы один элемент должен быть отличен от нуля.

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

3  Геометрическая интерпретация

Можно дать простую геометрическую интерпретацию однородных координат на плоскости. Пусть даны однородные координаты (x,y,w) точки на плоскости Oxy, поставим ей в соответствие точку в трехмерном евклидовом пространстве с координатами x, y и w по осям X, Y и W соответственно. Прямая, соединяющая эту точку c началом координат, пересекает плоскость w=1 в точке (x/w, y/w, 1) (см. Рис. 1).


Figure 1: Геометрическая интерпретация однородных координат
Таким образом, преобразование из однородных координат в евклидовы эквивалентно проекции точки на плоскость w=1 вдоль линии, соединяющей точку с началом координат. Из рисунка также видно, что если преобразование из однородных координат в евклидовы однозначно, то обратное преобразование - нет, потому что все точки на линии, соединяющей точку (x,y,w) и начало координат будут проецироваться в точку (x/w, y/w).

4  Свойства

4.1  Точка в бесконечности

Как было сказано выше, с помощью однородных координат можно легко описывать бесконечность. Рассмотрим точку с однородными координатами (x,y,w). Ей соответствует точка с евклидовыми координатами (x/w, y/w). Зафиксируем x и y и устремим w к нулю. Точка (x/w, y/w) будет удаляться все дальше и дальше в бесконечность в направлении (x,y). Когда w станет нулем, (x/w, y/w) уходит в бесконечность. Следовательно, однородные координаты (x,y,0) - идеальная точка (ideal point) или, по-другому, точка в бесконечности (point at infinity) по направлению (x,y). Аналогично для трехмерного пространства: точка (x,y,z,0) - точка в бесконечности по направлению (x,y,z). Например, в OpenGL для определения положения источника света используются однородные координаты. С их помощью определить как точечный источник света (w=1), так и параллельный источник света (w=0).

4.2  Различие между точками и векторами

Пусть имеется система координат [3] (O,[`i],[`j],[`k]). Чтобы представить данный вектор v, необходимо найти три числа (v₁,v₂,v₃), причем такие, что выполняется соотношение:

v = v1 - i   +v2 - j   +v3 - k

Это значит, что вектор v задает направление относительно векторов базиса [`i],[`j],[`k]. С другой стороны, чтобы представить точку P, можно рассматривать ее местоположение как смещение на определенный вектор (p₁, p₂, p₃) относительно начала координат. Следовательно, положение точки P можно записать следующим образом:

P = O + p1 - i   + p2 - j   + p3 - k

Таким образом, для описания положения точки трех параметров недостаточно. Используя однородные координаты, эти выражения можно записать как v = (v₁, v₂, v₃, 0) и P=(p₁,p₂,p₃,1). В данном случае 1 или 0 показывают, принимает ли начало координат участие в вычислениях. Действительно, это согласуется с представлением о том, что вектор - это точка, бесконечно удаленная в некотором направлении (т.е. с w=0 в однородных координатах). Заметим, что покоординатные операции с векторами сохраняют однородную форму записи координат:

• Разность двух точек (x, y, z, 1) и (d,e,f,1) равна (x-d, y-e,z-f,0), т.е. как и ожидалось, является вектором.
  
  
• Сумма точки (x, y, z, 1) и вектора (d,e,f,0) равна другой точке (x+d, y+e, z+f, 1).
  
  
• Два вектора можно складывать, в результате получается вектор (d, e,f, 0) + (m, n, r, 0) = (d + m, e + n, f + r, 0)
  
  
• Имеет смысл масштабирование вектора 3(d, e, f, 0) = (3f, 3f, 3f, 0)
  
  
• Имеет смысл создание любой линейной комбинации векторов.
  
  

4.3  Унифицированная запись аффинных преобразований

Аффинное преобразования на плоскости для точки (x,y) записывается следующим образом:

xў = ax + by + l yў = gy + delta y + m

Известно, что любое подобное преобразование можно представить как суперпозицию простейших преобразований: поворота, масштабирования, отражения и переноса В компьютерной графике используется матричная запись этих преобразований. Для первых трех преобразований матричная форма находится тривиально (см., например, [2]). А преобразование переноса представить через матрицы 2-го порядка не удается. Для устранения этого недостатка используются однородные координаты: вместо матриц 2x2 используются матрицы 3x3 и векторы (x,y,1). Для преобразования переноса строится следующая матрица:

Tlm = ж з з и 1 0 l 0 1 m 0 0 1 ц ч ч ш

Следовательно, перенос точки v=(x,y,1) на вектор (l,m) считается следующим образом:

Tlmv = ж з з и 1 0 l 0 1 m 0 0 1 ц ч ч ш ж з з и x y 1 ц ч ч ш = ж з з и x+l y+m 1 ц ч ч ш

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

ж з з и a b l g delta m 0 0 1 ц ч ч ш

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

4.4  Проективные преобразования

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

P = ж з з з и 1 0 0 0 0 1 0 0 0 0 0 0 1 0 -1/c 1 ц ч ч ч ш

После применения матрицы проекции P к точке (x,y,z,1), получим точку (x,y,z,0, 1-z/c). Это точка с однородными координатами, которые еще нужно преобразовать в декартовы путем деления на четвертую компоненту. Таким образом, использование однородных координат позволяет использовать аппарат матриц четвертого порядка для проективных преобразований, что заметно упрощает решение задач геометрического моделирования. Обратите внимание, в отличие от матриц аффинного преобразования, матрица перспективной проекции может преобразовывать вектор в точку. Т.е. для бесконечно удаленной точки (x,y,z,0) существует ее проекция на экран, что согласуется с интутивными представлениями о перспективе. Например, используя однородные координаты, в OpenGL можно задать треугольник, у которого две вершины будут лежать в бесконечности. Это свойство используется в некоторых графических алгоритмах (например, визуализация теневых объемов)

5  Заключение

Приведем основные характеристики однородных координат:

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

References

[1]

Ю.М. Баяковский, А.В.Игнатенко, and А.А. Фролов. Графическая библиотека OpenGL. Москва, 2003.

[2]

Е.В. Шикин and А.В. Боресков. Компьютерная графика. Полигональные модели. Диалог-МИФИ, Москва, 2001.

[3]

Эдвард Эйнджел. Интерактивная компьютерная графика. Вводный курс на базе OpenGL. Вильямс, Москва, 2 edition, 2001.

[4]

http://www.opengl.org.

Дополнительная информация

Ссылка: 

Алексей Игнатенко. Однородные координаты. Компьютерная графика и мультимедиа. Выпуск №1(5)/2003. http://cgm.computergraphics.ru/content/view/51

Выпуск: 

Выпуск №1(5)/2003