aboutsummaryrefslogtreecommitdiffhomepage
path: root/tools/pathops_sorter.htm
Commit message (Collapse)AuthorAge
* handle degenerate cubic loopsGravatar Cary Clark2018-02-02
| | | | | | | | | | | | | | | | | | | fuzzer generated a cubic with a very tiny loop at one end. Breaking the cubic in two generated a piece so small it was discarded, passing the original along. Instead, use the loop detection as a hint that passing the original may fail further along. Keep the big piece, which is more linear than the original; and change its end to match the original input if the small piece isn't worth keeping. R=kjlubick Bug: skia:7480 Change-Id: If4c5cd46dbf7e16526269f2854e4f2278f427461 Reviewed-on: https://skia-review.googlesource.com/103100 Reviewed-by: Kevin Lubick <kjlubick@google.com> Commit-Queue: Cary Clark <caryclark@skia.org>
* Remove carriage returns.Gravatar Ben Wagner2017-10-09
| | | | | | | | | Also add a presubmit so they don't get added to source code. Change-Id: I6a85c6a934b1068a63646a0dcc0d3a08baa96ced Reviewed-on: https://skia-review.googlesource.com/57110 Reviewed-by: Ravi Mistry <rmistry@google.com> Commit-Queue: Ben Wagner <bungeman@google.com>
* add nonsquare scale to pathops sorter toolGravatar Cary Clark2017-06-02
| | | | | | | Change-Id: I1b45992cc6eb18d0f79edcbd97d00d73c66c349a Reviewed-on: https://skia-review.googlesource.com/18035 Reviewed-by: Cary Clark <caryclark@google.com> Commit-Queue: Cary Clark <caryclark@google.com>
* Revert "offset angle check edge in common"Gravatar Cary Clark2017-01-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit d2eb581ebc8f8009e80cccccd74d5b341ef5bd5b. Reason for revert: broke Google3 MSAN run of dm Original change's description: > offset angle check edge in common > > When curves cross, their intersection points may be nearby, but not exactly the same. > Sort the angles formed by the crossing curves when all angles don't have the same > origin. > > This sets up the framework to solve test case that currently fail (e.g., joel6) but > does not fix all related test cases (e.g., joel9). > > All older existing test cases, including extended tests, pass. > > Rework the test framework to better report when tests expected to produce failing > results now pass. > > Add new point and vector operations to support offset angles. > > TBR=reed@google.com > BUG=skia:6041 > > Change-Id: I67c651ded0a25e99ad93d55d6a35109b3ee3698e > Reviewed-on: https://skia-review.googlesource.com/6624 > Commit-Queue: Cary Clark <caryclark@google.com> > Reviewed-by: Cary Clark <caryclark@google.com> > TBR=caryclark@google.com,reviews@skia.org # Not skipping CQ checks because original CL landed > 1 day ago. BUG=skia:6041 Change-Id: I43db0808522ac44aceeb4f70e296167ea84a3663 Reviewed-on: https://skia-review.googlesource.com/7373 Commit-Queue: Cary Clark <caryclark@google.com> Reviewed-by: Cary Clark <caryclark@google.com>
* offset angle check edge in commonGravatar Cary Clark2017-01-20
| | | | | | | | | | | | | | | | | | | | | | | | When curves cross, their intersection points may be nearby, but not exactly the same. Sort the angles formed by the crossing curves when all angles don't have the same origin. This sets up the framework to solve test case that currently fail (e.g., joel6) but does not fix all related test cases (e.g., joel9). All older existing test cases, including extended tests, pass. Rework the test framework to better report when tests expected to produce failing results now pass. Add new point and vector operations to support offset angles. TBR=reed@google.com BUG=skia:6041 Change-Id: I67c651ded0a25e99ad93d55d6a35109b3ee3698e Reviewed-on: https://skia-review.googlesource.com/6624 Commit-Queue: Cary Clark <caryclark@google.com> Reviewed-by: 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>
* 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 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
* 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 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
* 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
* 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
* 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
* 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
* fix pathops battle testGravatar caryclark2015-07-07
| | | | | | | | | | The intermediate subtraction threw away bits causing the subsequent cross product to fail. Defer the bit truncation until after the vector is computed. TBR=reed@google.com Review URL: https://codereview.chromium.org/1226933003
* 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
* handle large conic strokes betterGravatar caryclark2015-05-19
| | | | | | | | | | | | | | | | | | | | A stroked conic computes the outset quad's control point by computing the intersection of the quad's endpoints. If the the denominator used to compute the scale factor for the control point is small, check to see if the numerator is also small so that the division stays bounded. Also clean up error returns and internal function calls to simplify the code. Additionally, remove comic max curvature (unimplemented) and call extrema functions instead to handle cases where the conic is degenerate or is a line. R=reed@google.com, fmalita@chromium.org BUG=skia:3843 Review URL: https://codereview.chromium.org/1144883003
* 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
* minor fixes to cubics code and overall alignment of how bounds and tops are ↵Gravatar caryclark2015-04-29
| | | | | | | | | | | | computed for all curve types All but 17 extended tests work. A helper function is privately added to SkPath.h to permit a test to modify a given point in a path. BUG=skia:3588 Review URL: https://codereview.chromium.org/1107353004
* fix multiple intersection logicGravatar caryclark2015-04-24
| | | | | | | | | | | When three or more curves intersect at the same point, ensure that each curve records the intersections of the others. This fixes a number of cubic tests. TBR=reed@google.com BUG=skia:3588 Review URL: https://codereview.chromium.org/1105943002
* 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
* These tests stress pathops by describing the union of circle-like paths that ↵Gravatar caryclark2014-11-13
| | | | | | | | | | | | | | | | | | | have tiny line segments embedded and double back to create near-coincident conditions. The fixes include - detect when finding the active top loops between two possible answers - preflight chasing winding to ensure answer is consistent - binary search more often when quadratic intersection fails - add more failure paths when an intersect is missed While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. TBR= BUG=421132 Committed: https://skia.googlesource.com/skia/+/6f726addf3178b01949bb389ef83cf14a1d7b6b2 Review URL: https://codereview.chromium.org/633393002
* Revert of harden pathops for pathological test (patchset #19 id:410001 of ↵Gravatar hcm2014-10-28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/633393002/) Reason for revert: Compile errors on bots Original issue's description: > These tests stress pathops by describing the union of circle-like paths that have tiny line segments embedded and double back to create near-coincident conditions. > > The fixes include > - detect when finding the active top loops between two possible answers > - preflight chasing winding to ensure answer is consistent > - binary search more often when quadratic intersection fails > - add more failure paths when an intersect is missed > > While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. > > TBR= > BUG=421132 > > Committed: https://skia.googlesource.com/skia/+/6f726addf3178b01949bb389ef83cf14a1d7b6b2 TBR=caryclark@google.com NOTREECHECKS=true NOTRY=true BUG=421132 Review URL: https://codereview.chromium.org/686843002
* These tests stress pathops by describing the union of circle-like paths that ↵Gravatar caryclark2014-10-28
| | | | | | | | | | | | | | | | | have tiny line segments embedded and double back to create near-coincident conditions. The fixes include - detect when finding the active top loops between two possible answers - preflight chasing winding to ensure answer is consistent - binary search more often when quadratic intersection fails - add more failure paths when an intersect is missed While this fixes the chrome bug, reenabling path ops in svg should be deferred until additional fixes are landed. TBR= BUG=421132 Review URL: https://codereview.chromium.org/633393002
* 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
* add cubic red option to pathops toolGravatar caryclark2014-07-29
| | | | | | | | | | | R=reed@google.com TBR=reed@google.com NOTREECHECKS=true NOTRY=true Author: caryclark@google.com Review URL: https://codereview.chromium.org/428963004
* update pathops core and testsGravatar caryclark2014-07-18
| | | | | | | | | | split out skpclip (the test of 1M pictures) into its own project TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/400033002
* Fix last pathops skp bugGravatar caryclark2014-06-18
| | | | | | | | | | | | | | | | | | | | | | This fixes the last bug discovered by iterating through the 800K skp corpus representing the top 1M websites. For every clip on the stack, the paths are replaced with the pathop intersection. The resulting draw is compared with the original draw for pixel errors. At least two prominent bugs remain. In one, the winding value is confused by a cubic with an inflection. In the other, a quad/cubic pair, nearly coincident, fails to find an intersection. These minor changes include ignoring very tiny self-intersections of cubics, and processing degenerate edges that don't connect to anything else. R=reed@android.com TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/340103002
* Enabling the canvas bit to turn the clip stack into a flat replace exposed ↵Gravatar caryclark2014-06-17
| | | | | | | | | | | | | | | | | | around 100 failures when testing the 800K skp set generated from the top 1M web sites. This fixes all but one of those failures. Major changes include: - Replace angle indices with angle pointers. This was motivated by the need to add angles later but not renumber existing angles. - Aggressive segment chase. When the winding is known on a segment, more aggressively passing that winding to adjacent segments allows fragmented data sets to succeed. - Line segments with ends nearly the same are treated as coincident first. - Transfer partial coincidence by observing that if segment A is partially coincident to B and C then B and C may be partially coincident. TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/272153002
* When solving the cubic line intersection directly fails, use binary search ↵Gravatar commit-bot@chromium.org2014-05-07
| | | | | | | | | | | | | | | | | as a fallback. The cubic line intersection math empirically works 99.99% of the time (fails 3100 out of 1B random tests) but when it fails, an intersection may be missed altogether. The binary search is may not find a solution if the cubic line failed to find any solutions at all, but so far that case hasn't arisen. BUG=skia:2504 TBR=reed@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/266063003 git-svn-id: http://skia.googlecode.com/svn/trunk@14614 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
* Mike R: please sanity check SkPostConfig.hGravatar commit-bot@chromium.org2014-04-14
Mike K: please sanity check Test.cpp and skia_test.cpp Feel free to look at the rest, but I don't expect any in depth review of path ops innards. Path Ops first iteration used QuickSort to order segments radiating from an intersection to compute the winding rule. This revision uses a circular sort instead. Breaking out the circular sort into its own long-lived structure (SkOpAngle) allows doing less work and provides a home for caching additional sorting data. The circle sort is more stable than the former sort, has a robust ordering and fewer exceptions. It finds unsortable ordering less often. It is less reliant on the initial curve tangent, using convex hulls instead whenever it can. Additional debug validation makes sure that the computed structures are self-consistent. A new visualization tool helps verify that the angle ordering is correct. The 70+M tests pass with this change on Windows, Mac, Linux 32 and Linux 64 in debug and release. R=mtklein@google.com, reed@google.com Author: caryclark@google.com Review URL: https://codereview.chromium.org/131103009 git-svn-id: http://skia.googlecode.com/svn/trunk@14183 2bbb7eff-a529-9590-31e7-b0007b416f81
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-16 20:16:44 +0000