added fix that deals with precision in layer sorter

Fixed a bug in the layer sorter to deal with layers that are very close together.  Due to numeric precision issues, the sorter would produce wrong results for some transformations.  The patch checks to see if all tests that compare the edges of the two layers result in significant precision loss.  If all tests cause significant precision loss the sorter now declares that it is impossible to tell which layer should be drawn first and falls back to document order for those layers.  This produces a consistent result across frames for layers that are close together and eliminated flickering artifacts on the test scene.

A unit test is included.  The test takes two layers (very close together) and tests to see what order the layer-sorter produces.  The correct sorted order of the layers is the same as document order.  Without this patch the layer-sorter puts them in the wrong order.

BUG=61666
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=176178

[enne (OOO), 2012-11-01 20:08:55]

Just FYI, unless you "publish and mail comments" (even with a blank comment),
nobody gets email that you've created this issue, so it's unlikely to get looked
at unless somebody looks at their "My Issues" page and sees it.

You can use git cl upload --send-mail (along with specifying a reviewer) to send
one during upload.  You can also just hit the publish and mail comments and send
a blank comment once you've specified CC/reviewers as you see fit.

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc
File cc/layer_sorter.cc (right):

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode125
cc/layer_sorter.cc:125: // if we have 2-sided quads that are very close together
then we draw them
style nit: cc code doesn't obey the Chromium 80 col limit yet in general, but if
you're going to wrap comments, at least wrap them at 80 col.

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode130
cc/layer_sorter.cc:130: float absmax = fmax(fabs(zb), fabs(za));
style nit: Can you match the variable style in this file, i.e. absmax => absMax
and absdif => absDiff?

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode132
cc/layer_sorter.cc:132: if (absdif > 1e-4 * absmax)
Can you pull this constant out into a named variable at the top of the file,
with some comment justification about why you picked this value?

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc
File cc/layer_sorter_unittest.cc (right):

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc#ne...
cc/layer_sorter_unittest.cc:292: layerList.push_back(layer1.get());
Does this test pass before this patch? I thought positive Z was out of the page,
so painter's algorithm would paint lower Z values before higher ones.

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc#ne...
cc/layer_sorter_unittest.cc:305: EXPECT_FALSE(1.0f == 999999f);
Missing a period here. Also, maybe better to actually just get the value out of
layer1->drawTransform().m43() than to repeat the literals?

[danakj, 2012-11-01 20:15:33]

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc
File cc/layer_sorter.cc (right):

http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode118
cc/layer_sorter.cc:118: // flag to tell us if we've computed an accurate (w.r.t.
floating point) answer
All comments should be complete sentences with capital letters and punctuation.

[whunt, 2012-11-01 22:34:07]

On 2012/11/01 20:08:55, enne wrote:
> Just FYI, unless you "publish and mail comments" (even with a blank comment),
> nobody gets email that you've created this issue, so it's unlikely to get
looked
> at unless somebody looks at their "My Issues" page and sees it.
> 
Thanks!
> You can use git cl upload --send-mail (along with specifying a reviewer) to
send
> one during upload.  You can also just hit the publish and mail comments and
send
> a blank comment once you've specified CC/reviewers as you see fit.
> 
> http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc
> File cc/layer_sorter.cc (right):
> 
> http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode125
> cc/layer_sorter.cc:125: // if we have 2-sided quads that are very close
together
> then we draw them
> style nit: cc code doesn't obey the Chromium 80 col limit yet in general, but
if
> you're going to wrap comments, at least wrap them at 80 col.
Done.
> 
> http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode130
> cc/layer_sorter.cc:130: float absmax = fmax(fabs(zb), fabs(za));
> style nit: Can you match the variable style in this file, i.e. absmax =>
absMax
> and absdif => absDiff?
> 
Done.

> 
http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode132
> cc/layer_sorter.cc:132: if (absdif > 1e-4 * absmax)
> Can you pull this constant out into a named variable at the top of the file,
> with some comment justification about why you picked this value?
> 
Done and commented.
> http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc
> File cc/layer_sorter_unittest.cc (right):
> 
>
http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc#ne...
> cc/layer_sorter_unittest.cc:292: layerList.push_back(layer1.get());
> Does this test pass before this patch? I thought positive Z was out of the
page,
> so painter's algorithm would paint lower Z values before higher ones.
> 
I believe you are correct, I also believe the sorter sorts in reverse order (for
painting).  The sorter putouts layers in order of increasing Z (I went ahead and
verified that again).
>
http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter_unittest.cc#ne...
> cc/layer_sorter_unittest.cc:305: EXPECT_FALSE(1.0f == 999999f);
> Missing a period here. Also, maybe better to actually just get the value out
of
> layer1->drawTransform().m43() than to repeat the literals?

Fixed, with the f suffix it shouldn't matter unless the compiler is buggy. 
Given that we use 2 transforms, I'm pretty certain that .m43() is not 0.999999f
anymore anyway.

[enne (OOO), 2012-11-01 22:55:23]

lgtm

(In other words, feel free to land this after addressing the nits below and
uploading a new patch.)

