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 <cmath>
   8
   9 #include "ui/gfx/point.h"
  10
  11 namespace gfx {
  12
  13 namespace {
  14
  15 double Length3(double v[3]) {
  16   return std::sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
  17 }
  18
  19 void Scale3(double v[3], double scale) {
  20   for (int i = 0; i < 3; ++i)
  21     v[i] *= scale;
  22 }
  23
  24 template <int n>
  25 double Dot(const double* a, const double* b) {
  26   double toReturn = 0;
  27   for (int i = 0; i < n; ++i)
  28     toReturn += a[i] * b[i];
  29   return toReturn;
  30 }
  31
  32 template <int n>
  33 void Combine(double* out,
  34              const double* a,
  35              const double* b,
  36              double scale_a,
  37              double scale_b) {
  38   for (int i = 0; i < n; ++i)
  39     out[i] = a[i] * scale_a + b[i] * scale_b;
  40 }
  41
  42 void Cross3(double out[3], double a[3], double b[3]) {
  43   double x = a[1] * b[2] - a[2] * b[1];
  44   double y = a[2] * b[0] - a[0] * b[2];
  45   double z = a[0] * b[1] - a[1] * b[0];
  46   out[0] = x;
  47   out[1] = y;
  48   out[2] = z;
  49 }
  50
  51 // Taken from http://www.w3.org/TR/css3-transforms/.
  52 bool Slerp(double out[4],
  53            const double q1[4],
  54            const double q2[4],
  55            double progress) {
  56   double product = Dot<4>(q1, q2);
  57
  58   // Clamp product to -1.0 <= product <= 1.0.
  59   product = std::min(std::max(product, -1.0), 1.0);
  60
  61   // Interpolate angles along the shortest path. For example, to interpolate
  62   // between a 175 degree angle and a 185 degree angle, interpolate along the
  63   // 10 degree path from 175 to 185, rather than along the 350 degree path in
  64   // the opposite direction. This matches WebKit's implementation but not
  65   // the current W3C spec. Fixing the spec to match this approach is discussed
  66   // at:
  67   // http://lists.w3.org/Archives/Public/www-style/2013May/0131.html
  68   double scale1 = 1.0;
  69   if (product < 0) {
  70     product = -product;
  71     scale1 = -1.0;
  72   }
  73
  74   const double epsilon = 1e-5;
  75   if (std::abs(product - 1.0) < epsilon) {
  76     for (int i = 0; i < 4; ++i)
  77       out[i] = q1[i];
  78     return true;
  79   }
  80
  81   double denom = std::sqrt(1 - product * product);
  82   double theta = std::acos(product);
  83   double w = std::sin(progress * theta) * (1 / denom);
  84
  85   scale1 *= std::cos(progress * theta) - product * w;
  86   double scale2 = w;
  87   Combine<4>(out, q1, q2, scale1, scale2);
  88
  89   return true;
  90 }
  91
  92 // Returns false if the matrix cannot be normalized.
  93 bool Normalize(SkMatrix44& m) {
  94   if (m.getDouble(3, 3) == 0.0)
  95     // Cannot normalize.
  96     return false;
  97
  98   double scale = 1.0 / m.getDouble(3, 3);
  99   for (int i = 0; i < 4; i++)
 100     for (int j = 0; j < 4; j++)
 101       m.setDouble(i, j, m.getDouble(i, j) * scale);
 102
 103   return true;
 104 }
 105
 106 }  // namespace
 107
 108 Transform GetScaleTransform(const Point& anchor, float scale) {
 109   Transform transform;
 110   transform.Translate(anchor.x() * (1 - scale),
 111                       anchor.y() * (1 - scale));
 112   transform.Scale(scale, scale);
 113   return transform;
 114 }
 115
 116 DecomposedTransform::DecomposedTransform() {
 117   translate[0] = translate[1] = translate[2] = 0.0;
 118   scale[0] = scale[1] = scale[2] = 1.0;
 119   skew[0] = skew[1] = skew[2] = 0.0;
 120   perspective[0] = perspective[1] = perspective[2] = 0.0;
 121   quaternion[0] = quaternion[1] = quaternion[2] = 0.0;
 122   perspective[3] = quaternion[3] = 1.0;
 123 }
 124
 125 bool BlendDecomposedTransforms(DecomposedTransform* out,
 126                                const DecomposedTransform& to,
 127                                const DecomposedTransform& from,
 128                                double progress) {
 129   double scalea = progress;
 130   double scaleb = 1.0 - progress;
 131   Combine<3>(out->translate, to.translate, from.translate, scalea, scaleb);
 132   Combine<3>(out->scale, to.scale, from.scale, scalea, scaleb);
 133   Combine<3>(out->skew, to.skew, from.skew, scalea, scaleb);
 134   Combine<4>(
 135       out->perspective, to.perspective, from.perspective, scalea, scaleb);
 136   return Slerp(out->quaternion, from.quaternion, to.quaternion, progress);
 137 }
 138
 139 // Taken from http://www.w3.org/TR/css3-transforms/.
 140 bool DecomposeTransform(DecomposedTransform* decomp,
 141                         const Transform& transform) {
 142   if (!decomp)
 143     return false;
 144
 145   // We'll operate on a copy of the matrix.
 146   SkMatrix44 matrix = transform.matrix();
 147
 148   // If we cannot normalize the matrix, then bail early as we cannot decompose.
 149   if (!Normalize(matrix))
 150     return false;
 151
 152   SkMatrix44 perspectiveMatrix = matrix;
 153
 154   for (int i = 0; i < 3; ++i)
 155     perspectiveMatrix.setDouble(3, i, 0.0);
 156
 157   perspectiveMatrix.setDouble(3, 3, 1.0);
 158
 159   // If the perspective matrix is not invertible, we are also unable to
 160   // decompose, so we'll bail early. Constant taken from SkMatrix44::invert.
 161   if (std::abs(perspectiveMatrix.determinant()) < 1e-8)
 162     return false;
 163
 164   if (matrix.getDouble(3, 0) != 0.0 ||
 165       matrix.getDouble(3, 1) != 0.0 ||
 166       matrix.getDouble(3, 2) != 0.0) {
 167     // rhs is the right hand side of the equation.
 168     SkMScalar rhs[4] = {
 169       matrix.get(3, 0),
 170       matrix.get(3, 1),
 171       matrix.get(3, 2),
 172       matrix.get(3, 3)
 173     };
 174
 175     // Solve the equation by inverting perspectiveMatrix and multiplying
 176     // rhs by the inverse.
 177     SkMatrix44 inversePerspectiveMatrix(SkMatrix44::kUninitialized_Constructor);
 178     if (!perspectiveMatrix.invert(&inversePerspectiveMatrix))
 179       return false;
 180
 181     SkMatrix44 transposedInversePerspectiveMatrix =
 182         inversePerspectiveMatrix;
 183
 184     transposedInversePerspectiveMatrix.transpose();
 185     transposedInversePerspectiveMatrix.mapMScalars(rhs);
 186
 187     for (int i = 0; i < 4; ++i)
 188       decomp->perspective[i] = rhs[i];
 189
 190   } else {
 191     // No perspective.
 192     for (int i = 0; i < 3; ++i)
 193       decomp->perspective[i] = 0.0;
 194     decomp->perspective[3] = 1.0;
 195   }
 196
 197   for (int i = 0; i < 3; i++)
 198     decomp->translate[i] = matrix.getDouble(i, 3);
 199
 200   double row[3][3];
 201   for (int i = 0; i < 3; i++)
 202     for (int j = 0; j < 3; ++j)
 203       row[i][j] = matrix.getDouble(j, i);
 204
 205   // Compute X scale factor and normalize first row.
 206   decomp->scale[0] = Length3(row[0]);
 207   if (decomp->scale[0] != 0.0)
 208     Scale3(row[0], 1.0 / decomp->scale[0]);
 209
 210   // Compute XY shear factor and make 2nd row orthogonal to 1st.
 211   decomp->skew[0] = Dot<3>(row[0], row[1]);
 212   Combine<3>(row[1], row[1], row[0], 1.0, -decomp->skew[0]);
 213
 214   // Now, compute Y scale and normalize 2nd row.
 215   decomp->scale[1] = Length3(row[1]);
 216   if (decomp->scale[1] != 0.0)
 217     Scale3(row[1], 1.0 / decomp->scale[1]);
 218
 219   decomp->skew[0] /= decomp->scale[1];
 220
 221   // Compute XZ and YZ shears, orthogonalize 3rd row
 222   decomp->skew[1] = Dot<3>(row[0], row[2]);
 223   Combine<3>(row[2], row[2], row[0], 1.0, -decomp->skew[1]);
 224   decomp->skew[2] = Dot<3>(row[1], row[2]);
 225   Combine<3>(row[2], row[2], row[1], 1.0, -decomp->skew[2]);
 226
 227   // Next, get Z scale and normalize 3rd row.
 228   decomp->scale[2] = Length3(row[2]);
 229   if (decomp->scale[2] != 0.0)
 230     Scale3(row[2], 1.0 / decomp->scale[2]);
 231
 232   decomp->skew[1] /= decomp->scale[2];
 233   decomp->skew[2] /= decomp->scale[2];
 234
 235   // At this point, the matrix (in rows) is orthonormal.
 236   // Check for a coordinate system flip.  If the determinant
 237   // is -1, then negate the matrix and the scaling factors.
 238   double pdum3[3];
 239   Cross3(pdum3, row[1], row[2]);
 240   if (Dot<3>(row[0], pdum3) < 0) {
 241     for (int i = 0; i < 3; i++) {
 242       decomp->scale[i] *= -1.0;
 243       for (int j = 0; j < 3; ++j)
 244         row[i][j] *= -1.0;
 245     }
 246   }
 247
 248   decomp->quaternion[0] =
 249       0.5 * std::sqrt(std::max(1.0 + row[0][0] - row[1][1] - row[2][2], 0.0));
 250   decomp->quaternion[1] =
 251       0.5 * std::sqrt(std::max(1.0 - row[0][0] + row[1][1] - row[2][2], 0.0));
 252   decomp->quaternion[2] =
 253       0.5 * std::sqrt(std::max(1.0 - row[0][0] - row[1][1] + row[2][2], 0.0));
 254   decomp->quaternion[3] =
 255       0.5 * std::sqrt(std::max(1.0 + row[0][0] + row[1][1] + row[2][2], 0.0));
 256
 257   if (row[2][1] > row[1][2])
 258       decomp->quaternion[0] = -decomp->quaternion[0];
 259   if (row[0][2] > row[2][0])
 260       decomp->quaternion[1] = -decomp->quaternion[1];
 261   if (row[1][0] > row[0][1])
 262       decomp->quaternion[2] = -decomp->quaternion[2];
 263
 264   return true;
 265 }
 266
 267 // Taken from http://www.w3.org/TR/css3-transforms/.
 268 Transform ComposeTransform(const DecomposedTransform& decomp) {
 269   SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
 270   for (int i = 0; i < 4; i++)
 271     matrix.setDouble(3, i, decomp.perspective[i]);
 272
 273   matrix.preTranslate(SkDoubleToMScalar(decomp.translate[0]),
 274                       SkDoubleToMScalar(decomp.translate[1]),
 275                       SkDoubleToMScalar(decomp.translate[2]));
 276
 277   double x = decomp.quaternion[0];
 278   double y = decomp.quaternion[1];
 279   double z = decomp.quaternion[2];
 280   double w = decomp.quaternion[3];
 281
 282   SkMatrix44 rotation_matrix(SkMatrix44::kUninitialized_Constructor);
 283   rotation_matrix.set3x3(1.0 - 2.0 * (y * y + z * z),
 284                          2.0 * (x * y + z * w),
 285                          2.0 * (x * z - y * w),
 286                          2.0 * (x * y - z * w),
 287                          1.0 - 2.0 * (x * x + z * z),
 288                          2.0 * (y * z + x * w),
 289                          2.0 * (x * z + y * w),
 290                          2.0 * (y * z - x * w),
 291                          1.0 - 2.0 * (x * x + y * y));
 292
 293   matrix.preConcat(rotation_matrix);
 294
 295   SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
 296   if (decomp.skew[2]) {
 297     temp.setDouble(1, 2, decomp.skew[2]);
 298     matrix.preConcat(temp);
 299   }
 300
 301   if (decomp.skew[1]) {
 302     temp.setDouble(1, 2, 0);
 303     temp.setDouble(0, 2, decomp.skew[1]);
 304     matrix.preConcat(temp);
 305   }
 306
 307   if (decomp.skew[0]) {
 308     temp.setDouble(0, 2, 0);
 309     temp.setDouble(0, 1, decomp.skew[0]);
 310     matrix.preConcat(temp);
 311   }
 312
 313   matrix.preScale(SkDoubleToMScalar(decomp.scale[0]),
 314                   SkDoubleToMScalar(decomp.scale[1]),
 315                   SkDoubleToMScalar(decomp.scale[2]));
 316
 317   Transform to_return;
 318   to_return.matrix() = matrix;
 319   return to_return;
 320 }
 321
 322 }  // namespace ui