Support calculation of inflated bounds for rotation transform operations.

We compute the inflated bound for a rotated 3d box by computing the axis aligned
bounding boxes for the arcs described by the corners during the rotation and
taking the union of those boxes. Lots of fun math.

R=ajuma@chromium.org
BUG=None

Review URL: https://codereview.chromium.org/26672005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@228026 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 197 insertions, 1 deletions

diff --git a/cc/animation/transform_operation.cc b/cc/animation/transform_operation.cc
index a06b533..b709ccb 100644
--- a/cc/animation/transform_operation.cc
+++ b/cc/animation/transform_operation.cc
@@ -2,6 +2,11 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+// Needed on Windows to get |M_PI| from <cmath>
+#ifdef _WIN32
+#define _USE_MATH_DEFINES
+#endif
+
 #include <algorithm>
 #include <cmath>
 #include <limits>
@@ -209,6 +214,181 @@ static void UnionBoxWithZeroScale(gfx::BoxF* box) {
       min_x, min_y, min_z, max_x - min_x, max_y - min_y, max_z - min_z);
 }
 
+// If p = (px, py) is a point in the plane being rotated about (0, 0, nz), this
+// function computes the angles we would have to rotate from p to get to
+// (length(p), 0), (-length(p), 0), (0, length(p)), (0, -length(p)). If nz is
+// negative, these angles will need to be reversed.
+static void FindCandidatesInPlane(float px,
+                                  float py,
+                                  float nz,
+                                  double* candidates,
+                                  int* num_candidates) {
+  double phi = atan2(px, py);
+  *num_candidates = 4;
+  candidates[0] = phi;
+  for (int i = 1; i < *num_candidates; ++i)
+    candidates[i] = candidates[i - 1] + M_PI_2;
+  if (nz < 0.f) {
+    for (int i = 0; i < *num_candidates; ++i)
+      candidates[i] *= -1.f;
+  }
+}
+
+static float RadiansToDegrees(float radians) {
+  return (180.f * radians) / M_PI;
+}
+
+static float DegreesToRadians(float degrees) {
+  return (M_PI * degrees) / 180.f;
+}
+
+// Div by zero doesn't always result in Inf as you might hope, so we'll do this
+// explicitly here.
+static float SafeDivide(float numerator, float denominator) {
+  if (numerator == 0.f)
+    return 0.f;
+
+  if (denominator == 0.f) {
+    return numerator > 0.f ? std::numeric_limits<float>::infinity()
+                           : -std::numeric_limits<float>::infinity();
+  }
+
+  return numerator / denominator;
+}
+
+static void BoundingBoxForArc(const gfx::Point3F& point,
+                              const TransformOperation* from,
+                              const TransformOperation* to,
+                              gfx::BoxF* box) {
+  const TransformOperation* exemplar = from ? from : to;
+  *box = gfx::BoxF();
+  gfx::Point3F point_rotated_from = point;
+  if (from)
+    from->matrix.TransformPoint(&point_rotated_from);
+  gfx::Point3F point_rotated_to = point;
+  if (to)
+    to->matrix.TransformPoint(&point_rotated_to);
+
+  box->set_origin(point_rotated_from);
+  box->ExpandTo(point_rotated_to);
+
+  const bool x_is_zero = exemplar->rotate.axis.x == 0.f;
+  const bool y_is_zero = exemplar->rotate.axis.y == 0.f;
+  const bool z_is_zero = exemplar->rotate.axis.z == 0.f;
+
+  // We will have at most 6 angles to test (excluding from->angle and
+  // to->angle).
+  static const int kMaxNumCandidates = 6;
+  double candidates[kMaxNumCandidates];
+  int num_candidates = kMaxNumCandidates;
+
+  if (x_is_zero && y_is_zero && z_is_zero)
+    return;
+
+  if (x_is_zero && y_is_zero) {
+    FindCandidatesInPlane(point.x(),
+                          point.y(),
+                          exemplar->rotate.axis.z,
+                          candidates,
+                          &num_candidates);
+  } else if (x_is_zero && z_is_zero) {
+    FindCandidatesInPlane(point.z(),
+                          point.x(),
+                          exemplar->rotate.axis.y,
+                          candidates,
+                          &num_candidates);
+  } else if (y_is_zero && z_is_zero) {
+    FindCandidatesInPlane(point.y(),
+                          point.z(),
+                          exemplar->rotate.axis.x,
+                          candidates,
+                          &num_candidates);
+  } else {
+    gfx::Vector3dF normal(exemplar->rotate.axis.x,
+                          exemplar->rotate.axis.y,
+                          exemplar->rotate.axis.z);
+    float normal_length = normal.Length();
+    if (normal_length == 0.f)
+      return;
+
+    normal.Scale(1.f / normal_length);
+
+    // First, find center of rotation.
+    gfx::Point3F origin;
+    gfx::Vector3dF to_point = point - origin;
+    gfx::Point3F center =
+        origin + gfx::ScaleVector3d(normal, gfx::DotProduct(to_point, normal));
+
+    // Now we need to find two vectors in the plane of rotation. One pointing
+    // towards point and another, perpendicular vector in the plane.
+    gfx::Vector3dF v1 = point - center;
+    float v1_length = v1.Length();
+    if (v1_length == 0.f)
+      return;
+
+    v1.Scale(1.f / v1_length);
+
+    gfx::Vector3dF v2 = gfx::CrossProduct(normal, v1);
+
+    // Now figure out where (1, 0, 0) and (0, 0, 1) project on the rotation
+    // plane.
+    gfx::Point3F px(1.f, 0.f, 0.f);
+    gfx::Vector3dF to_px = px - center;
+    gfx::Point3F px_projected =
+        px - gfx::ScaleVector3d(normal, gfx::DotProduct(to_px, normal));
+    gfx::Vector3dF vx = px_projected - origin;
+
+    gfx::Point3F pz(0.f, 0.f, 1.f);
+    gfx::Vector3dF to_pz = pz - center;
+    gfx::Point3F pz_projected =
+        pz - ScaleVector3d(normal, gfx::DotProduct(to_pz, normal));
+    gfx::Vector3dF vz = pz_projected - origin;
+
+    double phi_x = atan2(gfx::DotProduct(v2, vx), gfx::DotProduct(v1, vx));
+    double phi_z = atan2(gfx::DotProduct(v2, vz), gfx::DotProduct(v1, vz));
+
+    // NB: it is fine if the denominators here are zero and these values go to
+    // infinity; atan can handle it.
+    double tan_theta1 = SafeDivide(normal.y(), (normal.x() * normal.z()));
+    double tan_theta2 = SafeDivide(-normal.z(), (normal.x() * normal.y()));
+
+    candidates[0] = atan(tan_theta1) + phi_x;
+    candidates[1] = candidates[0] + M_PI;
+    candidates[2] = atan(tan_theta2) + phi_x;
+    candidates[3] = candidates[2] + M_PI;
+    candidates[4] = atan(-tan_theta1) + phi_z;
+    candidates[5] = candidates[4] + M_PI;
+  }
+
+  double min_theta = from ? DegreesToRadians(from->rotate.angle) : 0.0;
+  double max_theta = to ? DegreesToRadians(to->rotate.angle) : 0.0;
+
+  if (min_theta > max_theta)
+    std::swap(min_theta, max_theta);
+
+  gfx::Vector3dF axis(exemplar->rotate.axis.x,
+                      exemplar->rotate.axis.y,
+                      exemplar->rotate.axis.z);
+  axis.Scale(1.f / axis.Length());
+
+  for (int i = 0; i < num_candidates; ++i) {
+    double theta = candidates[i];
+    while (theta < min_theta)
+      theta += 2.0 * M_PI;
+    while (theta > max_theta)
+      theta -= 2.0 * M_PI;
+    if (theta < min_theta)
+      continue;
+
+    gfx::Transform rotation;
+    rotation.RotateAbout(axis, RadiansToDegrees(theta));
+    gfx::Point3F rotated = point;
+    rotation.TransformPoint(&rotated);
+
+    box->ExpandTo(rotated);
+  }
+}
+
 bool TransformOperation::BlendedBoundsForBox(const gfx::BoxF& box,
                                              const TransformOperation* from,
                                              const TransformOperation* to,
@@ -301,7 +481,23 @@ bool TransformOperation::BlendedBoundsForBox(const gfx::BoxF& box,
     case TransformOperation::TransformOperationIdentity:
       *bounds = box;
       return true;
-    case TransformOperation::TransformOperationRotate:
+    case TransformOperation::TransformOperationRotate: {
+      bool first_point = true;
+      for (int i = 0; i < 8; ++i) {
+        gfx::Point3F corner = box.origin();
+        corner += gfx::Vector3dF(i & 1 ? box.width() : 0.f,
+                                 i & 2 ? box.height() : 0.f,
+                                 i & 4 ? box.depth() : 0.f);
+        gfx::BoxF box_for_arc;
+        BoundingBoxForArc(corner, from, to, &box_for_arc);
+        if (first_point)
+          *bounds = box_for_arc;
+        else
+          bounds->Union(box_for_arc);
+        first_point = false;
+      }
+      return true;
+    }
     case TransformOperation::TransformOperationSkew:
     case TransformOperation::TransformOperationPerspective:
     case TransformOperation::TransformOperationMatrix: