1474284 - SVG path interpolation broken for certain bezier curves

Status: RESOLVED FIXED

(Core :: Graphics, defect, P3)

Description

[Paul LeBeau]

User Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:61.0) Gecko/20100101 Firefox/61.0
Build ID: 20180621125625

Steps to reproduce:

Try the following animateMotion test:

<svg width="500" height="500" viewBox="0 0 112 112">
  <path id="path1" fill="none" stroke="#000"
        d="M 40.500,32.500
           C 40.500,32.500 24.500,32.500 24.500,16.500"/>
  <circle cx="0" cy="0" r="2" fill="rgba(224,0,0,0.5)">
    <animateMotion dur="2s" repeatCount="indefinite" rotate="auto" >
      <mpath xlink:href="#path1"/>
    </animateMotion>
  </circle>
</svg>

See fiddle: https://jsfiddle.net/29avn0t7/9/

The animated circle is not following the curve as it is supposed to.

It appears that path interpolation has a bug for this particular bezier (which was extracted from a longer original path).  This can also be seen in the following test of getPointAtLength():

<svg width="500" height="500" viewBox="0 0 112 112">
  <path id="path1" fill="none" stroke="#000"
        d="M 40.500,32.500
           C 40.500,32.500 24.500,32.500 24.500,16.500"/>
  <circle cx="0" cy="0" r="2" fill="rgba(224,0,0,0.5)">
    <animateMotion dur="2s" repeatCount="indefinite" rotate="auto" >
      <mpath xlink:href="#path1"/>
    </animateMotion>
  </circle>
</svg>

var path = document.getElementById("path1");
var len = path.getTotalLength();
var halfway = path.getPointAtLength(len/2);

var circle = document.createElementNS(path.namespaceURI, "circle");
circle.cx.baseVal.value = halfway.x;
circle.cy.baseVal.value = halfway.y;
circle.r.baseVal.value = 1;
path.parentElement.appendChild(circle);

See fiddle: https://jsfiddle.net/29avn0t7/14/




Actual results:

Small circle leaves the curve and instead moves linearly from the start to the end.


Expected results:

Circle should follow path as rendered.

Comment 1

[Robert Longson [:longsonr]]

 a build from 2011-01-01 works. Having trouble finding a regression window though.

Comment 2

[Daniel Holbert [:dholbert]]

Attachment: testcase 1 (from reporter's jsfiddle)

2011-era Firefox builds don't seem to like jsfiddle, so here's a standalone testcase that works even in old builds.

Comment 3

[Daniel Holbert [:dholbert]]

Tracking down a regression range.

The testcase goes from animating to not-animating-at-all with this regression range:
 https://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=a475f94bb1b1&tochange=f2adb62d07eb
(likely from "Bug 937994 - Make the SMIL animateMotion code use a Moz2D PathBuilder instead of gfxContext.")

Now tracking down when it started animating (incorrectly) after that...

Comment 4

[Daniel Holbert [:dholbert]]

The second behavior-change (from not-animating-at-all to animating-incorrectly-straight-across) happened in this range:
  https://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=57e4e9c33bef&tochange=55f3224d7513

My guess is that that's from:
https://hg.mozilla.org/mozilla-central/rev/b9458d466161
Bug 1068603: Extend FlattenBezier to handle case where full path can be approximated by a linear segment.

Comment 5

[Daniel Holbert [:dholbert]]

So, bottom line, it seems Moz2D's "FlattenBezier" function is having trouble flattening this Bezier curve accurately.

We're hitting a case that was initially unhandled in Moz2D (hence the first breakage, comment 3) and now is handled using a straight line (hence the only partial restoration of functionality, comment 4).

I took a quick look at the "one line segment" clause in gdb:
>  // Process ranges. [t1min, t1max] and [t2min, t2max] are approximated by line
>  // segments.
>  if (count == 1 && t1min <= 0 && t1max >= 1.0) {
>    // The whole range can be approximated by a line segment.
>    aSink->LineTo(aControlPoints.mCP4.ToPoint());
>    return;
>  }

When we get here, we have count = 1, t1 = 0, t1min = -inf and t1max = +inf.

I'm not sure what that means, but it seems maybe pathological/unexpected.

I think the infinity values come from this expression in FindInflectionApproximationRange:
>      // Use the absolute value so that Min and Max will correspond with the
>      // minimum and maximum of the range.
>      *aMin = aT - CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
>      *aMax = aT + CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));

