aboutsummaryrefslogtreecommitdiffhomepage
path: root/gm/concavepaths.cpp
Commit message (Collapse)AuthorAge
* GrTessellator: implement out-of-range splitting and AEL rewinding.Gravatar Stephen White2017-06-07
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Due to floating point inaccuracy, when intersecting edges, the intersection point may fall above one of the edges' top vertices or below one of the bottom vertices. In these cases, we were simply splitting one edge on the relevant endpoint of the other edge. This is incorrect if the intersection is far from the endpoint (e.g., the test case in the linked bug, where one of the intersected edges is near-horizontal but the intersection falls below both of its endpoints, in the middle of the edge.) The correct solution is to split both edges as normal, and take care to produce edges with the correct ordering where the intersection is above or below an edge. However, since the new vertex may be above the current vertex, simply restarting intersection checks at the current vertex won't work. We need to process the intersection vertex before the current one. This introduces another problem: unlike all other splitting modes (which always shorten edges), splitting an edge above the top or below the bottom can lengthen it, causing it to violate the AEL with an adjacent edge which then shortens it back to the original point (in cleanup_active_edges()). Since the splitting and merging code can't agree, we loop forever. Instead of simply fusing neighboring edges in cleanup_active_edges(), the proper fix to this problem is to detect the AEL violation and rewind all processing to the vertex above it. For performance, we only rewind when we detect that a split edge is no longer ordered within the mesh (merge_enclosing_edges()) or within the the AEL (rewind_if_necessary()). We also store the enclosing edges of each vertex, which allows us to rewind quickly, since we know exactly which edges need to be added/removed from the AEL. cleanup_active_edges(), fix_active_state() and Vertex::fProcessed have been removed. In their place are rewind_active_edges() and rewind_if_necessary(), which uses the same logic as cleanup_active_edges() but uses it to know when to rewind. Bug: skia:5026 Change-Id: I3638a429f5428498d6df6bb7b98c67374dc291aa Reviewed-on: https://skia-review.googlesource.com/18900 Reviewed-by: Brian Salomon <bsalomon@google.com> Commit-Queue: Stephen White <senorblanco@chromium.org>
* GrTessellator (AA): fix "Canvas Arcs" coverage artifact.Gravatar Stephen White2017-02-13
| | | | | | | | | | | | | | | | | When sanitizing contours, if the first and last vertices coincide, continue with the previous vertex, not the next vertex, since we may otherwise exit prematurely. Also, round the last vertex before entering the loop, just in case it coincides with the first. Add a test case to exercise the above, and another one which exercises the intruding-vertex workaround. BUG=691593 Change-Id: Ic28a9308a21164d185edef0ee6fbc29b40742149 Reviewed-on: https://skia-review.googlesource.com/8364 Reviewed-by: Brian Salomon <bsalomon@google.com> Commit-Queue: Stephen White <senorblanco@chromium.org>
* Switch a bunch of tests to use DEF_SIMPLE_GM.Gravatar Stephen White2017-01-13
| | | | | | | | | | | Should be no user- or test-visible changes. BUG=skia: Change-Id: I6499dc978a41fee344b847c118f84227271561c5 Reviewed-on: https://skia-review.googlesource.com/6906 Reviewed-by: Brian Salomon <bsalomon@google.com> Commit-Queue: Stephan White <senorblanco@chromium.org>
* Quality and performance fixes for AA tessellating path renderer.Gravatar Stephen White2017-01-03
| | | | | | | | | | | | | | | | | | | | | | | | | | Use quads rather than triangles for the edge geometry. This allows us to perform a simpler edge categorization (see below). It also improves performance by reducing the number of edges processed during the simplify and tessellate steps. Label AA edges as three types: inner, outer, and connector. This results in correct alpha values for intersected edges, even when the top or bottom vertex has been merged with a vertex on edges of different types. Changed the "collinear edges" sample from the concavepaths GM for a "fast-foward" shape, which more clearly shows the problem being fixed here. (The collinearity from the "collinear edges" was actually being removed earlier up the stack, causing the path to become convex and not exercise the concave path renderers anyway.) NOTE: this will cause changes in the "concavepaths" GM results, and minor pixel diffs in a number of other tests. Change-Id: I6c2b0cdb35cda42b01cf1100621271fef5be35b0 Reviewed-on: https://skia-review.googlesource.com/6430 Reviewed-by: Stephan White <senorblanco@chromium.org> Commit-Queue: Stephan White <senorblanco@chromium.org>
* Revert "Quality and performance fixes for AA tessellating path renderer."Gravatar Stephan White2017-01-03
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit d4b21552481a6d313dfa9bc14b624c9ec94b56ce. Reason for revert: accidentally added some unwanted changes Original change's description: > Quality and performance fixes for AA tessellating path renderer. > > Use quads rather than triangles for the edge geometry. This allows > us to perform a simpler edge categorization (see below). It also > improves performance by reducing the number of edges processed during > the simplify and tessellate steps. > > Label AA edges as three types: inner, outer, and connector. This > results in correct alpha values for intersected edges, even when > the top or bottom vertex has been merged with a vertex on edges > of different types. > > Changed the "collinear edges" sample from the concavepaths GM for a > "fast-foward" shape, which more clearly shows the problem being fixed > here. (The collinearity from the "collinear edges" was actually being > removed earlier up the stack, causing the path to become convex and > not exercise the concave path renderers anyway.) > > NOTE: this will cause changes in the "concavepaths" GM results, and > minor pixel diffs in a number of other tests. > > BUG=660893 > > Change-Id: Ide49374d6d173404c7223f7316dd439df1435787 > Reviewed-on: https://skia-review.googlesource.com/6427 > Commit-Queue: Stephan White <senorblanco@chromium.org> > Reviewed-by: Brian Salomon <bsalomon@google.com> > TBR=bsalomon@google.com,senorblanco@chromium.org,reviews@skia.org BUG=660893 NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Change-Id: I06a36e397645bfc42442a5a9e7c27328f6048ab9 Reviewed-on: https://skia-review.googlesource.com/6428 Commit-Queue: Stephan White <senorblanco@chromium.org> Reviewed-by: Stephan White <senorblanco@chromium.org>
* Quality and performance fixes for AA tessellating path renderer.Gravatar Stephen White2017-01-03
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Use quads rather than triangles for the edge geometry. This allows us to perform a simpler edge categorization (see below). It also improves performance by reducing the number of edges processed during the simplify and tessellate steps. Label AA edges as three types: inner, outer, and connector. This results in correct alpha values for intersected edges, even when the top or bottom vertex has been merged with a vertex on edges of different types. Changed the "collinear edges" sample from the concavepaths GM for a "fast-foward" shape, which more clearly shows the problem being fixed here. (The collinearity from the "collinear edges" was actually being removed earlier up the stack, causing the path to become convex and not exercise the concave path renderers anyway.) NOTE: this will cause changes in the "concavepaths" GM results, and minor pixel diffs in a number of other tests. BUG=660893 Change-Id: Ide49374d6d173404c7223f7316dd439df1435787 Reviewed-on: https://skia-review.googlesource.com/6427 Commit-Queue: Stephan White <senorblanco@chromium.org> Reviewed-by: Brian Salomon <bsalomon@google.com>
* Tessellator: stop copying vertices into Polys and Monotones.Gravatar senorblanco2016-06-02
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 Review-Url: https://codereview.chromium.org/2029243002
* Use DEF_GM everywhereGravatar scroggo2015-12-10
| | | | | | BUG=skia:1902 Review URL: https://codereview.chromium.org/1518893002
* IWYU: 'core' target, files starting A-C.Gravatar bungeman2015-08-05
| | | | | | | | | TBR=reed@google.com Verbal lgtm, does not change API. Committed: https://skia.googlesource.com/skia/+/7403d87db8e43d4c2b5b25ac22a0ebc22bd09d69 Review URL: https://codereview.chromium.org/1265033002
* Revert of IWYU: 'core' target, files starting A-C. (patchset #5 id:80001 of ↵Gravatar reed2015-08-04
| | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1265033002/ ) Reason for revert: revert to unblock DEPS roll ../../chrome/browser/chromeos/display/overscan_calibrator.cc:43:10: error: variable has incomplete type 'SkPath' SkPath base_path; Original issue's description: > IWYU: 'core' target, files starting A-C. > > TBR=reed@google.com > Verbal lgtm, does not change API. > > Committed: https://skia.googlesource.com/skia/+/7403d87db8e43d4c2b5b25ac22a0ebc22bd09d69 TBR=reed@google.com,mtklein@google.com,bungeman@google.com NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1273613002
* IWYU: 'core' target, files starting A-C.Gravatar bungeman2015-08-04
| | | | | | | TBR=reed@google.com Verbal lgtm, does not change API. Review URL: https://codereview.chromium.org/1265033002
* C++11 override should now be supported by all of {bots,Chrome,Android,Mozilla}Gravatar mtklein2015-03-25
| | | | | | | | | NOPRESUBMIT=true BUG=skia: DOCS_PREVIEW= https://skia.org/?cl=1037793002 Review URL: https://codereview.chromium.org/1037793002
* Tessellating GPU path renderer.Gravatar senorblanco2015-02-26
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: Review URL: https://codereview.chromium.org/855513004