GrTessellator (AA): implement fast path for non-intersecting geometry.
authorStephen White <senorblanco@chromium.org>
Mon, 13 Mar 2017 19:10:13 +0000 (15:10 -0400)
committerSkia Commit-Bot <skia-commit-bot@chromium.org>
Mon, 13 Mar 2017 19:45:36 +0000 (19:45 +0000)
commitbda29c076bf3d6811bde142d57e54e5792727481
treeba715479d76ce646b25fd6e3696f6dd02abfb484
parenta368bb31184d07fca9bc543e0566a71a4a2f09c0
GrTessellator (AA): implement fast path for non-intersecting geometry.

In the common case, there are no intersections in the inner or outer
meshes generated for edge-AA. In that case, we don't have to build
connector edges, and we don't need to run the full simplify and
tessellate path on the full combined mesh. In order to maintain the
correspondence between inner and outer meshes, we can keep partner
pointers between inner and outer vertices instead.

So the new flow is:

- stroke the original boundaries to generate inner & outer meshes
- assign partner pointers to join inner & outer vertices
- build Edges only for Inner and Outer contours
- sort the two meshes independently
- do a complexity check on both meshes (simplified Bentley-Ottmann that
  just aborts on the first found intersection)
- if neither mesh is complex, use the fast path:
  - tessellate only the inner mesh
  - return the outer mesh, and use the partner pointers to generate
    the outer geometry triangles
- otherwise, use the complex path (as before):
  - connect the inner & outer partners with Connector Edges
  - merge the inner & outer meshes via sorted_merge()
  - simplify and tessellate the resulting complete mesh

On a 2012 Retina MBP (Intel), this yields:
Canvas Arcs +6%
Stroke Shapes +6%
Fill Shapes +15%

On a Z620 Ubuntu w/NVidia GTX 650:
Canvas Arcs: +5.0%
Stroke Shapes: +1.8%
Fill Shapes: +17.6%

Other changes:

- implemented VertexList::append(VertexList), for use by sorted_merge()
- renamed boundary_to_aa_mesh() to stroke_boundary(), and made it append
  inner & outer contours to inner & outer meshes
- the connect() loop at the bottom of stroke_boundary() now uses open
  VertexLists, since it can then append them easily to the inner & outer meshes
- sort_and_simplify() changed to sort_mesh(), with merging and simplification
  done explicitly by the callers
- sorted_merge() factored out of merge_sort(), for use when zipping together
  the inner and outer meshes

Change-Id: Ib00f9f12a375412eff35dd2bb78ccd787d9c37ce
Reviewed-on: https://skia-review.googlesource.com/9600
Commit-Queue: Stephen White <senorblanco@chromium.org>
Reviewed-by: Brian Salomon <bsalomon@google.com>
src/gpu/GrTessellator.cpp