[chromium] Implement hit-testing for impl-side input handling in accelerated compositor

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Shawn Singh]

To handle scrolling of any scrollable composited layer on the impl thread, we have to first recognize which scrollable layer was hit by the scrolling action.  The major part of that work is done in Sami's patch in https://bugs.webkit.org/show_bug.cgi?id=73350.

This patch takes a chunk of that patch that actually implemented hit-testing, and here we create a generic helper function that performs the hit testing.  This patch cleans up performance and correctness issues, and adds several unit tests.  I also manually tested it with a quick hack, and it seemed to work very nicely, even on poster circle, and 2011.beercamp.com.

Hit testing turns out to be beautifully simple with the already ordered renderSurfaceLayerList, and Dana's awesome iterator.

Originally I was concerned with a perspective w < 0 error.   In the original code, which inverse-projected the point to layer's local space, this was still an issue.  It turns out that by converting the layer's visibleLayerRect to screenSpace, issues with this are reduced, because the visibleLayerRect was already computed with correct clipping.   NOTE however, that the visibleLayerRect, in some pathological cases, might actually be larger than the actual visible portion itself, because of the clipping issue.  In those cases, we may successfully hit a layer even though the hit point was slightly outside the layer.   To fix this, we will have to change a lot of axis-aligned rects in the code to quads, and worse, to generalized polygons.  So unfortunately I don't think that is a fix we'll be making any time soon.

I tested this code manually, and it seems to work as desired.  Unit tests cover a few interesting edge cases, such as contentBounds != bounds.

[Shawn Singh]

vollick@:  I'm pretty sure that device scaling will need to be accounted for here.  We can discuss that when the time comes...

[Shawn Singh]

Created attachment 147254 [details]
Patch

[Shawn Singh]

Created attachment 147256 [details]
restructured to expose additional helper function

The inner portion of the hit testing could actually be used in other parts of Sami's patch in 73305, to reduce redundant code.

[Dana Jansens]

> It turns out that by converting the layer's visibleLayerRect to screenSpace, issues with this are reduced, because the visibleLayerRect was already computed with correct clipping.   NOTE however, that the visibleLayerRect, in some pathological cases, might actually be larger than the actual visible portion itself, because of the clipping issue.  In those cases, we may successfully hit a layer even though the hit point was slightly outside the layer.   To fix this, we will have to change a lot of axis-aligned rects in the code to quads, and worse, to generalized polygons.

What about non-axis aligned visibleLayerRects (45 degree rotation as a pathological case). Does that make much larger hit-area for the layer than its visible region? What about using quads to handle that situation? (no general polys)

[Shawn Singh]

