Closed
Bug 1276068
Opened 3 years ago
Closed 3 years ago
The path flattening code is incorrectly computing its flatness estimation
Categories
(Core :: Graphics, defect)
Core
Graphics
Not set
Tracking
()
RESOLVED
FIXED
mozilla49
Tracking  Status  

firefox49    fixed 
People
(Reporter: nical, Assigned: nical)
Details
Attachments
(2 files)
121.59 KB,
image/png

Details  
1.13 KB,
patch

bas.schouten
:
review+

Details  Diff  Splinter Review 
Here: https://dxr.mozilla.org/mozillacentral/rev/8d0aadfe7da782d415363880008b4ca027686137/gfx/2d/Path.cpp#263 The Paper that this code is based on is here: http://cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf A comment says: > // The basic premise is that for a small t the third order term in the > // equation of a cubic bezier curve is insignificantly small. This can > // then be approximated by a quadratic equation for which the maximum > // difference from a linear approximation can be much more easily determined. and then we start computating things based on the control points mP1, mP2, mP3, but not mP4. > PointD cp21 = currentCP.mCP2  currentCP.mCP3; > PointD cp31 = currentCP.mCP3  currentCP.mCP1; I was trying to wrap my head around that because if I was to approximate a cubic bezier equation with a quadratic one by picking 3 of the 4 bezier points i'd certainly pick the two anchors and one of the control points (or probably an average of the two control points although I assume what the paper says is that the it doesn't make a big difference, I am still in the process of digesting the maths involved). Each window in the attached image contains the paths > move_to(vec2(20.0, 20.0) > cubic_bezier_to(vec2(100.0, 20.0), vec2(100.0, 30.0), vec2(20.0, 30.0)) > end(); > move_to(vec2(20.0, 80.0)) > cubic_bezier_to(vec2(100.0, 80.0), vec2(100.0, 70.0), vec2(20.0, 70.0)) > end(); On the left you can see the current behavior, which overestimates the flatness towards the beginning of the paths, on the left we see the behavior we would get if the approximation was not leaving out the last anchor, which definitely looks better. So I think that we are wrongly doing our second order approximation here, and that luckily this means we just overtesselate our path, produces correct but less time and memory efficient results.
Assignee  
Updated•3 years ago

Assignee: nobody → nical.bugzilla
Assignee  
Comment 1•3 years ago


(In reply to Nicolas Silva [:nical] from comment #0) > I was trying to wrap my head around that because if I was to approximate a > cubic bezier equation with a quadratic one by picking 3 of the 4 bezier > points i'd certainly pick the two anchors and one of the control points Obviously that hunch is completely off when it comes to the actual maths involved, but still I can't connect the weird cross product that we do with our 3 points to the actual math in the paper.
Assignee  
Comment 2•3 years ago


> PointD cp21 = currentCP.mCP2  currentCP.mCP3; > PointD cp31 = currentCP.mCP3  currentCP.mCP1; Bas, looks like this corresponds to the translation that the paper makes to put the first point of the curve at the origin. If that's so then we should be doing instead: > PointD cp21 = currentCP.mCP2  currentCP.mCP1; > PointD cp31 = currentCP.mCP3  currentCP.mCP1; And that kinda lines up with the naming which isn't meaningful in itself but it does look like a hint :). With this modification I get a much nicer tesselation.
Flags: needinfo?(bas)
Comment 3•3 years ago


(In reply to Nicolas Silva [:nical] from comment #2) > > PointD cp21 = currentCP.mCP2  currentCP.mCP3; > > PointD cp31 = currentCP.mCP3  currentCP.mCP1; > > Bas, looks like this corresponds to the translation that the paper makes to > put the first point of the curve at the origin. If that's so then we should > be doing instead: > > > PointD cp21 = currentCP.mCP2  currentCP.mCP1; > > PointD cp31 = currentCP.mCP3  currentCP.mCP1; > > And that kinda lines up with the naming which isn't meaningful in itself but > it does look like a hint :). > > With this modification I get a much nicer tesselation. I understand the cross product and you're right, it's a bug :).
Flags: needinfo?(bas)
Assignee  
Comment 4•3 years ago


Attachment #8757894 
Flags: review?(bas)
Updated•3 years ago

Attachment #8757894 
Flags: review?(bas) → review+
Pushed by nsilva@mozilla.com: https://hg.mozilla.org/integration/mozillainbound/rev/e33ed35dc9d9 Correct the path flatness estimation computation. r=Bas
Comment 6•3 years ago


bugherder 
https://hg.mozilla.org/mozillacentral/rev/e33ed35dc9d9
Status: NEW → RESOLVED
Closed: 3 years ago
statusfirefox49:
 → fixed
Resolution:  → FIXED
Target Milestone:  → mozilla49
You need to log in
before you can comment on or make changes to this bug.
Description
•