Improve the reliability and accuracy of SVG getTotalLength

Improve the reliability and accuracy of SVG getTotalLength

The existing code for SVG path.getTotalLength had two problems when
subdividing curves to estimate length. The subdivision terminated when
the straight-line vs curved length was within a fixed limit, regardless
of the scale of the curve. The termination condition for infinite loops
also failed to stop on infinite loops.

This patch fixes both issues. The subdivision threshold now accounts for
the magnitude of the values, so that we give more resolution on very small
curves and less on very large curves. This is consistent with the actual
precision we have in floating point numbers. The infinite loop termination
tracks and examines the total number of subdivisions thus far, terminating
after 20 (which is more than enough - most curves do no more than 10
subdivisions).

We also remove two unused variables and a FIXME that makes little sense and that we won't ever fix.

R=fmalita@chromium.org, pdr@chromium.org, fs@opera.com
BUG=349873
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=172519

[f(malita), 2014-04-10 20:09:06]

I can buy an argument for adjusting the precision dynamically based on
magnitude, but I'm not sure how the current heuristic guarantees that split()
stays within a safe FP domain. I still think we should check that the loop is
actually making progress, as a depth-20 limit is quite large (see below).

Quick experiment: instrument curveLength() to dump the number of iteration
needed to complete, open http://crbug.com/349873 's svg-test.html and compare
this approach vs. https://codereview.chromium.org/190943002 (first 30 entries
only):

    1        1
    1        1
 8937      151
 2309       87
19115      163
22925      215
 3887       57
  447       29
  367       27
  353       39
  753       31
  817       53
  217       27
10493       85
10277       83
  633       39
  447       17
 3883       67
 5025       93
39809      143
32999      137
 7057       83
 1009       21
  835       21
 2921       73
31015      141
    1        1
33025      139
33965      137
32373      137

I'm guessing this is due to increased precision? Not sure the perf hit is
worth/acceptable though.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:50: return
((double)(start.dot(start)) + (double)(control.dot(control)) +
(double)(end.dot(end))) / 9.0;
X.dot(X) -> X.lengthSquared()?

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy *
lengthDiscrepancy) / curveScaleForToleranceSquared >
pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
Hmm, this doesn't quite match the description: we're not terminating after 20
subdivisions, we just don't divide beyond depth 20. In the worst theoretical
case, 2^20 is a lot of splits.

[fs, 2014-04-11 10:29:17]

The >30k entries in the measurements Florin did has me kind of worried...

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:50: return
((double)(start.dot(start)) + (double)(control.dot(control)) +
(double)(end.dot(end))) / 9.0;
Why do you want the distance from the origin rather than, say, the the distance
from P0 (start)? (Or put differently: why is the position of the curve of
interest?)

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:136: static const double
pathSegmentLengthToleranceSquared = 1.e-20;
Why "bump" (reduce) this down to 1e-20 (rather than, say, 1e-10). There's still
mostly floats involved here after all.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy *
lengthDiscrepancy) / curveScaleForToleranceSquared >
pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
On 2014/04/10 20:09:06, Florin Malita wrote:
> Hmm, this doesn't quite match the description: we're not terminating after 20
> subdivisions, we just don't divide beyond depth 20. In the worst theoretical
> case, 2^20 is a lot of splits.

No different from before though? I wonder if the new splitDepth is really needed
(as opposed to checking the stack-depth as previously.)

[f(malita), 2014-04-11 13:22:48]

On 2014/04/11 10:29:17, fs wrote:
>
https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
> Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy *
> lengthDiscrepancy) / curveScaleForToleranceSquared >
> pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit)
{
> On 2014/04/10 20:09:06, Florin Malita wrote:
> > Hmm, this doesn't quite match the description: we're not terminating after
20
> > subdivisions, we just don't divide beyond depth 20. In the worst theoretical
> > case, 2^20 is a lot of splits.
> 
> No different from before though?
Yeah, that's why I suspect the larger iteration numbers are due to increased
precision and not necessarily the depth limit.

> I wonder if the new splitDepth is really needed
> (as opposed to checking the stack-depth as previously.)

The problem with just checking the stack size is that it doesn't guarantee
progress: we can get into a state where split([oldCurve]) ->
[zeroCurve],[oldCurve] due to FP precision, which can then oscillate on the
stack indefinitely. splitDepth is always incremented on split(), so progress is
guaranteed.

[Stephen Chennney, 2014-04-11 13:48:02]

Also, regarding the extra iterations. It is probably a combination of the extra
precision and the change to stack depth monitoring. In the old code, the
potential stack depth varied for the left and right branches of the split, I
think. More experiments required.

Ultimately, what we have now is wrong in two ways. We can argue about tolerances
and max recursion depth, but I do want to land something like this.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:50: return
((double)(start.dot(start)) + (double)(control.dot(control)) +
(double)(end.dot(end))) / 9.0;
On 2014/04/10 20:09:06, Florin Malita wrote:
> X.dot(X) -> X.lengthSquared()?

Forgot that existed, which is sad since I touched it a week ago.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:50: return
((double)(start.dot(start)) + (double)(control.dot(control)) +
(double)(end.dot(end))) / 9.0;
On 2014/04/11 10:29:18, fs wrote:
> Why do you want the distance from the origin rather than, say, the the
distance
> from P0 (start)? (Or put differently: why is the position of the curve of
> interest?)

Because we want an estimate of the magnitude of the numbers so we know how much
precision we can possibly have in the float. The distance from p0 would give us
the approximate curve length, which is the same for short curves near the origin
and short curves near infinity.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:136: static const double
pathSegmentLengthToleranceSquared = 1.e-20;
On 2014/04/11 10:29:18, fs wrote:
> Why "bump" (reduce) this down to 1e-20 (rather than, say, 1e-10). There's
still
> mostly floats involved here after all.

Because I'm willing to go for 10 decimal digits of precision, which means 20 in
the squared values. I should probably just use 10-16, as Wikipedia claims 7.2
decimal digits of precision in a float.

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy *
lengthDiscrepancy) / curveScaleForToleranceSquared >
pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
On 2014/04/11 10:29:18, fs wrote:
> On 2014/04/10 20:09:06, Florin Malita wrote:
> > Hmm, this doesn't quite match the description: we're not terminating after
20
> > subdivisions, we just don't divide beyond depth 20. In the worst theoretical
> > case, 2^20 is a lot of splits.
> 
> No different from before though? I wonder if the new splitDepth is really
needed
> (as opposed to checking the stack-depth as previously.)

