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

Issue 1111333002: compute initial winding from projected rays (Closed)

Created:
5 years, 7 months ago by caryclark
Modified:
5 years, 7 months ago
Reviewers:
CC:
reviews_skia.org
Base URL:
https://skia.googlesource.com/skia.git@master
Target Ref:
refs/heads/master
Project:
skia
Visibility:
Public.

Description

Path ops formerly found the topmost unprocessed edge and determined its angle sort order to initialize the winding. This never worked correctly with cubics and was flaky with paths consisting mostly of vertical edges. This replacement shoots axis-aligned rays through all intersecting edges to find the outermost one either horizontally or vertically. The resulting code is smaller and twice as fast. To support this, most of the horizontal / vertical intersection code was rewritten and standardized, and old code supporting the top-directed winding was deleted. Contours were pointed to by an SkTDArray. Instead, put them in a linked list, and designate the list head with its own class to ensure that methods that take lists of contours start at the top. This change removed a large percentage of memory allocations used by path ops. TBR=reed@google.com BUG=skia:3588 Committed: https://skia.googlesource.com/skia/+/624637cc8ec22c000409704d0b403ac1b81ad4b0

Patch Set 1 #

Patch Set 2 : zero in on first failure #

Patch Set 3 : first cut on op winding #

Patch Set 4 : more work on ops winding #

Patch Set 5 : more work on op winding #

Patch Set 6 : path winding work in progress #

Patch Set 7 : path ops winding work in progress #

Patch Set 8 : more work in progress #

Patch Set 9 : work in progress #

Patch Set 10 : work in progress #

Patch Set 11 : remove old find top; remove ray check experiment #

Patch Set 12 : remove more dead code #

Patch Set 13 : remove even more dead code #

Patch Set 14 : one more pass of deleting dead code #

Patch Set 15 : all (non-extended) tests work in debug #

Patch Set 16 : add failing tests from extended test #

Patch Set 17 : fix compile error #

Patch Set 18 : remove unused test data, duplicate tests #

