Bug 88972

Summary: [chromium] Implement hit-testing for impl-side input handling in accelerated compositor
Product: WebKit Reporter: Shawn Singh <shawnsingh>
Component: Layout and RenderingAssignee: Shawn Singh <shawnsingh>
Status: RESOLVED FIXED    
Severity: Normal CC: cc-bugs, danakj, enne, jamesr, skyostil, vangelis, vollick, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 73350    
Attachments:
Description Flags
Patch
none
restructured to expose additional helper function
none
Avoids visibleLayerRect problems and quad limitations
none
Patch that landed none

Description Shawn Singh 2012-06-13 00:32:26 PDT
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.
Comment 1 Shawn Singh 2012-06-13 00:43:18 PDT
vollick@:  I'm pretty sure that device scaling will need to be accounted for here.  We can discuss that when the time comes...
Comment 2 Shawn Singh 2012-06-13 00:43:59 PDT
Created attachment 147254 [details]
Patch
Comment 3 Shawn Singh 2012-06-13 01:05:37 PDT
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.
Comment 4 Dana Jansens 2012-06-13 08:15:16 PDT
> 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)
Comment 5 Shawn Singh 2012-06-13 10:02:01 PDT
(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.
Comment 6 Dana Jansens 2012-06-13 10:04:09 PDT
(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.
Comment 7 Adrienne Walker 2012-06-13 10:12:14 PDT
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.
Comment 8 Adrienne Walker 2012-06-13 10:19:12 PDT
(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.
Comment 9 Shawn Singh 2012-06-13 10:55:33 PDT
(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 =)
Comment 10 James Robinson 2012-06-13 11:01:50 PDT
(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.
Comment 11 Shawn Singh 2012-06-13 11:06:49 PDT
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.
Comment 12 Shawn Singh 2012-06-13 15:29:32 PDT
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.
Comment 13 Adrienne Walker 2012-06-13 16:31:19 PDT
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.
Comment 14 Shawn Singh 2012-06-13 16:45:48 PDT
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.
Comment 15 Shawn Singh 2012-06-13 17:05:27 PDT
Committed r120261: <http://trac.webkit.org/changeset/120261>
Comment 16 Shawn Singh 2012-06-13 17:06:30 PDT
Reopening to attach new patch.
Comment 17 Shawn Singh 2012-06-13 17:06:33 PDT
Created attachment 147446 [details]
Patch that landed