transform_util.cc revision 2a99a7e74a7f215066514fe81d2bfa6639d9eddd 
1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "ui/gfx/transform_util.h"
6
7#include <cmath>
8
9#include "ui/gfx/point.h"
10
11namespace gfx {
12
13namespace {
14
15double Length3(double v[3]) {
16  return std::sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
17}
18
19void Scale3(double v[3], double scale) {
20  for (int i = 0; i < 3; ++i)
21    v[i] *= scale;
22}
23
24template <int n>
25double Dot(const double* a, const double* b) {
26  double toReturn = 0;
27  for (int i = 0; i < n; ++i)
28    toReturn += a[i] * b[i];
29  return toReturn;
30}
31
32template <int n>
33void Combine(double* out,
34             const double* a,
35             const double* b,
36             double scale_a,
37             double scale_b) {
38  for (int i = 0; i < n; ++i)
39    out[i] = a[i] * scale_a + b[i] * scale_b;
40}
41
42void Cross3(double out[3], double a[3], double b[3]) {
43  double x = a[1] * b[2] - a[2] * b[1];
44  double y = a[2] * b[0] - a[0] * b[2];
45  double z = a[0] * b[1] - a[1] * b[0];
46  out[0] = x;
47  out[1] = y;
48  out[2] = z;
49}
50
51// Taken from http://www.w3.org/TR/css3-transforms/.
52bool Slerp(double out[4],
53           const double q1[4],
54           const double q2[4],
55           double progress) {
56  double product = Dot<4>(q1, q2);
57
58  // Clamp product to -1.0 <= product <= 1.0.
59  product = std::min(std::max(product, -1.0), 1.0);
60
61  const double epsilon = 1e-5;
62  if (std::abs(product - 1.0) < epsilon) {
63    for (int i = 0; i < 4; ++i)
64      out[i] = q1[i];
65    return true;
66  }
67
68  if (std::abs(product) < epsilon) {
69    // Rotation by 180 degrees. We'll fail. It's ambiguous how to interpolate.
70    return false;
71  }
72
73  double denom = std::sqrt(1 - product * product);
74  double theta = std::acos(product);
75  double w = std::sin(progress * theta) * (1 / denom);
76
77  double scale1 = std::cos(progress * theta) - product * w;
78  double scale2 = w;
79  Combine<4>(out, q1, q2, scale1, scale2);
80
81  return true;
82}
83
84// Returns false if the matrix cannot be normalized.
85bool Normalize(SkMatrix44& m) {
86  if (m.getDouble(3, 3) == 0.0)
87    // Cannot normalize.
88    return false;
89
90  double scale = 1.0 / m.getDouble(3, 3);
91  for (int i = 0; i < 4; i++)
92    for (int j = 0; j < 4; j++)
93      m.setDouble(i, j, m.getDouble(i, j) * scale);
94
95  return true;
96}
97
98}  // namespace
99
100Transform GetScaleTransform(const Point& anchor, float scale) {
101  Transform transform;
102  transform.Translate(anchor.x() * (1 - scale),
103                      anchor.y() * (1 - scale));
104  transform.Scale(scale, scale);
105  return transform;
106}
107
108DecomposedTransform::DecomposedTransform() {
109  translate[0] = translate[1] = translate[2] = 0.0;
110  scale[0] = scale[1] = scale[2] = 1.0;
111  skew[0] = skew[1] = skew[2] = 0.0;
112  perspective[0] = perspective[1] = perspective[2] = 0.0;
113  quaternion[0] = quaternion[1] = quaternion[2] = 0.0;
114  perspective[3] = quaternion[3] = 1.0;
115}
116
117bool BlendDecomposedTransforms(DecomposedTransform* out,
118                               const DecomposedTransform& to,
119                               const DecomposedTransform& from,
120                               double progress) {
121  double scalea = progress;
122  double scaleb = 1.0 - progress;
123  Combine<3>(out->translate, to.translate, from.translate, scalea, scaleb);
124  Combine<3>(out->scale, to.scale, from.scale, scalea, scaleb);
125  Combine<3>(out->skew, to.skew, from.skew, scalea, scaleb);
126  Combine<4>(
127      out->perspective, to.perspective, from.perspective, scalea, scaleb);
128  return Slerp(out->quaternion, from.quaternion, to.quaternion, progress);
129}
130
131// Taken from http://www.w3.org/TR/css3-transforms/.
132bool DecomposeTransform(DecomposedTransform* decomp,
133                        const Transform& transform) {
134  if (!decomp)
135    return false;
136
137  // We'll operate on a copy of the matrix.
138  SkMatrix44 matrix = transform.matrix();
139
140  // If we cannot normalize the matrix, then bail early as we cannot decompose.
141  if (!Normalize(matrix))
142    return false;
143
144  SkMatrix44 perspectiveMatrix = matrix;
145
146  for (int i = 0; i < 3; ++i)
147    perspectiveMatrix.setDouble(3, i, 0.0);
148
149  perspectiveMatrix.setDouble(3, 3, 1.0);
150
151  // If the perspective matrix is not invertible, we are also unable to
152  // decompose, so we'll bail early. Constant taken from SkMatrix44::invert.
153  if (std::abs(perspectiveMatrix.determinant()) < 1e-8)
154    return false;
155
156  if (matrix.getDouble(3, 0) != 0.0 ||
157      matrix.getDouble(3, 1) != 0.0 ||
158      matrix.getDouble(3, 2) != 0.0) {
159    // rhs is the right hand side of the equation.
160    SkMScalar rhs[4] = {
161      matrix.get(3, 0),
162      matrix.get(3, 1),
163      matrix.get(3, 2),
164      matrix.get(3, 3)
165    };
166
167    // Solve the equation by inverting perspectiveMatrix and multiplying
168    // rhs by the inverse.
169    SkMatrix44 inversePerspectiveMatrix(SkMatrix44::kUninitialized_Constructor);
170    if (!perspectiveMatrix.invert(&inversePerspectiveMatrix))
171      return false;
172
173    SkMatrix44 transposedInversePerspectiveMatrix =
174        inversePerspectiveMatrix;
175
176    transposedInversePerspectiveMatrix.transpose();
177    transposedInversePerspectiveMatrix.mapMScalars(rhs);
178
179    for (int i = 0; i < 4; ++i)
180      decomp->perspective[i] = rhs[i];
181
182  } else {
183    // No perspective.
184    for (int i = 0; i < 3; ++i)
185      decomp->perspective[i] = 0.0;
186    decomp->perspective[3] = 1.0;
187  }
188
189  for (int i = 0; i < 3; i++)
190    decomp->translate[i] = matrix.getDouble(i, 3);
191
192  double row[3][3];
193  for (int i = 0; i < 3; i++)
194    for (int j = 0; j < 3; ++j)
195      row[i][j] = matrix.getDouble(j, i);
196
197  // Compute X scale factor and normalize first row.
198  decomp->scale[0] = Length3(row[0]);
199  if (decomp->scale[0] != 0.0)
200    Scale3(row[0], 1.0 / decomp->scale[0]);
201
202  // Compute XY shear factor and make 2nd row orthogonal to 1st.
203  decomp->skew[0] = Dot<3>(row[0], row[1]);
204  Combine<3>(row[1], row[1], row[0], 1.0, -decomp->skew[0]);
205
206  // Now, compute Y scale and normalize 2nd row.
207  decomp->scale[1] = Length3(row[1]);
208  if (decomp->scale[1] != 0.0)
209    Scale3(row[1], 1.0 / decomp->scale[1]);
210
211  decomp->skew[0] /= decomp->scale[1];
212
213  // Compute XZ and YZ shears, orthogonalize 3rd row
214  decomp->skew[1] = Dot<3>(row[0], row[2]);
215  Combine<3>(row[2], row[2], row[0], 1.0, -decomp->skew[1]);
216  decomp->skew[2] = Dot<3>(row[1], row[2]);
217  Combine<3>(row[2], row[2], row[1], 1.0, -decomp->skew[2]);
218
219  // Next, get Z scale and normalize 3rd row.
220  decomp->scale[2] = Length3(row[2]);
221  if (decomp->scale[2] != 0.0)
222    Scale3(row[2], 1.0 / decomp->scale[2]);
223
224  decomp->skew[1] /= decomp->scale[2];
225  decomp->skew[2] /= decomp->scale[2];
226
227  // At this point, the matrix (in rows) is orthonormal.
228  // Check for a coordinate system flip.  If the determinant
229  // is -1, then negate the matrix and the scaling factors.
230  double pdum3[3];
231  Cross3(pdum3, row[1], row[2]);
232  if (Dot<3>(row[0], pdum3) < 0) {
233    for (int i = 0; i < 3; i++) {
234      decomp->scale[i] *= -1.0;
235      for (int j = 0; j < 3; ++j)
236        row[i][j] *= -1.0;
237    }
238  }
239
240  decomp->quaternion[0] =
241      0.5 * std::sqrt(std::max(1.0 + row[0][0] - row[1][1] - row[2][2], 0.0));
242  decomp->quaternion[1] =
243      0.5 * std::sqrt(std::max(1.0 - row[0][0] + row[1][1] - row[2][2], 0.0));
244  decomp->quaternion[2] =
245      0.5 * std::sqrt(std::max(1.0 - row[0][0] - row[1][1] + row[2][2], 0.0));
246  decomp->quaternion[3] =
247      0.5 * std::sqrt(std::max(1.0 + row[0][0] + row[1][1] + row[2][2], 0.0));
248
249  if (row[2][1] > row[1][2])
250      decomp->quaternion[0] = -decomp->quaternion[0];
251  if (row[0][2] > row[2][0])
252      decomp->quaternion[1] = -decomp->quaternion[1];
253  if (row[1][0] > row[0][1])
254      decomp->quaternion[2] = -decomp->quaternion[2];
255
256  return true;
257}
258
259// Taken from http://www.w3.org/TR/css3-transforms/.
260Transform ComposeTransform(const DecomposedTransform& decomp) {
261  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
262  for (int i = 0; i < 4; i++)
263    matrix.setDouble(3, i, decomp.perspective[i]);
264
265  matrix.preTranslate(SkDoubleToMScalar(decomp.translate[0]),
266                      SkDoubleToMScalar(decomp.translate[1]),
267                      SkDoubleToMScalar(decomp.translate[2]));
268
269  double x = decomp.quaternion[0];
270  double y = decomp.quaternion[1];
271  double z = decomp.quaternion[2];
272  double w = decomp.quaternion[3];
273
274  SkMatrix44 rotation_matrix(SkMatrix44::kUninitialized_Constructor);
275  rotation_matrix.set3x3(1.0 - 2.0 * (y * y + z * z),
276                         2.0 * (x * y + z * w),
277                         2.0 * (x * z - y * w),
278                         2.0 * (x * y - z * w),
279                         1.0 - 2.0 * (x * x + z * z),
280                         2.0 * (y * z + x * w),
281                         2.0 * (x * z + y * w),
282                         2.0 * (y * z - x * w),
283                         1.0 - 2.0 * (x * x + y * y));
284
285  matrix.preConcat(rotation_matrix);
286
287  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
288  if (decomp.skew[2]) {
289    temp.setDouble(1, 2, decomp.skew[2]);
290    matrix.preConcat(temp);
291  }
292
293  if (decomp.skew[1]) {
294    temp.setDouble(1, 2, 0);
295    temp.setDouble(0, 2, decomp.skew[1]);
296    matrix.preConcat(temp);
297  }
298
299  if (decomp.skew[0]) {
300    temp.setDouble(0, 2, 0);
301    temp.setDouble(0, 1, decomp.skew[0]);
302    matrix.preConcat(temp);
303  }
304
305  matrix.preScale(SkDoubleToMScalar(decomp.scale[0]),
306                  SkDoubleToMScalar(decomp.scale[1]),
307                  SkDoubleToMScalar(decomp.scale[2]));
308
309  Transform to_return;
310  to_return.matrix() = matrix;
311  return to_return;
312}
313
314}  // namespace ui
315