Матричные операции

Введение

Начну я с одной забавной фразы, которую многие приписывают к философии кунг-фу - “...Ученик не должен показывать свои умения на людях, ибо он еще не все умеет. Если же ученик выполнил это условие и научился кунг-фу, то он уже мастер и должен учить других...” Вот и я, просидев месяц над оптимизацией процедур расчета геометрии своего движка, решил “пронести знание в массы” и разъяснить всем, что такое матрицы, с чем их едят и как они связаны с трехмерной графикой. Для начала надо, видимо, будет пояснить, что же такое матрицы вообще. Если вам (как и мне :), математику в ВУЗе не преподавали или вы болели (якобы :), то не волнуйтесь, тут все будет написано доходчиво и понятно. Итак, обычная матрица имеет следующий вид: В целом мы видим перед собой таблицу (массив) чисел 4х4, обозначенных через X: i - это номер строки и, соответственно, j - номер столбца. Похоже на Excel, да? :) Кстати, пока не забыл - в виде матрицы можно представить и обычную точку (или вектор - одно и то же... почти...) в трехмерном пространстве. Это будет выглядеть так: Вы наверно спросите - “а что это за W? Пространство-то трехмерно”. Не думайте, что я ошибся. W отныне мы будем называть коэффициентом перспективы, а пока, чтобы не забивать голову, предположим, что он всегда равен единице. Запомните - W равно единице. Ну а теперь посмотрим, как же матрицы могут быть использованы для упрощения описания трансформаций в трехмерном пространстве. А пока - все пьют кофе... .

Трансформации

