aboutsummaryrefslogtreecommitdiffhomepage
path: root/tests/PathOpsOpTest.cpp
Commit message (Collapse)AuthorAge
* path ops: fix fuzz-found divide by zeroGravatar caryclark2015-11-02
| | | | | | | TBR=reed@google.com BUG=542391 Review URL: https://codereview.chromium.org/1427913005
* 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
* remove unused fields from SkOpSegmentGravatar caryclark2015-09-04
| | | | | | TBR=reed@google.com Review URL: https://codereview.chromium.org/1322413002
* link test to bugGravatar caryclark2015-09-01
| | | | | | | | | | | | | | | | | | | | | | | | crbug.com/526025 includes a minimized SVG test case. Translating that test case into native code (fuzzTNG) did not reproduce the bug. That test case should have not been included with skia issue 1323813003, and is deleted here. Running the minimal test case in a modified version of chrome isolated the bug. The modified version generated the test fuzz763_3 with the edit #define DEBUGGING_PATHOPS_FROM_HOST 1 in src/pathops/SkPathopsOp.cpp line 188. Rename fuzz763_3 to issue_526025 to associate the test with the bug. Note that the bug contains the body of the CL in comment $5. R=reed@google.com Review URL: https://codereview.chromium.org/1315503005
* remove duplicate linked list adjustmentGravatar caryclark2015-08-31
| | | | | | | | | | | | | | | | | | | | | The list of intersection points on a curve segment may have entries that can be safely removed when nearby points have nearly the same t value and point value. When a path includes very large curves as well as small ones, as is the case with this fuzzer, additional points may lie between the similar points that do not meet the nearby criteria. After merging the nearby point with its doppelganger, SkOpSegment::moveNearby() unnecessarily set the doppelganger's next pointer to the one following the nearby point. While this usually has no effect, since the merge already updated the linked list, the explicit call removes the additional outlier points from the segment. TBR=reed@google.com BUG=526025 Review URL: https://codereview.chromium.org/1323813003
* Style Change: NULL->nullptrGravatar halcanary2015-08-27
| | | | | | DOCS_PREVIEW= https://skia.org/?cl=1316233002 Review URL: https://codereview.chromium.org/1316233002
* fix pathops fuzz failuresGravatar caryclark2015-08-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | If a curve has the identical start and control points, the initial or final tangent can't be trivally determined. The perpendicular to the tangent is used to measure coincidence. Add logic for cubics, quadratics, and conics, to use the secondary control points or the end points if the initial control point alone can't determine the tangent. Add debugging (currently untriggered by exhaustive testing) to detect zero-length tangents which are not at the curve endpoints. Increase the number of temporary intersecions gathered from 10 to 12 but reduce the max passed in by cubic intersection from 27 to 12. Also, add checks if the max passed exceeds the storage allocated. When cleaning up parallel lines, choose the intersection which is on the end of both segments over the intersection which is on the end of a single segment. TBR=reed@google.com BUG=425140,516266 Review URL: https://codereview.chromium.org/1288863004
* 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
* minor fixes to cubics code and overall alignment of how bounds and tops are ↵Gravatar caryclark2015-04-29
| | | | | | | | | | | | computed for all curve types All but 17 extended tests work. A helper function is privately added to SkPath.h to permit a test to modify a given point in a path. BUG=skia:3588 Review URL: https://codereview.chromium.org/1107353004
* fix multiple intersection logicGravatar caryclark2015-04-24
| | | | | | | | | | | When three or more curves intersect at the same point, ensure that each curve records the intersections of the others. This fixes a number of cubic tests. TBR=reed@google.com BUG=skia:3588 Review URL: https://codereview.chromium.org/1105943002
* working on initial winding for cubicsGravatar caryclark2015-04-23
| | | | | | | | | | | Path ops works well for all tests except for cubics. Isolate failures caused by cubics, and do a better job of computing the initial winding for cubics. TBR=reed@google.com BUG=skia:3588 Review URL: https://codereview.chromium.org/1096923003
* 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
* These tests stress pathops by describing the union of circle-like paths that ↵Gravatar caryclark2014-11-13
| | | | | | | | | | | | | | | | | | | have tiny line segments embedded and double back to create near-coincident conditions. The fixes include - detect when finding the active top loops between two possible answers - preflight chasing winding to ensure answer is consistent - binary search more often when quadratic intersection fails - add more failure paths when an intersect is missed While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. TBR= BUG=421132 Committed: https://skia.googlesource.com/skia/+/6f726addf3178b01949bb389ef83cf14a1d7b6b2 Review URL: https://codereview.chromium.org/633393002
* Revert of harden pathops for pathological test (patchset #19 id:410001 of ↵Gravatar hcm2014-10-28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/633393002/) Reason for revert: Compile errors on bots Original issue's description: > These tests stress pathops by describing the union of circle-like paths that have tiny line segments embedded and double back to create near-coincident conditions. > > The fixes include > - detect when finding the active top loops between two possible answers > - preflight chasing winding to ensure answer is consistent > - binary search more often when quadratic intersection fails > - add more failure paths when an intersect is missed > > While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. > > TBR= > BUG=421132 > > Committed: https://skia.googlesource.com/skia/+/6f726addf3178b01949bb389ef83cf14a1d7b6b2 TBR=caryclark@google.com NOTREECHECKS=true NOTRY=true BUG=421132 Review URL: https://codereview.chromium.org/686843002
* These tests stress pathops by describing the union of circle-like paths that ↵Gravatar caryclark2014-10-28
| | | | | | | | | | | | | | | | | have tiny line segments embedded and double back to create near-coincident conditions. The fixes include - detect when finding the active top loops between two possible answers - preflight chasing winding to ensure answer is consistent - binary search more often when quadratic intersection fails - add more failure paths when an intersect is missed While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. TBR= BUG=421132 Review URL: https://codereview.chromium.org/633393002
* abort op early if path isn't parseableGravatar caryclark2014-10-03
| | | | | | | TBR= BUG=419649 Review URL: https://codereview.chromium.org/623943002
* fail on extremely large coincident curvesGravatar caryclark2014-09-29
| | | | | | | | | TBR= BUG=418381 Author: caryclark@google.com Review URL: https://codereview.chromium.org/607913007
* fail early if coincidence can't be resolvedGravatar caryclark2014-09-19
| | | | | | | | | | | | Bail out if a very large value causes coincidence resolution to fail. TBR= BUG=415866 Author: caryclark@google.com Review URL: https://codereview.chromium.org/585913002
* fix battlefield website by disallowing very small coordinatesGravatar caryclark2014-09-18
| | | | | | | | | | | also add and remove comments to document other attempts to fix this that had drawbacks R=fmalita@chromium.org BUG=414409 Author: caryclark@google.com Review URL: https://codereview.chromium.org/575553003
* fail when coincidence is too far apartGravatar caryclark2014-09-08
| | | | | | | | | TBR= BUG=410552 Author: caryclark@google.com Review URL: https://codereview.chromium.org/556433002
* relax quadratic binary search testGravatar caryclark2014-08-12
| | | | | | | | | | | | | | | | Extreme implicit quartic equations solve to roots that are different enough that they appear to have failed. In this case, fall back on binary searching to find an intersection. Relax the condition when this happens; don't give up just because the computed implicit root points aren't remotely the same. TBR=reed BUG=skia:2808 Author: caryclark@google.com Review URL: https://codereview.chromium.org/456383003
* 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
* Fix last pathops skp bugGravatar caryclark2014-06-18
| | | | | | | | | | | | | | | | | | | | | | This fixes the last bug discovered by iterating through the 800K skp corpus representing the top 1M websites. For every clip on the stack, the paths are replaced with the pathop intersection. The resulting draw is compared with the original draw for pixel errors. At least two prominent bugs remain. In one, the winding value is confused by a cubic with an inflection. In the other, a quad/cubic pair, nearly coincident, fails to find an intersection. These minor changes include ignoring very tiny self-intersections of cubics, and processing degenerate edges that don't connect to anything else. R=reed@android.com TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/340103002
* 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
* When solving the cubic line intersection directly fails, use binary search ↵Gravatar commit-bot@chromium.org2014-05-07
| | | | | | | | | | | | | | | | | as a fallback. The cubic line intersection math empirically works 99.99% of the time (fails 3100 out of 1B random tests) but when it fails, an intersection may be missed altogether. The binary search is may not find a solution if the cubic line failed to find any solutions at all, but so far that case hasn't arisen. BUG=skia:2504 TBR=reed@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/266063003 git-svn-id: http://skia.googlecode.com/svn/trunk@14614 2bbb7eff-a529-9590-31e7-b0007b416f81
* fix cubic/line intersection; add skp testsGravatar commit-bot@chromium.org2014-04-30
| | | | | | | | | | | BUG=skia:2488 TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/252243003 git-svn-id: http://skia.googlecode.com/svn/trunk@14458 2bbb7eff-a529-9590-31e7-b0007b416f81
* 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
* 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
* remove SkFloatToScalar macroGravatar commit-bot@chromium.org2013-11-25
| | | | | | | | | | | BUG= R=reed@google.com, djsollen@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/85463005 git-svn-id: http://skia.googlecode.com/svn/trunk@12385 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-11-02
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@12101 2bbb7eff-a529-9590-31e7-b0007b416f81
* pathops work in progressGravatar caryclark@google.com2013-11-01
| | | | | | | | BUG= Review URL: https://codereview.chromium.org/52653002 git-svn-id: http://skia.googlecode.com/svn/trunk@12089 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
* fix 10.6Gravatar caryclark@google.com2013-10-02
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@11572 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
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-07-24
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@10299 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
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-07-16
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@10096 2bbb7eff-a529-9590-31e7-b0007b416f81
* add florin testsGravatar caryclark@google.com2013-07-15
| | | | | | | | | | hopefully fix build BUG= Review URL: https://codereview.chromium.org/19183005 git-svn-id: http://skia.googlecode.com/svn/trunk@10079 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops near exactGravatar caryclark@google.com2013-07-15
| | | | | | | | | | | | | | | | | Modify line intersections to first - match exact ends - compute intersections - match near ends where the exact ends are preferred, then near matches, then computed matches. This pulls matches towards existing end points when possible, and keeps intersection distances consistent with different line/line line/quad and line/cubic computations. BUG= Review URL: https://codereview.chromium.org/19183003 git-svn-id: http://skia.googlecode.com/svn/trunk@10073 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 10:31:36 +0000