Implement transform snapping for gfx::Transforms.

ui/gfx/transform_util.cc

Index: ui/gfx/transform_util.cc
diff --git a/ui/gfx/transform_util.cc b/ui/gfx/transform_util.cc
index 916b0b0bf8562294eed85196f60c4653cfb9a2b2..c83dfa59a2924660385354ae199f8a9321954aef 100644
--- a/ui/gfx/transform_util.cc
+++ b/ui/gfx/transform_util.cc
@@ -7,13 +7,25 @@
 #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 {
 
 namespace {
 
+// TODO(avallee): Move this somewhere appropriate in Skia.
+// Taken from SkMatrix44
+const float kNearIntEpsilon = 1e-8f;
+
+bool NearInteger(float f) {
+  f = std::abs(f);
+  return (std::abs(f - std::floor(f + 0.5f)) < kNearIntEpsilon);

[Ian Vollick, 2013/10/18 14:54:46]

We should be able to ditch this, I think. See below.

[avallee, 2013/10/21 15:15:44]

Done.

+}
+
 SkMScalar Length3(SkMScalar v[3]) {
   double vd[3] = {SkMScalarToDouble(v[0]), SkMScalarToDouble(v[1]),
                   SkMScalarToDouble(v[2])};
@@ -108,6 +120,152 @@ bool Normalize(SkMatrix44& m) {
   return true;
 }
 
+void BuildPerspectiveMatrix(SkMatrix44* matrix,
+                            const DecomposedTransform& decomp) {
+  matrix->setIdentity();
+
+  for (int i = 0; i < 4; i++)
+    matrix->setDouble(3, i, decomp.perspective[i]);
+}
+
+void BuildTranslationMatrix(SkMatrix44 * matrix,
+                            const DecomposedTransform& decomp) {
+  matrix->setTranslate(SkDoubleToMScalar(decomp.translate[0]),
+                       SkDoubleToMScalar(decomp.translate[1]),
+                       SkDoubleToMScalar(decomp.translate[2]));
+}
+
+void BuildRotationMatrix(SkMatrix44* matrix,
+                         const DecomposedTransform& decomp) {
+  double x = decomp.quaternion[0];
+  double y = decomp.quaternion[1];
+  double z = decomp.quaternion[2];
+  double w = decomp.quaternion[3];
+
+  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 BuildSnappedRotationMatrix(const DecomposedTransform& decomp) {
+  // Create snapped rotation.
+  SkMatrix44 rotation_matrix(SkMatrix44::kUninitialized_Constructor);
+  BuildRotationMatrix(&rotation_matrix, 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;
+}
+
+void BuildSkewMatrix(SkMatrix44* matrix, const DecomposedTransform& decomp) {
+  matrix->setIdentity();
+
+  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);
+  }
+}
+
+void BuildScaleMatrix(SkMatrix44* matrix, const DecomposedTransform& decomp) {
+  matrix->setIdentity();
+  matrix->setScale(SkDoubleToMScalar(decomp.scale[0]),
+                   SkDoubleToMScalar(decomp.scale[1]),
+                   SkDoubleToMScalar(decomp.scale[2]));
+}
+
+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 CheckViewportPointMapsWithinAPixel(const Point& point,
+                                          const Transform& transform_a,
+                                          const Transform& transform_b) {
+  Point3F point_a, point_b;
+  point_a = point_b = Point3F(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_a.TransformPoint(&point_a);
+  transform_b.TransformPoint(&point_b);
+
+  if (!(NearInteger(point_b.x()) && NearInteger(point_b.y()))) {

[Ian Vollick, 2013/10/18 14:54:46]

If we snap everything (not just rotation), then we will certainly map int points
to int points, so this would be unnecessary. I'm nervous about the behavior of
NearInteger with large floating point values. I think your second check below
will be sufficient if we go full-snapping.

[avallee, 2013/10/21 15:15:44]

Gone. Implemented full snapping, (skew snapped to identity, perspective
untouched).

+    // Integers should get mapped back into integer points.
+    return false;
+  }
+
+  if ((point_b - point_a).Length() > 1.0) {
+    // The changed distance should not be more than 1 pixel.
+    return false;
+  }
+  return true;
+}
+
+bool CheckTransformsMapsIntViewportWithinAPixel(const Rect& viewport,
+                                                const Transform& original,
+                                                const Transform& snapped) {
+
+  Transform original_inv(Transform::kSkipInitialization);
+  Transform snapped_inv(Transform::kSkipInitialization);
+  bool invertible = true;
+  invertible &= original.GetInverse(&original_inv);
+  invertible &= snapped.GetInverse(&snapped_inv);
+  DCHECK(invertible) << "Non-invertible transform, cannot snap.";
+
+  return CheckViewportPointMapsWithinAPixel(
+             viewport.origin(), original_inv, snapped_inv) &&
+         CheckViewportPointMapsWithinAPixel(
+             viewport.top_right(), original_inv, snapped_inv) &&
+         CheckViewportPointMapsWithinAPixel(
+             viewport.bottom_left(), original_inv, snapped_inv) &&
+         CheckViewportPointMapsWithinAPixel(
+             viewport.bottom_right(), original_inv, snapped_inv);
+}
+
 }  // namespace
 
 Transform GetScaleTransform(const Point& anchor, float scale) {
@@ -270,54 +428,56 @@ 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(SkMatrix44::kUninitialized_Constructor);
+  BuildPerspectiveMatrix(&perspective, decomp);
 
-  matrix.preTranslate(
-      decomp.translate[0], decomp.translate[1], decomp.translate[2]);
+  SkMatrix44 translation(SkMatrix44::kUninitialized_Constructor);
+  BuildTranslationMatrix(&translation, decomp);
 
-  SkMScalar x = decomp.quaternion[0];
-  SkMScalar y = decomp.quaternion[1];
-  SkMScalar z = decomp.quaternion[2];
-  SkMScalar w = decomp.quaternion[3];
+  SkMatrix44 rotation(SkMatrix44::kUninitialized_Constructor);
+  BuildRotationMatrix(&rotation, decomp);
 
-  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));
-
-  matrix.preConcat(rotation_matrix);
+  SkMatrix44 skew(SkMatrix44::kUninitialized_Constructor);
+  BuildSkewMatrix(&skew, decomp);
 
-  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
-  if (decomp.skew[2]) {
-    temp.set(1, 2, decomp.skew[2]);
-    matrix.preConcat(temp);
-  }
+  SkMatrix44 scale(SkMatrix44::kUninitialized_Constructor);
+  BuildScaleMatrix(&scale, decomp);
 
-  if (decomp.skew[1]) {
-    temp.set(1, 2, 0);
-    temp.set(0, 2, decomp.skew[1]);
-    matrix.preConcat(temp);
-  }
+  return ComposeTransform(perspective, translation, rotation, skew, scale);
+}
 
