aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkPathOpsTSect.h
Commit message (Collapse)AuthorAge
* fix fuzzGravatar Cary Clark2017-01-04
| | | | | | | | | | R=kjlubick@google.com BUG=skia:6084 Change-Id: I5978805c8d9048e399d83a13173c6a776cabe8ac Reviewed-on: https://skia-review.googlesource.com/6544 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 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
* 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
* 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 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
* 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
* 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
* 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
* 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
* 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
* 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
* 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
* 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 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 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
* 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
* only call scalar finite when necessaryGravatar caryclark2015-12-16
| | | | | | | | | | | | | | | | | Mike points that the the ulps compares rank high in path ops profiles. The check for finite scalars is rarely required. Call it less by: - specializing _pin version of compares - checking for 0 divides up front - handling failing cases before comparing - casting float to double before adding R=reed@google.com Review URL: https://codereview.chromium.org/1522183002
* More conic-specific tests revealed a few conic-specific bugs. Because ↵Gravatar caryclark2015-10-30
| | | | | | | | | | | | | | | | | | | | | | | | javascript / canvas make visualizing conics tricky, new native tools are required. The utility SubsetPath removes parts of a potentially very large path to isolate a minimal test case. SubsetPath is very useful for debugging path ops, but is not path ops specific. PathOpsBuilderConicTest compares the output of the Path Ops Builder, sequential calls to Simplify, and SkRegions for some number of rotated ovals. Some tests caused path ops to hang. It was caught adding a loop of curves because the head was not found by the tail. Even though the root cause has been fixed, SkSegment::addCurveTo callers now abort the path op if the same curve was added twice. The subdivided conic weight was been computed anew. Fortunately, it's a simpler computation that the one it replaces. Some Simplify() subroutines returned false to signal that the results needed assembling. Change these to abort the current operation instead. Coincident curve intersection triggered two small bugs; one where no perpendicular could be found for coincident curves, and one where no coincident curves remain after looping. The SixtyOvals test can be run through multiple processes instead of multiple threads. This strategy allows a 48 core machine to saturate all cores at 100%. The DEBUG_VISUALIZE_CONICS code in PathOpsConicIntersectionTest acknowleges that it is easier to visualize conics with Skia than with script and html canvas. This test also verifies that path ops subdivision matches geometry chopping. TBR=reed@google.com Review URL: https://codereview.chromium.org/1405383004
* Reland of path ops: fix conic weight and partial coincidence (patchset #1 ↵Gravatar caryclark2015-10-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | id:1 of https://codereview.chromium.org/1408923003/ ) Reason for revert: suppressions have landed in chrome Original issue's description: > Revert of path ops: fix conic weight and partial coincidence (patchset #5 id:80001 of https://codereview.chromium.org/1413763002/ ) > > Reason for revert: > path ops change breaks svg clipping layout tests -- conic is now more accurate, changing edge of circle in clip > > These need to be rebaselined > > svg/clip-path/clip-path-child-clipped.svg > svg/clip-path/clip-path-nonzero.svg > svg/clip-path/clip-path-evenodd-nonzero.svg > svg/clip-path/clip-path-nonzero-evenodd.svg > > Original issue's description: > > The remaining 1m skp bugs are asserts that can be harmlessly > > suppressed and bugs around conics. > > > > The conic calculation for a subdivided w was just wrong. > > > > Also added debugging to template intersection to initialize > > reused structures and dump additional data. > > > > TBR=reed@google.com > > > > Committed: https://skia.googlesource.com/skia/+/ef33b1e739b23a1201100ff17a572da85b03d9af > > TBR= > NOPRESUBMIT=true > NOTREECHECKS=true > NOTRY=true > > Committed: https://skia.googlesource.com/skia/+/f428df1be3e96d3f8970d0f7f415b862f7da5404 TBR= NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1407003016
* Revert of path ops: fix conic weight and partial coincidence (patchset #5 ↵Gravatar caryclark2015-10-21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | id:80001 of https://codereview.chromium.org/1413763002/ ) Reason for revert: path ops change breaks svg clipping layout tests -- conic is now more accurate, changing edge of circle in clip These need to be rebaselined svg/clip-path/clip-path-child-clipped.svg svg/clip-path/clip-path-nonzero.svg svg/clip-path/clip-path-evenodd-nonzero.svg svg/clip-path/clip-path-nonzero-evenodd.svg Original issue's description: > The remaining 1m skp bugs are asserts that can be harmlessly > suppressed and bugs around conics. > > The conic calculation for a subdivided w was just wrong. > > Also added debugging to template intersection to initialize > reused structures and dump additional data. > > TBR=reed@google.com > > Committed: https://skia.googlesource.com/skia/+/ef33b1e739b23a1201100ff17a572da85b03d9af TBR= NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1408923003
* The remaining 1m skp bugs are asserts that can be harmlesslyGravatar caryclark2015-10-20
| | | | | | | | | | | | | suppressed and bugs around conics. The conic calculation for a subdivided w was just wrong. Also added debugging to template intersection to initialize reused structures and dump additional data. TBR=reed@google.com Review URL: https://codereview.chromium.org/1413763002
* 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
* Style Change: NULL->nullptrGravatar halcanary2015-08-27
| | | | | | DOCS_PREVIEW= https://skia.org/?cl=1316233002 Review URL: https://codereview.chromium.org/1316233002
* Style Change: SkNEW->new; SkDELETE->deleteGravatar halcanary2015-08-26
| | | | | | DOCS_PREVIEW= https://skia.org/?cl=1316123003 Review URL: https://codereview.chromium.org/1316123003
* 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
* fix valgrind uninitialized var errorGravatar caryclark2015-04-21
| | | | | | R=mtklein@google.com Review URL: https://codereview.chromium.org/1097293002
* 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
* fix valgrind uninitialized issueGravatar caryclark2015-04-13
| | | | | | | R=mtklein@google.com BUG=skia:3654 Review URL: https://codereview.chromium.org/1082753002
* fix valgrind bugGravatar caryclark2015-04-06
| | | | | | | R=mtklein BUG=skia:3654 Review URL: https://codereview.chromium.org/1064663003
* add legacy pathop enums; fix uninitialized warningGravatar caryclark2015-03-26
| | | | | | | | | | R=reed@google.com BUG=skia:3588 NOTREECHECKS=true NOTRY=true NOPRESUBMIT=true Review URL: https://codereview.chromium.org/1034073004
* 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
* new files for pathops geometric intersectionGravatar caryclark2015-01-16
There's no gyp references to these new files, so this should only have the effect of reducing the size of the commit that turns this code on. TBR= Review URL: https://codereview.chromium.org/853223002
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-20 11:51:28 +0000