501569 - nsSMILKeySpline(1, 0, 0, 1) miscalculates values just under 0.5

Status: RESOLVED FIXED

(Core :: SVG, defect)

Description

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

I'm calling nsSMILKeySpline from the CSS transitions implementation that I'm working on (bug 435441).  I found a case where the approximation algorithm it uses produces a drastically-incorrect result.  The simple testcase for this is to write the following code:

    nsSMILKeySpline s(1.0, 0.0, 0.0, 1.0);
    printf("%f\n", s.GetSplineValue(0.4965));

It should produce a value slightly under 0.5 (but significantly more under than 0.4965).  It instead produces 702199096.822357.

(While I'm there... it seems like the "pow(aT, 3)" in CalcBezier might be significantly slower aT*aT*aT*aT, although I haven't profiled.)

Comment 1

[Brian Birtles (:birtles)]

Looks like a good catch to me. I checked the old unit tests and this case isn't covered. I'm happy to take this provided there's no urgency. I probably won't be able to get to it for a few weeks.

If someone else wants to have a look at this, it is described in section 6.4 of http://brian.sol1.net/svg/report/report.pdf

(I'll also take your word for it regarding the performance tweak. I'm sure you know more about it than I do. Unless someone else takes this or suggests otherwise I'll include this in the patch too.)

Comment 2

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Slightly more data.  Based on:

    nsSMILKeySpline s(1.0, 0.0, 0.0, 1.0);
    for (double time_portion = 0.4958; time_portion < 0.5002;
         time_portion += 0.00001) {
        printf("time=%f value=%f\n",
               time_portion, s.GetSplineValue(time_portion));
    }

(I started with a broader range and then did that one and a few others) the problem occurs when the input is between 0.496 and 0.5 (both boundaries exclusive, but apparently exact)

Comment 3

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

When this is fixed, we need to undo the following change to test_transitions.html (which is the mochitest equivalent of marking a test random):

http://hg.mozilla.org/users/dbaron_mozilla.com/patches/rev/0df87177dc55

(If test_transitions.html doesn't land first, then I'll need to do it myself, but if it does, whoever lands this patch should.)

Comment 4

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

(In reply to comment #0)
> (While I'm there... it seems like the "pow(aT, 3)" in CalcBezier might be
> significantly slower aT*aT*aT*aT, although I haven't profiled.)

This was fixed in bug 501428.

Comment 5

[Brian Birtles (:birtles)]

Attachment: proposed patch v1a

Proposed patch to fix this. We're using Newton-Raphson which doesn't converge on a root near those points where the slope is 0 (as occurs for x=f(t) with x1=1, x2=0). This patch detects that situation and uses binary subdivision when it occurs.

I haven't updated test_transitions.html as it doesn't appear to have landed yet.

I've converted over the old C++ unit tests for keySplines from bug 474742.

Comment 6

[Robert Longson [:longsonr]]

Some nits...

Use PRuint32 rather than int and move the Newton-Raphson code to a separate method like you have done for BinarySubdivide you can then just return the result rathern than assigning to currentT.

Comment 7

[Brian Birtles (:birtles)]

Attachment: patch v1b

Address Robert's feedback in comment 6.

Thanks Robert!

Comment 8

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Comment on attachment 395187 [details] [diff] [review]
patch v1b

It might help if the comments said that:

  * CalcBezier returns x(t) given t, x1, and x2, or y(t) given
    t, y1, and y2
  * CalcSlope returns dx/dt given t, x1, and x2, or dy/dt given
    t, y1, and y2
    
+  double const *currentSample = &mSampleValues[1];
+  double const * const lastSample = &mSampleValues[kSplineTableSize - 1];

I prefer |const double| over |double const|, but it's your call.

+  for (PRUint32 i = 0;
+       fabs(currentX) > SUBDIVISION_PRECISION && i < SUBDIVISION_MAX_ITERATIONS;
+       ++i) {

Given that the condition is always false the first time through, it 
seems like it would be clearer to make this a do { } while (); loop.  
That way you also wouldn't need to initialize currentX to the bogus 1.0 
to force it to fail.



This doesn't look like it needs sr, so marking r=dbaron.  (Or was there 
a particular reason you wanted roc to look at it?)

Comment 9

[Brian Birtles (:birtles)]

Attachment: patch v1c (address dbaron's review comments)

Ready for landing

Comment 10

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

http://hg.mozilla.org/mozilla-central/rev/fb83d13c0625

Comment 11

[Boris Zbarsky [:bzbarsky]]

So this added a lot of noise to the tinderbox short logs; presumably because of the use of "error:" in all those test strings?

Comment 12

[Boris Zbarsky [:bzbarsky]]

Yeah, the shortlog parser looks for things including:

  /\WError: /i

Comment 13

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

I fixed the strings in the test so they don't have "error:" in them:
http://hg.mozilla.org/mozilla-central/rev/4152186f5fda