Tessellating GPU path renderer.

Tessellating GPU path renderer.

This path renderer converts paths to linear contours, resolves intersections via Bentley-Ottman, implements a trapezoidal decomposition a la Fournier and Montuno to produce triangles, and renders those with a single draw call. It does not currently do antialiasing, so it must be used in conjunction with multisampling.

A fair amount of the code is to handle floating point edge cases in intersections. Rather than perform exact computations (which would require arbitrary precision arithmetic), we reconnect the mesh to reflect the intersection points. For example, intersections can occur above the current vertex, and force edges to be merged into the current vertex, requiring a restart of the intersections. Splitting edges for intersections can also force them to merge with formerly-distinct edges in the same polygon, or to violate the ordering of the active edge list, or the active edge state of split edges.

BUG=skia:

Committed: https://skia.googlesource.com/skia/+/d6ed19cc751463285491a538bc7bf154cc7e6d8c

[Stephen White, 2015-01-16 19:57:11]

senorblanco@chromium.org changed reviewers:
+ bsalomon@google.com

[Stephen White, 2015-01-16 19:57:12]

Hi Brian,

I'm sending this out for early comments.

Known issues:

- the way I'm adding to the path rendering chain is probably wrong
- edge AA is a WIP, and currently disabled, so boundary extraction is unused and
could be removed
- needs formatting and comments

[bsalomon, 2015-01-20 15:12:24]

https://codereview.chromium.org/855513004/diff/1/samplecode/SampleConcavePath...
File samplecode/SampleConcavePaths.cpp (right):

https://codereview.chromium.org/855513004/diff/1/samplecode/SampleConcavePath...
samplecode/SampleConcavePaths.cpp:139: // Star test (self-intersecting)
should we make this guy a GM instead of a Sample?

https://codereview.chromium.org/855513004/diff/1/src/gpu/GrTessellatingPathRe...
File src/gpu/GrTessellatingPathRenderer.h (right):

