1 // quaternion.cpp (Quaternion implementation)
2 //
3 // The WorldForge Project
4 // Copyright (C) 2002 The WorldForge Project
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 2 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 //
20 // For information about WorldForge and its authors, please contact
21 // the Worldforge Web Site at http://www.worldforge.org.
22 //
23
24 // Author: Ron Steinke
25
26 // Some code here was taken from the quaternion implementation is
27 // eris. Some of the other algorithms are based on information
28 // found here <http://www.cs.ualberta.ca/~andreas/math/matrfaq_latest.html>
29 // and here <http://www.cs.berkeley.edu/~laura/cs184/quat/quaternion.html>.
30
31 #ifdef HAVE_CONFIG_H
32 #include "config.h"
33 #endif
34
35 #include "quaternion.h"
36 #include "error.h"
37 #include "rotmatrix.h"
38
39 #include <cmath>
40
41 #include <cassert>
42
43 namespace WFMath {
44
Quaternion(CoordType w_in,CoordType x_in,CoordType y_in,CoordType z_in)45 Quaternion::Quaternion (CoordType w_in,
46 CoordType x_in,
47 CoordType y_in,
48 CoordType z_in)
49 : m_w(0), m_vec(), m_valid(true), m_age(1)
50 {
51 CoordType norm = std::sqrt(w_in*w_in + x_in*x_in + y_in*y_in + z_in*z_in);
52
53 m_w = w_in / norm;
54 m_vec[0] = x_in / norm;
55 m_vec[1] = y_in / norm;
56 m_vec[2] = z_in / norm;
57 m_vec.setValid();
58 }
59
60 // The equality functions regard q and -q as equal, since they
61 // correspond to the same rotation matrix. We consider the form
62 // of the quaternion with w > 0 canonical.
63
isEqualTo(const Quaternion & q,float epsilon) const64 bool Quaternion::isEqualTo(const Quaternion &q, float epsilon) const
65 {
66 // Since the sum of squares is 1, the magnitude of the largest
67 // element must be between 1 and 0.5, so we don't need to scale epsilon.
68
69 assert(epsilon > 0);
70
71 if(std::fabs(m_w - q.m_w) <= epsilon) {
72 int i;
73 for(i = 0; i < 3; ++i)
74 if(std::fabs(m_vec[i] - q.m_vec[i]) > epsilon)
75 break; // try again with swapped signs
76 if(i == 3) // got through the loop
77 return true;
78 }
79
80 // This makes q == -q true
81 if(std::fabs(m_w + q.m_w) <= epsilon) {
82 for(int i = 0; i < 3; ++i)
83 if(std::fabs(m_vec[i] + q.m_vec[i]) > epsilon)
84 return false;
85 return true;
86 }
87
88 return false;
89 }
90
91 // order of multiplication vs sense of rotation
92 //
93 // v.rotate(q1).rotate(q2) is the same as v.rotate(q1 * q2),
94 // the same as with matrices
95
operator *=(const Quaternion & rhs)96 Quaternion& Quaternion::operator*= (const Quaternion& rhs)
97 {
98 m_valid = m_valid && rhs.m_valid;
99 m_age = m_age + rhs.m_age;
100 checkNormalization();
101
102 CoordType old_w = m_w;
103 m_w = m_w * rhs.m_w - Dot(m_vec, rhs.m_vec);
104 m_vec = old_w * rhs.m_vec + rhs.m_w * m_vec - Cross(m_vec, rhs.m_vec);
105
106 return *this;
107 }
108
operator /=(const Quaternion & rhs)109 Quaternion& Quaternion::operator/= (const Quaternion& rhs)
110 {
111 m_valid = m_valid && rhs.m_valid;
112 m_age = m_age + rhs.m_age;
113 checkNormalization();
114
115 CoordType old_w = m_w;
116 m_w = m_w * rhs.m_w + Dot(m_vec, rhs.m_vec);
117 m_vec = rhs.m_w * m_vec - old_w * rhs.m_vec + Cross(m_vec, rhs.m_vec);
118
119 return *this;
120 }
121
fromRotMatrix(const RotMatrix<3> & m)122 bool Quaternion::fromRotMatrix(const RotMatrix<3>& m)
123 {
124 RotMatrix<3> m_tmp;
125 bool not_flip = !m.parity();
126
127 m_valid = m.isValid();
128 m_vec.setValid(m.isValid());
129
130 if(!not_flip)
131 m_tmp = Prod(m, RotMatrix<3>().mirrorX());
132
133 const RotMatrix<3> &m_ref = not_flip ? m : m_tmp;
134
135 CoordType s;
136 const int nxt[3] = {1, 2, 0};
137 CoordType tr = m_ref.trace();
138
139 // check the diagonal
140 if (tr > 0.0) {
141 s = std::sqrt(tr + 1.0f);
142 m_w = (s / 2.0f);
143 s = (0.5f / s);
144
145 m_vec[0] = -(m_ref.elem(2, 1) - m_ref.elem(1, 2)) * s;
146 m_vec[1] = -(m_ref.elem(0, 2) - m_ref.elem(2, 0)) * s;
147 m_vec[2] = -(m_ref.elem(1, 0) - m_ref.elem(0, 1)) * s;
148 } else {
149 // diagonal is negative
150 int i = 0;
151
152 if (m_ref.elem(1, 1) > m_ref.elem(0, 0)) i = 1;
153 if (m_ref.elem(2, 2) > m_ref.elem(i, i)) i = 2;
154
155 int j = nxt[i], k = nxt[j];
156
157 s = std::sqrt (1.0f + m_ref.elem(i, i) - m_ref.elem(j, j) - m_ref.elem(k, k));
158 m_vec[i] = -(s * 0.5f);
159
160 assert("sqrt() returns positive" && s > 0.0);
161 s = (0.5f / s);
162
163 m_w = (m_ref.elem(k, j) - m_ref.elem(j, k)) * s;
164 m_vec[j] = -(m_ref.elem(i, j) + m_ref.elem(j, i)) * s;
165 m_vec[k] = -(m_ref.elem(i, k) + m_ref.elem(k, i)) * s;
166 }
167
168 m_age = m.age();
169
170 return not_flip;
171 }
172
inverse() const173 Quaternion Quaternion::inverse() const
174 {
175 Quaternion q(m_valid);
176 q.m_w = m_w;
177 q.m_vec = -m_vec;
178 q.m_age = m_age; // no multiplication was done, so roundoff error does not increase
179 return q;
180 }
181
rotate(const RotMatrix<3> & m)182 Quaternion& Quaternion::rotate(const RotMatrix<3>& m)
183 {
184 // FIXME find a more efficient way to do this
185 Quaternion tmp;
186 tmp.fromRotMatrix(m);
187 *this *= tmp;
188 return *this;
189 }
190
rotation(int axis,CoordType angle)191 Quaternion& Quaternion::rotation(int axis, CoordType angle)
192 {
193 if (axis < 0 || axis > 2) {
194 m_valid = false;
195 return *this;
196 }
197
198 CoordType half_angle = angle / 2;
199
200 m_w = std::cos(half_angle);
201 for(int i = 0; i < 3; ++i)
202 // Note sin() only called once
203 m_vec[i] = (i == axis) ? std::sin(half_angle) : 0;
204 m_vec.setValid();
205
206 m_valid = true;
207 m_age = 1;
208
209 return *this;
210 }
211
rotation(const Vector<3> & axis,CoordType angle)212 Quaternion& Quaternion::rotation(const Vector<3>& axis, CoordType angle)
213 {
214 CoordType axis_mag = axis.mag();
215 CoordType half_angle = angle / 2;
216
217 if (axis_mag < numeric_constants<CoordType>::epsilon()) {
218 m_valid = false;
219 return *this;
220 }
221
222 m_w = std::cos(half_angle);
223 m_vec = axis * (std::sin(half_angle) / axis_mag);
224
225 m_valid = axis.isValid();
226 m_age = 1;
227
228 return *this;
229 }
230
rotation(const Vector<3> & axis)231 Quaternion& Quaternion::rotation(const Vector<3>& axis)
232 {
233 CoordType axis_mag = axis.mag();
234 CoordType half_angle = axis_mag / 2;
235
236 if (axis_mag < numeric_constants<CoordType>::epsilon()) {
237 m_valid = false;
238 return *this;
239 }
240
241 m_w = std::cos(half_angle);
242 m_vec = axis * (std::sin(half_angle) / axis_mag);
243
244 m_valid = axis.isValid();
245 m_age = 1;
246
247 return *this;
248 }
249
rotation(const Vector<3> & from,const Vector<3> & to)250 Quaternion& Quaternion::rotation(const Vector<3>& from, const Vector<3>& to)
251 {
252 CoordType mag_prod = std::sqrt(from.sqrMag() * to.sqrMag());
253 CoordType ctheta_plus_1 = Dot(from, to) / mag_prod + 1;
254
255 if (mag_prod < numeric_constants<CoordType>::epsilon()) {
256 m_valid = false;
257 return *this;
258 }
259
260 // antiparallel vectors
261 if(ctheta_plus_1 < numeric_constants<CoordType>::epsilon()) // same check as used in the RotMatrix function
262 throw ColinearVectors<3>(from, to);
263
264 // cosine of half the angle
265 m_w = std::sqrt(ctheta_plus_1 / 2.f);
266
267 // vector in direction of axis, magnitude of cross product is proportional to
268 // the sin of the angle, divide to make the magnitude the sin of half the angle,
269 // sin(x) = 2sin(x/2)cos(x/2), so sin(x/2) = sin(x)/(2cos(x/2))
270 m_vec = Cross(from, to) / (2 * mag_prod * m_w);
271
272 m_valid = from.isValid() && to.isValid();
273 m_age = 1;
274
275 return *this;
276 }
277
normalize()278 void Quaternion::normalize()
279 {
280 // Assume that we're not too far off, and compute the norm
281 // only to linear order in the difference from 1.
282 // If q.sqrMag() = 1 + x, q.mag() = 1 + x/2 = (q.SqrMag() + 1)/2
283 // to linear order.
284 CoordType norm = (m_w * m_w + m_vec.sqrMag() + 1)/2;
285 m_w /= norm;
286 m_vec /= norm;
287 m_age = 1;
288 }
289
290 }
291