aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkOpCoincidence.h
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>
* 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>
* 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 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
* 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>
* 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
* 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
* 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
* 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
* 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
* 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
* 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 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
* 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
* 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
* When three or more edges are coincident, the logic needsGravatar caryclark2015-07-06
| | | | | | | | | | | | | | | | to compute the overlapping ranges and combine the winding into a single destination. This computes coincidence more rigorously, fixing the edge cases exposed by this bug. Also, add the ability to debug and dump pathop structures from the coincident context. TBR=reed@google.com BUG=skia:3651 Review URL: https://codereview.chromium.org/1182493015
* deal more consistently with unsortable edgesGravatar caryclark2015-05-13
| | | | | | | | | | | | | Improve line/curve coincident detection and resolution. This fixed the remaining simple failures. When an edge is unsortable, use the ray intersection to determine the angles' winding. Deal with degenerate segments. TBR=reed@google.com BUG=skia:3588,skia:3762 Review URL: https://codereview.chromium.org/1140813002
* Path ops formerly found the topmost unprocessed edge and determined its ↵Gravatar caryclark2015-05-11
| | | | | | | | | | | | | | | angle sort order to initialize the winding. This never worked correctly with cubics and was flaky with paths consisting mostly of vertical edges. This replacement shoots axis-aligned rays through all intersecting edges to find the outermost one either horizontally or vertically. The resulting code is smaller and twice as fast. To support this, most of the horizontal / vertical intersection code was rewritten and standardized, and old code supporting the top-directed winding was deleted. Contours were pointed to by an SkTDArray. Instead, put them in a linked list, and designate the list head with its own class to ensure that methods that take lists of contours start at the top. This change removed a large percentage of memory allocations used by path ops. TBR=reed@google.com BUG=skia:3588 Review URL: https://codereview.chromium.org/1111333002
* 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
* 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-07-01 21:23:40 +0000