Analytic AntiAlias for Convex Shapes

Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here: https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSypMlHWZk/edit?usp=sharing

Our best case is filling big triangles, which according to our experiment has ~2.9x speedup. Our worst case is filling small ovals/circles, which has a ~1.06x slowdown.

To see how our new algorithm changes the DM images, see: https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002

Committed: https://skia.googlesource.com/skia/+/7795822807478143120c33228b68d2ab3918af2c

[liyuqian, 2016-08-08 17:43:14]

Description was changed from

==========
Handle some edge cases


Snap alpha to accelerate blitting


Fall back on sampling for concave paths


Snap y


Implement AnalyticAA for convex shapes

BUG=skia:
==========

to

==========
Handle some edge cases


Snap alpha to accelerate blitting


Fall back on sampling for concave paths


Snap y


Implement AnalyticAA for convex shapes

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-08 19:34:35]

Description was changed from

==========
Handle some edge cases


Snap alpha to accelerate blitting


Fall back on sampling for concave paths


Snap y


Implement AnalyticAA for convex shapes

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional ys in the middle
of the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-08 19:34:35]

liyuqian@google.com changed reviewers:
+ caryclark@google.com, reed@google.com

[liyuqian, 2016-08-08 19:41:02]

Hi Mike and Cary, having both convex and concave shapes' change in one CL might
be too large. So I'm first uploading a CL that only implements the convex
shapes' analytic anti-aliasing. (It's still quite large...)

I've made SkAnalyticEdge completely separate from SkEdge so there's no more
multiple-inheritance.

Please let me know if you have any comments.

[liyuqian, 2016-08-08 20:44:21]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional ys in the middle
of the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional y in the middle of
the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-08 20:44:58]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional y in the middle of
the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional y in the middle of
the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[caryclark, 2016-08-10 13:08:10]

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkAntiRun.h
File src/core/SkAntiRun.h (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkAntiRun.h#ne...
src/core/SkAntiRun.h:82: alpha[0] = SkToU8(SkTMin<int>(0xFF, alpha[0] +
maxValue));
In what case is this needed?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp
File src/core/SkEdge.cpp (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:483: int SkAnalyticEdge::setLine(const SkPoint& p0, const
SkPoint& p1, const SkIRect* clip) {
Since this shares so much code with the other setLine, can this call the other,
or call a function common to both?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:486: x0 = SkScalarToFixed(p0.fX);
SkFixed x0 = ...

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:503: if (y0 == y1) {
move test before top, bot

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:519: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 -
y0, x1 - x0)) : SK_MaxS32;
x1 == x0 ?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:540: if (y0 == y1)
add braces around if

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:551: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 -
y0, x1 - x0)) : SK_MaxS32;
this also shares a lot of code with setline. Can they all share a common
function?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:564: {
brace on same line as if

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:576: x0 = SkScalarToFixed(pts[0].fX);
SkFDot6 x0 = ...

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:596: if (top == bot)
add braces

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:614: }
Out of curiosity, is this any less efficient and more readable as

shift = SkTMax(1, SkTMin(shift, MAX_COEFF_SHIFT));

?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h
File src/core/SkEdge.h (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:138: kQuad_Type,
could you add a comment about how conic is supported?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:147: SkFixed fUpperX;
Could you add comments on what these fields mean and/or how they are used?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:151: SkFixed fDY;            // abs of the inverse of fDX; may
be SK_MaxS32 when fDX is close to 0
is this comment on the right line?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:181: int setLine(const SkPoint& p0, const SkPoint& p1, const
SkIRect* clip);
what does the return result mean? If it is always 1 or 0, can it return a bool
instead?

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:183: inline int setLine(const SkPoint& p0, const SkPoint& p1);
ditto

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:263: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 - y0,
x1 - x0)) : SK_MaxS32;
x1 == x0 ?

[liyuqian, 2016-08-16 13:07:45]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles or rotated rectangles, which has almost
2x speedup. Our worst case is filling small ovals, which has a 1.5x slowdown.
The slowdown can be eliminated by removing all the fractional y in the middle of
the oval.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-16 13:08:47]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GSMXNRjl1oFuSyp...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-16 13:09:56]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[liyuqian, 2016-08-16 13:22:06]

Hi Mike and Cary, I couldn't help to try to further accelerate my program during
the last week. The result is significant: now the fastest speedup is 2.8x and
the slowest slowdown is only ~10%. Also, I run the dm diff for every change I
made to ensure the quality. The links of the speedup and diff information are in
the CL description.

