aboutsummaryrefslogtreecommitdiffhomepage
path: root/tests/PathOpsCubicIntersectionTest.cpp
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 trailing whitespace.Gravatar Ben Wagner2017-10-09
| | | | | | | | | | | Also adds a presubmit to prevent adding trailing whitespace to source code in the future. Change-Id: I41a4df81487f6f00aa19b188f0cac6a3377efde6 Reviewed-on: https://skia-review.googlesource.com/57380 Reviewed-by: Ravi Mistry <rmistry@google.com> Reviewed-by: Mike Reed <reed@google.com> Commit-Queue: Ben Wagner <bungeman@google.com>
* Improve cubic KLM accuracyGravatar Chris Dalton2017-06-09
| | | | | | | | | | | | | | | | | | | | | | Moves cubic root finding logic out of GrPathUtils and PathOpsCubicIntersectionTest, and unifies it in SkGeometry. "Normalizes" the homogeneous parameter values of the roots, rather than the cubic inflection function. Does this normalization by twiddling the exponents instead of division (which causes a loss of precision). Abandons the built-in derivatives in GrCubicEffect. These don't have high enough precision on many mobile gpus. Instead we pass the KLM matrix to the vertex shader via uniform, where we can use it to set up new linear functionals from which the fragment shader can calculate the gradient of the implicit function. Bug: skia:4410 Change-Id: Ibd64e999520adc8cdef7803a492d3699995aef5a Reviewed-on: https://skia-review.googlesource.com/19017 Reviewed-by: Greg Daniel <egdaniel@google.com> Commit-Queue: Chris Dalton <csmartdalton@google.com>
* Improve accuracy of cubic classificationGravatar Chris Dalton2017-04-14
| | | | | | | | | | | | | | | | | | - Updates the logic to reflect the Loop-Blinn paper instead of the GPU gems website. - Removes the threshold for detecting local cusps. The serpentine codepath works for these cusps anyway, so what we really want to know is whether the discriminant is negative. - Makes sure to not scale the inflection function by 1/0. - Shifts the inflection function coefficients in d[] so they match the paper. - Stores the cubic discriminant in d[0]. Bug: skia: Change-Id: I909a522a0fd27c9c8dfbc27d968bc43eeb7a416f Reviewed-on: https://skia-review.googlesource.com/13304 Reviewed-by: Greg Daniel <egdaniel@google.com> Commit-Queue: Chris Dalton <csmartdalton@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>
* 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 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
* 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
* remove unused fields from SkOpSegmentGravatar caryclark2015-09-04
| | | | | | TBR=reed@google.com Review URL: https://codereview.chromium.org/1322413002
* Remove include of stdlib.h from SkTypes.h.Gravatar bungeman2015-08-26
| | | | | | | | | | | | | | | Unfortunately, immintrin.h (which is also included by SkTypes) includes xmmintrin.h which includes mm_malloc.h which includes stdlib.h for malloc even though, from the implementation, it is difficult to see why. Fortunately, arm_neon.h does not seem to be involved in such shenanigans, so building for Android will keep things sane. TBR=reed@google.com Doesn't change Skia API, just moves an include. Review URL: https://codereview.chromium.org/1313203003
* 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
* 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
* Revert of remove obsolete tests (patchset #1 id:1 of ↵Gravatar caryclark2015-03-24
| | | | | | | | | | | | | | | | | | | | | | | https://codereview.chromium.org/1030883002/) Reason for revert: working on asan fix Original issue's description: > remove obsolete tests > > remove tests that are breaking the build -- uninitialized memory > > TBR=reed > > Committed: https://skia.googlesource.com/skia/+/e02c944e97ad6a3b8befb1f4f784919767941ba6 TBR=reed@android.com NOPRESUBMIT=true NOTREECHECKS=true NOTRY=true Review URL: https://codereview.chromium.org/1036633002
* remove obsolete testsGravatar caryclark2015-03-24
| | | | | | | | remove tests that are breaking the build -- uninitialized memory TBR=reed Review URL: https://codereview.chromium.org/1030883002
* 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
* 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
* 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
* Move macros from TestClassDef.h to Test.hGravatar commit-bot@chromium.org2014-01-14
| | | | | | | | | | | | | | Motivation: those macros don't make any sense without the definitions in Test.h. BUG= R=mtklein@google.com Author: halcanary@google.com Review URL: https://codereview.chromium.org/138563004 git-svn-id: http://skia.googlecode.com/svn/trunk@13074 2bbb7eff-a529-9590-31e7-b0007b416f81
* Get rid of DEFINE_TESTCLASS_SHORT() macro.Gravatar tfarina@chromium.org2014-01-02
| | | | | | | | | | | | | Instead tests should be written using DEF_TEST() macro, which is much nicer and simplifies the process of setting up an unit test. BUG=None TEST=skpskgr_test, pathops_unittest R=mtklein@google.com Review URL: https://codereview.chromium.org/117863005 git-svn-id: http://skia.googlecode.com/svn/trunk@12870 2bbb7eff-a529-9590-31e7-b0007b416f81
* remove unused reduce order codeGravatar caryclark@google.com2013-11-25
| | | | | | | | BUG= Review URL: https://codereview.chromium.org/85763002 git-svn-id: http://skia.googlecode.com/svn/trunk@12377 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
* Sanitizing source files in Housekeeper-NightlyGravatar skia.committer@gmail.com2013-10-03
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@11585 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-10-02
| | | | | | | | | | | | make more skps work remove edit files BUG= Review URL: https://codereview.chromium.org/23542056 git-svn-id: http://skia.googlecode.com/svn/trunk@11570 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-24
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@10299 2bbb7eff-a529-9590-31e7-b0007b416f81
* turn off debugging printfsGravatar caryclark@google.com2013-07-23
| | | | | | | | | | | | | fix pathops issues 1417, 1418 be more rigorous about pulling intersections of lines to end points rewrite cubic/line and quad/line intersections to share style BUG= Review URL: https://codereview.chromium.org/19543005 git-svn-id: http://skia.googlecode.com/svn/trunk@10270 2bbb7eff-a529-9590-31e7-b0007b416f81
* harden and speed up path op unit testsGravatar caryclark@google.com2013-07-16
| | | | | | | | | | | | | | | | | | | PathOps tests internal routines direcctly. Check to make sure that test points, lines, quads, curves, triangles, and bounds read from arrays are valid (i.e., don't contain NaN) before calling the test function. Repurpose the test flags. - make 'v' verbose test region output against path output - make 'z' single threaded (before it made it multithreaded) The latter change speeds up tests run by the buildbot by 2x to 3x. BUG= Review URL: https://codereview.chromium.org/19374003 git-svn-id: http://skia.googlecode.com/svn/trunk@10107 2bbb7eff-a529-9590-31e7-b0007b416f81
* call newOneOff instead of oneOffGravatar caryclark@google.com2013-07-15
| | | | | | | | | | | | | calling the latter instead of the former walked off the end of the array causing mysterious bugs TODO: safeguard against NaNs in the input BUG= Review URL: https://codereview.chromium.org/19280002 git-svn-id: http://skia.googlecode.com/svn/trunk@10093 2bbb7eff-a529-9590-31e7-b0007b416f81
* Fix compiler warning/error in r10079Gravatar robertphillips@google.com2013-07-15
| | | | git-svn-id: http://skia.googlecode.com/svn/trunk@10081 2bbb7eff-a529-9590-31e7-b0007b416f81
* add florin testsGravatar caryclark@google.com2013-07-15
| | | | | | | | | | hopefully fix build BUG= Review URL: https://codereview.chromium.org/19183005 git-svn-id: http://skia.googlecode.com/svn/trunk@10079 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops near exactGravatar caryclark@google.com2013-07-15
| | | | | | | | | | | | | | | | | Modify line intersections to first - match exact ends - compute intersections - match near ends where the exact ends are preferred, then near matches, then computed matches. This pulls matches towards existing end points when possible, and keeps intersection distances consistent with different line/line line/quad and line/cubic computations. BUG= Review URL: https://codereview.chromium.org/19183003 git-svn-id: http://skia.googlecode.com/svn/trunk@10073 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
* path ops -- rewrite angle sortGravatar caryclark@google.com2013-06-04
| | | | | | | | | | | | | | | | | | | | | | | | This is a major change resulting from a minor tweak. In the old code, the intersection point of two curves was shared between them, but the intersection points and end points of sorted edges was computed directly from the intersection T value. In this CL, both intersection points and sorted points are the same, and intermediate control points are computed to preserve their slope. The sort itself has been completely rewritten to be more robust and remove 'magic' checks, conditions that empirically worked but couldn't be rationalized. This CL was triggered by errors generated computing the clips of SKP files. At this point, all 73M standard tests work and at least the first troublesome SKPs work. Review URL: https://codereview.chromium.org/15338003 git-svn-id: http://skia.googlecode.com/svn/trunk@9432 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops -- fix skp bugsGravatar caryclark@google.com2013-05-07
| | | | | | | | | This fixes a series of bugs discovered by running the small set of Skia skp files through pathops to flatten the clips. Review URL: https://codereview.chromium.org/14798004 git-svn-id: http://skia.googlecode.com/svn/trunk@9042 2bbb7eff-a529-9590-31e7-b0007b416f81
* shape ops work in progressGravatar caryclark@google.com2013-04-17
| | | | | | | | | | | | | Try to fix the 32 bit build by making some math decisions more robust. Rewrite the cubic intersection special case that detects if only end points are shared. Rewrite the angle sort setup that computes whether a cubic bends to the left or right. git-svn-id: http://skia.googlecode.com/svn/trunk@8726 2bbb7eff-a529-9590-31e7-b0007b416f81
* path ops work in progressGravatar caryclark@google.com2013-04-15
| | | | | | | | | standardize tests use SK_ARRAY_COUNT everywhere debug why x87 differs from SIMD 64 various platform specific fixes git-svn-id: http://skia.googlecode.com/svn/trunk@8689 2bbb7eff-a529-9590-31e7-b0007b416f81
* shape ops test fixesGravatar caryclark@google.com2013-04-11
| | | | | | | | | - fix rand for Android - build unit test on linux - use atomic inc in test count - add casting for Android git-svn-id: http://skia.googlecode.com/svn/trunk@8610 2bbb7eff-a529-9590-31e7-b0007b416f81
* Add intersections for path opsGravatar caryclark@google.com2013-04-08
This CL depends on https://codereview.chromium.org/12827020/ "Add base types for path ops" The intersection of a line, quadratic, or cubic with another curve (or with itself) is found by solving the implicit equation for the curve pair. The curves are first reduced to find the simplest form that will describe the original, and to detect degenerate or special-case data like horizontal and vertical lines. For cubic self-intersection, and for a pair of cubics, the intersection is found by recursively approximating the cubic with a series of quadratics. The implicit solutions depend on the root finding contained in the DCubic and DQuad structs, and the quartic root finder included here. Review URL: https://codereview.chromium.org/12880016 git-svn-id: http://skia.googlecode.com/svn/trunk@8552 2bbb7eff-a529-9590-31e7-b0007b416f81
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-19 19:34:06 +0000