Optimized box border side painting order

Optimized box border side painting order

We are currently drawing border sides in a predefined/hard-coded order: top, bottom, left, right.
This is limiting the applicability of overdraw as a corner seam avoidance technique (drawing an
expanded side shape while relying on adjacent sides overdrawing unwanted portions) because the
hard-coded side order is in many cases suboptimal (e.g. a double border side painted after a solid
side cannot be used for overdraw as it doesn't fully cover the mitre area).

The current approach is also inefficient when it comes to translucent borders: translucent sides
may draw after opaque sides (preventing overdraw) and we create one transparency layer for each
common-color edge set - but these layers are drawn/clipped independently, resulting in seaming
artifacts.

The CL removes this predefined order assumption and introduces a general side order optimizer with
the following rules:

* if needed, side opacity is always applied via (nested) transparency layers
* more opaque sides are painted after less opaque sides
* for equal opacity, more "solid" sides are painted after less solid sides (solid style after
  double style, etc.)
* for equal opacity and style, try painting in non-adjacent order

These rules are all geared towards maximizing the applicability of overdraw: if opaque color/style
sides are always painted last, then mitres are not required for prior sides.

The handling of translucent border sides is improved in a couple of ways:

1) instead of creating one transparency layer per unique translucent color, we now only create
one transparency layer per unique alpha/opacity

2) using the layer nesting algorithm described in BoxBorderPainter::paintOpacityGroup() allows us
to always draw sides using opaque paints => translucent sides are now effectively usable for
overdraw

While optimizing paint order, the CL doesn't attempt to maximize the use of overdraw. More
aggressive overdraw optimizations may follow.


BUG=474265
R=chrishtr@chromium.org,junov@chromium.org,pdr@chromium.org,fs@opera.com

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=196620

[f(malita), 2015-06-03 18:40:52]

fmalita@chromium.org changed reviewers:
+ chrishtr@chromium.org, fs@opera.com, junov@chromium.org, pdr@chromium.org

[f(malita), 2015-06-03 19:58:45]

This is the meat of https://codereview.chromium.org/1156663008/, enabling more
aggressive use of overdraw for corner seam avoidance purposes.

Local telemetry runs are a wash, while CT may read a tiny record time
improvement (too small for certainty though):
https://storage.cloud.google.com/cluster-telemetry/tasks/chromium_perf_runs/f...

A handful of layout tests require rebaselining:
https://storage.googleapis.com/chromium-layout-test-archives/linux_blink_rel/...

Most of those are trivial blending diffs due to different side painting order,
but a couple are corner seam/bleed progressions thanks to overdraw now being
usable for translucent sides.  Specifically, the bottom-left seam diffs for
fast/borders/border-mixed-alpha.html & fast/borders/mixed-border-styles.html.

