third_party/web-animations-js/sources/src/matrix-decomposition.js

   1 // Copyright 2014 Google Inc. All rights reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 //   You may obtain a copy of the License at
   6 //
   7 // http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 //   See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 (function(scope, testing) {
  16   var decomposeMatrix = (function() {
  17     function determinant(m) {
  18       return m[0][0] * m[1][1] * m[2][2] +
  19              m[1][0] * m[2][1] * m[0][2] +
  20              m[2][0] * m[0][1] * m[1][2] -
  21              m[0][2] * m[1][1] * m[2][0] -
  22              m[1][2] * m[2][1] * m[0][0] -
  23              m[2][2] * m[0][1] * m[1][0];
  24     }
  25
  26     // from Wikipedia:
  27     //
  28     // [A B]^-1 = [A^-1 + A^-1B(D - CA^-1B)^-1CA^-1     -A^-1B(D - CA^-1B)^-1]
  29     // [C D]      [-(D - CA^-1B)^-1CA^-1                (D - CA^-1B)^-1      ]
  30     //
  31     // Therefore
  32     //
  33     // [A [0]]^-1 = [A^-1       [0]]
  34     // [C  1 ]      [ -CA^-1     1 ]
  35     function inverse(m) {
  36       var iDet = 1 / determinant(m);
  37       var a = m[0][0], b = m[0][1], c = m[0][2];
  38       var d = m[1][0], e = m[1][1], f = m[1][2];
  39       var g = m[2][0], h = m[2][1], k = m[2][2];
  40       var Ainv = [
  41         [(e * k - f * h) * iDet, (c * h - b * k) * iDet,
  42          (b * f - c * e) * iDet, 0],
  43         [(f * g - d * k) * iDet, (a * k - c * g) * iDet,
  44          (c * d - a * f) * iDet, 0],
  45         [(d * h - e * g) * iDet, (g * b - a * h) * iDet,
  46          (a * e - b * d) * iDet, 0]
  47       ];
  48       var lastRow = [];
  49       for (var i = 0; i < 3; i++) {
  50         var val = 0;
  51         for (var j = 0; j < 3; j++) {
  52           val += m[3][j] * Ainv[j][i];
  53         }
  54         lastRow.push(val);
  55       }
  56       lastRow.push(1);
  57       Ainv.push(lastRow);
  58       return Ainv;
  59     }
  60
  61     function transposeMatrix4(m) {
  62       return [[m[0][0], m[1][0], m[2][0], m[3][0]],
  63               [m[0][1], m[1][1], m[2][1], m[3][1]],
  64               [m[0][2], m[1][2], m[2][2], m[3][2]],
  65               [m[0][3], m[1][3], m[2][3], m[3][3]]];
  66     }
  67
  68     function multVecMatrix(v, m) {
  69       var result = [];
  70       for (var i = 0; i < 4; i++) {
  71         var val = 0;
  72         for (var j = 0; j < 4; j++) {
  73           val += v[j] * m[j][i];
  74         }
  75         result.push(val);
  76       }
  77       return result;
  78     }
  79
  80     function normalize(v) {
  81       var len = length(v);
  82       return [v[0] / len, v[1] / len, v[2] / len];
  83     }
  84
  85     function length(v) {
  86       return Math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
  87     }
  88
  89     function combine(v1, v2, v1s, v2s) {
  90       return [v1s * v1[0] + v2s * v2[0], v1s * v1[1] + v2s * v2[1],
  91               v1s * v1[2] + v2s * v2[2]];
  92     }
  93
  94     function cross(v1, v2) {
  95       return [v1[1] * v2[2] - v1[2] * v2[1],
  96               v1[2] * v2[0] - v1[0] * v2[2],
  97               v1[0] * v2[1] - v1[1] * v2[0]];
  98     }
  99
 100     // TODO: Implement 2D matrix decomposition.
 101     // http://dev.w3.org/csswg/css-transforms/#decomposing-a-2d-matrix
 102     function decomposeMatrix(matrix) {
 103       var m3d = [
 104         matrix.slice(0, 4),
 105         matrix.slice(4, 8),
 106         matrix.slice(8, 12),
 107         matrix.slice(12, 16)
 108       ];
 109
 110       // skip normalization step as m3d[3][3] should always be 1
 111       if (m3d[3][3] !== 1) {
 112         return null;
 113       }
 114
 115       var perspectiveMatrix = [];
 116       for (var i = 0; i < 4; i++) {
 117         perspectiveMatrix.push(m3d[i].slice());
 118       }
 119
 120       for (var i = 0; i < 3; i++) {
 121         perspectiveMatrix[i][3] = 0;
 122       }
 123
 124       if (determinant(perspectiveMatrix) === 0) {
 125         return false;
 126       }
 127
 128       var rhs = [];
 129
 130       var perspective;
 131       if (m3d[0][3] || m3d[1][3] || m3d[2][3]) {
 132         rhs.push(m3d[0][3]);
 133         rhs.push(m3d[1][3]);
 134         rhs.push(m3d[2][3]);
 135         rhs.push(m3d[3][3]);
 136
 137         var inversePerspectiveMatrix = inverse(perspectiveMatrix);
 138         var transposedInversePerspectiveMatrix =
 139             transposeMatrix4(inversePerspectiveMatrix);
 140         perspective = multVecMatrix(rhs, transposedInversePerspectiveMatrix);
 141       } else {
 142         perspective = [0, 0, 0, 1];
 143       }
 144
 145       var translate = m3d[3].slice(0, 3);
 146
 147       var row = [];
 148       row.push(m3d[0].slice(0, 3));
 149       var scale = [];
 150       scale.push(length(row[0]));
 151       row[0] = normalize(row[0]);
 152
 153       var skew = [];
 154       row.push(m3d[1].slice(0, 3));
 155       skew.push(dot(row[0], row[1]));
 156       row[1] = combine(row[1], row[0], 1.0, -skew[0]);
 157
 158       scale.push(length(row[1]));
 159       row[1] = normalize(row[1]);
 160       skew[0] /= scale[1];
 161
 162       row.push(m3d[2].slice(0, 3));
 163       skew.push(dot(row[0], row[2]));
 164       row[2] = combine(row[2], row[0], 1.0, -skew[1]);
 165       skew.push(dot(row[1], row[2]));
 166       row[2] = combine(row[2], row[1], 1.0, -skew[2]);
 167
 168       scale.push(length(row[2]));
 169       row[2] = normalize(row[2]);
 170       skew[1] /= scale[2];
 171       skew[2] /= scale[2];
 172
 173       var pdum3 = cross(row[1], row[2]);
 174       if (dot(row[0], pdum3) < 0) {
 175         for (var i = 0; i < 3; i++) {
 176           scale[i] *= -1;
 177           row[i][0] *= -1;
 178           row[i][1] *= -1;
 179           row[i][2] *= -1;
 180         }
 181       }
 182
 183       var t = row[0][0] + row[1][1] + row[2][2] + 1;
 184       var s;
 185       var quaternion;
 186
 187       if (t > 1e-4) {
 188         s = 0.5 / Math.sqrt(t);
 189         quaternion = [
 190           (row[2][1] - row[1][2]) * s,
 191           (row[0][2] - row[2][0]) * s,
 192           (row[1][0] - row[0][1]) * s,
 193           0.25 / s
 194         ];
 195       } else if (row[0][0] > row[1][1] && row[0][0] > row[2][2]) {
 196         s = Math.sqrt(1 + row[0][0] - row[1][1] - row[2][2]) * 2.0;
 197         quaternion = [
 198           0.25 * s,
 199           (row[0][1] + row[1][0]) / s,
 200           (row[0][2] + row[2][0]) / s,
 201           (row[2][1] - row[1][2]) / s
 202         ];
 203       } else if (row[1][1] > row[2][2]) {
 204         s = Math.sqrt(1.0 + row[1][1] - row[0][0] - row[2][2]) * 2.0;
 205         quaternion = [
 206           (row[0][1] + row[1][0]) / s,
 207           0.25 * s,
 208           (row[1][2] + row[2][1]) / s,
 209           (row[0][2] - row[2][0]) / s
 210         ];
 211       } else {
 212         s = Math.sqrt(1.0 + row[2][2] - row[0][0] - row[1][1]) * 2.0;
 213         quaternion = [
 214           (row[0][2] + row[2][0]) / s,
 215           (row[1][2] + row[2][1]) / s,
 216           0.25 * s,
 217           (row[1][0] - row[0][1]) / s
 218         ];
 219       }
 220
 221       return [translate, scale, skew, quaternion, perspective];
 222     }
 223     return decomposeMatrix;
 224   })();
 225
 226   function dot(v1, v2) {
 227     var result = 0;
 228     for (var i = 0; i < v1.length; i++) {
 229       result += v1[i] * v2[i];
 230     }
 231     return result;
 232   }
 233
 234   function multiplyMatrices(a, b) {
 235     return [
 236       a[0] * b[0] + a[4] * b[1] + a[8] * b[2] + a[12] * b[3],
 237       a[1] * b[0] + a[5] * b[1] + a[9] * b[2] + a[13] * b[3],
 238       a[2] * b[0] + a[6] * b[1] + a[10] * b[2] + a[14] * b[3],
 239       a[3] * b[0] + a[7] * b[1] + a[11] * b[2] + a[15] * b[3],
 240
 241       a[0] * b[4] + a[4] * b[5] + a[8] * b[6] + a[12] * b[7],
 242       a[1] * b[4] + a[5] * b[5] + a[9] * b[6] + a[13] * b[7],
 243       a[2] * b[4] + a[6] * b[5] + a[10] * b[6] + a[14] * b[7],
 244       a[3] * b[4] + a[7] * b[5] + a[11] * b[6] + a[15] * b[7],
 245
 246       a[0] * b[8] + a[4] * b[9] + a[8] * b[10] + a[12] * b[11],
 247       a[1] * b[8] + a[5] * b[9] + a[9] * b[10] + a[13] * b[11],
 248       a[2] * b[8] + a[6] * b[9] + a[10] * b[10] + a[14] * b[11],
 249       a[3] * b[8] + a[7] * b[9] + a[11] * b[10] + a[15] * b[11],
 250
 251       a[0] * b[12] + a[4] * b[13] + a[8] * b[14] + a[12] * b[15],
 252       a[1] * b[12] + a[5] * b[13] + a[9] * b[14] + a[13] * b[15],
 253       a[2] * b[12] + a[6] * b[13] + a[10] * b[14] + a[14] * b[15],
 254       a[3] * b[12] + a[7] * b[13] + a[11] * b[14] + a[15] * b[15]
 255     ];
 256   }
 257
 258   // TODO: This can probably be made smaller.
 259   function convertItemToMatrix(item) {
 260     switch (item.t) {
 261       // TODO: Handle units other than rads and degs.
 262       case 'rotatex':
 263         var rads = item.d[0].rad || 0;
 264         var degs = item.d[0].deg || 0;
 265         var angle = (degs * Math.PI / 180) + rads;
 266         return [1, 0, 0, 0,
 267                 0, Math.cos(angle), Math.sin(angle), 0,
 268                 0, -Math.sin(angle), Math.cos(angle), 0,
 269                 0, 0, 0, 1];
 270       case 'rotatey':
 271         var rads = item.d[0].rad || 0;
 272         var degs = item.d[0].deg || 0;
 273         var angle = (degs * Math.PI / 180) + rads;
 274         return [Math.cos(angle), 0, -Math.sin(angle), 0,
 275                 0, 1, 0, 0,
 276                 Math.sin(angle), 0, Math.cos(angle), 0,
 277                 0, 0, 0, 1];
 278       case 'rotate':
 279       case 'rotatez':
 280         var rads = item.d[0].rad || 0;
 281         var degs = item.d[0].deg || 0;
 282         var angle = (degs * Math.PI / 180) + rads;
 283         return [Math.cos(angle), Math.sin(angle), 0, 0,
 284                 -Math.sin(angle), Math.cos(angle), 0, 0,
 285                 0, 0, 1, 0,
 286                 0, 0, 0, 1];
 287       case 'rotate3d':
 288         var x = item.d[0];
 289         var y = item.d[1];
 290         var z = item.d[2];
 291         var rads = item.d[3].rad || 0;
 292         var degs = item.d[3].deg || 0;
 293         var angle = (degs * Math.PI / 180) + rads;
 294
 295         var sqrLength = x * x + y * y + z * z;
 296         if (sqrLength === 0) {
 297           x = 1;
 298           y = 0;
 299           z = 0;
 300         } else if (sqrLength !== 1) {
 301           var length = Math.sqrt(sqrLength);
 302           x /= length;
 303           y /= length;
 304           z /= length;
 305         }
 306
 307         var s = Math.sin(angle / 2);
 308         var sc = s * Math.cos(angle / 2);
 309         var sq = s * s;
 310         return [
 311           1 - 2 * (y * y + z * z) * sq,
 312           2 * (x * y * sq + z * sc),
 313           2 * (x * z * sq - y * sc),
 314           0,
 315
 316           2 * (x * y * sq - z * sc),
 317           1 - 2 * (x * x + z * z) * sq,
 318           2 * (y * z * sq + x * sc),
 319           0,
 320
 321           2 * (x * z * sq + y * sc),
 322           2 * (y * z * sq - x * sc),
 323           1 - 2 * (x * x + y * y) * sq,
 324           0,
 325
 326           0, 0, 0, 1
 327         ];
 328       case 'scale':
 329         return [item.d[0], 0, 0, 0,
 330                 0, item.d[1], 0, 0,
 331                 0, 0, 1, 0,
 332                 0, 0, 0, 1];
 333       case 'scalex':
 334         return [item.d[0], 0, 0, 0,
 335                 0, 1, 0, 0,
 336                 0, 0, 1, 0,
 337                 0, 0, 0, 1];
 338       case 'scaley':
 339         return [1, 0, 0, 0,
 340                 0, item.d[0], 0, 0,
 341                 0, 0, 1, 0,
 342                 0, 0, 0, 1];
 343       case 'scalez':
 344         return [1, 0, 0, 0,
 345                 0, 1, 0, 0,
 346                 0, 0, item.d[0], 0,
 347                 0, 0, 0, 1];
 348       case 'scale3d':
 349         return [item.d[0], 0, 0, 0,
 350                 0, item.d[1], 0, 0,
 351                 0, 0, item.d[2], 0,
 352                 0, 0, 0, 1];
 353       // FIXME: Skew behaves differently in Blink, FireFox and here. Need to work out why.
 354       case 'skew':
 355         var xDegs = item.d[0].deg || 0;
 356         var xRads = item.d[0].rad || 0;
 357         var yDegs = item.d[1].deg || 0;
 358         var yRads = item.d[1].rad || 0;
 359         var xAngle = (xDegs * Math.PI / 180) + xRads;
 360         var yAngle = (yDegs * Math.PI / 180) + yRads;
 361         return [1, Math.tan(yAngle), 0, 0,
 362                 Math.tan(xAngle), 1, 0, 0,
 363                 0, 0, 1, 0,
 364                 0, 0, 0, 1];
 365       case 'skewx':
 366         var rads = item.d[0].rad || 0;
 367         var degs = item.d[0].deg || 0;
 368         var angle = (degs * Math.PI / 180) + rads;
 369         return [1, 0, 0, 0,
 370                 Math.tan(angle), 1, 0, 0,
 371                 0, 0, 1, 0,
 372                 0, 0, 0, 1];
 373       case 'skewy':
 374         var rads = item.d[0].rad || 0;
 375         var degs = item.d[0].deg || 0;
 376         var angle = (degs * Math.PI / 180) + rads;
 377         return [1, Math.tan(angle), 0, 0,
 378                 0, 1, 0, 0,
 379                 0, 0, 1, 0,
 380                 0, 0, 0, 1];
 381       // TODO: Work out what to do with non-px values.
 382       case 'translate':
 383         var x = item.d[0].px || 0;
 384         var y = item.d[1].px || 0;
 385         return [1, 0, 0, 0,
 386                 0, 1, 0, 0,
 387                 0, 0, 1, 0,
 388                 x, y, 0, 1];
 389       case 'translatex':
 390         var x = item.d[0].px || 0;
 391         return [1, 0, 0, 0,
 392                 0, 1, 0, 0,
 393                 0, 0, 1, 0,
 394                 x, 0, 0, 1];
 395       case 'translatey':
 396         var y = item.d[0].px || 0;
 397         return [1, 0, 0, 0,
 398                 0, 1, 0, 0,
 399                 0, 0, 1, 0,
 400                 0, y, 0, 1];
 401       case 'translatez':
 402         var z = item.d[0].px || 0;
 403         return [1, 0, 0, 0,
 404                 0, 1, 0, 0,
 405                 0, 0, 1, 0,
 406                 0, 0, z, 1];
 407       case 'translate3d':
 408         var x = item.d[0].px || 0;
 409         var y = item.d[1].px || 0;
 410         var z = item.d[2].px || 0;
 411         return [1, 0, 0, 0,
 412                 0, 1, 0, 0,
 413                 0, 0, 1, 0,
 414                 x, y, z, 1];
 415       case 'perspective':
 416         var p = item.d[0].px ? (-1 / item.d[0].px) : 0;
 417         return [
 418           1, 0, 0, 0,
 419           0, 1, 0, 0,
 420           0, 0, 1, p,
 421           0, 0, 0, 1];
 422       case 'matrix':
 423         return [item.d[0], item.d[1], 0, 0,
 424                 item.d[2], item.d[3], 0, 0,
 425                 0, 0, 1, 0,
 426                 item.d[4], item.d[5], 0, 1];
 427       case 'matrix3d':
 428         return item.d;
 429       default:
 430         WEB_ANIMATIONS_TESTING && console.assert(false, 'Transform item type ' + item.t +
 431             ' conversion to matrix not yet implemented.');
 432     }
 433   }
 434
 435   function convertToMatrix(transformList) {
 436     if (transformList.length === 0) {
 437       return [1, 0, 0, 0,
 438               0, 1, 0, 0,
 439               0, 0, 1, 0,
 440               0, 0, 0, 1];
 441     }
 442     return transformList.map(convertItemToMatrix).reduce(multiplyMatrices);
 443   }
 444
 445   function makeMatrixDecomposition(transformList) {
 446     return [decomposeMatrix(convertToMatrix(transformList))];
 447   }
 448
 449   scope.dot = dot;
 450   scope.makeMatrixDecomposition = makeMatrixDecomposition;
 451
 452 })(webAnimations1, webAnimationsTesting);