Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(9)

Issue 131103009: update pathops to circle sort (Closed)

Created:
6 years, 11 months ago by caryclark
Modified:
6 years, 8 months ago
Reviewers:
mtklein, reed1
CC:
skia-review_googlegroups.com
Base URL:
https://skia.googlesource.com/skia.git@master
Visibility:
Public.

Description

Mike R: please sanity check SkPostConfig.h Mike K: please sanity check Test.cpp and skia_test.cpp Feel free to look at the rest, but I don't expect any in depth review of path ops innards. Path Ops first iteration used QuickSort to order segments radiating from an intersection to compute the winding rule. This revision uses a circular sort instead. Breaking out the circular sort into its own long-lived structure (SkOpAngle) allows doing less work and provides a home for caching additional sorting data. The circle sort is more stable than the former sort, has a robust ordering and fewer exceptions. It finds unsortable ordering less often. It is less reliant on the initial curve tangent, using convex hulls instead whenever it can. Additional debug validation makes sure that the computed structures are self-consistent. A new visualization tool helps verify that the angle ordering is correct. The 70+M tests pass with this change on Windows, Mac, Linux 32 and Linux 64 in debug and release. Committed: http://code.google.com/p/skia/source/detail?r=14183

Patch Set 1 #

Patch Set 2 : use half plane rule #

Patch Set 3 : laptop wip #

Patch Set 4 : remove visualizer #

Patch Set 5 : unit test works #

Patch Set 6 : first cut moving ideas into op angle #

Patch Set 7 : working on simplify quad 18 #

Patch Set 8 : up to testQuad9 #

Patch Set 9 : working on Quad8 #

Patch Set 10 : fix on mac #

Patch Set 11 : working on quadratic51 #

Patch Set 12 : all simplify tests working with circle sort #

Patch Set 13 : start on cubics and binary ops #

Patch Set 14 : fixed small coincidence detection #

Patch Set 15 : checkpoint up to cubicOp61d #

Patch Set 16 : tests up to carpetplanet working #

Patch Set 17 : simplify + op tests working #

Patch Set 18 : working on degenerate failures #

Patch Set 19 : found bug regarding angles on stack #

Patch Set 20 : checkpoint #

Patch Set 21 : dot product goes to zero #

Patch Set 22 : fix for linux #

Patch Set 23 : checkpoint: all but PathOpsSkp* run #

Patch Set 24 : tracking down joomla #

Patch Set 25 : all work except skpbreakmystyle which fails flakily #

Patch Set 26 : delete large file #

Patch Set 27 : fix sort when ray intersects three or more points #

Patch Set 28 : quadratic threaded passes #

Patch Set 29 : simplify angle::after #

Patch Set 30 : allow ternary order sorting #

Patch Set 31 : all basic tests working -- some bug when debugging is disabled #

Patch Set 32 : working on rewrite of findtop #

Patch Set 33 : all 73M tests, save testQuads46x, working #

Patch Set 34 : no failures extended release, non-extended debug #

Patch Set 35 : fix linux build #

Patch Set 36 : fix release w/ printf build (linux 32 fails mysteriously) #

Patch Set 37 : fix debugging release builds on linux #

Patch Set 38 : pass name of test all the way down #

Patch Set 39 : fix 32/64 debug/release linux #

Patch Set 40 : clean up code -- remove experiments, dead code, move debug code #

Patch Set 41 : fix one non-circle sort test, verify remaining tests work less one #

Patch Set 42 : added a couple of new skp failures #

Patch Set 43 : fix several of the new failures uncovered by new skps #

Patch Set 44 : fix one more skp test -- fix is incomplete proof of concept #

Patch Set 45 : fix last break in current skp set #

Patch Set 46 : disable old test that still fails on linux 32 release #