https://codereview.chromium.org/855513004/diff/1/src/gpu/GrTessellatingPathRe...
src/gpu/GrTessellatingPathRenderer.h:18: class SK_API GrTessellatingPathRenderer
: public GrPathRenderer {
Curious why this has SK_API?

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp#n...
tests/ConcavePathTests.cpp:18: static void draw_path_0(SkCanvas* canvas, const
SkPaint& paint) {
What do theses tests test? Just that we don't crash when drawing these paths?

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp#n...
tests/ConcavePathTests.cpp:241: SkAutoTUnref<SkGpuDevice>
device(SkGpuDevice::Create(context,
Can you use a sksurface instead of creating a device directly?

[Stephen White, 2015-01-20 18:54:15]

https://codereview.chromium.org/855513004/diff/1/samplecode/SampleConcavePath...
File samplecode/SampleConcavePaths.cpp (right):

https://codereview.chromium.org/855513004/diff/1/samplecode/SampleConcavePath...
samplecode/SampleConcavePaths.cpp:139: // Star test (self-intersecting)
On 2015/01/20 15:12:24, bsalomon wrote:
> should we make this guy a GM instead of a Sample?

Done.

https://codereview.chromium.org/855513004/diff/1/src/gpu/GrTessellatingPathRe...
File src/gpu/GrTessellatingPathRenderer.h (right):

https://codereview.chromium.org/855513004/diff/1/src/gpu/GrTessellatingPathRe...
src/gpu/GrTessellatingPathRenderer.h:18: class SK_API GrTessellatingPathRenderer
: public GrPathRenderer {
On 2015/01/20 15:12:24, bsalomon wrote:
> Curious why this has SK_API?

Copypasta from the DefaultPathRenderer. Should I remove it from both?

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp#n...
tests/ConcavePathTests.cpp:18: static void draw_path_0(SkCanvas* canvas, const
SkPaint& paint) {
On 2015/01/20 15:12:24, bsalomon wrote:
> What do theses tests test? Just that we don't crash when drawing these paths?

Yep. I've added a comment to that effect, and comments for the individual tests
I have notes for.

https://codereview.chromium.org/855513004/diff/1/tests/ConcavePathTests.cpp#n...
tests/ConcavePathTests.cpp:241: SkAutoTUnref<SkGpuDevice>
device(SkGpuDevice::Create(context,
On 2015/01/20 15:12:24, bsalomon wrote:
> Can you use a sksurface instead of creating a device directly?

Done.

[Stephen White, 2015-01-20 19:04:49]

Note that I've removed the (unused) boundary code in PS 3 & 4. This shaves about
200 lines from GrTessellatingPathRenderer.
I also updated to ToT in PS 2, and responded to Brian's review comments in PS 5.

[Stephen White, 2015-01-20 23:26:43]

Patchset #6 (id:100001) has been deleted

[bsalomon, 2015-01-22 15:15:40]

bsalomon@google.com changed reviewers:
+ egdaniel@google.com, jvanverth@google.com, robertphillips@google.com

[bsalomon, 2015-01-22 15:15:40]

Adding a few more people for review.

[Stephen White, 2015-01-23 17:07:26]

I've added a descriptive comment outlining the path rendering algorithm.

This patch is ready for review.

[jvanverth1, 2015-01-26 21:49:45]

A few quick comments -- I'll take a deeper look tomorrow.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrPathRendererC...
File src/gpu/GrPathRendererChain.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrPathRendererC...
src/gpu/GrPathRendererChain.cpp:82:
this->addPathRenderer(SkNEW(GrTessellatingPathRenderer))->unref();
Why not add this to GrPathRenderer::AddPathRenderers?

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:167: if
(GrTessellatingPathRenderer::gWireframe) {
Is this for testing? You're injecting a conditional into a highly-used function
which could hurt performance. Maybe hide it behind a #define?

[Ken Russell (switch to Gerrit), 2015-01-26 23:48:09]

kbr@chromium.org changed reviewers:
+ kbr@chromium.org

[Ken Russell (switch to Gerrit), 2015-01-26 23:48:10]

This is very exciting! There are relatively few highly robust tessellators in
the open-source community that can satisfy this purpose. Great work!

[egdaniel, 2015-01-27 15:03:43]

first wave of comments. More to come

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:36: * not exact and may violate the mesh
topology or active edge list ordering. We
I'm sure it is in the paper, but since you reference the term "active edge"
multiple times in this description, can you give a very brief definition for
what this means.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:561: SkScalar srcSpaceTolSqd =
srcSpaceTol * srcSpaceTol;
So it looks like you are using a device space path, but using a src space tol.
Is this correct or are things just named wrong?

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1372: if (NULL == rt) {
can this check move before transforming the path into device space? Save a
little work if we don't need it

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1392: SkChunkAlloc alloc(maxPts * (3 *
sizeof(Vertex) + sizeof(Edge)));
Where is this coming from? Is this just a general heuristic that each point in
the contour on average will expand to 3 points and an edge?

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1395: path_to_contours(deviceSpacePath,
tol, SkRect::Make(clipBounds), contours.get(), alloc);
does this implementation always end up giving you contourCnt contours? Just
asking since this value came from the worstCasePointCount call.

[Stephen White, 2015-01-27 15:26:29]

New patch up for Jim's comments.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrPathRendererC...
File src/gpu/GrPathRendererChain.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrPathRendererC...
src/gpu/GrPathRendererChain.cpp:82:
this->addPathRenderer(SkNEW(GrTessellatingPathRenderer))->unref();
On 2015/01/26 21:49:45, jvanverth1 wrote:
> Why not add this to GrPathRenderer::AddPathRenderers?

Done.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:167: if
(GrTessellatingPathRenderer::gWireframe) {
On 2015/01/26 21:49:45, jvanverth1 wrote:
> Is this for testing? You're injecting a conditional into a highly-used
function
> which could hurt performance. Maybe hide it behind a #define?

It never showed up as hot in profiling. Changed it to compile-time anyway.

[Stephen White, 2015-01-27 16:46:19]

Greg: thanks for your review. New patch up.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:36: * not exact and may violate the mesh
topology or active edge list ordering. We
On 2015/01/27 15:03:43, egdaniel wrote:
> I'm sure it is in the paper, but since you reference the term "active edge"
> multiple times in this description, can you give a very brief definition for
> what this means.

Done.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:561: SkScalar srcSpaceTolSqd =
srcSpaceTol * srcSpaceTol;
On 2015/01/27 15:03:43, egdaniel wrote:
> So it looks like you are using a device space path, but using a src space tol.
> Is this correct or are things just named wrong?

Things are named wrong. Now that we're no longer doing edge antialiasing, I 
think I can actually get rid of the path transformation, and use src space
tolerance. But for now I've just renamed it.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1372: if (NULL == rt) {
On 2015/01/27 15:03:43, egdaniel wrote:
> can this check move before transforming the path into device space? Save a
> little work if we don't need it

Done.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1392: SkChunkAlloc alloc(maxPts * (3 *
sizeof(Vertex) + sizeof(Edge)));
On 2015/01/27 15:03:43, egdaniel wrote:
> Where is this coming from? Is this just a general heuristic that each point in
> the contour on average will expand to 3 points and an edge?

It's a heuristic. Added a comment to explain.

https://codereview.chromium.org/855513004/diff/380001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1395: path_to_contours(deviceSpacePath,
tol, SkRect::Make(clipBounds), contours.get(), alloc);
On 2015/01/27 15:03:43, egdaniel wrote:
> does this implementation always end up giving you contourCnt contours? Just
> asking since this value came from the worstCasePointCount call. 

worstCasePointCount() always gives you the correct contour count; it's just the
maxPts values that is an estimate.

[Stephen White, 2015-01-29 18:36:12]

Ping?

[egdaniel, 2015-01-29 19:31:19]

Do you have any perf numbers for this compared to the default path renderer. The
one case in particular that I wonder about is for convex paths. The DPR will see
the path is convex and immediately triangle fan it without needing to go through
stenciling. I feel like your path renderer and the DPR will basically end up
with the same triangulation, but yours will do more cpu to get there.

If it is the case the the DPR does convex faster maybe make the canDrawPath for
this function let convex fall through (even thought it "could" do them)?

https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:25: * 2) Sort the vertices in Y (and
secondarily in X) (merge_sort()).
step 2 and 3 here are actually reversed in the code

[Stephen White, 2015-01-29 19:38:18]

On 2015/01/29 19:31:19, egdaniel wrote:
> Do you have any perf numbers for this compared to the default path renderer.
The
> one case in particular that I wonder about is for convex paths. The DPR will
see
> the path is convex and immediately triangle fan it without needing to go
through
> stenciling. I feel like your path renderer and the DPR will basically end up
> with the same triangulation, but yours will do more cpu to get there.

I'm working on getting some comprehensive numbers together. Will send them out
when done.

> If it is the case the the DPR does convex faster maybe make the canDrawPath
for
> this function let convex fall through (even thought it "could" do them)?

Yeah, that's a good plan. I'll do that.

>
https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
> File src/gpu/GrTessellatingPathRenderer.cpp (right):
> 
>
https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
> src/gpu/GrTessellatingPathRenderer.cpp:25: * 2) Sort the vertices in Y (and
> secondarily in X) (merge_sort()).
> step 2 and 3 here are actually reversed in the code

[Stephen White, 2015-01-29 19:38:29]

https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/520001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:25: * 2) Sort the vertices in Y (and
secondarily in X) (merge_sort()).
On 2015/01/29 19:31:19, egdaniel wrote:
> step 2 and 3 here are actually reversed in the code

Good catch; will fix.

[Stephen White, 2015-01-29 22:28:49]

New patch up; PTAL.

[Stephen White, 2015-01-30 18:07:52]

As discussed, I've left the code in, but disabled the flag that adds it to the
path renderer chain (for now).

PTAL

[Stephen White, 2015-01-30 18:12:50]

On 2015/01/30 18:07:52, Stephen White wrote:
> As discussed, I've left the code in, but disabled the flag that adds it to the
> path renderer chain (for now).
> 
> PTAL

.. and in PS30 I've actually disabled the flag, instead of enabling it (oops).

[jvanverth1, 2015-01-30 20:48:00]

jvanverth@google.com changed reviewers:
+ reed@google.com

[jvanverth1, 2015-01-30 20:48:03]

I did another pass, but frankly it's rather hard to follow, so most of my
comments are related to that. I'm also adding Mike because he may be more
familiar with this sort of algorithm. I'll try to do another pass, but I don't
think I'll finish today.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrPathUtils.cpp
File src/gpu/GrPathUtils.cpp (right):

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrPathUtils.cpp...
src/gpu/GrPathUtils.cpp:47: if (d <= tol || !SkScalarIsFinite(d)) {
Is this an issue? When are we getting a distance of infinity?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:98: 
Could you use SkTInternalLList instead?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:131: 
The wall of text below is disconcerting. Breaking it up with some sort of
delineator between the helper classes would help a lot.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:143: SkPoint fPoint;
It's not immediately clear to me what this list (I assume it's a list) of
vertices is used for. The merge sort?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:145: Vertex* fNext;
It's not clear how the following members are used -- maybe a comment?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:214: Edge*    fRight;
It's not clear how the following members are used -- is this a winged edge data
structure?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:253: double tNumer = dy * fDX - dx * fDY;
This use of the ternary operator strikes me as a bit odd.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:575: }
Comment that this is Stage 1?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:673: 
I'm guessing all these edge methods are used by many of the main methods below
(I was expecting Stage 2) -- but it's a little unclear. Another comment?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1030: 
Stage 3. (Before Stage 2?)

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1102: 
Comment that this is Stage 2?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1134: 
Stage 4

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1192: 
Stage 5.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1349: 
Stage 6.

[Stephen White, 2015-01-30 21:36:47]

Thanks for your review.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrPathUtils.cpp
File src/gpu/GrPathUtils.cpp (right):

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrPathUtils.cpp...
src/gpu/GrPathUtils.cpp:47: if (d <= tol || !SkScalarIsFinite(d)) {
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Is this an issue? When are we getting a distance of infinity?

There's an assert which triggers in GrNextPow2() below with both the default
path renderer and the tessellating one when run in the Fuzzer if we don't check
for this here. Something in the distanceToLineSegmentBetween() function above
can return +Inf; I'm not sure of the cause.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:98: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Could you use SkTInternalLList instead?

I don't think so, because both the vertices and edges participate in multiple
linked lists, and SkTInternalLList can only do a single one
per class, since it seems to require fPrev and fNext as part of its template
contract (correct me if I'm wrong).

This implementation allows the Prev and Next members to be templated member
variables.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:131: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> The wall of text below is disconcerting. Breaking it up with some sort of
> delineator between the helper classes would help a lot.

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:143: SkPoint fPoint;
On 2015/01/30 20:48:02, jvanverth1 wrote:
> It's not immediately clear to me what this list (I assume it's a list) of
> vertices is used for. The merge sort?

It's used for both the input contours, and the merge sort. Added some comments.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:145: Vertex* fNext;
On 2015/01/30 20:48:02, jvanverth1 wrote:
> It's not clear how the following members are used -- maybe a comment?

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:214: Edge*    fRight;
On 2015/01/30 20:48:02, jvanverth1 wrote:
> It's not clear how the following members are used -- is this a winged edge
data
> structure?

Added some comments.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:253: double tNumer = dy * fDX - dx * fDY;
On 2015/01/30 20:48:02, jvanverth1 wrote:
> This use of the ternary operator strikes me as a bit odd. 

Would you prefer nested ifs?

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:575: }
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Comment that this is Stage 1?

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:673: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> I'm guessing all these edge methods are used by many of the main methods below
> (I was expecting Stage 2) -- but it's a little unclear. Another comment?

Stage 2 also does some preliminary merging of collinear edges in the original
contours, so it needs these helpers.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1030: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Stage 3. (Before Stage 2?)

Done, and moved.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1102: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Comment that this is Stage 2?

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1134: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Stage 4

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1192: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Stage 5.

Done.

https://codereview.chromium.org/855513004/diff/600001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1349: 
On 2015/01/30 20:48:02, jvanverth1 wrote:
> Stage 6.

Done.

[Stephen White, 2015-01-30 21:38:41]

New patch up. PTAL.

[Stephen White, 2015-02-17 21:04:35]

Updated to ToT.

PTAL.

[reed1, 2015-02-19 20:52:23]

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:101: {
nit: Skia places { on the same line (unless things get too wide)

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:168: bool operator<(const SkPoint& a,
const SkPoint& b) {
Very hard to find the call-sites :) Can these just be named functions like
sweep_lt or sweep_gt?

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:630: SkAutoConicToQuads converter;
I think you can hoist this outside of the loop/switch (just might improve
readability a little bit).

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1104: {
nit: Skia places { on the same line as the definition

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.h (right):

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.h:12: #include "SkTemplates.h"
Why is this guy needed?

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.h:22: virtual bool canDrawPath(const
GrDrawTarget*,
nit: Skia removes "virtual" when there is also SK_OVERRIDE

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:28: path.moveTo( 229.127044677734375,   
67.34100341796875);
These are fantastically precise values. Can you in any way simplify them and
still make them useful.

Also, they are doubles as written, and will create warnings (at least on
Windows).

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:131: path.moveTo(   389.8609619140625, 
369.326873779296875);
micro nit: this white-space formatting in fact makes it harder to compare the
actual numeric values, since the decimal-points don't align.

how about

lineTo(  470.12312321,   23.012321 );
lineTo(   70.12312321,  123.012321 );

[Stephen White, 2015-02-20 21:58:41]

THanks for your review! New patch up.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:101: {
On 2015/02/19 20:52:22, reed1 wrote:
> nit: Skia places { on the same line (unless things get too wide)

Done.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:168: bool operator<(const SkPoint& a,
const SkPoint& b) {
On 2015/02/19 20:52:22, reed1 wrote:
> Very hard to find the call-sites :) Can these just be named functions like
> sweep_lt or sweep_gt?

Done.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:630: SkAutoConicToQuads converter;
On 2015/02/19 20:52:22, reed1 wrote:
> I think you can hoist this outside of the loop/switch (just might improve
> readability a little bit).

Done.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:1104: {
On 2015/02/19 20:52:22, reed1 wrote:
> nit: Skia places { on the same line as the definition

Done.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.h (right):

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.h:12: #include "SkTemplates.h"
On 2015/02/19 20:52:22, reed1 wrote:
> Why is this guy needed?

Hysterical reasons. Removed.

https://codereview.chromium.org/855513004/diff/720001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.h:22: virtual bool canDrawPath(const
GrDrawTarget*,
On 2015/02/19 20:52:22, reed1 wrote:
> nit: Skia removes "virtual" when there is also SK_OVERRIDE

Done.

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:28: path.moveTo( 229.127044677734375,   
67.34100341796875);
On 2015/02/19 20:52:23, reed1 wrote:
> These are fantastically precise values. Can you in any way simplify them and
> still make them useful.

Sadly, no. Most were produced by fuzzing and animation, and trigger  floating
point issues which only occur with these exact values, down  to the ULP. (If
it's any consolation, many of the paths were originally hundreds of segments
long, and I whittled the paths down to the minimal reduction length.)

> Also, they are doubles as written, and will create warnings (at least on
> Windows).

Fixed.

https://codereview.chromium.org/855513004/diff/720001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:131: path.moveTo(   389.8609619140625, 
369.326873779296875);
On 2015/02/19 20:52:23, reed1 wrote:
> micro nit: this white-space formatting in fact makes it harder to compare the
> actual numeric values, since the decimal-points don't align.
> 
> how about
> 
> lineTo(  470.12312321,   23.012321 );
> lineTo(   70.12312321,  123.012321 );

Fixed (aligned on the decimal point).

[reed2, 2015-02-24 16:29:59]

reed@chromium.org changed reviewers:
+ reed@chromium.org

[reed2, 2015-02-24 16:30:02]

just some nits and comments.

deferring the rest to the GPU team.

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrPathUtils.cpp
File src/gpu/GrPathUtils.cpp (right):

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrPathUtils.cpp...
src/gpu/GrPathUtils.cpp:102: if (d <= tol || !SkScalarIsFinite(d)) {
FYI : Seems like the changes to this file could land independent of the larger
CL.

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:241: double   fDX;               // The
line equation for this edge, in implicit form.
Did you try using SkScalar first, and it failed for some reason? If so, we might
document that, to make it clear why this code is different than most of the rest
of skia (which uses scalars for intermediates). Do you have a repro-case that
forced you to use doubles?

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:274: if (denom > 0.0 ? (sNumer < 0.0 ||
sNumer > denom || tNumer < 0.0 || tNumer > denom)
// We check that the result of the divide (sNumer / denom) will be 0 <= ... < 1

I wonder if it might be simpler to read if we just always did the divide, and
then check s?

Alternatively, should have add an assert to s to confirm the above check?

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:584: SkPoint q[] = {
nit: can q[] and r[] be const?

[Stephen White, 2015-02-24 18:45:16]

Thanks for your review. New patch up.

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrPathUtils.cpp
File src/gpu/GrPathUtils.cpp (right):

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrPathUtils.cpp...
src/gpu/GrPathUtils.cpp:102: if (d <= tol || !SkScalarIsFinite(d)) {
On 2015/02/24 16:30:01, reed2 wrote:
> FYI : Seems like the changes to this file could land independent of the larger
> CL.

Done: https://codereview.chromium.org/951403002/

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:241: double   fDX;               // The
line equation for this edge, in implicit form.
On 2015/02/24 16:30:01, reed2 wrote:
> Did you try using SkScalar first, and it failed for some reason? If so, we
might
> document that, to make it clear why this code is different than most of the
rest
> of skia (which uses scalars for intermediates). Do you have a repro-case that
> forced you to use doubles?

Added a comment.

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:274: if (denom > 0.0 ? (sNumer < 0.0 ||
sNumer > denom || tNumer < 0.0 || tNumer > denom)
On 2015/02/24 16:30:01, reed2 wrote:
> // We check that the result of the divide (sNumer / denom) will be 0 <= ... <
1
> 
> I wonder if it might be simpler to read if we just always did the divide, and
> then check s?

See the comment above "struct Edge {". It would be simpler, but slower (that's
how it was originally written). The optimization is to only do the divide in the
case where there's an actual intersection.

> Alternatively, should have add an assert to s to confirm the above check?

Done. Floating point issues being what they are, it wouldn't surprise me if this
fires even when it "shouldn't", but I'll leave it in for now.

https://codereview.chromium.org/855513004/diff/820001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:584: SkPoint q[] = {
On 2015/02/24 16:30:01, reed2 wrote:
> nit: can q[] and r[] be const?

Done.

[egdaniel, 2015-02-25 15:46:10]

https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:591: if (pointsLeft < 2 || (d1 < tolSqd
&& d2 < tolSqd) || !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
100 chars

https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:228: static void test_concave_paths(SkSurface*
surface, skiatest::Reporter* reporter) {
So I feel like what is being tested here are cases that you have found that test
your tessellation in very specific ways and does so through high level canvas
draw commands. Especially since this path renderer won't even be on, these test
cases really aren't testing you tessellation.

I feel like a better solution would be to somehow privately expose the functions
in your tessellator and unit test those specifically with some of these corner
cases you listed here. That we can verify your tessellator continues to work
regardless of the current state of turning the path renderer on.

[Stephen White, 2015-02-25 16:37:23]

Thanks for your review.

https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
File src/gpu/GrTessellatingPathRenderer.cpp (right):

https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
src/gpu/GrTessellatingPathRenderer.cpp:591: if (pointsLeft < 2 || (d1 < tolSqd
&& d2 < tolSqd) || !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
On 2015/02/25 15:46:10, egdaniel wrote:
> 100 chars

Fixed.

https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests.cpp
File tests/ConcavePathTests.cpp (right):

https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests....
tests/ConcavePathTests.cpp:228: static void test_concave_paths(SkSurface*
surface, skiatest::Reporter* reporter) {
On 2015/02/25 15:46:10, egdaniel wrote:
> So I feel like what is being tested here are cases that you have found that
test
> your tessellation in very specific ways and does so through high level canvas
> draw commands. Especially since this path renderer won't even be on, these
test
> cases really aren't testing you tessellation.
> 
> I feel like a better solution would be to somehow privately expose the
functions
> in your tessellator and unit test those specifically with some of these corner
> cases you listed here. That we can verify your tessellator continues to work
> regardless of the current state of turning the path renderer on.

I hear what you're saying, but adding hooks to allow that type of testing would
be a big impact to the code, and may impact performance as well.

I've removed the tests from the build for now, and will re-enable when the
tessellator is enabled.

[egdaniel, 2015-02-25 17:01:21]

On 2015/02/25 16:37:23, Stephen White wrote:
> Thanks for your review.
> 
>
https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
> File src/gpu/GrTessellatingPathRenderer.cpp (right):
> 
>
https://codereview.chromium.org/855513004/diff/880001/src/gpu/GrTessellatingP...
> src/gpu/GrTessellatingPathRenderer.cpp:591: if (pointsLeft < 2 || (d1 < tolSqd
> && d2 < tolSqd) || !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
> On 2015/02/25 15:46:10, egdaniel wrote:
> > 100 chars
> 
> Fixed.
> 
>
https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests.cpp
> File tests/ConcavePathTests.cpp (right):
> 
>
https://codereview.chromium.org/855513004/diff/880001/tests/ConcavePathTests....
> tests/ConcavePathTests.cpp:228: static void test_concave_paths(SkSurface*
> surface, skiatest::Reporter* reporter) {
> On 2015/02/25 15:46:10, egdaniel wrote:
> > So I feel like what is being tested here are cases that you have found that
> test
> > your tessellation in very specific ways and does so through high level
canvas
> > draw commands. Especially since this path renderer won't even be on, these
> test
> > cases really aren't testing you tessellation.
> > 
> > I feel like a better solution would be to somehow privately expose the
> functions
> > in your tessellator and unit test those specifically with some of these
corner
> > cases you listed here. That we can verify your tessellator continues to work
> > regardless of the current state of turning the path renderer on.
> 
> I hear what you're saying, but adding hooks to allow that type of testing
would
> be a big impact to the code, and may impact performance as well.
> 
> I've removed the tests from the build for now, and will re-enable when the
> tessellator is enabled.

Just re-adding when we enable tessellator is not really the problem/solution.
Since these test rely on a whole stack of calls throughout skia to eventually
even fall into the tesselator code path (this is what gm's do), any chances
along this stack of calls can change these tests.

A solution, especially since your GrTessellatingPathRenderer (GrTPR) is not
public, is to include the header in your test file and create some entry
functions in GrTPR that allow you to test it (for example a function that takes
in SKPath and does what it needs to do to test). Setting it up like this opens a
way to more easily add new specific tests in GrTPR. Doing this should have no
impact on actual performance outside of testing.

[egdaniel, 2015-02-25 21:47:03]

lgtm, but anyone else can feel free to jump in

[bsalomon, 2015-02-25 21:55:25]

On 2015/02/25 21:47:03, egdaniel wrote:
> lgtm, but anyone else can feel free to jump in

lgtm, let's land it

[Stephen White, 2015-02-26 14:52:16]

The CQ bit was checked by senorblanco@chromium.org

[commit-bot: I haz the power, 2015-02-26 14:53:02]

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

[commit-bot: I haz the power, 2015-02-26 14:58:22]

Committed patchset #50 (id:990001) as
https://skia.googlesource.com/skia/+/d6ed19cc751463285491a538bc7bf154cc7e6d8c