stroke-linejoin="arcs"

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

stroke-linejoin="arcs"

Diego Nehab
Hey guys,

I am a computer graphics researcher and have been looking into the new "arcs" stroke-linejoin proposal for SVG 2. Is the specification complete? If so, I can imagine many developers will have trouble sorting out the missing details. Take at look at 12.5.8 and figure 13 at

http://www.w3.org/TR/SVG2/painting.html#CurvatureCalculation

It seems to me that easiest way to specify the center of the circle is relative to point P, and not relative to points P1 and P2. This is because we are offsetting the osculating circles to the path at P (at each side). The offset circle has the same center as the osculating circle. If the normals of the path at P are N1 and N2 and the curvatures are k1 and k2, the center is always at P + N1/k1 and P + N2/k2, regardless of the stroke-width.

Once the center is fixed, we need the radius. Here, I believe the correct formula is abs(1/k - 0.5 stroke-width). Look at figure 13. If you increase the stroke width on and on, at some point P1 will cross the center of Aoutside. You need the abs() for this case. It is the sign of the curvature that tells whether we should add or subtract 0.5 stroke-width to the radius of curvature. The abs() allows us to unify everything in a single case.

There also seems to be missing information on the arcs that make up the join:

" If the two circles (or circle and line) intersect, the line join region is defined by the lines that connect P with P1 and P2 and the arcs defined by the circles (or arc and line) between the closest intersection point to P, and P1 and P2. "

In the case where both curvatures are positive and both radii of curvature are smaller than 0.5 stroke-width, the arcs that connect P1 to P4 and P4 to P2 are CCW (and can easily span more than 180 degrees). In all other cases, the arcs seem to be CW.

There is an additional interesting corner case. The documentation mentions the cases where the points do not intersect and when both curvatures are zero, in which case we should fall back to miterclip. However, when either curvature is +/- infinite (or very large magnitude), it is better to revert to round instead.

There seems to be a a typo in "For a line: the curvature is infinite." I think you mean that the curvature is zero, right?

At any rate, this is just a heads up and a request for clarifications. The more explicit the documentation is, the fewer confused people like me there will be.

Kind regards,
Diego
Reply | Threaded
Open this post in threaded view
|

Re: stroke-linejoin="arcs"

Tavmjong Bah-2
On Thu, 2015-11-26 at 18:30 -0200, Diego Nehab wrote:

> Hey guys,
>
> I am a computer graphics researcher and have been looking into the
> new "arcs" stroke-linejoin proposal for SVG 2. Is the specification
> complete? If so, I can imagine many developers will have trouble
> sorting out the missing details. Take at look at 12.5.8 and figure 13
> at
>
> http://www.w3.org/TR/SVG2/painting.html#CurvatureCalculation
>
> It seems to me that easiest way to specify the center of the circle
> is relative to point P, and not relative to points P1 and P2. This is
> because we are offsetting the osculating circles to the path at P (at
> each side). The offset circle has the same center as the osculating
> circle. If the normals of the path at P are N1 and N2 and the
> curvatures are k1 and k2, the center is always at P + N1/k1 and P +
> N2/k2, regardless of the stroke-width.

It does seem to be a clearer to define the center of the circles as the
center of the osculating circle. I'll make the change. The problem with
your definition of the center is that the N1 and N2 are ambiguous in
sign.

> Once the center is fixed, we need the radius. Here, I believe the
> correct formula is abs(1/k - 0.5 stroke-width). Look at figure 13. If
> you increase the stroke width on and on, at some point P1 will cross
> the center of Aoutside. You need the abs() for this case. It is the
> sign of the curvature that tells whether we should add or subtract
> 0.5 stroke-width to the radius of curvature. The abs() allows us to
> unify everything in a single case.

This works for a path where the join is to the left of the path
(relative to the path direction) but fails if the join is to the right.
Then the radius is abs(1/k + 0.5 stroke-width). See [1]

