Use binary subdivision rather than Newton-Raphson iteration when the slope is very near 0 to avoid failing to converge correctly. (Bug 501569) r=dbaron
authorBrian Birtles <birtles@gmail.com>
Mon, 24 Aug 2009 12:34:34 -0700
changeset 31794 fb83d13c0625587521bfbf189501687acb520e95
parent 31793 c4365eddea673f2e48c695cd664ce7d3eab72ea8
child 31795 4aa19414e651669fa16f4c4a5ac53567f8f471c9
push id1
push userroot
push dateTue, 26 Apr 2011 22:38:44 +0000
treeherdermozilla-beta@bfdb6e623a36 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs501569
milestone1.9.3a1pre
Use binary subdivision rather than Newton-Raphson iteration when the slope is very near 0 to avoid failing to converge correctly. (Bug 501569) r=dbaron
content/smil/nsSMILAnimationFunction.cpp
content/smil/nsSMILKeySpline.cpp
content/smil/nsSMILKeySpline.h
content/smil/test/Makefile.in
content/smil/test/test_smilKeySplines.xhtml
--- a/content/smil/nsSMILAnimationFunction.cpp
+++ b/content/smil/nsSMILAnimationFunction.cpp
@@ -240,16 +240,20 @@ nsSMILAnimationFunction::ComposeResult(c
     return;
 
   // Get the animation values
   nsSMILValueArray values;
   nsresult rv = GetValues(aSMILAttr, values);
   if (NS_FAILED(rv))
     return;
 
+  // GetValues may update the error state
+  if (mErrorFlags != 0)
+    return;
+
   // If this interval is active, we must have a non-negative
   // mSampleTime and a resolved or indefinite mSimpleDuration.
   // (Otherwise, we're probably just frozen.)
   if (mIsActive) {
     NS_ENSURE_TRUE(mSampleTime >= 0,);
     NS_ENSURE_TRUE(mSimpleDuration.IsResolved() ||
                    mSimpleDuration.IsIndefinite(),);
   }
--- a/content/smil/nsSMILKeySpline.cpp
+++ b/content/smil/nsSMILKeySpline.cpp
@@ -31,19 +31,23 @@
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsSMILKeySpline.h"
+#include "prtypes.h"
 #include <math.h>
 
-#define NEWTON_ITERATIONS   4
+#define NEWTON_ITERATIONS          4
+#define NEWTON_MIN_SLOPE           0.02
+#define SUBDIVISION_PRECISION      0.0000001
+#define SUBDIVISION_MAX_ITERATIONS 10
 
 const double nsSMILKeySpline::kSampleStepSize =
                                         1.0 / double(kSplineTableSize - 1);
 
 nsSMILKeySpline::nsSMILKeySpline(double aX1,
                                  double aY1,
                                  double aX2,
                                  double aY2)
@@ -63,17 +67,17 @@ nsSMILKeySpline::GetSplineValue(double a
     return aX;
 
   return CalcBezier(GetTForX(aX), mY1, mY2);
 }
 
 void
 nsSMILKeySpline::CalcSampleValues()
 {
-  for (int i = 0; i < kSplineTableSize; ++i) {
+  for (PRUint32 i = 0; i < kSplineTableSize; ++i) {
     mSampleValues[i] = CalcBezier(double(i) * kSampleStepSize, mX1, mX2);
   }
 }
 
 /*static*/ double
 nsSMILKeySpline::CalcBezier(double aT,
                             double aA1,
                             double aA2)
@@ -82,40 +86,83 @@ nsSMILKeySpline::CalcBezier(double aT,
   return ((A(aA1, aA2)*aT + B(aA1, aA2))*aT + C(aA1))*aT;
 }
 
 /*static*/ double
 nsSMILKeySpline::GetSlope(double aT,
                           double aA1,
                           double aA2)
 {
-  double denom = (3.0 * A(aA1, aA2)*aT*aT + 2.0 * B(aA1, aA2) * aT + C(aA1));
-  return (denom == 0.0) ? 0.0 : 1.0 / denom;
+  return 3.0 * A(aA1, aA2)*aT*aT + 2.0 * B(aA1, aA2) * aT + C(aA1);
 }
 
 double
 nsSMILKeySpline::GetTForX(double aX) const
 {
-  int i;
+  // Find interval where t lies
+  double intervalStart = 0.0;
+  const double* currentSample = &mSampleValues[1];
+  const double* const lastSample = &mSampleValues[kSplineTableSize - 1];
+  for (; currentSample != lastSample && *currentSample <= aX;
+        ++currentSample) {
+    intervalStart += kSampleStepSize;
+  }
+  --currentSample; // t now lies between *currentSample and *currentSample+1
+
+  // Interpolate to provide an initial guess for t
+  double dist = (aX - *currentSample) /
+                (*(currentSample+1) - *currentSample);
+  double guessForT = intervalStart + dist * kSampleStepSize;
 
-  // Get an initial guess.
-  //
-  // Note: This is better than just taking x as our initial guess as cases such
-  // as where the control points are (1, 1), (0, 0) will take some 20 iterations
-  // to converge to a good accuracy. By taking an initial guess in this way we
-  // only need 3~4 iterations depending on the size of the table.
-  for (i = 0; i < kSplineTableSize - 2 && mSampleValues[i] < aX; ++i);
-  double currentT =
-    double(i) * kSampleStepSize + (aX - mSampleValues[i]) * kSampleStepSize;
+  // Check the slope to see what strategy to use. If the slope is too small
+  // Newton-Raphson iteration won't converge on a root so we use bisection
+  // instead.
+  double initialSlope = GetSlope(guessForT, mX1, mX2);
+  if (initialSlope >= NEWTON_MIN_SLOPE) {
+    return NewtonRaphsonIterate(aX, guessForT);
+  } else if (initialSlope == 0.0) {
+    return guessForT;
+  } else {
+    return BinarySubdivide(aX, intervalStart, intervalStart + kSampleStepSize);
+  }
+}
 
-  // Refine with Newton-Raphson iteration
-  for (i = 0; i < NEWTON_ITERATIONS; ++i) {
-    double currentX = CalcBezier(currentT, mX1, mX2);
-    double currentSlope = GetSlope(currentT, mX1, mX2);
+double
+nsSMILKeySpline::NewtonRaphsonIterate(double aX, double aGuessT) const
+{
+  // Refine guess with Newton-Raphson iteration
+  for (PRUint32 i = 0; i < NEWTON_ITERATIONS; ++i) {
+    // We're trying to find where f(t) = aX,
+    // so we're actually looking for a root for: CalcBezier(t) - aX
+    double currentX = CalcBezier(aGuessT, mX1, mX2) - aX;
+    double currentSlope = GetSlope(aGuessT, mX1, mX2);
 
     if (currentSlope == 0.0)
-      return currentT;
+      return aGuessT;
+
+    aGuessT -= currentX / currentSlope;
+  }
+
+  return aGuessT;
+}
 
-    currentT -= (currentX - aX) * currentSlope;
-  }
+double
+nsSMILKeySpline::BinarySubdivide(double aX, double aA, double aB) const
+{
+  double currentX;
+  double currentT;
+  PRUint32 i = 0;
+
+  do
+  {
+    currentT = aA + (aB - aA) / 2.0;
+    currentX = CalcBezier(currentT, mX1, mX2) - aX;
+
+    if (currentX > 0.0) {
+      aB = currentT;
+    } else {
+      aA = currentT;
+    }
+  } while (fabs(currentX) > SUBDIVISION_PRECISION
+           && ++i < SUBDIVISION_MAX_ITERATIONS);
 
   return currentT;
 }
--- a/content/smil/nsSMILKeySpline.h
+++ b/content/smil/nsSMILKeySpline.h
@@ -33,53 +33,64 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef NS_SMILKEYSPLINE_H_
 #define NS_SMILKEYSPLINE_H_
 
-#include "prtypes.h"
-
 /**
  * Utility class to provide scaling defined in a keySplines element.
  */
 class nsSMILKeySpline
 {
 public:
-  /*
-   * Create a new key spline control point description.
+  /**
+   * Creates a new key spline control point description.
    *
    * aX1, etc. are the x1, y1, x2, y2 cubic Bezier control points as defined by
    * SMILANIM 3.2.3. They must each be in the range 0.0 <= x <= 1.0
    */
   nsSMILKeySpline(double aX1, double aY1,
                   double aX2, double aY2);
 
-  /*
-   * Get the output (y) value for an input (x).
+  /**
+   * Gets the output (y) value for an input (x).
    *
-   * x should be a floating-point number between 0 and 1 (inclusive).
+   * @param aX  The input x value. A floating-point number between 0 and
+   *            1 (inclusive).
    */
   double GetSplineValue(double aX) const;
 
 private:
   void
   CalcSampleValues();
 
+  /**
+   * Returns x(t) given t, x1, and x2, or y(t) given t, y1, and y2.
+   */
   static double
   CalcBezier(double aT, double aA1, double aA2);
 
+  /**
+   * Returns dx/dt given t, x1, and x2, or dy/dt given t, y1, and y2.
+   */
   static double
   GetSlope(double aT, double aA1, double aA2);
 
   double
   GetTForX(double aX) const;
 
+  double
+  NewtonRaphsonIterate(double aX, double aGuessT) const;
+
+  double
+  BinarySubdivide(double aX, double aA, double aB) const;
+
   static double
   A(double aA1, double aA2)
   {
     return 1.0 - 3.0 * aA2 + 3.0 * aA1;
   }
 
   static double
   B(double aA1, double aA2)
--- a/content/smil/test/Makefile.in
+++ b/content/smil/test/Makefile.in
@@ -42,16 +42,17 @@ VPATH		= @srcdir@
 relativesrcdir  = content/smil/test
 
 include $(DEPTH)/config/autoconf.mk
 include $(topsrcdir)/config/rules.mk
 
 _TEST_FILES = 	test_smilRestart.xhtml \
 	  test_smilGetStartTime.xhtml \
 	  test_smilGetSimpleDuration.xhtml \
+	  test_smilKeySplines.xhtml \
 	  test_smilSetCurrentTime.xhtml \
 	  test_smilSync.xhtml \
 	  test_smilSyncTransform.xhtml \
 	  test_smilTiming.xhtml \
 	  test_smilTimingZeroIntervals.xhtml \
 		$(NULL)
 
 libs:: $(_TEST_FILES)
new file mode 100644
--- /dev/null
+++ b/content/smil/test/test_smilKeySplines.xhtml
@@ -0,0 +1,297 @@
+<html xmlns="http://www.w3.org/1999/xhtml">
+<head>
+  <title>Test for SMIL keySplines</title>
+  <script type="text/javascript" src="/MochiKit/packed.js"></script>
+  <script type="text/javascript" src="/tests/SimpleTest/SimpleTest.js"></script>
+  <link rel="stylesheet" type="text/css" href="/tests/SimpleTest/test.css" />
+</head>
+<body>
+<p id="display"></p>
+<div id="content" style="display: none">
+<svg id="svg" xmlns="http://www.w3.org/2000/svg" width="120px" height="120px">
+  <circle cx="-100" cy="20" r="15" fill="blue" id="circle"/>
+</svg>
+</div>
+<pre id="test">
+<script class="testbody" type="text/javascript">
+<![CDATA[
+/** Test for SMIL keySplines **/
+
+/* Global Variables */
+const svgns="http://www.w3.org/2000/svg";
+var svg = document.getElementById("svg");
+var circle = document.getElementById('circle');
+
+SimpleTest.waitForExplicitFinish();
+
+function createAnim() {
+  var anim = document.createElementNS(svgns,'animate');
+  anim.setAttribute('attributeName','cx');
+  anim.setAttribute('dur','10s');
+  anim.setAttribute('begin','0s');
+  anim.setAttribute('fill', 'freeze');
+  return circle.appendChild(anim);
+}
+
+function main() {
+  svg.pauseAnimations();
+  var tests =
+    [ testSimpleA, // these first four are from SVG 1.1
+      testSimpleB,
+      testSimpleC,
+      testSimpleD,
+      testSimpleE, // bug 501569
+      testMultipleIntervalsA,
+      testMultipleIntervalsB,
+      testMultipleIntervalsC,
+      testOneValue,
+      testFromTo,
+      testWrongNumSplines,
+      testToAnimation,
+      testOkSyntax,
+      testBadSyntaxA,
+      testBadSyntaxB
+    ];
+  for (var i = 0; i < tests.length; i++) {
+    var anim = createAnim();
+    svg.setCurrentTime(0);
+    tests[i](anim);
+    removeElement(anim);
+  }
+  SimpleTest.finish();
+}
+
+function checkSample(time, expectedValue) {
+  svg.setCurrentTime(time);
+  is(circle.cx.animVal.value, expectedValue);
+}
+
+function checkSampleRough(time, expectedValue, precision) {
+  const defaultPrecision = 0.00001;
+  if (typeof precision == "undefined") {
+    precision = defaultPrecision;
+  }
+  svg.setCurrentTime(time);
+  var diff = Math.abs(expectedValue - circle.cx.animVal.value);
+  ok(diff <= precision, 
+    "Unexpected sample value got " + circle.cx.animVal.value
+      + ", expected " + expectedValue + " [error: " + diff
+      + " > tolerance: " + precision + "]");
+}
+
+/*
+ * These first four tests are the examples given in SVG 1.1, section 19.2.7
+ */
+
+function testSimpleA(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20');
+  anim.setAttribute('keyTimes', '0; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '0 0 1 1');
+  checkSample(0, 10);
+  checkSample(1, 12.5);
+  checkSample(2, 15);
+  checkSample(3, 17.5);
+  checkSample(4, 20);
+}
+
+function testSimpleB(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20');
+  anim.setAttribute('keyTimes', '0; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '.5 0 .5 1');
+  checkSample(0, 10);
+  checkSampleRough(1, 11.058925);
+  checkSample(2, 15);
+  checkSampleRough(3, 18.941075);
+  checkSample(4, 20);
+}
+
+function testSimpleC(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20');
+  anim.setAttribute('keyTimes', '0; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '0 .75 .25 1');
+  checkSample(0, 10);
+  checkSampleRough(1, 18.101832);
+  checkSampleRough(2, 19.413430);
+  checkSampleRough(3, 19.886504);
+  checkSample(4, 20);
+}
+
+function testSimpleD(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20');
+  anim.setAttribute('keyTimes', '0; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '1 0 .25 .25');
+  checkSample(0, 10);
+  checkSampleRough(1, 10.076925);
+  checkSampleRough(2, 10.644369);
+  checkSampleRough(3, 16.908699);
+  checkSample(4, 20);
+}
+
+// Bug 501569 -- nsSMILKeySpline(1, 0, 0, 1) miscalculates values just under 0.5
+function testSimpleE(anim) {
+  anim.setAttribute('dur','10s');
+  anim.setAttribute('values', '0; 10');
+  anim.setAttribute('keyTimes', '0; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '1 0 0 1');
+  checkSample(0, 0);
+  checkSampleRough(0.001, 0);
+  checkSampleRough(4.95, 3.409174);
+  checkSampleRough(4.98, 3.819443);
+  checkSampleRough(4.99, 4.060174);
+  checkSampleRough(4.999, 4.562510);
+  checkSample(5, 5);
+  checkSampleRough(5.001, 5.437490);
+  checkSampleRough(5.01, 5.939826);
+  checkSampleRough(5.015, 6.075002);
+  checkSampleRough(5.02, 6.180557);
+  checkSampleRough(9.9999, 10);
+  checkSample(10, 10);
+}
+
+function testMultipleIntervalsA(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20; 30');
+  anim.setAttribute('keyTimes', '0; 0.25; 1');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '0 0 1 1; .5 0 .5 1;');
+  checkSample(0.5, 15);
+  checkSampleRough(0.999, 20, 0.02);
+  checkSample(1, 20);
+  checkSampleRough(1.001, 20, 0.05);
+  checkSample(2.5, 25);
+  checkSampleRough(3.25, 29, 0.1);
+}
+
+function testMultipleIntervalsB(anim) {
+  // as above but without keyTimes
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20; 30');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '0 0 1 1; .5 0 .5 1;');
+  checkSample(1, 15);
+  checkSampleRough(1.999, 20, 0.01);
+  checkSample(2, 20);
+  checkSampleRough(2.001, 20, 0.01);
+  checkSample(3, 25);
+  checkSampleRough(3.5, 29, 0.1);
+}
+
+function testMultipleIntervalsC(anim) {
+  // test some unusual (but valid) syntax
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20; 30');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', ' 0 .75 0.25 1 ; 1, 0 ,.25 .25  \t');
+  checkSampleRough(3.5, 26.9, 0.2);
+}
+
+function testOneValue(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '5');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '0 0 1 1');
+  checkSample(0, 5);
+  checkSample(1.5, 5);
+}
+
+function testFromTo(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('from', '10');
+  anim.setAttribute('to', '20');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '.5 0 .5 1');
+  checkSample(0, 10);
+  checkSampleRough(1, 11, 0.1);
+}
+
+function testWrongNumSplines(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('from', '10');
+  anim.setAttribute('to', '20');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '.5 0 .5 1; 0 0 1 1');
+  // animation is in error, should do nothing
+  checkSample(1.5, -100);
+}
+
+function testToAnimation(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('to', '20');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', '.5 0 .5 1');
+  checkSample(0, -100);
+  checkSampleRough(1, -87.3, 0.1);
+}
+
+function testOkSyntax(anim) {
+  var okStrs = ['0,0,0,0', // all commas
+                '  0 0   , 0  ,0  ', // mix of separators
+                '0 0 0 0;', // trailing semi-colon
+                '0 0 0 0 ;']; //   "      "
+
+  for (var i = 0; i < okStrs.length; i++) {
+    testAnim = createAnim();
+    testAnim.setAttribute('dur','4s');
+    testAnim.setAttribute('from', '0');
+    testAnim.setAttribute('to', '20');
+    testAnim.setAttribute('calcMode', 'spline');
+    testAnim.setAttribute('keySplines', okStrs[i]);
+    checkSample(4, 20);
+  }
+}
+
+function testBadSyntaxA(anim) {
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('from', '0');
+  anim.setAttribute('to', '20');
+  anim.setAttribute('calcMode', 'spline');
+
+  var badStrs = ['', // empty
+                 '    ', // whitespace only
+                 '0,1.1,0,0', // bad range
+                 '0,0,0,-0.1', // "   "
+                 '  0 0   , 0  0   ,', // stray comma
+                 '1-1 0 0', // path-style separators
+                 '0 0 0', // wrong number of values
+                 '0 0 0 0 0', //  "     "
+                 '0 0 0 0 0 0 0 0', //  "     "
+                 '0 0 0; 0 0 0 0', //  "     "
+                 '0 0 0; 0', // mis-placed semi-colon
+                 ';0 0 0 0']; //    "    "
+
+  for (var i = 0; i < badStrs.length; i++) {
+    testAnim = createAnim();
+    testAnim.setAttribute('dur','4s');
+    testAnim.setAttribute('from', '0');
+    testAnim.setAttribute('to', '20');
+    testAnim.setAttribute('calcMode', 'spline');
+    testAnim.setAttribute('keySplines', badStrs[i]);
+    checkSample(4, -100);
+  }
+}
+
+function testBadSyntaxB(anim) {
+  // test some illegal syntax
+  anim.setAttribute('dur','4s');
+  anim.setAttribute('values', '10; 20; 30');
+  anim.setAttribute('calcMode', 'spline');
+  anim.setAttribute('keySplines', ' 0 .75 0.25 1 ; 1, A0 ,.25 .25  \t');
+  // animation is in error, should do nothing
+  checkSample(3.5, -100);
+}
+
+window.addEventListener("load", main, false);
+]]>
+</script>
+</pre>
+</body>
+</html>