Add edge AA for concave polys to tesselated path renderer

The basic algorithm is to run the GLU tesselator once to retrieve the boundary contours, compute the edge equations, and run the tesselator again, passing the inflated and intersected edges to get the interior polygons.  We use the edge flags from the second run to know which vertices are on the polygon edge (since some edge vertices become interior vertices when inflated).  These are drawn as separate triangles in order to pass the correct edge equations.

In order to share code as much as possible with the non-AA and convex paths, I wrapped the tesselator into some helper classes for the boundary tesselator, polygon tesselator, and polygon-with-edges tesselator.

[Stephen White, 2011-06-14 19:21:00]

Remove some unnecessary changes

[reed1, 2011-06-14 19:44:51]

http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h
File gpu/include/GrDrawTarget.h (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h#n...
gpu/include/GrDrawTarget.h:439: bool isConcaveState() const {
Perhaps we name this EdgeAAConcaveState, to match the flag, and to not have it
confused with more generic meanings of concave?

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.h
File gpu/src/GrGLProgram.h (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.h#newcod...
gpu/src/GrGLProgram.h:157: bool fEdgeAAConcave;
We did a lot of work to keep this struct small and dense. Can we move this to
the other byte fields, and call it SkBool8 (removing one of the pad bytes)?

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp
File gpu/src/GrGpuGLShaders.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp#n...
gpu/src/GrGpuGLShaders.cpp:734: desc.fEdgeAANumEdges =
fCurrDrawState.fEdgeAANumEdges;
should call SkToBool() I think, to turn the bit-test into a 0-or-1 (in case the
bit moves outside of 8 bits in the future).

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrPathUtils.cpp
File gpu/src/GrPathUtils.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrPathUtils.cpp#newc...
gpu/src/GrPathUtils.cpp:113: 
Is this a bug-fix, or required for your code now? Does it adversely affect the
old code paths?

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrTesselatedPathRend...
File gpu/src/GrTesselatedPathRenderer.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:40: {
skia puts the { on the same line as the ) of a function definition. (more like
this below)

[bsalomon, 2011-06-14 20:33:13]

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp
File gpu/src/GrGLProgram.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp#newc...
gpu/src/GrGLProgram.cpp:514: GR_DEBUGASSERT((count & 0x01) == 0);
Can we add a new segment rather than appending to the Unis segment? Maybe
fFSHelpers or fFSFunctions?

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp#newc...
gpu/src/GrGLProgram.cpp:520: segments.fFSCode.append("\tfloat b");
This block might be more readable using appendf. e.g.:
segments.fFSCode.appendf("\tfloat b%d;", i/2);
segments.fFSCode.appendf("\tif (cross2(" EDGES_UNI_NAME "[%d].xy, "
EDGES_UNI_NAME "[%d].xy) < 0.0) {\n", i/2);
...
Also probably a reasonable case of breaking the 80 col wrap rule :)

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp
File gpu/src/GrGpuGLShaders.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp#n...
gpu/src/GrGpuGLShaders.cpp:735: desc.fEdgeAAConcave = fCurrDrawState.fFlagBits &
kEdgeAAConcave_StateBit;
Can we make this:

desc.fEdgeAAConcave = desc.fNumAAEges > 0 && (fCurrDrawState.fFlagBits &
kEdgeAAConcave_StateBit);

Just want to avoid generating a different key in cases when the value won't
affect the generated program.

[Stephen White, 2011-06-14 22:18:13]

On 2011/06/14 19:44:51, reed1 wrote:
> http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h
> File gpu/include/GrDrawTarget.h (right):
> 
>
http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h#n...
> gpu/include/GrDrawTarget.h:439: bool isConcaveState() const {
> Perhaps we name this EdgeAAConcaveState, to match the flag, and to not have it
> confused with more generic meanings of concave?

Done.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.h
> File gpu/src/GrGLProgram.h (right):
> 
>
http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.h#newcod...
> gpu/src/GrGLProgram.h:157: bool fEdgeAAConcave;
> We did a lot of work to keep this struct small and dense. Can we move this to
> the other byte fields, and call it SkBool8 (removing one of the pad bytes)?

Done.  It should probably be merged with the other SkBool8 into something else
at some point.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp
> File gpu/src/GrGpuGLShaders.cpp (right):
> 
>
http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp#n...
> gpu/src/GrGpuGLShaders.cpp:734: desc.fEdgeAANumEdges =
> fCurrDrawState.fEdgeAANumEdges;
> should call SkToBool() I think, to turn the bit-test into a 0-or-1 (in case
the
> bit moves outside of 8 bits in the future).

Done.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrPathUtils.cpp
> File gpu/src/GrPathUtils.cpp (right):
> 
>
http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrPathUtils.cpp#newc...
> gpu/src/GrPathUtils.cpp:113: 
> Is this a bug-fix, or required for your code now? Does it adversely affect the
> old code paths?

I'm to blame for mistakenly changing this to true in r1353, which meant it was
adding space for a closing vertex that the old code path never used (since it
passes false when it creates its actual SkPath::Iter).  This change makes it not
add space that extra vertex, and changes the tesselated path renderer to not
request one either when it creates its SkPath::Iter.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrTesselatedPathRend...
> File gpu/src/GrTesselatedPathRenderer.cpp (right):
> 
>
http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrTesselatedPathRend...
> gpu/src/GrTesselatedPathRenderer.cpp:40: {
> skia puts the { on the same line as the ) of a function definition. (more like
> this below)

Done.

[Stephen White, 2011-06-14 22:22:25]

Thanks for the review.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp
File gpu/src/GrGLProgram.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp#newc...
gpu/src/GrGLProgram.cpp:514: GR_DEBUGASSERT((count & 0x01) == 0);
On 2011/06/14 20:33:13, bsalomon wrote:
> Can we add a new segment rather than appending to the Unis segment? Maybe
> fFSHelpers or fFSFunctions?

Done.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGLProgram.cpp#newc...
gpu/src/GrGLProgram.cpp:520: segments.fFSCode.append("\tfloat b");
On 2011/06/14 20:33:13, bsalomon wrote:
> This block might be more readable using appendf. e.g.:
> segments.fFSCode.appendf("\tfloat b%d;", i/2);
> segments.fFSCode.appendf("\tif (cross2(" EDGES_UNI_NAME "[%d].xy, "
> EDGES_UNI_NAME "[%d].xy) < 0.0) {\n", i/2);
> ...
> Also probably a reasonable case of breaking the 80 col wrap rule :)

Done.

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp
File gpu/src/GrGpuGLShaders.cpp (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/src/GrGpuGLShaders.cpp#n...
gpu/src/GrGpuGLShaders.cpp:735: desc.fEdgeAAConcave = fCurrDrawState.fFlagBits &
kEdgeAAConcave_StateBit;
On 2011/06/14 20:33:13, bsalomon wrote:
> Can we make this:
> 
> desc.fEdgeAAConcave = desc.fNumAAEges > 0 && (fCurrDrawState.fFlagBits &
> kEdgeAAConcave_StateBit);
> 
> Just want to avoid generating a different key in cases when the value won't
> affect the generated program.

Done.

[Stephen White, 2011-06-14 22:23:45]

Fixes from review comments

[Stephen White, 2011-06-14 22:30:50]

Thanks for the review.

http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h
File gpu/include/GrDrawTarget.h (right):

http://codereview.appspot.com/4571072/diff/11001/gpu/include/GrDrawTarget.h#n...
gpu/include/GrDrawTarget.h:439: bool isConcaveState() const {
Actually, it turns out this accessor wasn't needed, so I just removed it.

[reed1, 2011-06-15 12:07:07]

LGTM, waiting on others

http://codereview.appspot.com/4571072/diff/18002/gpu/include/GrDrawTarget.h
File gpu/include/GrDrawTarget.h (right):

http://codereview.appspot.com/4571072/diff/18002/gpu/include/GrDrawTarget.h#n...
gpu/include/GrDrawTarget.h:91: //   ops.
Not specific to this CL, but does this multi-line comment work with doxygen?

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrGpuGLShaders.cpp
File gpu/src/GrGpuGLShaders.cpp (right):

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrGpuGLShaders.cpp#n...
gpu/src/GrGpuGLShaders.cpp:734: desc.fEdgeAANumEdges =
fCurrDrawState.fEdgeAANumEdges;
LF + TAB after &&, to preserve ~80 cols?

[bsalomon, 2011-06-15 13:06:33]

LGTM, too. I assume it passed the program unit test.

Are we seeing cases where we exceed the ushort index range or was the check
added in an abundance of caution? We can add 32 bit index support. It just
hasn't been necessary yet.

[TomH, 2011-06-15 13:49:43]

LGTM, modulo nits.
Sorry this was so slow, I thought I was CC: rather than R:

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
File gpu/src/GrTesselatedPathRenderer.cpp (right):

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:302: } while (nearlyEqual(v1, v2) && count
> 3);
What happens here if we run out of points and we still have two nearly-equal
vectors? (I suppose it isn't any worse than what came before...)

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:316: if (numVertices < 3) return 0;
Nit: Skia style gives even short if statements {} and newlines (here and below).

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:549: for (int i = 0; i < indices.count(); i
+= 3) {
Another small thing: can we assert that indices.count() % 3 == 0? Otherwise we
reference off the array... Alternately, check that i + 2 < indices.count()

[Stephen White, 2011-06-15 13:52:40]

On Wed, Jun 15, 2011 at 9:06 AM, <bsalomon@google.com> wrote:

> LGTM, too. I assume it passed the program unit test.
>
> Are we seeing cases where we exceed the ushort index range or was the
> check added in an abundance of caution? We can add 32 bit index support.
> It just hasn't been necessary yet.


The fuzzer in some cases produces enormous geometry which blows the limit (I
presume most of it offscreen -- we should probably look at better clipping
here).  It also produces some pathological curves with hundreds of thousands
of self-intersections, where the GLU tesselator's combine callback puts the
number of verts over the limit.

I don't think OpenGL ES2 supports 32 bit indices.  IIRC many Intel
integrated chipsets don't support more than 16bit indices either.  The
correct solution is probably to use 32 bit indices until draw time, then
upload the geometry in chunks. In fact, the concave edge AA doesn't use
indexed geometry at all (only the non-AA concave path drawing does); I just
wanted to keep the datatypes the same to share code.

Stephen


>
>
>
>
http://codereview.appspot.com/**4571072/<http://codereview.appspot.com/4571072/>
>

[Stephen White, 2011-06-15 14:23:50]

Fixes for ProgramUnitTest; Responding to Tom's comments

[Stephen White, 2011-06-15 14:24:29]

Thanks for the review, Tom.

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
File gpu/src/GrTesselatedPathRenderer.cpp (right):

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:302: } while (nearlyEqual(v1, v2) && count
> 3);
On 2011/06/15 13:49:43, TomH wrote:
> What happens here if we run out of points and we still have two nearly-equal
> vectors? (I suppose it isn't any worse than what came before...)

If all the points are collinear, it'll basically return something meaningless. 
But that's probably ok, since we're not going to render anything anyway.  Could
do a check for that elsewhere, though, and early return.

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:316: if (numVertices < 3) return 0;
On 2011/06/15 13:49:43, TomH wrote:
> Nit: Skia style gives even short if statements {} and newlines (here and
below).

Done.

http://codereview.appspot.com/4571072/diff/18002/gpu/src/GrTesselatedPathRend...
gpu/src/GrTesselatedPathRenderer.cpp:549: for (int i = 0; i < indices.count(); i
+= 3) {
On 2011/06/15 13:49:43, TomH wrote:
> Another small thing: can we assert that indices.count() % 3 == 0? Otherwise we
> reference off the array... Alternately, check that i + 2 < indices.count()

Done.

[Stephen White, 2011-06-15 17:24:45]

Do you guys want to take a look at the updated version, or should I assume your
LGTM's stand?

[TomH, 2011-06-15 17:27:31]

On 2011/06/15 17:24:45, Stephen White wrote:
> Do you guys want to take a look at the updated version, or should I assume
your
> LGTM's stand?

You're still missing a couple of if {} in computeEdgesAndIntersect, but still
LGTM enough.

[Stephen White, 2011-06-15 17:53:14]

Landed as r1600.  Closing.