1276068 - The path flattening code is incorrectly computing its flatness estimation

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Nicolas Silva [:nical]]

Attachment: On the left the current flattening behavior, on the right the adjusted behavior

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.

Comment 1

[Nicolas Silva [:nical]]

(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.

Comment 2

[Nicolas Silva [:nical]]

> 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.

Comment 3

[Bas Schouten (:bas.schouten)]

(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 :).

Comment 4

[Nicolas Silva [:nical]]

Attachment: Fix the flatness estimation

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e33ed35dc9d9
Correct the path flatness estimation computation. r=Bas

Comment 6

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e33ed35dc9d9