Most accelerations apply to future non-convex cases: use inline wisely, drop
slow virtual functions, use mask buffer, and make the whole program cleaner with
less complex condition/loop flow. However, in some cases, I expanded the
loop/condition flow myself because the compiler isn't smart enough to do the
optimization.

Additionally, I made two tables for quick triangle area lookup and SkFDot6
inverse lookup. Ben told me that they'd be better in SkOnce. Please let me know
what you recommend me doing.

Finally, I've also revised the code according to Cary's comments.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkAntiRun.h
File src/core/SkAntiRun.h (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkAntiRun.h#ne...
src/core/SkAntiRun.h:82: alpha[0] = SkToU8(SkTMin<int>(0xFF, alpha[0] +
maxValue));
On 2016/08/10 13:08:09, caryclark wrote:
> In what case is this needed?

Our RunBaseAdditiveBlitter uses SkAntiRun and it may trigger this case when
we're adding alphas of two partial rows.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp
File src/core/SkEdge.cpp (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:483: int SkAnalyticEdge::setLine(const SkPoint& p0, const
SkPoint& p1, const SkIRect* clip) {
On 2016/08/10 13:08:09, caryclark wrote:
> Since this shares so much code with the other setLine, can this call the
other,
> or call a function common to both?

Done. I removed the other method and make clip having the default value of
nullptr

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:486: x0 = SkScalarToFixed(p0.fX);
On 2016/08/10 13:08:10, caryclark wrote:
> SkFixed x0 = ...

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:503: if (y0 == y1) {
On 2016/08/10 13:08:10, caryclark wrote:
> move test before top, bot

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:519: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 -
y0, x1 - x0)) : SK_MaxS32;
On 2016/08/10 13:08:09, caryclark wrote:
> x1 == x0 ? 

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:540: if (y0 == y1)
On 2016/08/10 13:08:10, caryclark wrote:
> add braces around if

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:551: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 -
y0, x1 - x0)) : SK_MaxS32;
On 2016/08/10 13:08:09, caryclark wrote:
> this also shares a lot of code with setline. Can they all share a common
> function?

In my new CL, this probably is not the case as I heavily optimized the
updateLine.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:564: {
On 2016/08/10 13:08:09, caryclark wrote:
> brace on same line as if

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:576: x0 = SkScalarToFixed(pts[0].fX);
On 2016/08/10 13:08:09, caryclark wrote:
> SkFDot6 x0 = ...

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:596: if (top == bot)
On 2016/08/10 13:08:09, caryclark wrote:
> add braces

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.cpp#new...
src/core/SkEdge.cpp:614: }
On 2016/08/10 13:08:09, caryclark wrote:
> Out of curiosity, is this any less efficient and more readable as
> 
> shift = SkTMax(1, SkTMin(shift, MAX_COEFF_SHIFT));
> 
> ?

I'm not sure. Maybe shift = SkTPin(shift, 1, MAX_COEFF_SHIFT) is even simpler.
Anyway, I don't think setQuadratic is a performance bottleneck so I'll adopt
your cleaner implementation. (I was copying from the old code anyway so I don't
know why the old code is like this.)

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h
File src/core/SkEdge.h (right):

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:138: kQuad_Type,
On 2016/08/10 13:08:10, caryclark wrote:
> could you add a comment about how conic is supported?

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:147: SkFixed fUpperX;
On 2016/08/10 13:08:10, caryclark wrote:
> Could you add comments on what these fields mean and/or how they are used?

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:151: SkFixed fDY;            // abs of the inverse of fDX; may
be SK_MaxS32 when fDX is close to 0
On 2016/08/10 13:08:10, caryclark wrote:
> is this comment on the right line?

Yes, I'm adding an extra newline to make it more clear.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:181: int setLine(const SkPoint& p0, const SkPoint& p1, const
SkIRect* clip);
On 2016/08/10 13:08:10, caryclark wrote:
> what does the return result mean? If it is always 1 or 0, can it return a bool
> instead?

I've changed it to bool. I don't know why the original code (which I copied
from) has return type int.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:183: inline int setLine(const SkPoint& p0, const SkPoint& p1);
On 2016/08/10 13:08:10, caryclark wrote:
> ditto

Done.

