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

Source/platform/transforms/TransformOperations.cpp

 /*
  * Copyright (C) 1999 Antti Koivisto (koivisto@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library General Public License
  * along with this library; see the file COPYING.LIB.  If not, write to
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  *
  */
 
 #include "config.h"
 #include "platform/transforms/TransformOperations.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;
 
 namespace WebCore {
 
+const double kAngleEpsilon = 1e-4;
+
+static inline void blendFloat(double& from, double to, double progress)

[Ian Vollick, 2014/06/16 15:23:37]

Please switch this to the pre-existing blend fn you told me about offline.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+{
+    if (from != to)
+        from = from + (to - from) * progress;
+}
+
 TransformOperations::TransformOperations(bool makeIdentity)
 {
     if (makeIdentity)
         m_operations.append(IdentityTransformOperation::create());
 }
 
 bool TransformOperations::operator==(const TransformOperations& o) const
 {
     if (m_operations.size() != o.m_operations.size())
         return false;
@@ skipping 59 matching lines @@
     if (from == *this || (!from.size() && !size()))
         return *this;
 
     // If either list is empty, use blendByMatchingOperations which has special logic for this case.
     if (!from.size() || !size() || from.operationsMatch(*this))
         return blendByMatchingOperations(from, progress);
 
     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;
+    }
+}
+

[Ian Vollick, 2014/06/16 15:23:37]

A general comment here about how this method works would be helpful. I.e., finds
potential extrema along the x, y and z axes and checks which of these actually
lie along the arc.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+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.x(), fromTransform.y(), fromTransform.z());
+    double fromDegrees = fromTransform.angle();
+    double toDegrees = toTransform.angle();
+
+    if (axis.dot(FloatPoint3D(toTransform.x(), toTransform.y(), toTransform.z())) < 0) {

[Ian Vollick, 2014/06/16 15:23:37]

FloatPoint3D RotationTransformOperation::axis() would be nice.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+        toDegrees *= -1;

[Ian Vollick, 2014/06/16 15:23:37]

Nit: no braces on one-liners in blink. Here and elsewhere.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+    }
+
+    blendFloat(fromDegrees, toTransform.angle(), minProgress);
+    blendFloat(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;
+    }
+

[Ian Vollick, 2014/06/16 15:23:37]

Pls add comment that explains that this is where we check if the candidates are
actually on the arc.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+    double minRadians = deg2rad(fromDegrees);
+    double maxRadians = deg2rad(toDegrees);
+    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));
+    }
+}
+
+static bool isEmptyAxis(const RotateTransformOperation& from)

[Ian Vollick, 2014/06/16 15:23:37]

nuke.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+{
+    double lengthSquared = from.x() * from.x() + from.y() * from.y() + from.z() * from.z();
+    return (lengthSquared < kAngleEpsilon);
+}
+
+static bool shareSameAxis(const RotateTransformOperation* from, const RotateTransformOperation* to, double& x, double& y, double& z)

[Ian Vollick, 2014/06/16 15:23:37]

ditto.

[awoloszyn, 2014/06/17 14:26:01]

Done.

+{
+    if (!from && !to) {
+        x = 0.f;
+        y = 0.f;
+        z = 1.f;
+        return true;
+    }
+
+    if (from && to) {
+        if (!from->isSameType(*to)) {
+            return false;
+        }
+    } else {
+        if (from) {
+            x = from->x();
+            y = from->y();
+            z = from->z();
+            return true;
+        }
+
+        x = to->x();
+        y = to->y();
+        z = to->z();
+        return true;
+    }
+
+    double fromSquared = from->x() * from->x() + from->y() * from->y() + from->z() * from->z();
+    double toSquared   = to->x()   * to->x()   + to->y()   * to->y()   + to->z()   * to->z();
+
+    if (fromSquared <= kAngleEpsilon || toSquared <= kAngleEpsilon) {
+        return false;
+    }
+
+    double dot = from->x() * to->x() + from->y() * to->y() + from->z() * to->z();
+    double error = std::abs(1 - (dot * dot) / (fromSquared * toSquared));
+
+    x = from->x();
+    y = from->y();
+    z = from->z();
+
+    return (error < kAngleEpsilon);
+}
+
+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]: static_cast<TransformOperation*>(0);
+        RefPtr<TransformOperation> toOperation = (i < toSize)? operations()[i]: static_cast<TransformOperation*>(0);
+        if (fromOperation && fromOperation->type() == TransformOperation::None) {
+            fromOperation = static_cast<TransformOperation*>(0);
+        }
+        if (toOperation && toOperation->type() == TransformOperation::None) {
+            toOperation = static_cast<TransformOperation*>(0);
+        }
+        TransformOperation::OperationType interpolationType = toOperation? toOperation->type():
+            fromOperation? fromOperation->type():
+            TransformOperation::None;
+        if (fromOperation && toOperation && !fromOperation->isCompatibleType(*toOperation.get())) {
+            continue;
+        }
+
+        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 (isEmptyAxis(*fromRotation)) {
+                        fromRotation = nullptr;
+                    }
+                }
+
+                if (toOperation) {
+                    toRotation = static_cast<const RotateTransformOperation*>(toOperation.get());
+                    if (isEmptyAxis(*toRotation)) {
+                        toRotation = nullptr;
+                    }
+                }
+                double x = 0;
+                double y = 0;
+                double z = 0;
+                if (!shareSameAxis(fromRotation, toRotation, x, y, z)) {
+                    return(false);
+                }
+
+                if (!fromRotation) {
+                    identityRotation = RotateTransformOperation::create(x, y, z, 0, fromOperation? fromOperation->type(): toOperation->type());
+                    fromRotation = identityRotation.get();
+                }
+
+                if (!toRotation) {
+                    if (!identityRotation) {
+                        identityRotation = RotateTransformOperation::create(x, y, z, 0, fromOperation? fromOperation->type(): toOperation->type());
+                    }
+                    toRotation = identityRotation.get();
+                }
+
+                FloatBox fromBox = *bounds;
+                bool first = true;
+                for (int i = 0; i < 8; i++) {
+                    FloatBox boundsForArc;
+                    FloatPoint3D corner(fromBox.x(), fromBox.y(), fromBox.z());
+                    corner += FloatPoint3D(i & 1? fromBox.width() :0.f,

[Ian Vollick, 2014/06/16 15:23:38]

nit: very inconsistent use of spaces around here.

In retrospect, this code is probably too cute. A tiny triply-nested for might be
easier to read?

[awoloszyn, 2014/06/17 14:26:01]

I have no problems putting in the triply nested for-loop, my only concern is
that this will end up with us having 8 levels of indentation, which might cause
some confusion, although the last 4 levels will all be very localized to these
10 lines of code, so you are right it will probably be better.

+                        i & 2? fromBox.height():0.f,
+                        i & 4? fromBox.depth() :0.f);
+                    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;
     result.m_operations = operations();
     result.m_operations.appendVector(addend.operations());
     return result;
 }
 
 } // namespace WebCore