ui/gfx/transform_util.cc

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