[chrishtr, 2015-06-03 22:12:00]

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
File Source/core/paint/BoxBorderPainter.cpp (right):

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:403: struct
BoxBorderPainter::ComplexBorderInfo {
All of this code is just to determine the order in which to draw the four sides,
right? It seems like it could all be encoded in a sort function, is that too
awkward?

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:758: // FIXME: find a way to rationalize
this.
What does this mean? Also, TODO is the new FIXME.

[f(malita), 2015-06-04 01:54:21]

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
File Source/core/paint/BoxBorderPainter.cpp (right):

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:403: struct
BoxBorderPainter::ComplexBorderInfo {
On 2015/06/03 22:12:00, chrishtr wrote:
> All of this code is just to determine the order in which to draw the four
sides,
> right? It seems like it could all be encoded in a sort function, is that too
> awkward?

Right - done (split into smaller utility functions).

https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:758: // FIXME: find a way to rationalize
this.
On 2015/06/03 22:11:59, chrishtr wrote:
> What does this mean?

There's too much repetition for my taste, but enough semantic variance to make
the consolidation non-obvious. I had a consolidated version at some point, but
it ended up looking quite nasty so just making a note for now.

> Also, TODO is the new FIXME.
ACK, updated comment.

[fs, 2015-06-04 11:53:40]

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
File Source/core/paint/BoxBorderPainter.cpp (right):

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:739: effectiveOpacity *= groupOpacity;
Based on the example above... won't this be 0.5 * 0.25 = 0.125, when it should
be 0.5 * 0.5 = 0.25? (I.e. effectiveOpacity *= groupOpacity / effectiveOpacity;
expecting effectiveOpacity ~= groupOpacity afterwards?)

[f(malita), 2015-06-04 15:29:05]

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
File Source/core/paint/BoxBorderPainter.cpp (right):

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:739: effectiveOpacity *= groupOpacity;
On 2015/06/04 11:53:39, fs wrote:
> Based on the example above... won't this be 0.5 * 0.25 = 0.125, when it should
> be 0.5 * 0.5 = 0.25? (I.e. effectiveOpacity *= groupOpacity /
effectiveOpacity;
> expecting effectiveOpacity ~= groupOpacity afterwards?)

Indeed, that's accumulating way too much transparency. Great catch!

One option is to track the accumulated layer opacity accurately, compensating
for limited saveLayer alpha resolution (1/255) - but that opens up a can of
worms as effectiveOpacity may snap to 0.

The other option is to consider effectiveOpacity == groupOpacity.  This may
produce slightly-off blends, but it's more robust and since we have an upper
bound of 4 layers we can probably live with the accumulated error. Going to try
this for now.

Kinda surprising that we don't have tests exercising more than two levels of
border opacity. Added one.

[fs, 2015-06-04 15:49:14]

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
File Source/core/paint/BoxBorderPainter.cpp (right):

https://codereview.chromium.org/1159113010/diff/60001/Source/core/paint/BoxBo...
Source/core/paint/BoxBorderPainter.cpp:739: effectiveOpacity *= groupOpacity;
On 2015/06/04 15:29:05, f(malita) wrote:
> On 2015/06/04 11:53:39, fs wrote:
> > Based on the example above... won't this be 0.5 * 0.25 = 0.125, when it
should
> > be 0.5 * 0.5 = 0.25? (I.e. effectiveOpacity *= groupOpacity /
> effectiveOpacity;
> > expecting effectiveOpacity ~= groupOpacity afterwards?)
> 
> Indeed, that's accumulating way too much transparency. Great catch!
> 
> One option is to track the accumulated layer opacity accurately, compensating
> for limited saveLayer alpha resolution (1/255) - but that opens up a can of
> worms as effectiveOpacity may snap to 0.
> 
> The other option is to consider effectiveOpacity == groupOpacity.  This may
> produce slightly-off blends, but it's more robust and since we have an upper
> bound of 4 layers we can probably live with the accumulated error. Going to
try
> this for now.

Sounds reasonable to me. As long as the error is within 0.002 (or whatever it
is) it ought to be fine.

[chrishtr, 2015-06-04 21:00:21]

On 2015/06/04 at 01:54:21, fmalita wrote:
>
https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
> File Source/core/paint/BoxBorderPainter.cpp (right):
> 
>
https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
> Source/core/paint/BoxBorderPainter.cpp:403: struct
BoxBorderPainter::ComplexBorderInfo {
> On 2015/06/03 22:12:00, chrishtr wrote:
> > All of this code is just to determine the order in which to draw the four
sides,
> > right? It seems like it could all be encoded in a sort function, is that too
> > awkward?
> 
> Right - done (split into smaller utility functions).

There is still a while loop before sorting, can that be unified into one sort
function? It seems the sort function would have multi-dimensional sorting within
itself, but can still be one function.


> 
>
https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
> Source/core/paint/BoxBorderPainter.cpp:758: // FIXME: find a way to
rationalize this.
> On 2015/06/03 22:11:59, chrishtr wrote:
> > What does this mean?
> 
> There's too much repetition for my taste, but enough semantic variance to make
the consolidation non-obvious. I had a consolidated version at some point, but
it ended up looking quite nasty so just making a note for now.
> 
> > Also, TODO is the new FIXME.
> ACK, updated comment.

[f(malita), 2015-06-05 18:15:54]

On 2015/06/04 21:00:21, chrishtr wrote:
> On 2015/06/04 at 01:54:21, fmalita wrote:
> >
>
https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
> > File Source/core/paint/BoxBorderPainter.cpp (right):
> > 
> >
>
https://codereview.chromium.org/1159113010/diff/40001/Source/core/paint/BoxBo...
> > Source/core/paint/BoxBorderPainter.cpp:403: struct
> BoxBorderPainter::ComplexBorderInfo {
> > On 2015/06/03 22:12:00, chrishtr wrote:
> > > All of this code is just to determine the order in which to draw the four
> sides,
> > > right? It seems like it could all be encoded in a sort function, is that
too
> > > awkward?
> > 
> > Right - done (split into smaller utility functions).
> 
> There is still a while loop before sorting, can that be unified into one sort
> function? It seems the sort function would have multi-dimensional sorting
within
> itself, but can still be one function.

I see what you mean.

I have tried to completely do away with opacity groups before (just use a single
paint-order-sorted edge list), but things got hairy because the nested
transparency layer algorithm needs some look-ahead info (are there adjacent
sides in the current group? any groups following?) - so it's not as trivial as
iterating through the unified list sequentially.  I figured it's cleaner to
compute the opacity groups upfront.

But I think you're right: even with groups, we can perform a unified sort
*first* and then build the groups based on the sorted output.  It's cleaner and
also removes the need for some indirection (opacityGroupIndices).

Updated, PTAL.

[chrishtr, 2015-06-05 18:53:21]

Sort function looks good now.

I still don't uderstand the need for opacity groups though. Can't we just walk
the borders in sorted order and paint them? This seems equivalent to cases when
each side has its own opacity, and I don't quite see what complexity arises when
multiple have the same opacity.

[f(malita), 2015-06-06 00:09:57]

On 2015/06/05 18:53:21, chrishtr wrote:
> Sort function looks good now.
> 
> I still don't uderstand the need for opacity groups though. Can't we just walk
> the borders in sorted order and paint them? This seems equivalent to cases
when
> each side has its own opacity, and I don't quite see what complexity arises
when
> multiple have the same opacity.


The CL relies on nested transparency layers to ensure the paint is always opaque
(otherwise overdraw is not usable).  This technique requires creating the layer
stack in decreasing opacity order, while we paint the sides in increasing
opacity order.

There is one transparency layer per opacity group, and in some cases we can skip
the creation of the last (most translucent) layer as an optimization.

This could be implemented with two passes over the unified list (one in
decreasing order to create the layers, one in increasing order to paint the
sides), but it ends up quite tricky because some decisions require look-ahead
info.  When creating the layer stack: does the current layer/group contain any
adjacent edges? are there any other layers following?  When drawing sides: is
this the last side in the current layer (if so, we need to close the layer)?

So we'd end up effectively re-computing the opacity group info on the fly, in a
very convoluted way.  It's a lot cleaner to drive the algorithm with a
pre-computed group topology.

[chrishtr, 2015-06-06 00:20:20]

The CQ bit was checked by chrishtr@chromium.org

[chrishtr, 2015-06-06 00:20:21]

lgtm

[commit-bot: I haz the power, 2015-06-06 00:20:40]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1159113010/120001

[commit-bot: I haz the power, 2015-06-06 03:29:09]

Committed patchset #7 (id:120001) as
https://src.chromium.org/viewvc/blink?view=rev&revision=196620