Кватернионы в компьютерной графике
код для вставкиСкачатьДано изложение алгебры кватернионов ориентированное на использование в компьютерной
графике
Математические основыкомпьютерной графики В.В.Усов 1 Кватернионыв компьютерной графике 1.1 Определение кватерниона Кватернионы были открыты Гамильтоном в XVIII веке.Кватернионы являются некоммутативным расширением поля комплексных чисел,и поэтому часто называют гиперкомплексными числами. Кватернион по аналогии с комплексными числами можно представить в виде q = w + xi + yj + zk,где w,x,y,z- вещественные числа,а i,j,k -мнимые единицы.Сложение кватернионов определяется аналогично сложению комплексных чисел,а умножение кватернионов определяется правилами умножения мнимых единиц: i 2 = j 2 = k 2 = −1,i ∙ j = k,j ∙ k = i,k ∙ i = j,j ∙ i = −k,k ∙ j = −i,i ∙ k = −j. Легко проверяется,что операция умножения кватернионов ассоциативна (q 1 ∙ q 2 ) ∙ q 3 = q 1 ∙ (q 2 ∙ q 3 ). 1.2 Сопряжение,модуль и обратный кватернион По аналогии с комплексными числами в пространстве кватернионов вводится операция сопряжения. Если q = w +xi +yj +zk,то сопряженный с q кватернион q определяется правилом q = w −xi −yj −zk. Отметим,что операция сопряжения обладает свойством: q 1 ∙ q 2 = q 2 ∙ q 1 . Это следует из того,что данное соотношение справедливо на множестве 1,i,j,k .Легко проверить,что q ∙ q = q ∙ q = w 2 +x 2 +y 2 +z 2 . Модуль |q| кватерниона q определяется выражением |q| = q q. Несмотря на то,что в пространстве кватернионов отсутствует коммутативность операции умножения, легко устанавливается,что |q 1 ∙ q 2 | = |q 2 ∙ q 1 | = |q 1 | ∙ |q 2 |. Из выражения q ∙ q = q ∙ q = |q| 2 получаем,что если положить q −1 = q |q| 2 , то q −1 ∙ q = q ∙ q −1 = 1.Поэтому кватернион q −1 = q |q| 2 , называется обратным для кватерниона q и этим оправдано его обозначение. 1 1.3 Геометрия кватернионов Рассмотрим четырехмерное евклидово пространствоE 4 с ортонормированным базисом e 1 ,e 2 ,e 3 ,e 4 . Построим линейное отображение Θ множества кватернионов Q в E 4 определив его на множестве единиц(линейном базисе кватернионов) следующим образом Θ(1) = e 1 ,Θ(i) = e 2 ,Θ(j) = e 3 ,Θ(k) = e 4 . Пусть X ∈ E 4 q ∈ Q X = x 1 e 1 +x 2 e 2 +x 3 e 3 +x 4 e 4 ,q = w +xi +yj +zk, Положим [X] = (x 1 ,x 2 ,x 3 ,x 4 ),[q] = (w,x,y,z). Тогда имеем [Q(q)] = [q].Отметим,что для любого q ∈ Qсправедливо равенство |Θ(q)| = |q| Отображение Θпозволяет перенести на линейное пространство кватернионов Qважнейшие понятия. Расстояние между кватернионами ρ(q 1 ,q 2 ) = |Θ(q 1 ) −Θ(q 2 )| = |q 1 −q 2 |. Скалярное произведение кватернионов (q 1 ,q 2 ) = (Θ(q 1 ),Θ(q 2 )) = Re(q 1 ∙ q 2 ), где Re(q) действительная часть кватерниона,т.е.для [q] = (w,x,y,z) [Re(q)] = (w,0,0,0). Подпространства Re(Q)и Im(Q) Для [q] = (w,x,y,z) положим [Im(q)] = (0,x,y,z).Тогда q = Re(q) +Im(q) и для любых a,b ∈ Q имеем (Re(a),Im(b)) = 0.Обозначим Re(Q) = {q ∈ Q|Im(q) = 0} и Im(Q) = {q ∈ Q|Re(q) = 0}.Tогда Q = Re(Q) ⊕Im(Q) прямая сумма подпространств. Угол между кватернионами cos( (q 1 ,q 2 )) = (q 1 ,q 2 ) |q 1 ||q 2 | . Cопоставим кватерниону q три линейных преобразования пространства Q q R :Q →Q, q L :Q →Q, U(q):Q →Q по правилам q R (a) = a∙ q,q L (a) = q ∙ a,и U(q)(a) = q ∙ a∙ q −1 .Изучим действие этих преобразований. Лемма 1 ρ(q R (q 1 ),q R (q 2 )) = |q||q 1 −q 2 |, ρ(q L (q 1 ),q L (q 2 )) = |q||q 1 −q 2 |, ρ(U(q)(q 1 ),U(q)(q 2 )) = |q 1 −q 2 |, Лемма 2 (Об инвариантных подпространствах) Для произвольных a ∈ Q,|a| = 0 и q ∈ Qимеем U(a)(Re(q)) ∈ Re(Q), U(a)(Im(q)) ∈ Im(Q), (a ∙ Re(q) ∙ a) ∈ Re(Q), (a ∙ Im(q) ∙ a) ∈ Im(Q). 2 Доказательство.Первое утверждение очевидно.Второе можно доказать непосредственнымвычислением. Но,как мы покажем,оно является прямым следствием первого.Действительно,из |U(a)(q)| = |q| вытекает,что (U(a) сохраняет скалярное произведение.Имеем q ∈ Im(Q) ⇐⇒(1,q) = 0. Поскольку (U(a)(1),U(a)(q)) = (1,U(a)(q)) = (1,q), то для q ∈ Im(Q) получаем(1,U(a)(q)) = 0.Поэтому из q ∈ Im(Q) следует,что U(a)(q) ∈ Im(Q).Третье утверждение очевидно.Для доказательства последнего утверждения разделим произведение (a ∙ Im(q) ∙ a) на |a| 2 ,и сведем таким образом к уже установленному второму утверждению. Лемма 3 cos( (q R (q 1 ),q R (q 2 ))) = cos( (q R (q 1 ),q R (q 2 ))). Для действия q L равенства аналогичны. 1.4 Правило умножения кватернионов Непосредственным вычислением устанавливается Лемма 4 Для q 1 ,q 2 ∈ Qимеем Re(q 1 ∙ q 2 ) = Re(q 1 )Re(q 2 ) −(Im(q 1 ),Im(q 2 )), Im(q 1 ∙ q 2 ) = Re(q 1 )Im(q 2 ) +Re(q 2 )Im(q 1 ) +Im(q 1 ) ×Im(q 2 ), где Im(q 1 ) ×Im(q 2 ) = i j k x 1 y 1 z 1 x 2 y 2 z 2 , если [q 1 ] = (w 1 ,x 1 ,y 1 ,z 1 ),[q 2 ] = (w 2 ,x 2 ,y 2 ,z 2 ). Из леммы получаем правило умножения кватернионов.Пусть [q 1 ] = (w 1 ,v 1 ),[q 2 ] = (w 2 ,v 2 ),w 1 ,w 2 ∈ R,v 1 ,v 2 ∈ R 3 Тогда [q 1 ∙ q 2 ] = (w 1 w 2 −(v 1 ,v 2 ),w 1 v 2 +w 2 v 1 +v 1 ×v 2 ) 1.5 Сферические координатыкватерниона Пусть q ∈ Q,[q] = (w,x,y,z).Сферические координаты кватерниона (ρ,φ,ψ,θ) связаны с его декартовыми координатами (w,x,y,z) следующими соотношениями: w = ρcos(φ), x = ρsin(φ) cos(ψ), y = ρsin(φ) sin(ψ) cos(θ), z = ρsin(φ) sin(ψ) sin(θ), где ρ ∈ (0,∞),φ ∈ (0,π),ψ ∈ (0,π),θ ∈ (0,2π). Выражения сопоставляющие декартовым координатам сферические имеют вид: ρ = w 2 +x 2 +y 2 +z 2 , φ = arccos(w/ w 2 +x 2 +y 2 +z 2 ), ψ = arccos(x/ x 2 +y 2 +z 2 ), угол θ определяется из равенств cos(θ) = y/ y 2 +z 2 , sin(θ) = z/ y 2 +z 2 . 3 1.6 Степень кватерниона.Формула Эйлера Запишем кватернион q в виде q = |q|(cos(φ) +sin(φ) ∙ I), где I ∈ Im(Q),|I| = 1 Используя правило умножения кватернионов,получаем q 2 = |q|(cos 2 (φ) −sin 2 (φ) +2 cos(φ) sin(φ) ∙ I) или q 2 = |q| 2 (cos(2φ) +sin(2φ) ∙ I) По индукции получаем формулу Эйлера для степени кватерниона q n = |q| n (cos(nφ) +sin(nφ) ∙ I),n = 1,2,3,... 1.7 Отображениe exp:Q →Q Отображение exp:Q →Q для q ∈ Qопределяется формулой exp(q) = ∞ n=0 q n n! . Этот ряд сходится для всех q ∈ Q.Представив кватернион q в виде q = |q|(cos(φ) +sin(φ) ∙ I), выразим exp(q) через элементарные функции.Используя формулу Эйлера легко получаем exp(q) = ∞ n=0 |q| n (cos(nφ) +sin(nφ)I) n! или exp(q) = ∞ n=0 |q| n cos(nφ) n! +I ∙ ∞ n=0 |q| n sin(nφ) n! . Для вычисления сумм A = ∞ n=0 |q| n cos(nφ) n! , B = ∞ n=0 |q| n sin(nφ) n! , заметим,что A+B ∙ i = ∞ n=0 (|q| exp(iφ)) n n! = exp(|q| exp(iφ)) = exp(|q|(cos(φ) +i sin(φ))). Но exp(|q|(cos(φ) +i sin(φ))) = exp(|q|(cos(φ))(cos(sin(φ)) +i sin(sin(φ))). Следовательно A = exp(|q|(cos(φ))) ∙ cos(sin(φ)), B = exp(|q|(cos(φ))) ∙ sin(sin(φ)). Итак,установлена Лемма 5 Если q = |q|(cos(φ) +sin(φ) ∙ I), где I ∈ Im(Q),|I| = 1,то exp(q) = exp(|q|(cos(φ))) ∙ cos(sin(φ)) +exp(|q|(cos(φ))) ∙ sin(sin(φ)) ∙ I. 4 1.8 Вращение пространства E 3 индуцированное кватернионом Пусть q ∈ Q,|q| = 0 и U(q):Q →Qзадано соотношением U(q)(s) = q ∙ s ∙ q −1 . Тогда имеем |U(q)(s)| = |s|,и из леммы об инвариантных подпространствах следует,что отображение U(q):Im(Q) →Im(Q) сохраняет длины векторов.Покажем,что отображение является вращением пространства Im(Q) ≈ E 3 . Рассмотрим множество неподвижных точек I(q) отображения U(q) I(q) = {s ∈ Im(Q)|U(q)(s) = s}. Если s ∈ I(q),то q ∙ s = s ∙ q. Пусть s ∈ Im(Q),q = w + v,w ∈ Re(Q),v ∈ Im(Q).Используя правило умножения кватернионов получаем sq = w ∙ s +s ∙ v = −(s,v) +w ∙ s +s ×v, qs = w ∙ s +v ∙ s = −(s,v) +w ∙ s +v ×s. Следовательно,если s ∈ I(q),то s×v = v×s.Из s×v = v×s получаем,что s = λv,где λ-действительное число.Итак,установлена Лемма 6 Пусть q ∈ Q,[q] = (w,v),v = (x,y,z).Tогда (U(q)(s) = s) =⇒(s = λ(xi +yj +zk)) . Для дальнейшего нам понадобится следующее. Теорема 1 Пусть ϕ:L →L -линейное преобразование линейного пространства конечной размерности n,[ϕ] E E -матрица ϕ в базисе E =< e 1 ,e 2 ,...,e n > определенная равенством [ϕ(X)] E = [X] E [ϕ] E E ,где [X] E = (x 1 ,x 2 ,...,x n ) -координаты вектора X ∈ L в базисе E. Тогда определитель χ(ϕ,λ) = det([ϕ] E E −λ ∙ I) называемый характеристическим многочленом линейного преобразования ϕ зависит от выбора базиса. Из этой теоремы следует,что определитель det(ϕ) = det([ϕ] E E ) является инвариантом линейного преобразования. Легко устанавливается Лемма 7 Пусть p,q ∈ Q.Тогда 1)Линейные преобразования p L :Q →Q,q R :Q →Q, перестановочны p L ◦ q R = q R ◦ p L . 2) U(p) = U(λ ∙ p) для любых p ∈ Q,|p| > 0,λ ∈ R,λ = 0. 3) Если |p| = 0,то U(p) = 1 |p| 2 (p L ◦ p R ) Лемма 8 Пусть p ∈ Q. Q = Re(Q) ⊕I(p) ⊕I(p) ⊥ - разложения пространства в прямуюсумму инвариантных относительно преобразования U(p):Q →Q подпространств.Toгда определители det(U(p) 4 ) = 1,det(U(p) 3 ) = 1,det(U(p) 2 ) = 1, где U(p) 4 = U(p),U(p) 3 = U(p)| Im(Q) ,U(p) 2 = U(p)| I(p) ⊥ . 5 Доказательство.На каждом из инвариантных подпространств U(p) сохраняет расстояние.Поэтому определители могут принимать лишь два значения +1,−1.Преобразование U(p) гомотопно тождественному.Поскольку det(U(1)) = 1,то и det(U(p) i ) = 1. Лемму можно установить также вычислив предварительно матрицы [p L ],[p R ] и [U(p)] в естественном базисе < 1,i,j,k >пространства Q.Приведем эти матрицы для [p] = (w,x,y,z),|p| = 1. [ p R ] = w −x −y −z x w z −y y −z w x z y −x w [p L ] = w x y z −x w z −y −y −z w x −z y −x w [U(p)] = w 2 +x 2 +y 2 +z 2 0 0 0 0 x 2 +w 2 −z 2 −y 2 2xy +2wz 2xz −2wy 0 2xy −2wz y 2 −z 2 +w 2 −x 2 2 y z +2wx 0 2xz +2wy 2y z −2wx z 2 −y 2 −x 2 +w 2 Матрица [U(p) 3 ] получается из [U(p) 4 ] вычеркиванием первого столбца и первой строки. Лемма 9 Ортогональное преобразование двумерого пространства с определителем равным единице является вращением. Из установленных лемм вытекает Теорема 2 Линейное преобразование U(p):Im(Q) →Im(Q) является вращением пространства Im(Q) вокруг вектора Im(p). Если |p| = 1,то угол ϕ вращения определяется равенством ϕ = 2 ∙ arccos(Re(p)). Матрица движения 4 × 4 определяющее вращение пространства вокруг единичного вектора v = (α,β,γ) на угол ϕ имеет вид: [Rot(n,ϕ)] L = 1 −α 2 cos ϕ +α 2 (1 −cos ϕ)αβ +γ sinϕ (1 −cos ϕ)αγ −β sinϕ 0 (1 −cos ϕ)αβ +γ sinϕ 1 −β 2 cos ϕ +β 2 (1 −cos ϕ)βγ −αsinϕ 0 (1 −cos ϕ)αγ +β sinϕ (1 −cos ϕ)βγ −αsinϕ 1 −γ 2 cos ϕ +γ 2 0 0 0 0 1 Это матрица cоответствует матрице [U(p) 3 ] заданной кватернионом единичной длины: [p] = [cos(ϕ/2),sin(ϕ/2)v] 1.9 Полезные функции использующие кватернионы 1.9.1 Вращение переводящее направление вектора v 1 в направление вектора v 2 Кватернион q реализующий такое вращение определяется так.Пусть [q] = ((v 1 ,v 2 ),v 1 ×v 2 ) Положим [Q] = (|q|,0,0,0),тогда [Rot(v1,v2)] = [q +Q] В этой формуле отсутствуют тригонометрические функции.При вычислении матрицы [U(q)] следует использовать тождество U(q) = 1 |q| 2 (q L ◦ q R ). Тогда нет необходимости нормировать векторыv 1 ,v 2 ! 6 1.9.2 Вычисление кватерниона соответствующего матрице вращения Матрица вращения [U(q) 3 ] соответствующяя кватерниону [q] = (w,x,y,z) c точностью до множителя 1/(w 2 +x 2 +y 2 +z 2 ) имеет вид: [U(q) 3 ] = x 2 +w 2 −z 2 −y 2 2xy +2wz 2xz −2 wy 2xy −2wz y 2 −z 2 +w 2 −x 2 2y z +2wx 2xz +2wy 2y z −2 wx z 2 −y 2 −x 2 +w 2 Выразим координаты кватерниона через элементы матрицы m= [U(q) 3 ], m[i,j],i = 1,2,3;j = 1,2,3. Пусть a = (m[1,1] +m[3,3])/2, b = (m[3,1] −m[1,3])/4, c = (m[1,2] −m[2,1])/4, d = (m[2,3] −m[3,2])/4. Тогда получаем систему уравнений: w 2 −y 2 = a wy = b wz = c wx = d Cчитая w > 0 положительным получаем: w = a 2 + a 2 4 +b 2 Затем находим x,y,z. 1.9.3"Прямая",соединяющая вращения Для того,чтобы построить все промежуточные вращения между U(p 1 ) и U(p 2 ) соединим кватернионы p 1 ,p 2 отрезком p(t) = p 1 ∙ (1 −t) +p 2 ∙ t,t ∈ [0,1]. Тогда вращение U(p(t)) при изменении параметра t от нуля до единицы непрерывно превращается из вращения U(p 1 ) во вращение U(p 2 ).Полезно предварительно кватернион p 2 умножить на −1,если Re(p 1 ),Re(p 2 ) имеют разные знаки.Таким образом мы избегаем краха,при p 1 = −p 2 .Если p 1 = −p 2 , то вращение U(p 1 ) совпадает с вращением U(p 2 ) совпадают,а при t=1/2 кватернион p(t) обращается в нулевой кватернион. 1.9.4 Простейшее оснащение кривой репером Рассмотрим гладкуюкривуюв R 3 , γ:[a,b] →R 3 . Предположим требуется с каждой точкой γ(t) = (x(t),y(t),z(t)) кривой γ связать некоторую локальную декартову систему координат,координатный репер которой R(t) =< o(t),e 1 (t),e 2 (t),e 3 (t) > обладает свойством: o(t) = γ(t),e 3 (t) = γ (t)/|γ (t)|. Для этого достаточно в качестве векторов e 1 (t),e 2 (t),e 3 (t) взять строки матрицы [U(q(t))],соответствующей кватерниону [q(t)] = (z (t),−y (t),x (t),0). 7 1.9.5 Поверхность с границей,составленной из четырех кривых Рассмотрим в пространстве четыре кривые bottom:[0,1] →R 3 ,up:[0,1] →R 3 , right:[0,1] →R 3 ,left:[0,1] →R 3 , образующие"четырехугольник" bottom(1) ∼ right(0),right(1) ∼ up(1),up(0) ∼ left(1),left(0) ∼ bottom(0), где знак ∼означает совпадение или"близость"соответствующих точек.Поверхность Ψ:[0,1] ×[0,1] →R 3 у которой Ψ(0,v) = left(v),Ψ(1,v) = right(v), Ψ(u,0) ∼ bottom(u),Ψ(u,1) ∼ up(u) может быть построена следующим образом. 8
1/--страниц