Unified diffs Side-by-side diffs Delta from patch set Stats (+10298 lines, -3415 lines) Patch
M gyp/pathops_unittest.gyp View 1 2 3 4 5 6 7 8 9 25 1 chunk +2 lines, -0 lines 0 comments Download
M include/core/SkPostConfig.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 43 1 chunk +5 lines, -3 lines 0 comments Download
M src/pathops/SkAddIntersections.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 25 1 chunk +2 lines, -2 lines 0 comments Download
M src/pathops/SkDCubicIntersection.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 1 chunk +4 lines, -1 line 0 comments Download
M src/pathops/SkDCubicToQuads.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 25 1 chunk +0 lines, -1 line 0 comments Download
M src/pathops/SkDLineIntersection.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 2 chunks +7 lines, -1 line 0 comments Download
M src/pathops/SkDQuadIntersection.cpp View 1 2 3 4 5 6 7 8 9 10 25 4 chunks +10 lines, -8 lines 0 comments Download
M src/pathops/SkDQuadLineIntersection.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4 chunks +6 lines, -41 lines 0 comments Download
M src/pathops/SkIntersectionHelper.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 2 chunks +5 lines, -15 lines 0 comments Download
M src/pathops/SkIntersections.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 2 chunks +0 lines, -3 lines 0 comments Download
M src/pathops/SkIntersections.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1 chunk +0 lines, -14 lines 0 comments Download
M src/pathops/SkLineParameters.h View 3 25 5 chunks +42 lines, -38 lines 0 comments Download
M src/pathops/SkOpAngle.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4 chunks +68 lines, -32 lines 0 comments Download
M src/pathops/SkOpAngle.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4 chunks +913 lines, -301 lines 0 comments Download
M src/pathops/SkOpContour.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 7 chunks +49 lines, -5 lines 0 comments Download
M src/pathops/SkOpContour.cpp View 1 2 3 4 5 6 7 8 9 10 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 2 chunks +17 lines, -0 lines 0 comments Download
M src/pathops/SkOpSegment.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 15 chunks +138 lines, -53 lines 0 comments Download
M src/pathops/SkOpSegment.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 67 chunks +1346 lines, -896 lines 0 comments Download
M src/pathops/SkOpSpan.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 25 1 chunk +9 lines, -5 lines 0 comments Download
M src/pathops/SkPathOpsCommon.h View 1 2 3 4 5 6 7 8 9 10 25 1 chunk +2 lines, -2 lines 0 comments Download
M src/pathops/SkPathOpsCommon.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 12 chunks +106 lines, -52 lines 0 comments Download
M src/pathops/SkPathOpsCubic.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1 chunk +3 lines, -3 lines 0 comments Download
M src/pathops/SkPathOpsCubic.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 2 chunks +4 lines, -17 lines 0 comments Download
M src/pathops/SkPathOpsCurve.h View 1 2 3 4 5 6 25 2 chunks +26 lines, -0 lines 0 comments Download
M src/pathops/SkPathOpsDebug.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 5 chunks +44 lines, -4 lines 0 comments Download
M src/pathops/SkPathOpsDebug.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 2 chunks +499 lines, -48 lines 0 comments Download
M src/pathops/SkPathOpsLine.h View 1 2 3 4 5 6 7 8 9 10 11 25 1 chunk +1 line, -3 lines 0 comments Download
M src/pathops/SkPathOpsLine.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1 chunk +0 lines, -10 lines 0 comments Download
M src/pathops/SkPathOpsOp.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 7 chunks +30 lines, -54 lines 0 comments Download
M src/pathops/SkPathOpsPoint.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 6 chunks +40 lines, -19 lines 0 comments Download
M src/pathops/SkPathOpsQuad.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1 chunk +4 lines, -3 lines 0 comments Download
M src/pathops/SkPathOpsQuad.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 3 chunks +6 lines, -19 lines 0 comments Download
M src/pathops/SkPathOpsSimplify.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 3 chunks +9 lines, -6 lines 0 comments Download
M src/pathops/SkPathOpsTypes.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 9 chunks +60 lines, -19 lines 0 comments Download
M src/pathops/SkPathWriter.h View 1 2 3 4 5 6 7 8 9 10 25 1 chunk +0 lines, -1 line 0 comments Download
M src/pathops/SkQuarticRoot.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 25 2 chunks +5 lines, -2 lines 0 comments Download
A tests/PathOpsAngleIdeas.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 1 chunk +858 lines, -0 lines 0 comments Download
M tests/PathOpsAngleTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 3 chunks +404 lines, -161 lines 0 comments Download
M tests/PathOpsCubicIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 25 7 chunks +13 lines, -12 lines 0 comments Download
M tests/PathOpsCubicLineIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 3 chunks +21 lines, -15 lines 0 comments Download
M tests/PathOpsCubicQuadIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 3 chunks +246 lines, -38 lines 0 comments Download
A tests/PathOpsDebug.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 1 chunk +568 lines, -0 lines 0 comments Download
M tests/PathOpsExtendedTest.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 2 chunks +9 lines, -6 lines 0 comments Download
M tests/PathOpsExtendedTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 22 chunks +94 lines, -65 lines 0 comments Download
M tests/PathOpsInverseTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 1 chunk +1 line, -1 line 0 comments Download
M tests/PathOpsOpCubicThreadedTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 2 chunks +2 lines, -1 line 0 comments Download
M tests/PathOpsOpRectThreadedTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 1 chunk +1 line, -1 line 0 comments Download
M tests/PathOpsOpTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 179 chunks +608 lines, -386 lines 0 comments Download
M tests/PathOpsQuadIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 25 3 chunks +5 lines, -2 lines 0 comments Download
M tests/PathOpsQuadLineIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1 chunk +2 lines, -0 lines 0 comments Download
M tests/PathOpsQuadLineIntersectionThreadedTest.cpp View 1 2 3 4 5 6 7 8 9 10 25 1 chunk +0 lines, -1 line 0 comments Download
M tests/PathOpsQuadParameterizationTest.cpp View 1 2 3 4 5 6 7 8 9 25 1 chunk +6 lines, -6 lines 0 comments Download
M tests/PathOpsSimplifyFailTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 2 chunks +5 lines, -2 lines 0 comments Download
M tests/PathOpsSimplifyQuadThreadedTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 1 chunk +1 line, -0 lines 0 comments Download
M tests/PathOpsSimplifyTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 163 chunks +1559 lines, -811 lines 0 comments Download
M tests/PathOpsSkpClipTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 16 chunks +120 lines, -113 lines 0 comments Download
M tests/PathOpsSkpTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 51 chunks +259 lines, -112 lines 0 comments Download
M tests/Test.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 1 chunk +0 lines, -1 line 0 comments Download
M tests/skia_test.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 chunk +3 lines, -0 lines 0 comments Download
A tools/pathops_sorter.htm View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 1 chunk +2051 lines, -0 lines 0 comments Download

Messages

Total messages: 6 (0 generated)
caryclark
6 years, 9 months ago (2014-03-26 20:09:35 UTC) #1
reed1
public api lgtm
6 years, 9 months ago (2014-03-26 20:22:13 UTC) #2
mtklein
On 2014/03/26 20:22:13, reed1 wrote: > public api lgtm test changes lgtm
6 years, 9 months ago (2014-03-26 20:57:28 UTC) #3
caryclark
The CQ bit was checked by caryclark@google.com
6 years, 8 months ago (2014-04-14 15:51:47 UTC) #4
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://skia-tree-status.appspot.com/cq/caryclark@google.com/131103009/1620001
6 years, 8 months ago (2014-04-14 15:51:56 UTC) #5
commit-bot: I haz the power
6 years, 8 months ago (2014-04-14 17:10:31 UTC) #6
Message was sent while issue was closed.
Change committed as 14183

Powered by Google App Engine
This is Rietveld 408576698