935049 - Implement ComputeLength and ComputePointAtLength on all Moz2D backends

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Bas Schouten (:bas.schouten)]

For SVG we need ComputeLength and ComputePointAtLength to work on all Moz2D backends.

Comment 1

[Bas Schouten (:bas.schouten)]

Attachment: Part 2: Add ComputeLength and ComputePointAtLength implementations for Direct2D.

Comment 2

[Milan Sreckovic [:milan] (needinfo for best results)]

Do we ever have to worry about getting point at length when there is a non-identity transformation?

Comment 3

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionality

I'll likely be making some small tweaks here and there, but this is the generic approach I'm suggesting we take.

Comment 4

[Bas Schouten (:bas.schouten)]

(In reply to Milan Sreckovic [:milan] from comment #2)
> Do we ever have to worry about getting point at length when there is a
> non-identity transformation?

We can support that by simply transforming the whole path, we could also add an API for it when we find out it's needed? But since our current code didn't support it I believe Matt decided to not add that option in the new API.

Comment 5

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 827843 [details] [diff] [review]
Part 3: Add generic ComputeLength code for backends with no such functionality

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

::: 2D.h
@@ +474,5 @@
> +protected:
> +  Path();
> +  void EnsureFlattenedPath();
> +
> +  RefPtr<FlattenedPath> mFlattenedPath;

It's sort of crappy that we have to hang the FlattenedPath off of the Path. Wouldn't it be better to just allow consumers to get a FlattenedPath?

::: Path.cpp
@@ +85,5 @@
> +{
> +  // We need to elevate the degree of this quadratic Bézier to cubic, so we're
> +  // going to add an intermediate control point, and recompute control point 1.
> +  // The first and last control points remain the same.
> +  // This formula can be found on http://fontforge.sourceforge.net/bezier.html

It's sort of dumb to lift Quadratics up to Cubics only to have approximate them later on during flattening.

@@ +140,5 @@
> +      Float segmentLength = Distance(currentPoint, mPathOps[i].mPoint);
> +
> +      if (segmentLength > aLength) {
> +        Point currentVector = mPathOps[i].mPoint - currentPoint;
> +        *aTangent = currentVector / hypotf(currentVector.x, currentVector.y);

/ sgementLength?

@@ +158,5 @@
> +                     const Point &aCP3, const Point &aCP4,
> +                     Point *aPrevCP2, Point *aPrevCP3,
> +                     Point *aNextCP1, Point *aNextCP2,
> +                     Point *aNextCP3,
> +                     Float t)

SplitBezier()? Doesn't seem to be much searching.

@@ +190,5 @@
> +{
> +  /* The algorithm implemented here is based on:
> +   * http://cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf
> +   *
> +   * The basic premesis is that for a small t the third order term in the

premise

@@ +193,5 @@
> +   *
> +   * The basic premesis 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 me much more easily determined.

s/me/be/

@@ +231,5 @@
> +
> +void
> +FlattenBezier(const Point &aCP1, const Point &aCP2,
> +              const Point &aCP3, const Point &aCP4,
> +              PathSink *aSink, Float aTolerance)

I'd suggest having a knot_t/curve_t style type instead of passing around the points separately. It will make the bottom of this function more clear.

@@ +233,5 @@
> +FlattenBezier(const Point &aCP1, const Point &aCP2,
> +              const Point &aCP3, const Point &aCP4,
> +              PathSink *aSink, Float aTolerance)
> +{
> +  // Find inflection points.

I think it would be good to move finding the inflection points into a separate function. It would also be nice if you copied all of my comments from http://cgit.freedesktop.org/~jrmuizel/cairo/commit/?h=stroke-to-path2 in.

@@ +296,5 @@
> +    Point cp41 = aCP4 - nextCP1;
> +
> +    Float s4 = (cp41.x * cp21.y -
> +                cp41.y * cp21.x) /
> +                sqrt(cp21.x * cp21.x + cp21.y * cp21.y);

hypot?

@@ +298,5 @@
> +    Float s4 = (cp41.x * cp21.y -
> +                cp41.y * cp21.x) /
> +                sqrt(cp21.x * cp21.x + cp21.y * cp21.y);
> +
> +    Float tf = pow(abs(aTolerance / s4), Float(1. / 3.));

cbrtf()?

@@ +302,5 @@
> +    Float tf = pow(abs(aTolerance / s4), Float(1. / 3.));
> +
> +    t2min = t2 - tf * (1 - t2);
> +    t2max = t2 + tf * (1 - t2);
> +  }

Can this be a function? Do you really need to duplicate all of the code below or can we operate on side of the inflection

@@ +358,5 @@
> +      FlattenBezierCurveSegment(cp1, prevCP2, prevCP3, nextCP1, aSink, aTolerance);
> +    } else {
> +      FindBezierSubSegment(aCP1, aCP2, aCP3, aCP4, &prevCP2, &prevCP3,
> +                           &nextCP1, &nextCP2, &nextCP3, t2min);
> +      FlattenBezierCurveSegment(aCP1, prevCP2, prevCP3, nextCP1, aSink, aTolerance);

I think this section of the code could use a little bit more documentation on what's going on, as it is not obvious to me.

::: PathAnalysis.h
@@ +44,5 @@
> +  Float ComputeLength();
> +  Point ComputePointAtLength(Float aLength, Point *aTangent);
> +
> +private:
> +  Float mCachedLength;

The length isn't invalidated if you call LineTo() etc. after computing the length.

Comment 6

[Bas Schouten (:bas.schouten)]

(In reply to Jeff Muizelaar [:jrmuizel] from comment #5)
> Comment on attachment 827843 [details] [diff] [review]
> Part 3: Add generic ComputeLength code for backends with no such
> functionality
> 
> Review of attachment 827843 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: 2D.h
> @@ +474,5 @@
> > +protected:
> > +  Path();
> > +  void EnsureFlattenedPath();
> > +
> > +  RefPtr<FlattenedPath> mFlattenedPath;
> 
> It's sort of crappy that we have to hang the FlattenedPath off of the Path.
> Wouldn't it be better to just allow consumers to get a FlattenedPath?

No, I don't think so, the fact we're using a flattened path is an implementation detail. I'm hoping longer term we can do something better at some point in the future, we don't want the users to bother with what we implement this like. More importantly since for example D2D flattens anyway, users can now just use ComputeLength and get a faster codepath when backends support this functionality avoiding additional, needless overhead.

> ::: Path.cpp
> @@ +85,5 @@
> > +{
> > +  // We need to elevate the degree of this quadratic Bézier to cubic, so we're
> > +  // going to add an intermediate control point, and recompute control point 1.
> > +  // The first and last control points remain the same.
> > +  // This formula can be found on http://fontforge.sourceforge.net/bezier.html
> 
> It's sort of dumb to lift Quadratics up to Cubics only to have approximate
> them later on during flattening.

It is sort of dumb :) But it also sames code complexity.

> 
> @@ +140,5 @@
> > +      Float segmentLength = Distance(currentPoint, mPathOps[i].mPoint);
> > +
> > +      if (segmentLength > aLength) {
> > +        Point currentVector = mPathOps[i].mPoint - currentPoint;
> > +        *aTangent = currentVector / hypotf(currentVector.x, currentVector.y);
> 
> / sgementLength?

Sounds good I guess :)

> 
> @@ +158,5 @@
> > +                     const Point &aCP3, const Point &aCP4,
> > +                     Point *aPrevCP2, Point *aPrevCP3,
> > +                     Point *aNextCP1, Point *aNextCP2,
> > +                     Point *aNextCP3,
> > +                     Float t)
> 
> SplitBezier()? Doesn't seem to be much searching.

Sure.

> @@ +231,5 @@
> > +
> > +void
> > +FlattenBezier(const Point &aCP1, const Point &aCP2,
> > +              const Point &aCP3, const Point &aCP4,
> > +              PathSink *aSink, Float aTolerance)
> 
> I'd suggest having a knot_t/curve_t style type instead of passing around the
> points separately. It will make the bottom of this function more clear.

I guess, I don't feel strongly either way so I'll do that.

> @@ +233,5 @@
> > +FlattenBezier(const Point &aCP1, const Point &aCP2,
> > +              const Point &aCP3, const Point &aCP4,
> > +              PathSink *aSink, Float aTolerance)
> > +{
> > +  // Find inflection points.
> 
> I think it would be good to move finding the inflection points into a
> separate function. It would also be nice if you copied all of my comments
> from http://cgit.freedesktop.org/~jrmuizel/cairo/commit/?h=stroke-to-path2
> in.

I personally didn't find them very helpful when trying to understand your code. Not that there was anything necessarily wrong with them, plain text just isn't very well suited for doing math. I found using the link a lot more helpful. To be honest the additional info referring to Hain et al. even confused me because I was wondering why the details were in there :).

> @@ +296,5 @@
> > +    Point cp41 = aCP4 - nextCP1;
> > +
> > +    Float s4 = (cp41.x * cp21.y -
> > +                cp41.y * cp21.x) /
> > +                sqrt(cp21.x * cp21.x + cp21.y * cp21.y);
> 
> hypot?

Good one.

> @@ +298,5 @@
> > +    Float s4 = (cp41.x * cp21.y -
> > +                cp41.y * cp21.x) /
> > +                sqrt(cp21.x * cp21.x + cp21.y * cp21.y);
> > +
> > +    Float tf = pow(abs(aTolerance / s4), Float(1. / 3.));
> 
> cbrtf()?

Good idea! Didn't even know that existed :).
> 
> @@ +302,5 @@
> > +    Float tf = pow(abs(aTolerance / s4), Float(1. / 3.));
> > +
> > +    t2min = t2 - tf * (1 - t2);
> > +    t2max = t2 + tf * (1 - t2);
> > +  }
> 
> Can this be a function? Do you really need to duplicate all of the code
> below or can we operate on side of the inflection

Not sure what the second part here means, but moving it into a function I can do! :)

> @@ +358,5 @@
> > +      FlattenBezierCurveSegment(cp1, prevCP2, prevCP3, nextCP1, aSink, aTolerance);
> > +    } else {
> > +      FindBezierSubSegment(aCP1, aCP2, aCP3, aCP4, &prevCP2, &prevCP3,
> > +                           &nextCP1, &nextCP2, &nextCP3, t2min);
> > +      FlattenBezierCurveSegment(aCP1, prevCP2, prevCP3, nextCP1, aSink, aTolerance);
> 
> I think this section of the code could use a little bit more documentation
> on what's going on, as it is not obvious to me.

I can imagine, will fix.

> ::: PathAnalysis.h
> @@ +44,5 @@
> > +  Float ComputeLength();
> > +  Point ComputePointAtLength(Float aLength, Point *aTangent);
> > +
> > +private:
> > +  Float mCachedLength;
> 
> The length isn't invalidated if you call LineTo() etc. after computing the
> length.

This should never happen, I'll add asserts for this in all the Path op functions.

Comment 7

[Jeff Muizelaar [:jrmuizel]]

(In reply to Bas Schouten (:bas.schouten) from comment #6)
> (In reply to Jeff Muizelaar [:jrmuizel] from comment #5)
> No, I don't think so, the fact we're using a flattened path is an
> implementation detail. I'm hoping longer term we can do something better at
> some point in the future, we don't want the users to bother with what we
> implement this like. More importantly since for example D2D flattens anyway,
> users can now just use ComputeLength and get a faster codepath when backends
> support this functionality avoiding additional, needless overhead.

Ok.

> 
> > ::: Path.cpp
> > @@ +85,5 @@
> > > +{
> > > +  // We need to elevate the degree of this quadratic Bézier to cubic, so we're
> > > +  // going to add an intermediate control point, and recompute control point 1.
> > > +  // The first and last control points remain the same.
> > > +  // This formula can be found on http://fontforge.sourceforge.net/bezier.html
> > 
> > It's sort of dumb to lift Quadratics up to Cubics only to have approximate
> > them later on during flattening.
> 
> It is sort of dumb :) But it also sames code complexity.

Maybe add a comment that it's intentional.

> > 
> > @@ +158,5 @@
> > > +                     const Point &aCP3, const Point &aCP4,
> > > +                     Point *aPrevCP2, Point *aPrevCP3,
> > > +                     Point *aNextCP1, Point *aNextCP2,
> > > +                     Point *aNextCP3,
> > > +                     Float t)
> > 
> > SplitBezier()? Doesn't seem to be much searching.
> 
> Sure.

SplitBezierAt() is probably even better.

> 
> > @@ +231,5 @@
> > > +
> > > +void
> > > +FlattenBezier(const Point &aCP1, const Point &aCP2,
> > > +              const Point &aCP3, const Point &aCP4,
> > > +              PathSink *aSink, Float aTolerance)
> > 
> > I'd suggest having a knot_t/curve_t style type instead of passing around the
> > points separately. It will make the bottom of this function more clear.
> 
> I guess, I don't feel strongly either way so I'll do that.
> 
> > @@ +233,5 @@
> > > +FlattenBezier(const Point &aCP1, const Point &aCP2,
> > > +              const Point &aCP3, const Point &aCP4,
> > > +              PathSink *aSink, Float aTolerance)
> > > +{
> > > +  // Find inflection points.
> > 
> > I think it would be good to move finding the inflection points into a
> > separate function. It would also be nice if you copied all of my comments
> > from http://cgit.freedesktop.org/~jrmuizel/cairo/commit/?h=stroke-to-path2
> > in.
> 
> I personally didn't find them very helpful when trying to understand your
> code. Not that there was anything necessarily wrong with them, plain text
> just isn't very well suited for doing math. I found using the link a lot
> more helpful. To be honest the additional info referring to Hain et al. even
> confused me because I was wondering why the details were in there :).

While they are not useful for understanding the code, they are helpful for understanding why a particular implementation was chosen over others.

> > Can this be a function? Do you really need to duplicate all of the code
> > below or can we operate on side of the inflection
> 
> Not sure what the second part here means, but moving it into a function I
> can do! :)

I'm not sure but it seems like you're doing the same thing for both sides of the inflection points. If you can move that all into a separate function that is called twice, that would be nice.

This is sort of an example of what I mean:
http://cgit.freedesktop.org/~jrmuizel/cairo/tree/src/cairo-spline-offset.c?h=stroke-to-path2#n820

Comment 8

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionalityadd-compute-length

Quite some changes here so re-requesting review.

Comment 9

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionality

Correct patch this time.

Comment 10

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 829040 [details] [diff] [review]
Part 3: Add generic ComputeLength code for backends with no such functionality

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

::: Path.cpp
@@ +18,5 @@
> +    : mCP1(aCP1), mCP2(aCP2), mCP3(aCP3), mCP4(aCP4)
> +  {
> +  }
> +
> +  Point mCP1, mCP2, mCP3, mCP4;

I prefer struct members to not have 'm' in them like Size.width/height

Comment 11

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionality v3

Some bugfixes, carrying r+.

Comment 12

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionality v4

This fixes some more degeneracies I discovered. Small changes, carrying r+.

Comment 13

[Bas Schouten (:bas.schouten)]

Attachment: Part 4: Add Moz2D unittests for path measuring functionality

This covers all the degeneracies we found and I could come up with. What do you think Matt?

Comment 14

[Bas Schouten (:bas.schouten)]

So, there's a little oddity in the current behavior of our tangent computation code. When it hits a discontinuity at the moment (i.e. a joint between two segments), it will return the tangent of the former segment rather than the tangent of the next segment. There's tests we have that rely on this behavior to pass, however we've been unable to find anything about this in the spec, and I personally believe this behavior is wrong, for two major reasons:

1. Segments more or less run from <segmentStart, segmentEnd]. I.e. if you have MoveTo(0, 0) LineTo(10, 0) LineTo(10, 10), at distance ten, we're conceptually at the start of the second line, not the end of the first. This also makes for more consistency, i.e. right now if we have a clockwise rectangle, at the top left corner we get the tangent of the top line (since at 0 length there's nothing before it), at the top right corner we get the tangent of the top line as well (since at distance 10 it takes the tangent of the previous segment), the bottom right corner we get the tangent of the line on the right, and the bottom left the line at the bottom. This means '0' becomes sort of unique here, this is very counter-intuitive.
2. In general it's more intuitive to think of the tangent as how to go 'forward' not how we arrived at the current position. I.e. in the case of the rectangle at the top right, we're going to go down next, it's very odd to get your 'past direction' as your tangent here.

I'd like to know if you guys are okay with us changing these tests and implementing the new behavior. Where we'd always take the 'right-hand' side of a discontinuity.

Comment 15

[Jonathan Watt [:jwatt]]

Brian, is there any spec requirement that you know of? (See comment 14, which is regarding animateMotion tests, I believe.)

Comment 16

[Jonathan Watt [:jwatt]]

Try push with failures: https://tbpl.mozilla.org/?tree=Try&rev=88736cebe2d1

Comment 17

[Jonathan Watt [:jwatt]]

Attachment: testcase for animateMotion mpath discontinuity

Currently Firefox, Chrome and Opera all agree that the tangent at a discontinuity in an mpath is the tangent at the end of the previous segment, not the tangent at the start of the next segment. Maybe someone can test IE?

I'm not sure that this really matters all that much, but I'd like Brian's opinion before we decide to change behavior since he's really the expert on this.

Comment 18

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Jonathan Watt [:jwatt] from comment #17)
> Maybe someone can test IE?

IE11 on Windows 7 doesn't display the testcase correctly. Instead of showing the arrow pointing out of the line, it's sitting in the top left corner of the page.

Comment 19

[Jonathan Watt [:jwatt]]

Oh, right. No SMIL animation support, I forgot. Thanks, Emanuel.

Bas says that D2D chooses the tangent at the start of the next segment, so it'd also be interesting to know what the behavior of Chrome and Opera on Windows is.

Comment 20

[Brian Birtles (:birtles)]

(In reply to Jonathan Watt [:jwatt] from comment #15)
> Brian, is there any spec requirement that you know of? (See comment 14,
> which is regarding animateMotion tests, I believe.)

Sorry, I'm afraid Daniel did the animateMotion implementation so he would know best.

Daniel, do you recall any specific requirements here?

Comment 21

[Emanuel Hoogeveen [:ehoogeveen]]

(In reply to Jonathan Watt [:jwatt] from comment #19)
> Bas says that D2D chooses the tangent at the start of the next segment, so
> it'd also be interesting to know what the behavior of Chrome and Opera on
> Windows is.

In Chrome 31, with all the hardware acceleration flags enabled, the testcase looks the same as in Firefox. I don't know if the testcase was actually rendered using D2D though (flags or no flags).

Comment 22

[Brian Birtles (:birtles)]

(In reply to Bas Schouten (:bas.schouten) from comment #14)
> 1. Segments more or less run from <segmentStart, segmentEnd]. I.e. if you
> have MoveTo(0, 0) LineTo(10, 0) LineTo(10, 10), at distance ten, we're
> conceptually at the start of the second line, not the end of the first. This
> also makes for more consistency, i.e. right now if we have a clockwise
> rectangle, at the top left corner we get the tangent of the top line (since
> at 0 length there's nothing before it), at the top right corner we get the
> tangent of the top line as well (since at distance 10 it takes the tangent
> of the previous segment), the bottom right corner we get the tangent of the
> line on the right, and the bottom left the line at the bottom. This means
> '0' becomes sort of unique here, this is very counter-intuitive.

I agree with this reasoning. In animation (both SVG and CSS going forward) we use endpoint-exclusive timing which means that when you arrive right on the boundary of two intervals you treat it as if the first interval has finished and you are at the start of the second.

As jwatt pointed out in IRC, the current text for Web Animations (which is still quite draft in this section) agrees with this too:

  "At non-smooth junction points, the angle of the tangent vector for the purpose of these calculations is determined by the tangent to the curve after the junction."
http://dev.w3.org/fxtf/web-animations/#calculating-the-rotation-value-of-a-path-animation-effect

Comment 23

[Cameron McCormack (:heycam)]

For the placement of SVG markers, and I guess for the orientation of <animateMotion orient="auto"> animations, I thought it was the case that the orientation of the path at the discontinuous point took the preceding orientation, if there was one, and the following orientation, if there wasn't a preceding one, and 0deg otherwise.  And that if there were a series of a zero length path segments, then it would look beyond those to find an orientation.  Also, if the discontinuity was between two normal line segments, and not between two zero length segments, then it would use the average of the incoming and outgoing segments to orient the marker.

This may or may not be exactly clear from:

  http://svgwg.org/svg2-draft/painting.html#OrientAttribute and
  http://svgwg.org/svg2-draft/implnote.html#PathElementImplementationNotes

If you want this behaviour to change in SVG, it would be good to see what implementations currently do.

Comment 24

[Jonathan Watt [:jwatt]]

(In reply to Cameron McCormack (:heycam) from comment #23)
> For the placement of SVG markers

Markers are different since the spec requires us to orient them with the "angle bisector":

http://www.w3.org/TR/SVG11/painting.html#MarkerElement

We have to handle that specially using GetMarkerPositioningData rather than using platform libs, so we don't need to worry about markers here.

> and I guess for the orientation of <animateMotion orient="auto"> animations

The only spec text I've seen for the animateMotion case is linked in comment 22.

>   http://svgwg.org/svg2-draft/painting.html#OrientAttribute and
>   http://svgwg.org/svg2-draft/implnote.html#PathElementImplementationNotes

These links relate to markers, and we're only concerned with animateMotion with an mpath here.

> If you want this behaviour to change in SVG, it would be good to
> see what implementations currently do.

The only time anyone is ever going to notice any difference is when an animation is paused /exactly/ at the point in time that the position of an object being animated using an <animateMotion orient="auto"> with an <mpath> coincides at the point between two /discontinuous/ segments of the motion path. So I doubt very much that we need to care.

Like Brian, I totally agree with Bas' point #1 in comment 14.

Comment 25

[Bas Schouten (:bas.schouten)]

(In reply to Cameron McCormack (:heycam) from comment #23)
> For the placement of SVG markers, and I guess for the orientation of
> <animateMotion orient="auto"> animations, I thought it was the case that the
> orientation of the path at the discontinuous point took the preceding
> orientation, if there was one, and the following orientation, if there
> wasn't a preceding one, and 0deg otherwise.  And that if there were a series
> of a zero length path segments, then it would look beyond those to find an
> orientation.  Also, if the discontinuity was between two normal line
> segments, and not between two zero length segments, then it would use the
> average of the incoming and outgoing segments to orient the marker.
> 
> This may or may not be exactly clear from:
> 
>   http://svgwg.org/svg2-draft/painting.html#OrientAttribute and
>   http://svgwg.org/svg2-draft/implnote.html#PathElementImplementationNotes
> 
> If you want this behaviour to change in SVG, it would be good to see what
> implementations currently do.

I don't read this in here. Because this is for markers, this only speaks about the end point and start point behavior of a segment. The thing is that here, the discussion is whether in a MoveTo(0, 0) LineTo(10, 0) LineTo(10, 10) the point at distance 10 is the -end- of the first line segment or the -beginning- of the next line segment. The linked specs aren't clear on that point.

It would be nice to have a test case that showed us D2D's behavior.

Comment 26

[Milan Sreckovic [:milan] (needinfo for best results)]

(In reply to Brian Birtles (:birtles) from comment #22)
>...
>   "At non-smooth junction points, the angle of the tangent vector for the
> purpose of these calculations is determined by the tangent to the curve
> after the junction."
> http://dev.w3.org/fxtf/web-animations/#calculating-the-rotation-value-of-a-
> path-animation-effect

That seems fairly clear for animation - take the tangent of the following segment.

For SVG, it seems to be fairly clear that the average should be taken (http://www.w3.org/TR/SVG/painting.html):
"... should point toward the angle bisector for the angle at the given vertex, where that angle has one side consisting of tangent vector for the path segment going into the vertex and the other side the tangent vector for the path segment going out of the vertex..."

Comment 27

[Daniel Holbert [:dholbert]]

(In reply to Milan Sreckovic [:milan] from comment #26)
> >   "At non-smooth junction points, the angle of the tangent vector for the
> > purpose of these calculations is determined by the tangent to the curve
> > after the junction."
> > http://dev.w3.org/fxtf/web-animations/#calculating-the-rotation-value-of-a-
> > path-animation-effect
> 
> That seems fairly clear for animation - take the tangent of the following
> segment.

I don't think we should treat the web-animations spec as authoritative here; it's a recent creation & IIUC is meant to be descriptive of animation specs up to this point (and proscriptive going forward). If we end up disagreeing with what it says, Brian can change it. :)

> For SVG, it seems to be fairly clear that the average should be taken

That's for markers, which are different (and have better-defined behavior) per beginning of comment 24.

Comment 28

[Daniel Holbert [:dholbert]]

So I'd like to take a step back, disregard angles altogether, and ask a simpler question which I think would give us the answer here.

On path with *disjoint* segments (e.g. a horizontal line and then a vertical line, with a move command in between them), where should <animateMotion> place the moved object when our clock reaches the time corresponding to the discontinuity?

Should it place the object...
  (a) at the end of the first segment?
or
  (b) after the jump, at the beginning of the second segment?

That is the more fundamental question, and the answer to that question determines which line-segment we should use for determining the angle.

I'm guessing that our current code's answer is (a) and Bas's new code's answer is (b), and that behavior-change is the root cause of the difference here.

Comment 29

[Daniel Holbert [:dholbert]]

(the "Should it place the object..." question can of course be read as "Should ComputePointAtLength() return a point...")

Comment 30

[Jonathan Watt [:jwatt]]

I think (b). My reasoning would be the same as Bas' reasoning for (1) in comment 14; for consistency in a looping animation each segment should be [start,end) otherwise the start and end segments are "different".

Comment 31

[Daniel Holbert [:dholbert]]

Attachment: (old version of testcase 2; disregard, because Opera apparently can't distinguish between t=1.001 and t=1.)

Comment 32

[Daniel Holbert [:dholbert]]

Attachment: testcase 2 (for "which segment are we on" discontinuity)

(In reply to Jonathan Watt [:jwatt] from comment #17)
> Currently Firefox, Chrome and Opera all agree that the tangent at a
> discontinuity in an mpath is the tangent at the end of the previous segment

This testcase shows that Firefox, Chrome, and Opera[Presto] all also agree that the *point* visited at the discontinuity is at the end of the previous segment, too (i.e. they agree that the answer is (a) to my question in comment 28, too.)

Comment 33

[Daniel Holbert [:dholbert]]

I think I agree conceptually with what jwatt said in comment 28.

(Expanding on what he said, slightly: in SMIL, at the discontinuity point of a repeating animation, we don't sample the final point -- we instead jump back to the beginning time. This is conceptually similar to the idea of not quite sampling the final point in a line-segment, but instead jumping to the beginning of the next line segment.)

Another way of thinking about this, stepping back a bit more: the distinction between (a)/(b) in comment 28 could be thought of as being a bit arbitrary in the real world, due to float error. e.g. in my "testcase 2", you could imagine that the representation of "1 second" that we're seeking to (at the inflection point) is marginally less than or greater than the "true" inflection point, due to float approximation.  So whether we behave like (a) or (b) is a bit arbitrary. [hand-wave hand-wave] [This is more the case with numbers whose floating point representation is messier than 1's representation.])

SO: I think I'm OK with Moz2D having behavior (b), though it's a bit unfortunate that this means we'll be switching away from a consensus behavior.

Comment 34

[Daniel Holbert [:dholbert]]

Attachment: testcase 3: animateMotion with fill="freeze", rotate="auto", & closed path

jwatt brought up one possibly-problematic case -- a non-repeating animation across a closed path (i.e. one that ends with "z"), with fill="freeze" (which makes the final animated value stick around after the animation).

For this situation, we definitely *do* need to sample the end of the final path-segment (and use that segment for determining the angle), not the beginning of the first path segment.

This testcase demonstrates that situation -- if we render it correctly, no red should be visible at the end of the animation.  Bas, could you check if we do the right thing here, with your patches? jwatt and I are guessing we don't.  

jwatt says that for this to work, we may need support from Moz2D to be able to say "at joins, return the tangent of the previous segment" or "at joins, return the tangent of the next segment" -- in other words have Moz2D be able to do both (but normally have the (b) behavior).

Comment 35

[Bas Schouten (:bas.schouten)]

(In reply to Daniel Holbert [:dholbert] from comment #34)
> Created attachment 830328 [details]
> testcase 3: animateMotion with fill="freeze", rotate="auto", & closed path
> 
> jwatt brought up one possibly-problematic case -- a non-repeating animation
> across a closed path (i.e. one that ends with "z"), with fill="freeze"
> (which makes the final animated value stick around after the animation).
> 
> For this situation, we definitely *do* need to sample the end of the final
> path-segment (and use that segment for determining the angle), not the
> beginning of the first path segment.
> 
> This testcase demonstrates that situation -- if we render it correctly, no
> red should be visible at the end of the animation.  Bas, could you check if
> we do the right thing here, with your patches? jwatt and I are guessing we
> don't.  
> 
> jwatt says that for this to work, we may need support from Moz2D to be able
> to say "at joins, return the tangent of the previous segment" or "at joins,
> return the tangent of the next segment" -- in other words have Moz2D be able
> to do both (but normally have the (b) behavior).

I think we'll be good by default, as at the -end- of a path, we won't 'loop around' the path, i.e. we'll return the tangent of the 'final vector' since path generally aren't considered looping, at least in my code. I'm not sure what D2D will do here, but I think it will do the same.

Comment 36

[Brian Birtles (:birtles)]

(In reply to Daniel Holbert [:dholbert] from comment #28)
> On path with *disjoint* segments (e.g. a horizontal line and then a vertical
> line, with a move command in between them), where should <animateMotion>
> place the moved object when our clock reaches the time corresponding to the
> discontinuity?
> 
> Should it place the object...
>   (a) at the end of the first segment?
> or
>   (b) after the jump, at the beginning of the second segment?

For time intervals, SMIL's endpoint-exclusive timing is well defined[1] and says (b). While it's not spelled out that this should also apply to path segments I think that's the most consistent behavior (i.e. least surprising).

[1] http://www.w3.org/TR/smil-animation/#IntervalTiming

Comment 37

[Bas Schouten (:bas.schouten)]

(In reply to Daniel Holbert [:dholbert] from comment #34)
> Created attachment 830328 [details]
> testcase 3: animateMotion with fill="freeze", rotate="auto", & closed path
> 
> jwatt brought up one possibly-problematic case -- a non-repeating animation
> across a closed path (i.e. one that ends with "z"), with fill="freeze"
> (which makes the final animated value stick around after the animation).
> 
> For this situation, we definitely *do* need to sample the end of the final
> path-segment (and use that segment for determining the angle), not the
> beginning of the first path segment.
> 
> This testcase demonstrates that situation -- if we render it correctly, no
> red should be visible at the end of the animation.  Bas, could you check if
> we do the right thing here, with your patches? jwatt and I are guessing we
> don't.  
> 
> jwatt says that for this to work, we may need support from Moz2D to be able
> to say "at joins, return the tangent of the previous segment" or "at joins,
> return the tangent of the next segment" -- in other words have Moz2D be able
> to do both (but normally have the (b) behavior).

As I expected, this test case is fine, so I think we can go right ahead and implement this everywhere (I added a unittest to Moz2D to verify this behavior too).

Comment 38

[Bas Schouten (:bas.schouten)]

Attachment: Part 1: Add documentation for ComputeLength and ComputePointAtLength API

Comment 39

[Bas Schouten (:bas.schouten)]

Attachment: Part 3: Add generic ComputeLength code for backends with no such functionality v5

This corrects a forgotten qref in the last patch.

Comment 40

[Ed Morley [:emorley]]

Part 2 landed with incorrect bug number:
https://hg.mozilla.org/mozilla-central/rev/f2e964f10799

Comment 41

[Daniel Holbert [:dholbert]]

Did parts 1 or 3 ever land? We only have a record here of Part 2 landing (with the wrong bug number).

Comment 42

[Daniel Holbert [:dholbert]]

Actually, the known-landed patch from comment 40 (labeled "Part 2" in its commit message) seems to match the attachment on this bug that's labeled "part 3" (attachment 832286 [details] [diff] [review]).

So, my question in Comment 41 really meant to say: did this bug's attachments labeled "Part 1", "Part 2", or "Part 4" ever land?

Comment 43

[Milan Sreckovic [:milan] (needinfo for best results)]

I have a feeling you know the answer :), but to be explicit:
Part 1 - no, it hasn't landed.
Part 2 - partially - not the PathD2D.{h,cpp} files
Part 4 - no, it hasn't landed.

Comment 44

[Daniel Holbert [:dholbert]]

OK. I wasn't sure, & wanted to make sure they at least hadn't been forgotten [or perhaps made-unnecessary without that being recorded in the bug].  (Noticed this when investigating bug 1066556, a regression that seems to have been caused by the patch that did land.)

Comment 45

[Milan Sreckovic [:milan] (needinfo for best results)]

I can't recall if there were test failure issues, performance issues, but I imagine Part 1 at least just got forgotten (function docs :)

Comment 46

[Bas Schouten (:bas.schouten)]

(In reply to Milan Sreckovic [:milan] from comment #45)
> I can't recall if there were test failure issues, performance issues, but I
> imagine Part 1 at least just got forgotten (function docs :)

Part 2 had bugs, and other than that it's just a performance improvement, so we just sort of ignored it for the time being. Part 1, as Milan said, got forgotten. Part 4 was landed on Moz2D stand-alone (it would only apply there anyway :-)).

Comment 47

[Daniel Holbert [:dholbert]]

OK. Perhaps this bug's scope should be narrowed to cover what actually landed, and any actually-likely-to-land remaining work here can be spun off as followups?  (Then, this can be closed, instead of being in its current "1/4 in 3/4 out" state indefinitely.)