Comments (12)
@mbutterick I was able to reproduce this issue! As you reported, the result is falsely empty. I'm not sure why yet, but I'm saving this test data for later.
let firstCurves: [BezierCurve] = [BezierKit.CubicCurve(p0: CGPoint(x: 28.0, y: 14.0),
p1: CGPoint(x: 32.0, y: 21.0),
p2: CGPoint(x: 33.0, y: 42.0),
p3: CGPoint(x: 30.0, y: 53.0)),
BezierKit.CubicCurve(p0: CGPoint(x: 30.0, y: 53.0),
p1: CGPoint(x: 19.0, y: 32.0),
p2: CGPoint(x: 22.0, y: 26.0),
p3: CGPoint(x: 28.0, y: 14.0))]
let secondCurves: [BezierCurve] = [BezierKit.CubicCurve(p0: CGPoint(x: 42.0, y: 38.0),
p1: CGPoint(x: 42.0, y: 53.0),
p2: CGPoint(x: 36.0, y: 53.0),
p3: CGPoint(x: 27.0, y: 53.0)),
BezierKit.CubicCurve(p0: CGPoint(x: 27.0, y: 53.0),
p1: CGPoint(x: 19.0, y: 40.0),
p2: CGPoint(x: 29.0, y: 32.0),
p3: CGPoint(x: 42.0, y: 38.0))]
let component1 = PathComponent(curves: firstCurves)
let component2 = PathComponent(curves: secondCurves)
let path = Path(components: [component1, component2])
let result = path.crossingsRemoved()
XCTAssertFalse(result.isEmpty)
from bezierkit.
My credibility is restored đ
from bezierkit.
Haha, well you're pretty credible in my book. The issues you open always have the exact data needed to reproduce which makes them pretty stellar.
from bezierkit.
delving into this a bit (and please pardon my stream of consciousness):
The top intersection shown in this diagram is actually two separate nearby intersections, one at (30.01, 52.98) and the other at (29.99, 52.98). If we look at the first contour (the long skinny one), the first nearby intersection falls on its first curve at t = 0.99929, and the second nearby intersection falls on its second curve at t = 0.00036. If we look at the second contour, the first nearby intersection falls on its first curve at t = 0.88399, and the second nearby intersection falls on the same curve at t = 0.88474. These intersections are actually being computed accurately, and oddly do not appear to be the cause of the failure.
Next in AugmentedGraph we classify the edges, and appear to do so correctly for the first contour (we even classify the tiny edge of the contour between the two nearby intersections correctly). The problem is with when we go to classify the second contour. When we classify the edge from the first curve at t = 0.884 to the second curve at t = 0.364 we falsely conclude that this edge should be excluded from the solution.
from bezierkit.
It looks like if we do component2.contains(CGPoint(x: 28.52584147560618, y: 52.99912729740088))
we are getting the wrong answer. I think this is the root of the problem. contains
says the point is contained but in fact the point should have a y value greater than the curve 52.997
making it fall outside the contour.
from bezierkit.
@mbutterick in Util.swift could you try changing the line 190 to if discriminant < -1.0e-14 {
and line 207 to if discriminant > 1.0e-14 {
and report results?
I think this should do the trick.
from bezierkit.
Before the patch, here are the glyphs that fail:
glyph X in [AFFont: Advocate Slab C45 Regular, 706 glyphs] did not have overlap removed successfully
glyph y in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph k in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph y.mid in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph y in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph K in [AFFont: Advocate Slab C63 Regular, 775 glyphs] did not have overlap removed successfully
glyph k.alt in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph y.mid in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph k.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph k.alt.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
After the patch:
glyph iogonek.mid in [AFFont: Advocate Slab C43 Regular, 775 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C45 Regular, 706 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C55 Regular, 706 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C63 Regular, 775 glyphs] did not have overlap removed successfully
So the patch is apparently fixing one bug & introducing another (because the two sets of problem glyphs have nothing in common).
The interesting common feature of the first set of glyphs is that they all have diagonal parts â curious why that would consistently trigger a bug.
The interesting feature of the second set is that it's the same glyph in different styles. The iogonek.mid
is shown below. I will have to experiment some more to see which points in the glyph are causing the problem (though based on the results, I suspect itâs where the ogonek accent is intersecting the bottom).
Hereâs a fragment of the glyph that still manifests the problem:
And the debug report for that fragment:
path.components.map { $0.curves } =
[[BezierKit.CubicCurve(p0: (96.0, 75.0), p1: (96.0, 71.0), p2: (97.0, 70.0), p3: (101.0, 70.0)), BezierKit.LineSegment(p0: (101.0, 70.0), p1: (187.0, 70.0)), BezierKit.CubicCurve(p0: (187.0, 70.0), p1: (192.0, 70.0), p2: (194.0, 71.0), p3: (194.0, 77.0)), BezierKit.CubicCurve(p0: (194.0, 77.0), p1: (194.0, 578.0), p2: (96.0, 578.0), p3: (96.0, 75.0))], [BezierKit.CubicCurve(p0: (61.0, 85.0), p1: (61.0, 70.0), p2: (61.0, 70.0), p3: (76.0, 70.0)), BezierKit.LineSegment(p0: (76.0, 70.0), p1: (214.0, 70.0)), BezierKit.CubicCurve(p0: (214.0, 70.0), p1: (229.0, 70.0), p2: (229.0, 70.0), p3: (229.0, 85.0)), BezierKit.CubicCurve(p0: (229.0, 85.0), p1: (229.0, 158.0), p2: (61.0, 158.0), p3: (61.0, 85.0))], [BezierKit.LineSegment(p0: (216.0, 103.0), p1: (182.0, 118.0)), BezierKit.CubicCurve(p0: (182.0, 118.0), p1: (123.0, 90.0), p2: (144.0, -45.0), p3: (144.0, -19.0)), BezierKit.CubicCurve(p0: (144.0, -19.0), p1: (144.0, 26.0), p2: (170.0, 64.0), p3: (216.0, 97.0)), BezierKit.LineSegment(p0: (216.0, 97.0), p1: (216.0, 103.0))]]
path.crossingsRemoved().components.map { $0.curves } =
[]
In this case, I notice that as with the previous cases, it has a little âpointâ sticking below a horizontal line. (Maybe your patch corrects the âpointing upâ case but breaks the âpointing downâ case?)
from bezierkit.
@mbutterick this is extremely helpful feedback. Before I had you set the value to 1.0e-14
it was effectively set at 1.0e-8
. Perhaps I am being too aggressive with my change. I noticed that to fix the first path specifically I only need to set it as low as 1.0e-10
, which is 10,000x larger than 1.0e-14
. We might try 1.0e-10
, 1.0e-11
, 1.0e-12
or 1.0e-13
here instead. Any of these values might have some chance of working without causing regressions.
For some reason I can't reproduce the issue you are having using the fragment you sent me. Here is my code:
let curves1: [BezierCurve] = [CubicCurve(p0: CGPoint(x: 96.0, y: 75.0),
p1: CGPoint(x: 96.0, y: 71.0),
p2: CGPoint(x: 97.0, y: 70.0),
p3: CGPoint(x: 101.0, y: 70.0)),
LineSegment(p0: CGPoint(x: 101.0, y: 70.0),
p1: CGPoint(x: 187.0, y: 70.0)),
CubicCurve(p0: CGPoint(x: 187.0, y: 70.0),
p1: CGPoint(x: 192.0, y: 70.0),
p2: CGPoint(x: 194.0, y: 71.0),
p3: CGPoint(x: 194.0, y: 77.0)),
CubicCurve(p0: CGPoint(x: 194.0, y: 77.0),
p1: CGPoint(x: 194.0, y: 578.0),
p2: CGPoint(x: 96.0, y: 578.0),
p3: CGPoint(x: 96.0, y: 75.0))]
let component1 = PathComponent(curves: curves1)
let curves2: [BezierCurve] = [CubicCurve(p0: CGPoint(x: 61.0, y: 85.0),
p1: CGPoint(x: 61.0, y: 70.0),
p2: CGPoint(x: 61.0, y: 70.0),
p3: CGPoint(x: 76.0, y: 70.0)),
BezierKit.LineSegment(p0: CGPoint(x: 76.0, y: 70.0),
p1: CGPoint(x: 214.0, y: 70.0)),
BezierKit.CubicCurve(p0: CGPoint(x: 214.0, y: 70.0),
p1: CGPoint(x: 229.0, y: 70.0),
p2: CGPoint(x: 229.0, y: 70.0),
p3: CGPoint(x: 229.0, y: 85.0)),
BezierKit.CubicCurve(p0: CGPoint(x: 229.0, y: 85.0),
p1: CGPoint(x: 229.0, y: 158.0),
p2: CGPoint(x: 61.0, y: 158.0),
p3: CGPoint(x: 61.0, y: 85.0))]
let component2 = PathComponent(curves: curves2)
let curves3: [BezierCurve] = [LineSegment(p0: CGPoint(x: 216.0, y: 103.0),
p1: CGPoint(x: 182.0, y: 118.0)),
CubicCurve(p0: CGPoint(x: 182.0, y: 118.0),
p1: CGPoint(x: 123.0, y: 90.0),
p2: CGPoint(x: 144.0, y: -45.0),
p3: CGPoint(x: 144.0, y: -19.0)),
CubicCurve(p0: CGPoint(x: 144.0, y: -19.0),
p1: CGPoint(x: 144.0, y: 26.0),
p2: CGPoint(x: 170.0, y: 64.0),
p3: CGPoint(x: 216.0, y: 97.0)),
LineSegment(p0: CGPoint(x: 216.0, y: 97.0),
p1: CGPoint(x: 216.0, y: 103.0))]
let component3 = PathComponent(curves: curves3)
let path = Path(components: [component1, component2, component3])
XCTAssertNotEqual(path.crossingsRemoved(), Path())
Here's the results of crossingsRemoved ... I think iit looks correct (pardon the fact it's flipped vertically).
from bezierkit.
Whoops, I made a mistake typing your patch â I didnât notice that the second number is positive. That explains where the ânew bugâ came from ⊠đ€Š
The revised results:
-
If I type your patch correctly (setting line 190 to
-1.0e-14
and 207 to1.0e-14
), then all the errors are cleared. -
If I adjust the constants to
±1.0e-12
, I still get an error on one of the K glyphs. -
If I adjust the constants to
±1.0e-13
, then the errors are still cleared.
from bezierkit.
@mbutterick wohoo! It sounds like either 1.0e-13 or 1.0e-14 could work. I'll use 1.0e-14 for now.
from bezierkit.
@mbutterick I've added a unit test using your data and merged the fix into the branch 0.9-release
. I'm closing the issue now.
from bezierkit.
Thank you!
from bezierkit.
Related Issues (20)
- boundingBox vs boundingBoxOfPath follows opposite convention as CoreGraphics
- Hard to work with ends of simple, unclosed bezier path HOT 2
- Path and PathComponent hash and hashValue is simply memory address HOT 1
- Unknown references to BezierKit.min(...) and BezierKit.max(...) HOT 3
- Path.offset(distance:) hits assertion failure when called on a Path where all points are equal HOT 1
- Union of 2 overlapping paths returns an empty path HOT 4
- `union` with nonzero winding rule HOT 9
- Path.crossingRemoved() produces wrong result HOT 11
- simplifying a curve? HOT 2
- `offset` seems to treat straight & curved segments differently HOT 3
- feature request: permit separate x and y inputs for scale, outline, reduce HOT 8
- this contour crashes `crossingsRemoved` HOT 9
- how to quiet the SwiftLint warning? HOT 2
- `crossingsRemoved` gets confused by coincident points HOT 3
- droots can have low precision in some cases, which could affect Path.contains(_ point:)
- Newton iteration may fail to converge, producing wrong results in curve.project()
- `offset` fatalError when all control points of segments are the same HOT 3
- Impossible to make closed PathComponent HOT 19
- Proposal: Use Sylvester Matrix for finding the intersection of cubic beziers HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
đ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. đđđ
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google â€ïž Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bezierkit.