[SVG] Fix infinite curveLength() loop.

Source/platform/graphics/PathTraversalState.cpp

 /*
  * Copyright (C) 2006, 2007 Eric Seidel <eric@webkit.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 33 matching lines @@
         , control(c)
         , end(e)
     {
     }
 
     float approximateDistance() const
     {
         return distanceLine(start, control) + distanceLine(control, end);
     }
 
-    void split(QuadraticBezier& left, QuadraticBezier& right) const
+    bool equals(const QuadraticBezier& other) const
+    {
+        return start == other.start
+            && end == other.end
+            && control == other.control;
+    }
+
+    bool split(QuadraticBezier& left, QuadraticBezier& right) const
     {
         left.control = midPoint(start, control);
         right.control = midPoint(control, end);
 
         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
         left.end = leftControlToRightControl;
         right.start = leftControlToRightControl;
 
         left.start = start;
         right.end = end;
+
+        return !equals(left) && !equals(right);
     }
 
     FloatPoint start;
     FloatPoint control;
     FloatPoint end;
 };
 
 struct CubicBezier {
     CubicBezier() { }
     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
         : start(s)
         , control1(c1)
         , control2(c2)
         , end(e)
     {
     }
 
     float approximateDistance() const
     {
         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
     }
 
-    void split(CubicBezier& left, CubicBezier& right) const
+    bool equals(const CubicBezier& other) const
+    {
+        return start == other.start
+            && end == other.end
+            && control1 == other.control1
+            && control2 == other.control2;
+    }
+
+    bool split(CubicBezier& left, CubicBezier& right) const
     {
         FloatPoint startToControl1 = midPoint(control1, control2);
 
         left.start = start;
         left.control1 = midPoint(start, control1);
         left.control2 = midPoint(left.control1, startToControl1);
 
         right.control2 = midPoint(control2, end);
         right.control1 = midPoint(right.control2, startToControl1);
         right.end = end;
 
         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
         left.end = leftControl2ToRightControl1;
         right.start = leftControl2ToRightControl1;
+
+        return !equals(left) && !equals(right);
     }
 
     FloatPoint start;
     FloatPoint control1;
     FloatPoint control2;
     FloatPoint end;
 };
 
 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
 // A simple speed-up would be to use an additional boolean template parameter to control whether
 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
 // version which does update the PathTraversalState. We'll have to shark it to see if that's necessary.
 // Another check which is possible up-front (to send us down the fast path) would be to check if
 // approximateDistance() + current total distance > desired distance
 template<class CurveType>
 static float curveLength(PathTraversalState& traversalState, CurveType curve)
 {
     static const unsigned curveStackDepthLimit = 20;
 
     Vector<CurveType> curveStack;
     curveStack.append(curve);
 
     float totalLength = 0;
+    CurveType leftCurve, rightCurve;
     do {
         float length = curve.approximateDistance();
-        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() <= curveStackDepthLimit) {
-            CurveType leftCurve;
-            CurveType rightCurve;
-            curve.split(leftCurve, rightCurve);
+        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance

[Stephen Chennney, 2014/03/07 16:25:31]

The real problem is that tolerance is a fixed value that fails to account for
the scale of the values. You should compare fabs(((length -
distanceLine(...))/length) > kPathSegLengthTolerance. You might even be able to
adjust kPathSegLengthTolerance in that case to a higher value. 0.001 bounds your
error to 0.1%.

[f(malita), 2014/03/07 18:02:26]

I disagree: the immediate problem is that the algorithm gets stuck trying to
split curves and not making any progress. We can detect and avoid this condition
easily.

Now maybe (**) the updated tolerance test you suggest guarantees a significant
split, but it's not obvious and I would much rather have a direct check for that
condition instead of relying on inference subject to numerical stability issues.

(**) Turns out it doesn't: the issue repro still gets stuck, even with a
tolerance increased to 1%.

It's probably still a good idea to update the tolerance test (although I think
we can assert length >= distanceLine and skip fabs), but not as a replacement
for the split test. What do you think?

[f(malita), 2014/03/07 19:14:08]

Come to think of it, it's obvious this would not work as a fix: for very small
curve segments (length << 1) this is *increasing* the metric value and making us
try to split even further than before.

Case in point: splitting falls apart for [(786.879395,346.877930)
(786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]

because (346.877930f + 346.877899f) / 2 == 346.877930f.

We're hitting this numerical precision wall for an original metric value (length
- distanceLine(curve.start, curve.end)) of 0.000023. When switching to a metric
of fabs((length - distanceLine(curve.start, curve.end)) / length), we're going
to hit this at a much higher value: 0.254644 <- if anything, we've made things
(much) worse.

+            && curveStack.size() <= curveStackDepthLimit
+            && curve.split(leftCurve, rightCurve)) {
             curve = leftCurve;
             curveStack.append(rightCurve);
         } else {
             totalLength += length;
             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
                 traversalState.m_previous = curve.start;
                 traversalState.m_current = curve.end;
                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
                     return totalLength;
             }
@@ skipping 74 matching lines @@
         } else {
             m_normalAngle = rad2deg(slope);
         }
         m_success = true;
     }
     m_previous = m_current;
 }
 
 }