Tessellator: stop copying vertices into Polys and Monotones.

Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

2) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

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

Committed: https://skia.googlesource.com/skia/+/531237ef3aaf0d3c86e0853fde3b4c8f517bc662

[Stephen White, 2016-06-01 20:39:16]

Description was changed from

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the tesselator are
copied into the Polys and MonotonePolys it produces. This is
necessary because each vertex may have an arbitrary valence, since it
may participate in an arbitrary number of Polys, so we can't use the
vertex's prev/next pointers to represent all the Monotones of which
this vertex may be a member.

However, each Edge can only be a member of two Polys (one on each side
of the edge). So by adding two prev/next pointer pairs to each Edge,
we can represent each Monotone as a list of edges instead. Then we
no longer need to copy the vertices.

One wrinkle is that the ear-clipping stage (6) of the tessellator
does require prev/next pointers, in order to remove vertices as
their ears are clipped. So we convert the edge list into a vertex
list during Monotone::emit(), using the prev/next pointers temporarily
for that monotone.

This change improves performance by 7-20% a non-caching version of the
tessellator, and reduces memory use.
==========

to

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the tesselator are
copied into the Polys and MonotonePolys it produces. This is
necessary because each vertex may have an arbitrary valence, since it
may participate in an arbitrary number of Polys, so we can't use the
vertex's prev/next pointers to represent all the Monotones of which
this vertex may be a member.

However, each Edge can only be a member of two Polys (one on each side
of the edge). So by adding two prev/next pointer pairs to each Edge,
we can represent each Monotone as a list of edges instead. Then we
no longer need to copy the vertices.

One wrinkle is that the ear-clipping stage (6) of the tessellator
does require prev/next pointers, in order to remove vertices as
their ears are clipped. So we convert the edge list into a vertex
list during Monotone::emit(), using the prev/next pointers temporarily
for that monotone.

This change improves performance by 7-20% a non-caching version of the
tessellator, and reduces memory use.
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2029243002
==========

[Stephen White, 2016-06-01 20:48:22]

The CQ bit was checked by senorblanco@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-06-01 20:48:32]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2029243002/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2029243002/1

[Stephen White, 2016-06-01 20:48:57]

Description was changed from

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the tesselator are
copied into the Polys and MonotonePolys it produces. This is
necessary because each vertex may have an arbitrary valence, since it
may participate in an arbitrary number of Polys, so we can't use the
vertex's prev/next pointers to represent all the Monotones of which
this vertex may be a member.

However, each Edge can only be a member of two Polys (one on each side
of the edge). So by adding two prev/next pointer pairs to each Edge,
we can represent each Monotone as a list of edges instead. Then we
no longer need to copy the vertices.

One wrinkle is that the ear-clipping stage (6) of the tessellator
does require prev/next pointers, in order to remove vertices as
their ears are clipped. So we convert the edge list into a vertex
list during Monotone::emit(), using the prev/next pointers temporarily
for that monotone.

This change improves performance by 7-20% a non-caching version of the
tessellator, and reduces memory use.
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2029243002
==========

to

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the tesselator are
copied into the Polys and MonotonePolys it produces. This is
necessary because each vertex may have an arbitrary valence, since it
may participate in an arbitrary number of Polys, so we can't use the
vertex's prev/next pointers to represent all the Monotones of which
this vertex may be a member.

However, each Edge can only be a member of two Polys (one on each side
of the edge). So by adding two prev/next pointer pairs to each Edge,
we can represent each Monotone as a list of edges instead. Then we
no longer need to copy the vertices.

One wrinkle is that the ear-clipping stage (6) of the tessellator
does require prev/next pointers, in order to remove vertices as
their ears are clipped. So we convert the edge list into a vertex
list during Monotone::emit(), using the prev/next pointers temporarily
for that monotone.

This change improves performance by 7-20% on a non-caching version of the
tessellator, and reduces memory use.
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2029243002
==========

[Stephen White, 2016-06-01 20:48:57]

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

[Stephen White, 2016-06-01 21:00:11]

Description was changed from

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the tesselator are
copied into the Polys and MonotonePolys it produces. This is
necessary because each vertex may have an arbitrary valence, since it
may participate in an arbitrary number of Polys, so we can't use the
vertex's prev/next pointers to represent all the Monotones of which
this vertex may be a member.

However, each Edge can only be a member of two Polys (one on each side
of the edge). So by adding two prev/next pointer pairs to each Edge,
we can represent each Monotone as a list of edges instead. Then we
no longer need to copy the vertices.

One wrinkle is that the ear-clipping stage (6) of the tessellator
does require prev/next pointers, in order to remove vertices as
their ears are clipped. So we convert the edge list into a vertex
list during Monotone::emit(), using the prev/next pointers temporarily
for that monotone.

This change improves performance by 7-20% on a non-caching version of the
tessellator, and reduces memory use.
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2029243002
==========

to

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) VertexList was refactored into List<T>, and reused
for the MonotonePoly list.

2) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

3) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

4) Partnering is handled a bit differently: Poly::addEdge() 
(formerly addVertex()) now transfers the partner's Monotone 
into this Poly, so it doesn't need a return value. This 
means we don't need to reassign leftPoly/rightPoly in the 
tessellate() loops, simplifying the code.

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

[Stephen White, 2016-06-01 21:03:04]

Rob: PTAL. Thanks!

[commit-bot: I haz the power, 2016-06-01 21:05:38]

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