https://codereview.chromium.org/2221103002/diff/60001/src/core/SkEdge.h#newco...
src/core/SkEdge.h:263: fDY         = x1 - x0 != 0 ? SkAbs32(SkFixedDiv(y1 - y0,
x1 - x0)) : SK_MaxS32;
On 2016/08/10 13:08:10, caryclark wrote:
> x1 == x0 ?

Done.

[liyuqian, 2016-08-18 19:06:08]

Any updated comments?

[caryclark, 2016-08-18 19:26:20]

On 2016/08/18 19:06:08, liyuqian wrote:
> Any updated comments?

Not from me. lgtm

[reed1, 2016-08-18 20:31:01]

https://codereview.chromium.org/2221103002/diff/100001/include/private/SkFixed.h
File include/private/SkFixed.h (right):

https://codereview.chromium.org/2221103002/diff/100001/include/private/SkFixe...
include/private/SkFixed.h:91: inline SkFixed SkFixedMul_lowprec(SkFixed a,
SkFixed b) {
is this referenced from several files? wondering if we need to add it to this
shared header.

Also, can we add asserts that it never overflows?

e.g.
    if debug mode, compute the answer as int64_t and assert that that fits in
32bits

https://codereview.chromium.org/2221103002/diff/100001/samplecode/SampleApp.cpp
File samplecode/SampleApp.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/samplecode/SampleApp.c...
samplecode/SampleApp.cpp:1688: GlobalAAConfig::getInstance().fUseAnalyticAA =
Do you intend to land this permanently?

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkAntiRun.h
File src/core/SkAntiRun.h (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkAntiRun.h#n...
src/core/SkAntiRun.h:82: alpha[0] = SkToU8(SkTMin<int>(0xFF, alpha[0] +
maxValue));
is this needed today, or just with your CL? If today, lets land this sooner.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkBlitter.cpp
File src/core/SkBlitter.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkBlitter.cpp...
src/core/SkBlitter.cpp:79: if (leftAlpha > 0) { // we may send in x = -1 with
leftAlpha = 0
Can this land ahead of time, or does it only make sense w/ your CL?

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp
File src/core/SkEdge.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:483: static const int kInverseTableSize = 1024; //
SK_FDot6One * 16
Does this impl use shared functions form SkEdge.cpp, or could we move it to its
own impl file? I ask, since SkEdge.cpp was already modestly big, and this makes
it much larger. Not critical.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:491: if (i != 0) {
nit: is it any faster to just have 2 loops, so we don't have to check for i == 0
on each iteration? (does the compiler already make that optimization?)

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:500: static FDot6InverseTable table;
nit: static variables are gPrefixedWIthAG.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:502: inline static SkFixed lookup(SkFDot6 x) {
nit: static methods are Capitalized.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:508: FDot6InverseTable QuickFDot6Inverse::table;
Chrome won't allow us to have a complex constructor. I suspect you'll need to
precompute the table, and check it in as a const table. Typically, we add that
in a separate file, e.g.

// new file

const SkFixed gInverse1KFixedTable[] = {
    0x..., ...
};

/*
Here is the code that builds the table...
*/

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:510: inline SkFixed quickSkFDot6Div(SkFDot6 a, SkFDot6 b) {
'static' is more important than 'inline' (I think), since as written this
creates a global symbol.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:510: inline SkFixed quickSkFDot6Div(SkFDot6 a, SkFDot6 b) {
Would this optimized version of FDot6Div also help the other callers? Perhaps it
could be landed as a separate CL... (with its own unittest)

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:533: {
nit: skia places the { on the same line as the function name

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:584: {
interesting. appears that much of this impl is the same as SkQuadraticEdge. Is
that the case? I wonder if there is some way to share code / macro / etc. ?

[liyuqian, 2016-08-22 15:30:48]

Revised according to Mike's comments. See the detailed responses below.

https://codereview.chromium.org/2221103002/diff/100001/include/private/SkFixed.h
File include/private/SkFixed.h (right):

https://codereview.chromium.org/2221103002/diff/100001/include/private/SkFixe...
include/private/SkFixed.h:91: inline SkFixed SkFixedMul_lowprec(SkFixed a,
SkFixed b) {
On 2016/08/18 20:31:00, reed1 wrote:
> is this referenced from several files? wondering if we need to add it to this
> shared header.
> 
> Also, can we add asserts that it never overflows?
> 
> e.g.
>     if debug mode, compute the answer as int64_t and assert that that fits in
> 32bits

It's used in SkEdge.h, SkEdge.cpp (SkAnalyticEdge.cpp in the future), and
SkScan_AAAPath.cpp. I can move it SkEdge.h which is private. I'll also add the
overflow check.

https://codereview.chromium.org/2221103002/diff/100001/samplecode/SampleApp.cpp
File samplecode/SampleApp.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/samplecode/SampleApp.c...
samplecode/SampleApp.cpp:1688: GlobalAAConfig::getInstance().fUseAnalyticAA =
On 2016/08/18 20:31:00, reed1 wrote:
> Do you intend to land this permanently?

I intend to have this as long as both the old supersampling algorithm and my new
algorithm coexist, so I can switch between them easily in the SampleApp. If we
can completely replace supersampling algorithm, then I'll drop this.

Considering our current performance (2.8 - 0.9x speedup), do you want to turn it
on by default?

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkAntiRun.h
File src/core/SkAntiRun.h (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkAntiRun.h#n...
src/core/SkAntiRun.h:82: alpha[0] = SkToU8(SkTMin<int>(0xFF, alpha[0] +
maxValue));
On 2016/08/18 20:31:00, reed1 wrote:
> is this needed today, or just with your CL? If today, lets land this sooner.

I don't think that the current supersampling algorithm will trigger this because
it's descretized (0 - 16) without many arithmetic operations.

Anyway, I found that I actually triggered this because of some bugs in my code.
I've fixed them and I no longer need this check.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkBlitter.cpp
File src/core/SkBlitter.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkBlitter.cpp...
src/core/SkBlitter.cpp:79: if (leftAlpha > 0) { // we may send in x = -1 with
leftAlpha = 0
On 2016/08/18 20:31:00, reed1 wrote:
> Can this land ahead of time, or does it only make sense w/ your CL?

I think it only make sens w/ my CL as previous algorithm won't have this edge
case.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp
File src/core/SkEdge.cpp (right):

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:483: static const int kInverseTableSize = 1024; //
SK_FDot6One * 16
On 2016/08/18 20:31:01, reed1 wrote:
> Does this impl use shared functions form SkEdge.cpp, or could we move it to
its
> own impl file? I ask, since SkEdge.cpp was already modestly big, and this
makes
> it much larger. Not critical.

Nothing shared. I'll create a new cpp file.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:491: if (i != 0) {
On 2016/08/18 20:31:00, reed1 wrote:
> nit: is it any faster to just have 2 loops, so we don't have to check for i ==
0
> on each iteration? (does the compiler already make that optimization?)

Not sure. Since this code is run once during the start, I didn't tune its
performance. Also, I don't know if nanobench can test this run-once-at-start
code.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:500: static FDot6InverseTable table;
On 2016/08/18 20:31:00, reed1 wrote:
> nit: static variables are gPrefixedWIthAG.

Done.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:502: inline static SkFixed lookup(SkFDot6 x) {
On 2016/08/18 20:31:00, reed1 wrote:
> nit: static methods are Capitalized.

Done.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:508: FDot6InverseTable QuickFDot6Inverse::table;
On 2016/08/18 20:31:01, reed1 wrote:
> Chrome won't allow us to have a complex constructor. I suspect you'll need to
> precompute the table, and check it in as a const table. Typically, we add that
> in a separate file, e.g.
> 
> // new file
> 
> const SkFixed gInverse1KFixedTable[] = {
>     0x..., ...
> };
> 
> /*
> Here is the code that builds the table...
> */

Done.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:510: inline SkFixed quickSkFDot6Div(SkFDot6 a, SkFDot6 b) {
On 2016/08/18 20:31:01, reed1 wrote:
> 'static' is more important than 'inline' (I think), since as written this
> creates a global symbol.

Done.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:510: inline SkFixed quickSkFDot6Div(SkFDot6 a, SkFDot6 b) {
On 2016/08/18 20:31:00, reed1 wrote:
> Would this optimized version of FDot6Div also help the other callers? Perhaps
it
> could be landed as a separate CL... (with its own unittest)

Maybe. But so far, SkEdge.cpp/h is the only place that uses SkFDot6Div. Do you
still want to land it as a separate CL considering that?

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:533: {
On 2016/08/18 20:31:00, reed1 wrote:
> nit: skia places the { on the same line as the function name

Done.

https://codereview.chromium.org/2221103002/diff/100001/src/core/SkEdge.cpp#ne...
src/core/SkEdge.cpp:584: {
On 2016/08/18 20:31:00, reed1 wrote:
> interesting. appears that much of this impl is the same as SkQuadraticEdge. Is
> that the case? I wonder if there is some way to share code / macro / etc. ?

Done.

[liyuqian, 2016-08-24 18:10:22]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.8x speedup. Our worst case is filling small ovals, which has a ~1.1x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.9x speedup. Our worst case is filling small ovals/circles, which has a ~1.06x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

[reed1, 2016-10-03 13:44:21]

ok, lets dig into this thing :)

Can you create a separate header for the analytic edges? I am thinking mostly
about wanting to see clearly 
1. what (if any) changes were needed to the old path
2. what is added for the new path

[liyuqian, 2016-10-03 14:54:00]

On 2016/10/03 13:44:21, reed1 wrote:
> ok, lets dig into this thing :)
> 
> Can you create a separate header for the analytic edges? I am thinking mostly
> about wanting to see clearly 
> 1. what (if any) changes were needed to the old path
> 2. what is added for the new path

Ok, it's now separated as SkAnalyticEdge.h

[reed1, 2016-10-03 17:33:35]

do we want the new GMs, other than to trigger the global switch for the two
modes?

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp
File src/core/SkBlitter.cpp (right):

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp...
src/core/SkBlitter.cpp:79: if (leftAlpha > 0) { // we may send in x = -1 with
leftAlpha = 0
can/should we land this file ahead of time?

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h
File src/core/SkScan.h (right):

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h#newc...
src/core/SkScan.h:102: static void aaa_fill_path(const SkPath& path, const
SkIRect* clipRect, AdditiveBlitter*,
who calls this method? (aaa...) Does it need to be in this header?

[liyuqian, 2016-10-03 17:55:02]

On 2016/10/03 17:33:35, reed1 wrote:
> do we want the new GMs, other than to trigger the global switch for the two
> modes?
> 
> https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp
> File src/core/SkBlitter.cpp (right):
> 
>
https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp...
> src/core/SkBlitter.cpp:79: if (leftAlpha > 0) { // we may send in x = -1 with
> leftAlpha = 0
> can/should we land this file ahead of time?
> 
> https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h
> File src/core/SkScan.h (right):
> 
>
https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h#newc...
> src/core/SkScan.h:102: static void aaa_fill_path(const SkPath& path, const
> SkIRect* clipRect, AdditiveBlitter*,
> who calls this method? (aaa...) Does it need to be in this header?

Do you mean gm/aaa.cpp and gm/addarc.cpp? gm/aaa.cpp is used to illustrate the
difference between the old approach and our analytic approach. gm/addarc.cpp
draws many animated circles to ensure that my optimization doesn't go too far to
harm our quality. In my opinion, they're both useful.

[liyuqian, 2016-10-03 17:55:42]

Responses for the comments.

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp
File src/core/SkBlitter.cpp (right):

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkBlitter.cpp...
src/core/SkBlitter.cpp:79: if (leftAlpha > 0) { // we may send in x = -1 with
leftAlpha = 0
On 2016/10/03 17:33:35, reed1 wrote:
> can/should we land this file ahead of time?

I think that we don't need to land this file first. See our earlier discussion:
https://codereview.chromium.org/2221103002/diff/100001/src/core/SkBlitter.cpp...

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h
File src/core/SkScan.h (right):

https://codereview.chromium.org/2221103002/diff/180001/src/core/SkScan.h#newc...
src/core/SkScan.h:102: static void aaa_fill_path(const SkPath& path, const
SkIRect* clipRect, AdditiveBlitter*,
On 2016/10/03 17:33:35, reed1 wrote:
> who calls this method? (aaa...) Does it need to be in this header?

Only AAAFillPath is using aaa_fill_path.

However, aaa_fill_path now calls SkScan::AntiFillPath to fill non-convex paths
because we haven't implemented that yet. Since AntiFillPath is private in
SkScan, I have to also make aaa_fill_path as a member of SkScan. (If
AntiFillPath is not called in the future, I could just make aaa_fill_path a
static void function in SkScan_AAAPath.cpp.)

[liyuqian, 2016-10-03 18:03:36]

I simplified gm/aaa.cpp to make it less confusing. Currently, we do not set the
fUseAnalyticAA bit in gm itself. Instead, we rely on the dm, nanobench, or
SampleApp to turn that bit on/off.

If we do set the fUseAnalyticAA bit in the gm itself, it will break the dm or
nanobench because they will run many GMs concurrently. We don't want one GM to
change the fUseAnalyticAA bit for another GM.

[reed1, 2016-10-03 19:02:28]

https://codereview.chromium.org/2221103002/diff/200001/gm/aaa.cpp
File gm/aaa.cpp (right):

https://codereview.chromium.org/2221103002/diff/200001/gm/aaa.cpp#newcode49
gm/aaa.cpp:49: canvas->drawRectCoords(20, 20, 20.2, 200, p);
nit: you'll get warnings about doubles. Use 20.2f

[liyuqian, 2016-10-04 13:54:57]

Hi Mike, I've rebased the CL so the GM changes are now gone.

[reed1, 2016-10-04 15:04:20]

Is the effect of the CL as is, that nothing changes unless we wack the new
global? If so, lgtm

[liyuqian, 2016-10-04 15:29:02]

The CQ bit was checked by liyuqian@google.com to run a CQ dry run

[commit-bot: I haz the power, 2016-10-04 15:29:06]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[liyuqian, 2016-10-04 15:31:52]

The CQ bit was unchecked by liyuqian@google.com

[liyuqian, 2016-10-04 15:32:26]

On 2016/10/04 15:04:20, reed1 wrote:
> Is the effect of the CL as is, that nothing changes unless we wack the new
> global? If so, lgtm

Yes. I'm going to land it. Thank you!

[liyuqian, 2016-10-04 15:32:38]

The CQ bit was checked by liyuqian@google.com

[liyuqian, 2016-10-04 15:32:39]

The patchset sent to the CQ was uploaded after l-g-t-m from caryclark@google.com
Link to the patchset: https://codereview.chromium.org/2221103002/#ps220001
(title: "Merge the GM CL")

[commit-bot: I haz the power, 2016-10-04 15:32:42]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[liyuqian, 2016-10-04 15:32:57]

The CQ bit was unchecked by liyuqian@google.com

[liyuqian, 2016-10-04 15:51:34]

The CQ bit was checked by liyuqian@google.com

[liyuqian, 2016-10-04 15:51:35]

The patchset sent to the CQ was uploaded after l-g-t-m from
caryclark@google.com, reed@google.com
Link to the patchset: https://codereview.chromium.org/2221103002/#ps240001
(title: "Change comma to semicolon to avoid compile warning")

[commit-bot: I haz the power, 2016-10-04 15:51:42]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-04 15:56:31]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-04 15:56:33]

Try jobs failed on following builders:
  Build-Win-MSVC-x86-Debug-Trybot on master.client.skia.compile (JOB_FAILED,
http://build.chromium.org/p/client.skia.compile/builders/Build-Win-MSVC-x86-D...)

[liyuqian, 2016-10-04 16:05:45]

The CQ bit was checked by liyuqian@google.com

[liyuqian, 2016-10-04 16:05:46]

The patchset sent to the CQ was uploaded after l-g-t-m from
caryclark@google.com, reed@google.com
Link to the patchset: https://codereview.chromium.org/2221103002/#ps260001
(title: "Try fixing constexpr error in MSVC")

[commit-bot: I haz the power, 2016-10-04 16:05:55]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-10-04 16:29:53]

Description was changed from

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.9x speedup. Our worst case is filling small ovals/circles, which has a ~1.06x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002
==========

to

==========
Implement AnalyticAA for convex shapes.

Design doc: go/analyticAA

A performance test can be found here:
https://docs.google.com/a/google.com/spreadsheets/d/1n9LSjFzrQzx0hovFddWey0GS...

Our best case is filling big triangles, which according to our experiment has
~2.9x speedup. Our worst case is filling small ovals/circles, which has a ~1.06x
slowdown.

To see how our new algorithm changes the DM images, see:
https://x20web.corp.google.com/~liyuqian/dmdiff/index.html
The most significant changes are in convexpaths and analytic_antialias_convex

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2221103002

Committed:
https://skia.googlesource.com/skia/+/7795822807478143120c33228b68d2ab3918af2c
==========

[commit-bot: I haz the power, 2016-10-04 16:29:54]

Committed patchset #14 (id:260001) as
https://skia.googlesource.com/skia/+/7795822807478143120c33228b68d2ab3918af2c

[stephana, 2016-10-04 16:55:46]

A revert of this CL (patchset #14 id:260001) has been created in
https://codereview.chromium.org/2388213003/ by stephana@google.com.

The reason for reverting is: Breaks iOS build. .