Also, when responding to comments, could you respond via reply on the comments
themselves, rather than inline in the text reply? For example, if I go to
http://codereview.chromium.org/11362024/diff/1/cc/layer_sorter.cc#newcode125, I
just see my comment but not your "Done." reply.

http://codereview.chromium.org/11362024/diff/1003/cc/layer_sorter_unittest.cc
File cc/layer_sorter_unittest.cc (right):

http://codereview.chromium.org/11362024/diff/1003/cc/layer_sorter_unittest.cc...
cc/layer_sorter_unittest.cc:311: EXPECT_FALSE(1.0f == 0.999999f);
As I think about it, I'm not sure this is worth asserting.  Can you just remove
this line?

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc
File cc/layer_sorter.cc (right):

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc#newcode28
cc/layer_sorter.cc:28: const float LAYER_EPSILON = 1e-4f;
style nit: kLayerEpsilon

[shawnsingh, 2012-11-01 23:03:57]

I checked the first version of this patch against my list of 3d CSS demos. 
seems to me this doesn't regress any other sorting flickering issues, but it
does indeed reduce the flickering on the sonnetRotate demo on issue 61666.   I
noticed there still is some flickering, but like Warren says, I agree that it's
essentially a content issue beyond this patch.

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc
File cc/layer_sorter.cc (right):

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc#newcode128
cc/layer_sorter.cc:128: bool accurate = false;
Could we move the computation of "accurate" and associated comments into a
simple trivial helper function?

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc#newcode141
cc/layer_sorter.cc:141: float absMax = fmax(fabs(zb), fabs(za));
We probably should be consistent in our usage of fabsf() versus fabs()

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc#newcode143
cc/layer_sorter.cc:143: if (absDif > LAYER_EPSILON * absMax)
I'm still not understanding exactly how this checks ulp-level precision?  this
seems like a relative threshold based on "within percent accuracy" where
LAYER_EPSILON is that percentage.  I'm pretty sure that's not exactly the same
as ulp-thresholding.  Can we discuss it offline briefly?

That said, it might be acceptable to use relative thresholding here than
ulp-level thresholding.

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter_unittest.cc
File cc/layer_sorter_unittest.cc (right):

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter_unittest.cc...
cc/layer_sorter_unittest.cc:274: // Layer 1 should occur of layer 2 in paint. 
However, due to numeric
"of" --> is this a typo?   do we mean "before" or "after" here?

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter_unittest.cc...
cc/layer_sorter_unittest.cc:275: // issues in the sorter, it will puts the
layers in the wrong order
puts --> put

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter_unittest.cc...
cc/layer_sorter_unittest.cc:276: // in some situations.  Here we test a patch
that results in in
"in in" --> "in"

[danakj, 2012-11-01 23:06:34]

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc
File cc/layer_sorter.cc (right):

http://codereview.chromium.org/11362024/diff/2014/cc/layer_sorter.cc#newcode141
cc/layer_sorter.cc:141: float absMax = fmax(fabs(zb), fabs(za));
On 2012/11/01 23:03:57, shawnsingh wrote:
> We probably should be consistent in our usage of fabsf() versus fabs()

Why aren't we using std::abs() from <cmath> ?

[shawnsingh, 2012-11-02 01:30:07]

Follow-up about relative error thresholding versus ulp thresholding (i.e.
integer comparison of float values) - 

http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

After refreshing myself on the difference, its clear that relative error
threshold is more than good enough for this code.

[enne (OOO), 2012-11-02 19:21:54]

One other minor thing.  Since the description becomes the commit message, could
you edit it so that it has one short line of description followed by more
paragraphs of explanation if needed?

I find that easier to skim, but it also makes git tools and things like
tools/my_review.py behave a lot better when there's a single short line as the
first description line.

See also:
http://tbaggery.com/2008/04/19/a-note-about-git-commit-messages.html

[shawnsingh, 2012-11-03 03:54:48]

LGTM except you might have meant to run "git cl try" from the command line
rather than where the upload script was asking you for the patch title =)

Did you locally check the layout tests that were failing, too?  I'm guessing git
cl try will still fail those tests since the patch hasn't changed much, if
that's true then we'll have to find out why and address it before committing
this.

[enne (OOO), 2012-11-21 01:56:29]

Were you planning to commit this at some point?

[whunt, 2012-11-21 20:29:48]

On 2012/11/21 01:56:29, enne wrote:
> Were you planning to commit this at some point?

I am.  Apparently the patch causes one layout test to fail so I need to
investigate that before checking in.  It has been de-prioritized until quad
coalescing has been completed and checked in for the code yellow.  I'll get back
to it after that.

[enne (OOO), 2012-11-26 14:41:23]

Ok, thanks! I was just going through stale codereviews in my list to see if this
was being blocked by review.  (I apologize if that last comment came off as
curt; it wasn't intended.)

[commit-bot: I haz the power, 2013-01-08 00:21:02]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/whunt@chromium.org/11362024/25001

[commit-bot: I haz the power, 2013-01-10 19:25:26]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/whunt@chromium.org/11362024/25001

[commit-bot: I haz the power, 2013-01-10 22:31:14]

Change committed as 176178