Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
Thanks a bunch! Johan
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Tav
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet. And handling all corner cases is also a mess... the code in trunk should work reasonably well now. The attached file has a "wrong" result for the middle path.
Ciao, Johan
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
On 8-10-2012 10:35, Jasper van de Gronde wrote:
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
I tried the norm of second derivative but I forgot about arc-length reparametrisation, thanks for the hint! Arc-length reparametrisation is already present in 2geom, so that is easy. Yes I need it 'signed', such that the touching circle is on the inside of the curve. I indeed get that from the normal, but the trick is to figure out which direction points inward for the normal! :-) For that I look at the direction of 2nd derivative w.r.t. the tangent.
And just now I find at function named "curvature" in 2geom... (although it has a todo comment that it is claimed incomplete...)
Cheers, Johan
On 9-10-2012 1:04, Johan Engelen wrote:
On 8-10-2012 10:35, Jasper van de Gronde wrote:
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
I tried the norm of second derivative but I forgot about arc-length reparametrisation, thanks for the hint! Arc-length reparametrisation is already present in 2geom, so that is easy. Yes I need it 'signed', such that the touching circle is on the inside of the curve. I indeed get that from the normal, but the trick is to figure out which direction points inward for the normal! :-) For that I look at the direction of 2nd derivative w.r.t. the tangent.
And just now I find at function named "curvature" in 2geom... (although it has a todo comment that it is claimed incomplete...)
"Extrapolated arc" works much better with the improved curvature calculation (not sure whether it is really the curvature but OK :)). Now what is left is to fix the calculation for zero-length handles. Attached is a modified version of the "Choose your miter" file that I showed at LGM. In many cases, the difference between "Extrapolated" and "Extrapolated arc" is not very big. But there are things that one or the other can't do. For example, with "extrapolate" it is not possible to end up with a curving miter at the end of an almost straight line segment simply because the mirrored piece will be straight too instead of curved. Overall it seems that "Extrapolated arc" is easier to control and leads to nicer results, so I am tempted to pick that one by default.
Please play with it a bit and form an opinion.
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Cheers, Johan
On 9-10-2012 1:04, Johan Engelen wrote:
On 8-10-2012 10:35, Jasper van de Gronde wrote:
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
I tried the norm of second derivative but I forgot about arc-length reparametrisation, thanks for the hint! Arc-length reparametrisation is already present in 2geom, so that is easy. Yes I need it 'signed', such that the touching circle is on the inside of the curve. I indeed get that from the normal, but the trick is to figure out which direction points inward for the normal! :-) For that I look at the direction of 2nd derivative w.r.t. the tangent.
And just now I find at function named "curvature" in 2geom... (although it has a todo comment that it is claimed incomplete...)
"Extrapolated arc" works much better with the improved curvature calculation (not sure whether it is really the curvature but OK :)). Now what is left is to fix the calculation for zero-length handles. Attached is a modified version of the "Choose your miter" file that I showed at LGM. In many cases, the difference between "Extrapolated" and "Extrapolated arc" is not very big. But there are things that one or the other can't do. For example, with "extrapolate" it is not possible to end up with a curving miter at the end of an almost straight line segment simply because the mirrored piece will be straight too instead of curved. Overall it seems that "Extrapolated arc" is easier to control and leads to nicer results, so I am tempted to pick that one by default.
Please play with it a bit and form an opinion.
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Cheers, Johan
On Tue, 2012-10-09 at 23:37 +0200, Johan Engelen wrote:
On 9-10-2012 1:04, Johan Engelen wrote:
On 8-10-2012 10:35, Jasper van de Gronde wrote:
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote:
Hi all, I've lost track of all the problems with powerstroke. Please send me again the bugs you have found (with a test file!) or the UI ideas we definitely need for release.
I have been working on "extrapolate by arcs matching path curvature", but I think it will take me too long to make that work reliably before release. There are still too many bumps along that road... I've committed the code, but it is disabled.
What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
I tried the norm of second derivative but I forgot about arc-length reparametrisation, thanks for the hint! Arc-length reparametrisation is already present in 2geom, so that is easy. Yes I need it 'signed', such that the touching circle is on the inside of the curve. I indeed get that from the normal, but the trick is to figure out which direction points inward for the normal! :-) For that I look at the direction of 2nd derivative w.r.t. the tangent.
And just now I find at function named "curvature" in 2geom... (although it has a todo comment that it is claimed incomplete...)
For my Cairo hack, I used the last three points (two handles, end point) of the cubic Bezier curve to determine the curvature. If the last two points are degenerate, I uses the start point, first handle, and end point. This seems to work fine (and as Cairo only uses cubic Bezier and lines at the rendering point I don't have to worry about arcs, quadratic Beziers, etc.). The math for finding the curvature of a cubic Bezier can be found at:
http://tavmjong.free.fr/SVG/LINEJOIN/index.html
"Extrapolated arc" works much better with the improved curvature calculation (not sure whether it is really the curvature but OK :)). Now what is left is to fix the calculation for zero-length handles. Attached is a modified version of the "Choose your miter" file that I showed at LGM. In many cases, the difference between "Extrapolated" and "Extrapolated arc" is not very big. But there are things that one or the other can't do. For example, with "extrapolate" it is not possible to end up with a curving miter at the end of an almost straight line segment simply because the mirrored piece will be straight too instead of curved. Overall it seems that "Extrapolated arc" is easier to control and leads to nicer results, so I am tempted to pick that one by default.
Please play with it a bit and form an opinion.
I would choose the extrapolated arc. (This also matches what will be in SVG 2.)
There seems to be a bug in your code where the wrong intersection of the two circles is sometimes chosen.
I noticed in your code that if the two circles don't intersect, you fall back to bevel join. I am thinking in the SVG 2 spec about falling back to miter join.
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Yes, a better name would be nice... If someone comes up with one it might just end up in the SVG 2 spec. Maybe just "arc"?
Tav
On 10-10-2012 18:23, Martin Owens wrote:
On Tue, 2012-10-09 at 23:37 +0200, Johan Engelen wrote:
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Is "Extrapolated" not an arc?
Explain what these things are and I'll give you your names. :-)
"Extrapolated" = extend the incoming segment by mirroring it "Extrapolated arc" = extend the incoming segment by a circle that has same curvature as last point on incoming segment.
-Johan
On 10-10-2012 9:52, Tavmjong Bah wrote:
On Tue, 2012-10-09 at 23:37 +0200, Johan Engelen wrote:
On 9-10-2012 1:04, Johan Engelen wrote:
On 8-10-2012 10:35, Jasper van de Gronde wrote:
On 07-10-12 21:05, Johan Engelen wrote:
On 7-10-2012 7:49, Tavmjong Bah wrote:
On Sat, 2012-10-06 at 22:26 +0200, Johan Engelen wrote: > Hi all, > I've lost track of all the problems with powerstroke. > Please send me again the bugs you have found (with a test file!) or the > UI ideas we definitely need for release. > > I have been working on "extrapolate by arcs matching path curvature", > but I think it will take me too long to make that work reliably before > release. There are still too many bumps along that road... I've > committed the code, but it is disabled. What is your problem with "extrapolate by arcs matching path curvature"? I've got a hacked version of Cairo that does the extrapolated line-join... but not properly (it only works at 100% zoom at the moment).
Determining the curvature is messy, have not found a good way to do that yet.
In principle, curvature is just the norm of the second derivative w.r.t. arc-length (if you want it signed, you'd probably just have to take the dot product with the unit normal, instead of the norm).
Of course, the trick is in the "arc-length" bit, is that where you're getting stuck? One trick you could try is taking an explicit formula like (x'*y'' - y'*x'')/(x'^2+y'^2)^(3/2) and approximating it with a polynomial (which doesn't require any values near the endpoints, where you'll usually get singularities and other problems), then evaluating the polynomial at the endpoints. I haven't tried it, so I'm not sure how well it would work, but my guess is that it could work pretty well.
I tried the norm of second derivative but I forgot about arc-length reparametrisation, thanks for the hint! Arc-length reparametrisation is already present in 2geom, so that is easy. Yes I need it 'signed', such that the touching circle is on the inside of the curve. I indeed get that from the normal, but the trick is to figure out which direction points inward for the normal! :-) For that I look at the direction of 2nd derivative w.r.t. the tangent.
And just now I find at function named "curvature" in 2geom... (although it has a todo comment that it is claimed incomplete...)
For my Cairo hack, I used the last three points (two handles, end point) of the cubic Bezier curve to determine the curvature. If the last two points are degenerate, I uses the start point, first handle, and end point. This seems to work fine (and as Cairo only uses cubic Bezier and lines at the rendering point I don't have to worry about arcs, quadratic Beziers, etc.). The math for finding the curvature of a cubic Bezier can be found at:
Nice explanation, we should link our release notes to it.
I think my 2geom's math is sound now, but... I could transform to cubic bezier and do the math there, to make sure it is identical to yours/SVG's............
But... I spot a difference with my implementation: I extrapolate with circles that are tangent to the stroke of the path, instead of the concentric circles with reduced radius like you do. Because of varying stroke width, the direction and curvature at the stroke itself may be very different from the direction and curvature of the original path. Intuition tells me that our two approaches are identical for fixed stroke width, but am too lazy to do the math. I guess for you it is an easy change, so hoping you can change that aspect to "my" calculation, so your text is valid for varying stroke width too!
"Extrapolated arc" works much better with the improved curvature calculation (not sure whether it is really the curvature but OK :)). Now what is left is to fix the calculation for zero-length handles. Attached is a modified version of the "Choose your miter" file that I showed at LGM. In many cases, the difference between "Extrapolated" and "Extrapolated arc" is not very big. But there are things that one or the other can't do. For example, with "extrapolate" it is not possible to end up with a curving miter at the end of an almost straight line segment simply because the mirrored piece will be straight too instead of curved. Overall it seems that "Extrapolated arc" is easier to control and leads to nicer results, so I am tempted to pick that one by default.
Please play with it a bit and form an opinion.
I would choose the extrapolated arc. (This also matches what will be in SVG 2.)
There seems to be a bug in your code where the wrong intersection of the two circles is sometimes chosen.
Which rev did you use? Should've been fixed yesterday.
Have to fix the effect for straight paths now.
I noticed in your code that if the two circles don't intersect, you fall back to bevel join. I am thinking in the SVG 2 spec about falling back to miter join.
Ok, I just did the fallback as a temp fix. Let's see if it makes much difference. (because very often the miter will have to fallback to bevel I think)
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Yes, a better name would be nice... If someone comes up with one it might just end up in the SVG 2 spec. Maybe just "arc"?
Do people still want the original extrapolate? I'm not too proud of my original idea to not leave it out if people find it to have very little use. I have not made up my mind yet. The mirror-extrapolate allows for some funky looking stuff that you can't get with circle-extrapolate, but perhaps it is too extreme to be useful :P
Cheers, Johan
On 10-10-2012 23:08, Johan Engelen wrote:
On 10-10-2012 9:52, Tavmjong Bah wrote:
There seems to be a bug in your code where the wrong intersection of the two circles is sometimes chosen.
Which rev did you use? Should've been fixed yesterday.
Hmm, bzr up, it didn't commit yesterday. (I also changed fallback to miter, but there is a downside: when it falls back to miter, you may not spot that the corner is ugly again if you are not careful)
Cheers, Johan
On Wed, 2012-10-10 at 19:28 +0200, Johan Engelen wrote:
"Extrapolated" = extend the incoming segment by mirroring it "Extrapolated arc" = extend the incoming segment by a circle that has same curvature as last point on incoming segment.
* Mirror Extension or Reflective Extension * Arc Extension or Circular Extension
Vote for your favorite.
Martin,
Arc Extension or Circular Extension sound good for large masses yet Circular has +0.1 meaning for the peoples with not many math classes ;)
..just a voice from the crowd
2012/10/11 Martin Owens <doctormo@...400...>:
On Wed, 2012-10-10 at 19:28 +0200, Johan Engelen wrote:
"Extrapolated" = extend the incoming segment by mirroring it "Extrapolated arc" = extend the incoming segment by a circle that has same curvature as last point on incoming segment.
- Mirror Extension or Reflective Extension
- Arc Extension or Circular Extension
Vote for your favorite.
Martin,
Don't let slow site performance ruin your business. Deploy New Relic APM Deploy New Relic app performance management and know exactly what is happening inside your Ruby, Python, PHP, Java, and .NET app Try New Relic at no cost today and get our sweet Data Nerd shirt too! http://p.sf.net/sfu/newrelic-dev2dev _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
On Thu, 2012-10-11 at 11:26 +0800, SorinN wrote:
yet Circular has +0.1 meaning for the peoples with not many math classes ;)
Actually it doesn't have to be concrete. it just has to be a little "lie to children" which is on the right track, explains a little and is distinctive.
Martin,
On 2012-10-10 09:52, Tavmjong Bah wrote:
For my Cairo hack, I used the last three points (two handles, end point) of the cubic Bezier curve to determine the curvature. If the last two points are degenerate, I uses the start point, first handle, and end point. This seems to work fine (and as Cairo only uses cubic Bezier and lines at the rendering point I don't have to worry about arcs, quadratic Beziers, etc.). The math for finding the curvature of a cubic Bezier can be found at: http://tavmjong.free.fr/SVG/LINEJOIN/index.html
Nice exposition! The cross product is ill-defined in 2D though, so what you can do is take the determinant of the matrix with row (or column vectors) corresponding to v and v'. Alternatively, you can extend the vectors to be 3D of course, but that would essentially just be a roundabout way to compute a determinant of a 2x2 matrix.
To deal with zero-length handles, the easiest (and correct) method is probably to specify that the curvature is zero at the endpoint with the zero-length handle (if both handles are zero-length, then the Bézier curve forms a line segment). That this is correct can be derived from the fact that the unit tangent vector at the endpoint with a zero-length handle points in the same direction as the second derivative (so locally it's a straight line). This is a consequence of l'Hôpital's rule btw.
If the first handle is zero-length and the second handle corresponds to the starting point, then again the whole curve is straight, and the curvature should be zero everywhere.
One way of doing this "automatically", is to simply add a small epsilon to the denominator (or clamp it to some small positive value). (Perhaps a bit obvious, but it's nice to know that it actually "does the right thing".)
... I noticed in your code that if the two circles don't intersect, you fall back to bevel join. I am thinking in the SVG 2 spec about falling back to miter join.
It might make more sense to use (something like) miterlimit, in some cases at least. Essentially there are two cases, either one circle is inside the other, or not. If they are "inside" each other, it might simply make perfect sense to just fill the area between the two circles, unless the area gets (really) large, then you'd probably want to limit it (using something akin to miterlimit). If the circles are not inside each other, the area "between" is always infinite (the entire plane minus the inside of the two circles). In that case, you really have to limit the extent of the join. But even then, it should be possible to still show part of the "true" join.
One possible way to specify the restriction for this kind of join would be to limit the arc-length on either side of the join. The main problem is then joining the end points, as a line segment between the two is not guaranteed to not intersect the circles. Some experimentation suggests that it might be possible to define a sensible boundary using interpolation between the two end points that is guaranteed not to intersect either of the circles.
On Wed, Oct 10, 2012 at 1:55 AM, Johan Engelen wrote:
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Wasn't "Artistic" suggested at some point?
BTW, is this SVG 2.0 material?
Alexandre Prokoudine http://libregraphicsworld.org
On Fri, 2012-10-12 at 17:34 +0400, Alexandre Prokoudine wrote:
On Wed, Oct 10, 2012 at 1:55 AM, Johan Engelen wrote:
I really hope someone comes up with better names for "Extrapolated" and "Extrapolated arc"
Wasn't "Artistic" suggested at some point?
The SVG WG liked "arc", as is short and fits with the style of the other line join options (miter, round, bevel).
BTW, is this SVG 2.0 material?
Yes and no. Inkscape's implementation is in the Power Stroke LPE which is independent of anything the SVG WG is doing. However, I suggested to the WG that it be added to SVG 2 as an option for regular paths and they have agreed.
Tav
On 12-10-2012 14:59, Jasper van de Gronde wrote:
On 2012-10-10 09:52, Tavmjong Bah wrote:
For my Cairo hack, I used the last three points (two handles, end point) of the cubic Bezier curve to determine the curvature. If the last two points are degenerate, I uses the start point, first handle, and end point. This seems to work fine (and as Cairo only uses cubic Bezier and lines at the rendering point I don't have to worry about arcs, quadratic Beziers, etc.). The math for finding the curvature of a cubic Bezier can be found at: http://tavmjong.free.fr/SVG/LINEJOIN/index.html
Nice exposition! The cross product is ill-defined in 2D though, so what you can do is take the determinant of the matrix with row (or column vectors) corresponding to v and v'. Alternatively, you can extend the vectors to be 3D of course, but that would essentially just be a roundabout way to compute a determinant of a 2x2 matrix.
To deal with zero-length handles, the easiest (and correct) method is probably to specify that the curvature is zero at the endpoint with the zero-length handle (if both handles are zero-length, then the Bézier curve forms a line segment). That this is correct can be derived from the fact that the unit tangent vector at the endpoint with a zero-length handle points in the same direction as the second derivative (so locally it's a straight line). This is a consequence of l'Hôpital's rule btw.
I don't think this is correct. It is possible to make segments with and without a zero-length handle that look exactly the same. Also, as you are moving the handle closer and closer to the knot, it does not converge to zero curvature, in fact it tends to lead to higher curvature instead of lower curvature. Wouldn't l'Hopital imply that you can get away by using +1 higher derivs instead?
If the first handle is zero-length and the second handle corresponds to the starting point, then again the whole curve is straight, and the curvature should be zero everywhere.
One way of doing this "automatically", is to simply add a small epsilon to the denominator (or clamp it to some small positive value). (Perhaps a bit obvious, but it's nice to know that it actually "does the right thing".)
... I noticed in your code that if the two circles don't intersect, you fall back to bevel join. I am thinking in the SVG 2 spec about falling back to miter join.
It might make more sense to use (something like) miterlimit, in some cases at least. Essentially there are two cases, either one circle is inside the other, or not. If they are "inside" each other, it might simply make perfect sense to just fill the area between the two circles, unless the area gets (really) large, then you'd probably want to limit it (using something akin to miterlimit). If the circles are not inside each other, the area "between" is always infinite (the entire plane minus the inside of the two circles). In that case, you really have to limit the extent of the join. But even then, it should be possible to still show part of the "true" join.
One possible way to specify the restriction for this kind of join would be to limit the arc-length on either side of the join. The main problem is then joining the end points, as a line segment between the two is not guaranteed to not intersect the circles. Some experimentation suggests that it might be possible to define a sensible boundary using interpolation between the two end points that is guaranteed not to intersect either of the circles.
I have no clue what you are saying here. :-)
I am starting to strongly dislike the miter fallback btw, simply because of it not being clear whether you have arc extension or a miter. Bevel fallback has a much better UI experience for me.
Cheers, Johan
On Thu, Oct 11, 2012 at 2:38 AM, Johan Engelen <jbc.engelen@...2592...> wrote:
But... I spot a difference with my implementation: I extrapolate with circles that are tangent to the stroke of the path, instead of the concentric circles with reduced radius like you do. Because of varying stroke width, the direction and curvature at the stroke itself may be very different from the direction and curvature of the original path.
Hi -- nice to hear the idea about the arc join. Can you give me a pointer to the two separate codes which implement the extrapolation based on the stroke and that base on the path? I'm interested to see what algorithm you are using for this.
On 13-10-2012 17:18, Shriramana Sharma wrote:
On Thu, Oct 11, 2012 at 2:38 AM, Johan Engelen <jbc.engelen@...2592...> wrote:
But... I spot a difference with my implementation: I extrapolate with circles that are tangent to the stroke of the path, instead of the concentric circles with reduced radius like you do. Because of varying stroke width, the direction and curvature at the stroke itself may be very different from the direction and curvature of the original path.
Hi -- nice to hear the idea about the arc join. Can you give me a pointer to the two separate codes which implement the extrapolation based on the stroke and that base on the path? I'm interested to see what algorithm you are using for this.
In Inkscape's source: /src/live_effects/lpe-powerstroke.cpp The arc extrapolation code starts at line 409 ("case LINEJOIN_EXTRP_MITER_ARC:")
Cheers, Johan
Hi Johan, is there a reason you reposted your extrapolated_arc_cusp SVGZ as an SVG? I don't see any changes except for the compression.
On Sat, Oct 13, 2012 at 2:41 AM, Johan Engelen <jbc.engelen@...2592...> wrote:
I am starting to strongly dislike the miter fallback btw, simply because of it not being clear whether you have arc extension or a miter. Bevel fallback has a much better UI experience for me.
I also prefer bevel fallback FWIW, but are we talking about the "extrapolated" join or the "extrapolated arc" thing (w.r.t. the example SVG)?
And please tell me whether I have understood correctly that extrapolated arc is more like bevel and basically ensures that all bevels are straightlines whereas extrapolated is more like miter and just ensures continuity of curvature? Personally I feel extrapolated arc is too extreme (too many sharp ends... Naah!)
On Fri, 2012-10-12 at 23:11 +0200, Johan Engelen wrote:
I am starting to strongly dislike the miter fallback btw, simply because of it not being clear whether you have arc extension or a miter. Bevel fallback has a much better UI experience for me.
But that is exactly what you want. Think about a path with multiple line joins. You want all the line joins to look similar but not all the joins may be possible with the arc join so you want those that aren't possible to be the closest thing... mitered. If you can't tell visually the difference, then it doesn't matter if you have an arc join or a mitered join but it may matter on some other join on the path.
Tav
On 15-10-2012 16:33, Tavmjong Bah wrote:
On Fri, 2012-10-12 at 23:11 +0200, Johan Engelen wrote:
I am starting to strongly dislike the miter fallback btw, simply because of it not being clear whether you have arc extension or a miter. Bevel fallback has a much better UI experience for me.
But that is exactly what you want. Think about a path with multiple line joins. You want all the line joins to look similar but not all the joins may be possible with the arc join so you want those that aren't possible to be the closest thing... mitered. If you can't tell visually the difference, then it doesn't matter if you have an arc join or a mitered join but it may matter on some other join on the path.
Can you give me a join where miter is possible but arc isn't (without a smidge tweaking the path to get the arc)? On the other hand, making the arc impossible by changing the curvature slightly may give a choice for "miter-type join" and "bevel type join". Perhaps it is nice to be able to intentionally make an arc extension impossible (because you tweaked the curvature slightly), to get a bevel on an otherwise "miter type" path.
The visual difference between miter and extrapolation is subtle, but the miter is almost always (very) ugly in my opinion. I find it very annoying to have to pay detailed attention to such ugliness (for which you may have to zoom in a bit) the whole time while modifying a path.
Did you try powerstroke with arc extension to see what fall-back you would like better? I will probably never seriously use powerstroke. So I cannot judge on these issues too well. It is simply something that pops up when I am playing with powerstroked paths.
Ciao, Johan
On 12-10-12 23:11, Johan Engelen wrote:
On 12-10-2012 14:59, Jasper van de Gronde wrote:
... To deal with zero-length handles, the easiest (and correct) method is probably to specify that the curvature is zero at the endpoint with the zero-length handle (if both handles are zero-length, then the Bézier curve forms a line segment). That this is correct can be derived from the fact that the unit tangent vector at the endpoint with a zero-length handle points in the same direction as the second derivative (so locally it's a straight line). This is a consequence of l'Hôpital's rule btw.
I don't think this is correct.
That observation /is/ :)
Note that the case of two zero-length handles or two coinciding handles of which one has zero-length gives a straight line (segment), though. So for that case it makes perfect sense to have zero curvature throughout (and this actually follows from the description below).
It is possible to make segments with and without a zero-length handle that look exactly the same.
It should not be, in general. (Fewer degrees of freedom.)
Also, as you are moving the handle closer and closer to the knot, it does not converge to zero curvature, in fact it tends to lead to higher curvature instead of lower curvature.
There is essentially a bit of instability here. Yes, if you approach it from most angles, then the curvature increases. However, if you follow l'Hôpital's rule to compute the unit tangent vector at t=0 (so the derivative divided by the norm of the derivative), or (which is a bit easier), the derivative of y w.r.t. x, then you see that the unit tangent vector at t=0 points to the second handle. If you then take the limit as P2 approaches P1 from the direction of P2 (or opposite), you get zero curvature.
Also (just as an observation), as the handle gets smaller, its influence decreases. So although locally you have a very large curvature, it's only over a very small portion of the curve.
Wouldn't l'Hopital imply that you can get away by using +1 higher derivs instead?
You're completely right. (If you intended taking the derivative of the numerator and denominator and dividing those.) However, higher derivatives can (and will) still be zero in this case, so this complicates things a bit.
However, if you make the first handle zero-length, and then compute the limit of the curvature as t goes to zero, then you find that the curvature is equal to det([P3-P1,P4-P1]) divided by something that is zero at t=0 and positive for t slightly above zero, as long as P3-P1 is not zero-length. Thus, if det([P3-P1,P4-P1])=0, (all points and handles on a line), then the curvature at t=0 is zero, and otherwise it is infinite with the sign of det([P3-P1,P4-P1]).
So, I stand corrected, the rule isn't zero-length=zero-curvature, but rather, a zero-length P1-P0 implies that the curvature at P0 is either -infinity, zero or +infinity, depending on the sign of det([P3-P1,P4-P1])=0. (Assuming at least some point does not coincide with P1.)
... One possible way to specify the restriction for this kind of join would be to limit the arc-length on either side of the join. The main problem is then joining the end points, as a line segment between the two is not guaranteed to not intersect the circles. Some experimentation suggests that it might be possible to define a sensible boundary using interpolation between the two end points that is guaranteed not to intersect either of the circles.
I have no clue what you are saying here. :-)
Okay, turns out my assumption about how miterlimit worked was wrong, but I still think it makes sense. Basically, when using a miter join, the miter can get infinitely large. This causes all sorts of problems, so "miterlimit" was introduced. Basically this says: "a miter larger than so and so can't be good". The solution then is to fall back to a bevel join... I had assumed it would just "cap" the miter (as this would still prevent it from being insanely large, while preventing a sudden jump from miter to bevel).
For the moment, assume that SVG had chosen to simply "cap" the miter. For example, one could restrict the length of both sides of the miter to the miterlimit and draw a straight line between the two. This should cause no further problems (at least in rendering, maybe there are other issues that caused the committee to not go down this route).
Now, when joining using arcs, it seems to make even more sense to simply "cap" the join. Otherwise you can have a nice curved join one minute and a bevel (or miter) join the next, seems a bit weird to me. So suppose that you simply "cap" the join. How do you go about capping it?
That brings us back to what I was saying. Because both sides of the join are curved, there is no guarantee that a straight line between the endpoints (of the limited sides of the join) does not cross either side of the join (which I think would look really weird). So you want some other kind of "cap". This is why I took a short look into finding a sensible cap by interpolating between both arcs. This looks promising, but a straightforward interpolation between the two arcs still has some problems. But feel free to ignore these fine points, the gist is that if one wanted to "cap" the join instead of falling back to a miter or bevel (and introducing discontinuous/unstable behaviour), then some thought needs to go into how to actually cap it.
But of course it might just be simplest to fall back to a miter or bevel.
On 16-10-2012 13:43, Jasper van de Gronde wrote:
On 12-10-12 23:11, Johan Engelen wrote:
On 12-10-2012 14:59, Jasper van de Gronde wrote:
... To deal with zero-length handles, the easiest (and correct) method is probably to specify that the curvature is zero at the endpoint with the zero-length handle (if both handles are zero-length, then the Bézier curve forms a line segment). That this is correct can be derived from the fact that the unit tangent vector at the endpoint with a zero-length handle points in the same direction as the second derivative (so locally it's a straight line). This is a consequence of l'Hôpital's rule btw.
I don't think this is correct.
That observation /is/ :)
Note that the case of two zero-length handles or two coinciding handles of which one has zero-length gives a straight line (segment), though. So for that case it makes perfect sense to have zero curvature throughout (and this actually follows from the description below).
Taking a very special case does not make for a very strong argument ;-) ;-) Technically I guess you are correct (perhaps depending on the definition of curvature?). I think we should use a more intuitive definition of curvature perhaps... If one would arc-length-reparametrise a zero-length handle segment, would it result in zero-curvature? In other words: if one reparametrises a segment, does that change the curvature, without visual differences?
It is possible to make segments with and without a zero-length handle that look exactly the same.
It should not be, in general. (Fewer degrees of freedom.)
I meant: zero-length handle segment ---> non-zero length handles segment. That goes in the direction of increasing degrees of freedom, so at least no worries for that matter. But perhaps it is indeed mathematically impossible. See attachment.
Also, as you are moving the handle closer and closer to the knot, it does not converge to zero curvature, in fact it tends to lead to higher curvature instead of lower curvature.
There is essentially a bit of instability here. Yes, if you approach it from most angles, then the curvature increases. However, if you follow l'Hôpital's rule to compute the unit tangent vector at t=0 (so the derivative divided by the norm of the derivative), or (which is a bit easier), the derivative of y w.r.t. x, then you see that the unit tangent vector at t=0 points to the second handle. If you then take the limit as P2 approaches P1 from the direction of P2 (or opposite), you get zero curvature.
Also (just as an observation), as the handle gets smaller, its influence decreases. So although locally you have a very large curvature, it's only over a very small portion of the curve.
Does that mean that as the handle goes to zero, it's region of influence tends to zero too and hence perhaps it is not very indicative of the visual curvature any more?
Wouldn't l'Hopital imply that you can get away by using +1 higher derivs instead?
You're completely right. (If you intended taking the derivative of the numerator and denominator and dividing those.) However, higher derivatives can (and will) still be zero in this case, so this complicates things a bit.
(simply do the same "trick" again in those cases? ;)
However, if you make the first handle zero-length, and then compute the limit of the curvature as t goes to zero, then you find that the curvature is equal to det([P3-P1,P4-P1]) divided by something that is zero at t=0 and positive for t slightly above zero, as long as P3-P1 is not zero-length. Thus, if det([P3-P1,P4-P1])=0, (all points and handles on a line), then the curvature at t=0 is zero, and otherwise it is infinite with the sign of det([P3-P1,P4-P1]).
So, I stand corrected, the rule isn't zero-length=zero-curvature, but rather, a zero-length P1-P0 implies that the curvature at P0 is either -infinity, zero or +infinity, depending on the sign of det([P3-P1,P4-P1])=0. (Assuming at least some point does not coincide with P1.)
I have an example attached where there are two paths: one with zero-length handle, and one 'normal' path. They are visually *very* similar; if you zoom in you will notice a small difference in angle and the end of the path on the right-hand side. I think the normal path has a non-zero curvature (it is not straight at the end), so I thought the zero-length path would have the same curvature.
Now there are two different viewpoints to a solution: - math. SVG definition - user Don't know which one to take...
Cheers, Johan
On 16-10-12 20:24, Johan Engelen wrote:
On 16-10-2012 13:43, Jasper van de Gronde wrote:
...
It is possible to make segments with and without a zero-length handle that look exactly the same.
It should not be, in general. (Fewer degrees of freedom.)
I meant: zero-length handle segment ---> non-zero length handles segment. That goes in the direction of increasing degrees of freedom, so at least no worries for that matter. But perhaps it is indeed mathematically impossible. See attachment.
Now I get it. Yes, but... (see below).
Also (just as an observation), as the handle gets smaller, its influence decreases. So although locally you have a very large curvature, it's only over a very small portion of the curve.
Does that mean that as the handle goes to zero, it's region of influence tends to zero too and hence perhaps it is not very indicative of the visual curvature any more?
Exactly right.
Wouldn't l'Hopital imply that you can get away by using +1 higher derivs instead?
You're completely right. (If you intended taking the derivative of the numerator and denominator and dividing those.) However, higher derivatives can (and will) still be zero in this case, so this complicates things a bit.
(simply do the same "trick" again in those cases? ;)
Yes, you can do that, but that's basically a pretty convoluted way of doing the same thing as what I did in a slightly different way. Basically what happens is that the denominator typically stays zero for "longer" then the numerator, unless you have a completely straight line (segment).
However, if you make the first handle zero-length, and then compute the limit of the curvature as t goes to zero, then you find that the curvature is equal to det([P3-P1,P4-P1]) divided by something that is zero at t=0 and positive for t slightly above zero, as long as P3-P1 is not zero-length. Thus, if det([P3-P1,P4-P1])=0, (all points and handles on a line), then the curvature at t=0 is zero, and otherwise it is infinite with the sign of det([P3-P1,P4-P1]).
So, I stand corrected, the rule isn't zero-length=zero-curvature, but rather, a zero-length P1-P0 implies that the curvature at P0 is either -infinity, zero or +infinity, depending on the sign of det([P3-P1,P4-P1])=0. (Assuming at least some point does not coincide with P1.)
I have an example attached where there are two paths: one with zero-length handle, and one 'normal' path. They are visually *very* similar; if you zoom in you will notice a small difference in angle and the end of the path on the right-hand side. I think the normal path has a non-zero curvature (it is not straight at the end), so I thought the zero-length path would have the same curvature.
Now there are two different viewpoints to a solution:
- math. SVG definition
- user
Don't know which one to take...
Now there's the real problem. I even asked a question related to this on math.stackexchange, as it was driving me crazy. Essentially the problem is that curves with zero-length handles do tend to have infinite curvature at the endpoint(s) with a zero-length handle, but the curvature grows very quickly over a very short length of the segment. So visually, you hardly see anything. Put differently, the slope has a non-zero derivative at the endpoint, while the norm of the derivative is zero, so the slope changes by some finite amount over an infinitesimally small length, leading to infinite curvature, but a finite (and typically quite small) change in slope.
So essentially you have the extremely weird situation where a slope that looks very smooth and (almost) straight, can actually have infinite curvature at its endpoints (I think in principle this can also happen elsewhere, but that's less of a problem in this context).
The problem with taking an approximation of the path is that I'm not entirely sure how "stable" this is. So would taking a slightly different approximation give you a completely different curvature, or is there some "natural" curvature that can be defined? In fact, I've just tried fitting a quadratic curve through the first 1/3 of a Bézier curve with a zero-length handle (at the first node), and I can get a huge range of curvatures, without a big difference in fitting quality.
Of course this can always be "solved" by simply prescribing an approximation method. One thing you could try is to basically take a finite difference approximation to the curvature over a predefined range of the curve (if the SVG spec would do something like this, the range would probably have to be specified in the spec). For example, take the angle of the curve at t=0 and t=1/3, take the difference and divide by the arc-length. You could experiment with the range, or even try to do a "higher order" approximation. I'm not entirely sure what this would accomplish though.
On Mon, Oct 15, 2012 at 11:23 PM, Johan Engelen <jbc.engelen@...2592...> wrote:
The visual difference between miter and extrapolation is subtle, but the miter is almost always (very) ugly in my opinion. I find it very annoying to have to pay detailed attention to such ugliness (for which you may have to zoom in a bit) the whole time while modifying a path.
FWIW I also feel the difference between the desired rendering and fallback rendering should be clear enough so the user knows s/he hasn't really got an arc. My vote for bevel as fallback if tapered extrapolation is not possible (but why wouldn't it be?).
On 14-10-2012 18:05, Shriramana Sharma wrote:
On Sat, Oct 13, 2012 at 2:41 AM, Johan Engelen <jbc.engelen@...2592...> wrote:
I am starting to strongly dislike the miter fallback btw, simply because of it not being clear whether you have arc extension or a miter. Bevel fallback has a much better UI experience for me.
I also prefer bevel fallback FWIW, but are we talking about the "extrapolated" join or the "extrapolated arc" thing (w.r.t. the example SVG)?
We were talking about the fallback for "extrapolated arc".
And please tell me whether I have understood correctly that extrapolated arc is more like bevel and basically ensures that all bevels are straightlines
Extrapolated arc = extrapolate with a circle segment. With continuity of curvature/smoothness. (the whole arc has the same curvature as path join point.
whereas extrapolated is more like miter and just ensures continuity of curvature? Personally I feel extrapolated arc is too extreme (too many sharp ends... Naah!)
Extrapolated = extrapolate by mirroring the path segment. This also results in continuity of curvature and smoothness.
-Johan
participants (7)
-
Alexandre Prokoudine -
Jasper van de Gronde -
Johan Engelen -
Martin Owens -
Shriramana Sharma -
SorinN -
Tavmjong Bah