К. В. Рябинин вычислительная геометрия и алгоритмы компьютерной графики
 Скачать 1.44 Mb.
|
|
4. Размещение объектов на сцене и проекция на экран Для того чтобы создать итоговое изображение, примитивы, из которых состоят объекты сцены, должны быть спроецированы из пространства сцены на плоскость экрана. Однако перед этим, как правило, объекты должны быть размещены на сцене. Их положение в пространстве характеризуется положением принадлежащих им вершин. Согласованное изменение положения всех вершин объекта приведёт к изменению его положения в пространстве. В трёхмерном пространстве у каждого объекта есть 6 степе- ней свободы: перемещение в трёх направлениях и три поворота во- круг взаимно перпендикулярных осей. В компьютерной графике к операциям размещения относят также масштабирование (изменение размера) и наклон объекта. 4.1. Аффинные преобразования Как правило, каждый объект имеет некоторую свою локаль- ную систему координат, в которой заданы его вершины. Например, если объект был создан в некотором 3D-редакторе, его вершины за- даны в системе координат, определённой этим редактором. Если вме- сте с этим объектом на сцену будет загружен другой объект, создан- ный в том же редакторе, но отдельно от первого, скорее всего, эти два объекта пересекутся в пространстве, так как их вершины будут распределены в пересекающихся областях пространства. Для того чтобы корректно расставить объекты на сцене, им необходимо задать некоторое положение в глобальной системе ко- ординат сцены. Для перехода из одной системы координат в другую удобно использовать аффинные преобразования – отображения вида f : R n → R n , сохраняющие свойство параллельности прямых линий. 17 Иначе говоря, аффинными называются преобразования, кото- рые можно получить следующим образом: 1. Выбрать «новый» базис пространства с «новым» началом ко- ординат t 2. Каждой точке v пространства поставить в соответствие точку f (v) , имеющую те же координаты относительно «новой» си- стемы координат, что и v относительно «старой». К аффинным преобразованиям относятся такие действия, как 1. Параллельный перенос. 2. Масштабирование. 3. Поворот. 4. Наклон. Осуществлять их удобнее всего при помощи матриц преоб- разования . Любое аффинное преобразование может быть выражено в виде f (v) = M v + t, где v – вектор-столбец координат исходной точки, M – матрица преобразования, t – вектор-столбец координат начала «новой» системы, выраженных в «старой» системе. Для трёхмерного случая матрица M имеет размерность 3 × 3 , а векторы v и t , соответственно, размерность 3 . Однако для упро- щения вида преобразований в компьютерной графике принято «вно- сить» вектор t в матрицу M . В этом случае, чтобы удовлетворить требованиям к операндам при умножении, её размерность увеличи- вают до 4 × 4 , а размерность вектора v увеличивают до 4 . Для это- го M дополняется строкой (0, 0, 0, 1) , а вектор-столбец v – числом 1. Так происходит переход к однородным координатам . Аффинное преобразование в этом случае принимает вид f (v) = M v. Матрица аффинного преобразования, по сути, описывает «но- вую» систему координат, к которой осуществляется переход при по- мощи соответствующего отображения (рис. 4). 18 Рис. 4. Матрица аффинного преобразования Векторы (m 0 , m 1 , m 2 ) , (m 4 , m 5 , m 6 ) и (m 8 , m 9 , m 10 ) , составленные из соответствующих элементов матрицы M , пред- ставляют собой разложение базиса «новой» системы координат в базисе «старой»; вектор (m 12 , m 13 , m 14 ) представляет собой начало «новой» системы относительно «старой». Основываясь на таком принципе построения, нетрудно выве- сти матрицы для описанных выше аффинных преобразований: T = 1 0 0 x 0 1 0 y 0 0 1 z 0 0 0 1 , где T – матрица переноса, x, y, z – значения переноса по соответствующим осям. S = s x 0 0 0 0 s y 0 0 0 0 s z 0 0 0 0 1 , где S – матрица масштабирования, s x , s y , s z – значения масштаба по соответствующим осям. R = x 2 (1 − c) + c xy(1 − c) − zs xz(1 − c) + ys 0 yx(1 − c) + zs y 2 (1 − c) + c yz(1 − c) − xs 0 xz(1 − c) − ys yz(1 − c) + xs z 2 (1 − c) + c 0 0 0 0 1 , 19 где R – матрица поворота вокруг начала координат, c = cos θ , s = sin θ , θ – угол поворота, x, y, z – вектор, задающий ось поворота, причём |(x, y, z)| = 1 Задание: Вывести матрицу наклона на угол θ Подсказка: Наклон рассмотреть отдельно в каждой координатной плоскости (в результате получится 6 различных матриц, соответствующих различным ко- ординатным плоскостям). Суперпозиция аффинных преобразований достигается путём перемножения соответствующих матриц. Так, например, если необ- ходимо изменить размер объекта и переместить его, каждую из его вершин необходимо умножить (слева) на матрицу M = T S, где T – матрица переноса, S – матрица масштабирования. Если требуется повернуть объект вокруг точки с координата- ми (x, y, z) , каждую из его вершин необходимо умножить (слева) на матрицу M = T 1 RT 2 , где T 1 – матрица переноса на (x, y, z) , R – матрица поворота, T 2 – матрица переноса на ( −x, −y, −z) При комбинировании матричных преобразований необходимо иметь в виду, что умножение матриц ассоциативно, но некоммута- тивно. Преобразование, записанное как произведение матриц, чита- ется слева направо и представляет собой цепочку последовательных изменений системы координат объекта. Для того, чтобы правильно его интерпретировать, можно воспользоваться следующим нефор- мальным правилом: воспринимать каждую матрицу в цепочке как 20 очередную команду объекту совершить то или иное действие отно- сительно его текущей локальной системы координат. Ещё одно важное свойство матричных аффинных преобразо- ваний – невырожденность. Для любой матрицы аффинного преобра- зования существует обратная, более того, она соответствует обратно- му преобразованию. Например, если T – матрица переноса, то T −1 – матрица, которая «вернёт на место» объект, перемещённый при по- мощи T . Данное свойство справедливо и для произвольной цепочки аффинных преобразований. Таким образом, любое преобразование можно «отменить», умножив (слева) вершины объекта, трансформи- рованного матрицей M , на матрицу M −1 Поскольку положения объектов на сцене обычно динамически изменяются (например, в ответ на действия пользователя), коорди- наты их вершин оставляют локальными, и перед каждым выводом объекта на экран применяют к ним необходимые преобразования. Частое переписывание значений в видеопамяти неэффективно, так как шина передачи данных между ОЗУ и видеопамятью является уз- ким местом с точки зрения скорости работы. При этом умножение матрицы преобразования на координаты каждой вершины имеет ап- паратную поддержку графического процессора, потому выполняет- ся достаточно быстро. Настолько быстро, что в процессе подготов- ки каждого кадра за приемлемое для демонстрации плавных движе- ний время удаётся обрабатывать сотни тысяч вершин на мобильных устройствах и миллионы вершин на настольных компьютерах. Умножение происходит на этапе преобразования вершин графического конвейера. Каждому объекту сцены ставится в соот- ветствие его матрица преобразования, которая называется матрицей модели (англ. Model Matrix ). Она хранится вместе с дескриптором объекта в ОЗУ (предполагается, что сами данные объекта хранятся в видеопамяти, а в ОЗУ – лишь его дескриптор, необходимый для оперирования объектом на стороне приложения). Перед отрисовкой очередного кадра эта матрица изменяется так, чтобы обеспечить текущее положение объекта на сцене, и передаётся в видеопамять. Пересылка 16 значений матрицы происходит значительно быстрее, 21 чем копирование всего массива вершин объекта, поэтому частое её изменение не снижает производительность. Суперпозиция аффинных преобразований путём перемноже- ния соответствующих матриц позволяет сохранить взаимное распо- ложение объектов, тем самым объединив их «иерархическими» свя- зями. При этом справедливо следующее выражение: M = M p M c , где M – итоговая матрица для объекта, M p – матрица «родительского» объекта (относительно которого должны быть расположены «дочерние» объекты), M c – матрица «дочернего» (данного) объекта, обеспечивающая из- менение его положения относительно его «родителя». Например, если необходимо разместить на сцене модель сто- ла, а на ней – модель вазы, то удобно задать матрицу преобразования для вазы, изменяющую её положение относительно начала коорди- нат стола, матрицу преобразования стола, изменяющую его положе- ние относительно начала координат сцены, затем трансформировать стол его матрицей, а к вазе – результат перемножения, как показано выше. В этом случае появляется возможность организовать зависи- мость положения вазы от положения стола на сцене: ваза будет «ав- томатически» перемещаться вслед за столом, оставаясь относитель- но него неподвижной. На таком принципе можно создавать сложные иерархические конструкции и минимальными изменениями управ- лять их положением на сцене. 4.2. Углы Эйлера и шарнирный замок Особого внимания заслуживает вопрос комбинирования пово- ротов объекта. Как было отмечено выше, ориентацию объекта в про- странстве можно задать при помощи трёх поворотов вокруг взаимно перпендикулярных осей. Такой способ носит название углов Эйлера (англ. Euler Angles ) и предполагает выражать ориентацию объекта в виде трёх числовых значений, соответствующих трём углам. Кон- кретный способ выбора осей поворота для определения углов Эй- 22 лера имеет множество вариаций. Наиболее часто используется спо- соб Тэйта-Брайана (англ. Tait-Bryan Angles ), при котором все три оси различны. Углы поворота имеют различные названия в зависимости от конкретной предметной области: способ Тэйта-Брайана используют- ся в теоретической механике, авиации, мореплавании, навигации. В компьютерной графике принято в данном случае использовать авиа- ционную терминологию и называть углы так: тангаж (англ. Pitch ) – поворот объекта вокруг поперечной оси; рыскание (англ. Yaw ) – по- ворот объекта вокруг вертикальной оси; крен (англ. Roll ) – поворот объекта вокруг продольной оси. Наименование углов продемонстри- ровано на рис. 5. Рис. 5. Наименование углов Тэйта-Брайана Для задания ориентации удобно положить оси тангажа, рыс- кания и крена совпадающими с осями локальной системы координат объекта. В этом случае можно уйти от специальных названий углов и именовать их в соответствии с осями координат: r x , r y , r z Важным свойством поворотов, выраженных углами Эйлера (и углами Тэйта-Брайана в частности), является зависимость от поряд- ка применения. Так, например, при фиксированных числовых значе- ниях углов применение поворотов в последовательности r x , r y , r z и в последовательности r y , r x , r z дадут различные итоговые ориента- ции объекта. При этом не важно, выполняются ли эти повороты от- носительно глобальной (статичной, не поворачивающейся вместе с объектом) или же относительно локальной (меняющей ориентацию с каждым поворотом) системы координат – их порядок в обоих случа- 23 ях будет важен. Поэтому, при оперировании углами Эйлера, помимо задания осей, всегда оговаривают порядок применения (иерархию) поворотов. Если оси вращения совпадают с осями локальной системы ко- ординат объекта, центр объекта совпадает с началом координат и за- дан некоторый порядок применения поворотов, например, r x , r y , r z , то итоговая ориентация объекта может быть получена путём умно- жения каждой его вершины слева на матрицу вида M = R x (r x )R y (r y )R z (r z ), где M – итоговая матрица для объекта, R x (r x ) – матрица поворота вокруг вектора (1, 0, 0) на угол r x , R y (r y ) – матрица поворота вокруг вектора (0, 1, 0) на угол r y , R z (r z ) – матрица поворота вокруг вектора (0, 0, 1) на угол r z Таким образом, повороты на углы Тэйта-Брайана оказываются достаточно интуитивным способом задания ориентации объекта. Однако этот способ, как и любой, основанный на углах Эйлера, имеет серьёзный недостаток: шарнирный замок (англ. Gimbal Lock ). Шарнирный замок (складывание рамок, блокировка осей, карданная блокировка) – это ситуация потери одной из степеней свободы в про- цессе вращения при определённых значениях углов Эйлера. Он возникает в момент, когда второй по иерархии поворот (в приведённом выше примере – поворот на угол r y ) составляет ±π/2 Причина этой ситуации состоит в том, что после второго поворота локальная ось первого поворота совпадает с глобальной осью третье- го поворота. В результате получается, что первый и третий повороты вращают объект вокруг одной и той же глобальной оси, то есть те- ряется одна из степеней свободы. Эта ситуация продемонстрирована на рис. 6. Как можно видеть, ось X на рис. 6 (а) коллинеарна оси Z на рис. 6 (г), в результате чего повороты, изображённые на этих рисун- ках (первый и третий повороты в иерархии углов Эйлера) влияют на одну и ту же степень свободы объекта. 24 Рис. 6. Шарнирный замок: (а) – начальное положение объекта, (б) – положение после поворота на угол r x , (в) – положение после поворота на угол r y = π/2, (г) – положение после поворота на угол r z Ещё одной проблемой углов Эйлера (и углов Тэйта-Брайана в частности) является сложность анимации. Если необходимо плавно изменить ориентацию объекта по кратчайшему пути, линейная ин- терполяция углов Эйлера не даст корректного результата (равно как и линейная интерполяция географических координат, по сути тоже являющихся углами Эйлера, не даст кратчайший путь между двумя точками на поверхности планеты). Решить указанные проблемы можно путём представления по- воротов при помощи кватернионов (англ. Quaternion ). Однако дан- ный подход читателю предлагается изучить самостоятельно. Часто при создании интерактивных систем визуализации тре- буется связать поворот объекта с командами пользователя. Пусть, на- пример, нажатие клавиш со стрелками должно поворачивать объект в соответствующих направлениях вне зависимости от его текущей ориентации. Если использовать углы Эйлера (изменяя соответствующий угол на некоторую величину в ответ на нажатие клавиши), требо- вание независимости от текущей ориентации выполнено не будет: например, при повороте на π вокруг оси X , направление поворотов вокруг оси Y инвертируется. Однако вместо аккумуляции углов и создания из них матрицы поворота, можно аккумулировать саму матрицу поворота. В начале работы программы эта матрица должна быть единичной (либо долж- на содержать начальный поворот объекта). Нажатие каждой клави- 25 ши со стрелкой должно поворачивать объект на некоторый угол ∆ ϕ вокруг глобальной оси без учёта предыдущих поворотов. В терминах матриц это означает, что текущая матрица поворо- та M должна быть умножена справа на матрицу поворота R v (∆ ϕ ) , составленную на основе угла ∆ ϕ и вектора v , задающего ось враще- ния. Вектор v необходимо выбрать таким образом, чтобы он выра- жал глобальную ось a желаемого поворота в системе координат, за- даваемой текущей матрицей M . Это означает, что M v = a , то есть v = M −1 a Так как M – матрица поворота, её обратная матрица совпадает с транспонированной: M −1 = M T . Так как глобальная ось поворота a , скорее всего, совпадает с одной из координатных осей, для полу- чения вектора v достаточно просто взять соответствующий столбец матрицы M T (см. рис. 4), или соответствующую строку матрицы M Например, если нажата клавиша со стрелкой вправо и поворот должен осуществляться вокруг глобальной оси Y , новая матрица по- ворота определяется как M ′ = M R (m 1 ,m 5 ,m 9 ) (∆ ϕ ), где M ′ – итоговая матрица поворота (которая станет текущей на сле- дующем шаге), M – текущая матрица поворота, R (m 1 ,m 5 ,m 9 ) (∆ ϕ ) – матрица поворота на угол ∆ ϕ вокруг вектора, со- ставленного из элементов 1, 5 и 9 матрицы M По нажатию клавиши со стрелкой влево формула вычисления матрицы остаётся прежней, но в качестве величины угла использу- ется −∆ ϕ Аналогично, если нажата клавиша со стрелкой вверх и пово- рот должен осуществляться вокруг глобальной ост X , новая матрица поворота определяется как M ′ = M R (m 0 ,m 4 ,m 8 ) (∆ ϕ ), где R (m 0 ,m 4 ,m 8 ) (∆ ϕ ) – матрица поворота на угол ∆ ϕ вокруг вектора, составленного из элементов 0, 4 и 8 матрицы M 26 |