aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkOpCoincidence.cpp
Commit message (Collapse)AuthorAge
* Remove SkOpTAllocatorGravatar Herb Derby2017-04-19
| | | | | | | | | | Have the callsites of SkOpTAllocator call SkArenaAlloc directly. Bug: skia: Change-Id: Ic54e92c3e9a0abed038aa3ae40e8a195895af99d Reviewed-on: https://skia-review.googlesource.com/13870 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Herb Derby <herb@google.com>
* limit addEndMoveSpans loop in pathopsGravatar Cary Clark2017-03-09
| | | | | | | | | | | | | | Prevent addEndMoveSpans from looping forever and abort with an error if the loop count is crazy big. R=kjlubick@google.com BUG=684553 Change-Id: I16c250c0b2f88534f809aba17a18081aea4e1f44 Reviewed-on: https://skia-review.googlesource.com/9458 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* fix fuzz asserts triggered by old fuzzesGravatar Cary Clark2017-01-20
| | | | | | | | | | | | | | fuzz fixes Fixes from running all pathops fuzz testson ToT. R=kjlubick@google.com BUG=skia: Change-Id: Ic84b868a0cc53993e6561bc95fa364218bc3aa34 Reviewed-on: https://skia-review.googlesource.com/7325 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* fix fuzzerGravatar Cary Clark2017-01-03
| | | | | | | | | | | | abort if incoming data is out of range TBR=reed@google.com BUG=676866 Change-Id: I7d4850611654a399e32ea2012b23ca369dc53e70 Reviewed-on: https://skia-review.googlesource.com/6525 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* rework xor to be more like windingGravatar Cary Clark2016-12-16
| | | | | | | | | | | | | | | | Pathops is very well exercised with winding paths, but less so with xor (even odd) paths. Rewrite the xor main loop to look like the winding one to take advantage of the latter's bug fixes. TBR=reed@google.com BUG=skia:6041 Change-Id: Ied8d522254a327b1817b54f0abbf4414f5fab7da Reviewed-on: https://skia-review.googlesource.com/6228 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* speculative pointer to member fixGravatar Cary Clark2016-12-15
| | | | | | | | | | | | | | | | Move the body of simple functions out of line if they are used in pointer to member function expressions. This may fix a chromeos-reported bug. TBR=reed@google.com BUG=674047 Change-Id: Id2a080a6d047103a48ebe2319abdae444de413e3 Reviewed-on: https://skia-review.googlesource.com/6110 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* fix fuzzGravatar Cary Clark2016-12-12
| | | | | | | | | | | | | Don't walk off the end if the loop doesn't contain the expected value. R=kjlubick@google.com BUG=skia:6047 Change-Id: I96815180dc7c92b45691037ae6c4b40beedc009a Reviewed-on: https://skia-review.googlesource.com/5845 Reviewed-by: Kevin Lubick <kjlubick@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* fix fuzzersGravatar Cary Clark2016-12-08
| | | | | | | | | | | | | | Two crashes and a hang. Abort and return false in these cases. TBR=kjlubick@google.com BUG=skia:5983 Change-Id: I41ac3e56d47ee423b634b2f4886085b9caada76b Reviewed-on: https://skia-review.googlesource.com/5716 Reviewed-by: Cary Clark <caryclark@google.com> Reviewed-by: Kevin Lubick <kjlubick@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* fix fuzzer crashGravatar Cary Clark2016-11-17
| | | | | | | | | | | | | | | Fail if data is inconsistent. R=kjlubick@google.com BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=4923 Change-Id: Ie3f65c80c0d59968b1e3fc8bc91839bedb2e3da3 Reviewed-on: https://skia-review.googlesource.com/4923 Commit-Queue: Cary Clark <caryclark@google.com> Reviewed-by: Kevin Lubick <kjlubick@google.com>
* chmod -x *.cpp *.hGravatar Hal Canary2016-10-27
| | | | | | | Change-Id: I5b37499505e26e0837921292c1aea0056e4d5ecd Reviewed-on: https://skia-review.googlesource.com/4035 Reviewed-by: Ben Wagner <bungeman@google.com> Commit-Queue: Hal Canary <halcanary@google.com>
* fix a few more fuzzesGravatar caryclark2016-10-24
| | | | | | | | | | | | Minor changes to fix some fuzz conditions. A couple of ignored asserts when the data is fuzzy, and one fail condition when the underlying data has already been deleted. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2443243002 Review-Url: https://codereview.chromium.org/2443243002
* fix one more fuzzerGravatar caryclark2016-10-24
| | | | | | | TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2438333002 Review-Url: https://codereview.chromium.org/2438333002
* fix more fuzz, carsvgGravatar caryclark2016-10-20
| | | | | | | | | | | | | Fix a few kevin-generated fuzzers. Remove an assert triggered by carsvg when thrown through the distance field stuff. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2427253005 Review-Url: https://chromiumcodereview.appspot.com/2427253005
* fix more chrome asan fuzzer failuresGravatar caryclark2016-10-20
| | | | | | | | | | | | Small change to gracefully quit when fuzzer values cause pathops to fail. TBR=reed@google.com BUG=657411, 657559 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2426393004 Review-Url: https://chromiumcodereview.appspot.com/2426393004
* fix fuzzersGravatar caryclark2016-10-20
| | | | | | | | | | | | | | | Many old pathops-related fuzz failures have built up while the codebase was under a state a flux. Now that the code is stable, address these failures. Most of the CL plumbs the debug global state to downstream routines so that, if the data is not trusted (ala fuzzed) the function can safely exit without asserting. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2426173002 Review-Url: https://chromiumcodereview.appspot.com/2426173002
* fix some fuzzGravatar caryclark2016-10-17
| | | | | | | | TBR=reed@google.com BUG=654939, 655829, 656149 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2425733002 Review-Url: https://codereview.chromium.org/2425733002
* fix another fuzzGravatar caryclark2016-10-07
| | | | | | | | | Add one more early exit. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2401673004 Review-Url: https://codereview.chromium.org/2401673004
* fix fuzz bustersGravatar caryclark2016-10-07
| | | | | | | | | | | When fuzz is hit just quit TBR=reed@google.com BUG=skia:5837, skia:5838, skia:5839 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2404483002 Review-Url: https://codereview.chromium.org/2404483002
* fuzzer fixGravatar Cary Clark2016-10-06
| | | | | | | | | | | | | | | | | | Error out when fuzzing conditions are met. Also, make degenerate input line ends consistent. TBR=reed@google.com BUG=653452, 626164, skia:5829 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=3048 Change-Id: I23a01adde9dec07b54d66ab2418b3ea0b96e4456 Reviewed-on: https://skia-review.googlesource.com/3048 Commit-Queue: Cary Clark <caryclark@google.com> Reviewed-by: Cary Clark <caryclark@google.com>
* remove dead codeGravatar Cary Clark2016-10-05
| | | | | | | | | | | | | | | Use code coverage and a new '-c' flag to find and remove unneeded code. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2397593002 patch from issue 2397593002 at patchset 1 (http://crrev.com/2397593002#ps1) Change-Id: I741a82de9191146c10457d4c0b9cb9605dff2069 Reviewed-on: https://skia-review.googlesource.com/2983 Reviewed-by: Cary Clark <caryclark@google.com>
* fix fuzz with null checkGravatar Cary Clark2016-10-04
| | | | | | | | | | | | TBR=reed@google.com BUG=skia:5819 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2925 Change-Id: I1957d3f8f5c78bed41bb7fe413ae870df24f7c50 Reviewed-on: https://skia-review.googlesource.com/2925 Reviewed-by: Mike Reed <reed@google.com> Reviewed-by: Cary Clark <caryclark@google.com>
* coin debugging runs all tests in extendedGravatar Cary Clark2016-10-04
| | | | | | | | | | | | | | | | | | | This extends path ops concidence debugging to find unused algorithms and determine the extent of loops. This verifies that all 140M tests run without error in release and debug. TBR=reed@google.com BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2391733002 patch from issue 2391733002 at patchset 1 (http://crrev.com/2391733002#ps1) Change-Id: I02ca29764405c5ac3e7ca3b2621fba28dbaaffc2 Reviewed-on: https://skia-review.googlesource.com/2923 Reviewed-by: Cary Clark <caryclark@google.com>
* fix tiger bGravatar caryclark2016-09-26
| | | | | | | | | | | | | | | The tiger tests have uncovered numerous bugs. This CL fixes the last of them. If a pair of curves do not intersect, but have one or both ends very close to the opposite curve, consider that an intersection. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2356363003 Review-Url: https://codereview.chromium.org/2356363003
* split tight quads and conicsGravatar caryclark2016-09-23
| | | | | | | | | | | | Tight quads and conics may nearly fold over on themselves, confusing coincidence against other curves. Split them at their max curvature early on to avoid complicating later logic. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2357353002 Review-Url: https://codereview.chromium.org/2357353002
* fix next kevin fuzzGravatar caryclark2016-09-22
| | | | | | | | | | Fix one more fuzzer crash. R=kjlubick@google.com BUG=skia:5775 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2357373002 Review-Url: https://codereview.chromium.org/2357373002
* fix fuzzer bugsGravatar caryclark2016-09-19
| | | | | | | | | | | | Add a couple more cases where Op() fails and returns false when the out of range input values make the internal numeric unstable. TBR=reed@google.com BUG=647834, 648068 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2348263002 Review-Url: https://codereview.chromium.org/2348263002
* quad and conic do not intersectGravatar caryclark2016-09-15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a quad a conic intersect only where the end of one is contained by the convex hull of the other, and the curve contained by the hull is nearly a straight line, treating it as a line may move the end point to the other side of the curve. Detect this by checking to see if the end point is in the hull, and if so, continue to subdivide the curve rather than treating it as a line. This fixes several existing tests that were disabled earlier this year. A typo in SkDCurve::nearPoint() prevented detecting when the end of a line was nearly touching a curve. Also fixed concidence a bit to get the second half of tiger further along. All existing tests, including extended testing in Release and the first half of tiger, work. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2338323002 Review-Url: https://codereview.chromium.org/2338323002
* Skip adding coincident edges foundGravatar caryclark2016-09-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | during curve intersection if their ends are nearly the same. Loosen conic/line intersection point check. Detect when coincident points are unordered. This means that points a/b/c on one curve may appear in b/c/a order on the opposite curve. Restructure addMissing to return success and return if a coincidence was added as a parameter. With this, tiger part a works. Tiger part b exposes bugs around tight quads that are nearly coincident with themselves, and are coincident with something else. The greedy coicident matcher may cause the point order to be out of sync. Still working out what to do in this case. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2321773002 Review-Url: https://codereview.chromium.org/2321773002
* fix fuzzerGravatar caryclark2016-09-09
| | | | | | | | | | | | Earlier fix aborted coincident loop on wrong condition. This aborts only when it reaches the end, and then propagates the error out correctly. TBR=reed@google.com BUG=644680, 644684 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2327053002 Review-Url: https://codereview.chromium.org/2327053002
* fix pathops fuzzersGravatar caryclark2016-09-07
| | | | | | | | | | | | | | Extreme values trigger asserts that in range values allow. Disable asserts and other tests to prevent extreme values from crashing. TBR=reed@google.com BUG=644684. 644680, 644640 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2316173002 Review-Url: https://codereview.chromium.org/2316173002
* 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
* path ops stream-liningGravatar caryclark2016-08-25
| | | | | | | | | | | | | | | | The addT() function is a workhorse of pathops. Make it simpler, removing branches and parameters. Separate addOpp() into const and modify parts. Add more debugging that asserts if the function fails and the data is not extreme (e.g., fuzzer generated). TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2273293004 Review-Url: https://codereview.chromium.org/2273293004
* add pathops debuggingGravatar caryclark2016-08-25
| | | | | | | | | | | | | | | | | | | Pathops has many points of failure, most of which are triggered by extreme data generated by fuzzers. It's difficult to figure out which failure point was triggered when the operation gives up. Add instrumentation so that the failure can be debugged when the data is well-behaved. Also, add a check that looks for a sequence of coincident points on multiple edges that are out of order when compared to each other. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2274803003 Review-Url: https://codereview.chromium.org/2274803003
* remove point aliasesGravatar caryclark2016-08-24
| | | | | | | | | | | | | | | | This removes the notion of keeping track of every different t value that resolves to the same or a similar point. Other fixes make this concept unnecessary, and removing it simplifies the code. This removes an allocation, and speeds up paths with many overlapping curves. As a bonus, four fuzzer tests that failed before now succeed. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2275703003 Review-Url: https://codereview.chromium.org/2275703003
* fix fuzzesGravatar caryclark2016-08-19
| | | | | | | | TBR=reed@google.com BUG=639157, 638783 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2255243003 Review-Url: https://codereview.chromium.org/2255243003
* fix fuzz bugGravatar caryclark2016-08-16
| | | | | | | | TBR=reed@google.com BUG=637968, 638002 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2250573003 Review-Url: https://codereview.chromium.org/2250573003
* 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
* template intersection fuzz fixesGravatar caryclark2016-08-08
| | | | | | | | | | | | | Plumb in the ability to ignore asserts for out of range input deeper into the template intersection code. Exit gracefully when error conditions are found. TBR=reed@google.com BUG=632607,632628,633063,633065,634251,633608 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2224823004 Review-Url: https://codereview.chromium.org/2224823004
* fuzz wednesdayGravatar caryclark2016-07-27
| | | | | | | | | | | | | Add debug 'skip assert' access to SkCoincidentSpans. That permits suppressing asserts to make it easier to detect when this fuzz data generates unparsable data. TBR=reed@google.com BUG=631564, 631992 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2186973002 Review-Url: https://codereview.chromium.org/2186973002
* fix fuzz bugsGravatar caryclark2016-07-26
| | | | | | | | | | | | | | | Add ability for intersection template to detect that the test contains bounded numbers so that extra asserts can trigger. Add some exit points for out of range numbers in those templates. TBR=reed@google.com BUG=631383,631374,631360 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2185703002 Review-Url: https://codereview.chromium.org/2185703002
* fix fuzzGravatar caryclark2016-07-25
| | | | | | | | | | | | Extreme inputs trigger asserts intended for in range data. Return an error without asserting unless the test signals otherwise. TBR=reed@google.com BUG=630736 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2178923002 Review-Url: https://codereview.chromium.org/2178923002
* fix fuzzer bugGravatar caryclark2016-07-21
| | | | | | | | | | | | | | | | | Fix another fuzzer bug. Some PathOps asserts only make sense if the incoming data is well-behaved. Well-behaved tests set debugging state to trigger these additional asserts. Formalize this by creating macros similar to SkASSERT that check to see if the assert should be skipped. TBR=reed@google.com BUG=629962 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2169863002 Review-Url: https://codereview.chromium.org/2169863002
* 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 fuzz bugsGravatar caryclark2016-06-28
| | | | | | | | | | | | | | | | Detect more places where the pathops numerics cause numbers to become nearly identical and subsequently fail. These tests have extreme inputs and cannot succeed. Also remove the expectSuccess parameter from PathOpsDebug and check instead in the test framework. R=mbarbella@chromium.org TBR=reed@google.com BUG=623072,623022 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103513002 Review-Url: https://codereview.chromium.org/2103513002
* add fail condition to addexpandedGravatar caryclark2016-06-10
| | | | | | | | | | | If coincident pairs don't match, give up rather than deref null. R=fmalita@chromium.org BUG=618991 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2058773002 Review-Url: https://codereview.chromium.org/2058773002
* fix pathops fuzz bugsGravatar caryclark2016-06-08
| | | | | | | | | | | | | | | | | | | Fail out in a couple of new places when the input data is very large and exceeds the limits of the pathops machinery. Most of the change here plumbs in a way to exclude an assert in one of these exceptional cases. The current SkAddIntersection implementation and the inner functions it calls has no way to report an error to the root caller for an early exit, so rather than add that in, exclude the assert when the test that would trigger it runs (allowing the test to otherwise ensure that it properly fails). TBR=reed@google.com BUG=617586,617635 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2046713003 Review-Url: https://codereview.chromium.org/2046713003
* give up if huge paths have unresolvable coincidenceGravatar caryclark2016-04-05
| | | | | | | | | | | | This fuzzy test has enormous curves with coincidence runs that break numerics. If the computed intersections identify that the span of coincidence has been deleted, give up and return that the path op failed. TBR=reed@google.com BUG=597926 GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1854333002 Review URL: https://codereview.chromium.org/1854333002
* detach -> releaseGravatar mtklein2016-03-16
| | | | | | | | | | | | | The C++ standard library uses the name "release" for the operation we call "detach". Rewriting each "detach(" to "release(" brings us a step closer to using standard library types directly (e.g. std::unique_ptr instead of SkAutoTDelete). This was a fairly blind transformation. There may have been unintentional conversions in here, but it's probably for the best to have everything uniformly say "release". BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1809733002 Review URL: https://codereview.chromium.org/1809733002
* path ops: check for deleted endsGravatar caryclark2015-12-14
| | | | | | | TBR=fmalita@chromium.org BUG=569540 Review URL: https://codereview.chromium.org/1524803002
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 09:17:55 +0000