-  if (decomp.skew[0]) {
-    temp.set(0, 2, 0);
-    temp.set(0, 1, decomp.skew[0]);
-    matrix.preConcat(temp);
-  }
+bool SnapRotation(Transform* out,

[Ian Vollick, 2013/10/18 14:54:46]

s/SnapRotation/SnapTransform/ and snap everything but perspective, please.

[avallee, 2013/10/21 15:15:44]

Done.

+                  const Transform& transform,
+                  const Rect& viewport) {
+  DecomposedTransform decomp;
+  DecomposeTransform(&decomp, transform);
 
-  matrix.preScale(decomp.scale[0], decomp.scale[1], decomp.scale[2]);
+  SkMatrix44 rotation_matrix = BuildSnappedRotationMatrix(decomp);
 
-  Transform to_return;
-  to_return.matrix() = matrix;
-  return to_return;
+  // Rebuild matrices for other unchanged components.
+  SkMatrix44 perspective(SkMatrix44::kUninitialized_Constructor);
+  BuildPerspectiveMatrix(&perspective, decomp);
+
+  SkMatrix44 translation(SkMatrix44::kUninitialized_Constructor);
+  BuildTranslationMatrix(&translation, decomp);
+
+  SkMatrix44 skew(SkMatrix44::kUninitialized_Constructor);
+  BuildSkewMatrix(&skew, decomp);
+
+  SkMatrix44 scale(SkMatrix44::kUninitialized_Constructor);
+  BuildScaleMatrix(&scale, decomp);
+
+  // Get full tranform
+  Transform snapped =
+      ComposeTransform(perspective, translation, rotation_matrix, skew, scale);
+
+  // Verify that viewport is not moved unnaturally.
+  bool snappable =
+    CheckTransformsMapsIntViewportWithinAPixel(viewport, transform, snapped);
+  if (snappable) {
+    *out = snapped;
+  }
+  return snappable;
 }
 
 std::string DecomposedTransform::ToString() const {