Bug 80806 - [chromium] Need to clip to homogeneous w=0 plane when applying transforms.
Summary: [chromium] Need to clip to homogeneous w=0 plane when applying transforms.
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Shawn Singh
URL:
Keywords:
Depends on: 83299
Blocks: 74147 79136 83082 83217
  Show dependency treegraph
 
Reported: 2012-03-11 20:47 PDT by Shawn Singh
Modified: 2012-04-05 13:14 PDT (History)
10 users (show)

See Also:


Attachments
Patch (41.15 KB, patch)
2012-04-02 20:11 PDT, Shawn Singh
no flags Details | Formatted Diff | Diff
Should compile on linux now (41.21 KB, patch)
2012-04-03 10:31 PDT, Shawn Singh
no flags Details | Formatted Diff | Diff
Addressed reviewers comments (41.50 KB, patch)
2012-04-03 17:38 PDT, Shawn Singh
no flags Details | Formatted Diff | Diff
Addressed second round of comments (42.20 KB, patch)
2012-04-04 16:26 PDT, Shawn Singh
no flags Details | Formatted Diff | Diff
Patch for landing (42.38 KB, patch)
2012-04-05 10:03 PDT, Shawn Singh
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Shawn Singh 2012-03-11 20:47:25 PDT
WebCore TransformationMatrix does not properly handle un-projecting from a perspective transform, for surfaces where at least one of its vertices is behind the camera.

But it is not as simple as "handling this case properly" because there really isn't a good way to handle it.  (refer to http://dl.acm.org/citation.cfm?id=807398 to understand why)  The real need is to clip geometry that goes behind the camera so that we never try to un-project vertices that are behind the camera.  However, this can create triangles, pentagons, or other general polygons depending on what we need to clip.

This patch will first implement clipping in chromium, to get some rendering bugs fixed (for example, http://code.google.com/p/chromium/issues/detail?id=105100 among others).  Later we will try to migrate the correct clipping to WebCore to fix problems for hit testing bugs (for example, https://bugs.webkit.org/show_bug.cgi?id=79136 among others).

One question that might come up is "why doesn't this affect rendering for Safari?" -- the answer is that Safari, as far as I know, doesn't use projectQuad in its compositor.  But the hit testing bugs do indeed affect both Safari and Chromium.
Comment 1 Shawn Singh 2012-03-30 19:04:07 PDT
Correction to above comment: The bug can occur on any usage of mapRect, mapQuad, or projectQuad, if the transform has a perspective component and layers go behind the projection plane.  My earlier thought about it going wrong only when un-projecting is actually just subset of the entire bug.

The clipping solution is still necessary and that explanation given in the previous comment still applies.
Comment 2 Shawn Singh 2012-03-31 12:43:19 PDT
I just want to be crystal clear about the problem statement before posting another complicated update.

Some matrices with perspective projection component may cause homogeneous coordinate w to become negative.  According to the math, when this happens the point may appear to project validly to the visible portion of the screen in cartesian coordinates, but it actually should not be visible to the screen.

The correct way to handle this is to clip the geometry after applying the transform in homogeneous coordinates, but before divide-by-w is applied.  Specifically, we should be clipping to the w=0 plane (w = epsilon is fine to avoid divide-by-zero).

Note:

1. Any usage of mapRect / mapQuad / projectQuad / mapPoint will suffer from this problem.

2. Clipping like this will cause polygons other than quads, too.  In most cases we can tolerate it because we only care about the rect enclosing the vertices, but of course we can't do this when drawing the clipped geometry.
Comment 3 Shawn Singh 2012-03-31 12:50:27 PDT
David and Enne: this needs your attention and feedback.  I tried to give clear context of the bug in comment #2 above.  Thanks in advance!

Status:
I have a fix for this bug which works nicely - but only when bypassing the antialiasing code path (i.e. forcing CCTileDrawQuad to return false for all the AA booleans).

Of course we need to fix the anti-aliasing code path, too - in LRC::drawTileQuad().  As I understand, that code maps the quad to device space to determine correct AA inflation in pixel units, and then it maps back so that it can issue a drawTexturedQuad call.  There are a few issues that come up:

(a) why do we flatten the deviceTransform to 2d?   For layers that have perspective, won't that actually be incorrect when we try to inflate the edges for AA and then transform back?  (i.e. the amount we inflate the near part of the edge and far part of the edge should indeed be different, but in 2d they won't be)

