src/third_party/WebKit/Source/platform/transforms/TransformOperations.cpp

   1 /*
   2  * Copyright (C) 1999 Antti Koivisto (koivisto@kde.org)
   3  * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this library; see the file COPYING.LIB.  If not, write to
  17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 #include "config.h"
  23 #include "platform/transforms/TransformOperations.h"
  24
  25 #include "platform/animation/AnimationUtilities.h"
  26 #include "platform/geometry/FloatBox.h"
  27 #include "platform/transforms/IdentityTransformOperation.h"
  28 #include "platform/transforms/InterpolatedTransformOperation.h"
  29 #include "platform/transforms/RotateTransformOperation.h"
  30 #include <algorithm>
  31
  32 using namespace std;
  33
  34 namespace blink {
  35
  36 TransformOperations::TransformOperations(bool makeIdentity)
  37 {
  38     if (makeIdentity)
  39         m_operations.append(IdentityTransformOperation::create());
  40 }
  41
  42 bool TransformOperations::operator==(const TransformOperations& o) const
  43 {
  44     if (m_operations.size() != o.m_operations.size())
  45         return false;
  46
  47     unsigned s = m_operations.size();
  48     for (unsigned i = 0; i < s; i++) {
  49         if (*m_operations[i] != *o.m_operations[i])
  50             return false;
  51     }
  52
  53     return true;
  54 }
  55
  56 bool TransformOperations::operationsMatch(const TransformOperations& other) const
  57 {
  58     size_t numOperations = operations().size();
  59     // If the sizes of the function lists don't match, the lists don't match
  60     if (numOperations != other.operations().size())
  61         return false;
  62
  63     // If the types of each function are not the same, the lists don't match
  64     for (size_t i = 0; i < numOperations; ++i) {
  65         if (!operations()[i]->isSameType(*other.operations()[i]))
  66             return false;
  67     }
  68     return true;
  69 }
  70
  71 TransformOperations TransformOperations::blendByMatchingOperations(const TransformOperations& from, const double& progress) const
  72 {
  73     TransformOperations result;
  74
  75     unsigned fromSize = from.operations().size();
  76     unsigned toSize = operations().size();
  77     unsigned size = max(fromSize, toSize);
  78     for (unsigned i = 0; i < size; i++) {
  79         RefPtr<TransformOperation> fromOperation = (i < fromSize) ? from.operations()[i].get() : 0;
  80         RefPtr<TransformOperation> toOperation = (i < toSize) ? operations()[i].get() : 0;
  81         RefPtr<TransformOperation> blendedOperation = toOperation ? toOperation->blend(fromOperation.get(), progress) : (fromOperation ? fromOperation->blend(0, progress, true) : nullptr);
  82         if (blendedOperation)
  83             result.operations().append(blendedOperation);
  84         else {
  85             RefPtr<TransformOperation> identityOperation = IdentityTransformOperation::create();
  86             if (progress > 0.5)
  87                 result.operations().append(toOperation ? toOperation : identityOperation);
  88             else
  89                 result.operations().append(fromOperation ? fromOperation : identityOperation);
  90         }
  91     }
  92
  93     return result;
  94 }
  95
  96 TransformOperations TransformOperations::blendByUsingMatrixInterpolation(const TransformOperations& from, double progress) const
  97 {
  98     TransformOperations result;
  99     result.operations().append(InterpolatedTransformOperation::create(from, *this, progress));
 100     return result;
 101 }
 102
 103 TransformOperations TransformOperations::blend(const TransformOperations& from, double progress) const
 104 {
 105     if (from == *this || (!from.size() && !size()))
 106         return *this;
 107
 108     // If either list is empty, use blendByMatchingOperations which has special logic for this case.
 109     if (!from.size() || !size() || from.operationsMatch(*this))
 110         return blendByMatchingOperations(from, progress);
 111
 112     return blendByUsingMatrixInterpolation(from, progress);
 113 }
 114
 115 static void findCandidatesInPlane(double px, double py, double nz, double* candidates, int* numCandidates)
 116 {
 117     // The angle that this point is rotated with respect to the plane nz
 118     double phi = atan2(px, py);
 119
 120     *numCandidates = 4;
 121     candidates[0] = phi; // The element at 0deg (maximum x)
 122
 123     for (int i = 1; i < *numCandidates; ++i)
 124         candidates[i] = candidates[i - 1] + M_PI_2; // every 90 deg
 125     if (nz < 0.f) {
 126         for (int i = 0; i < *numCandidates; ++i)
 127             candidates[i] *= -1;
 128     }
 129 }
 130
 131 // This method returns the bounding box that contains the starting point,
 132 // the ending point, and any of the extrema (in each dimension) found across
 133 // the circle described by the arc. These are then filtered to points that
 134 // actually reside on the arc.
 135 static void boundingBoxForArc(const FloatPoint3D& point, const RotateTransformOperation& fromTransform, const RotateTransformOperation& toTransform, double minProgress, double maxProgress, FloatBox& box)
 136 {
 137     double candidates[6];
 138     int numCandidates = 0;
 139
 140     FloatPoint3D axis(fromTransform.axis());
 141     double fromDegrees = fromTransform.angle();
 142     double toDegrees = toTransform.angle();
 143
 144     if (axis.dot(toTransform.axis()) < 0)
 145         toDegrees *= -1;
 146
 147     fromDegrees  = blend(fromDegrees, toTransform.angle(), minProgress);
 148     toDegrees = blend(toDegrees, fromTransform.angle(), 1.0 - maxProgress);
 149     if (fromDegrees > toDegrees)
 150         std::swap(fromDegrees, toDegrees);
 151
 152     TransformationMatrix fromMatrix;
 153     TransformationMatrix toMatrix;
 154     fromMatrix.rotate3d(fromTransform.x(), fromTransform.y(), fromTransform.z(), fromDegrees);
 155     toMatrix.rotate3d(fromTransform.x(), fromTransform.y(), fromTransform.z(), toDegrees);
 156
 157     FloatPoint3D fromPoint = fromMatrix.mapPoint(point);
 158     FloatPoint3D toPoint = toMatrix.mapPoint(point);
 159
 160     if (box.isEmpty())
 161         box.setOrigin(fromPoint);
 162     else
 163         box.expandTo(fromPoint);
 164
 165     box.expandTo(toPoint);
 166
 167     switch (fromTransform.type()) {
 168     case TransformOperation::RotateX:
 169         findCandidatesInPlane(point.y(), point.z(), fromTransform.x(), candidates, &numCandidates);
 170         break;
 171     case TransformOperation::RotateY:
 172         findCandidatesInPlane(point.z(), point.x(), fromTransform.y(), candidates, &numCandidates);
 173         break;
 174     case TransformOperation::RotateZ:
 175         findCandidatesInPlane(point.x(), point.y(), fromTransform.z(), candidates, &numCandidates);
 176         break;
 177     default:
 178         {
 179             FloatPoint3D normal = axis;
 180             if (normal.isZero())
 181                 return;
 182             normal.normalize();
 183             FloatPoint3D origin;
 184             FloatPoint3D toPoint = point - origin;
 185             FloatPoint3D center = origin + normal * toPoint.dot(normal);
 186             FloatPoint3D v1 = point - center;
 187             if (v1.isZero())
 188                 return;
 189
 190             v1.normalize();
 191             FloatPoint3D v2 = normal.cross(v1);
 192             // v1 is the basis vector in the direction of the point.
 193             // i.e. with a rotation of 0, v1 is our +x vector.
 194             // v2 is a perpenticular basis vector of our plane (+y).
 195
 196             // Take the parametric equation of a circle.
 197             // (x = r*cos(t); y = r*sin(t);
 198             // We can treat that as a circle on the plane v1xv2
 199             // From that we get the parametric equations for a circle on the
 200             // plane in 3d space of
 201             // x(t) = r*cos(t)*v1.x + r*sin(t)*v2.x + cx
 202             // y(t) = r*cos(t)*v1.y + r*sin(t)*v2.y + cy
 203             // z(t) = r*cos(t)*v1.z + r*sin(t)*v2.z + cz
 204             // taking the derivative of (x, y, z) and solving for 0 gives us our
 205             // maximum/minimum x, y, z values
 206             // x'(t) = r*cos(t)*v2.x - r*sin(t)*v1.x = 0
 207             // tan(t) = v2.x/v1.x
 208             // t = atan2(v2.x, v1.x) + n*M_PI;
 209
 210             candidates[0] = atan2(v2.x(), v1.x());
 211             candidates[1] = candidates[0] + M_PI;
 212             candidates[2] = atan2(v2.y(), v1.y());
 213             candidates[3] = candidates[2] + M_PI;
 214             candidates[4] = atan2(v2.z(), v1.z());
 215             candidates[5] = candidates[4] + M_PI;
 216             numCandidates = 6;
 217         }
 218         break;
 219     }
 220
 221     double minRadians = deg2rad(fromDegrees);
 222     double maxRadians = deg2rad(toDegrees);
 223     // Once we have the candidates, we now filter them down to ones that
 224     // actually live on the arc, rather than the entire circle.
 225     for (int i = 0; i < numCandidates; ++i) {
 226         double radians = candidates[i];
 227
 228         while (radians < minRadians)
 229             radians += 2.0 * M_PI;
 230         while (radians > maxRadians)
 231             radians -= 2.0 * M_PI;
 232         if (radians < minRadians)
 233             continue;
 234
 235         TransformationMatrix rotation;
 236         rotation.rotate3d(axis.x(), axis.y(), axis.z(), rad2deg(radians));
 237         box.expandTo(rotation.mapPoint(point));
 238     }
 239 }
 240
 241 bool TransformOperations::blendedBoundsForBox(const FloatBox& box, const TransformOperations& from, const double& minProgress, const double& maxProgress, FloatBox* bounds) const
 242 {
 243
 244     int fromSize = from.operations().size();
 245     int toSize = operations().size();
 246     int size = max(fromSize, toSize);
 247
 248     *bounds = box;
 249     for (int i = size - 1; i >= 0; i--) {
 250         RefPtr<TransformOperation> fromOperation = (i < fromSize) ? from.operations()[i] : nullptr;
 251         RefPtr<TransformOperation> toOperation = (i < toSize) ? operations()[i] : nullptr;
 252         if (fromOperation && fromOperation->type() == TransformOperation::None)
 253             fromOperation = nullptr;
 254
 255         if (toOperation && toOperation->type() == TransformOperation::None)
 256             toOperation = nullptr;
 257
 258         TransformOperation::OperationType interpolationType = toOperation ? toOperation->type() :
 259             fromOperation ? fromOperation->type() :
 260             TransformOperation::None;
 261         if (fromOperation && toOperation && !fromOperation->canBlendWith(*toOperation.get()))
 262             return false;
 263
 264         switch (interpolationType) {
 265         case TransformOperation::Identity:
 266             bounds->expandTo(box);
 267             continue;
 268         case TransformOperation::Translate:
 269         case TransformOperation::TranslateX:
 270         case TransformOperation::TranslateY:
 271         case TransformOperation::TranslateZ:
 272         case TransformOperation::Translate3D:
 273         case TransformOperation::Scale:
 274         case TransformOperation::ScaleX:
 275         case TransformOperation::ScaleY:
 276         case TransformOperation::ScaleZ:
 277         case TransformOperation::Scale3D:
 278         case TransformOperation::Skew:
 279         case TransformOperation::SkewX:
 280         case TransformOperation::SkewY:
 281         case TransformOperation::Perspective:
 282             {
 283                 RefPtr<TransformOperation> fromTransform;
 284                 RefPtr<TransformOperation> toTransform;
 285                 if (!toOperation) {
 286                     fromTransform = fromOperation->blend(toOperation.get(), 1-minProgress, false);
 287                     toTransform = fromOperation->blend(toOperation.get(), 1-maxProgress, false);
 288                 } else {
 289                     fromTransform = toOperation->blend(fromOperation.get(), minProgress, false);
 290                     toTransform = toOperation->blend(fromOperation.get(), maxProgress, false);
 291                 }
 292                 if (!fromTransform || !toTransform)
 293                     continue;
 294                 TransformationMatrix fromMatrix;
 295                 TransformationMatrix toMatrix;
 296                 fromTransform->apply(fromMatrix, FloatSize());
 297                 toTransform->apply(toMatrix, FloatSize());
 298                 FloatBox fromBox = *bounds;
 299                 FloatBox toBox = *bounds;
 300                 fromMatrix.transformBox(fromBox);
 301                 toMatrix.transformBox(toBox);
 302                 *bounds = fromBox;
 303                 bounds->expandTo(toBox);
 304                 continue;
 305             }
 306         case TransformOperation::Rotate: // This is also RotateZ
 307         case TransformOperation::Rotate3D:
 308         case TransformOperation::RotateX:
 309         case TransformOperation::RotateY:
 310             {
 311                 RefPtr<RotateTransformOperation> identityRotation;
 312                 const RotateTransformOperation* fromRotation = nullptr;
 313                 const RotateTransformOperation* toRotation = nullptr;
 314                 if (fromOperation) {
 315                     fromRotation = static_cast<const RotateTransformOperation*>(fromOperation.get());
 316                     if (fromRotation->axis().isZero())
 317                         fromRotation = nullptr;
 318                 }
 319
 320                 if (toOperation) {
 321                     toRotation = static_cast<const RotateTransformOperation*>(toOperation.get());
 322                     if (toRotation->axis().isZero())
 323                         toRotation = nullptr;
 324                 }
 325
 326                 double fromAngle;
 327                 double toAngle;
 328                 FloatPoint3D axis;
 329                 if (!RotateTransformOperation::shareSameAxis(fromRotation, toRotation, &axis, &fromAngle, &toAngle)) {
 330                     return(false);
 331                 }
 332
 333                 if (!fromRotation) {
 334                     identityRotation = RotateTransformOperation::create(axis.x(), axis.y(), axis.z(), 0, fromOperation ? fromOperation->type() : toOperation->type());
 335                     fromRotation = identityRotation.get();
 336                 }
 337
 338                 if (!toRotation) {
 339                     if (!identityRotation)
 340                         identityRotation = RotateTransformOperation::create(axis.x(), axis.y(), axis.z(), 0, fromOperation ? fromOperation->type() : toOperation->type());
 341                     toRotation = identityRotation.get();
 342                 }
 343
 344                 FloatBox fromBox = *bounds;
 345                 bool first = true;
 346                 for (size_t i = 0; i < 2; ++i) {
 347                     for (size_t j = 0; j < 2; ++j) {
 348                         for (size_t k = 0; k < 2; ++k) {
 349                             FloatBox boundsForArc;
 350                             FloatPoint3D corner(fromBox.x(), fromBox.y(), fromBox.z());
 351                             corner += FloatPoint3D(i * fromBox.width(), j * fromBox.height(), k * fromBox.depth());
 352                             boundingBoxForArc(corner, *fromRotation, *toRotation, minProgress, maxProgress, boundsForArc);
 353                             if (first) {
 354                                 *bounds = boundsForArc;
 355                                 first = false;
 356                             } else {
 357                                 bounds->expandTo(boundsForArc);
 358                             }
 359                         }
 360                     }
 361                 }
 362             }
 363             continue;
 364         case TransformOperation::None:
 365             continue;
 366         case TransformOperation::Matrix:
 367         case TransformOperation::Matrix3D:
 368         case TransformOperation::Interpolated:
 369             return(false);
 370         }
 371     }
 372
 373     return true;
 374 }
 375
 376 TransformOperations TransformOperations::add(const TransformOperations& addend) const
 377 {
 378     TransformOperations result;
 379     result.m_operations = operations();
 380     result.m_operations.appendVector(addend.operations());
 381     return result;
 382 }
 383
 384 } // namespace blink