aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
Commit message (Collapse)AuthorAge
...
* 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
* Fix SkDEBUGCODE to accept commasGravatar csmartdalton2016-08-10
| | | | | | | BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2231663002 Review-Url: https://codereview.chromium.org/2231663002
* 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
* require semi at the end of SkASSERT and friendsGravatar caryclark2016-07-27
| | | | | | | | R=bungeman@google.com TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2185063002 Review-Url: https://codereview.chromium.org/2185063002
* 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
* limit number of searched rootsGravatar caryclark2016-07-22
| | | | | | | | | | | | | | Extreme numbers can generate more than three found cubic roots when the roots are found through a binary search. Fail in this case. TBR=reed@google.com BUG=630649 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2176733002 Review-Url: https://codereview.chromium.org/2176733002
* conic fuzz fixGravatar caryclark2016-07-22
| | | | | | | | | | | | | | | If no closest section is found in conic intersection (which can happen if the numbers are out of range) abort the intersection. Also suppress assert fired in this case so it only checks intersections with in-range values. TBR=reed@google.com BUG=630378 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2166813006 Review-Url: https://codereview.chromium.org/2166813006
* let line/cubic intersect at four spotsGravatar caryclark2016-07-21
| | | | | | | | | With this, let's update the fuzzer. R=kjlubick@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2169983002 Review-Url: https://codereview.chromium.org/2169983002
* allow curves on side of lines to be very smallGravatar caryclark2016-07-21
| | | | | | | | | | | | | | Increase the precision of the 'all on one side' pathops angle test to reduce the number of unorderable segments found by the cubics_d3 test. This allows pathsops_unittest release build with -v -V -x to run without error. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2168163002 Review-Url: https://codereview.chromium.org/2168163002
* fix builder fuzzGravatar caryclark2016-07-21
| | | | | | | | | Fix ASAN_heap-use-after-free crash R=kjlubick GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2168963002 Review-Url: https://codereview.chromium.org/2168963002
* 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
* fix fuzzerGravatar caryclark2016-07-19
| | | | | | | | | | | | Previous spans always have a valid next pointer. The final span does not. Change the test for a valid link to take into consideration whether the links are chased forwards or backwards. TBR=reed@google.com BUG=629454 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2166543002 Review-Url: https://codereview.chromium.org/2166543002
* 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 asan bug triggered by pathops fuzz testsGravatar caryclark2016-06-29
| | | | | | | | R=dogben@google.com TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2111473004 Review-Url: https://codereview.chromium.org/2111473004
* fix another pathops fuzz bugGravatar caryclark2016-06-29
| | | | | | | | | | | | Tunnel out the error case when the numerics create uncalculable angles. R=mmoroz@chromium.org TBR=reed@google.com BUG=624351 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103863005 Review-Url: https://codereview.chromium.org/2103863005
* fix fuzz test that exceeds numeric limitGravatar caryclark2016-06-29
| | | | | | | | | | | | The extreme values here exceed an internal test that expects computed numbers to be less than MAX_FLT. Use MAX_DBL instead. R=mmoroz@chromium.org TBR=reed@google.com BUG=624346 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2103903004 Review-Url: https://codereview.chromium.org/2103903004
* 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
* A Mozilla developer ran the µmix static analyzer on its codebase and ↵Gravatar lsalzman2016-06-07
| | | | | | | | | | | incidentally found some issues regarding null checks in Skia. This fixes the issues that were found. Downstream bug report: https://bugzilla.mozilla.org/show_bug.cgi?id=1278452 BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2046563007 Review-Url: https://codereview.chromium.org/2046563007
* pin before calling acosGravatar caryclark2016-05-27
| | | | | | | | | | | | Adobe reports some user crashes in acos(). While the cause is unknown, it's safe and may help stability to pin the input in case the arguments drifted slightly outside [-1, 1]. R=reed@google.com BUG=skia:5222 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2006653006 Review-Url: https://codereview.chromium.org/2006653006
* 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
* Revert of SK_DECLARE_STATIC_MUTEX -> static SkMutex (patchset #1 id:1 of ↵Gravatar reed2016-05-04
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1948193002/ ) Reason for revert: broken the Mac and Linux builders, e.g.: https://build.chromium.org/p/chromium/builders/Mac/builds/15151 https://build.chromium.org/p/chromium/builders/Linux%20x64/builds/19052 Original issue's description: > SK_DECLARE_STATIC_MUTEX -> static SkMutex > > There's no need to use a macro to declare static SkMutexes any more > (and there's likewise no need to restrict them to global scope). > > BUG=skia: > GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1948193002 > > Committed: https://skia.googlesource.com/skia/+/5e56cfd3fa1041dbb83899844fb92fa9a2ef1009 TBR=mtklein@google.com,mtklein@chromium.org # Skipping CQ checks because original CL landed less than 1 days ago. NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true BUG=skia: Review-Url: https://codereview.chromium.org/1945353003
* SK_DECLARE_STATIC_MUTEX -> static SkMutexGravatar mtklein2016-05-04
| | | | | | | | | | There's no need to use a macro to declare static SkMutexes any more (and there's likewise no need to restrict them to global scope). BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1948193002 Review-Url: https://codereview.chromium.org/1948193002
* Fix warnings that were exposed when running with SK_DEBUG enable on an ↵Gravatar djsollen2016-04-29
| | | | | | | | optimized release build. GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1917223006 Review-Url: https://codereview.chromium.org/1917223006
* pathops: Split loop type cubics only when there is a self-intersection.Gravatar deanm2016-04-26
| | | | | | | | | | | | | The ComplexBreak code comes from Loop and Blinn, which requires loops to be split if either double point is visible. However for intersection loops only need to be split when there is actually a self-intersection (when both double points are in [0, 1]). This patch splits cubics much less often so the output doesn't have extra segments unless the input had a self-intersecting loop. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1920663002 Review URL: https://codereview.chromium.org/1920663002
* pathops: Cosmetic only change, update comments around ComplexBreak().Gravatar deanm2016-04-26
| | | | | | | | | | Rename loopT to splitT and make it clearer that it is not just self intersecting loop cubics that are split. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1921173003 Review URL: https://codereview.chromium.org/1921173003
* pathops: Add missing header guards in two files.Gravatar deanm2016-04-26
| | | | | | | | | | Guards were missing in SkIntersectionHelper.h and SkPathOpsTSect.h. BUG=skia: GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1914873002 Review URL: https://codereview.chromium.org/1914873002
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-07 11:55:41 +0000