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 9bb3bbcbcfbf261b17b84d306f823f52ea6a8c3e..f59a7231066c646c3f35f4543f9bfd27f15183a9 100644
--- a/ui/gfx/transform_util.cc
+++ b/ui/gfx/transform_util.cc
@@ -7,12 +7,23 @@
 #include <algorithm>
 #include <cmath>
 
+#include "base/logging.h"
 #include "ui/gfx/point.h"
+#include "ui/gfx/point3_f.h"
+#include "ui/gfx/rect_f.h"
 
 namespace gfx {
 
 namespace {
 
+// TODO(avallee): Move this somewhere appropriate in Skia.
+// Taken from SkMatrix44
+const float kNearIntEpsilon = 1e-8;
+
+bool NearInteger(float f) {
+  return (std::abs(f - std::round(f)) < kNearIntEpsilon);
+}
+
 SkMScalar Length3(SkMScalar v[3]) {
   return std::sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]);
 }
@@ -104,6 +115,112 @@ 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));
+}
+
+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 CheckTansformPoint(const PointF& point,

[Ian Vollick, 2013/09/14 23:45:31]

nit: typo, but even still, it would be nice if the fn name mentioned what in
particular it was checking. InverseTransformsMapIntPointToWithinAPixel maybe?
It's a mouthful, but it's a bit more meaningful.

[avallee, 2013/10/15 19:22:48]

Done.

+                        const Transform& transform_a,
+                        const Transform& transform_b) {
+  Point3F point_a, point_b;
+  point_a = point_b = Point3F(point.x(), point.y(), 0.f);

[Ian Vollick, 2013/09/14 23:45:31]

nit: Use the Point3F ctor that takes a PointF.

[avallee, 2013/10/15 19:22:48]

Done.

+
+  // 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.
+  bool invertible = true;
+  invertible &= transform_a.TransformPointReverse(&point_a);
+  invertible &= transform_b.TransformPointReverse(&point_b);

[Ian Vollick, 2013/09/14 23:45:31]

It's a bummer that we recompute the inverse of these matrices 4 times for each
corner. Please pass the inverted matrices as parameters. Also, should the point
param be a Point rather than a PointF?

[avallee, 2013/10/15 19:22:48]

Done.

+  DCHECK(invertible) << "Non-invertible transform, cannot snap.";
+
+  if (!(NearInteger(point_b.x()) && NearInteger(point_b.y()))) {
+    // 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;
+}
+
 }  // namespace
 
 Transform GetScaleTransform(const Point& anchor, float scale) {
@@ -266,54 +383,74 @@ 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(DecomposedTransform* out,
+                  const DecomposedTransform& decomp,
+                  const Transform& transform,

[Ian Vollick, 2013/09/14 23:45:31]

This is not the signature I expected. I was hoping for
bool SnapTransform(Transform* out, const Transform& unsnapped, const Rect&
viewport);

I don't think it would be too much of a stretch from what you have here to snap
the rest of the components and I think it would be more useful.

[avallee, 2013/10/15 19:22:48]

Done.

I don't think you want other snapping yet, right?

+                  const RectF& viewport) {
+
+  // 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);
+    }
   }

[Ian Vollick, 2013/09/14 23:45:31]

Please make a BuildSnappedRotationMatrix helper (and similar helpers for
translation, etc).

[avallee, 2013/10/15 19:22:48]

Added Snapped rotation unless we also want snapped translation helper right
away. However, only snapped rotation would be used here in SnapRotation.

 
-  matrix.preScale(decomp.scale[0], decomp.scale[1], decomp.scale[2]);
+  // Rebuild matrices for other unchanged components.
+  SkMatrix44 perspective(SkMatrix44::kUninitialized_Constructor);
+  BuildPerspectiveMatrix(&perspective, decomp);
 
-  Transform to_return;
-  to_return.matrix() = matrix;
-  return to_return;
+  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 =
+      CheckTansformPoint(viewport.origin(), transform, snapped) &&
+      CheckTansformPoint(viewport.top_right(), transform, snapped) &&
+      CheckTansformPoint(viewport.bottom_left(), transform, snapped) &&
+      CheckTansformPoint(viewport.bottom_right(), transform, snapped);
+  if (snappable) {
+    DecomposeTransform(out, snapped);
+  }
+  return snappable;
 }
 
 }  // namespace ui