(b) was there a reason we used mapQuad on the inverse (when transforming back to local quad space)?  I'm pretty sure it should be projectQuad.  Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad, but when there is perspective, the unprojection is correct.

(c) even better: why couldn't we just issue a drawTexturedQuad call using the identity transform and the device-space quad?  We could avoid computing an inverse and another transform mapping anyway.

(d) and finally, the act of transforming to device coordinates in the first place is where this clipping bug shows up.  So even if we address the first 3 points, we still have to implement proper clipping here.

I can think of 2 possible solutions.  Please let me know what you think:

Solution 1: if there is perspective component in the quadTransform, we could skip the antialiasing code path, at least until we have a better fix.

Solution 2: I think we can simultaneously get correct clipping and AA by transforming each edge separately, clipping the edges first, then doing the AA inflation, and finally reconstructing a new device-space CCTileDrawQuad from the clipped edges (or, if it was clipped to be a pentagon, construct two quads).  Then we would use the identityTransform in drawTexturedQuad.  Would this work?
Comment 4 Shawn Singh 2012-03-31 13:55:13 PDT
Solution 3:  if there is any possible way to determine the AA inflation without transforming the quad (or, without drawing the transformed-and-then-inverse-transformed quad), we could do that too.  The GPU does properly clip w<0 items.
Comment 5 Adrienne Walker 2012-04-02 11:49:47 PDT
(In reply to comment #3)

> Of course we need to fix the anti-aliasing code path, too - in LRC::drawTileQuad().  As I understand, that code maps the quad to device space to determine correct AA inflation in pixel units, and then it maps back so that it can issue a drawTexturedQuad call.  There are a few issues that come up:
> 
> (a) why do we flatten the deviceTransform to 2d?   For layers that have perspective, won't that actually be incorrect when we try to inflate the edges for AA and then transform back?  (i.e. the amount we inflate the near part of the edge and far part of the edge should indeed be different, but in 2d they won't be)

We are inflating the bounds in 2d device space so that we can guarantee that particular pixels in this post-projection space get coverage from this quad.  In this space, the amount we inflate the edges should be identical since pixels are distributed evenly in device space.  When you do the inverse projection, the inflation for points further away will end up being larger.

> (b) was there a reason we used mapQuad on the inverse (when transforming back to local quad space)?  I'm pretty sure it should be projectQuad.  Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad, but when there is perspective, the unprojection is correct.

It's cheaper and just as correct in this case.

> I can think of 2 possible solutions.  Please let me know what you think:
> 
> Solution 1: if there is perspective component in the quadTransform, we could skip the antialiasing code path, at least until we have a better fix.

This seems like a heavy-handed solution.  Can't you detect this particular issue in a more fine-grained way? I think these sorts of transforms are not the common case.

> Solution 2: I think we can simultaneously get correct clipping and AA by transforming each edge separately, clipping the edges first, then doing the AA inflation, and finally reconstructing a new device-space CCTileDrawQuad from the clipped edges (or, if it was clipped to be a pentagon, construct two quads).  Then we would use the identityTransform in drawTexturedQuad.  Would this work?

