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 <algorithm>
8#include <cmath>
9
10#include "base/logging.h"
11#include "base/strings/stringprintf.h"
12#include "ui/gfx/point.h"
13#include "ui/gfx/point3_f.h"
14#include "ui/gfx/rect.h"
15
16namespace gfx {
17
18namespace {
19
20SkMScalar Length3(SkMScalar v[3]) {
21  double vd[3] = {SkMScalarToDouble(v[0]), SkMScalarToDouble(v[1]),
22                  SkMScalarToDouble(v[2])};
23  return SkDoubleToMScalar(
24      std::sqrt(vd[0] * vd[0] + vd[1] * vd[1] + vd[2] * vd[2]));
25}
26
27void Scale3(SkMScalar v[3], SkMScalar scale) {
28  for (int i = 0; i < 3; ++i)
29    v[i] *= scale;
30}
31
32template <int n>
33SkMScalar Dot(const SkMScalar* a, const SkMScalar* b) {
34  double total = 0.0;
35  for (int i = 0; i < n; ++i)
36    total += a[i] * b[i];
37  return SkDoubleToMScalar(total);
38}
39
40template <int n>
41void Combine(SkMScalar* out,
42             const SkMScalar* a,
43             const SkMScalar* b,
44             double scale_a,
45             double scale_b) {
46  for (int i = 0; i < n; ++i)
47    out[i] = SkDoubleToMScalar(a[i] * scale_a + b[i] * scale_b);
48}
49
50void Cross3(SkMScalar out[3], SkMScalar a[3], SkMScalar b[3]) {
51  SkMScalar x = a[1] * b[2] - a[2] * b[1];
52  SkMScalar y = a[2] * b[0] - a[0] * b[2];
53  SkMScalar z = a[0] * b[1] - a[1] * b[0];
54  out[0] = x;
55  out[1] = y;
56  out[2] = z;
57}
58
59SkMScalar Round(SkMScalar n) {
60  return SkDoubleToMScalar(std::floor(SkMScalarToDouble(n) + 0.5));
61}
62
63// Taken from http://www.w3.org/TR/css3-transforms/.
64bool Slerp(SkMScalar out[4],
65           const SkMScalar q1[4],
66           const SkMScalar q2[4],
67           double progress) {
68  double product = Dot<4>(q1, q2);
69
70  // Clamp product to -1.0 <= product <= 1.0.
71  product = std::min(std::max(product, -1.0), 1.0);
72
73  // Interpolate angles along the shortest path. For example, to interpolate
74  // between a 175 degree angle and a 185 degree angle, interpolate along the
75  // 10 degree path from 175 to 185, rather than along the 350 degree path in
76  // the opposite direction. This matches WebKit's implementation but not
77  // the current W3C spec. Fixing the spec to match this approach is discussed
78  // at:
79  // http://lists.w3.org/Archives/Public/www-style/2013May/0131.html
80  double scale1 = 1.0;
81  if (product < 0) {
82    product = -product;
83    scale1 = -1.0;
84  }
85
86  const double epsilon = 1e-5;
87  if (std::abs(product - 1.0) < epsilon) {
88    for (int i = 0; i < 4; ++i)
89      out[i] = q1[i];
90    return true;
91  }
92
93  double denom = std::sqrt(1.0 - product * product);
94  double theta = std::acos(product);
95  double w = std::sin(progress * theta) * (1.0 / denom);
96
97  scale1 *= std::cos(progress * theta) - product * w;
98  double scale2 = w;
99  Combine<4>(out, q1, q2, scale1, scale2);
100
101  return true;
102}
103
104// Returns false if the matrix cannot be normalized.
105bool Normalize(SkMatrix44& m) {
106  if (m.get(3, 3) == 0.0)
107    // Cannot normalize.
108    return false;
109
110  SkMScalar scale = 1.0 / m.get(3, 3);
111  for (int i = 0; i < 4; i++)
112    for (int j = 0; j < 4; j++)
113      m.set(i, j, m.get(i, j) * scale);
114
115  return true;
116}
117
118SkMatrix44 BuildPerspectiveMatrix(const DecomposedTransform& decomp) {
119  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
120
121  for (int i = 0; i < 4; i++)
122    matrix.setDouble(3, i, decomp.perspective[i]);
123  return matrix;
124}
125
126SkMatrix44 BuildTranslationMatrix(const DecomposedTransform& decomp) {
127  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
128  // Implicitly calls matrix.setIdentity()
129  matrix.setTranslate(SkDoubleToMScalar(decomp.translate[0]),
130                      SkDoubleToMScalar(decomp.translate[1]),
131                      SkDoubleToMScalar(decomp.translate[2]));
132  return matrix;
133}
134
135SkMatrix44 BuildSnappedTranslationMatrix(DecomposedTransform decomp) {
136  decomp.translate[0] = Round(decomp.translate[0]);
137  decomp.translate[1] = Round(decomp.translate[1]);
138  decomp.translate[2] = Round(decomp.translate[2]);
139  return BuildTranslationMatrix(decomp);
140}
141
142SkMatrix44 BuildRotationMatrix(const DecomposedTransform& decomp) {
143  double x = decomp.quaternion[0];
144  double y = decomp.quaternion[1];
145  double z = decomp.quaternion[2];
146  double w = decomp.quaternion[3];
147
148  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
149
150  // Implicitly calls matrix.setIdentity()
151  matrix.set3x3(1.0 - 2.0 * (y * y + z * z),
152                2.0 * (x * y + z * w),
153                2.0 * (x * z - y * w),
154                2.0 * (x * y - z * w),
155                1.0 - 2.0 * (x * x + z * z),
156                2.0 * (y * z + x * w),
157                2.0 * (x * z + y * w),
158                2.0 * (y * z - x * w),
159                1.0 - 2.0 * (x * x + y * y));
160  return matrix;
161}
162
163SkMatrix44 BuildSnappedRotationMatrix(const DecomposedTransform& decomp) {
164  // Create snapped rotation.
165  SkMatrix44 rotation_matrix = BuildRotationMatrix(decomp);
166  for (int i = 0; i < 3; ++i) {
167    for (int j = 0; j < 3; ++j) {
168      SkMScalar value = rotation_matrix.get(i, j);
169      // Snap values to -1, 0 or 1.
170      if (value < -0.5f) {
171        value = -1.0f;
172      } else if (value > 0.5f) {
173        value = 1.0f;
174      } else {
175        value = 0.0f;
176      }
177      rotation_matrix.set(i, j, value);
178    }
179  }
180  return rotation_matrix;
181}
182
183SkMatrix44 BuildSkewMatrix(const DecomposedTransform& decomp) {
184  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
185
186  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
187  if (decomp.skew[2]) {
188    temp.setDouble(1, 2, decomp.skew[2]);
189    matrix.preConcat(temp);
190  }
191
192  if (decomp.skew[1]) {
193    temp.setDouble(1, 2, 0);
194    temp.setDouble(0, 2, decomp.skew[1]);
195    matrix.preConcat(temp);
196  }
197
198  if (decomp.skew[0]) {
199    temp.setDouble(0, 2, 0);
200    temp.setDouble(0, 1, decomp.skew[0]);
201    matrix.preConcat(temp);
202  }
203  return matrix;
204}
205
206SkMatrix44 BuildScaleMatrix(const DecomposedTransform& decomp) {
207  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
208  matrix.setScale(SkDoubleToMScalar(decomp.scale[0]),
209                  SkDoubleToMScalar(decomp.scale[1]),
210                  SkDoubleToMScalar(decomp.scale[2]));
211  return matrix;
212}
213
214SkMatrix44 BuildSnappedScaleMatrix(DecomposedTransform decomp) {
215  decomp.scale[0] = Round(decomp.scale[0]);
216  decomp.scale[1] = Round(decomp.scale[1]);
217  decomp.scale[2] = Round(decomp.scale[2]);
218  return BuildScaleMatrix(decomp);
219}
220
221Transform ComposeTransform(const SkMatrix44& perspective,
222                           const SkMatrix44& translation,
223                           const SkMatrix44& rotation,
224                           const SkMatrix44& skew,
225                           const SkMatrix44& scale) {
226  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
227
228  matrix.preConcat(perspective);
229  matrix.preConcat(translation);
230  matrix.preConcat(rotation);
231  matrix.preConcat(skew);
232  matrix.preConcat(scale);
233
234  Transform to_return;
235  to_return.matrix() = matrix;
236  return to_return;
237}
238
239bool CheckViewportPointMapsWithinOnePixel(const Point& point,
240                                          const Transform& transform) {
241  Point3F point_original(point);
242  Point3F point_transformed(point);
243
244  // Can't use TransformRect here since it would give us the axis-aligned
245  // bounding rect of the 4 points in the initial rectable which is not what we
246  // want.
247  transform.TransformPoint(&point_transformed);
248
249  if ((point_transformed - point_original).Length() > 1.f) {
250    // The changed distance should not be more than 1 pixel.
251    return false;
252  }
253  return true;
254}
255
256bool CheckTransformsMapsIntViewportWithinOnePixel(const Rect& viewport,
257                                                  const Transform& original,
258                                                  const Transform& snapped) {
259
260  Transform original_inv(Transform::kSkipInitialization);
261  bool invertible = true;
262  invertible &= original.GetInverse(&original_inv);
263  DCHECK(invertible) << "Non-invertible transform, cannot snap.";
264
265  Transform combined = snapped * original_inv;
266
267  return CheckViewportPointMapsWithinOnePixel(viewport.origin(), combined) &&
268         CheckViewportPointMapsWithinOnePixel(viewport.top_right(), combined) &&
269         CheckViewportPointMapsWithinOnePixel(viewport.bottom_left(),
270                                              combined) &&
271         CheckViewportPointMapsWithinOnePixel(viewport.bottom_right(),
272                                              combined);
273}
274
275}  // namespace
276
277Transform GetScaleTransform(const Point& anchor, float scale) {
278  Transform transform;
279  transform.Translate(anchor.x() * (1 - scale),
280                      anchor.y() * (1 - scale));
281  transform.Scale(scale, scale);
282  return transform;
283}
284
285DecomposedTransform::DecomposedTransform() {
286  translate[0] = translate[1] = translate[2] = 0.0;
287  scale[0] = scale[1] = scale[2] = 1.0;
288  skew[0] = skew[1] = skew[2] = 0.0;
289  perspective[0] = perspective[1] = perspective[2] = 0.0;
290  quaternion[0] = quaternion[1] = quaternion[2] = 0.0;
291  perspective[3] = quaternion[3] = 1.0;
292}
293
294bool BlendDecomposedTransforms(DecomposedTransform* out,
295                               const DecomposedTransform& to,
296                               const DecomposedTransform& from,
297                               double progress) {
298  double scalea = progress;
299  double scaleb = 1.0 - progress;
300  Combine<3>(out->translate, to.translate, from.translate, scalea, scaleb);
301  Combine<3>(out->scale, to.scale, from.scale, scalea, scaleb);
302  Combine<3>(out->skew, to.skew, from.skew, scalea, scaleb);
303  Combine<4>(
304      out->perspective, to.perspective, from.perspective, scalea, scaleb);
305  return Slerp(out->quaternion, from.quaternion, to.quaternion, progress);
306}
307
308// Taken from http://www.w3.org/TR/css3-transforms/.
309bool DecomposeTransform(DecomposedTransform* decomp,
310                        const Transform& transform) {
311  if (!decomp)
312    return false;
313
314  // We'll operate on a copy of the matrix.
315  SkMatrix44 matrix = transform.matrix();
316
317  // If we cannot normalize the matrix, then bail early as we cannot decompose.
318  if (!Normalize(matrix))
319    return false;
320
321  SkMatrix44 perspectiveMatrix = matrix;
322
323  for (int i = 0; i < 3; ++i)
324    perspectiveMatrix.set(3, i, 0.0);
325
326  perspectiveMatrix.set(3, 3, 1.0);
327
328  // If the perspective matrix is not invertible, we are also unable to
329  // decompose, so we'll bail early. Constant taken from SkMatrix44::invert.
330  if (std::abs(perspectiveMatrix.determinant()) < 1e-8)
331    return false;
332
333  if (matrix.get(3, 0) != 0.0 || matrix.get(3, 1) != 0.0 ||
334      matrix.get(3, 2) != 0.0) {
335    // rhs is the right hand side of the equation.
336    SkMScalar rhs[4] = {
337      matrix.get(3, 0),
338      matrix.get(3, 1),
339      matrix.get(3, 2),
340      matrix.get(3, 3)
341    };
342
343    // Solve the equation by inverting perspectiveMatrix and multiplying
344    // rhs by the inverse.
345    SkMatrix44 inversePerspectiveMatrix(SkMatrix44::kUninitialized_Constructor);
346    if (!perspectiveMatrix.invert(&inversePerspectiveMatrix))
347      return false;
348
349    SkMatrix44 transposedInversePerspectiveMatrix =
350        inversePerspectiveMatrix;
351
352    transposedInversePerspectiveMatrix.transpose();
353    transposedInversePerspectiveMatrix.mapMScalars(rhs);
354
355    for (int i = 0; i < 4; ++i)
356      decomp->perspective[i] = rhs[i];
357
358  } else {
359    // No perspective.
360    for (int i = 0; i < 3; ++i)
361      decomp->perspective[i] = 0.0;
362    decomp->perspective[3] = 1.0;
363  }
364
365  for (int i = 0; i < 3; i++)
366    decomp->translate[i] = matrix.get(i, 3);
367
368  SkMScalar row[3][3];
369  for (int i = 0; i < 3; i++)
370    for (int j = 0; j < 3; ++j)
371      row[i][j] = matrix.get(j, i);
372
373  // Compute X scale factor and normalize first row.
374  decomp->scale[0] = Length3(row[0]);
375  if (decomp->scale[0] != 0.0)
376    Scale3(row[0], 1.0 / decomp->scale[0]);
377
378  // Compute XY shear factor and make 2nd row orthogonal to 1st.
379  decomp->skew[0] = Dot<3>(row[0], row[1]);
380  Combine<3>(row[1], row[1], row[0], 1.0, -decomp->skew[0]);
381
382  // Now, compute Y scale and normalize 2nd row.
383  decomp->scale[1] = Length3(row[1]);
384  if (decomp->scale[1] != 0.0)
385    Scale3(row[1], 1.0 / decomp->scale[1]);
386
387  decomp->skew[0] /= decomp->scale[1];
388
389  // Compute XZ and YZ shears, orthogonalize 3rd row
390  decomp->skew[1] = Dot<3>(row[0], row[2]);
391  Combine<3>(row[2], row[2], row[0], 1.0, -decomp->skew[1]);
392  decomp->skew[2] = Dot<3>(row[1], row[2]);
393  Combine<3>(row[2], row[2], row[1], 1.0, -decomp->skew[2]);
394
395  // Next, get Z scale and normalize 3rd row.
396  decomp->scale[2] = Length3(row[2]);
397  if (decomp->scale[2] != 0.0)
398    Scale3(row[2], 1.0 / decomp->scale[2]);
399
400  decomp->skew[1] /= decomp->scale[2];
401  decomp->skew[2] /= decomp->scale[2];
402
403  // At this point, the matrix (in rows) is orthonormal.
404  // Check for a coordinate system flip.  If the determinant
405  // is -1, then negate the matrix and the scaling factors.
406  SkMScalar pdum3[3];
407  Cross3(pdum3, row[1], row[2]);
408  if (Dot<3>(row[0], pdum3) < 0) {
409    for (int i = 0; i < 3; i++) {
410      decomp->scale[i] *= -1.0;
411      for (int j = 0; j < 3; ++j)
412        row[i][j] *= -1.0;
413    }
414  }
415
416  decomp->quaternion[0] =
417      0.5 * std::sqrt(std::max(1.0 + row[0][0] - row[1][1] - row[2][2], 0.0));
418  decomp->quaternion[1] =
419      0.5 * std::sqrt(std::max(1.0 - row[0][0] + row[1][1] - row[2][2], 0.0));
420  decomp->quaternion[2] =
421      0.5 * std::sqrt(std::max(1.0 - row[0][0] - row[1][1] + row[2][2], 0.0));
422  decomp->quaternion[3] =
423      0.5 * std::sqrt(std::max(1.0 + row[0][0] + row[1][1] + row[2][2], 0.0));
424
425  if (row[2][1] > row[1][2])
426      decomp->quaternion[0] = -decomp->quaternion[0];
427  if (row[0][2] > row[2][0])
428      decomp->quaternion[1] = -decomp->quaternion[1];
429  if (row[1][0] > row[0][1])
430      decomp->quaternion[2] = -decomp->quaternion[2];
431
432  return true;
433}
434
435// Taken from http://www.w3.org/TR/css3-transforms/.
436Transform ComposeTransform(const DecomposedTransform& decomp) {
437  SkMatrix44 perspective = BuildPerspectiveMatrix(decomp);
438  SkMatrix44 translation = BuildTranslationMatrix(decomp);
439  SkMatrix44 rotation = BuildRotationMatrix(decomp);
440  SkMatrix44 skew = BuildSkewMatrix(decomp);
441  SkMatrix44 scale = BuildScaleMatrix(decomp);
442
443  return ComposeTransform(perspective, translation, rotation, skew, scale);
444}
445
446bool SnapTransform(Transform* out,
447                   const Transform& transform,
448                   const Rect& viewport) {
449  DecomposedTransform decomp;
450  DecomposeTransform(&decomp, transform);
451
452  SkMatrix44 rotation_matrix = BuildSnappedRotationMatrix(decomp);
453  SkMatrix44 translation = BuildSnappedTranslationMatrix(decomp);
454  SkMatrix44 scale = BuildSnappedScaleMatrix(decomp);
455
456  // Rebuild matrices for other unchanged components.
457  SkMatrix44 perspective = BuildPerspectiveMatrix(decomp);
458
459  // Completely ignore the skew.
460  SkMatrix44 skew(SkMatrix44::kIdentity_Constructor);
461
462  // Get full tranform
463  Transform snapped =
464      ComposeTransform(perspective, translation, rotation_matrix, skew, scale);
465
466  // Verify that viewport is not moved unnaturally.
467  bool snappable =
468    CheckTransformsMapsIntViewportWithinOnePixel(viewport, transform, snapped);
469  if (snappable) {
470    *out = snapped;
471  }
472  return snappable;
473}
474
475std::string DecomposedTransform::ToString() const {
476  return base::StringPrintf(
477      "translate: %+0.4f %+0.4f %+0.4f\n"
478      "scale: %+0.4f %+0.4f %+0.4f\n"
479      "skew: %+0.4f %+0.4f %+0.4f\n"
480      "perspective: %+0.4f %+0.4f %+0.4f %+0.4f\n"
481      "quaternion: %+0.4f %+0.4f %+0.4f %+0.4f\n",
482      translate[0],
483      translate[1],
484      translate[2],
485      scale[0],
486      scale[1],
487      scale[2],
488      skew[0],
489      skew[1],
490      skew[2],
491      perspective[0],
492      perspective[1],
493      perspective[2],
494      perspective[3],
495      quaternion[0],
496      quaternion[1],
497      quaternion[2],
498      quaternion[3]);
499}
500
501}  // namespace ui
502