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// MSVC++ requires this to be set before any other includes to get M_PI.
6#define _USE_MATH_DEFINES
7
8#include "ui/gfx/transform.h"
9
10#include <cmath>
11
12#include "base/logging.h"
13#include "base/strings/stringprintf.h"
14#include "ui/gfx/box_f.h"
15#include "ui/gfx/point.h"
16#include "ui/gfx/point3_f.h"
17#include "ui/gfx/rect.h"
18#include "ui/gfx/safe_integer_conversions.h"
19#include "ui/gfx/skia_util.h"
20#include "ui/gfx/transform_util.h"
21#include "ui/gfx/vector3d_f.h"
22
23namespace gfx {
24
25namespace {
26
27// Taken from SkMatrix44.
28const SkMScalar kEpsilon = 1e-8f;
29
30SkMScalar TanDegrees(double degrees) {
31  double radians = degrees * M_PI / 180;
32  return SkDoubleToMScalar(std::tan(radians));
33}
34
35inline bool ApproximatelyZero(SkMScalar x, SkMScalar tolerance) {
36  return std::abs(x) <= tolerance;
37}
38
39inline bool ApproximatelyOne(SkMScalar x, SkMScalar tolerance) {
40  return std::abs(x - SkDoubleToMScalar(1.0)) <= tolerance;
41}
42
43}  // namespace
44
45Transform::Transform(SkMScalar col1row1,
46                     SkMScalar col2row1,
47                     SkMScalar col3row1,
48                     SkMScalar col4row1,
49                     SkMScalar col1row2,
50                     SkMScalar col2row2,
51                     SkMScalar col3row2,
52                     SkMScalar col4row2,
53                     SkMScalar col1row3,
54                     SkMScalar col2row3,
55                     SkMScalar col3row3,
56                     SkMScalar col4row3,
57                     SkMScalar col1row4,
58                     SkMScalar col2row4,
59                     SkMScalar col3row4,
60                     SkMScalar col4row4)
61    : matrix_(SkMatrix44::kUninitialized_Constructor) {
62  matrix_.set(0, 0, col1row1);
63  matrix_.set(1, 0, col1row2);
64  matrix_.set(2, 0, col1row3);
65  matrix_.set(3, 0, col1row4);
66
67  matrix_.set(0, 1, col2row1);
68  matrix_.set(1, 1, col2row2);
69  matrix_.set(2, 1, col2row3);
70  matrix_.set(3, 1, col2row4);
71
72  matrix_.set(0, 2, col3row1);
73  matrix_.set(1, 2, col3row2);
74  matrix_.set(2, 2, col3row3);
75  matrix_.set(3, 2, col3row4);
76
77  matrix_.set(0, 3, col4row1);
78  matrix_.set(1, 3, col4row2);
79  matrix_.set(2, 3, col4row3);
80  matrix_.set(3, 3, col4row4);
81}
82
83Transform::Transform(SkMScalar col1row1,
84                     SkMScalar col2row1,
85                     SkMScalar col1row2,
86                     SkMScalar col2row2,
87                     SkMScalar x_translation,
88                     SkMScalar y_translation)
89    : matrix_(SkMatrix44::kIdentity_Constructor) {
90  matrix_.set(0, 0, col1row1);
91  matrix_.set(1, 0, col1row2);
92  matrix_.set(0, 1, col2row1);
93  matrix_.set(1, 1, col2row2);
94  matrix_.set(0, 3, x_translation);
95  matrix_.set(1, 3, y_translation);
96}
97
98void Transform::RotateAboutXAxis(double degrees) {
99  double radians = degrees * M_PI / 180;
100  SkMScalar cosTheta = SkDoubleToMScalar(std::cos(radians));
101  SkMScalar sinTheta = SkDoubleToMScalar(std::sin(radians));
102  if (matrix_.isIdentity()) {
103      matrix_.set3x3(1, 0, 0,
104                     0, cosTheta, sinTheta,
105                     0, -sinTheta, cosTheta);
106  } else {
107    SkMatrix44 rot(SkMatrix44::kUninitialized_Constructor);
108    rot.set3x3(1, 0, 0,
109               0, cosTheta, sinTheta,
110               0, -sinTheta, cosTheta);
111    matrix_.preConcat(rot);
112  }
113}
114
115void Transform::RotateAboutYAxis(double degrees) {
116  double radians = degrees * M_PI / 180;
117  SkMScalar cosTheta = SkDoubleToMScalar(std::cos(radians));
118  SkMScalar sinTheta = SkDoubleToMScalar(std::sin(radians));
119  if (matrix_.isIdentity()) {
120      // Note carefully the placement of the -sinTheta for rotation about
121      // y-axis is different than rotation about x-axis or z-axis.
122      matrix_.set3x3(cosTheta, 0, -sinTheta,
123                     0, 1, 0,
124                     sinTheta, 0, cosTheta);
125  } else {
126    SkMatrix44 rot(SkMatrix44::kUninitialized_Constructor);
127    rot.set3x3(cosTheta, 0, -sinTheta,
128               0, 1, 0,
129               sinTheta, 0, cosTheta);
130    matrix_.preConcat(rot);
131  }
132}
133
134void Transform::RotateAboutZAxis(double degrees) {
135  double radians = degrees * M_PI / 180;
136  SkMScalar cosTheta = SkDoubleToMScalar(std::cos(radians));
137  SkMScalar sinTheta = SkDoubleToMScalar(std::sin(radians));
138  if (matrix_.isIdentity()) {
139      matrix_.set3x3(cosTheta, sinTheta, 0,
140                     -sinTheta, cosTheta, 0,
141                     0, 0, 1);
142  } else {
143    SkMatrix44 rot(SkMatrix44::kUninitialized_Constructor);
144    rot.set3x3(cosTheta, sinTheta, 0,
145               -sinTheta, cosTheta, 0,
146               0, 0, 1);
147    matrix_.preConcat(rot);
148  }
149}
150
151void Transform::RotateAbout(const Vector3dF& axis, double degrees) {
152  if (matrix_.isIdentity()) {
153    matrix_.setRotateDegreesAbout(SkFloatToMScalar(axis.x()),
154                                  SkFloatToMScalar(axis.y()),
155                                  SkFloatToMScalar(axis.z()),
156                                  degrees);
157  } else {
158    SkMatrix44 rot(SkMatrix44::kUninitialized_Constructor);
159    rot.setRotateDegreesAbout(SkFloatToMScalar(axis.x()),
160                              SkFloatToMScalar(axis.y()),
161                              SkFloatToMScalar(axis.z()),
162                              degrees);
163    matrix_.preConcat(rot);
164  }
165}
166
167void Transform::Scale(SkMScalar x, SkMScalar y) { matrix_.preScale(x, y, 1); }
168
169void Transform::Scale3d(SkMScalar x, SkMScalar y, SkMScalar z) {
170  matrix_.preScale(x, y, z);
171}
172
173void Transform::Translate(SkMScalar x, SkMScalar y) {
174  matrix_.preTranslate(x, y, 0);
175}
176
177void Transform::Translate3d(SkMScalar x, SkMScalar y, SkMScalar z) {
178  matrix_.preTranslate(x, y, z);
179}
180
181void Transform::SkewX(double angle_x) {
182  if (matrix_.isIdentity())
183    matrix_.set(0, 1, TanDegrees(angle_x));
184  else {
185    SkMatrix44 skew(SkMatrix44::kIdentity_Constructor);
186    skew.set(0, 1, TanDegrees(angle_x));
187    matrix_.preConcat(skew);
188  }
189}
190
191void Transform::SkewY(double angle_y) {
192  if (matrix_.isIdentity())
193    matrix_.set(1, 0, TanDegrees(angle_y));
194  else {
195    SkMatrix44 skew(SkMatrix44::kIdentity_Constructor);
196    skew.set(1, 0, TanDegrees(angle_y));
197    matrix_.preConcat(skew);
198  }
199}
200
201void Transform::ApplyPerspectiveDepth(SkMScalar depth) {
202  if (depth == 0)
203    return;
204  if (matrix_.isIdentity())
205    matrix_.set(3, 2, -1.0 / depth);
206  else {
207    SkMatrix44 m(SkMatrix44::kIdentity_Constructor);
208    m.set(3, 2, -1.0 / depth);
209    matrix_.preConcat(m);
210  }
211}
212
213void Transform::PreconcatTransform(const Transform& transform) {
214  matrix_.preConcat(transform.matrix_);
215}
216
217void Transform::ConcatTransform(const Transform& transform) {
218  matrix_.postConcat(transform.matrix_);
219}
220
221bool Transform::IsApproximatelyIdentityOrTranslation(
222    SkMScalar tolerance) const {
223  DCHECK_GE(tolerance, 0);
224  return
225      ApproximatelyOne(matrix_.get(0, 0), tolerance) &&
226      ApproximatelyZero(matrix_.get(1, 0), tolerance) &&
227      ApproximatelyZero(matrix_.get(2, 0), tolerance) &&
228      matrix_.get(3, 0) == 0 &&
229      ApproximatelyZero(matrix_.get(0, 1), tolerance) &&
230      ApproximatelyOne(matrix_.get(1, 1), tolerance) &&
231      ApproximatelyZero(matrix_.get(2, 1), tolerance) &&
232      matrix_.get(3, 1) == 0 &&
233      ApproximatelyZero(matrix_.get(0, 2), tolerance) &&
234      ApproximatelyZero(matrix_.get(1, 2), tolerance) &&
235      ApproximatelyOne(matrix_.get(2, 2), tolerance) &&
236      matrix_.get(3, 2) == 0 &&
237      matrix_.get(3, 3) == 1;
238}
239
240bool Transform::IsIdentityOrIntegerTranslation() const {
241  if (!IsIdentityOrTranslation())
242    return false;
243
244  bool no_fractional_translation =
245      static_cast<int>(matrix_.get(0, 3)) == matrix_.get(0, 3) &&
246      static_cast<int>(matrix_.get(1, 3)) == matrix_.get(1, 3) &&
247      static_cast<int>(matrix_.get(2, 3)) == matrix_.get(2, 3);
248
249  return no_fractional_translation;
250}
251
252bool Transform::IsBackFaceVisible() const {
253  // Compute whether a layer with a forward-facing normal of (0, 0, 1, 0)
254  // would have its back face visible after applying the transform.
255  if (matrix_.isIdentity())
256    return false;
257
258  // This is done by transforming the normal and seeing if the resulting z
259  // value is positive or negative. However, note that transforming a normal
260  // actually requires using the inverse-transpose of the original transform.
261  //
262  // We can avoid inverting and transposing the matrix since we know we want
263  // to transform only the specific normal vector (0, 0, 1, 0). In this case,
264  // we only need the 3rd row, 3rd column of the inverse-transpose. We can
265  // calculate only the 3rd row 3rd column element of the inverse, skipping
266  // everything else.
267  //
268  // For more information, refer to:
269  //   http://en.wikipedia.org/wiki/Invertible_matrix#Analytic_solution
270  //
271
272  double determinant = matrix_.determinant();
273
274  // If matrix was not invertible, then just assume back face is not visible.
275  if (std::abs(determinant) <= kEpsilon)
276    return false;
277
278  // Compute the cofactor of the 3rd row, 3rd column.
279  double cofactor_part_1 =
280      matrix_.get(0, 0) * matrix_.get(1, 1) * matrix_.get(3, 3);
281
282  double cofactor_part_2 =
283      matrix_.get(0, 1) * matrix_.get(1, 3) * matrix_.get(3, 0);
284
285  double cofactor_part_3 =
286      matrix_.get(0, 3) * matrix_.get(1, 0) * matrix_.get(3, 1);
287
288  double cofactor_part_4 =
289      matrix_.get(0, 0) * matrix_.get(1, 3) * matrix_.get(3, 1);
290
291  double cofactor_part_5 =
292      matrix_.get(0, 1) * matrix_.get(1, 0) * matrix_.get(3, 3);
293
294  double cofactor_part_6 =
295      matrix_.get(0, 3) * matrix_.get(1, 1) * matrix_.get(3, 0);
296
297  double cofactor33 =
298      cofactor_part_1 +
299      cofactor_part_2 +
300      cofactor_part_3 -
301      cofactor_part_4 -
302      cofactor_part_5 -
303      cofactor_part_6;
304
305  // Technically the transformed z component is cofactor33 / determinant.  But
306  // we can avoid the costly division because we only care about the resulting
307  // +/- sign; we can check this equivalently by multiplication.
308  return cofactor33 * determinant < 0;
309}
310
311bool Transform::GetInverse(Transform* transform) const {
312  if (!matrix_.invert(&transform->matrix_)) {
313    // Initialize the return value to identity if this matrix turned
314    // out to be un-invertible.
315    transform->MakeIdentity();
316    return false;
317  }
318
319  return true;
320}
321
322bool Transform::Preserves2dAxisAlignment() const {
323  // Check whether an axis aligned 2-dimensional rect would remain axis-aligned
324  // after being transformed by this matrix (and implicitly projected by
325  // dropping any non-zero z-values).
326  //
327  // The 4th column can be ignored because translations don't affect axis
328  // alignment. The 3rd column can be ignored because we are assuming 2d
329  // inputs, where z-values will be zero. The 3rd row can also be ignored
330  // because we are assuming 2d outputs, and any resulting z-value is dropped
331  // anyway. For the inner 2x2 portion, the only effects that keep a rect axis
332  // aligned are (1) swapping axes and (2) scaling axes. This can be checked by
333  // verifying only 1 element of every column and row is non-zero.  Degenerate
334  // cases that project the x or y dimension to zero are considered to preserve
335  // axis alignment.
336  //
337  // If the matrix does have perspective component that is affected by x or y
338  // values: The current implementation conservatively assumes that axis
339  // alignment is not preserved.
340
341  bool has_x_or_y_perspective =
342      matrix_.get(3, 0) != 0 || matrix_.get(3, 1) != 0;
343
344  int num_non_zero_in_row_0 = 0;
345  int num_non_zero_in_row_1 = 0;
346  int num_non_zero_in_col_0 = 0;
347  int num_non_zero_in_col_1 = 0;
348
349  if (std::abs(matrix_.get(0, 0)) > kEpsilon) {
350    num_non_zero_in_row_0++;
351    num_non_zero_in_col_0++;
352  }
353
354  if (std::abs(matrix_.get(0, 1)) > kEpsilon) {
355    num_non_zero_in_row_0++;
356    num_non_zero_in_col_1++;
357  }
358
359  if (std::abs(matrix_.get(1, 0)) > kEpsilon) {
360    num_non_zero_in_row_1++;
361    num_non_zero_in_col_0++;
362  }
363
364  if (std::abs(matrix_.get(1, 1)) > kEpsilon) {
365    num_non_zero_in_row_1++;
366    num_non_zero_in_col_1++;
367  }
368
369  return
370      num_non_zero_in_row_0 <= 1 &&
371      num_non_zero_in_row_1 <= 1 &&
372      num_non_zero_in_col_0 <= 1 &&
373      num_non_zero_in_col_1 <= 1 &&
374      !has_x_or_y_perspective;
375}
376
377void Transform::Transpose() {
378  matrix_.transpose();
379}
380
381void Transform::FlattenTo2d() {
382  matrix_.set(2, 0, 0.0);
383  matrix_.set(2, 1, 0.0);
384  matrix_.set(0, 2, 0.0);
385  matrix_.set(1, 2, 0.0);
386  matrix_.set(2, 2, 1.0);
387  matrix_.set(3, 2, 0.0);
388  matrix_.set(2, 3, 0.0);
389}
390
391Vector2dF Transform::To2dTranslation() const {
392  return gfx::Vector2dF(SkMScalarToFloat(matrix_.get(0, 3)),
393                        SkMScalarToFloat(matrix_.get(1, 3)));
394}
395
396void Transform::TransformPoint(Point* point) const {
397  DCHECK(point);
398  TransformPointInternal(matrix_, point);
399}
400
401void Transform::TransformPoint(Point3F* point) const {
402  DCHECK(point);
403  TransformPointInternal(matrix_, point);
404}
405
406bool Transform::TransformPointReverse(Point* point) const {
407  DCHECK(point);
408
409  // TODO(sad): Try to avoid trying to invert the matrix.
410  SkMatrix44 inverse(SkMatrix44::kUninitialized_Constructor);
411  if (!matrix_.invert(&inverse))
412    return false;
413
414  TransformPointInternal(inverse, point);
415  return true;
416}
417
418bool Transform::TransformPointReverse(Point3F* point) const {
419  DCHECK(point);
420
421  // TODO(sad): Try to avoid trying to invert the matrix.
422  SkMatrix44 inverse(SkMatrix44::kUninitialized_Constructor);
423  if (!matrix_.invert(&inverse))
424    return false;
425
426  TransformPointInternal(inverse, point);
427  return true;
428}
429
430void Transform::TransformRect(RectF* rect) const {
431  if (matrix_.isIdentity())
432    return;
433
434  SkRect src = RectFToSkRect(*rect);
435  const SkMatrix& matrix = matrix_;
436  matrix.mapRect(&src);
437  *rect = SkRectToRectF(src);
438}
439
440bool Transform::TransformRectReverse(RectF* rect) const {
441  if (matrix_.isIdentity())
442    return true;
443
444  SkMatrix44 inverse(SkMatrix44::kUninitialized_Constructor);
445  if (!matrix_.invert(&inverse))
446    return false;
447
448  const SkMatrix& matrix = inverse;
449  SkRect src = RectFToSkRect(*rect);
450  matrix.mapRect(&src);
451  *rect = SkRectToRectF(src);
452  return true;
453}
454
455void Transform::TransformBox(BoxF* box) const {
456  BoxF bounds;
457  bool first_point = true;
458  for (int corner = 0; corner < 8; ++corner) {
459    gfx::Point3F point = box->origin();
460    point += gfx::Vector3dF(corner & 1 ? box->width() : 0.f,
461                            corner & 2 ? box->height() : 0.f,
462                            corner & 4 ? box->depth() : 0.f);
463    TransformPoint(&point);
464    if (first_point) {
465      bounds.set_origin(point);
466      first_point = false;
467    } else {
468      bounds.ExpandTo(point);
469    }
470  }
471  *box = bounds;
472}
473
474bool Transform::TransformBoxReverse(BoxF* box) const {
475  gfx::Transform inverse = *this;
476  if (!GetInverse(&inverse))
477    return false;
478  inverse.TransformBox(box);
479  return true;
480}
481
482bool Transform::Blend(const Transform& from, double progress) {
483  DecomposedTransform to_decomp;
484  DecomposedTransform from_decomp;
485  if (!DecomposeTransform(&to_decomp, *this) ||
486      !DecomposeTransform(&from_decomp, from))
487    return false;
488
489  if (!BlendDecomposedTransforms(&to_decomp, to_decomp, from_decomp, progress))
490    return false;
491
492  matrix_ = ComposeTransform(to_decomp).matrix();
493  return true;
494}
495
496void Transform::TransformPointInternal(const SkMatrix44& xform,
497                                       Point3F* point) const {
498  if (xform.isIdentity())
499    return;
500
501  SkMScalar p[4] = {SkFloatToMScalar(point->x()), SkFloatToMScalar(point->y()),
502                    SkFloatToMScalar(point->z()), 1};
503
504  xform.mapMScalars(p);
505
506  if (p[3] != SK_MScalar1 && p[3] != 0.f) {
507    float w_inverse = SK_MScalar1 / p[3];
508    point->SetPoint(p[0] * w_inverse, p[1] * w_inverse, p[2] * w_inverse);
509  } else {
510    point->SetPoint(p[0], p[1], p[2]);
511  }
512}
513
514void Transform::TransformPointInternal(const SkMatrix44& xform,
515                                       Point* point) const {
516  if (xform.isIdentity())
517    return;
518
519  SkMScalar p[4] = {SkFloatToMScalar(point->x()), SkFloatToMScalar(point->y()),
520                    0, 1};
521
522  xform.mapMScalars(p);
523
524  point->SetPoint(ToRoundedInt(p[0]), ToRoundedInt(p[1]));
525}
526
527std::string Transform::ToString() const {
528  return base::StringPrintf(
529      "[ %+0.4f %+0.4f %+0.4f %+0.4f  \n"
530      "  %+0.4f %+0.4f %+0.4f %+0.4f  \n"
531      "  %+0.4f %+0.4f %+0.4f %+0.4f  \n"
532      "  %+0.4f %+0.4f %+0.4f %+0.4f ]\n",
533      matrix_.get(0, 0),
534      matrix_.get(0, 1),
535      matrix_.get(0, 2),
536      matrix_.get(0, 3),
537      matrix_.get(1, 0),
538      matrix_.get(1, 1),
539      matrix_.get(1, 2),
540      matrix_.get(1, 3),
541      matrix_.get(2, 0),
542      matrix_.get(2, 1),
543      matrix_.get(2, 2),
544      matrix_.get(2, 3),
545      matrix_.get(3, 0),
546      matrix_.get(3, 1),
547      matrix_.get(3, 2),
548      matrix_.get(3, 3));
549}
550
551}  // namespace gfx
552