aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
Commit message (Collapse)AuthorAge
* use reversePathTo in place of addPathReverseGravatar caryclark2016-11-07
| | | | | | | | | | | | | | Path ops was using addPathReverse, instead of reversePathTo. The former adds a moveTo always, and the latter requires that the caller add the moveTo if needed. Simplify the reversePathTo implementation. R=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2481463002 Committed: https://skia.googlesource.com/skia/+/d8db392be9dd1887df04b10b5670991d6b098c17 Review-Url: https://codereview.chromium.org/2481463002
* Revert of use reversePathTo in place of addPathReverse (patchset #1 id:1 of ↵Gravatar caryclark2016-11-04
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/2481463002/ ) Reason for revert: breqking some bots Original issue's description: > use reversePathTo in place of addPathReverse > > Path ops was using addPathReverse, instead of reversePathTo. > The former adds a moveTo always, and the latter requires > that the caller add the moveTo if needed. > > Simplify the reversePathTo implementation. > > R=reed@google.com > GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2481463002 > > Committed: https://skia.googlesource.com/skia/+/d8db392be9dd1887df04b10b5670991d6b098c17 TBR=reed@google.com # Skipping CQ checks because original CL landed less than 1 days ago. NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review-Url: https://codereview.chromium.org/2478763003
* use reversePathTo in place of addPathReverseGravatar caryclark2016-11-04
| | | | | | | | | | | | | Path ops was using addPathReverse, instead of reversePathTo. The former adds a moveTo always, and the latter requires that the caller add the moveTo if needed. Simplify the reversePathTo implementation. R=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2481463002 Review-Url: https://codereview.chromium.org/2481463002
* 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 fuzzGravatar caryclark2016-10-25
| | | | | | | | | | Abort early if fuzz data breaks intersection. R=kjlubick@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2444333002 Review-Url: https://codereview.chromium.org/2444333002
* 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
* nc seal breaks simplifyGravatar caryclark2016-10-24
| | | | | | | | | | | | | | | This test has nearly coincident lines that are missorted. The underlying bug is caused when a pair of curves are coincident when reduced to line segments, but the end points aren't detected. The error was generated by running nanobench over all svg sample data with the distance field patch installed. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2440043003 Review-Url: https://codereview.chromium.org/2440043003
* formalize host debuggingGravatar caryclark2016-10-24
| | | | | | | | | | | | | | Pathops writes files, anticipating upcoming crashes, and verifies the results against regions. Formalize these debugging methods so that they are more easily triggered by hosts outside of skia unit tests. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2441763003 Review-Url: https://codereview.chromium.org/2441763003
* 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 debug version of cubicpair detected by asanGravatar caryclark2016-10-20
| | | | | | | TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2435063002 Review-Url: https://chromiumcodereview.appspot.com/2435063002
* 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
* break ambiguous angle sorting loopGravatar caryclark2016-10-18
| | | | | | | | | | | | | | | | | | A pair of cubics may be difficult to sort if the tangents suggest one sort but the midpoints suggest a different one. When in this gray area, and when the cumulative sort of all the angles fails to resolve, reverse the sort to break the tie. Before, when tiger8 was run through the signed distance field generated directly from the path data, the simplify call might hang since the angle could not be resolved. If the endless loop is detected, and if there is no tie to break, just fail instead. TBR=reed@google.com BUG=skia:5131 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2426753002 Review-Url: https://codereview.chromium.org/2426753002
* 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>
* tight bounds optimizationGravatar caryclark2016-10-05
| | | | | | | | | | | | | | | | | Add support for tight bounds to detect and return moveTo followed by close or zero-length lineTo. Also short circuit so that hard work is avoided when the path bounds is also the tight bounds. Avoid doing work if the bounds can be trivially computed. Include naked moveTo coordinates in the tight bounds. R=fmalita@chromium.org BUG=skia:5555, skia:5553 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2394443004 Review-Url: https://codereview.chromium.org/2394443004
* fix fuzzGravatar Cary Clark2016-10-05
| | | | | | | | | | | | | | | | This fix is slightly interesting; if the final close of the contour degenerates into a zero-length line, remove the previous line from the generated contour. TBR=reed@google.com BUG=skia:5822 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=3004 Change-Id: Id668d13ccf6aad9bc81d78588fc77437527a0b7b Reviewed-on: https://skia-review.googlesource.com/3004 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 cubic linear testGravatar caryclark2016-09-28
| | | | | | | | | | | | | | Check to see if the line between end points is degenerate before measuring control points. Also, add test case for a bug to see if it shows up on any platform. TBR=reed@google.com BUG=skia:5169, skia:5240 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2375053002 Review-Url: https://codereview.chromium.org/2375053002
* allow conic chop to failGravatar caryclark2016-09-26
| | | | | | | | | | | | | Fuzzy values may cause the conic chop to fail. Check to see if the values are all finite, and require the caller to do the same. R=reed@google.com BUG=650178 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2368993002 Review-Url: https://codereview.chromium.org/2368993002
* 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
* fix msan bug in pathopsGravatar caryclark2016-09-23
| | | | | | | | | | | | Msan and Valgrind found an uninitialized memory mistake in pathops. This also fixes similar bugs where not all parts of the geometry were covered in the loop iteration. R=borenet@google.com NOTREECHECKS=true GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2366893003 Review-Url: https://codereview.chromium.org/2366893003
* 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
* don't close a contour with a line if nothing's thereGravatar caryclark2016-09-22
| | | | | | | | R=kjlubick@google.com BUG=skia:5789 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2360083006 Review-Url: https://codereview.chromium.org/2360083006
* 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 skia pathops fuzzersGravatar caryclark2016-09-21
| | | | | | | | | | Add isolated tests. R=kjlubick@google.com BUG=skia:5775 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2358043002 Review-Url: https://codereview.chromium.org/2358043002
* 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
* Rewriting path writerGravatar caryclark2016-09-14
| | | | | | | | | | | | | | | | | | | | | | | | | The path writer takes constructs the output path out of curves that satisfy the pathop operation. Curves contain lists of t/point pairs that may not be comparable to each other. To match up curve ends in the output path, look for adjacent curves to have a shared membership rather than comparing point values. Use path utilities to connect partial curve lists into closed contours. Share the angle code that determines if a curve has become a degenerate line with the path writer. Clean up some code on the way, and delete some unused functions. TBR=reed@google.com BUG=5188 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2321973005 Review-Url: https://codereview.chromium.org/2321973005
* change SkStreams to work with sk_sp<SkData> instead of SkData*Gravatar reed2016-09-12
| | | | | | | BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2333713002 Review-Url: https://codereview.chromium.org/2333713002
* 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
* provide safe exit for runaway intersectionsGravatar caryclark2016-09-06
| | | | | | | | | | | | | | Curve intersections with extreme numbers may cause the intersection template code to loop forever. Detect this by looking for marking more spans gone than exist, and return without any intersections found. TBR=reed@google.com BUG=643855 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2310113002 Review-Url: https://codereview.chromium.org/2310113002
* 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
* if the winding of the top can't be computed, give upGravatar caryclark2016-08-26
| | | | | | | | TBR=reed@google.com BUG=641478 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2283993002 Review-Url: https://codereview.chromium.org/2283993002
* 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 pathops fuzzGravatar caryclark2016-08-23
| | | | | | | | | | | Extreme cubics may split so that one half is a point. Discard this rather than generating a degenerate line. TBR=reed@google.com BUG=640025 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2276503002 Review-Url: https://codereview.chromium.org/2276503002
* 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 fuzzGravatar caryclark2016-08-17
| | | | | | | | TBR=reed@google.com BUG=638496 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2250413002 Review-Url: https://codereview.chromium.org/2250413002
* 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-04 15:53:03 +0000