[commit-bot: I haz the power, 2016-06-01 21:05:39]

Dry run: This issue passed the CQ dry run.

[robertphillips, 2016-06-02 12:19:48]

lgtm (as far as I understand it all)

https://codereview.chromium.org/2029243002/diff/1/src/gpu/GrTessellator.cpp
File src/gpu/GrTessellator.cpp (right):

https://codereview.chromium.org/2029243002/diff/1/src/gpu/GrTessellator.cpp#n...
src/gpu/GrTessellator.cpp:415: e->fBottom->fPoint.fX, e->fBottom->fPoint.fY,
Does the "neither" case still make sense ?

https://codereview.chromium.org/2029243002/diff/1/src/gpu/GrTessellator.cpp#n...
src/gpu/GrTessellator.cpp:1216: if (v->fFirstEdgeAbove) {
Either "nullptr != e" or "e" ?

[Stephen White, 2016-06-02 18:01:21]

https://codereview.chromium.org/2029243002/diff/1/src/gpu/GrTessellator.cpp
File src/gpu/GrTessellator.cpp (right):

https://codereview.chromium.org/2029243002/diff/1/src/gpu/GrTessellator.cpp#n...
src/gpu/GrTessellator.cpp:415: e->fBottom->fPoint.fX, e->fBottom->fPoint.fY,
On 2016/06/02 12:19:48, robertphillips wrote:
> Does the "neither" case still make sense ?

Good point. Removed.

[Stephen White, 2016-06-02 18:02:56]

It turns out this CL had a bug which was not caught by 
existing GMs. I've added a test case to make sure I don't
break it in future, and reverted the refactoring/simplification part of the
change for now.

PTAL. It's now closer to the existing code, so diffing 
against the original might be easiest.

[Stephen White, 2016-06-02 18:03:03]

The CQ bit was checked by senorblanco@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-06-02 18:03:13]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2029243002/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2029243002/40001

[Stephen White, 2016-06-02 18:07:04]

Description was changed from

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) VertexList was refactored into List<T>, and reused
for the MonotonePoly list.

2) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

3) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

4) Partnering is handled a bit differently: Poly::addEdge() 
(formerly addVertex()) now transfers the partner's Monotone 
into this Poly, so it doesn't need a return value. This 
means we don't need to reassign leftPoly/rightPoly in the 
tessellate() loops, simplifying the code.

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

to

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

2) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

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

[Stephen White, 2016-06-02 18:07:49]

The CQ bit was checked by senorblanco@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-06-02 18:07:53]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2029243002/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2029243002/60001

[robertphillips, 2016-06-02 18:12:02]

lgtm

https://codereview.chromium.org/2029243002/diff/60001/src/gpu/GrTessellator.cpp
File src/gpu/GrTessellator.cpp (right):

https://codereview.chromium.org/2029243002/diff/60001/src/gpu/GrTessellator.c...
src/gpu/GrTessellator.cpp:349: , fNext(nullptr) {
this-> ?

[Stephen White, 2016-06-02 18:18:47]

https://codereview.chromium.org/2029243002/diff/60001/src/gpu/GrTessellator.cpp
File src/gpu/GrTessellator.cpp (right):

https://codereview.chromium.org/2029243002/diff/60001/src/gpu/GrTessellator.c...
src/gpu/GrTessellator.cpp:349: , fNext(nullptr) {
On 2016/06/02 18:12:02, robertphillips wrote:
> this-> ?

Done.

[Stephen White, 2016-06-02 18:19:23]

The CQ bit was checked by senorblanco@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-06-02 18:19:33]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2029243002/80001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2029243002/80001

[commit-bot: I haz the power, 2016-06-02 18:34:26]

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

[commit-bot: I haz the power, 2016-06-02 18:34:27]

Dry run: This issue passed the CQ dry run.

[Stephen White, 2016-06-02 18:35:48]

The CQ bit was checked by senorblanco@chromium.org

[Stephen White, 2016-06-02 18:35:48]

The patchset sent to the CQ was uploaded after l-g-t-m from
robertphillips@google.com
Link to the patchset: https://codereview.chromium.org/2029243002/#ps80001
(title: "Fix style per review")

[commit-bot: I haz the power, 2016-06-02 18:35:55]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2029243002/80001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/2029243002/80001

[commit-bot: I haz the power, 2016-06-02 18:36:54]

Description was changed from

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

2) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

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

to

==========
Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the 
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an 
arbitrary valence, since it may participate in an arbitrary 
number of Polys, so we can't use the vertex's prev/next 
pointers to represent all the Monotones of which this 
vertex may be a member.

However, each Edge can only be a member of two Polys (one 
on each side of the edge). So by adding two prev/next 
pointer pairs to each Edge, we can represent each Monotone 
as a list of edges instead. Then we no longer need to copy 
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to 
remove vertices as their ears are clipped. So we convert 
the edge list into a vertex list during Monotone::emit(), 
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching 
version of the tessellator, and reduces memory use.

Other notes: 

1) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom 
vertex is seen.

2) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no 
return value.

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

Committed:
https://skia.googlesource.com/skia/+/531237ef3aaf0d3c86e0853fde3b4c8f517bc662
==========

[commit-bot: I haz the power, 2016-06-02 18:36:55]

Committed patchset #5 (id:80001) as
https://skia.googlesource.com/skia/+/531237ef3aaf0d3c86e0853fde3b4c8f517bc662