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)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla49
Tracking Status
firefox49 --- fixed

People

(Reporter: nical, Assigned: nical)

Details

Attachments

(2 files)

Here: https://dxr.mozilla.org/mozilla-central/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 over-estimates  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 over-tesselate our path, produces correct but less time and memory efficient results.
Assignee: nobody → nical.bugzilla
(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.
> 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)
(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)
Attachment #8757894 - Flags: review?(bas)
Attachment #8757894 - Flags: review?(bas) → review+
Pushed by nsilva@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e33ed35dc9d9
Correct the path flatness estimation computation. r=Bas
https://hg.mozilla.org/mozilla-central/rev/e33ed35dc9d9
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla49
You need to log in before you can comment on or make changes to this bug.