> There also seems to be missing information on the arcs that make up
> the join:
>
> " If the two circles (or circle and line) intersect, the line join
> region is defined by the lines that connect P with P1 and P2 and the
> arcs defined by the circles (or arc and line) between the closest
> intersection point to P, and P1 and P2. "
>
> In the case where both curvatures are positive and both radii of
> curvature are smaller than 0.5 stroke-width, the arcs that connect P1
> to P4 and P4 to P2 are CCW (and can easily span more than 180
> degrees). In all other cases, the arcs seem to be CW.
>
> There is an additional interesting corner case. The documentation
> mentions the cases where the points do not intersect and when both
> curvatures are zero, in which case we should fall back to miterclip.
> However, when either curvature is +/- infinite (or very large
> magnitude), it is better to revert to round instead.

Whenever the radius of curvature is less than half the stroke width the
tangent flips direction. This is not a new problem. Browsers are not
consistent in how they handle these edge cases for existing line joins
and end caps.[2][3] We should work on defining these cases better but
may be hampered by the baked in behavior of the graphics libraries that
the browsers use.

> There seems to be a a typo in "For a line: the curvature is
> infinite." I think you mean that the curvature is zero, right?

The denominator goes to zero faster than the numerator so in the limit
as P1 goes to P0, for example, the curvature goes to infinity and the
radius goes to zero. This does raise the point, that the fallback of
using a straight line should probably be changed to using a curve with
the radius of half the line width. This will take a bit of
investigation.

> At any rate, this is just a heads up and a request for
> clarifications. The more explicit the documentation is, the fewer
> confused people like me there will be.

Thanks for the feedback.

Tav
 
[1] http://tavmjong.free.fr/SVG/LINEJOIN/line_join_arcs_diagram.svg
[2] http://tavmjong.free.fr/SVG/LINEJOIN/line_join_test_all.svg
[3] http://tavmjong.free.fr/blog/?m=201504

> Kind regards,
> Diego

Reply | Threaded
Open this post in threaded view
|

Re: stroke-linejoin="arcs"

Diego Nehab
Dear Tav,

I assumed the right-hand convention for the normals. Take the tangent direction at a point P(t) while moving along the segment. Call it T(t). Rotate it CCW by 90 degrees and normalize to produce N(t). Now compute signed curvature κ(t) as usual. The center of the osculating circle is at P(t) + N(t)/k(t). As long as the tangent direction and curvature have been computed consistently (i.e., traversing the curve in consistent directions), the formula should work, no? Where is the ambiguity? The formulas do not change regardless of whether the join is to the right or left of the path.

I think we have a few cases here, depending on signed curvatures of the two connecting segments. In order of precedence:

1) If either curvature is -, we revert to the round join.

2) If both curvatures are in (-, 0], then the offset osculating "circles" intersect and we are golden. Quotes are because these circles could degenerate to lines, but this is no trouble.

3) If one curvature is in (-, 0] and the other is in (0, 2/w), where w is the stroke width, the offset osculating circles may or may not intersect. This case is problematic because, according to the proposal, we don't have a continuous behavior here. Reverting back to miter when no intersection is found will basically create a pop. Perhaps we should instead take the positive curvature and reduce it until the circles are tangent? At least this would create a continuous behavior more in the line of what SVG does in other cases...

4) If either curvature is in [2/w, +], the offset osculating circles may or may not intersect. However, the intersection is *not* meaningful, because the offset osculating circle does not correspond to the offset stroke. It is as though you are offsetting a circle by more than its radius. Only the outer boundary matters. The inner boundary simply disappears. It doesn't make sense to intersect inner boundaries because they are not part of the offset path at all.

For some reason, I can't load the SVG files you linked to. (Subscripts in a link?)

As for your blog, can I get the SVG files for these cool examples you show?

Kind regards,
Diego
Reply | Threaded
Open this post in threaded view
|

Re: stroke-linejoin="arcs"

Tavmjong Bah-2

Hi Diego,

Sorry it has taken me so long to reply...

