950549 - SVG path getTotalLength reports 0 for some cubic bezier segments

Status: RESOLVED FIXED

(Core :: SVG, defect)

Description

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: path-test.svg

In the attached test case the path has a single cubic bezier segment. The length of the segment reported by getTotalLength in Firefox 27 is 100.50668... but in Firefox 28 it is reported as 0.

Bug 934305 seems a likely culprit.

Comment 1

[Brian Birtles (:birtles, Feb 26~ parental leave)]

I started looking into this. The call stack looks like this:

>	gkmedias.dll!mozilla::gfx::FlattenBezier(const mozilla::gfx::BezierControlPoints & aControlPoints, mozilla::gfx::PathSink * aSink, float aTolerance) Line 493	C++
 	gkmedias.dll!mozilla::gfx::FlattenedPath::BezierTo(const mozilla::gfx::PointTyped<mozilla::gfx::UnknownUnits> & aCP1, const mozilla::gfx::PointTyped<mozilla::gfx::UnknownUnits> & aCP2, const mozilla::gfx::PointTyped<mozilla::gfx::UnknownUnits> & aCP3) Line 93	C++
 	gkmedias.dll!mozilla::gfx::StreamingGeometrySink::AddBeziers(const D2D1_BEZIER_SEGMENT * aSegments, unsigned int aCount) Line 140	C++
 	d2d1.dll!SandboxGeometrySink::AddBeziers(struct D2D1_BEZIER_SEGMENT const *,unsigned int)	Unknown
 	d2d1.dll!CFigureData::SendToD2DSinkInternal(struct ID2D1SimplifiedGeometrySink *,struct ID2D1GeometrySink *,enum D2D1_PATH_SEGMENT *)	Unknown
 	d2d1.dll!CShape::SendToD2DSinkInternal(struct ID2D1SimplifiedGeometrySink *,struct ID2D1GeometrySink *,class TMilRect_<float,struct D2D_RECT_F,struct MilPointAndSizeF,struct RectUniqueness::NotNeeded> const *)	Unknown
 	d2d1.dll!CShape::SendToD2DSink(struct ID2D1SimplifiedGeometrySink *,class TMilRect_<float,struct D2D_RECT_F,struct MilPointAndSizeF,struct RectUniqueness::NotNeeded> const *)	Unknown
 	d2d1.dll!CShapeBase::SendToD2DSink(struct ID2D1SimplifiedGeometrySink *,class MILMatrix3x2 const *,class TMilRect_<float,struct D2D_RECT_F,struct MilPointAndSizeF,struct RectUniqueness::NotNeeded> const *)	Unknown
 	d2d1.dll!D2DGeometry<struct ID2D1EllipseGeometry>::Simplify(enum D2D1_GEOMETRY_SIMPLIFICATION_OPTION,struct D2D_MATRIX_3X2_F const *,float,struct ID2D1SimplifiedGeometrySink *)	Unknown
 	d2d1debug1.dll!DebugGeometryGenerated<struct ID2D1EllipseGeometry>::Simplify(enum D2D1_GEOMETRY_SIMPLIFICATION_OPTION,struct D2D_MATRIX_3X2_F const *,float,struct ID2D1SimplifiedGeometrySink *)	Unknown
 	gkmedias.dll!ID2D1Geometry::Simplify(D2D1_GEOMETRY_SIMPLIFICATION_OPTION simplificationOption, const D2D_MATRIX_3X2_F & worldTransform, ID2D1SimplifiedGeometrySink * geometrySink) Line 2017	C++
 	gkmedias.dll!mozilla::gfx::PathD2D::StreamToSink(mozilla::gfx::PathSink * aSink) Line 367	C++
 	gkmedias.dll!mozilla::gfx::Path::EnsureFlattenedPath() Line 59	C++
 	gkmedias.dll!mozilla::gfx::Path::ComputeLength() Line 42	C++
 	xul.dll!mozilla::dom::SVGPathElement::GetTotalLength(mozilla::ErrorResult & rv) Line 70	C++
 	xul.dll!mozilla::dom::SVGPathElementBinding::getTotalLength(JSContext * cx, JS::Handle<JSObject *> obj, mozilla::dom::SVGPathElement * self, const JSJitMethodCallArgs & args) Line 55	C++


