Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: Johan Engelen <jbc.engelen@sw...>  20121006 20:26:44

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 
From: Tavmjong Bah <tavmjong@fr...>  20121007 05:49:47

On Sat, 20121006 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 linejoin... but not properly (it only works at 100% zoom at the moment). Tav 
From: Johan Engelen <jbc.engelen@sw...>  20121007 19:05:39
Attachments:
arc.svg

On 7102012 7:49, Tavmjong Bah wrote: > On Sat, 20121006 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 > linejoin... 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 
From: Jasper van de Gronde <th.gronde@hc...>  20121008 08:35:20

On 071012 21:05, Johan Engelen wrote: > On 7102012 7:49, Tavmjong Bah wrote: >> On Sat, 20121006 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 >> linejoin... 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. arclength (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 "arclength" 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. 
From: Johan Engelen <jbc.engelen@sw...>  20121008 23:04:16

On 8102012 10:35, Jasper van de Gronde wrote: > On 071012 21:05, Johan Engelen wrote: >> On 7102012 7:49, Tavmjong Bah wrote: >>> On Sat, 20121006 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 >>> linejoin... 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. > arclength (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 "arclength" 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 arclength reparametrisation, thanks for the hint! Arclength 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 
From: Johan Engelen <jbc.engelen@sw...>  20121009 21:37:58
Attachments:
extrapolated_arc_cusp.svg

On 9102012 1:04, Johan Engelen wrote: > On 8102012 10:35, Jasper van de Gronde wrote: >> On 071012 21:05, Johan Engelen wrote: >>> On 7102012 7:49, Tavmjong Bah wrote: >>>> On Sat, 20121006 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 >>>> linejoin... 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. >> arclength (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 "arclength" 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 arclength > reparametrisation, thanks for the hint! Arclength 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 zerolength 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 
From: Shriramana Sharma <samjnaa@gm...>  20121014 15:59:32

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.  Shriramana Sharma 
From: Johan Engelen <jbc.engelen@sw...>  20121009 21:55:12
Attachments:
extrapolated_arc_cusp.svgz

On 9102012 1:04, Johan Engelen wrote: > On 8102012 10:35, Jasper van de Gronde wrote: >> On 071012 21:05, Johan Engelen wrote: >>> On 7102012 7:49, Tavmjong Bah wrote: >>>> On Sat, 20121006 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 >>>> linejoin... 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. >> arclength (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 "arclength" 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 arclength > reparametrisation, thanks for the hint! Arclength 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 zerolength 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 
From: Tavmjong Bah <tavmjong@fr...>  20121010 07:52:30

On Tue, 20121009 at 23:37 +0200, Johan Engelen wrote: > On 9102012 1:04, Johan Engelen wrote: > > On 8102012 10:35, Jasper van de Gronde wrote: > >> On 071012 21:05, Johan Engelen wrote: > >>> On 7102012 7:49, Tavmjong Bah wrote: > >>>> On Sat, 20121006 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 > >>>> linejoin... 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. > >> arclength (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 "arclength" 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 arclength > > reparametrisation, thanks for the hint! Arclength 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 zerolength 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 
From: Martin Owens <doctormo@gm...>  20121010 16:24:08

On Tue, 20121009 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. :) Martin, 
From: Johan Engelen <jbc.engelen@sw...>  20121010 17:28:35

On 10102012 18:23, Martin Owens wrote: > On Tue, 20121009 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 
From: Johan Engelen <jbc.engelen@sw...>  20121010 21:08:39

On 10102012 9:52, Tavmjong Bah wrote: > On Tue, 20121009 at 23:37 +0200, Johan Engelen wrote: >> On 9102012 1:04, Johan Engelen wrote: >>> On 8102012 10:35, Jasper van de Gronde wrote: >>>> On 071012 21:05, Johan Engelen wrote: >>>>> On 7102012 7:49, Tavmjong Bah wrote: >>>>>> On Sat, 20121006 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 >>>>>> linejoin... 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. >>>> arclength (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 "arclength" 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 arclength >>> reparametrisation, thanks for the hint! Arclength 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 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 zerolength 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 mirrorextrapolate allows for some funky looking stuff that you can't get with circleextrapolate, but perhaps it is too extreme to be useful :P Cheers, Johan 
From: Johan Engelen <jbc.engelen@sw...>  20121010 21:24:58

On 10102012 23:08, Johan Engelen wrote: > On 10102012 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 
From: Martin Owens <doctormo@gm...>  20121010 22:21:27

On Wed, 20121010 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, 
From: SorinN <nemes.sorin@gm...>  20121011 03:26:19

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@...>: > On Wed, 20121010 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/newrelicdev2dev > _______________________________________________ > Inkscapedevel mailing list > Inkscapedevel@... > https://lists.sourceforge.net/lists/listinfo/inkscapedevel  Nemes Ioan Sorin 
From: Martin Owens <doctormo@gm...>  20121011 11:35:26

On Thu, 20121011 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, 
From: Jasper van de Gronde <th.gronde@hc...>  20121012 12:59:22

On 20121010 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 illdefined 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 zerolength handles, the easiest (and correct) method is probably to specify that the curvature is zero at the endpoint with the zerolength handle (if both handles are zerolength, 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 zerolength 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 zerolength 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 arclength 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. 
From: Alexandre Prokoudine <alexandre.prokoudine@gm...>  20121012 13:34:26

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 
From: Tavmjong Bah <tavmjong@fr...>  20121012 13:53:12

On Fri, 20121012 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 
From: Johan Engelen <jbc.engelen@sw...>  20121012 21:11:55

On 12102012 14:59, Jasper van de Gronde wrote: > On 20121010 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 illdefined 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 zerolength handles, the easiest (and correct) method is > probably to specify that the curvature is zero at the endpoint with the > zerolength handle (if both handles are zerolength, 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 zerolength > 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 zerolength 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 zerolength 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 arclength 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 
From: Shriramana Sharma <samjnaa@gm...>  20121013 15:18:27

On Thu, Oct 11, 2012 at 2:38 AM, Johan Engelen <jbc.engelen@...> 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.  Shriramana Sharma 
From: Johan Engelen <jbc.engelen@sw...>  20121013 16:05:26

On 13102012 17:18, Shriramana Sharma wrote: > On Thu, Oct 11, 2012 at 2:38 AM, Johan Engelen > <jbc.engelen@...> 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/lpepowerstroke.cpp The arc extrapolation code starts at line 409 ("case LINEJOIN_EXTRP_MITER_ARC:") Cheers, Johan 
From: Shriramana Sharma <samjnaa@gm...>  20121014 16:06:06

On Sat, Oct 13, 2012 at 2:41 AM, Johan Engelen <jbc.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. 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!)  Shriramana Sharma 
From: Johan Engelen <jbc.engelen@sw...>  20121021 22:03:50

On 14102012 18:05, Shriramana Sharma wrote: > On Sat, Oct 13, 2012 at 2:41 AM, Johan Engelen > <jbc.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. > 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 
From: Tavmjong Bah <tavmjong@fr...>  20121015 14:34:05

On Fri, 20121012 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 
From: Johan Engelen <jbc.engelen@sw...>  20121015 17:53:45

On 15102012 16:33, Tavmjong Bah wrote: > On Fri, 20121012 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 "mitertype 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 fallback 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 
From: Shriramana Sharma <samjnaa@gm...>  20121021 07:19:04

On Mon, Oct 15, 2012 at 11:23 PM, Johan Engelen <jbc.engelen@...> 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?).  Shriramana Sharma 
From: Jasper van de Gronde <th.gronde@hc...>  20121016 11:43:42

On 121012 23:11, Johan Engelen wrote: > On 12102012 14:59, Jasper van de Gronde wrote: >> ... >> To deal with zerolength handles, the easiest (and correct) method is >> probably to specify that the curvature is zero at the endpoint with the >> zerolength handle (if both handles are zerolength, 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 zerolength >> 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 zerolength handles or two coinciding handles of which one has zerolength 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 zerolength 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 zerolength, and then compute the limit of the curvature as t goes to zero, then you find that the curvature is equal to det([P3P1,P4P1]) divided by something that is zero at t=0 and positive for t slightly above zero, as long as P3P1 is not zerolength. Thus, if det([P3P1,P4P1])=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([P3P1,P4P1]). So, I stand corrected, the rule isn't zerolength=zerocurvature, but rather, a zerolength P1P0 implies that the curvature at P0 is either infinity, zero or +infinity, depending on the sign of det([P3P1,P4P1])=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 arclength 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. 
From: Johan Engelen <jbc.engelen@sw...>  20121016 18:25:01
Attachments:
curvature.svg

On 16102012 13:43, Jasper van de Gronde wrote: > On 121012 23:11, Johan Engelen wrote: >> On 12102012 14:59, Jasper van de Gronde wrote: >>> ... >>> To deal with zerolength handles, the easiest (and correct) method is >>> probably to specify that the curvature is zero at the endpoint with the >>> zerolength handle (if both handles are zerolength, 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 zerolength >>> 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 zerolength handles or two coinciding handles > of which one has zerolength 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 arclengthreparametrise a zerolength handle segment, would it result in zerocurvature? 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 zerolength handle that look exactly the same. > It should not be, in general. (Fewer degrees of freedom.) I meant: zerolength handle segment > nonzero 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 zerolength, and then compute the > limit of the curvature as t goes to zero, then you find that the > curvature is equal to det([P3P1,P4P1]) divided by something that is > zero at t=0 and positive for t slightly above zero, as long as P3P1 is > not zerolength. Thus, if det([P3P1,P4P1])=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([P3P1,P4P1]). > > So, I stand corrected, the rule isn't zerolength=zerocurvature, but > rather, a zerolength P1P0 implies that the curvature at P0 is either > infinity, zero or +infinity, depending on the sign of > det([P3P1,P4P1])=0. (Assuming at least some point does not coincide > with P1.) > I have an example attached where there are two paths: one with zerolength 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 righthand side. I think the normal path has a nonzero curvature (it is not straight at the end), so I thought the zerolength 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 
From: Jasper van de Gronde <th.gronde@hc...>  20121017 07:54:19

On 161012 20:24, Johan Engelen wrote: > On 16102012 13:43, Jasper van de Gronde wrote: >> ... >>> It is possible to make segments with and >>> without a zerolength handle that look exactly the same. >> It should not be, in general. (Fewer degrees of freedom.) > > I meant: zerolength handle segment > nonzero 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 zerolength, and then compute the >> limit of the curvature as t goes to zero, then you find that the >> curvature is equal to det([P3P1,P4P1]) divided by something that is >> zero at t=0 and positive for t slightly above zero, as long as P3P1 is >> not zerolength. Thus, if det([P3P1,P4P1])=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([P3P1,P4P1]). >> >> So, I stand corrected, the rule isn't zerolength=zerocurvature, but >> rather, a zerolength P1P0 implies that the curvature at P0 is either >> infinity, zero or +infinity, depending on the sign of >> det([P3P1,P4P1])=0. (Assuming at least some point does not coincide >> with P1.) >> > > I have an example attached where there are two paths: one with > zerolength 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 righthand side. I think the normal path has > a nonzero curvature (it is not straight at the end), so I thought the > zerolength 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 zerolength handles do tend to have infinite curvature at the endpoint(s) with a zerolength 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 nonzero 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 zerolength 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 arclength. 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. 