Here, we're dividing by 0., because cp41.x and .y are the same value (they happen to both be -16), which means (cp41.x - cp41.y) is 0.  So we're doing aT - CubicRoot(inf) and aT + CubicRoot(inf), basically, which is -inf and +inf.


Bas, it looks like you added this subtraction in bug 941585 ( https://hg.mozilla.org/mozilla-central/rev/22c11c35d1a3#l1.43 ) -- do you know what it means when .x and .y are the same here, and is there a way we can handle it better? (Divide-by-0 seems clearly undesirable, particularly given that it produces incorrect results.)

Comment 6

[Daniel Holbert [:dholbert]]

DXR links for comment 5's source code quotes:

https://searchfox.org/mozilla-central/rev/a80651653faa78fa4dfbd238d099c2aad1cec304/gfx/2d/Path.cpp#487-492
https://searchfox.org/mozilla-central/rev/a80651653faa78fa4dfbd238d099c2aad1cec304/gfx/2d/Path.cpp#299-314

Comment 7

[Bas Schouten (:bas.schouten)]

(In reply to Daniel Holbert [:dholbert] from comment #5)
> So, bottom line, it seems Moz2D's "FlattenBezier" function is having trouble
> flattening this Bezier curve accurately.
> 
> We're hitting a case that was initially unhandled in Moz2D (hence the first
> breakage, comment 3) and now is handled using a straight line (hence the
> only partial restoration of functionality, comment 4).
> 
> I took a quick look at the "one line segment" clause in gdb:
> >  // Process ranges. [t1min, t1max] and [t2min, t2max] are approximated by line
> >  // segments.
> >  if (count == 1 && t1min <= 0 && t1max >= 1.0) {
> >    // The whole range can be approximated by a line segment.
> >    aSink->LineTo(aControlPoints.mCP4.ToPoint());
> >    return;
> >  }
> 
> When we get here, we have count = 1, t1 = 0, t1min = -inf and t1max = +inf.
> 
> I'm not sure what that means, but it seems maybe pathological/unexpected.
> 
> I think the infinity values come from this expression in
> FindInflectionApproximationRange:
> >      // Use the absolute value so that Min and Max will correspond with the
> >      // minimum and maximum of the range.
> >      *aMin = aT - CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
> >      *aMax = aT + CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
> 
> Here, we're dividing by 0., because cp41.x and .y are the same value (they
> happen to both be -16), which means (cp41.x - cp41.y) is 0.  So we're doing
> aT - CubicRoot(inf) and aT + CubicRoot(inf), basically, which is -inf and
> +inf.
> 
> 
> Bas, it looks like you added this subtraction in bug 941585 (
> https://hg.mozilla.org/mozilla-central/rev/22c11c35d1a3#l1.43 ) -- do you
> know what it means when .x and .y are the same here, and is there a way we
> can handle it better? (Divide-by-0 seems clearly undesirable, particularly
> given that it produces incorrect results.)

Yes, this means that s3 == 0. Note the limit being solved is lim[n->0] (cp41.x * n) / n - (cp41.y * n) / n = cp41.x - cp41.y in order to find s3. Essentially '-inf' and '+inf' are correct here, we just need to make them into something sensible code-wise. Further down in the function is a codepath to deal with the s3 == 0 situation, we're simply missing this codepath when we're in this branch. Adding it there should be trivial, let me know if you can do it or whether you want me to do it.

Comment 8

[Daniel Holbert [:dholbert]]

Attachment: WIP patch based on comment 7 (& which unfortunately doesn't help)

(In reply to Bas Schouten (:bas.schouten) from comment #7)
> Yes, this means that s3 == 0.  [...] Further down in the function is a
> codepath to deal with the s3 == 0 situation, we're simply missing this
> codepath when we're in this branch. Adding it there should be trivial, let
> me know if you can do it or whether you want me to do it.

I took a crack at it, but wasn't successful.  I spun up a trivial patch to do what I think you suggested (checking for cp41.x == cp41.y and duplicating our "s3==0" return logic stuff if so), but it doesn't change our behavior here.  See attached (non-helping) patch.

(I verified in a debugger that we *are* hitting this patch's newly-added return statement, too.)

Perhaps it makes sense that it doesn't change our behavior, because the s3==0 scenario is trying to use a straight line approximation, and this bug happens to be a case where we're incorrectly animating in a straight line.

Bas, would you mind taking a crack at this?

Comment 9

[Daniel Holbert [:dholbert]]

Attachment: testcase 2 (with simpler numbers & more extreme curve in path command)

I simplified the numbers a bit to be rounder & to make the curve more extreme.

This testcase has this path "d" command:
          M 50,40
          C 50,40 0,60 30,20
...which we are apparently unable to flatten.

Comment 10

[Daniel Holbert [:dholbert]]

BTW if I call the JS getTotalLength() function (which uses the same flattening code) on the path in testcase 2...

 - Firefox gives me ~28px (following the same shorter/straight path)
 - Chrome gives me ~55px

Comment 11

[Paul LeBeau]

Sorry for sticking my nose into code I probably don't understand well :)
but...

The root problem with these two beziers is that CP1 and CP2 are co-incident.  If you check for this and
instead use CP3 in that test, does it result in better behaviour?
I.e.:

    Point cp21 = aControlPoints.mCP2 - aControlPoints.mCP1;
    Point cp41 = aControlPoints.mCP4 - aControlPoints.mCP1;

+   if (cp21.x == 0.f && cp21.y == 0.f) {
+     Point cp21 = aControlPoints.mCP3 - aControlPoints.mCP1;
+   }

    if (cp21.x == 0.f && cp21.y == 0.f) {
      // In this case s3 becomes lim[n->0] (cp41.x * n) / n - (cp41.y * n) / n = cp41.x - cp41.y.
      // Use the absolute value so that Min and Max will correspond with the
      // minimum and maximum of the range.
      *aMin = aT - CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
      *aMax = aT + CubicRoot(std::abs(aTolerance / (cp41.x - cp41.y)));
      return;
    }

This returns an inflection point approximation of:

    t1min=-0.33756467101443444 t1max=0.33756467101443444

that looks like it will result in the correct behaviour in FlattenBezier().

And if CP1 & CP3 are also coincident, then the linear approximation is justified then.

Unfortunately, I don't have the ability to check out the code, and test this suggestion, right now.
So there is a good chance I am wrong.  :)

Comment 12

[Robert Longson [:longsonr]]

Attachment: Complete crowdsourced bugfix

Comment 13

[Robert Longson [:longsonr]]

Attachment: crowdsourced patch with mochitest

https://treeherder.mozilla.org/#/jobs?repo=try&revision=95109cb437da57364aab7e452a3988a7dc1e85e6

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/44e34213f29d
cope with degenerate bezier curves r=baz

Comment 15

[Daniel Holbert [:dholbert]]

Thanks, Paul & Robert!

Comment 16

[Cristina Coroiu [:ccoroiu]]

https://hg.mozilla.org/mozilla-central/rev/44e34213f29d

Comment 17

[Ryan VanderMeulen [:RyanVM]]

Is this worth a Beta backport nomination?

Comment 18

[Robert Longson [:longsonr]]

Comment on attachment 8993950 [details] [diff] [review]
crowdsourced patch with mochitest

Approval Request Comment
[Feature/Bug causing the regression]: bug 937994 and bug 1068603
[User impact if declined]: wrong path length/position calculations
[Is this code covered by automated tests?]: yes
[Has the fix been verified in Nightly?]: yes
[Needs manual test from QE? If yes, steps to reproduce]: no
[List of other uplifts needed for the feature/fix]: none
[Is the change risky?]: no
[Why is the change risky/not risky?]: code is unlikely to be hit and change is very small
[String changes made/needed]: none

Comment 19

[Paul LeBeau]

Thanks for applying and testing the fix Robert.

Comment 20

[Ritu Kothari (:ritu) (Inactive, please n-i to RyanVM, jcristau, or pascal)]

Comment on attachment 8993950 [details] [diff] [review]
crowdsourced patch with mochitest

Low risk fix, verified on Nightly, beta62+

Comment 21

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/releases/mozilla-beta/rev/612a64354f61