aboutsummaryrefslogtreecommitdiffhomepage
path: root/tests/PathOpsSimplifyTest.cpp
Commit message (Collapse)AuthorAge
* interpolation of coincidence must be local to a single spanGravatar caryclark2016-09-06
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Pathops makes up intersections that it doesn't detect directly, but do exist. For instance, if a is coincident with b, and b is coincident with c, then for where they overlap a is coincident with c. The intersections are made up in different ways. In a few places, the t values that are detected are interpolated to guess the t values that represent invented intersections. The interpolated t is not necessarily linear, but a linear guess is good enough if the invented t lies between known t values. Additionally, improve debugging. This passes the extended release test suite and additionally passes the first 17 levels in the tiger test suite; previously, path ops passed 7 levels. The tiger suite is composed of 37 levels in increasing complexity, described by about 300K tests. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2300203002 Review-Url: https://codereview.chromium.org/2300203002
* pathops coincident workGravatar caryclark2016-08-31
| | | | | | | | | | | | | This is working towards fixing all bugs around simplifying the tiger. This installment simplifies the point-t intersection list as it is built rather than doing the analysis once the intersections are complete. This avoids getting the list in an inconsistent state and makes coincident checks faster and more stable. GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2237223002 TBR=reed@google.com BUG=skia:5131 Review-Url: https://codereview.chromium.org/2237223002
* start working on tiger againGravatar caryclark2016-08-11
| | | | | | | | | | | | | | | The tiger tests are a suite under development that exercise many coincident edge cases. This fixes the case when a duplicate point is not ignored when the coincident span references the primary point. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2239803002 Review-Url: https://codereview.chromium.org/2239803002
* disable new test since it fails on skia_fastGravatar caryclark2016-07-18
| | | | | | | TBR=jcgregario@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2155243002 Review-Url: https://codereview.chromium.org/2155243002
* pathops coincidence and security rewriteGravatar caryclark2016-07-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Most changes stem from working on an examples bracketed by #if DEBUG_UNDER_DEVELOPMENT // tiger These exposed many problems with coincident curves, as well as errors throughout the code. Fixing these errors also fixed a number of fuzzer-inspired bug reports. * Line/Curve Intersections Check to see if the end of the line nearly intersects the curve. This was a FIXME in the old code. * Performance Use a central chunk allocator. Plumb the allocator into the global variable state so that it can be shared. (Note that 'SkGlobalState' is allocated on the stack and is visible to children functions but not other threads.) * Refactor Let SkOpAngle grow up from a structure to a class. Let SkCoincidentSpans grow up from a structure to a class. Rename enum Alias to AliasMatch. * Coincidence Rewrite Add more debugging to coincidence detection. Parallel debugging routines have read-only logic to report the current coincidence state so that steps through the logic can expose whether things got better or worse. More functions can error-out and cause the pathops engine to non-destructively exit. * Accuracy Remove code that adjusted point locations. Instead, offset the curve part so that sorted curves all use the same origin. Reduce the size (and influence) of magic numbers. * Testing The debug suite with verify and the full release suite ./out/Debug/pathops_unittest -v -V ./out/Release/pathops_unittest -v -V -x expose one error. That error is captured as cubics_d3. This error exists in the checked in code as well. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2128633003 BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2128633003 Review-Url: https://codereview.chromium.org/2128633003
* fix security bugGravatar caryclark2016-05-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This fix is a tradeoff. It changes intersection to treat a case where one coincident run is intersected at one point and the other edge is not as continuing to be a span. The old code tried to treat this as a single point. The old code is probably right, but this change alone made the data structures inconsistent. Later, extending the coincident runs would fail by incorrectly discarding the single point intersection. As a result, this fixes the security test and one other, but makes a different test fail. Isolating the failure uncovered a reduced case that fails with and without the change, so there are more serious problems here. Those problems are addressed in a separate CL. Many of the test edits below remove ill-thought out debugging messaging that fire off global state, which isn't usable in a multi-threaded test environment. In the end, with this fix, all existing tests (modulo one new failure and one new non-failure) pass in debug and in the extended release test suites. TBR=reed@google.com BUG=614248 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2018513003 Review-Url: https://codereview.chromium.org/2018513003
* fix coincident fuzzerGravatar caryclark2015-12-07
| | | | | | | | | | | This fuzzer has very large Y values that cause the points to sort incorrectly by t. Exit out as soon as this is detected. TBR=reed@google.com BUG=561121 Review URL: https://codereview.chromium.org/1507803002
* fix pathops coincidence fuzz bugGravatar caryclark2015-11-20
| | | | | | | | | | | | | | | | | | | | | Simplifying a series of rects with very large bounds triggers a coincidence bug where, after one of the intersection points that marks a coincident range has been deleted, it is referenced. Both the deletion and reference is (probably) happening in the SkOpCoincidence::AddExpanded() phase of HandleCoincidence(), and may signify a bug that could happen with usable input data, but I haven't been able to determine that. For now, abort the Simplify() when the erroneous condition is detected. TBR=reed@google.com BUG=558281 Review URL: https://codereview.chromium.org/1463923002
* Enabling clip stack flattening exercises path ops.Gravatar caryclark2015-10-16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Iterating through the 903K skps that represent the imagable 1M top web pages triggers a number of bugs, some of which are addressed here. Some web pages trigger intersecting cubic representations of arc with their conic counterparts. This exposed a flaw in coincident detection that caused an infinite loop. The loop alternatively extended the coincident section and, determining the that the bounds of the curve pairs did not overlap, deleted the extension. Track the number of times the coincident detection is called, and if it exceeds an empirically found limit, assume that the curves are coincident and force it to be so. The loop count limit can be determined by enabling DEBUG_T_SECT_LOOP_COUNT and running all tests. The largest count is reported on completion. Another class of bugs was caused by concident detection duplicating nearly identical points that had been merged earlier. To track these bugs, the 'handle coincidence' code was duplicated as a const debug variety that reported if one of a dozen or so irregularities are present; then it is easier to see when a block of code that fixes one irregularity regresses another. Creating the debug const code version exposed some non-debug code that could be const, and some that was experimental and could be removed. Set DEBUG_COINCIDENCE to track coincidence health and handling. For running on Chrome, DEBUG_VERIFY checks the result of pathops against the same operation using SkRegion to verify that the results are nearly the same. When visualizing the pathops work using tools/pathops_visualizer.htm, set DEBUG_DUMP_ALIGNMENT to see the curves after they've been aligned for coincidence. Other bugs fixed include detecting when a section of a pair of curves have devolved into lines and are coincident. TBR=reed@google.com Review URL: https://codereview.chromium.org/1394503003
* looking for fuzz failureGravatar caryclark2015-09-23
| | | | | | | | | | | | | | | These tests were isolated from their respective minimized test cases. The tests work fine and pass path ops internal validation; hopefully some more intensive x-san or valgrind test will help isolate the bug. Sheriff, please revert if it fails and I don't get to it first. TBR=reed@google.com,halcanary@google.com BUG=535127,535151 Review URL: https://codereview.chromium.org/1359263003
* Style Change: NULL->nullptrGravatar halcanary2015-08-27
| | | | | | DOCS_PREVIEW= https://skia.org/?cl=1316233002 Review URL: https://codereview.chromium.org/1316233002
* compute split conic endpoints exactlyGravatar caryclark2015-07-28
| | | | | | | | | | | | | | The divide by w can generate slightly erroneous results even for t == 0 or t == 1. The error in turn defeats detecting a point in common for a pair of curves that travel in opposite directions. Instead, special case endpoints when the t is 0 or 1. TBR=reed@google.com BUG=514118 Review URL: https://codereview.chromium.org/1259513004
* fix path ops fuzz busterGravatar caryclark2015-07-23
| | | | | | | | | | | | Mark collapsed segments as done and remove collapsed segment references from the coincidence array. Also add test names to global debugging. R=fmalita@chromium.org BUG=512592 Review URL: https://codereview.chromium.org/1250293002
* When three or more edges are coincident, the logic needsGravatar caryclark2015-07-06
| | | | | | | | | | | | | | | | to compute the overlapping ranges and combine the winding into a single destination. This computes coincidence more rigorously, fixing the edge cases exposed by this bug. Also, add the ability to debug and dump pathop structures from the coincident context. TBR=reed@google.com BUG=skia:3651 Review URL: https://codereview.chromium.org/1182493015
* fix builder winding againGravatar caryclark2015-05-18
| | | | | | | | | | Record the nesting level when finding the edge winding contribution so that inner edges can be reversed as needed. R=fmalita@chromium.org BUG=skia:3838 Review URL: https://codereview.chromium.org/1140383002
* fix path op builderGravatar caryclark2015-05-14
| | | | | | | | | | | | | | | The rewrite of path ops caused the inner contour direction to be reversed. This exposed an existing bug in path ops builder, namely that the implicit winding of the internal sum path could hide inner contours if they ended up in the wrong direction. Setting the sum path's fill type to even-odd ensures that the inner contours aren't discarded. R=fmalita@chromium.org BUG=skia:3838 Review URL: https://codereview.chromium.org/1126193004
* deal more consistently with unsortable edgesGravatar caryclark2015-05-13
| | | | | | | | | | | | | Improve line/curve coincident detection and resolution. This fixed the remaining simple failures. When an edge is unsortable, use the ray intersection to determine the angles' winding. Deal with degenerate segments. TBR=reed@google.com BUG=skia:3588,skia:3762 Review URL: https://codereview.chromium.org/1140813002
* Path ops formerly found the topmost unprocessed edge and determined its ↵Gravatar caryclark2015-05-11
| | | | | | | | | | | | | | | 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
* Now, path ops natively intersect conics, quads, and cubics in any ↵Gravatar caryclark2015-04-20
| | | | | | | | | | | combination. There are still a class of cubic tests that fail and a handful of undiagnosed failures from skps and fuzz tests, but things are much better overall. Extended tests (150M+) run to completion in release in about 6 minutes; the standard test suite exceeds 100K and finishes in a few seconds on desktops. TBR=reed BUG=skia:3588 Review URL: https://codereview.chromium.org/1037953004
* cumulative pathops patchGravatar caryclark2015-03-26
| | | | | | | | | | | | | | | | | | | | | Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer. Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering. Unify t and point values so that small intervals can be eliminated in one pass. Break cubics up front to eliminate loops and cusps. Make the Simplify and Op code more regular and eliminate arbitrary differences. Add a builder that takes an array of paths and operators. Delete unused code. BUG=skia:3588 R=reed@google.com Review URL: https://codereview.chromium.org/1037573004
* Revert of pathops version two (patchset #16 id:150001 of ↵Gravatar reed2015-03-24
| | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1002693002/) Reason for revert: ASAN investigation Original issue's description: > pathops version two > > R=reed@google.com > > marked 'no commit' to attempt to get trybots to run > > TBR=reed@google.com > > Committed: https://skia.googlesource.com/skia/+/ccec0f958ffc71a9986d236bc2eb335cb2111119 TBR=caryclark@google.com NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1029993002
* pathops version twoGravatar caryclark2015-03-24
| | | | | | | | | | R=reed@google.com marked 'no commit' to attempt to get trybots to run TBR=reed@google.com Review URL: https://codereview.chromium.org/1002693002
* update pathops core and testsGravatar caryclark2014-07-18
| | | | | | | | | | split out skpclip (the test of 1M pictures) into its own project TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/400033002
* Enabling the canvas bit to turn the clip stack into a flat replace exposed ↵Gravatar caryclark2014-06-17
| | | | | | | | | | | | | | | | | | around 100 failures when testing the 800K skp set generated from the top 1M web sites. This fixes all but one of those failures. Major changes include: - Replace angle indices with angle pointers. This was motivated by the need to add angles later but not renumber existing angles. - Aggressive segment chase. When the winding is known on a segment, more aggressively passing that winding to adjacent segments allows fragmented data sets to succeed. - Line segments with ends nearly the same are treated as coincident first. - Transfer partial coincidence by observing that if segment A is partially coincident to B and C then B and C may be partially coincident. TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/272153002
* fix minor skp-found bugsGravatar commit-bot@chromium.org2014-04-25
| | | | | | | | | | | | | remove globals from pathops_unittest BUG=skia:2460 TBR=mtklein Author: caryclark@google.com Review URL: https://codereview.chromium.org/239563004 git-svn-id: http://skia.googlecode.com/svn/trunk@14378 2bbb7eff-a529-9590-31e7-b0007b416f81
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2014-04-15
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@14196 2bbb7eff-a529-9590-31e7-b0007b416f81
* Mike R: please sanity check SkPostConfig.hGravatar commit-bot@chromium.org2014-04-14
| | | | | | | | | | | | | | | | | | | | | | | | 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. R=mtklein@google.com, reed@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/131103009 git-svn-id: http://skia.googlecode.com/svn/trunk@14183 2bbb7eff-a529-9590-31e7-b0007b416f81
* Move macros from TestClassDef.h to Test.hGravatar commit-bot@chromium.org2014-01-14
| | | | | | | | | | | | | | Motivation: those macros don't make any sense without the definitions in Test.h. BUG= R=mtklein@google.com Author: halcanary@google.com Review URL: https://codereview.chromium.org/138563004 git-svn-id: http://skia.googlecode.com/svn/trunk@13074 2bbb7eff-a529-9590-31e7-b0007b416f81
* Get rid of DEFINE_TESTCLASS_SHORT() macro.Gravatar tfarina@chromium.org2014-01-02
| | | | | | | | | | | | | Instead tests should be written using DEF_TEST() macro, which is much nicer and simplifies the process of setting up an unit test. BUG=None TEST=skpskgr_test, pathops_unittest R=mtklein@google.com Review URL: https://codereview.chromium.org/117863005 git-svn-id: http://skia.googlecode.com/svn/trunk@12870 2bbb7eff-a529-9590-31e7-b0007b416f81
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-11-26
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@12389 2bbb7eff-a529-9590-31e7-b0007b416f81
* fix pathops quad line intersectionGravatar caryclark@google.com2013-11-25
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@12374 2bbb7eff-a529-9590-31e7-b0007b416f81
* optimize pathops coverageGravatar commit-bot@chromium.org2013-11-21
| | | | | | | | | | | | | | | Remove unused code from SkOpSegment.cpp and friends. Add new tests exposed by coverage. Fix a bug exposed by coverage -- removing the need to detect points that are nearby when intersecting. Add gyp rule for building coverage flavor on Mac. R=mtklein@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/75453003 git-svn-id: http://skia.googlecode.com/svn/trunk@12344 2bbb7eff-a529-9590-31e7-b0007b416f81
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-10-03
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@11585 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-10-02
| | | | | | | | | | | | make more skps work remove edit files BUG= Review URL: https://codereview.chromium.org/23542056 git-svn-id: http://skia.googlecode.com/svn/trunk@11570 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-09-16
| | | | | | | | | | path ops work in progress BUG= Review URL: https://codereview.chromium.org/21359002 git-svn-id: http://skia.googlecode.com/svn/trunk@11291 2bbb7eff-a529-9590-31e7-b0007b416f81
* turn off debugging printfsGravatar caryclark@google.com2013-07-23
| | | | | | | | | | | | | fix pathops issues 1417, 1418 be more rigorous about pulling intersections of lines to end points rewrite cubic/line and quad/line intersections to share style BUG= Review URL: https://codereview.chromium.org/19543005 git-svn-id: http://skia.googlecode.com/svn/trunk@10270 2bbb7eff-a529-9590-31e7-b0007b416f81
* fix linux point compareGravatar caryclark@google.com2013-07-15
| | | | | | | | | | fix linux pt compare BUG= Review URL: https://codereview.chromium.org/19203002 git-svn-id: http://skia.googlecode.com/svn/trunk@10076 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-07-08
| | | | | | | | BUG= Review URL: https://codereview.chromium.org/18058007 git-svn-id: http://skia.googlecode.com/svn/trunk@9908 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops -- rewrite angle sortGravatar caryclark@google.com2013-06-04
| | | | | | | | | | | | | | | | | | | | | | | | This is a major change resulting from a minor tweak. In the old code, the intersection point of two curves was shared between them, but the intersection points and end points of sorted edges was computed directly from the intersection T value. In this CL, both intersection points and sorted points are the same, and intermediate control points are computed to preserve their slope. The sort itself has been completely rewritten to be more robust and remove 'magic' checks, conditions that empirically worked but couldn't be rationalized. This CL was triggered by errors generated computing the clips of SKP files. At this point, all 73M standard tests work and at least the first troublesome SKPs work. Review URL: https://codereview.chromium.org/15338003 git-svn-id: http://skia.googlecode.com/svn/trunk@9432 2bbb7eff-a529-9590-31e7-b0007b416f81
* bump picture version since SkPath has changed (conics)Gravatar reed@google.com2013-05-31
| | | | | | enable conics in SkPath git-svn-id: http://skia.googlecode.com/svn/trunk@9370 2bbb7eff-a529-9590-31e7-b0007b416f81
* Revert "add asserts to point<-->verb helpers"Gravatar reed@google.com2013-05-30
| | | | | | This reverts commit b4775ac7b55802e87231768f002e4b42f233b0aa. git-svn-id: http://skia.googlecode.com/svn/trunk@9347 2bbb7eff-a529-9590-31e7-b0007b416f81
* add asserts to point<-->verb helpersGravatar reed@google.com2013-05-30
| | | | | | | | | | patch from issue 16153005 BUG= Review URL: https://codereview.chromium.org/16195004 git-svn-id: http://skia.googlecode.com/svn/trunk@9344 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops -- fix skp bugsGravatar caryclark@google.com2013-05-07
| | | | | | | | | This fixes a series of bugs discovered by running the small set of Skia skp files through pathops to flatten the clips. Review URL: https://codereview.chromium.org/14798004 git-svn-id: http://skia.googlecode.com/svn/trunk@9042 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops -- handle non-finite numbersGravatar caryclark@google.com2013-04-26
| | | | | | | | Op() and Simplify() do nothing if the input is non-finite. Add code and tests. Review URL: https://codereview.chromium.org/14407006 git-svn-id: http://skia.googlecode.com/svn/trunk@8882 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-04-18
| | | | | | | | | fix bugs in tests on 32 bit release Most changes revolve around pinning computed t values very close to zero and one. git-svn-id: http://skia.googlecode.com/svn/trunk@8745 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-04-15
| | | | | | | | | standardize tests use SK_ARRAY_COUNT everywhere debug why x87 differs from SIMD 64 various platform specific fixes git-svn-id: http://skia.googlecode.com/svn/trunk@8689 2bbb7eff-a529-9590-31e7-b0007b416f81
* fix a few pathops test bugs exposed on Mac and LinuxGravatar caryclark@google.com2013-04-10
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@8601 2bbb7eff-a529-9590-31e7-b0007b416f81
* Add implementation of path opsGravatar caryclark@google.com2013-04-08
This CL depends on https://codereview.chromium.org/12880016/ "Add intersections for path ops" Given a path, iterate through its contour, and construct an array of segments containing its curves. Intersect each curve with every other curve, and for cubics, with itself. Given the set of intersections, find one with the smallest y and sort the curves eminating from the intersection. Assign each curve a winding value. Operate on the curves, keeping and discarding them according to the current operation and the sum of the winding values. Assemble the kept curves into an output path. Review URL: https://codereview.chromium.org/13094010 git-svn-id: http://skia.googlecode.com/svn/trunk@8553 2bbb7eff-a529-9590-31e7-b0007b416f81
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-28 03:48:02 +0000