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