Home | History | Annotate | Download | only in gfx 
      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
    502