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
  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
  16 namespace gfx {
  17
  18 namespace {
  19
  20 SkMScalar 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
  27 void Scale3(SkMScalar v[3], SkMScalar scale) {
  28   for (int i = 0; i < 3; ++i)
  29     v[i] *= scale;
  30 }
  31
  32 template <int n>
  33 SkMScalar 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
  40 template <int n>
  41 void 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
  50 void 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
  59 SkMScalar Round(SkMScalar n) {
  60   return SkDoubleToMScalar(std::floor(SkMScalarToDouble(n) + 0.5));
  61 }
  62
  63 // Taken from http://www.w3.org/TR/css3-transforms/.
  64 bool 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.
 105 bool 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
 118 SkMatrix44 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
 126 SkMatrix44 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
 135 SkMatrix44 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
 142 SkMatrix44 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
 163 SkMatrix44 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
 183 SkMatrix44 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
 206 SkMatrix44 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
 214 SkMatrix44 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
 221 Transform 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
 239 bool 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
 256 bool 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
 277 Transform 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
 285 DecomposedTransform::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
 294 bool 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/.
 309 bool 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/.
 436 Transform 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
 446 bool 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
 475 std::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