Recent change to ellipse to path conversion method?
Earlier today I found one small bug related to images written to WMF files and posted it in launchpad. But while working on that noticed that there was also another binary change in the output that didn't correspond to anything I could see in the images. A careful byte by byte comparison of EMF and WMF output from the lp988601 and current trunk branches showed that outside of my code there has been a change, where the paths returned on ellipse to path conversions are not as they once were. In emf-print.cpp in the print_simple_shape() routine a print statement was added after the call to pathv_to_linear_and_cubic_beziers() and the loop which adds up nodes, lines, and curves. For the exact same ellipse (long axis aligned with x, short with y, axis ratio about 2:1) this is what was found:
nodes lines curves lp988601 5 0 4 trunk 9 0 8
They start at the same point, but differ from there. Tried it again with perfect circles and got the same result.
The strange thing is that there is no change at all to the geom.cpp file, where pathv_to_linear_and_cubic_beziers() is coded.
I also checked to see if anything similar could be seen in the GUI, and it sort of could be. Select the ellipse, select "stroke to path", then edit points. The points on the ellipse are in different places in the two branches, and there are different numbers of points. For lp988602 there is one point on the end of each axis plus one point in roughly the center of each quadrant. For trunk there are the same points on the ends of the axis, plus two points within each quadrant, and these are clustered towards the "sharp" ends of the ellipse.
Is this change intentional???
Thank you,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
Hi, intentional is the wrong word. This has to do with the change that ellipses are represented now as true elliptical arcs. These are converted implicitly to several Bezier segments. pathv_to_linear_and_cubic_beziers() does this conversion using a certain "tolerance". Thus, if the elliptical arc and the bezier curve differ too much, a new node is inserted automatically. Currently I'm thinking about a solution, as this is not quite user-friendly. One of my ideas was that we could introduce a new tab in the settings dialog where you can choose the tolerances for these path conversions yourself. So the average user could choose a high tolerance and get fewer (at least 4) nodes, the cad user who needs high precision, could set the tolerance to a small value.
What do you think?
Regards, Markus
-----Ursprüngliche Nachricht----- Von: mathog [mailto:mathog@...1176...] Gesendet: Freitag, 18. Oktober 2013 23:25 An: Inkscape Devel Betreff: [Inkscape-devel] Recent change to ellipse to path conversion method?
Earlier today I found one small bug related to images written to WMF files and posted it in launchpad. But while working on that noticed that there was also another binary change in the output that didn't correspond to anything I could see in the images. A careful byte by byte comparison of EMF and WMF output from the lp988601 and current trunk branches showed that outside of my code there has been a change, where the paths returned on ellipse to path conversions are not as they once were. In emf-print.cpp in the print_simple_shape() routine a print statement was added after the call to pathv_to_linear_and_cubic_beziers() and the loop which adds up nodes, lines, and curves. For the exact same ellipse (long axis aligned with x, short with y, axis ratio about 2:1) this is what was found:
nodes lines curves lp988601 5 0 4 trunk 9 0 8
They start at the same point, but differ from there. Tried it again with perfect circles and got the same result.
The strange thing is that there is no change at all to the geom.cpp file, where pathv_to_linear_and_cubic_beziers() is coded.
I also checked to see if anything similar could be seen in the GUI, and it sort of could be. Select the ellipse, select "stroke to path", then edit points. The points on the ellipse are in different places in the two branches, and there are different numbers of points. For lp988602 there is one point on the end of each axis plus one point in roughly the center of each quadrant. For trunk there are the same points on the ends of the axis, plus two points within each quadrant, and these are clustered towards the "sharp" ends of the ellipse.
Is this change intentional???
Thank you,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
---------------------------------------------------------------------------- -- October Webinars: Code for Performance Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register > http://pubads.g.doubleclick.net/gampad/clk?id=60135031&iu=/4140/ostg.clk... _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
On 18-Oct-2013 14:58, Markus Engel wrote:
This has to do with the change that ellipses are represented now as true elliptical arcs. These are converted implicitly to several Bezier segments.
As far as the output to other formats goes this was always the case, just not to as many segments as now.
pathv_to_linear_and_cubic_beziers() does this conversion using a certain "tolerance".
Right, but that code didn't change, so I assume this is the result of the default tolerance being made smaller.
Currently I'm thinking about a solution, as this is not quite user-friendly. One of my ideas was that we could introduce a new tab in the settings dialog where you can choose the tolerances for these path conversions yourself.
That sounds good. Can the default value please go back to where it was? I don't recall hearing a lot of people complaining about a lack of precision in the representation of ellipses and the tolerance change resulted in unexpected output differences.
I suppose you also need to make a distinction between what is going on on the drawing surface and the precision on a forced conversion to another format. Lots of graphics drivers have precision settings that affect what is seen on the display but which do not change the underlying data representation. This is super common for "smoothness" settings on 3D rendering, for instance. The current change seems to affect both. "Screen tolerance" and "Conversion tolerance", if you will.
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
As far as the output to other formats goes this was always the case, just not to as many segments as now. Right, but that code didn't change, so I assume this is the result of the default tolerance being made smaller.
The default tolerance didn't change but the code in sp-ellipse.cpp did. A few revisions ago the ellipses were created by explicitly calculating four Bezier (!) curves so there was no need for any conversion. Now I changed this to creating elliptical arcs and let 2geom do the calculation. Have a look at this bug report: https://bugs.launchpad.net/inkscape/+bug/1235504 . Try the patch I attached there (e_to_b.patch). This increases the tolerance to an arbitrary value of 1, so only for quite big ellipses more than four nodes are generated. Of course this value should be accessible via a settings tab later. Would this be an acceptable solution then?
Regards, Markus
-----Ursprüngliche Nachricht----- Von: system user for webserver-base [mailto:apache@...2855...] Im Auftrag von mathog Gesendet: Samstag, 19. Oktober 2013 00:19 An: Markus Engel Cc: 'Inkscape Devel' Betreff: Re: AW: [Inkscape-devel] Recent change to ellipse to path conversion method?
On 18-Oct-2013 14:58, Markus Engel wrote:
This has to do with the change that ellipses are represented now as true elliptical arcs. These are converted implicitly to several Bezier segments.
As far as the output to other formats goes this was always the case, just not to as many segments as now.
pathv_to_linear_and_cubic_beziers() does this conversion using a certain "tolerance".
Right, but that code didn't change, so I assume this is the result of the default tolerance being made smaller.
Currently I'm thinking about a solution, as this is not quite user-friendly. One of my ideas was that we could introduce a new tab in the settings dialog where you can choose the tolerances for these path conversions yourself.
That sounds good. Can the default value please go back to where it was? I don't recall hearing a lot of people complaining about a lack of precision in the representation of ellipses and the tolerance change resulted in unexpected output differences.
I suppose you also need to make a distinction between what is going on on the drawing surface and the precision on a forced conversion to another format. Lots of graphics drivers have precision settings that affect what is seen on the display but which do not change the underlying data representation. This is super common for "smoothness" settings on 3D rendering, for instance. The current change seems to affect both. "Screen tolerance" and "Conversion tolerance", if you will.
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
On 18-Oct-2013 15:32, Markus Engel wrote:
The default tolerance didn't change but the code in sp-ellipse.cpp did. A few revisions ago the ellipses were created by explicitly calculating four Bezier (!) curves so there was no need for any conversion. Now I changed this to creating elliptical arcs and let 2geom do the calculation. Have a look at this bug report: https://bugs.launchpad.net/inkscape/+bug/1235504 . Try the patch I attached there (e_to_b.patch).
I see it, but don't understand why:
Geom::cubicbezierpath_from_sbasis
generates so many beziers for an elliptical arc with a fit parameter of 0.1.
Ellipses are approximated very well by 4 beziers. Presumably the EllipticalArcs you use now are perfect segments of an Ellipse. (Otherwise, why bother with them? How many are you using, 4?) I would have assumed that an Elliptical arc perfectly representing 1/4 of an ellipse should have converted as well to a single Bezier curve as 1/4 of the ellipse did. Or was the conversion from some other function and not cubicbezierpath_from_sbasis()? The patch changes the fit parameter from 0.1 to 1.0, which seems like an awfully big change to make it do what you want. Is it maybe the case that somehow the cubicbezierpath_from_sbasis() algorithm starts with the assumption that it must use at least two bezier segments, that is, that it must split the curve into >=2 Beziers, and only omits the second one with an extreme parameter change?
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
Hi mathog,
On Fri, Oct 18, 2013 at 04:07:16PM -0700, mathog wrote:
I see it, but don't understand why:
Geom::cubicbezierpath_from_sbasis
generates so many beziers for an elliptical arc with a fit parameter of 0.1.
Because Geom::cubicbezierpath_from_sbasis is fitting the parameterisation rather than the geometric shape. That is, we think of a path as a pair of functions X(t), Y(t) with t in [0,1], but any function t(u) such that t([0,1]) = [0,1] gives another path X(t(u)), Y(t(u)) which is the same path. There is a best path approximation if we're allowed to change the parameterisation, and for circular arcs this has been worked out explicitly. This function, however, minimises |X(t) - Bezier(t)| over t, rather than |X(t) - Bezier(u)| over t,u.
There have been papers published on ways to do this efficiently in general (one search term is geometric interpolation). Nobody has implemented a competitive algorithm. I would recommend modifying the ellipse code to use the known approximation directly rather than going via sbasis (or equivalently, generating the approximation in sbasis form rather than using sin,cos in which case Geom::cubicbezierpath_from_sbasis should be the identity).
regards, njh
On 20-Oct-2013 14:35, Nathan Hurst wrote:
There have been papers published on ways to do this efficiently in general (one search term is geometric interpolation). Nobody has implemented a competitive algorithm. I would recommend modifying the ellipse code to use the known approximation directly rather than going via sbasis (or equivalently, generating the approximation in sbasis form rather than using sin,cos in which case Geom::cubicbezierpath_from_sbasis should be the identity).
Recapitulating:
1. The original ellipse -> bezier conversion used one of the worked out solutions which are calculated directly from the ellipse parameters. Probably something like this:
http://www.spaceroots.org/documents/ellipse/
It produced four beziers for any ellipse. These met the needs of most users.
2. Higher precision curve drawing of ellipses was required by some end users for CAD purposes, so the method was changed. This resulted in the default bezier representation of an ellipse being more complex (>4 beziers) than needed for general use. The new method uses a fit parameter which must be changed in a major way from its default value in order to return to beziers similar to (1), and there is currently no way to do this in the GUI. (Unsure: that same parameter is used for other curve -> bezier conversions? Does the end user need to be able to adjust the fit parameter?)
So far so good?
The issue then is how to allow those who need it to obtain a higher precision conversion to beziers without requiring that the average user know anything about it. I suggest that the usual solution to this sort of problem, as applied to Inkscape, would be to modify the toolbar for elliptical drawing to add a "precision" field that normally reads "Default", with other options perhaps called "CAD Low","CAD Medium","CAD High". Each corresponds to a parameter value, but that is not shown to the end user, in case things need to be changed around again at some point in future. Exposing the parameter value is unlikely to be helpful to most users, since it probably will not correspond in a simple way to an easily comprehended measure of error. The bezier generating code looks at this parameter, and when it sees the one corresponding to "Default" it uses the original algorithm, for all of the others it uses Geom::cubicbezierpath_from_sbasis.
In terms of usability that should be fine, and adding the control will not be hard. However, algorithmically I am guessing that Geom::cubicbezierpath_from_sbasis is not as efficient as using some partially precalculated method which uses the a/b ratio of the ellipse in question, at least for whole ellipses. For circles in particular symmetry suggests that there must be an extremely efficient method of determining the best set of Beziers for a given measure of fit.
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
- The original ellipse -> bezier conversion used one of the worked out solutions which are calculated directly from the ellipse parameters.
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/12550/src/sp-e...
for (s = this->start; s < this->end; s += M_PI_2) { double e = s + M_PI_2;
if (e > this->end) { e = this->end; }
len = 4*tan((e - s)/4)/3; double x0 = cos(s); double y0 = sin(s); double x1 = x0 + len * cos(s + M_PI_2); double y1 = y0 + len * sin(s + M_PI_2); double x3 = cos(e); double y3 = sin(e); double x2 = x3 + len * cos(e - M_PI_2); double y2 = y3 + len * sin(e - M_PI_2);
curve->curveto(x1,y1, x2,y2, x3,y3); }
It produced four beziers for any ellipse. These met the needs of most users.
That's correct.
- Higher precision curve drawing of ellipses was required by some end users for CAD purposes, so the method was changed.
It wasn't required (it's a nice feature though), but using 2geom for calculation is just so much easier and the preferred way to go: Geom::Circle circle(0, 0, 1); Geom::PathVector path;
circle.getPath(path);
curve = new SPCurve(path); curve->closepath(); That's it.
This resulted in the default bezier representation of an ellipse being more complex (>4 beziers) than needed for general use. The new method uses a fit parameter which must be changed in a major way from its default value in order to return to beziers similar to (1), and there is currently no way to do this in the GUI.
Right.
(Unsure: that same parameter is used for other curve -> bezier conversions? Does the end user need to be able to adjust the fit parameter?)
As soon as you modify a path using the node tool, all the curves the path consists of are converted to cubic Bezier curves. Currently, for all these conversions the fit parameter is 0.1.
The issue then is how to allow those who need it to obtain a higher precision conversion to beziers without requiring that the average user know anything about it. I suggest that the usual solution to this sort of problem, as applied to Inkscape, would be to modify the toolbar for elliptical drawing to add a "precision" field that normally reads "Default", with other options perhaps called "CAD Low","CAD Medium","CAD High". Each corresponds to a parameter value, but that is not shown to the end user, in case things need to be changed around again at some point in future. Exposing the parameter value is unlikely to be helpful to most users, since it probably will not correspond in a simple way to an easily comprehended measure of error. The bezier generating code looks at this parameter, and when it sees the one corresponding to "Default" it uses the original algorithm, for all of the others it uses Geom::cubicbezierpath_from_sbasis.
Putting the precision settting into the settings dialog seems better to me. Either you need to increase it or you don't. Usually, you won't change it all the time. So the average user won't even notice this option exists.
Regards, Markus
On 21-Oct-2013 14:34, Markus Engel wrote:
Putting the precision setting into the settings dialog seems better to me.
Do you mean
edit->preferences->shapes->ellipse #add to existing entry
or
edit->preferences->behavior->Path conversion #new entry in menu
or some other place?
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
On 21-Oct-2013 15:32, Markus Engel wrote:
edit->preferences->behavior->Path conversion #new entry in menu
That'd be the right place I think.
That would be fine by me.
Regards,
David Mathog mathog@...1176... Manager, Sequence Analysis Facility, Biology Division, Caltech
after looking a bit at the routine sbasis-to-bezier.cpp, it appears that the tolerance tol is expressed in absolute units such as pixels, rather than being relative to the size of the object. So it will be more difficult to satisfy for large objects. Is this a case where we could consider a relative tolerance, such as 0.001 of the radius or somesuch? as far as I understand it, the conversion of Beziers to sbasis, and vice-versa, is always lossless, so the issue should only arise for arcs, I believe. (If at all humanly possible, I think options in the Preferences to choose this tolerance should be avoided at all costs, on the grounds that no one will know what this means.)
Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Recent-change-to-ellipse-to-path-conversion... Sent from the Inkscape - Dev mailing list archive at Nabble.com.
I think one could argue that the current formula for calculating the error, tail_error(B, 2), in build_from_sbasis() in sbasis-to-bezier.cpp is unnecessarily pessimistic, due to recent changes in the code. The tolerance on the error is 0.1. The error is linear in the radius of the arc. The dividing point in switching from 4 beziers to 8, for a full circle, occurs at r = 8.18. The dividing point in switching from 8 beziers to 16, for a full circle, occurs at r = 107.4. This can be confirmed using Path->Object-To-Path. Numerical tests at different arc angles have indicated that the tail_error function is roughly given by 0.0026*r*(theta)^4, where theta is in radians. This is consistent with the way in which the Bezier approximation used to be done. Recalling a previous thread on this subject: http://article.gmane.org/gmane.comp.graphics.inkscape.devel/35435 the arm length of the Bezier approximation to an arc was given by:
d/r = theta/3, where d = Bezier control arm length
The resulting fit will be worst at t=0.5 and the Bezier radius at this point will be:
r(t = 0.5) = cos(theta/2) + (theta/4)*sin(theta/2)
The error, for a unit circle, is roughly given by:
error = -(theta)^4/24/16
which is consistent with the previous numerical tests of tail_error.
The code in sbasis-to-bezier.cpp has been modifed (lib2geom rev 2122) to use a different approach to the fit, one which fits the sbasis curve at t=0.5. In the case of arcs, this is consistent with a Bezier arm length of:
d/r = 4*tan(theta/4)/3
The Bezier radius will be correct at t = 0, 0.5, and 1. The maximum error in radius will occur at t values which satisfy the equation 6*t*(1-t) = 1. The maximum radius is given by:
r^2 = 1 + (4/27)*(sin(theta/4))^6/(cos(theta/4))^2
The error, for a unit circle, is roughly given by:
error = (2/27)*(theta/4)^6
This is significantly smaller than the previous estimate (about 55 times smaller for an arc of 90 degrees), and would allow larger arc radii to be used without subdivision of the Bezier curves.
Unfortunately, I do not have sufficient math fu to do this type of analysis directly in the sbasis representation, but I think it would be worthwhile to try to perform such an error analysis.
Cheers, Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Recent-change-to-ellipse-to-path-conversion... Sent from the Inkscape - Dev mailing list archive at Nabble.com.
The behaviour of the tail_error(B, n) function in build_from_sbasis() in the file sbasis-to-bezier.cpp has been reevaluated. The term tail_error(B, 2) is too large since it is of order 4 in theta, for an arc, while the error currently produced is of order 6 in theta. For this reason the term tail_error(B, 3) was investigated numerically to see how it behaves. By numerical printouts at different theta, it was found that for a unit circle the tail_error(B, 3) term is roughly given by : 0.000022*(theta)^6. This agrees surprisingly well with the formula given above for the case where the sbasis is fit at t = 0.5. The formula given above was: error = (2/27)*(theta/4)^6. The difference between these results is only 20%, which I find surprising given the very different histories of the two calculations. In any event, I would like to propose that the term tail_error(B, 3) be used to determine the error estimate when bisecting the sbasis curves to meet the required tolerance. If this is done, numerical tests indicate that the dividing point in switching from 4 Beziers to 8 Beziers for a full circle will occur at r = 407 instead of the current r = 8.18.
cheers, Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Recent-change-to-ellipse-to-path-conversion... Sent from the Inkscape - Dev mailing list archive at Nabble.com.
On Sat, Nov 30, 2013 at 06:50:06AM -0800, alvinpenner wrote:
The behaviour of the tail_error(B, n) function in build_from_sbasis() inthe file sbasis-to-bezier.cpp has been reevaluated. The term tail_error(B, 2) is too large since it is of order 4 in theta, for an arc, while the error currently produced is of order 6 in theta. For this reason the term tail_error(B, 3) was investigated numerically to see how it behaves. By numerical printouts at different theta, it was found that for a unit circle the tail_error(B, 3) term is roughly given by : 0.000022*(theta)^6. This agrees surprisingly well with the formula given above for the case where the sbasis is fit at t = 0.5. The formula given above was: error = (2/27)*(theta/4)^6. The difference between these results is only 20%, which I find surprising given the very different histories of the two calculations. In any event, I would like to propose that the term tail_error(B, 3) be used to determine the error estimate when bisecting the sbasis curves to meet the required tolerance. If this is done, numerical tests indicate that the dividing point in switching from 4 Beziers to 8 Beziers for a full circle will occur at r = 407 instead of the current r = 8.18.
Hi Alvin,
Good sluthing!
This is puzzling, I think it must be due to the fact that you are using geometric subdivision (putting the new control points on the circle) rather than parametric (subdividing the higher order splines), because the tail_error(B, 2) value should be fairly tight. Can you check the analysis and see if we didn't make a silly out-by-one error in the api.
I agree with your assessment though, let's switch to tail_error(B, 3) and see if anyone complains.
njh
thanks, change from (B, 2) to (B, 3) committed to rev 2159 of lib2geom.
- Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Recent-change-to-ellipse-to-path-conversion... Sent from the Inkscape - Dev mailing list archive at Nabble.com.
participants (4)
-
alvinpenner -
Markus Engel -
mathog -
Nathan Hurst