Adding Blink-side 3d Box and Bounds calculations to TransformOperations

Source/platform/transforms/TransformOperations.cpp

Index: Source/platform/transforms/TransformOperations.cpp
diff --git a/Source/platform/transforms/TransformOperations.cpp b/Source/platform/transforms/TransformOperations.cpp
index a0664f7d71439d9f48642e4150e4e74c81ba613d..809789fe3112f8bc3adecd6ee1d122568bc9571c 100644
--- a/Source/platform/transforms/TransformOperations.cpp
+++ b/Source/platform/transforms/TransformOperations.cpp
@@ -22,8 +22,11 @@
 #include "config.h"
 #include "platform/transforms/TransformOperations.h"
 
+#include "platform/animation/AnimationUtilities.h"
+#include "platform/geometry/FloatBox.h"
 #include "platform/transforms/IdentityTransformOperation.h"
 #include "platform/transforms/InterpolatedTransformOperation.h"
+#include "platform/transforms/RotateTransformOperation.h"
 #include <algorithm>
 
 using namespace std;
@@ -109,6 +112,267 @@ TransformOperations TransformOperations::blend(const TransformOperations& from,
     return blendByUsingMatrixInterpolation(from, progress);
 }
 
+static void findCandidatesInPlane(double px, double py, double nz, double* candidates, int* numCandidates)
+{
+    // The angle that this point is rotated with respect to the plane nz
+    double phi = atan2(px, py);
+
+    *numCandidates = 4;
+    candidates[0] = phi; // The element at 0deg (maximum x)
+
+    for (int i = 1; i < *numCandidates; ++i)
+        candidates[i] = candidates[i - 1] + M_PI_2; // every 90 deg
+    if (nz < 0.f) {
+        for (int i = 0; i < *numCandidates; ++i)
+            candidates[i] *= -1;
+    }
+}
+
+// This method returns the bounding box that contains the starting point,
+// the ending point, and any of the extrema (in each dimension) found across
+// the circle described by the arc. These are then filtered to points that
+// actually reside on the arc.
+static void boundingBoxForArc(const FloatPoint3D& point, const RotateTransformOperation& fromTransform, const RotateTransformOperation& toTransform, double minProgress, double maxProgress, FloatBox& box)
+{
+    double candidates[6];
+    int numCandidates = 0;
+
+    FloatPoint3D axis(fromTransform.axis());
+    double fromDegrees = fromTransform.angle();
+    double toDegrees = toTransform.angle();
+
+    if (axis.dot(toTransform.axis()) < 0)
+        toDegrees *= -1;
+
+    fromDegrees  = blend(fromDegrees, toTransform.angle(), minProgress);
+    toDegrees = blend(toDegrees, fromTransform.angle(), 1.0 - maxProgress);
+    if (fromDegrees > toDegrees)
+        std::swap(fromDegrees, toDegrees);
+
+    TransformationMatrix fromMatrix;
+    TransformationMatrix toMatrix;
+    fromMatrix.rotate3d(fromTransform.x(), fromTransform.y(), fromTransform.z(), fromDegrees);
+    toMatrix.rotate3d(fromTransform.x(), fromTransform.y(), fromTransform.z(), toDegrees);
+
+    FloatPoint3D fromPoint = fromMatrix.mapPoint(point);
+    FloatPoint3D toPoint = toMatrix.mapPoint(point);
+
+    if (box.isEmpty())
+        box.setOrigin(fromPoint);
+    else
+        box.expandTo(fromPoint);
+
+    box.expandTo(toPoint);
+
+    switch (fromTransform.type()) {
+    case TransformOperation::RotateX:
+        findCandidatesInPlane(point.y(), point.z(), fromTransform.x(), candidates, &numCandidates);
+        break;
+    case TransformOperation::RotateY:
+        findCandidatesInPlane(point.z(), point.x(), fromTransform.y(), candidates, &numCandidates);
+        break;
+    case TransformOperation::RotateZ:
+        findCandidatesInPlane(point.x(), point.y(), fromTransform.z(), candidates, &numCandidates);
+        break;
+    default:
+        {
+            FloatPoint3D normal = axis;
+            if (normal.isZero())
+                return;
+            normal.normalize();
+            FloatPoint3D origin;
+            FloatPoint3D toPoint = point - origin;
+            FloatPoint3D center = origin + normal * toPoint.dot(normal);
+            FloatPoint3D v1 = point - center;
+            if (v1.isZero())
+                return;
+
+            v1.normalize();
+            FloatPoint3D v2 = normal.cross(v1);
+            // v1 is the basis vector in the direction of the point.
+            // i.e. with a rotation of 0, v1 is our +x vector.
+            // v2 is a perpenticular basis vector of our plane (+y).
+
+            // Take the parametric equation of a circle.
+            // (x = r*cos(t); y = r*sin(t);
+            // We can treat that as a circle on the plane v1xv2
+            // From that we get the parametric equations for a circle on the
+            // plane in 3d space of
+            // x(t) = r*cos(t)*v1.x + r*sin(t)*v2.x + cx
+            // y(t) = r*cos(t)*v1.y + r*sin(t)*v2.y + cy
+            // z(t) = r*cos(t)*v1.z + r*sin(t)*v2.z + cz
+            // taking the derivative of (x, y, z) and solving for 0 gives us our
+            // maximum/minimum x, y, z values
+            // x'(t) = r*cos(t)*v2.x - r*sin(t)*v1.x = 0
+            // tan(t) = v2.x/v1.x
+            // t = atan2(v2.x, v1.x) + n*M_PI;
+
+            candidates[0] = atan2(v2.x(), v1.x());
+            candidates[1] = candidates[0] + M_PI;
+            candidates[2] = atan2(v2.y(), v1.y());
+            candidates[3] = candidates[2] + M_PI;
+            candidates[4] = atan2(v2.z(), v1.z());
+            candidates[5] = candidates[4] + M_PI;
+            numCandidates = 6;
+        }
+        break;
+    }
+
+    double minRadians = deg2rad(fromDegrees);
+    double maxRadians = deg2rad(toDegrees);
+    // Once we have the candidates, we now filter them down to ones that
+    // actually live on the arc, rather than the entire circle.
+    for (int i = 0; i < numCandidates; ++i) {
+        double radians = candidates[i];
+
+        while (radians < minRadians)
+            radians += 2.0 * M_PI;
+        while (radians > maxRadians)
+            radians -= 2.0 * M_PI;
+        if (radians < minRadians)
+            continue;
+
+        TransformationMatrix rotation;
+        rotation.rotate3d(axis.x(), axis.y(), axis.z(), rad2deg(radians));
+        box.expandTo(rotation.mapPoint(point));
+    }
+}
+
+bool TransformOperations::blendedBoundsForBox(const FloatBox& box, const TransformOperations& from, const double& minProgress, const double& maxProgress, FloatBox* bounds) const
+{
+
+    int fromSize = from.operations().size();
+    int toSize = operations().size();
+    int size = max(fromSize, toSize);
+
+    *bounds = box;
+    for (int i = size - 1; i >= 0; i--) {
+        RefPtr<TransformOperation> fromOperation = (i < fromSize) ? from.operations()[i] : nullptr;
+        RefPtr<TransformOperation> toOperation = (i < toSize) ? operations()[i] : nullptr;
+        if (fromOperation && fromOperation->type() == TransformOperation::None)
+            fromOperation = nullptr;
+
+        if (toOperation && toOperation->type() == TransformOperation::None)
+            toOperation = nullptr;
+
+        TransformOperation::OperationType interpolationType = toOperation ? toOperation->type() :
+            fromOperation ? fromOperation->type() :
+            TransformOperation::None;
+        if (fromOperation && toOperation && !fromOperation->canBlendWith(*toOperation.get()))
+            return false;
+
+        switch (interpolationType) {
+        case TransformOperation::Identity:
+            bounds->expandTo(box);
+            continue;
+        case TransformOperation::Translate:
+        case TransformOperation::TranslateX:
+        case TransformOperation::TranslateY:
+        case TransformOperation::TranslateZ:
+        case TransformOperation::Translate3D:
+        case TransformOperation::Scale:
+        case TransformOperation::ScaleX:
+        case TransformOperation::ScaleY:
+        case TransformOperation::ScaleZ:
+        case TransformOperation::Scale3D:
+        case TransformOperation::Skew:
+        case TransformOperation::SkewX:
+        case TransformOperation::SkewY:
+        case TransformOperation::Perspective:
+            {
+                RefPtr<TransformOperation> fromTransform;
+                RefPtr<TransformOperation> toTransform;
+                if (!toOperation) {
+                    fromTransform = fromOperation->blend(toOperation.get(), 1-minProgress, false);
+                    toTransform = fromOperation->blend(toOperation.get(), 1-maxProgress, false);
+                } else {
+                    fromTransform = toOperation->blend(fromOperation.get(), minProgress, false);
+                    toTransform = toOperation->blend(fromOperation.get(), maxProgress, false);
+                }
+                if (!fromTransform || !toTransform)
+                    continue;
+                TransformationMatrix fromMatrix;
+                TransformationMatrix toMatrix;
+                fromTransform->apply(fromMatrix, FloatSize());
+                toTransform->apply(toMatrix, FloatSize());
+                FloatBox fromBox = *bounds;
+                FloatBox toBox = *bounds;
+                fromMatrix.transformBox(fromBox);
+                toMatrix.transformBox(toBox);
+                *bounds = fromBox;
+                bounds->expandTo(toBox);
+                continue;
+            }
+        case TransformOperation::Rotate: // This is also RotateZ
+        case TransformOperation::Rotate3D:
+        case TransformOperation::RotateX:
+        case TransformOperation::RotateY:
+            {
+                RefPtr<RotateTransformOperation> identityRotation;
+                const RotateTransformOperation* fromRotation = nullptr;
+                const RotateTransformOperation* toRotation = nullptr;
+                if (fromOperation) {
+                    fromRotation = static_cast<const RotateTransformOperation*>(fromOperation.get());
+                    if (fromRotation->axis().isZero())
+                        fromRotation = nullptr;
+                }
+
+                if (toOperation) {
+                    toRotation = static_cast<const RotateTransformOperation*>(toOperation.get());
+                    if (toRotation->axis().isZero())
+                        toRotation = nullptr;
+                }
+
+                double fromAngle;
+                double toAngle;
+                FloatPoint3D axis;
+                if (!RotateTransformOperation::shareSameAxis(fromRotation, toRotation, &axis, &fromAngle, &toAngle)) {
+                    return(false);
+                }
+
+                if (!fromRotation) {
+                    identityRotation = RotateTransformOperation::create(axis.x(), axis.y(), axis.z(), 0, fromOperation ? fromOperation->type() : toOperation->type());
+                    fromRotation = identityRotation.get();
+                }
+
+                if (!toRotation) {
+                    if (!identityRotation)
+                        identityRotation = RotateTransformOperation::create(axis.x(), axis.y(), axis.z(), 0, fromOperation ? fromOperation->type() : toOperation->type());
+                    toRotation = identityRotation.get();
+                }
+
+                FloatBox fromBox = *bounds;
+                bool first = true;
+                for (size_t i = 0; i < 2; ++i) {
+                    for (size_t j = 0; j < 2; ++j) {
+                        for (size_t k = 0; k < 2; ++k) {
+                            FloatBox boundsForArc;
+                            FloatPoint3D corner(fromBox.x(), fromBox.y(), fromBox.z());
+                            corner += FloatPoint3D(i * fromBox.width(), j * fromBox.height(), k * fromBox.depth());
+                            boundingBoxForArc(corner, *fromRotation, *toRotation, minProgress, maxProgress, boundsForArc);
+                            if (first) {
+                                *bounds = boundsForArc;
+                                first = false;
+                            } else {
+                                bounds->expandTo(boundsForArc);
+                            }
+                        }
+                    }
+                }
+            }
+            continue;
+        case TransformOperation::None:
+            continue;
+        case TransformOperation::Matrix:
+        case TransformOperation::Matrix3D:
+        case TransformOperation::Interpolated:
+            return(false);
+        }
+    }
+
+    return true;
+}
+
 TransformOperations TransformOperations::add(const TransformOperations& addend) const
 {
     TransformOperations result;