Patch Set 19 : checkpoint; nearly everything works -- but some tests are flaky :( #

Patch Set 20 : fix memory leak #

Patch Set 21 : isolate tests that fail in -x mode #

Patch Set 22 : add missing test reference #

Unified diffs Side-by-side diffs Delta from patch set Stats (+1663 lines, -2476 lines) Patch
M gyp/core.gypi View 1 2 3 4 5 6 7 1 chunk +1 line, -0 lines 0 comments Download
M src/pathops/SkDConicLineIntersection.cpp View 1 2 3 13 chunks +48 lines, -22 lines 0 comments Download
M src/pathops/SkDLineIntersection.cpp View 1 2 3 4 chunks +4 lines, -4 lines 0 comments Download
M src/pathops/SkDQuadLineIntersection.cpp View 1 2 3 9 chunks +34 lines, -17 lines 0 comments Download
M src/pathops/SkIntersections.h View 1 2 3 4 5 6 7 8 9 10 11 12 5 chunks +7 lines, -13 lines 0 comments Download
M src/pathops/SkIntersections.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 3 chunks +0 lines, -65 lines 0 comments Download
M src/pathops/SkOpAngle.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 5 chunks +2 lines, -5 lines 0 comments Download
M src/pathops/SkOpAngle.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 chunks +4 lines, -98 lines 0 comments Download
M src/pathops/SkOpCoincidence.h View 1 2 1 chunk +1 line, -0 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 12 chunks +33 lines, -27 lines 0 comments Download
M src/pathops/SkOpContour.cpp View 1 2 3 4 5 6 7 8 9 10 11 2 chunks +0 lines, -57 lines 0 comments Download
M src/pathops/SkOpSegment.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 17 chunks +13 lines, -35 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 17 chunks +24 lines, -516 lines 0 comments Download
M src/pathops/SkOpSpan.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 chunks +4 lines, -9 lines 0 comments Download
M src/pathops/SkOpSpan.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 4 chunks +11 lines, -64 lines 0 comments Download
M src/pathops/SkPathOpsBounds.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +0 lines, -13 lines 0 comments Download
M src/pathops/SkPathOpsCommon.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +6 lines, -11 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 6 chunks +59 lines, -355 lines 0 comments Download
M src/pathops/SkPathOpsCubic.h View 1 2 3 4 5 6 7 8 9 10 11 4 chunks +4 lines, -8 lines 0 comments Download
M src/pathops/SkPathOpsCubic.cpp View 1 2 3 4 5 6 7 8 9 10 11 4 chunks +58 lines, -83 lines 0 comments Download
M src/pathops/SkPathOpsCurve.h View 1 2 3 4 5 6 7 8 9 10 11 12 3 chunks +55 lines, -7 lines 0 comments Download
M src/pathops/SkPathOpsCurve.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 3 chunks +0 lines, -107 lines 0 comments Download
M src/pathops/SkPathOpsDebug.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 6 chunks +3 lines, -31 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 8 chunks +74 lines, -27 lines 0 comments Download
M src/pathops/SkPathOpsLine.h View 1 2 3 4 1 chunk +2 lines, -1 line 0 comments Download
M src/pathops/SkPathOpsOp.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 chunks +24 lines, -54 lines 0 comments Download
M src/pathops/SkPathOpsPoint.h View 1 2 3 4 5 6 7 8 9 10 11 12 2 chunks +1 line, -3 lines 0 comments Download
M src/pathops/SkPathOpsPoint.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 1 chunk +0 lines, -5 lines 0 comments Download
M src/pathops/SkPathOpsQuad.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 3 chunks +1 line, -4 lines 0 comments Download
M src/pathops/SkPathOpsQuad.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 3 chunks +0 lines, -63 lines 0 comments Download
M src/pathops/SkPathOpsSimplify.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 chunks +17 lines, -53 lines 0 comments Download
M src/pathops/SkPathOpsTightBounds.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +6 lines, -10 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 5 chunks +16 lines, -3 lines 0 comments Download
A src/pathops/SkPathOpsWinding.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +402 lines, -0 lines 0 comments Download
M tests/PathOpsAngleIdeas.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +2 lines, -2 lines 0 comments Download
M tests/PathOpsAngleTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 chunks +4 lines, -4 lines 0 comments Download
M tests/PathOpsBattles.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 chunks +2 lines, -2 lines 0 comments Download
M tests/PathOpsBoundsTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 chunks +1 line, -42 lines 0 comments Download
M tests/PathOpsCubicReduceOrderTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 3 chunks +3 lines, -3 lines 0 comments Download
M tests/PathOpsDCubicTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 1 chunk +0 lines, -21 lines 0 comments Download
M tests/PathOpsDVectorTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 1 chunk +0 lines, -2 lines 0 comments Download
M tests/PathOpsDebug.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 13 chunks +64 lines, -110 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 1 chunk +2 lines, -0 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 5 chunks +19 lines, -8 lines 0 comments Download
M tests/PathOpsFuzz763Test.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 5 chunks +6 lines, -6 lines 0 comments Download
M tests/PathOpsIssue3651.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 chunks +3 lines, -3 lines 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 30 chunks +141 lines, -195 lines 0 comments Download
M tests/PathOpsQuadIntersectionTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 3 chunks +2 lines, -67 lines 0 comments Download
M tests/PathOpsSimplifyTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +28 lines, -0 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 2 chunks +2 lines, -2 lines 0 comments Download
M tools/pathops_sorter.htm View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 chunk +4 lines, -2 lines 0 comments Download
M tools/pathops_visualizer.htm View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18 chunks +466 lines, -237 lines 0 comments Download

Messages

Total messages: 22 (11 generated)
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/280001
5 years, 7 months ago (2015-05-08 15:35:34 UTC) #2
commit-bot: I haz the power
Dry run: Try jobs failed on following builders: Build-Ubuntu-Clang-x86_64-Debug-Trybot on client.skia.compile (JOB_FAILED, http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-Clang-x86_64-Debug-Trybot/builds/948) Build-Ubuntu-GCC-Arm7-Debug-Android-Trybot on ...
5 years, 7 months ago (2015-05-08 15:38:02 UTC) #4
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/300001
5 years, 7 months ago (2015-05-08 16:00:41 UTC) #6
commit-bot: I haz the power
Dry run: Try jobs failed on following builders: Build-Ubuntu-GCC-Arm7-Debug-Android-Trybot on client.skia.compile (JOB_FAILED, http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-GCC-Arm7-Debug-Android-Trybot/builds/957)
5 years, 7 months ago (2015-05-08 16:02:52 UTC) #8
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/320001
5 years, 7 months ago (2015-05-08 16:24:02 UTC) #10
commit-bot: I haz the power
Dry run: Try jobs failed on following builders: Build-Ubuntu-Clang-x86_64-Debug-Trybot on client.skia.compile (JOB_FAILED, http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-Clang-x86_64-Debug-Trybot/builds/952)
5 years, 7 months ago (2015-05-08 16:26:28 UTC) #12
commit-bot: I haz the power
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/350001
5 years, 7 months ago (2015-05-08 21:11:30 UTC) #14
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/390001
5 years, 7 months ago (2015-05-11 13:58:59 UTC) #17
commit-bot: I haz the power
Try jobs failed on following builders: Build-Ubuntu-Clang-x86_64-Debug-Trybot on client.skia.compile (JOB_FAILED, http://build.chromium.org/p/client.skia.compile/builders/Build-Ubuntu-Clang-x86_64-Debug-Trybot/builds/963)
5 years, 7 months ago (2015-05-11 14:00:42 UTC) #19
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1111333002/410001
5 years, 7 months ago (2015-05-11 14:14:44 UTC) #21
commit-bot: I haz the power
5 years, 7 months ago (2015-05-11 14:21:35 UTC) #22
Message was sent while issue was closed.
Committed patchset #22 (id:410001) as
https://skia.googlesource.com/skia/+/624637cc8ec22c000409704d0b403ac1b81ad4b0

Powered by Google App Engine
This is Rietveld 408576698