(In reply to comment #4)
> > It turns out that by converting the layer's visibleLayerRect to screenSpace, issues with this are reduced, because the visibleLayerRect was already computed with correct clipping.   NOTE however, that the visibleLayerRect, in some pathological cases, might actually be larger than the actual visible portion itself, because of the clipping issue.  In those cases, we may successfully hit a layer even though the hit point was slightly outside the layer.   To fix this, we will have to change a lot of axis-aligned rects in the code to quads, and worse, to generalized polygons.
> 
> What about non-axis aligned visibleLayerRects (45 degree rotation as a pathological case). Does that make much larger hit-area for the layer than its visible region? What about using quads to handle that situation? (no general polys)

the hit testing is transforming from quads to quads (converting the visibleLayerRect to a quad first).   So the problem is inherently that visibleLayerRect is a rect.  until now, it was OK that visibleLayerRect represented only the enclosing rect of the visibleLayerQuad.

support for visibleLayerQuad will totally require general polys because of clipping by w < 0.

So yeah, I think this is the best we can do, and the improvements would need to happen outside of hit testing code.

[Dana Jansens]

(In reply to comment #5)
> (In reply to comment #4)
> > > It turns out that by converting the layer's visibleLayerRect to screenSpace, issues with this are reduced, because the visibleLayerRect was already computed with correct clipping.   NOTE however, that the visibleLayerRect, in some pathological cases, might actually be larger than the actual visible portion itself, because of the clipping issue.  In those cases, we may successfully hit a layer even though the hit point was slightly outside the layer.   To fix this, we will have to change a lot of axis-aligned rects in the code to quads, and worse, to generalized polygons.
> > 
> > What about non-axis aligned visibleLayerRects (45 degree rotation as a pathological case). Does that make much larger hit-area for the layer than its visible region? What about using quads to handle that situation? (no general polys)
> 
> the hit testing is transforming from quads to quads (converting the visibleLayerRect to a quad first).   So the problem is inherently that visibleLayerRect is a rect.  until now, it was OK that visibleLayerRect represented only the enclosing rect of the visibleLayerQuad.
> 
> support for visibleLayerQuad will totally require general polys because of clipping by w < 0.
> 
> So yeah, I think this is the best we can do, and the improvements would need to happen outside of hit testing code.

Ah okay we're using quads, thanks. That sounds good then.

[Adrienne Walker]

Whoa there.  visibleLayerRect is a *conservative* projection of visibility into content space.  visibleLayerRect is only going to be exact if the layer's screen space transformation results in the layer being axis-aligned with an integer scale.  That's not pathological, that's just a common transform case, and one that I think we need to support.

I think this can be way simpler than using quads.  You just need one extra step to test the scissor.  Scissoring is always done in surface space, so you can transform the point into the target surface of that layer and test against the surface's scissor directly.  That's it.

Once you've done the scissor test, you could do something similar to what you're doing now to see if it hits the layer itself.  Optionally, you could use the layer's full bounds instead of the visibleLayerRect and skip the content space conversion.

[Adrienne Walker]

(In reply to comment #7)

> I think this can be way simpler than using quads.  You just need one extra step to test the scissor.  Scissoring is always done in surface space, so you can transform the point into the target surface of that layer and test against the surface's scissor directly.  That's it.

Actually, you'd probably need to do this test for every parent surface up to the root that has a scissor, and not just the immediate target surface.  However, you could just maintain a stack of surfaces that you've gone through that have a clip as you iterated and test against all of those.

[Shawn Singh]

(In reply to comment #8)
> (In reply to comment #7)
> 
> > I think this can be way simpler than using quads.  You just need one extra step to test the scissor.  Scissoring is always done in surface space, so you can transform the point into the target surface of that layer and test against the surface's scissor directly.  That's it.
> 
> Actually, you'd probably need to do this test for every parent surface up to the root that has a scissor, and not just the immediate target surface.  However, you could just maintain a stack of surfaces that you've gone through that have a clip as you iterated and test against all of those.

Yeah, pathological was the wrong word =)

I'm a little unclear on your proposed algorithm -  wouldnt the scissor be potentially a LOT smaller than where we want to hit-test, because of damage tracking and partial swap?  Also, transforming the point by itself should be avoided if possible - because when we do reach the w < 0 case, there is no way "clip" a single point.   By transforming quads, we can interpolate betweeen the vertices and clip away the w < 0 portions, and still perform the hit testing.  If the entire quad is clipped away, we know it wouldnt succesfully be hit by any point anyway.  But if the point is clipped when inverse-projecting, I'm not convinced that w < 0 means that it shouldn't hit that quad.

Whatever algorithm we employ to do this correctly will probably imply that we computed the correct visibleLayerQuad.  Just an interesting observation =)

[James Robinson]

(In reply to comment #1)
> vollick@:  I'm pretty sure that device scaling will need to be accounted for here.  We can discuss that when the time comes...

I believe that this hit testing and all layer geometry information should be in logical pixels, not device pixels (https://trac.webkit.org/wiki/ScalesAndZooms).  Thus, if we make sure the point we are trying to hit is in logical pixels we're done.

[Shawn Singh]

Update:  I spoke with Enne offline.   Now I understood what Enne meant, I see its simple and brilliant =)  So I'll submit a new patch soon and 1-2 more unit tests.

[Shawn Singh]

Created attachment 147425 [details]
Avoids visibleLayerRect problems and quad limitations

This version avoids using visibleLayerRect, and instead correctly hit tests arbitrary geometry by making sure no ancestors clipped away the hit test point. Added another test that checks that multiple clipping ancestors works as desired. Also needed to update CCMathUtil to provide a projectPoint() function. Thanks to Enne for the insightful idea of how the hit testing should work, I think its pretty clean and friendly.

[Adrienne Walker]

Comment on attachment 147425 [details]
Avoids visibleLayerRect problems and quad limitations

View in context: https://bugs.webkit.org/attachment.cgi?id=147425&action=review

R=me.  So many tests! :)

> Source/WebCore/platform/graphics/chromium/cc/CCLayerTreeHostCommon.cpp:884
> +    // Note: its possible to compute the hit test in two equivalent ways:
> +    //    inverse-project the point into local space
> +    //    forward-transform the rect to screen space
> +    //
> +    // Its not obvious which one would perform better, or which one would be more robust
> +    // to w < 0 homogeneous clipping issues. For now, we simply opt for the inverse-project
> +    // approach.
> +    //

s/its/it's/g

Also, I don't know if you need this big block comment here.  There's different ways to implement nearly everything, but there's no need to necessarily document that.  If you want to explain your reasoning, it might make more sense as a commit message.

[Shawn Singh]

Thanks for the review!

(In reply to comment #13)
> 
> s/its/it's/g
> 

Apparently I need a personal style checker for this bad habit =)

> Also, I don't know if you need this big block comment here.  There's different ways to implement nearly everything, but there's no need to necessarily document that.  If you want to explain your reasoning, it might make more sense as a commit message.

OK will make it a commit message and remove it from the code.

[Shawn Singh]

Committed r120261: <http://trac.webkit.org/changeset/120261>

[Shawn Singh]

Reopening to attach new patch.

[Shawn Singh]

Created attachment 147446 [details]
Patch that landed