Вопросы эффективности вычислений

Рассмотрим проблему ускорения вычислений в одной из самых трудоемких операций компьютерной графики – операции поворота точки относительно начала координат. Как было показано ранее, для ее выполнения необходимо произвести 4 операции умножения, 2 операции сложения, а также вычислить значения синуса и косинуса угла поворота. Напомним вид формул поворота:

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

Рис. 12. Вывод формулы О. Бьюнемана.

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

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

Будем искать выражение координат x и y через x' и y'. На оси Ox отложим отрезок OS, такой что OS = x'. Тогда x = OS – QS = x' – QS.. Здесь отрезок QS является горизонтальной проекцией отрезка PT, где

PT = PU + UT, PU = y', ,

где

.

Теперь, зная x, можно выразить y в виде суммы длин отрезков QV и VP. Так как длины отрезков PV и PT равны как радиусы окружности с центром в точке P, то

.

Обозначим PT = T^*, отсюда следует, что

,

Последние три равенства будем называть формулой Бьюнемана.

Пример композиции трехмерных преобразований

Путем объединения элементарных трехмерных преобразований можно получить другие преобразования. Рассмотрим пример. Задача состоит в том, чтобы преобразовать отрезки и из начальной позиции в конечную, так как показано на рис. 13. Точка Р₁ переносится в начало координат, располагается вдоль отрицательной полуоси z, а помещается в плоскости yz в той ее половине, где ось у положительна. На длины отрезков преобразование не воздействует.

Рис. 13. Преобразование точек Р₁, Р₂ и Р₃ из начальной позиции в конечную

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

1. Перенос точки Р₁ в начало координат.

2. Поворот вокруг оси у до совмещения с плоскостью yz.

3. Поворот вокруг оси х до совмещения с отрицательной плоскостью z.

4. Поворот вокруг оси z до совмещения с плоскостью yz.

Шаг 1. Перенос Р₁ в начало координат:

Применение Т к Р₁, Р₂ и Р₃ дает

Р₁' = P₁T(-x₁, -y₁, -z₁) = [0 0 0 1],

Р₂' = P₂T(-x₁, -y₁, -z₁) = [x₂-x₁ y₂-y₁ z₂-z₁ 1],

Р₃' = P₃T(-x₁, -y₁, -z₁) = [x₃-x₁ y₃-y₁ z₃-z₁ 1].

Шаг 2. Поворот вокруг оси у.

На рис. 14 показаны отрезки и после шага 1 и проекция на плоскость xz.

Поворот производится на положительный угол А, для которого

, ,

где

.

Рис. 14. Поворот вокруг оси у; проекция поворачивается до совмещения с отрицательной полуосью z

Рис. 15.Положение отрезка после шага 2

В результате подстановки этих значений в матрицу Ry(A) получаем:

Шаг 3. Поворот вокруг оси х.

На рис. 15 показан отрезок после шага 2.

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

cos(-B) = cosB = , sin(-B) = -sinB = ,

где

.

Результатом поворота на шаге 3 является:

,

т.е. теперь совпадает с отрицательной полуосью z.

Шаг 4. Поворот вокруг оси z.

На рис. 16 показаны и после шага 3, когда Р₂'' лежит на отрицательной полуоси z, а Р₃''' - в точке

Поворот производится на положительный угол С, для которого

cosC = y₃'''/D₂, sinC = x₃'''/D₂, D₂ = .

После шага 4 получается конечный результат.

Результирующая матрица

T(-x1,-y1,-z1)Ry(A)Rx(B)Rz(C) = TR

описывает искомое преобразование.

Рис. 16. Поворот вокруг оси z; проекция поворачивается до совмещения с осью у

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

Верхняя подматрица размером 33 ортогональная матрица, составленная из трех векторов R_x = [r_x1 r_x2 r_x3], R_y = [r_y1 r_y2 r_y3] и R_z = [r_z1 r_z2 r_z3], в которые будут преобразованы орты осей x, y и z соответственно.

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

.

Здесь - длина вектора .

Вектор, перпендикулярный плоскости, построенной на векторах и , должен быть направлен вдоль оси x, так как вектор лежит вдоль оси z, а вектор лежит в плоскости yz. Этот вектор задается векторным произведением

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

Искомая матрица преобразования есть