Path ops formerly found the topmost unprocessed edge and determined its angle sort...
authorcaryclark <caryclark@google.com>
Mon, 11 May 2015 14:21:27 +0000 (07:21 -0700)
committerCommit bot <commit-bot@chromium.org>
Mon, 11 May 2015 14:21:28 +0000 (07:21 -0700)
commit624637cc8ec22c000409704d0b403ac1b81ad4b0
tree3524a1f5dfb24a5afbe3dd1ebbfb495b8c0a299e
parentaf2d56d2139cc5597a5a43a4e16acbd8d10e9060
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

Review URL: https://codereview.chromium.org/1111333002
52 files changed:
gyp/core.gypi
src/pathops/SkDConicLineIntersection.cpp
src/pathops/SkDLineIntersection.cpp
src/pathops/SkDQuadLineIntersection.cpp
src/pathops/SkIntersections.cpp
src/pathops/SkIntersections.h
src/pathops/SkOpAngle.cpp
src/pathops/SkOpAngle.h
src/pathops/SkOpCoincidence.h
src/pathops/SkOpContour.cpp
src/pathops/SkOpContour.h
src/pathops/SkOpSegment.cpp
src/pathops/SkOpSegment.h
src/pathops/SkOpSpan.cpp
src/pathops/SkOpSpan.h
src/pathops/SkPathOpsBounds.h
src/pathops/SkPathOpsCommon.cpp
src/pathops/SkPathOpsCommon.h
src/pathops/SkPathOpsCubic.cpp
src/pathops/SkPathOpsCubic.h
src/pathops/SkPathOpsCurve.cpp
src/pathops/SkPathOpsCurve.h
src/pathops/SkPathOpsDebug.cpp
src/pathops/SkPathOpsDebug.h
src/pathops/SkPathOpsLine.h
src/pathops/SkPathOpsOp.cpp
src/pathops/SkPathOpsPoint.cpp
src/pathops/SkPathOpsPoint.h
src/pathops/SkPathOpsQuad.cpp
src/pathops/SkPathOpsQuad.h
src/pathops/SkPathOpsSimplify.cpp
src/pathops/SkPathOpsTightBounds.cpp
src/pathops/SkPathOpsTypes.h
src/pathops/SkPathOpsWinding.cpp [new file with mode: 0644]
tests/PathOpsAngleIdeas.cpp
tests/PathOpsAngleTest.cpp
tests/PathOpsBattles.cpp
tests/PathOpsBoundsTest.cpp
tests/PathOpsCubicReduceOrderTest.cpp
tests/PathOpsDCubicTest.cpp
tests/PathOpsDVectorTest.cpp
tests/PathOpsDebug.cpp
tests/PathOpsExtendedTest.cpp
tests/PathOpsExtendedTest.h
tests/PathOpsFuzz763Test.cpp
tests/PathOpsIssue3651.cpp
tests/PathOpsOpTest.cpp
tests/PathOpsQuadIntersectionTest.cpp
tests/PathOpsSimplifyTest.cpp
tests/PathOpsSkpTest.cpp
tools/pathops_sorter.htm
tools/pathops_visualizer.htm