aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkOpEdgeBuilder.cpp
Commit message (Collapse)AuthorAge
* fix fuzzing empty contours squirrelly cubicsGravatar Cary Clark2016-12-16
| | | | | | | | | | | | | | | | | | | The fuzzer triggered relatively new code that missized the split cubic array, i.e., if a cubic is split in three places it makes four cubics. The fuzzer triggered other relative new code that permits a contour to be empty. This happens when a line crosses over itself but doesn't enclose anything. R=kjlubick@google.com BUG=skia:6061 Change-Id: I0c04d0d390ff1092f7b3bb28ebbfca517451f497 Reviewed-on: https://skia-review.googlesource.com/6223 Commit-Queue: Cary Clark <caryclark@google.com> Reviewed-by: Kevin Lubick <kjlubick@google.com>
* more simplify bugsGravatar Cary Clark2016-12-14
| | | | | | | | | | | | | | | | | | | | | | | | | | SkOpAngle::alignmentSameSide() Shifting an edge to align it for angle sorting may move a compared edge to the opposite side. For lines that are shifted, check to see if this is so. class SkOpContourBuilder If the path contains a pair of lines that cancel, skip them as early as possible. While not strictly necessary, this optimization is cheap and makes debugging much easier. SkOpEdgeBuilder::walk() case SkPath::kCubic_Verb: If max curvature or inflections break a cubic into pieces, make sure that the pieces are large enough to process. If not, add the broken piece back to a neighbor. Correct debugging that had gone stale. Add active span debugging cache so only changes are shown. TBR=reed@google.com BUG=skia:6401 Change-Id: I766f77e4fb9b76537cf5464961addb103114f5db Reviewed-on: https://skia-review.googlesource.com/5764 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* simplify bugGravatar Cary Clark2016-12-08
| | | | | | | | | | | | | | | | | | | | | | | The path contains a cubic with a very tight curve. Split the cubic into pieces so that the individual curves are better behaved. Use both inflections and max curvature to potentially split cubics. Since this may require a bit of work, preflight to ignore cubics that monotonically change in x and y. Only one of the three tests referred to by the bug below repro'd. Use path.dumpHex() instead of path.dump() to capture the crashing data. TBR=reed@google.com BUG=skia:6041 Change-Id: I29a264f87242cacc7c421e7685b90aca81621c74 Reviewed-on: https://skia-review.googlesource.com/5702 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* 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>
* 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>
* 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 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
* 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
* 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
* 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
* 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
* remove unused fields from SkOpSegmentGravatar caryclark2015-09-04
| | | | | | TBR=reed@google.com Review URL: https://codereview.chromium.org/1322413002
* working on initial winding for cubicsGravatar caryclark2015-04-23
| | | | | | | | | | | Path ops works well for all tests except for cubics. Isolate failures caused by cubics, and do a better job of computing the initial winding for cubics. TBR=reed@google.com BUG=skia:3588 Review URL: https://codereview.chromium.org/1096923003
* Now, path ops natively intersect conics, quads, and cubics in any ↵Gravatar caryclark2015-04-20
| | | | | | | | | | | combination. There are still a class of cubic tests that fail and a handful of undiagnosed failures from skps and fuzz tests, but things are much better overall. Extended tests (150M+) run to completion in release in about 6 minutes; the standard test suite exceeds 100K and finishes in a few seconds on desktops. TBR=reed BUG=skia:3588 Review URL: https://codereview.chromium.org/1037953004
* cumulative pathops patchGravatar caryclark2015-03-26
| | | | | | | | | | | | | | | | | | | | | Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer. Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering. Unify t and point values so that small intervals can be eliminated in one pass. Break cubics up front to eliminate loops and cusps. Make the Simplify and Op code more regular and eliminate arbitrary differences. Add a builder that takes an array of paths and operators. Delete unused code. BUG=skia:3588 R=reed@google.com Review URL: https://codereview.chromium.org/1037573004
* Revert of pathops version two (patchset #16 id:150001 of ↵Gravatar reed2015-03-24
| | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1002693002/) Reason for revert: ASAN investigation Original issue's description: > pathops version two > > R=reed@google.com > > marked 'no commit' to attempt to get trybots to run > > TBR=reed@google.com > > Committed: https://skia.googlesource.com/skia/+/ccec0f958ffc71a9986d236bc2eb335cb2111119 TBR=caryclark@google.com NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1029993002
* pathops version twoGravatar caryclark2015-03-24
| | | | | | | | | | R=reed@google.com marked 'no commit' to attempt to get trybots to run TBR=reed@google.com Review URL: https://codereview.chromium.org/1002693002
* fixes for conicsGravatar reed2015-01-06
| | | | | | | | | | - use std tolerance in edgebuilder, since the path has not been scaled-up to its super-sample size (that happens in the builder methods. - off-by-1 fix for pathops when using the output of the conicquadder BUG=skia: Review URL: https://codereview.chromium.org/837023002
* Revert of use conics for ovals and roundrects (patchset #1 id:1 of ↵Gravatar reed2015-01-06
| | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/817283005/) Reason for revert: need fix in edgebuilder+aa Original issue's description: > use conics for ovals and roundrects > > adapted from https://codereview.chromium.org/831313002/ > > BUG=skia: > TBR= > > Committed: https://skia.googlesource.com/skia/+/2bf1c4d58b84c73c6421edcb25e3afb4971da200 TBR=reed@chromium.org NOTREECHECKS=true NOTRY=true BUG=skia: Review URL: https://codereview.chromium.org/840573002
* use conics for ovals and roundrectsGravatar reed2015-01-05
| | | | | | | | | adapted from https://codereview.chromium.org/831313002/ BUG=skia: TBR= Review URL: https://codereview.chromium.org/817283005
* fix battlefield website by disallowing very small coordinatesGravatar caryclark2014-09-18
| | | | | | | | | | | also add and remove comments to document other attempts to fix this that had drawbacks R=fmalita@chromium.org BUG=414409 Author: caryclark@google.com Review URL: https://codereview.chromium.org/575553003
* one more tsan fixGravatar commit-bot@chromium.org2014-04-25
| | | | | | | | | | | | BUG=skia:2460 R=mtklein@google.com TBR=mtklein Author: caryclark@google.com Review URL: https://codereview.chromium.org/255893002 git-svn-id: http://skia.googlecode.com/svn/trunk@14382 2bbb7eff-a529-9590-31e7-b0007b416f81
* fix minor skp-found bugsGravatar commit-bot@chromium.org2014-04-25
| | | | | | | | | | | | | remove globals from pathops_unittest BUG=skia:2460 TBR=mtklein Author: caryclark@google.com Review URL: https://codereview.chromium.org/239563004 git-svn-id: http://skia.googlecode.com/svn/trunk@14378 2bbb7eff-a529-9590-31e7-b0007b416f81
* pathops work in progressGravatar caryclark@google.com2013-11-01
| | | | | | | | BUG= Review URL: https://codereview.chromium.org/52653002 git-svn-id: http://skia.googlecode.com/svn/trunk@12089 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-09-16
| | | | | | | | | | path ops work in progress BUG= Review URL: https://codereview.chromium.org/21359002 git-svn-id: http://skia.googlecode.com/svn/trunk@11291 2bbb7eff-a529-9590-31e7-b0007b416f81
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-07-09
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@9919 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-07-08
| | | | | | | | BUG= Review URL: https://codereview.chromium.org/18058007 git-svn-id: http://skia.googlecode.com/svn/trunk@9908 2bbb7eff-a529-9590-31e7-b0007b416f81
* convert pathops to use SkSTArray where possible.Gravatar caryclark@google.com2013-06-17
| | | | | | | | | | | | | | | | | | Replace SkTDArray with SkTArray and use SkSTArray when the probable array size is known. In a couple of places (spans, chases) the arrays are constructed using insert() so SkTArrays can't be used for now. Also, add an optimization to cubic subdivide if either end is zero or one. BUG= Review URL: https://codereview.chromium.org/16951017 git-svn-id: http://skia.googlecode.com/svn/trunk@9635 2bbb7eff-a529-9590-31e7-b0007b416f81
* bump picture version since SkPath has changed (conics)Gravatar reed@google.com2013-05-31
| | | | | | enable conics in SkPath git-svn-id: http://skia.googlecode.com/svn/trunk@9370 2bbb7eff-a529-9590-31e7-b0007b416f81
* Revert "add asserts to point<-->verb helpers"Gravatar reed@google.com2013-05-30
| | | | | | This reverts commit b4775ac7b55802e87231768f002e4b42f233b0aa. git-svn-id: http://skia.googlecode.com/svn/trunk@9347 2bbb7eff-a529-9590-31e7-b0007b416f81
* add asserts to point<-->verb helpersGravatar reed@google.com2013-05-30
| | | | | | | | | | patch from issue 16153005 BUG= Review URL: https://codereview.chromium.org/16195004 git-svn-id: http://skia.googlecode.com/svn/trunk@9344 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops -- handle non-finite numbersGravatar caryclark@google.com2013-04-26
| | | | | | | | Op() and Simplify() do nothing if the input is non-finite. Add code and tests. Review URL: https://codereview.chromium.org/14407006 git-svn-id: http://skia.googlecode.com/svn/trunk@8882 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops : fix empty-diff bug, op-in-placeGravatar caryclark@google.com2013-04-25
| | | | | | | add some debugging around reverse diff, inverse Review URL: https://codereview.chromium.org/13851015 git-svn-id: http://skia.googlecode.com/svn/trunk@8852 2bbb7eff-a529-9590-31e7-b0007b416f81
* Add base types for path opsGravatar caryclark@google.com2013-04-08
Paths contain lines, quads, and cubics, which are collectively curves. To work with path intersections, intermediary curves are constructed. For now, those intermediates use doubles to guarantee sufficient precision. The DVector, DPoint, DLine, DQuad, and DCubic structs encapsulate these intermediate curves. The DRect and DTriangle structs are created to describe intersectable areas of interest. The Bounds struct inherits from SkRect to create a SkScalar-based rectangle that intersects shared edges. This also includes common math equalities and debugging that the remainder of path ops builds on, as well as a temporary top-level interface in include/pathops/SkPathOps.h. Review URL: https://codereview.chromium.org/12827020 git-svn-id: http://skia.googlecode.com/svn/trunk@8551 2bbb7eff-a529-9590-31e7-b0007b416f81
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-07 16:45:34 +0000