Yes, we could theoretically do 2^20 splits, but I don't think it is possible for
a quadratic or cubic curve to have that much curvature over its entire length.
The only way to get high curvature is with some control points very close and
others far away, resulting in high curvature near the close points. But with
only 3 or 4 controls, the scope to do that is limited and the best you can do is
a curve with really high curvature in one or two little parts and almost
entirely flat elsewhere.

Still, 20 may also be overkill. 10 is probably enough.

fs@, the code has an else clause if the limit is reached, which removes the last
thing on the stack, freeing up a spot for the next iteration to split again. It
was incorrectly written originally. My guess is actually that someone tried to
fix this before and screwed it up.

[fs, 2014-04-11 14:49:11]

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
File Source/platform/graphics/PathTraversalState.cpp (right):

https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy *
lengthDiscrepancy) / curveScaleForToleranceSquared >
pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
On 2014/04/11 13:48:02, Stephen Chenney wrote:
...
> fs@, the code has an else clause if the limit is reached, which removes the
last
> thing on the stack, freeing up a spot for the next iteration to split again.
It
> was incorrectly written originally. My guess is actually that someone tried to
> fix this before and screwed it up.

Yeah, I did notice the else-clause =). I guess I find this "top always popped"
structure a bit confusing, and would rather have structure like:

stack.push(initialCurve)
while (!stack.empty()) {
  curve = stack.pop();
  if (need_split(curve)) {
    ...
  else {
    ...
  }
}

[fs, 2014-04-11 14:53:00]

On 2014/04/11 13:22:48, Florin Malita wrote:
> On 2014/04/11 10:29:17, fs wrote:
> >
>
https://codereview.chromium.org/233063003/diff/1/Source/platform/graphics/Pat...
> > Source/platform/graphics/PathTraversalState.cpp:147: if ((lengthDiscrepancy
*
> > lengthDiscrepancy) / curveScaleForToleranceSquared >
> > pathSegmentLengthToleranceSquared && curve.splitDepth <
curveSplitDepthLimit)
> {
> > On 2014/04/10 20:09:06, Florin Malita wrote:
> > > Hmm, this doesn't quite match the description: we're not terminating after
> 20
> > > subdivisions, we just don't divide beyond depth 20. In the worst
theoretical
> > > case, 2^20 is a lot of splits.
> > 
> > No different from before though?
> Yeah, that's why I suspect the larger iteration numbers are due to increased
> precision and not necessarily the depth limit.
> 
> > I wonder if the new splitDepth is really needed
> > (as opposed to checking the stack-depth as previously.)
> 
> The problem with just checking the stack size is that it doesn't guarantee
> progress: we can get into a state where split([oldCurve]) ->
> [zeroCurve],[oldCurve] due to FP precision, which can then oscillate on the
> stack indefinitely. splitDepth is always incremented on split(), so progress
is
> guaranteed.

I guess I just don't like "wasting" 4-8 more bytes for an 8-bit counter ;-) (But
the stack is already bloated by storing one point too much per segment so...)

[Stephen Chennney, 2014-04-11 15:28:02]

OK, this version resolves the complaints, I think.

I reduced the tolerance to 10e-16, which leads to iteration counts similar to
the original ones Florin posted. It turns out that the stack-depth limitation
alone (leaving the original distance metric) does not change the iteration count
(but does prevent the infinite loop).

I also fixed a potential divide by zero.

And I removed two unused variables.

[Stephen Chennney, 2014-04-16 14:48:43]

Bump.

[f(malita), 2014-04-24 15:45:42]

lgtm

[Stephen Chennney, 2014-04-24 15:49:28]

The CQ bit was checked by schenney@chromium.org

[commit-bot: I haz the power, 2014-04-24 15:49:46]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/schenney@chromium.org/233063003/20001

[commit-bot: I haz the power, 2014-04-24 16:51:10]

Change committed as 172519