Inside FlattenBezier (http://mxr.mozilla.org/mozilla-central/source/gfx/2d/Path.cpp#398), for the test path in question, FindInflectionPoints returns t1 = 0, t2 = -1.#IND0000, count = 2.

Then we call FindInflectionApproximationRange for t1 and get t1min = -0.0449057780, t1max = 0.0449057780.

We don't call FindInflectionApproximationRange for t2 since it is < 0 so t2min = t2max = t2 = -1.#IND0000.

Inside the first block processing [t1min, t1max] none of the conditions match:
  if (t1min > 0) { /* t1min < 0 */
  if (t1max < 1.0 && (count == 1 || t2min > t1max)) { /* count == 2 */
  if (count > 1 && t2min < 1.0 && t2max > 0) { /* t2max < 0 */

The second block processing [t2min, t2max] is guarded by:
  if (count > 1 && t2min < 1.0 && t2max > 0) {
and since t2max < 0 we don't match there either

As a result we don't end up adding anything to the sink so when we finally go to compute the length of the path there is only a single move to path op.

Bas, what do you think the behaviour should be here?

One feature of the test path is that the first control point of the cubic bezier segment is coincident with the start point of the segment.

Comment 2

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Attachment: Possible patch

If I adjust FindInflectionPoints as in this patch I get close but not right.

Result of getTotalLength:
  Before regression: 100.50668
  Chrome: 100.50826
  IE: 100.50807
  With patch: 100.57024

Maybe I need to add a special branch for discriminant == 0 and return count = 1 but with the t2 point? I'll look into it further.

Comment 3

[Bas Schouten (:bas.schouten)]

(In reply to Brian Birtles (:birtles) from comment #2)
> Created attachment 8349794 [details] [diff] [review]
> Possible patch
> 
> If I adjust FindInflectionPoints as in this patch I get close but not right.
> 
> Result of getTotalLength:
>   Before regression: 100.50668
>   Chrome: 100.50826
>   IE: 100.50807
>   With patch: 100.57024
> 
> Maybe I need to add a special branch for discriminant == 0 and return count
> = 1 but with the t2 point? I'll look into it further.

Could you try with the patch in bug 941585?

Comment 4

[Bas Schouten (:bas.schouten)]

(In reply to Bas Schouten (:bas.schouten) from comment #3)
> (In reply to Brian Birtles (:birtles) from comment #2)
> > Created attachment 8349794 [details] [diff] [review]
> > Possible patch
> > 
> > If I adjust FindInflectionPoints as in this patch I get close but not right.
> > 
> > Result of getTotalLength:
> >   Before regression: 100.50668
> >   Chrome: 100.50826
> >   IE: 100.50807
> >   With patch: 100.57024
> > 
> > Maybe I need to add a special branch for discriminant == 0 and return count
> > = 1 but with the t2 point? I'll look into it further.
> 
> Could you try with the patch in bug 941585?

I doubt it'll work btw, but I just want to make sure.

Comment 5

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Bas Schouten (:bas.schouten) from comment #4)
> (In reply to Bas Schouten (:bas.schouten) from comment #3)
> > Could you try with the patch in bug 941585?
> 
> I doubt it'll work btw, but I just want to make sure.

It gives me a stack overflow. I pasted the call stack in bug 941585.

Comment 6

[Bas Schouten (:bas.schouten)]

Attachment: Correctly detect 1 inflection point where the discriminant is 0

This fixes an unneeded degeneracy when b == 0 and the discriminant is 0. It also correctly only detects a single inflection point when the discriminant is 0, and adjusts the flattening algorithm to deal with that correctly.

Comment 7

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8356128 [details] [diff] [review]
Correctly detect 1 inflection point where the discriminant is 0

Review of attachment 8356128 [details] [diff] [review]:
-----------------------------------------------------------------

Make sure to add a test case.

Comment 8

[Bas Schouten (:bas.schouten)]

Comment on attachment 8356128 [details] [diff] [review]
Correctly detect 1 inflection point where the discriminant is 0

This patch will be superceeded by a similar, but more complete patch I'll add to bug 941585.

Comment 9

[Logan Rosen [:Logan]]

The test case shows 100.49876 in the latest nightly build. Is this still a bug?

Comment 10

[Brian Birtles (:birtles, Feb 26~ parental leave)]

(In reply to Logan Rosen [:Logan] from comment #9)
> The test case shows 100.49876 in the latest nightly build. Is this still a
> bug?

That's probably close enough. In bug 941585 comment 15 it seems like we were getting 100.50825 at one point which seems much closer to other implementations (see comment 2). I guess the patch that got landed is somewhat less accurate for this case. The follow-up for that bug (see bug 941585 comment 28) may improve things but in any case, this is better than 0.

Comment 11

[Bas Schouten (:bas.schouten)]

(In reply to Brian Birtles (:birtles) from comment #10)
> (In reply to Logan Rosen [:Logan] from comment #9)
> > The test case shows 100.49876 in the latest nightly build. Is this still a
> > bug?
> 
> That's probably close enough. In bug 941585 comment 15 it seems like we were
> getting 100.50825 at one point which seems much closer to other
> implementations (see comment 2). I guess the patch that got landed is
> somewhat less accurate for this case. The follow-up for that bug (see bug
> 941585 comment 28) may improve things but in any case, this is better than 0.

Yes, it's hard to tell, in any case, it's really hard to tell, the other algorithms are probably all doing adaptive subdivision, in other words, their approximations probably have 'similar' sorts of inaccuracies. Our algorithm is totally different, and its inaccuracy is going to be different, not necessarily worse.

Comment 12

[Bas Schouten (:bas.schouten)]

Actually, 100.49876 seems like it must be an underapproximation. Since a simple line from 0 to 100,10 would be exactly 100.49876. I should look into this a little bit when I have some time, it's not really a big problem but it should be understood.

Comment 13

[Lukas Blakk [:lsblakk] use ?needinfo]

What's the user impact of this bug?  Comment 12 makes it sound like this might not be worth tracking any longer - clarification appreciated.

Comment 14

[Lukas Blakk [:lsblakk] use ?needinfo]

I can only surmise that the lack of activity here suggests low user impact and low priority.  If this is fixed in the future please go ahead and nominate for branch uplift if low risk.

Comment 15

[Brian Birtles (:birtles, Feb 26~ parental leave)]

Yes I think based on comment 10 and comment 11 this is more-or-less fixed by bug 941585. But I'm not marking it as a dupe just yet since I think Bas wanted to look into this more (comment 12).

Comment 16

[Bas Schouten (:bas.schouten)]

(In reply to Lukas Blakk [:lsblakk] from comment #13)
> What's the user impact of this bug?  Comment 12 makes it sound like this
> might not be worth tracking any longer - clarification appreciated.

Sorry, this is not worth tracking at all, we only left this open to investigate a tiny inconsistency which is unlikely to have any user impact.

Comment 17

[Ben]

(In reply to Bas Schouten (:bas.schouten) from comment #16)
> (In reply to Lukas Blakk [:lsblakk] from comment #13)
> > What's the user impact of this bug?  Comment 12 makes it sound like this
> > might not be worth tracking any longer - clarification appreciated.
> 
> Sorry, this is not worth tracking at all, we only left this open to
> investigate a tiny inconsistency which is unlikely to have any user impact.

This issue still occurs in nightly build: 31.0a1 (2014-04-02)
---------
<svg xmlns="http://www.w3.org/2000/svg" version="1.1" width="1250" height="1050">
<desc>Created with Raphaël</desc>
<defs></defs>
<path fill="none" stroke="#6a6a6a" d="M1005,319S1017,349,1008,374" style="stroke-linecap: square; stroke-width: 4;" stroke-linecap="square" stroke-width="4" stroke-opacity="0.9" stroke-dasharray="8,8"></path>
</svg>
---------
var path = $("svg path").get(0);
path.getTotalLength();
> 0.014904205687344074

Comment 18

[Marcus S.]

Today a customer reported missing elements on a SVG canvas on a productive system and I was shocked when I realized something went wrong with Firefox. I was struggling with the bounding box for some hours to realize that it seems to be this bug, in the end.

Version: 32.0.1

Testcase:
<head>
</head>
<body>
<div>
  <svg width="300" height="300">
    <path d="M 0 0 C 12.5 0 37.5 0 50 0 C 62.5 0 87.5 0 100 0" id="path1"/>
    <path d="M 0 0 L 12.5 0 37.5 0 50 0 L 62.5 0 87.5 0 100 0" id="path2"/>
  </svg>
</div>

<script>
var n = 2, i, path;
for (i = 1; i <= n; i++) {
  path = document.getElementById('path' + i);
  if (path) {
    console.log('path' + i, path);
    console.log('path' + i + '.length', path.getTotalLength());
  }
}
</script>
</body>
</html>

Result:
path1 <path id="path1" d="M 0 0 C 12.5 0 37.5 0 50 0 C 62.5 0 87.5 0 100 0">
path1.length 0
path2 <path id="path2" d="M 0 0 L 12.5 0 37.5 0 50 0 L 62.5 0 87.5 0 100 0">
path2.length 100

Comment 19

[Marcus S.]

Oh I am sorry, I just realized that this bug is slightly different and more or less solved, I will open a separate one.

Comment 20

[Robert Longson [:longsonr]]

less confusing to mark this fixed since it the testcase no longer reports 0.