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 323