Bug 1134549 - Switch FlattenBezier from floats to doubles. r=bas
☠☠ backed out by 55b78f481396 ☠ ☠
authorTom Klein <twointofive@gmail.com>
Wed, 20 May 2015 11:44:05 +0100
changeset 244750 81a47807c54a32c28d709c1ee555ec147e4f604a
parent 244749 9571f765357d8a3f3a79e681c44d8d516bffe719
child 244751 c163ecde3b7fbb232d87a8e1774f60e22134243d
push id28788
push userkwierso@gmail.com
push dateThu, 21 May 2015 01:16:49 +0000
treeherdermozilla-central@bc3500c5afa0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbas
bugs1134549
milestone41.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1134549 - Switch FlattenBezier from floats to doubles. r=bas
gfx/2d/Path.cpp
gfx/tests/crashtests/1134549-1.svg
gfx/tests/crashtests/crashtests.list
--- a/gfx/2d/Path.cpp
+++ b/gfx/2d/Path.cpp
@@ -5,40 +5,52 @@
 
 #include "2D.h"
 #include "PathAnalysis.h"
 #include "PathHelpers.h"
 
 namespace mozilla {
 namespace gfx {
 
-static float CubicRoot(float aValue) {
+static double CubicRoot(double aValue) {
   if (aValue < 0.0) {
     return -CubicRoot(-aValue);
   }
   else {
-    return powf(aValue, 1.0f / 3.0f);
+    return pow(aValue, 1.0 / 3.0);
   }
 }
 
+struct PointD : public BasePoint<double, PointD> {
+  typedef BasePoint<double, PointD> Super;
+
+  PointD() : Super() {}
+  PointD(double aX, double aY) : Super(aX, aY) {}
+  MOZ_IMPLICIT PointD(const Point& aPoint) : Super(aPoint.x, aPoint.y) {}
+
+  Point ToPoint() const {
+    return Point(static_cast<Float>(x), static_cast<Float>(y));
+  }
+};
+
 struct BezierControlPoints
 {
   BezierControlPoints() {}
-  BezierControlPoints(const Point &aCP1, const Point &aCP2,
-                      const Point &aCP3, const Point &aCP4)
+  BezierControlPoints(const PointD &aCP1, const PointD &aCP2,
+                      const PointD &aCP3, const PointD &aCP4)
     : mCP1(aCP1), mCP2(aCP2), mCP3(aCP3), mCP4(aCP4)
   {
   }
 
-  Point mCP1, mCP2, mCP3, mCP4;
+  PointD mCP1, mCP2, mCP3, mCP4;
 };
 
 void
 FlattenBezier(const BezierControlPoints &aPoints,
-              PathSink *aSink, Float aTolerance);
+              PathSink *aSink, double aTolerance);
 
 
 Path::Path()
 {
 }
 
 Path::~Path()
 {
@@ -200,109 +212,108 @@ FlattenedPath::ComputePointAtLength(Floa
 }
 
 // This function explicitly permits aControlPoints to refer to the same object
 // as either of the other arguments.
 static void 
 SplitBezier(const BezierControlPoints &aControlPoints,
             BezierControlPoints *aFirstSegmentControlPoints,
             BezierControlPoints *aSecondSegmentControlPoints,
-            Float t)
+            double t)
 {
   MOZ_ASSERT(aSecondSegmentControlPoints);
   
   *aSecondSegmentControlPoints = aControlPoints;
 
-  Point cp1a = aControlPoints.mCP1 + (aControlPoints.mCP2 - aControlPoints.mCP1) * t;
-  Point cp2a = aControlPoints.mCP2 + (aControlPoints.mCP3 - aControlPoints.mCP2) * t;
-  Point cp1aa = cp1a + (cp2a - cp1a) * t;
-  Point cp3a = aControlPoints.mCP3 + (aControlPoints.mCP4 - aControlPoints.mCP3) * t;
-  Point cp2aa = cp2a + (cp3a - cp2a) * t;
-  Point cp1aaa = cp1aa + (cp2aa - cp1aa) * t;
+  PointD cp1a = aControlPoints.mCP1 + (aControlPoints.mCP2 - aControlPoints.mCP1) * t;
+  PointD cp2a = aControlPoints.mCP2 + (aControlPoints.mCP3 - aControlPoints.mCP2) * t;
+  PointD cp1aa = cp1a + (cp2a - cp1a) * t;
+  PointD cp3a = aControlPoints.mCP3 + (aControlPoints.mCP4 - aControlPoints.mCP3) * t;
+  PointD cp2aa = cp2a + (cp3a - cp2a) * t;
+  PointD cp1aaa = cp1aa + (cp2aa - cp1aa) * t;
   aSecondSegmentControlPoints->mCP4 = aControlPoints.mCP4;
 
   if(aFirstSegmentControlPoints) {
     aFirstSegmentControlPoints->mCP1 = aControlPoints.mCP1;
     aFirstSegmentControlPoints->mCP2 = cp1a;
     aFirstSegmentControlPoints->mCP3 = cp1aa;
     aFirstSegmentControlPoints->mCP4 = cp1aaa;
   }
   aSecondSegmentControlPoints->mCP1 = cp1aaa;
   aSecondSegmentControlPoints->mCP2 = cp2aa;
   aSecondSegmentControlPoints->mCP3 = cp3a;
 }
 
 static void
 FlattenBezierCurveSegment(const BezierControlPoints &aControlPoints,
                           PathSink *aSink,
-                          Float aTolerance)
+                          double aTolerance)
 {
   /* The algorithm implemented here is based on:
    * http://cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf
    *
    * 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.
    */
   BezierControlPoints currentCP = aControlPoints;
 
-  Float t = 0;
-  while (t < 1.0f) {
-    Point cp21 = currentCP.mCP2 - currentCP.mCP3;
-    Point cp31 = currentCP.mCP3 - currentCP.mCP1;
+  double t = 0;
+  while (t < 1.0) {
+    PointD cp21 = currentCP.mCP2 - currentCP.mCP3;
+    PointD cp31 = currentCP.mCP3 - currentCP.mCP1;
 
-    Float s3 = (cp31.x * cp21.y - cp31.y * cp21.x) / hypotf(cp21.x, cp21.y);
+    double s3 = (cp31.x * cp21.y - cp31.y * cp21.x) / hypot(cp21.x, cp21.y);
 
-    t = 2 * Float(sqrt(aTolerance / (3. * std::abs(s3))));
+    t = 2 * sqrt(aTolerance / (3. * std::abs(s3)));
 
-    if (t >= 1.0f) {
-      aSink->LineTo(aControlPoints.mCP4);
+    if (t >= 1.0) {
+      aSink->LineTo(aControlPoints.mCP4.ToPoint());
       break;
     }
 
-    Point prevCP2, prevCP3, nextCP1, nextCP2, nextCP3;
     SplitBezier(currentCP, nullptr, &currentCP, t);
 
-    aSink->LineTo(currentCP.mCP1);
+    aSink->LineTo(currentCP.mCP1.ToPoint());
   }
 }
 
 static inline void
 FindInflectionApproximationRange(BezierControlPoints aControlPoints,
-                                 Float *aMin, Float *aMax, Float aT,
-                                 Float aTolerance)
+                                 double *aMin, double *aMax, double aT,
+                                 double aTolerance)
 {
     SplitBezier(aControlPoints, nullptr, &aControlPoints, aT);
 
-    Point cp21 = aControlPoints.mCP2 - aControlPoints.mCP1;
-    Point cp41 = aControlPoints.mCP4 - aControlPoints.mCP1;
+    PointD cp21 = aControlPoints.mCP2 - aControlPoints.mCP1;
+    PointD cp41 = aControlPoints.mCP4 - aControlPoints.mCP1;
 
-    if (cp21.x == 0.f && cp21.y == 0.f) {
+    if (cp21.x == 0. && cp21.y == 0.) {
       // 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;
     }
 
-    Float s3 = (cp41.x * cp21.y - cp41.y * cp21.x) / hypotf(cp21.x, cp21.y);
+    double s3 = (cp41.x * cp21.y - cp41.y * cp21.x) / hypot(cp21.x, cp21.y);
 
     if (s3 == 0) {
       // This means within the precision we have it can be approximated
       // infinitely by a linear segment. Deal with this by specifying the
       // approximation range as extending beyond the entire curve.
-      *aMin = -1.0f;
-      *aMax = 2.0f;
+      *aMin = -1.0;
+      *aMax = 2.0;
       return;
     }
 
-    Float tf = CubicRoot(std::abs(aTolerance / s3));
+    double tf = CubicRoot(std::abs(aTolerance / s3));
 
     *aMin = aT - tf * (1 - aT);
     *aMax = aT + tf * (1 - aT);
 }
 
 /* Find the inflection points of a bezier curve. Will return false if the
  * curve is degenerate in such a way that it is best approximated by a straight
  * line.
@@ -351,28 +362,28 @@ FindInflectionApproximationRange(BezierC
  * x = 3 * (-b + sqrt(b * b - 4 * a * c)) / (2 * 3 * a)
  * x = (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
  *
  * I haven't looked into whether the formulation of the quadratic formula in
  * hain has any numerical advantages over the one used below.
  */
 static inline void
 FindInflectionPoints(const BezierControlPoints &aControlPoints,
-                     Float *aT1, Float *aT2, uint32_t *aCount)
+                     double *aT1, double *aT2, uint32_t *aCount)
 {
   // Find inflection points.
   // See www.faculty.idc.ac.il/arik/quality/appendixa.html for an explanation
   // of this approach.
-  Point A = aControlPoints.mCP2 - aControlPoints.mCP1;
-  Point B = aControlPoints.mCP3 - (aControlPoints.mCP2 * 2) + aControlPoints.mCP1;
-  Point C = aControlPoints.mCP4 - (aControlPoints.mCP3 * 3) + (aControlPoints.mCP2 * 3) - aControlPoints.mCP1;
+  PointD A = aControlPoints.mCP2 - aControlPoints.mCP1;
+  PointD B = aControlPoints.mCP3 - (aControlPoints.mCP2 * 2) + aControlPoints.mCP1;
+  PointD C = aControlPoints.mCP4 - (aControlPoints.mCP3 * 3) + (aControlPoints.mCP2 * 3) - aControlPoints.mCP1;
 
-  Float a = Float(B.x) * C.y - Float(B.y) * C.x;
-  Float b = Float(A.x) * C.y - Float(A.y) * C.x;
-  Float c = Float(A.x) * B.y - Float(A.y) * B.x;
+  double a = B.x * C.y - B.y * C.x;
+  double b = A.x * C.y - A.y * C.x;
+  double c = A.x * B.y - A.y * B.x;
 
   if (a == 0) {
     // Not a quadratic equation.
     if (b == 0) {
       // Instead of a linear acceleration change we have a constant
       // acceleration change. This means the equation has no solution
       // and there are no inflection points, unless the constant is 0.
       // In that case the curve is a straight line, essentially that means
@@ -386,68 +397,68 @@ FindInflectionPoints(const BezierControl
       }
       *aCount = 0;
       return;
     }
     *aT1 = -c / b;
     *aCount = 1;
     return;
   } else {
-    Float discriminant = b * b - 4 * a * c;
+    double discriminant = b * b - 4 * a * c;
 
     if (discriminant < 0) {
       // No inflection points.
       *aCount = 0;
     } else if (discriminant == 0) {
       *aCount = 1;
       *aT1 = -b / (2 * a);
     } else {
       /* Use the following formula for computing the roots:
        *
        * q = -1/2 * (b + sign(b) * sqrt(b^2 - 4ac))
        * t1 = q / a
        * t2 = c / q
        */
-      Float q = sqrtf(discriminant);
+      double q = sqrt(discriminant);
       if (b < 0) {
         q = b - q;
       } else {
         q = b + q;
       }
-      q *= Float(-1./2);
+      q *= -1./2;
 
       *aT1 = q / a;
       *aT2 = c / q;
       if (*aT1 > *aT2) {
         std::swap(*aT1, *aT2);
       }
       *aCount = 2;
     }
   }
 
   return;
 }
 
 void
 FlattenBezier(const BezierControlPoints &aControlPoints,
-              PathSink *aSink, Float aTolerance)
+              PathSink *aSink, double aTolerance)
 {
-  Float t1;
-  Float t2;
+  double t1;
+  double t2;
   uint32_t count;
 
   FindInflectionPoints(aControlPoints, &t1, &t2, &count);
 
   // Check that at least one of the inflection points is inside [0..1]
   if (count == 0 || ((t1 < 0 || t1 > 1.0) && ((t2 < 0 || t2 > 1.0) || count == 1)) ) {
     FlattenBezierCurveSegment(aControlPoints, aSink, aTolerance);
     return;
   }
 
-  Float t1min = t1, t1max = t1, t2min = t2, t2max = t2;
+  double t1min = t1, t1max = t1, t2min = t2, t2max = t2;
 
   BezierControlPoints remainingCP = aControlPoints;
 
   // For both inflection points, calulate the range where they can be linearly
   // approximated if they are positioned within [0,1]
   if (count > 0 && t1 >= 0 && t1 < 1.0) {
     FindInflectionApproximationRange(aControlPoints, &t1min, &t1max, t1, aTolerance);
   }
@@ -456,75 +467,75 @@ FlattenBezier(const BezierControlPoints 
   }
   BezierControlPoints nextCPs = aControlPoints;
   BezierControlPoints prevCPs;
 
   // 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);
+    aSink->LineTo(aControlPoints.mCP4.ToPoint());
     return;
   }
 
   if (t1min > 0) {
     // Flatten the Bezier up until the first inflection point's approximation
     // point.
     SplitBezier(aControlPoints, &prevCPs,
                 &remainingCP, t1min);
     FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
   }
   if (t1max >= 0 && t1max < 1.0 && (count == 1 || t2min > t1max)) {
     // The second inflection point's approximation range begins after the end
     // of the first, approximate the first inflection point by a line and
     // subsequently flatten up until the end or the next inflection point.
     SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
 
-    aSink->LineTo(nextCPs.mCP1);
+    aSink->LineTo(nextCPs.mCP1.ToPoint());
 
     if (count == 1 || (count > 1 && t2min >= 1.0)) {
       // No more inflection points to deal with, flatten the rest of the curve.
       FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
     }
   } else if (count > 1 && t2min > 1.0) {
     // We've already concluded t2min <= t1max, so if this is true the
     // approximation range for the first inflection point runs past the
     // end of the curve, draw a line to the end and we're done.
-    aSink->LineTo(aControlPoints.mCP4);
+    aSink->LineTo(aControlPoints.mCP4.ToPoint());
     return;
   }
 
   if (count > 1 && t2min < 1.0 && t2max > 0) {
     if (t2min > 0 && t2min < t1max) {
       // In this case the t2 approximation range starts inside the t1
       // approximation range.
       SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
-      aSink->LineTo(nextCPs.mCP1);
+      aSink->LineTo(nextCPs.mCP1.ToPoint());
     } else if (t2min > 0 && t1max > 0) {
       SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
 
       // Find a control points describing the portion of the curve between t1max and t2min.
-      Float t2mina = (t2min - t1max) / (1 - t1max);
+      double t2mina = (t2min - t1max) / (1 - t1max);
       SplitBezier(nextCPs, &prevCPs, &nextCPs, t2mina);
       FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
     } else if (t2min > 0) {
       // We have nothing interesting before t2min, find that bit and flatten it.
       SplitBezier(aControlPoints, &prevCPs, &nextCPs, t2min);
       FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
     }
     if (t2max < 1.0) {
       // Flatten the portion of the curve after t2max
       SplitBezier(aControlPoints, nullptr, &nextCPs, t2max);
 
       // Draw a line to the start, this is the approximation between t2min and
       // t2max.
-      aSink->LineTo(nextCPs.mCP1);
+      aSink->LineTo(nextCPs.mCP1.ToPoint());
       FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
     } else {
       // Our approximation range extends beyond the end of the curve.
-      aSink->LineTo(aControlPoints.mCP4);
+      aSink->LineTo(aControlPoints.mCP4.ToPoint());
       return;
     }
   }
 }
 
 }
 }
new file mode 100644
--- /dev/null
+++ b/gfx/tests/crashtests/1134549-1.svg
@@ -0,0 +1,14 @@
+<svg xmlns="http://www.w3.org/2000/svg"
+     xmlns:xlink="http://www.w3.org/1999/xlink"
+     width="400" height="400"
+     viewBox="694400 -179730 8000 8000">
+
+  <defs>
+    <path id="tp_crash" d="M 698430.938,-174861.922 C 699068.125,-175493.781 699593.562,-176022.531 699499,-177727" />
+  </defs>
+
+  <text font-size="4000">
+    <textPath xlink:href="#tp_crash">Eisack</textPath>
+  </text>
+  <use xlink:href="#tp_crash" fill="none" stroke="green" stroke-width="200"></use>
+</svg>
--- a/gfx/tests/crashtests/crashtests.list
+++ b/gfx/tests/crashtests/crashtests.list
@@ -110,8 +110,9 @@ load 856784-1.html
 load 893572-1.html
 load 893572-2.html
 load 893572-3.html
 load 893572-4.html
 load 944579.svg
 load 944579.html
 pref(security.fileuri.strict_origin_policy,false) load 950000.html
 load 1034403-1.html
+load 1134549-1.svg