1// Copyright 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Needed on Windows to get |M_PI| from <cmath>
6#ifdef _WIN32
7#define _USE_MATH_DEFINES
8#endif
9
10#include <algorithm>
11#include <cmath>
12#include <limits>
13
14#include "base/logging.h"
15#include "cc/animation/transform_operation.h"
16#include "cc/animation/transform_operations.h"
17#include "ui/gfx/box_f.h"
18#include "ui/gfx/transform_util.h"
19#include "ui/gfx/vector3d_f.h"
20
21namespace {
22const SkMScalar kAngleEpsilon = 1e-4f;
23}
24
25namespace cc {
26
27bool TransformOperation::IsIdentity() const {
28  return matrix.IsIdentity();
29}
30
31static bool IsOperationIdentity(const TransformOperation* operation) {
32  return !operation || operation->IsIdentity();
33}
34
35static bool ShareSameAxis(const TransformOperation* from,
36                          const TransformOperation* to,
37                          SkMScalar* axis_x,
38                          SkMScalar* axis_y,
39                          SkMScalar* axis_z,
40                          SkMScalar* angle_from) {
41  if (IsOperationIdentity(from) && IsOperationIdentity(to))
42    return false;
43
44  if (IsOperationIdentity(from) && !IsOperationIdentity(to)) {
45    *axis_x = to->rotate.axis.x;
46    *axis_y = to->rotate.axis.y;
47    *axis_z = to->rotate.axis.z;
48    *angle_from = 0;
49    return true;
50  }
51
52  if (!IsOperationIdentity(from) && IsOperationIdentity(to)) {
53    *axis_x = from->rotate.axis.x;
54    *axis_y = from->rotate.axis.y;
55    *axis_z = from->rotate.axis.z;
56    *angle_from = from->rotate.angle;
57    return true;
58  }
59
60  SkMScalar length_2 = from->rotate.axis.x * from->rotate.axis.x +
61                       from->rotate.axis.y * from->rotate.axis.y +
62                       from->rotate.axis.z * from->rotate.axis.z;
63  SkMScalar other_length_2 = to->rotate.axis.x * to->rotate.axis.x +
64                             to->rotate.axis.y * to->rotate.axis.y +
65                             to->rotate.axis.z * to->rotate.axis.z;
66
67  if (length_2 <= kAngleEpsilon || other_length_2 <= kAngleEpsilon)
68    return false;
69
70  SkMScalar dot = to->rotate.axis.x * from->rotate.axis.x +
71                  to->rotate.axis.y * from->rotate.axis.y +
72                  to->rotate.axis.z * from->rotate.axis.z;
73  SkMScalar error =
74      std::abs(SK_MScalar1 - (dot * dot) / (length_2 * other_length_2));
75  bool result = error < kAngleEpsilon;
76  if (result) {
77    *axis_x = to->rotate.axis.x;
78    *axis_y = to->rotate.axis.y;
79    *axis_z = to->rotate.axis.z;
80    // If the axes are pointing in opposite directions, we need to reverse
81    // the angle.
82    *angle_from = dot > 0 ? from->rotate.angle : -from->rotate.angle;
83  }
84  return result;
85}
86
87static SkMScalar BlendSkMScalars(SkMScalar from,
88                                 SkMScalar to,
89                                 SkMScalar progress) {
90  return from * (1 - progress) + to * progress;
91}
92
93bool TransformOperation::BlendTransformOperations(
94    const TransformOperation* from,
95    const TransformOperation* to,
96    SkMScalar progress,
97    gfx::Transform* result) {
98  if (IsOperationIdentity(from) && IsOperationIdentity(to))
99    return true;
100
101  TransformOperation::Type interpolation_type =
102      TransformOperation::TransformOperationIdentity;
103  if (IsOperationIdentity(to))
104    interpolation_type = from->type;
105  else
106    interpolation_type = to->type;
107
108  switch (interpolation_type) {
109  case TransformOperation::TransformOperationTranslate: {
110    SkMScalar from_x = IsOperationIdentity(from) ? 0 : from->translate.x;
111    SkMScalar from_y = IsOperationIdentity(from) ? 0 : from->translate.y;
112    SkMScalar from_z = IsOperationIdentity(from) ? 0 : from->translate.z;
113    SkMScalar to_x = IsOperationIdentity(to) ? 0 : to->translate.x;
114    SkMScalar to_y = IsOperationIdentity(to) ? 0 : to->translate.y;
115    SkMScalar to_z = IsOperationIdentity(to) ? 0 : to->translate.z;
116    result->Translate3d(BlendSkMScalars(from_x, to_x, progress),
117                        BlendSkMScalars(from_y, to_y, progress),
118                        BlendSkMScalars(from_z, to_z, progress));
119    break;
120  }
121  case TransformOperation::TransformOperationRotate: {
122    SkMScalar axis_x = 0;
123    SkMScalar axis_y = 0;
124    SkMScalar axis_z = 1;
125    SkMScalar from_angle = 0;
126    SkMScalar to_angle = IsOperationIdentity(to) ? 0 : to->rotate.angle;
127    if (ShareSameAxis(from, to, &axis_x, &axis_y, &axis_z, &from_angle)) {
128      result->RotateAbout(gfx::Vector3dF(axis_x, axis_y, axis_z),
129                          BlendSkMScalars(from_angle, to_angle, progress));
130    } else {
131      gfx::Transform to_matrix;
132      if (!IsOperationIdentity(to))
133        to_matrix = to->matrix;
134      gfx::Transform from_matrix;
135      if (!IsOperationIdentity(from))
136        from_matrix = from->matrix;
137      *result = to_matrix;
138      if (!result->Blend(from_matrix, progress))
139        return false;
140    }
141    break;
142  }
143  case TransformOperation::TransformOperationScale: {
144    SkMScalar from_x = IsOperationIdentity(from) ? 1 : from->scale.x;
145    SkMScalar from_y = IsOperationIdentity(from) ? 1 : from->scale.y;
146    SkMScalar from_z = IsOperationIdentity(from) ? 1 : from->scale.z;
147    SkMScalar to_x = IsOperationIdentity(to) ? 1 : to->scale.x;
148    SkMScalar to_y = IsOperationIdentity(to) ? 1 : to->scale.y;
149    SkMScalar to_z = IsOperationIdentity(to) ? 1 : to->scale.z;
150    result->Scale3d(BlendSkMScalars(from_x, to_x, progress),
151                    BlendSkMScalars(from_y, to_y, progress),
152                    BlendSkMScalars(from_z, to_z, progress));
153    break;
154  }
155  case TransformOperation::TransformOperationSkew: {
156    SkMScalar from_x = IsOperationIdentity(from) ? 0 : from->skew.x;
157    SkMScalar from_y = IsOperationIdentity(from) ? 0 : from->skew.y;
158    SkMScalar to_x = IsOperationIdentity(to) ? 0 : to->skew.x;
159    SkMScalar to_y = IsOperationIdentity(to) ? 0 : to->skew.y;
160    result->SkewX(BlendSkMScalars(from_x, to_x, progress));
161    result->SkewY(BlendSkMScalars(from_y, to_y, progress));
162    break;
163  }
164  case TransformOperation::TransformOperationPerspective: {
165    SkMScalar from_perspective_depth =
166        IsOperationIdentity(from) ? std::numeric_limits<SkMScalar>::max()
167                                  : from->perspective_depth;
168    SkMScalar to_perspective_depth =
169        IsOperationIdentity(to) ? std::numeric_limits<SkMScalar>::max()
170                                : to->perspective_depth;
171    if (from_perspective_depth == 0.f || to_perspective_depth == 0.f)
172      return false;
173
174    SkMScalar blended_perspective_depth = BlendSkMScalars(
175        1.f / from_perspective_depth, 1.f / to_perspective_depth, progress);
176
177    if (blended_perspective_depth == 0.f)
178      return false;
179
180    result->ApplyPerspectiveDepth(1.f / blended_perspective_depth);
181    break;
182  }
183  case TransformOperation::TransformOperationMatrix: {
184    gfx::Transform to_matrix;
185    if (!IsOperationIdentity(to))
186      to_matrix = to->matrix;
187    gfx::Transform from_matrix;
188    if (!IsOperationIdentity(from))
189      from_matrix = from->matrix;
190    *result = to_matrix;
191    if (!result->Blend(from_matrix, progress))
192      return false;
193    break;
194  }
195  case TransformOperation::TransformOperationIdentity:
196    // Do nothing.
197    break;
198  }
199
200  return true;
201}
202
203// If p = (px, py) is a point in the plane being rotated about (0, 0, nz), this
204// function computes the angles we would have to rotate from p to get to
205// (length(p), 0), (-length(p), 0), (0, length(p)), (0, -length(p)). If nz is
206// negative, these angles will need to be reversed.
207static void FindCandidatesInPlane(float px,
208                                  float py,
209                                  float nz,
210                                  double* candidates,
211                                  int* num_candidates) {
212  double phi = atan2(px, py);
213  *num_candidates = 4;
214  candidates[0] = phi;
215  for (int i = 1; i < *num_candidates; ++i)
216    candidates[i] = candidates[i - 1] + M_PI_2;
217  if (nz < 0.f) {
218    for (int i = 0; i < *num_candidates; ++i)
219      candidates[i] *= -1.f;
220  }
221}
222
223static float RadiansToDegrees(float radians) {
224  return (180.f * radians) / M_PI;
225}
226
227static float DegreesToRadians(float degrees) {
228  return (M_PI * degrees) / 180.f;
229}
230
231static void BoundingBoxForArc(const gfx::Point3F& point,
232                              const TransformOperation* from,
233                              const TransformOperation* to,
234                              SkMScalar min_progress,
235                              SkMScalar max_progress,
236                              gfx::BoxF* box) {
237  const TransformOperation* exemplar = from ? from : to;
238  gfx::Vector3dF axis(exemplar->rotate.axis.x,
239                      exemplar->rotate.axis.y,
240                      exemplar->rotate.axis.z);
241
242  const bool x_is_zero = axis.x() == 0.f;
243  const bool y_is_zero = axis.y() == 0.f;
244  const bool z_is_zero = axis.z() == 0.f;
245
246  // We will have at most 6 angles to test (excluding from->angle and
247  // to->angle).
248  static const int kMaxNumCandidates = 6;
249  double candidates[kMaxNumCandidates];
250  int num_candidates = kMaxNumCandidates;
251
252  if (x_is_zero && y_is_zero && z_is_zero)
253    return;
254
255  SkMScalar from_angle = from ? from->rotate.angle : 0.f;
256  SkMScalar to_angle = to ? to->rotate.angle : 0.f;
257
258  // If the axes of rotation are pointing in opposite directions, we need to
259  // flip one of the angles. Note, if both |from| and |to| exist, then axis will
260  // correspond to |from|.
261  if (from && to) {
262    gfx::Vector3dF other_axis(
263        to->rotate.axis.x, to->rotate.axis.y, to->rotate.axis.z);
264    if (gfx::DotProduct(axis, other_axis) < 0.f)
265      to_angle *= -1.f;
266  }
267
268  float min_degrees =
269      SkMScalarToFloat(BlendSkMScalars(from_angle, to_angle, min_progress));
270  float max_degrees =
271      SkMScalarToFloat(BlendSkMScalars(from_angle, to_angle, max_progress));
272  if (max_degrees < min_degrees)
273    std::swap(min_degrees, max_degrees);
274
275  gfx::Transform from_transform;
276  from_transform.RotateAbout(axis, min_degrees);
277  gfx::Transform to_transform;
278  to_transform.RotateAbout(axis, max_degrees);
279
280  *box = gfx::BoxF();
281
282  gfx::Point3F point_rotated_from = point;
283  from_transform.TransformPoint(&point_rotated_from);
284  gfx::Point3F point_rotated_to = point;
285  to_transform.TransformPoint(&point_rotated_to);
286
287  box->set_origin(point_rotated_from);
288  box->ExpandTo(point_rotated_to);
289
290  if (x_is_zero && y_is_zero) {
291    FindCandidatesInPlane(
292        point.x(), point.y(), axis.z(), candidates, &num_candidates);
293  } else if (x_is_zero && z_is_zero) {
294    FindCandidatesInPlane(
295        point.z(), point.x(), axis.y(), candidates, &num_candidates);
296  } else if (y_is_zero && z_is_zero) {
297    FindCandidatesInPlane(
298        point.y(), point.z(), axis.x(), candidates, &num_candidates);
299  } else {
300    gfx::Vector3dF normal = axis;
301    normal.Scale(1.f / normal.Length());
302
303    // First, find center of rotation.
304    gfx::Point3F origin;
305    gfx::Vector3dF to_point = point - origin;
306    gfx::Point3F center =
307        origin + gfx::ScaleVector3d(normal, gfx::DotProduct(to_point, normal));
308
309    // Now we need to find two vectors in the plane of rotation. One pointing
310    // towards point and another, perpendicular vector in the plane.
311    gfx::Vector3dF v1 = point - center;
312    float v1_length = v1.Length();
313    if (v1_length == 0.f)
314      return;
315
316    v1.Scale(1.f / v1_length);
317    gfx::Vector3dF v2 = gfx::CrossProduct(normal, v1);
318    // v1 is the basis vector in the direction of the point.
319    // i.e. with a rotation of 0, v1 is our +x vector.
320    // v2 is a perpenticular basis vector of our plane (+y).
321
322    // Take the parametric equation of a circle.
323    // x = r*cos(t); y = r*sin(t);
324    // We can treat that as a circle on the plane v1xv2.
325    // From that we get the parametric equations for a circle on the
326    // plane in 3d space of:
327    // x(t) = r*cos(t)*v1.x + r*sin(t)*v2.x + cx
328    // y(t) = r*cos(t)*v1.y + r*sin(t)*v2.y + cy
329    // z(t) = r*cos(t)*v1.z + r*sin(t)*v2.z + cz
330    // Taking the derivative of (x, y, z) and solving for 0 gives us our
331    // maximum/minimum x, y, z values.
332    // x'(t) = r*cos(t)*v2.x - r*sin(t)*v1.x = 0
333    // tan(t) = v2.x/v1.x
334    // t = atan2(v2.x, v1.x) + n*M_PI;
335    candidates[0] = atan2(v2.x(), v1.x());
336    candidates[1] = candidates[0] + M_PI;
337    candidates[2] = atan2(v2.y(), v1.y());
338    candidates[3] = candidates[2] + M_PI;
339    candidates[4] = atan2(v2.z(), v1.z());
340    candidates[5] = candidates[4] + M_PI;
341  }
342
343  double min_radians = DegreesToRadians(min_degrees);
344  double max_radians = DegreesToRadians(max_degrees);
345
346  for (int i = 0; i < num_candidates; ++i) {
347    double radians = candidates[i];
348    while (radians < min_radians)
349      radians += 2.0 * M_PI;
350    while (radians > max_radians)
351      radians -= 2.0 * M_PI;
352    if (radians < min_radians)
353      continue;
354
355    gfx::Transform rotation;
356    rotation.RotateAbout(axis, RadiansToDegrees(radians));
357    gfx::Point3F rotated = point;
358    rotation.TransformPoint(&rotated);
359
360    box->ExpandTo(rotated);
361  }
362}
363
364bool TransformOperation::BlendedBoundsForBox(const gfx::BoxF& box,
365                                             const TransformOperation* from,
366                                             const TransformOperation* to,
367                                             SkMScalar min_progress,
368                                             SkMScalar max_progress,
369                                             gfx::BoxF* bounds) {
370  bool is_identity_from = IsOperationIdentity(from);
371  bool is_identity_to = IsOperationIdentity(to);
372  if (is_identity_from && is_identity_to) {
373    *bounds = box;
374    return true;
375  }
376
377  TransformOperation::Type interpolation_type =
378      TransformOperation::TransformOperationIdentity;
379  if (is_identity_to)
380    interpolation_type = from->type;
381  else
382    interpolation_type = to->type;
383
384  switch (interpolation_type) {
385    case TransformOperation::TransformOperationIdentity:
386      *bounds = box;
387      return true;
388    case TransformOperation::TransformOperationTranslate:
389    case TransformOperation::TransformOperationSkew:
390    case TransformOperation::TransformOperationPerspective:
391    case TransformOperation::TransformOperationScale: {
392      gfx::Transform from_transform;
393      gfx::Transform to_transform;
394      if (!BlendTransformOperations(from, to, min_progress, &from_transform) ||
395          !BlendTransformOperations(from, to, max_progress, &to_transform))
396        return false;
397
398      *bounds = box;
399      from_transform.TransformBox(bounds);
400
401      gfx::BoxF to_box = box;
402      to_transform.TransformBox(&to_box);
403      bounds->ExpandTo(to_box);
404
405      return true;
406    }
407    case TransformOperation::TransformOperationRotate: {
408      SkMScalar axis_x = 0;
409      SkMScalar axis_y = 0;
410      SkMScalar axis_z = 1;
411      SkMScalar from_angle = 0;
412      if (!ShareSameAxis(from, to, &axis_x, &axis_y, &axis_z, &from_angle))
413        return false;
414
415      bool first_point = true;
416      for (int i = 0; i < 8; ++i) {
417        gfx::Point3F corner = box.origin();
418        corner += gfx::Vector3dF(i & 1 ? box.width() : 0.f,
419                                 i & 2 ? box.height() : 0.f,
420                                 i & 4 ? box.depth() : 0.f);
421        gfx::BoxF box_for_arc;
422        BoundingBoxForArc(
423            corner, from, to, min_progress, max_progress, &box_for_arc);
424        if (first_point)
425          *bounds = box_for_arc;
426        else
427          bounds->Union(box_for_arc);
428        first_point = false;
429      }
430      return true;
431    }
432    case TransformOperation::TransformOperationMatrix:
433      return false;
434  }
435  NOTREACHED();
436  return false;
437}
438
439}  // namespace cc
440