Ну, кофе выпито, вернемся к нашим бакланам... или как там их... в общем - к матричным трансформациям. Вспомним, какие вообще основные виды преобразований в трехмерном пространстве мы знаем (если вы не знаете ни одного, сидите тихо). Как говорится, “данные занесем в таблицу”... Предположим, что у нас есть точка в трехмерном пространстве, описанная координатной тройкой (X, Y, Z). Все трансформации в таблице проведены по оси X. Вид трансформации Перенос по оси X (Translation) Масштабирование по оси X (Scale) Вращение по оси X (Rotation) Преобразование перспективы и проецирование Математическая запись X’ = X + Tx, Y’ = Y, Z’ = Z, где Tx – значение переноса по оси X X’ = X * Sx, Y’ = Y, Z’ = Z, где Sx - значение масштабирования по оси X X’ = X, Y’ = Y*cos(Rx) + Z*sin(Rx), Z’ = -Y*sin(Rx) + Z*cos(Rx), где Rx - значение угла поворота вокруг оси X Вообще это тема отдельного разговора... Да и обычно это делается отдельным модулем - здесь это преобразование не рассматривается А теперь попробуем представить процесс просчета геометрии внутри трехмерного движка по формулам в ситуации, близкой к реальной - предположим, что перед выводом геометрии нам надо просчитать переносы, изменения масштаба и вращения по всем трем осям... Смотрим кусок (псевдо)кода. void tipa_cool_3d_engine(void) { ....... // Ща будем трансформировать for (i=1; i<number_of_points_in_scene; i++) { translate_by_X(25); translate_by_Y(2.2); translate_by_Z(29); scale_by_X(1.5); scale_by_Y(0.3); scale_by_Z(1.2); rotate_by_X(30); rotate_by_Y(-30); rotate_by_Z(1.2); } draw_scene(); ........ } То есть, для каждой точки вызывается 9 (можно сделать три, но нужно ли?) функций. Представим такую ситуацию - нам надо разместить один объект в точке (10,15,14), а второй - сдвинуть на (2,2,2) относительно первого. Как это сделать? В принципе, можно твердо прописать в коде смещение первого объекта на (10,15,14), а второго - на (12,17,16), но что делать, если второй объект анимирован и изменят свое положение относительно первого с течением времени? А если он еще и вращается независимо от первого? Вот здесь и пригодятся матрицы - только они могут сочетать в себе большие количества разных видов трехмерных трансформаций и применять их к объекту за промежуток времени, не зависящий от количества преобразований. .

Матрицы

Ну вот мы и подошли к самому главному. Начнем изучать трансформации в трехмерном пространстве с использованием матриц. Но сначала нам придется усвоить, что означает “умножить матрицу на вектор (или точку)”. Если нам дана матрица [M] и вектор (точка) [V], то процесс их перемножения записывается так: Теперь распишем саму формулу (будем называть ее “неупрощенной” - она показывает общий принцип умножения матрицы на вектор): Если учесть, что рассматриваем мы только трансформации геометрии, а не проецирование, то формула примет следующий вид (назовем эту формулу “упрощенной” - она верна только для трансформаций геометрии): Однако, не советую упрощать, так как вы потеряете, например, возможность проецировать объекты, “баловаться” с перспективой и кое-что другое... Все-таки остановимся на неупрощенном варианте :). А теперь перейдем непосредственно к матрицам трансформаций и устройству графического ядра трехмерного движка. Взгляните на фрагмент кода (делающий то же самое, что и предыдущий, но через матрицы void tipa_cool_3d_engine_with_matrices(void) { ........ // Ща будем трансформировать load_identity_matrix(matrix); translate_matrix_XYZ(matrix, 25, 2.2, 29); scale_matrix_XYZ(matrix, 1.5, 0.3, 1.2); rotate_matrix_XYZ(matrix, 30, -30, 1.2); for (i=1; i<number_of_points_in_scene; i++) { multiply_vector_by_matrix(matrix); } draw_scene(); ........ } Прежде чем разбирать этот фрагмент по функциям, попробуем немного вникнуть в суть происходящего. Для этого представим себе процесс обработки геометрии более наглядно, однако для этого вам сначала понадобится понимание фразы “перемножение матриц”, а посему отсюда мы и начнем (математики это могут пропустить). Предположим, что нам даны две матрицы - [A] и [B]. Перемножим их Значения полученной матрицы C считаются по такой формуле: Расписывается это так: Вот и весь процесс перемножения матриц... А теперь начнем рассмотрение приведенного выше кода по функциям, предположив, что matrix - это массив из шестнадцати элементов, представляющий собой матрицу (float matrix[16];). .

load_identity_matrix(matrix); - Единичная матрица

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

translate_matrix_XYZ(matrix, Tx, Ty, Tz); - Матрица переноса

Эта функция создает матрицу переноса и умножает ее на матрицу, уже находящуюся в массиве matrix. Матрица переноса выглядит так: где Tx, Ty и Tz - соответственно значения переноса по осям X, Y и Z. После выполнения этой функции в массиве matrix будет находиться преобразование переноса в матричной форме - матрица переноса. P.S. Проверка этой и всех приведенных ниже матриц - умножение этой матрицы на вектор (X, Y, Z, W) с использованием упрощенной формулы, которую я уже приводил выше, например: X’ = X *1 + Y * 0 + Z * 0 + Tx = X + W * Tx, Y’ = X * 0 + Y * 1 + Z * 0 + Ty = Y + W * Ty, Z’ = X * 0 + Y * 0 + Z * 1 + Tz = Z + W * Tz, W’ = W; Получили обычные формулы переноса вектора (точки) по осям. Можете также попробовать использовать неупрощенную формулу - результат будет практически тот же, но W тоже будет участвовать в трансформациях: X’ = X *1 + Y * 0 + Z * 0 + W*Tx = X + W * Tx, Y’ = X * 0 + Y * 1 + Z * 0 + W*Ty = Y + W * Ty, Z’ = X * 0 + Y * 0 + Z * 1 + W*Tz = Z + W * Tz, W’ = X * 0 + Y * 0 + Z * 0 + W * 1 = W; .

scale_matrix_XYZ(matrix, Sx, Sy, Sz); - Матрица масштабирования

Эта функция создает матрицу масштабирования и умножает ее на матрицу, уже находящуюся в массиве matrix. Матрица масштабирования выглядит так: где Sx, Sy и Sz - соответственно значения коэффициентов растяжения (сжатия) по осям X, Y и Z. После выполнения этой функции в массиве matrix будет находиться совмещенное преобразование переноса и масштаба в матричной форме. .

rotate_matrix_XYZ(matrix, Rx, Ry, Rz); - Матрица вращения

Эта функция создает три матрицы вращения (по одной для каждой оси) и умножает их по очереди на матрицу, уже находящуюся в массиве matrix. Матрицы вращения выглядят так: по оси X - по оси Y - по оси Z - где Rx, Ry и Rz - соответственно значения углов вращения вокруг осей X, Y и Z. После выполнения этой функции в массиве matrix будет находиться суперпозиция преобразований переноса, масштаба и вращения по трем осям в матричной форме. Далее нам остается только умножить каждую точку сцены на полученную матрицу для преобразования объектов - это и делает функция multiply_vector_by_matrix(matrix). Формулу умножения матрицы на вектор я приводил выше. .

Вывод

Ну теперь, я думаю, все просекли то, что для реального совмещения трансформаций нам необходимо будет просто перемножать матрицы трансформаций. То есть, весь процесс сводится к двум основным формулам: где [M] - окончательная матрица (4х4) преобразования, [T] - матрица переноса, [S] - матрица сжатия(растяжения), [Rx], [Ry] и [Rz] - соответственно матрицы поворота вокруг осей X, Y и Z. Вторая формула имеет вид: где [M] - матрица преобразования, полученная выше, [V] - исходная точка в трехмерном пространстве и [V’] - трансформированная точка. Словами эти формулы описываются так: “...Для построения матрицы [M] желаемое преобразование представляется в виде суперпозиции простых преобразований, матрицы которых известны... Для осуществления желаемого преобразования нужно применить матрицу [M] ко всем вершинам многоугольников, из которых состоит объект...” .

Дегтя! Дегтя!...

...В каждой бочке меда есть ложка примесей :). Рассмотрим снова случай расчетов только по формулам (см. код выше). Итак для каждой точки вызывается 9 функций. Все они объявлены как _inline, расходы процессорного времени на их вызов равны нулю, и поэтому мы получаем: translate_by_... - 1 сложение scale_by_... - 1 умножение rotate_by_... - 2(4) выборки из таблицы синусов/косинусов (а при кривости ручек вообще просто вычисление этих функций 2(4) раза) + 2 сложения + 1 изменения унарного знака + 4 умножения Итого при повторе каждой из функций три раза мы получим 9 сложений, 15 умножений, 3 операции изменения знака числа и 6(12) выборок из таблицы (кривость ручек обсуждалась выше) для каждой точки сцены или объекта. Ну как вам системные требования? :) Подвергнем такому же анализу случай с матрицами: Сама процедура премножения матриц для сложения преобразований занимает 64 умножения, 48 сложений плюс опять же выборки из таблицы косинусов и синусов и изменение знака - зато выполняется не в цикле, а всего один (два, три, четыре, пять....но не тысячу) раз. Процедура (неупрощенная) умножения матрицы на вектор занимает 16 умножений и 12 сложений. Упрощенная же требует всего 12 умножений и 9 сложений, что превосходит показатели вычислений по формулам. Думаете, это плюс? Не уверен... Рассмотрим реальную ситуацию: если вам надо произвести, предположим, только перенос по одной оси (например, сдвинуть точки на 3 единицы по оси X), то, используя формулы, вы затратите 1 сложение, а используя матрицы (даже без их предварительного перемножения) - те же 12 умножений и 9 сложений (или даже 16 умножений и 12 сложений при использовании неупрощенного варианта процедуры). Налицо тот факт, что матрицы занимают гораздо больше процессорного времени, чем вычисления напрямую по формулам, но предоставляют более гибкие средства для манипуляций с геометрией и трансформациями. Матрицы хороши для анимации, навигации в трехмерном пространстве и деформации объектов в реальном времени, так как позволяют комбинировать производимые изменения. Хотя однозначный выбор в пользу матриц сделать нельзя, стоит заметить, что всякие “фишки” вроде OpenGL и Direct3D используют матрицы, причем вроде бы даже вполне успешно :). .

