Implement transform snapping for gfx::Transforms.

Implement SnapTransform which takes a decomposed transform and viewport
and tries to nudge the rotation, scale and translation values. It tries applying the inverse of
the transform to the viewport. (Objects in this rect having the
transform applied will end up in the viewport) If the transform maps the
corners onto integer points and the corners are no more than 1 pixel
away we will return success and the decomposed transform with the new
rotation value.

R=vollick@chromium.org
BUG=280280

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

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

3 files changed, 343 insertions, 40 deletions

diff --git a/ui/gfx/transform_util.cc b/ui/gfx/transform_util.cc
index 916b0b0..655ce57 100644
--- a/ui/gfx/transform_util.cc
+++ b/ui/gfx/transform_util.cc
@@ -7,8 +7,11 @@
 #include <algorithm>
 #include <cmath>
 
+#include "base/logging.h"
 #include "base/strings/stringprintf.h"
 #include "ui/gfx/point.h"
+#include "ui/gfx/point3_f.h"
+#include "ui/gfx/rect.h"
 
 namespace gfx {
 
@@ -53,6 +56,10 @@ void Cross3(SkMScalar out[3], SkMScalar a[3], SkMScalar b[3]) {
   out[2] = z;
 }
 
+SkMScalar Round(SkMScalar n) {
+  return SkDoubleToMScalar(std::floor(SkMScalarToDouble(n) + 0.5));
+}
+
 // Taken from http://www.w3.org/TR/css3-transforms/.
 bool Slerp(SkMScalar out[4],
            const SkMScalar q1[4],
@@ -108,6 +115,163 @@ bool Normalize(SkMatrix44& m) {
   return true;
 }
 
+SkMatrix44 BuildPerspectiveMatrix(const DecomposedTransform& decomp) {
+  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
+
+  for (int i = 0; i < 4; i++)
+    matrix.setDouble(3, i, decomp.perspective[i]);
+  return matrix;
+}
+
+SkMatrix44 BuildTranslationMatrix(const DecomposedTransform& decomp) {
+  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
+  // Implicitly calls matrix.setIdentity()
+  matrix.setTranslate(SkDoubleToMScalar(decomp.translate[0]),
+                      SkDoubleToMScalar(decomp.translate[1]),
+                      SkDoubleToMScalar(decomp.translate[2]));
+  return matrix;
+}
+
+SkMatrix44 BuildSnappedTranslationMatrix(DecomposedTransform decomp) {
+  decomp.translate[0] = Round(decomp.translate[0]);
+  decomp.translate[1] = Round(decomp.translate[1]);
+  decomp.translate[2] = Round(decomp.translate[2]);
+  return BuildTranslationMatrix(decomp);
+}
+
+SkMatrix44 BuildRotationMatrix(const DecomposedTransform& decomp) {
+  double x = decomp.quaternion[0];
+  double y = decomp.quaternion[1];
+  double z = decomp.quaternion[2];
+  double w = decomp.quaternion[3];
+
+  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
+
+  // Implicitly calls matrix.setIdentity()
+  matrix.set3x3(1.0 - 2.0 * (y * y + z * z),
+                2.0 * (x * y + z * w),
+                2.0 * (x * z - y * w),
+                2.0 * (x * y - z * w),
+                1.0 - 2.0 * (x * x + z * z),
+                2.0 * (y * z + x * w),
+                2.0 * (x * z + y * w),
+                2.0 * (y * z - x * w),
+                1.0 - 2.0 * (x * x + y * y));
+  return matrix;
+}
+
+SkMatrix44 BuildSnappedRotationMatrix(const DecomposedTransform& decomp) {
+  // Create snapped rotation.
+  SkMatrix44 rotation_matrix = BuildRotationMatrix(decomp);
+  for (int i = 0; i < 3; ++i) {
+    for (int j = 0; j < 3; ++j) {
+      SkMScalar value = rotation_matrix.get(i, j);
+      // Snap values to -1, 0 or 1.
+      if (value < -0.5f) {
+        value = -1.0f;
+      } else if (value > 0.5f) {
+        value = 1.0f;
+      } else {
+        value = 0.0f;
+      }
+      rotation_matrix.set(i, j, value);
+    }
+  }
+  return rotation_matrix;
+}
+
+SkMatrix44 BuildSkewMatrix(const DecomposedTransform& decomp) {
+  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
+
+  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
+  if (decomp.skew[2]) {
+    temp.setDouble(1, 2, decomp.skew[2]);
+    matrix.preConcat(temp);
+  }
+
+  if (decomp.skew[1]) {
+    temp.setDouble(1, 2, 0);
+    temp.setDouble(0, 2, decomp.skew[1]);
+    matrix.preConcat(temp);
+  }
+
+  if (decomp.skew[0]) {
+    temp.setDouble(0, 2, 0);
+    temp.setDouble(0, 1, decomp.skew[0]);
+    matrix.preConcat(temp);
+  }
+  return matrix;
+}
+
+SkMatrix44 BuildScaleMatrix(const DecomposedTransform& decomp) {
+  SkMatrix44 matrix(SkMatrix44::kUninitialized_Constructor);
+  matrix.setScale(SkDoubleToMScalar(decomp.scale[0]),
+                  SkDoubleToMScalar(decomp.scale[1]),
+                  SkDoubleToMScalar(decomp.scale[2]));
+  return matrix;
+}
+
+SkMatrix44 BuildSnappedScaleMatrix(DecomposedTransform decomp) {
+  decomp.scale[0] = Round(decomp.scale[0]);
+  decomp.scale[1] = Round(decomp.scale[1]);
+  decomp.scale[2] = Round(decomp.scale[2]);
+  return BuildScaleMatrix(decomp);
+}
+
+Transform ComposeTransform(const SkMatrix44& perspective,
+                           const SkMatrix44& translation,
+                           const SkMatrix44& rotation,
+                           const SkMatrix44& skew,
+                           const SkMatrix44& scale) {
+  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
+
+  matrix.preConcat(perspective);
+  matrix.preConcat(translation);
+  matrix.preConcat(rotation);
+  matrix.preConcat(skew);
+  matrix.preConcat(scale);
+
+  Transform to_return;
+  to_return.matrix() = matrix;
+  return to_return;
+}
+
+bool CheckViewportPointMapsWithinOnePixel(const Point& point,
+                                          const Transform& transform) {
+  Point3F point_original(point);
+  Point3F point_transformed(point);
+
+  // Can't use TransformRect here since it would give us the axis-aligned
+  // bounding rect of the 4 points in the initial rectable which is not what we
+  // want.
+  transform.TransformPoint(&point_transformed);
+
+  if ((point_transformed - point_original).Length() > 1.f) {
+    // The changed distance should not be more than 1 pixel.
+    return false;
+  }
+  return true;
+}
+
+bool CheckTransformsMapsIntViewportWithinOnePixel(const Rect& viewport,
+                                                  const Transform& original,
+                                                  const Transform& snapped) {
+
+  Transform original_inv(Transform::kSkipInitialization);
+  bool invertible = true;
+  invertible &= original.GetInverse(&original_inv);
+  DCHECK(invertible) << "Non-invertible transform, cannot snap.";
+
+  Transform combined = snapped * original_inv;
+
+  return CheckViewportPointMapsWithinOnePixel(viewport.origin(), combined) &&
+         CheckViewportPointMapsWithinOnePixel(viewport.top_right(), combined) &&
+         CheckViewportPointMapsWithinOnePixel(viewport.bottom_left(),
+                                              combined) &&
+         CheckViewportPointMapsWithinOnePixel(viewport.bottom_right(),
+                                              combined);
+}
+
 }  // namespace
 
 Transform GetScaleTransform(const Point& anchor, float scale) {
@@ -270,54 +434,42 @@ bool DecomposeTransform(DecomposedTransform* decomp,
 
 // Taken from http://www.w3.org/TR/css3-transforms/.
 Transform ComposeTransform(const DecomposedTransform& decomp) {
-  SkMatrix44 matrix(SkMatrix44::kIdentity_Constructor);
-  for (int i = 0; i < 4; i++)
-    matrix.set(3, i, decomp.perspective[i]);
+  SkMatrix44 perspective = BuildPerspectiveMatrix(decomp);
+  SkMatrix44 translation = BuildTranslationMatrix(decomp);
+  SkMatrix44 rotation = BuildRotationMatrix(decomp);
+  SkMatrix44 skew = BuildSkewMatrix(decomp);
+  SkMatrix44 scale = BuildScaleMatrix(decomp);
 
-  matrix.preTranslate(
-      decomp.translate[0], decomp.translate[1], decomp.translate[2]);
+  return ComposeTransform(perspective, translation, rotation, skew, scale);
+}
 
-  SkMScalar x = decomp.quaternion[0];
-  SkMScalar y = decomp.quaternion[1];
-  SkMScalar z = decomp.quaternion[2];
-  SkMScalar w = decomp.quaternion[3];
+bool SnapTransform(Transform* out,
+                   const Transform& transform,
+                   const Rect& viewport) {
+  DecomposedTransform decomp;
+  DecomposeTransform(&decomp, transform);
 
-  SkMatrix44 rotation_matrix(SkMatrix44::kUninitialized_Constructor);
-  rotation_matrix.set3x3(1.0 - 2.0 * (y * y + z * z),
-                         2.0 * (x * y + z * w),
-                         2.0 * (x * z - y * w),
-                         2.0 * (x * y - z * w),
-                         1.0 - 2.0 * (x * x + z * z),
-                         2.0 * (y * z + x * w),
-                         2.0 * (x * z + y * w),
-                         2.0 * (y * z - x * w),
-                         1.0 - 2.0 * (x * x + y * y));
+  SkMatrix44 rotation_matrix = BuildSnappedRotationMatrix(decomp);
+  SkMatrix44 translation = BuildSnappedTranslationMatrix(decomp);
+  SkMatrix44 scale = BuildSnappedScaleMatrix(decomp);
 
-  matrix.preConcat(rotation_matrix);
+  // Rebuild matrices for other unchanged components.
+  SkMatrix44 perspective = BuildPerspectiveMatrix(decomp);
 
-  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
-  if (decomp.skew[2]) {
-    temp.set(1, 2, decomp.skew[2]);
-    matrix.preConcat(temp);
-  }
+  // Completely ignore the skew.
+  SkMatrix44 skew(SkMatrix44::kIdentity_Constructor);
 
-  if (decomp.skew[1]) {
-    temp.set(1, 2, 0);
-    temp.set(0, 2, decomp.skew[1]);
-    matrix.preConcat(temp);
-  }
+  // Get full tranform
+  Transform snapped =
+      ComposeTransform(perspective, translation, rotation_matrix, skew, scale);
 
-  if (decomp.skew[0]) {
-    temp.set(0, 2, 0);
-    temp.set(0, 1, decomp.skew[0]);
-    matrix.preConcat(temp);
+  // Verify that viewport is not moved unnaturally.
+  bool snappable =
+    CheckTransformsMapsIntViewportWithinOnePixel(viewport, transform, snapped);
+  if (snappable) {
+    *out = snapped;
   }
-
-  matrix.preScale(decomp.scale[0], decomp.scale[1], decomp.scale[2]);
-
-  Transform to_return;
-  to_return.matrix() = matrix;
-  return to_return;
+  return snappable;
 }
 
 std::string DecomposedTransform::ToString() const {
diff --git a/ui/gfx/transform_util.h b/ui/gfx/transform_util.h
index 07bf0d5..a77ded2 100644
--- a/ui/gfx/transform_util.h
+++ b/ui/gfx/transform_util.h
@@ -11,6 +11,7 @@
 namespace gfx {
 
 class Point;
+class Rect;
 
 // Returns a scale transform at |anchor| point.
 GFX_EXPORT Transform GetScaleTransform(const Point& anchor, float scale);
@@ -53,6 +54,10 @@ GFX_EXPORT bool DecomposeTransform(DecomposedTransform* out,
 // http://www.w3.org/TR/css3-3d-transforms/.
 GFX_EXPORT Transform ComposeTransform(const DecomposedTransform& decomp);
 
+GFX_EXPORT bool SnapTransform(Transform* out,
+                              const Transform& transform,
+                              const Rect& viewport);
+
 }  // namespace gfx
 
 #endif  // UI_GFX_TRANSFORM_UTIL_H_
diff --git a/ui/gfx/transform_util_unittest.cc b/ui/gfx/transform_util_unittest.cc
index 94195c2..41bfc40 100644
--- a/ui/gfx/transform_util_unittest.cc
+++ b/ui/gfx/transform_util_unittest.cc
@@ -6,6 +6,8 @@
 
 #include "testing/gtest/include/gtest/gtest.h"
 #include "ui/gfx/point.h"
+#include "ui/gfx/point3_f.h"
+#include "ui/gfx/rect.h"
 
 namespace gfx {
 namespace {
@@ -30,5 +32,149 @@ TEST(TransformUtilTest, GetScaleTransform) {
   }
 }
 
+TEST(TransformUtilTest, SnapRotation) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+  transform.RotateAboutZAxis(89.99);
+
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_TRUE(snapped) << "Viewport should snap for this rotation.";
+}
+
+TEST(TransformUtilTest, SnapRotationDistantViewport) {
+  const int kOffset = 5000;
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+  transform.RotateAboutZAxis(89.99);
+
+  Rect viewport(kOffset, kOffset, 1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_FALSE(snapped) << "Distant viewport shouldn't snap by more than 1px.";
+}
+
+TEST(TransformUtilTest, NoSnapRotation) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+  const int kOffset = 5000;
+
+  transform.RotateAboutZAxis(89.9);
+
+  Rect viewport(kOffset, kOffset, 1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_FALSE(snapped) << "Viewport should not snap for this rotation.";
+}
+
+// Translations should always be snappable, the most we would move is 0.5
+// pixels towards either direction to the nearest value in each component.
+TEST(TransformUtilTest, SnapTranslation) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+  transform.Translate3d(
+      SkDoubleToMScalar(1.01), SkDoubleToMScalar(1.99), SkDoubleToMScalar(3.0));
+
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_TRUE(snapped) << "Viewport should snap for this translation.";
+}
+
+TEST(TransformUtilTest, SnapTranslationDistantViewport) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+  const int kOffset = 5000;
+
+  transform.Translate3d(
+      SkDoubleToMScalar(1.01), SkDoubleToMScalar(1.99), SkDoubleToMScalar(3.0));
+
+  Rect viewport(kOffset, kOffset, 1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_TRUE(snapped)
+      << "Distant viewport should still snap by less than 1px.";
+}
+
+TEST(TransformUtilTest, SnapScale) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+  transform.Scale3d(SkDoubleToMScalar(5.0),
+                    SkDoubleToMScalar(2.00001),
+                    SkDoubleToMScalar(1.0));
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_TRUE(snapped) << "Viewport should snap for this scaling.";
+}
+
+TEST(TransformUtilTest, NoSnapScale) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+  transform.Scale3d(
+    SkDoubleToMScalar(5.0), SkDoubleToMScalar(2.1), SkDoubleToMScalar(1.0));
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+
+  EXPECT_FALSE(snapped) << "Viewport shouldn't snap for this scaling.";
+}
+
+TEST(TransformUtilTest, SnapCompositeTransform) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+  transform.Translate3d(SkDoubleToMScalar(30.5), SkDoubleToMScalar(20.0),
+                        SkDoubleToMScalar(10.1));
+  transform.RotateAboutZAxis(89.99);
+  transform.Scale3d(SkDoubleToMScalar(1.0),
+                    SkDoubleToMScalar(3.00001),
+                    SkDoubleToMScalar(2.0));
+
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+  ASSERT_TRUE(snapped) << "Viewport should snap all components.";
+
+  Point3F point;
+
+  point = Point3F(viewport.origin());
+  result.TransformPoint(&point);
+  EXPECT_EQ(Point3F(31.f, 20.f, 10.f), point) << "Transformed origin";
+
+  point = Point3F(viewport.top_right());
+  result.TransformPoint(&point);
+  EXPECT_EQ(Point3F(31.f, 1940.f, 10.f), point) << "Transformed top-right";
+
+  point = Point3F(viewport.bottom_left());
+  result.TransformPoint(&point);
+  EXPECT_EQ(Point3F(-3569.f, 20.f, 10.f), point) << "Transformed bottom-left";
+
+  point = Point3F(viewport.bottom_right());
+  result.TransformPoint(&point);
+  EXPECT_EQ(Point3F(-3569.f, 1940.f, 10.f), point)
+      << "Transformed bottom-right";
+}
+
+TEST(TransformUtilTest, NoSnapSkewedCompositeTransform) {
+  Transform result(Transform::kSkipInitialization);
+  Transform transform;
+
+
+  transform.RotateAboutZAxis(89.99);
+  transform.Scale3d(SkDoubleToMScalar(1.0),
+                    SkDoubleToMScalar(3.00001),
+                    SkDoubleToMScalar(2.0));
+  transform.Translate3d(SkDoubleToMScalar(30.5), SkDoubleToMScalar(20.0),
+                        SkDoubleToMScalar(10.1));
+  transform.SkewX(20.0);
+  Rect viewport(1920, 1200);
+  bool snapped = SnapTransform(&result, transform, viewport);
+  EXPECT_FALSE(snapped) << "Skewed viewport should not snap.";
+}
+
 }  // namespace
 }  // namespace gfx