On Tue, 2015-12-01 at 13:54 -0200, Diego Nehab wrote:
> Dear Tav,
>
> I assumed the right-hand convention for the normals.

SVG actually uses a left-handed coordinate system as y point down...
but that doesn't affect the discussion below.

> Take the tangent direction at a point P(t) while moving along the
> segment. Call it T(t). Rotate it CCW by 90 degrees and normalize to
> produce N(t). Now compute signed curvature κ(t) as usual. The center
> of the osculating circle is at P(t) + N(t)/k(t). As long as the
> tangent direction and curvature have been computed consistently
> (i.e., traversing the curve in consistent directions), the formula
> should work, no? Where is the ambiguity? The formulas do not change
> regardless of whether the join is to the right or left of the path.

Yes, for calculating the center of the circle. But not for calculating
the offset radii. Try reversing the path.

> I think we have a few cases here, depending on signed curvatures of
> the two connecting segments. In order of precedence:
>
> 1) If either curvature is -∞, we revert to the round join.

This means the radius is zero. That can't happen for Bezier curves. I
suppose it could happen if an elliptical curve was flat. In any case, I
don't think this needs to be special cased since the offset path will
have a radius of w/2.

> 2) If both curvatures are in (-∞, 0], then the offset osculating
> "circles" intersect and we are golden. Quotes are because these
> circles could degenerate to lines, but this is no trouble.

Yes, this should always work, offset radii greater than w/2.

> 3) If one curvature is in (-∞, 0] and the other is in (0, 2/w),
> where w is the stroke width, the offset osculating circles may or may
> not intersect. This case is problematic because, according to the
> proposal, we don't have a continuous behavior here. Reverting back to
> miter when no intersection is found will basically create a pop.
> Perhaps we should instead take the positive curvature and reduce it
> until the circles are tangent? At least this would create a
> continuous behavior more in the line of what SVG does in other
> cases...

This is an interesting idea but as far as I can tell it requires
solving a quartic equation. I tried just increasing the smaller circle
until there is an intersection. See the animation in the web page
below.

> 4) If either curvature is in [2/w, +∞], the offset osculating
> circles may or may not intersect. However, the intersection is *not*
> meaningful, because the offset osculating circle does not correspond
> to the offset stroke. It is as though you are offsetting a circle by
> more than its radius. Only the outer boundary matters. The inner
> boundary simply disappears. It doesn't make sense to intersect inner
> boundaries because they are not part of the offset path at all.

I'm not 100% sure of what you are saying here but of course inner
boundaries are not relevant here.

> For some reason, I can't load the SVG files you linked to.
> (Subscripts in a link?)

Subscripts? Are you perhaps a tex user?

> As for your blog, can I get the SVG files for these cool examples you
> show?

Most if the images are SVG files. Inkscape trunk has a "Join" LPE which
implements the arcs line-join. It's a bit buggy but it gives quite
useful feedback. By setting the stroke color different than the fill
color one can see the generated offset path.

I've prepared a web page with some studies of line joins. I look at
several options for fallbacks for the 'arcs' line join and at the
bottom there is an exhaustive diagram of all the different possible
combinations of curvatures relative to stroke widths. See:

        http://tavmjong.free.fr/SVG/LINEJOIN_STUDY/

Tav


> Kind regards,
> Diego
>

Reply | Threaded
Open this post in threaded view
|

Re: stroke-linejoin="arcs"

Diego Nehab
Dear Tav,

Sorry it has taken me so long to reply...

No problem!

> Take the tangent direction at a point P(t) while moving along the
> segment. Call it T(t). Rotate it CCW by 90 degrees and normalize to
> produce N(t). Now compute signed curvature κ(t) as usual. The center
> of the osculating circle is at P(t) + N(t)/k(t). As long as the
> tangent direction and curvature have been computed consistently
> (i.e., traversing the curve in consistent directions), the formula
> should work, no? Where is the ambiguity? The formulas do not change
> regardless of whether the join is to the right or left of the path.