Оптимизация, оптимизация и еще раз оптимизация...

Сейчас я немного расскажу о методах, которые я надумал за неделю возни с этим текстом для оптимизации всей этой “бороды”. Рассмотрим их по порядку: Первый метод напрашивается сам - оптимизацию создания матрицы можно провести, убрав из нее перемножение матриц. Суть в следующем - мы “ручками” перемножаем матрицы в следующем порядке - [T]*[Rx]*[Ry]*[Rz]*[S], а полученную матрицу используем как матрицу геометрицеских преобразований. Остается только заполнять ее (вызывая только одну функцию) и умножать на вектор. Используйте упрощенную формулу умножения матрицы на вектор, если вам не нужны преобразования перспективы и модуль этого преобразования у вас отделен от модуля трансформации геометрии. Поднимите левую руку высоко вверх, опустите и скажите: “А ну его!”, напишите три функции умножения матрицы на вектор - неупрощенную, упрощенную и “совсем упрощенную” - такую, где W всегда равно единице (она будет занимать 9 умножений и 9 сложений). Потом вызывайте одну из трех по необходимости - неупрощенную, если в вашей матрице заполнен нижний ряд и W вектора не равно одному, упрощенную - если W не равно одному, а нижний ряд матрицы не заполнен и совсем упрощенную - если и нижний ряд не заполнен и W вектора равно одному. Три этих метода и умение оптимизировать код на ассемблере дадут вам большее преимущество в скорости перед вычислениями с использованием формул везде, где оно (преимущество) возможно и достижимо. Во как. Copyright 2001 by AWDP .