No.  This would result in non-perspective correct texture coordinates when interpolating in the fragment shader.  In other words, texture coordinates cannot be linearly interpolated in post-projection space and the fragment shader would use the wrong values.
Comment 6 Shawn Singh 2012-04-02 12:23:46 PDT
(In reply to comment #5)
> (In reply to comment #3)
> 
> > Of course we need to fix the anti-aliasing code path, too - in LRC::drawTileQuad().  As I understand, that code maps the quad to device space to determine correct AA inflation in pixel units, and then it maps back so that it can issue a drawTexturedQuad call.  There are a few issues that come up:
> > 
> > (a) why do we flatten the deviceTransform to 2d?   For layers that have perspective, won't that actually be incorrect when we try to inflate the edges for AA and then transform back?  (i.e. the amount we inflate the near part of the edge and far part of the edge should indeed be different, but in 2d they won't be)
> 
> We are inflating the bounds in 2d device space so that we can guarantee that particular pixels in this post-projection space get coverage from this quad.  In this space, the amount we inflate the edges should be identical since pixels are distributed evenly in device space.  When you do the inverse projection, the inflation for points further away will end up being larger.
> 

I think I already understood that we have to inflate for AA in device space.  That wasn't my question... I was asking why we remove 3-d portions of the transform itself.  Even if there are 3d portions of the transform, mapRect / mapQuad will correclty project it down to 2d.

> > (b) was there a reason we used mapQuad on the inverse (when transforming back to local quad space)?  I'm pretty sure it should be projectQuad.  Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad, but when there is perspective, the unprojection is correct.
> 
> It's cheaper and just as correct in this case.
> 


I'm not convinced of that... are you suggesting that inverse.projectQuad and inverse.mapRect are the same?


> > I can think of 2 possible solutions.  Please let me know what you think:
> > 
> > Solution 1: if there is perspective component in the quadTransform, we could skip the antialiasing code path, at least until we have a better fix.
> 
> This seems like a heavy-handed solution.  Can't you detect this particular issue in a more fine-grained way? I think these sorts of transforms are not the common case.

I agree this isn't the correct solution.  detecting this issue in a more fine-grained way could be possible, but if we go that far, we might as well consider doing proper AA in those fine-grained cases, too.  I think getting correct AA in all cases should still be possible.

> 
> > Solution 2: I think we can simultaneously get correct clipping and AA by transforming each edge separately, clipping the edges first, then doing the AA inflation, and finally reconstructing a new device-space CCTileDrawQuad from the clipped edges (or, if it was clipped to be a pentagon, construct two quads).  Then we would use the identityTransform in drawTexturedQuad.  Would this work?
> 
> No.  This would result in non-perspective correct texture coordinates when interpolating in the fragment shader.  In other words, texture coordinates cannot be linearly interpolated in post-projection space and the fragment shader would use the wrong values.

yeah, good catch.  I'll come back with some better proposed solutions.
Comment 7 Adrienne Walker 2012-04-02 13:04:15 PDT
(In reply to comment #6)

> I think I already understood that we have to inflate for AA in device space.  That wasn't my question... I was asking why we remove 3-d portions of the transform itself.  Even if there are 3d portions of the transform, mapRect / mapQuad will correclty project it down to 2d.

That's exactly it.  You've projected into 2d and modified the quad, and now you want to figure out what quad in the original space transformed with the draw transform will result in that modified quad.

My understanding here is that if you use the inverse of the 3d transform, you will end up with an incorrect result because you're transforming (x, y, 0), and z=0 is not actually correct for this point.
 
> > > (b) was there a reason we used mapQuad on the inverse (when transforming back to local quad space)?  I'm pretty sure it should be projectQuad.  Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad, but when there is perspective, the unprojection is correct.
> > 
> > It's cheaper and just as correct in this case.
>
> I'm not convinced of that... are you suggesting that inverse.projectQuad and inverse.mapRect are the same?

Quoting from yourself: "Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad"
Comment 8 Shawn Singh 2012-04-02 13:32:06 PDT
(In reply to comment #7)
> (In reply to comment #6)
> 
> > I think I already understood that we have to inflate for AA in device space.  That wasn't my question... I was asking why we remove 3-d portions of the transform itself.  Even if there are 3d portions of the transform, mapRect / mapQuad will correclty project it down to 2d.
> 
> That's exactly it.  You've projected into 2d and modified the quad, and now you want to figure out what quad in the original space transformed with the draw transform will result in that modified quad.

I'm referring to http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/chromium/LayerRendererChromium.cpp#L656

This removes the 3d stuff from the transform before we even figure out what the quad would look like in device space.  So for example, if there was a perspective transform, it wouldn't be considered when transforming to device space...


> 
> My understanding here is that if you use the inverse of the 3d transform, you will end up with an incorrect result because you're transforming (x, y, 0), and z=0 is not actually correct for this point.
> 
> > > > (b) was there a reason we used mapQuad on the inverse (when transforming back to local quad space)?  I'm pretty sure it should be projectQuad.  Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad, but when there is perspective, the unprojection is correct.
> > > 
> > > It's cheaper and just as correct in this case.
> >
> > I'm not convinced of that... are you suggesting that inverse.projectQuad and inverse.mapRect are the same?
> 
> Quoting from yourself: "Inverse + projectQuad is an unprojection; when there is no perspective component in the original matrix, it behaves equivalent to inverse + mapQuad"

Yes, when there is no perspective, inverse.projectQuad behaves equivalently to inverse.mapRect.

When there is perspective, I don't think mapRect is correct.  I think we should be using projectQuad so that both non-perspective and perspective cases are covered.
Comment 9 Adrienne Walker 2012-04-02 14:11:09 PDT
(In reply to comment #8)

> I'm referring to http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/chromium/LayerRendererChromium.cpp#L656
> 
> This removes the 3d stuff from the transform before we even figure out what the quad would look like in device space.  So for example, if there was a perspective transform, it wouldn't be considered when transforming to device space...

I don't understand why this is a problem. The "3d part" of the transform doesn't affect the final x and y components of the quad in device space, only the z component.  In other words, for all values of quad:

transform.to2dTransform().mapQuad(quad) == transform.mapQuad(quad)
Comment 10 Shawn Singh 2012-04-02 15:33:26 PDT
(In reply to comment #9)
> (In reply to comment #8)
> 
> > I'm referring to http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/chromium/LayerRendererChromium.cpp#L656
> > 
> > This removes the 3d stuff from the transform before we even figure out what the quad would look like in device space.  So for example, if there was a perspective transform, it wouldn't be considered when transforming to device space...
> 
> I don't understand why this is a problem. The "3d part" of the transform doesn't affect the final x and y components of the quad in device space, only the z component.  In other words, for all values of quad:
> 
> transform.to2dTransform().mapQuad(quad) == transform.mapQuad(quad)

OK, I see the problem.  I created https://bugs.webkit.org/show_bug.cgi?id=82956 to discuss it further.  This bug can stay focused on the clipping+AA problem.
Comment 11 Shawn Singh 2012-04-02 20:08:21 PDT
I have a patch ready for review, coming in just one moment.  Some notes:

(1) Tested on unit tests and compositing/ subset of layout tests.  Also tested manually on apple's VR demo, the css space cube demo, and reduce test case (all can be found from http://code.google.com/p/chromium/issues/detail?id=105100)

I will run all layout tests before submitting next version of patch, but this patch is working correctly and ready for review.


(2) please feel free to ask me for details about the math.


(3) I added unit tests for calculateVisibleRect, but I did not add unit testing for CCMathUtil.  The code is covered by existing unit tests, in particular the new tests for calculateVisibleLayerRect.  Please let me know if you still prefer that we add unit tests here.
Comment 12 Shawn Singh 2012-04-02 20:11:39 PDT
Created attachment 135264 [details]
Patch
Comment 13 WebKit Review Bot 2012-04-02 21:03:28 PDT
Comment on attachment 135264 [details]
Patch

Attachment 135264 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/12317046
Comment 14 Victor Robison 2012-04-03 08:55:42 PDT
Build failed.  Looks like either FloatPoint3d.h (and possibly other files) are missing or you are missing the include path.
Comment 15 Shawn Singh 2012-04-03 10:31:49 PDT
Created attachment 135357 [details]
Should compile on linux now
Comment 16 Dana Jansens 2012-04-03 10:41:01 PDT
Comment on attachment 135357 [details]
Should compile on linux now

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

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.h:50
> +    static FloatRect projectClippedRect(const TransformationMatrix&, const FloatQuad&);

projectRect() should take a rect as input. The function should be projectQuad, or the input should be a rect, IMO.
Comment 17 Shawn Singh 2012-04-03 10:50:10 PDT
(In reply to comment #16)
> (From update of attachment 135357 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=135357&action=review
> 
> > Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.h:50
> > +    static FloatRect projectClippedRect(const TransformationMatrix&, const FloatQuad&);
> 
> projectRect() should take a rect as input. The function should be projectQuad, or the input should be a rect, IMO.

OK, good idea.  I'll make the input arg a FloatRect.
Comment 18 Vangelis Kokkevis 2012-04-03 13:15:57 PDT
Comment on attachment 135357 [details]
Should compile on linux now

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

Nice! I would like at some point to move this inside TransformationMatrix but it can be done in a separate patch.  I agree with other reviewers that turning off multisampling for clipped layers is a bit heavy-handed.

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:155
> +    // This function omputes the 2d FloatRect that encloses the clipped quad. Note that

typo: computes

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:190
> +    // Step 2: Collect the list of vertices that represent the clipped quad.

Since the common case will require no clipping, maybe check if any of the points need to be clipped before calling computeClippedVerticesForTransformedQuad which creates a <vector> etc. ?  Also, adding the identityOrTranslation() test at the top should help a lot.

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:208
> +    Vector<HomogeneousCoordinate> verticesOfClippedQuad;

Same comments as above.  We should try to not regress the performance of the common case.

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:218
> +    // FIXME: this version of mapQuad is missing a useful optimization, isIdentityOrTranslation(), that is available only in TransformationMatrix.cpp

isIdentityOrTranslation() is a public method of TransformationMatrix
Comment 19 Shawn Singh 2012-04-03 13:49:41 PDT
Thanks for the reviews!  I'll submit a new patch soon

(In reply to comment #18)
> (From update of attachment 135357 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=135357&action=review
> 
> Nice! I would like at some point to move this inside TransformationMatrix but it can be done in a separate patch.  I agree with other reviewers that turning off multisampling for clipped layers is a bit heavy-handed.
> 

I should have mentioned that Enne and I decided it was OK to skip AA for clipped layers.  It is still less heavy-handed than skipping AA for all layers that have perspective.

Just let me know either way. I'm willing to put more time into getting AA to work, but if we can't figure out how to cleanly convert the AA inflation to local quad space, so that we can modify the original un-clipped quad, then we may need to resort to tesselation of the clipped polygon which will get ugly. =)
Comment 20 Vangelis Kokkevis 2012-04-03 14:37:44 PDT
(In reply to comment #19)
> Thanks for the reviews!  I'll submit a new patch soon
> 
> (In reply to comment #18)
> > (From update of attachment 135357 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=135357&action=review
> > 
> > Nice! I would like at some point to move this inside TransformationMatrix but it can be done in a separate patch.  I agree with other reviewers that turning off multisampling for clipped layers is a bit heavy-handed.
> > 
> 
> I should have mentioned that Enne and I decided it was OK to skip AA for clipped layers.  It is still less heavy-handed than skipping AA for all layers that have perspective.
> 
> Just let me know either way. I'm willing to put more time into getting AA to work, but if we can't figure out how to cleanly convert the AA inflation to local quad space, so that we can modify the original un-clipped quad, then we may need to resort to tesselation of the clipped polygon which will get ugly. =)

Ah, ok.  David may be able the help fixing up the AA shader for that case, possibly in a followup patch.
Comment 21 Shawn Singh 2012-04-03 17:38:55 PDT
Created attachment 135468 [details]
Addressed reviewers comments

IAlso rearranged some code so that there is less redundancy and fluff.  Ran all unit tests and layout tests on osx, no obvious regressions.
Comment 22 Adrienne Walker 2012-04-04 14:47:20 PDT
Comment on attachment 135468 [details]
Addressed reviewers comments

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

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:62
> +    double x, y, z, w;

One line per declaration, please.

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:184
> +    Vector<HomogeneousCoordinate> verticesOfClippedQuad;
> +    computeClippedVerticesForTransformedQuad(h1, h2, h3, h4, verticesOfClippedQuad);

Perhaps this is premature optimization, but can we not hit the allocator during mapClippedRect? Could computeClippedVerticesForTransformedQuad just return the enclosing rect instead of the list of vertices?

> Source/WebKit/chromium/tests/CCLayerTreeHostCommonTest.cpp:1148
> +    layerToSurfaceTransform.translate3d(-161.111111111111, 0, 0);
> +    expected = IntRect(IntPoint(50, -50), IntSize(100, 200)); // The right half of the layer's bounding rect.
> +    actual = CCLayerTreeHostCommon::calculateVisibleRect(targetSurfaceRect, layerContentRect, layerToSurfaceTransform);
> +    EXPECT_INT_RECT_EQ(expected, actual);

This seems a little flimsy, since you're using approximate floating point math and then going back to int.  Can you pick better numbers here that come out more evenly? Or, am I missing something that makes it more reliable than it looks at first blush?

> Source/WebKit/chromium/tests/CCLayerTreeHostCommonTest.cpp:1181
> +    // but actually they are not. The visibleRect needs to be properly clipped by the
> +    // w = 0 plane in homogeneous coordinates before converting to cartesian coordinates.

Can you assert that this happening in this test by calling a CCMath function?
Comment 23 Vangelis Kokkevis 2012-04-04 15:09:57 PDT
Comment on attachment 135468 [details]
Addressed reviewers comments

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

>> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:184
>> +    computeClippedVerticesForTransformedQuad(h1, h2, h3, h4, verticesOfClippedQuad);
> 
> Perhaps this is premature optimization, but can we not hit the allocator during mapClippedRect? Could computeClippedVerticesForTransformedQuad just return the enclosing rect instead of the list of vertices?

Enne makes a good point here. By combining computeClippedVerticesForTransformedQuad with computeEnclosingRectOfClippedQuad into a single function you can also easily replace the <vector> by a straight static array (since there is an upper limit on the number of points that result from this operation).

> Source/WebCore/platform/graphics/chromium/cc/CCOcclusionTracker.cpp:288
> +    IntRect unoccludedRect = enclosingIntRect(CCMathUtil::projectQuad(contentSpaceTransform.inverse(), FloatQuad(FloatRect(shrunkRect)), clamped).boundingBox());

Is there a reason for not using projectClippedRect() here ?

> Source/WebCore/platform/graphics/chromium/cc/CCOcclusionTracker.cpp:289
>      if (clamped)

nit:  clamped -> clipped (for consistency) ?
Comment 24 Shawn Singh 2012-04-04 15:18:59 PDT
(In reply to comment #23)
> 
> > Source/WebCore/platform/graphics/chromium/cc/CCOcclusionTracker.cpp:288
> > +    IntRect unoccludedRect = enclosingIntRect(CCMathUtil::projectQuad(contentSpaceTransform.inverse(), FloatQuad(FloatRect(shrunkRect)), clamped).boundingBox());
> 
> Is there a reason for not using projectClippedRect() here ?

No reason except that I preferred to do it in a separate step.  It will help isolate regressions and get things debugged more easily if something goes wrong.  We had already filed https://bugs.webkit.org/show_bug.cgi?id=83217 for this.  Does that sound OK?

But I will make all the other changes that you and Enne suggested.  It should compact things nicely.  Later, if we really need to compute the clipped quad, we can salvage it from this old patch.
Comment 25 Shawn Singh 2012-04-04 16:26:14 PDT
Created attachment 135711 [details]
Addressed second round of comments

also added Enne's requested assert to the un-projection case, too; still passes tests with no obvious regressions
Comment 26 Adrienne Walker 2012-04-04 16:58:37 PDT
Comment on attachment 135711 [details]
Addressed second round of comments

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

A few more math questions.  It's been a while since I've looked at this sort of thing, so maybe having a little bit more explanation would help me feel more comfortable.  :)

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:105
> +    //   p.w = 0 = (1-t) * h1.w + (t) * h2.w

Forgive my misunderstanding, but shouldn't you be solving for p.w = epsilon?

> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:119
> +    double w = 0.00001; // or any positive non-zero small epsilon

Given that you multiply x,y,z by 1/w, doesn't the choice of w here greatly affect the cartesian coordinates you get?
Comment 27 Shawn Singh 2012-04-04 17:57:53 PDT
(In reply to comment #26)
> (From update of attachment 135711 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=135711&action=review
> 
> A few more math questions.  It's been a while since I've looked at this sort of thing, so maybe having a little bit more explanation would help me feel more comfortable.  :)
> 
> > Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:105
> > +    //   p.w = 0 = (1-t) * h1.w + (t) * h2.w
> 
> Forgive my misunderstanding, but shouldn't you be solving for p.w = epsilon?

For all intents and purposes, epsilon == 0.  So where we can use 0 without divide-by-zero risks, its probably best to use it.

> 
> > Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:119
> > +    double w = 0.00001; // or any positive non-zero small epsilon
> 
> Given that you multiply x,y,z by 1/w, doesn't the choice of w here greatly affect the cartesian coordinates you get?

short answer:

Its a choice between the two evil solutions.  I feel epsilon is the lesser evil approach.  The other approach has much higher risk of overflow.

long answer:

The other solution is to set w=0, and implement a special case that forces x/w to be signed infinity when w==0.  If you prefer that, I'm OK with it.  Personally I think that's worse evil than epsilon.  The problem is that its a little too easy to accidentally cause overflow in those cases.  It is so natural to use the code assuming it maintains valid values, and as soon as something is clipped and set to INT_MAX, the next operation is very risky to cause overflow and suddenly everything goes kaput.

For the epsilon approach, the tradeoff favors incorrect results to reduce the risk of overflow.  We can think of the "normal case" and "pathological case":

normal case:  x/epsilon will cause extremely large values for the projected 2d value of x.  This is exactly what we want; we want to emulate x/w approaching infinity (or negative infinity), without having to deal with NaN or inf IEEE floating point idiosyncrasies.  This means that the x-coordinate is far offscreen somewhere, and that is what we want, but the risk of overflow is far less.

pathological case:  if x is very small, or if the viewport is extremely large, then perhaps x/w does not actually go offscreen like it should.  The net result of this is that we will still see some incorrect clipping.  I believe this should only occur in rare cases where the content itself has specified very large or very small units for their scene.
Comment 28 Shawn Singh 2012-04-04 18:01:08 PDT
correction about viewport.  it should say "if the viewport encompasses a large region of the projection plane".  not referring to large number of pixels.
Comment 29 Adrienne Walker 2012-04-04 18:11:05 PDT
Comment on attachment 135711 [details]
Addressed second round of comments

Gotcha.  I understand what's going on here, now; that sounds totally reasonable.  Thanks for the explanation.  :)
Comment 30 Shawn Singh 2012-04-04 18:22:40 PDT
(In reply to comment #29)
> (From update of attachment 135711 [details])
> Gotcha.  I understand what's going on here, now; that sounds totally reasonable.  Thanks for the explanation.  :)

Sure - thanks a bunch for reviewing.   I'll land it tomorrow morning.

Just for interest, I quickly tried the clamp-to-infinity method, and it seems like we are already easily reaching overflow problems already, and the patch breaks.  I had to use "int_max / 100" before it stopped showing artifacts.
Comment 31 Vangelis Kokkevis 2012-04-04 22:16:36 PDT
Comment on attachment 135711 [details]
Addressed second round of comments

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

>>> Source/WebCore/platform/graphics/chromium/cc/CCMathUtil.cpp:119
>>> +    double w = 0.00001; // or any positive non-zero small epsilon
>> 
>> Given that you multiply x,y,z by 1/w, doesn't the choice of w here greatly affect the cartesian coordinates you get?
> 
> short answer:
> 
> Its a choice between the two evil solutions.  I feel epsilon is the lesser evil approach.  The other approach has much higher risk of overflow.
> 
> long answer:
> 
> The other solution is to set w=0, and implement a special case that forces x/w to be signed infinity when w==0.  If you prefer that, I'm OK with it.  Personally I think that's worse evil than epsilon.  The problem is that its a little too easy to accidentally cause overflow in those cases.  It is so natural to use the code assuming it maintains valid values, and as soon as something is clipped and set to INT_MAX, the next operation is very risky to cause overflow and suddenly everything goes kaput.
> 
> For the epsilon approach, the tradeoff favors incorrect results to reduce the risk of overflow.  We can think of the "normal case" and "pathological case":
> 
> normal case:  x/epsilon will cause extremely large values for the projected 2d value of x.  This is exactly what we want; we want to emulate x/w approaching infinity (or negative infinity), without having to deal with NaN or inf IEEE floating point idiosyncrasies.  This means that the x-coordinate is far offscreen somewhere, and that is what we want, but the risk of overflow is far less.
> 
> pathological case:  if x is very small, or if the viewport is extremely large, then perhaps x/w does not actually go offscreen like it should.  The net result of this is that we will still see some incorrect clipping.  I believe this should only occur in rare cases where the content itself has specified very large or very small units for their scene.

Would it be more correct to solve for w = epsilon so that x,y,z and w are all consistent? This would mean finding a point that's within epsilon of the image plane.
Comment 32 Shawn Singh 2012-04-05 09:44:19 PDT
OK, Enne was suggesting that, too, so I'll go ahead and land it with that change (after re-testing of course).
Comment 33 Shawn Singh 2012-04-05 10:03:11 PDT
Created attachment 135844 [details]
Patch for landing
Comment 34 WebKit Review Bot 2012-04-05 11:24:34 PDT
Comment on attachment 135844 [details]
Patch for landing

Clearing flags on attachment: 135844

Committed r113341: <http://trac.webkit.org/changeset/113341>
Comment 35 WebKit Review Bot 2012-04-05 11:24:41 PDT
All reviewed patches have been landed.  Closing bug.
Comment 36 Shawn Singh 2012-04-05 13:14:40 PDT
Committed r113364: <http://trac.webkit.org/changeset/113364>