Implement transform snapping for gfx::Transforms.

ui/gfx/transform_util.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/transform_util.h"
 
 #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])};
   return SkDoubleToMScalar(
       std::sqrt(vd[0] * vd[0] + vd[1] * vd[1] + vd[2] * vd[2]));
 }
 
 void Scale3(SkMScalar v[3], SkMScalar scale) {
   for (int i = 0; i < 3; ++i)
     v[i] *= scale;
@@ skipping 74 matching lines @@
     return false;
 
   SkMScalar scale = 1.0 / m.get(3, 3);
   for (int i = 0; i < 4; i++)
     for (int j = 0; j < 4; j++)
       m.set(i, j, m.get(i, j) * scale);
 
   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) {
   Transform transform;
   transform.Translate(anchor.x() * (1 - scale),
                       anchor.y() * (1 - scale));
   transform.Scale(scale, scale);
   return transform;
 }
 
@@ skipping 142 matching lines @@
   if (row[0][2] > row[2][0])
       decomp->quaternion[1] = -decomp->quaternion[1];
   if (row[1][0] > row[0][1])
       decomp->quaternion[2] = -decomp->quaternion[2];
 
   return true;
 }
 
 // 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));
+  SkMatrix44 skew(SkMatrix44::kUninitialized_Constructor);
+  BuildSkewMatrix(&skew, decomp);
 
-  matrix.preConcat(rotation_matrix);
+  SkMatrix44 scale(SkMatrix44::kUninitialized_Constructor);
+  BuildScaleMatrix(&scale, decomp);
 
-  SkMatrix44 temp(SkMatrix44::kIdentity_Constructor);
-  if (decomp.skew[2]) {
-    temp.set(1, 2, decomp.skew[2]);
-    matrix.preConcat(temp);
+  return ComposeTransform(perspective, translation, rotation, skew, scale);
+}
+
+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);
+
+  SkMatrix44 rotation_matrix = BuildSnappedRotationMatrix(decomp);
+
+  // 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;
   }
-
-  if (decomp.skew[1]) {
-    temp.set(1, 2, 0);
-    temp.set(0, 2, decomp.skew[1]);
-    matrix.preConcat(temp);
-  }
-
-  if (decomp.skew[0]) {
-    temp.set(0, 2, 0);
-    temp.set(0, 1, decomp.skew[0]);
-    matrix.preConcat(temp);
-  }
-
-  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 {
   return base::StringPrintf(
       "translate: %+0.4f %+0.4f %+0.4f\n"
       "scale: %+0.4f %+0.4f %+0.4f\n"
       "skew: %+0.4f %+0.4f %+0.4f\n"
       "perspective: %+0.4f %+0.4f %+0.4f %+0.4f\n"
       "quaternion: %+0.4f %+0.4f %+0.4f %+0.4f\n",
       translate[0],
       translate[1],
       translate[2],
       scale[0],
       scale[1],
       scale[2],
       skew[0],
       skew[1],
       skew[2],
       perspective[0],
       perspective[1],
       perspective[2],
       perspective[3],
       quaternion[0],
       quaternion[1],
       quaternion[2],
       quaternion[3]);
 }
 
 }  // namespace ui