Bug 30442 – Add helper methods to determine whether a transformation matrix is only scaled or translated

• Component: Platform
• Status: RESOLVED FIXED

[Jakob Petsovits]

In order to determine whether a rectangle is still a rectangle after some transformation, it's sufficient to check if the transformation matrix only consists of scale and translation. That's a useful check to have, as you can, for example, use that knowledge to follow an optimized code path or a generic one. I think that check should be a helper method in TransformationMatrix - so far, I made use of that kind of check twice.

I could also imagine checks for scale-only and translation-only to be useful for some cases, so I'm adding those too as they're very straightforward.

Patch attached below.

[Jakob Petsovits]

Created attachment 41290 [details]
Add helper methods to determine whether a transformation matrix is only scaled or translated.

The patch, as detailed above.

[Adam Treat]

Comment on attachment 41290 [details]
Add helper methods to determine whether a transformation matrix is only scaled or translated.

The method names are the only part I have a problem with.  Reading the patch it seems the identity matrix will return true for all of these methods.  'isScaleOnly' implies to me that an actual scale is set in the matrix.  Similarly for 'isTranslationOnly.'  And then 'isScaleAndTranslationOnly' is rather 'isIdentityAndOrScaleAndOrTranslation', but that is obviously too wordy.  Looking for right names...

[Jakob Petsovits]

Created attachment 41327 [details]
Add a mapsRectToRect() helper method to TransformationMatrix.

Incorporate feedback from smfr and manyoso, stripping down the patch to the bare minimum and tailoring it for the actual use case it is intended to cover (checking if a rect is still a rect after the transformation). The isScale() and isTranslation() methods that I included as "bonus extra" were removed, and the isScaleOrTranslation() method has been renamed to mapsRectToRect(), throwing out the 3D parts that are not used for mapRect() calculations.

Please review, thanks!

[Chris Marrin]

Comment on attachment 41327 [details]
Add a mapsRectToRect() helper method to TransformationMatrix.

> diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
> +    bool isScaleOnly() const
> +    {
> +        return (m12() == 0 && m13() == 0 && m14() == 0 &&
> +                m21() == 0 && m23() == 0 && m24() == 0 &&
> +                m31() == 0 && m32() == 0 && m34() == 0 &&
> +                m41() == 0 && m42() == 0 && m43() == 0);
> +    }

If your purpose is to be able to go into optimized code paths, you probably want to make sure m44 is 1 in isScaleOnly() since scaling the 'w' component will certainly cause any optimizations I can think of to fail. You should probably make sure the diagonals are not 0 for the same reason. 

> +
> +    bool isTranslationOnly() const
> +    {
> +        return (m11() == 1 && m12() == 0 && m13() == 0 && m14() == 0 &&
> +                m21() == 0 && m22() == 1 && m23() == 0 && m24() == 0 &&
> +                m31() == 0 && m32() == 0 && m33() == 1 && m34() == 0);
> +    }

Similar to above, you probably don't want to allow a value other than 1 in m44 here.

> +
> +    bool isScaleAndTranslationOnly() const
> +    {
> +        return (m12() == 0 && m13() == 0 && m14() == 0 &&
> +                m21() == 0 && m23() == 0 && m24() == 0 &&
> +                m31() == 0 && m32() == 0 && m34() == 0);
> +    }
> +

Same comments above apply here.

In general I'm a little uncomfortable with adding functions that have no immediate purpose. If you're thinking of optimizations on rectangle tests maybe it would be better to add some bounds checking methods that operate on a passed in FloatRect or FloatQuad and do the optimizations there.









> +    // Check if a 2D rectangle (IntRect or FloatRect) will still be a rectangle
> +    // after the transformation, i.e. it won't be rotated or skewed.
> +    bool mapsRectToRect() const
> +    {
> +        return (m_matrix[0][1] == 0 && m_matrix[0][3] == 0 &&
> +                m_matrix[1][0] == 0 && m_matrix[1][3] == 0);
> +    }
> +

But a rotated rectangle is still a rectangle. And it's very possible that a matrix that returned true from the above function would still not preserve rectangularity. For instance, something other than 1 in [3][3] would fail. It seems like you are trying to create a low-level function that serves a very specific purpose but it's not clear what that purpose is. If what you want is some optimized way to do bounds or intersection checking, perhaps it would be better to add that function to TransformationMatrix rather than a function like this.

[Chris Marrin]

Sorry about that last comment. Please ignore everything above the big space in the middle. Just the last part is relevant.

[Jakob Petsovits]

Created attachment 41383 [details]
Add a mapsRectToRect() helper method to TransformationMatrix (try 2)

> But a rotated rectangle is still a rectangle.

It's not a "Rect" (IntRect, FloatRect) though, so the function name is correct - while the comment and commit message were slightly off this way, I changed those to say "upright rectangle" instead of just "rectangle".

> And it's very possible that a
> matrix that returned true from the above function would still not preserve
> rectangularity. For instance, something other than 1 in [3][3] would fail.

Well, the corresponding code in multVecMatrix() (2D version, used by mapPoint(), which is in turn used by mapQuad(), and that's used by mapRect()) goes like this:

double w = m_matrix[3][3] + x * m_matrix[0][3] + y * m_matrix[1][3];
if (w != 1 && w != 0) {
    resultX /= w;
    resultY /= w;
}

Assuming that [0][3] and [1][3] are 0 (which my method ensures), w is not affected by the x and y coordinates, which means that similar input x/y values will result in similar output values as well. For IntRects and FloatRects, which feature similar x/y values for their edges, it means that even if [3][3] is something other than 1 it will still result in an upright {Int,Float}Rect. Personally I don't care whether I check for [3][3] or not, I just thought I'd match the semantics with the function name.

> It seems like you are trying to create a low-level function that serves a very
> specific purpose but it's not clear what that purpose is. If what you want is
> some optimized way to do bounds or intersection checking, perhaps it would be
> better to add that function to TransformationMatrix rather than a function like
> this.

Nope, it's not meant to do anything more lower-level than checking if I can avoid using (and cumbersome checking of) Quads.

[Eric Seidel (no email)]

Chris or Simon are your best reviewers here.

[Jakob Petsovits]

Created attachment 42062 [details]
Add FloatQuad::isRectilinear() to check whether it can be represented as FloatRect.

I had a talk with Simon and Chris on Skype, and it was determined that checking the matrix would not be the best approach for the intended goal (which can be paraphrased as "determine whether a transformation will return a rectilinear quad in order to enable optimizations"). Instead of checking the transformation itself, they suggested a new method FloatQuad::isRectilinear() to check the output of that transformation, which is a more generic approach and can be used in a couple more cases (e.g. also applies to rectangles turned by 90/270 degrees, and a few less common cases).

Here's the implementation; I tested with rectangles that are flipped and turned by 90, 180 and 5 degrees, the latter will return false for isRectilinear() while all of the others return true. Please review, hopefully this time it's the way to go :)

[Adam Barth]

Attachment 42062 [details] passed the style-queue

[Eric Seidel (no email)]

ping, Simon, Chris?

[WebKit Commit Bot]

Comment on attachment 42062 [details]
Add FloatQuad::isRectilinear() to check whether it can be represented as FloatRect.

Clearing flags on attachment: 42062

Committed r52115: <http://trac.webkit.org/changeset/52115>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.