Yes, for calculating the center of the circle. But not for calculating
the offset radii. Try reversing the path.

It still works. The radius of the circular offset to be drawn in the direction of the normal is always abs(1/k + w/2). If k is positive, the center is on the same side as the normal and the curve is turning towards the normal. So the radius of the offset circle is 1/k - w/2. If k is negative, the center is on the opposite side of the normal and the curve is turning away from the normal. So the radius of the offset circle is -1/k + w/2. You will notice that, regardless of whether k is positive or negative, the radius is always abs(1/k-w/2) = abs(w/2-1/k), which is the formula I suggested using. It doesn't matter if you reverse the path.. The normal will flip and so will the sign of k. Nothing changes. This is in fact how I implement it. Move along the path offsetting one side then move along the reversed path offsetting the other side, always using the same formulas.
 
> I think we have a few cases here, depending on signed curvatures of
> the two connecting segments. In order of precedence:
>
> 1) If either curvature is -∞, we revert to the round join.

This means the radius is zero. That can't happen for Bezier curves. I
suppose it could happen if an elliptical curve was flat. In any case, I
don't think this needs to be special cased since the offset path will
have a radius of w/2.

 
Isn't this exactly what happens when there is a cusp in a cubic Bézier? Try repeating the first two control points. What is the curvature at t=0? But it doesn't matter. What matters is that when the radius of curvature is too small, the best approximation for the join is round, not miter. Right?

 
> 2) If both curvatures are in (-∞, 0], then the offset osculating
> "circles" intersect and we are golden. Quotes are because these
> circles could degenerate to lines, but this is no trouble.

Yes, this should always work, offset radii greater than w/2.

> 3) If one curvature is in (-∞, 0] and the other is in (0, 2/w),
> where w is the stroke width, the offset osculating circles may or may
> not intersect. This case is problematic because, according to the
> proposal, we don't have a continuous behavior here. Reverting back to
> miter when no intersection is found will basically create a pop.
> Perhaps we should instead take the positive curvature and reduce it
> until the circles are tangent? At least this would create a
> continuous behavior more in the line of what SVG does in other
> cases...

This is an interesting idea but as far as I can tell it requires
solving a quartic equation. I tried just increasing the smaller circle
until there is an intersection. See the animation in the web page
below.


I saw the animation. It is pretty cool. :) I do prefer this method. The length of the join wouldn't increase like crazy because of the miter limit, right? I haven't done the math to see if it requires solving a quartic or not. But even if it does, it shouldn't be a problem. We know the bounds for the roots we care about, right? There is a very simple method numerical method (I am saying 10-15 lines of code) that is guaranteed to find the roots of polynomials inside a bracket. Quite efficient for low-order polynomials.

I'm not 100% sure of what you are saying here but of course inner
boundaries are not relevant here.

> For some reason, I can't load the SVG files you linked to.
> (Subscripts in a link?)

Subscripts? Are you perhaps a tex user?


I am. But I swear that my e-mail reader (Gmail!) was rendering the file names as subscripts! :)
 
> As for your blog, can I get the SVG files for these cool examples you
> show?

Most if the images are SVG files. Inkscape trunk has a "Join" LPE which
implements the arcs line-join. It's a bit buggy but it gives quite
useful feedback. By setting the stroke color different than the fill
color one can see the generated offset path.

I've prepared a web page with some studies of line joins. I look at
several options for fallbacks for the 'arcs' line join and at the
bottom there is an exhaustive diagram of all the different possible
combinations of curvatures relative to stroke widths. See:

        http://tavmjong.free.fr/SVG/LINEJOIN_STUDY/

Do you know what algorithm Inkscape uses for offseting? When the stroke width is large, things start breaking apart. It's not something particular to Inkscape. Many renderers break down, and break down in a somewhat similar way. I was wondering if they all try to implement the same idea. NVPR has a directory with a bunch of these nasty examples. I think they converted examples they got from GhostScript.

Kind regards,
Diego