"Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.
Hi
I have noticed an inconsistency between "Edit paths by nodes" and "Object to path".
If we press F4 to draw an rectangle with rounded corner and then use "Object to path" to convert it to path, the rounded corners are approximated by one bezier curve at a corner. The bezier curve uses traditional method which ensures the middle point of the bezier curve is on the arc, and of course the zero and first degree continuity at end points. To put it in maths, for an arc on unit circle of length theta, the distance between first and second control point of the four control points of bezier curve is 4/3*tan(theta/4).
However, if we draw the same rectangle with manual edited path with A/a in path description element d, and use "Edit paths by nodes" to show the nodes, we have different approximation. We can press "Insert new nodes into selected segments" to get the representation in text in "XML Editor". We can see, every corner is represented by two bezier curves. That's not a big problem. The problem is for every bezier curve, the distance between the first and second control point of the four control points of the approximating bezier cuver is theta/3, if we transform the arc onto an unit circle. That's simply wrong.
Should I file a bug report? Please comment.
Best Regards,
On 2013-08-10 07:14, Auguste Pop wrote:
... Should I file a bug report? Please comment.
It is not entirely clear to me in what way the approximation is /wrong/. It is impossible to represent a circular arc using a Bézier curve, and there is thus not one best approximation. In my experience the curves look pretty decent, if you have an example where the approximation is clearly of very bad quality, that would be interesting.
As for the inconsistency, that could indeed be considered a bug. (Although as long as both approximations are of sufficient quality, I wouldn't be too worried.)
On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde < th.v.d.gronde@...226...> wrote:
On 2013-08-10 07:14, Auguste Pop wrote:
... Should I file a bug report? Please comment.
It is not entirely clear to me in what way the approximation is /wrong/. It is impossible to represent a circular arc using a Bézier curve, and there is thus not one best approximation. In my experience the curves look pretty decent, if you have an example where the approximation is clearly of very bad quality, that would be interesting.
As for the inconsistency, that could indeed be considered a bug. (Although as long as both approximations are of sufficient quality, I wouldn't be too worried.)
I said the approximation is "wrong" because there's no literature or resource that I am aware of comes up with this solution. I know an circular arc can not be represented by a cubic bezier curve losslessly. But with a certain criteria, there's certainly a "best" approximation. The "best" approximation may be very difficult to calculate, so we will finally use some "good" answers. The traditional approximation which puts the middle point of bezier curve on the arc is one of the "good" answers. In any case, the approximation used by "Edit path by nodes" is not "good" nor "best".
Of course, this can not be "wrong" as the error is still relatively slow to human eyes. When inkscape is treated as a design tool, this behavior is acceptable. But as a computer program, it is using the "wrong" equation mathematically.
Best regards,
On Mon, Aug 12, 2013 at 12:38 PM, Auguste Pop <auguste@...155...> wrote:
On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde < th.v.d.gronde@...226...> wrote:
On 2013-08-10 07:14, Auguste Pop wrote:
... Should I file a bug report? Please comment.
It is not entirely clear to me in what way the approximation is /wrong/. It is impossible to represent a circular arc using a Bézier curve, and there is thus not one best approximation. In my experience the curves look pretty decent, if you have an example where the approximation is clearly of very bad quality, that would be interesting.
As for the inconsistency, that could indeed be considered a bug. (Although as long as both approximations are of sufficient quality, I wouldn't be too worried.)
I said the approximation is "wrong" because there's no literature or resource that I am aware of comes up with this solution. I know an circular arc can not be represented by a cubic bezier curve losslessly. But with a certain criteria, there's certainly a "best" approximation. The "best" approximation may be very difficult to calculate, so we will finally use some "good" answers. The traditional approximation which puts the middle point of bezier curve on the arc is one of the "good" answers. In any case, the approximation used by "Edit path by nodes" is not "good" nor "best".
Of course, this can not be "wrong" as the error is still relatively slow to human eyes. When inkscape is treated as a design tool, this behavior is acceptable. But as a computer program, it is using the "wrong" equation mathematically.
Best regards,
In order to illustrate how large the error is, I have included a two graphs. These graphs show the absolute error from a point on the bezier curve to the circle. We get the graphs with the assumption that we are approximating a pi/4(45 degrees) arc on an unit circle.
The traditonal.png shows the error when using the traditional method. And the comparison.png shows the both errors from the traditional method and the method i think "wrong". Although the method in question still gives a relatively small error (about one thousandth), it is significantly worse than the traditional method (max error on 10^-6 order).
Best regards,
On Mon, 2013-08-12 at 14:07 +0800, Auguste Pop wrote:
On Mon, Aug 12, 2013 at 12:38 PM, Auguste Pop <auguste@...155...> wrote: On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde <th.v.d.gronde@...226...> wrote:
On 2013-08-10 07:14, Auguste Pop wrote: > ... > Should I file a bug report? Please comment. It is not entirely clear to me in what way the approximation is /wrong/. It is impossible to represent a circular arc using a Bézier curve, and there is thus not one best approximation. In my experience the curves look pretty decent, if you have an example where the approximation is clearly of very bad quality, that would be interesting. As for the inconsistency, that could indeed be considered a bug. (Although as long as both approximations are of sufficient quality, I wouldn't be too worried.) I said the approximation is "wrong" because there's no literature or resource that I am aware of comes up with this solution. I know an circular arc can not be represented by a cubic bezier curve losslessly. But with a certain criteria, there's certainly a "best" approximation. The "best" approximation may be very difficult to calculate, so we will finally use some "good" answers. The traditional approximation which puts the middle point of bezier curve on the arc is one of the "good" answers. In any case, the approximation used by "Edit path by nodes" is not "good" nor "best". Of course, this can not be "wrong" as the error is still relatively slow to human eyes. When inkscape is treated as a design tool, this behavior is acceptable. But as a computer program, it is using the "wrong" equation mathematically. Best regards,In order to illustrate how large the error is, I have included a two graphs. These graphs show the absolute error from a point on the bezier curve to the circle. We get the graphs with the assumption that we are approximating a pi/4(45 degrees) arc on an unit circle.
The traditonal.png shows the error when using the traditional method. And the comparison.png shows the both errors from the traditional method and the method i think "wrong". Although the method in question still gives a relatively small error (about one thousandth), it is significantly worse than the traditional method (max error on 10^-6 order).
Best regards,
A few comments:
1. The SVG spec requires rendering precision to be within 1 px. With regard to the spec, the errors are negligible. Of course, we should do the best we can within reason.
2. SVG 2 will allow markers on rectangles and other shapes. Conversion of shapes to paths should not changes how markers are placed. An ellipse/circle will have four markers, at the top, bottom, and two sides (0, 90, 180, 270 degrees). A rectangle will have four markers if the corners are not rounded and eight markers if they are.
3. Inkscape tends to use Beziers when arcs might be better. In any case, an arc should not be converted to two Bezier path segments as this changes the number of markers.
Tav
On 12-08-13 11:06, Tavmjong Bah wrote:
On Mon, 2013-08-12 at 14:07 +0800, Auguste Pop wrote:
... The traditonal.png shows the error when using the traditional method. And the comparison.png shows the both errors from the traditional method and the method i think "wrong". Although the method in question still gives a relatively small error (about one thousandth), it is significantly worse than the traditional method (max error on 10^-6 order).
In that case, yes, I would indeed call it a bug. (As three orders of magnitude worse approximation using more segments seems like a terribly bad idea.)
...3. Inkscape tends to use Beziers when arcs might be better. In any case, an arc should not be converted to two Bezier path segments as this changes the number of markers. Tav
Summarizing: feel free to submit one or two bugs, stressing that both the approximation quality is inconsistent (and significantly worse), and that Inkscape should not break up an arc into more than one segment. (Thanks for noticing this!)
My guess is that the culprit is either the conversion from arc to sbasis, or the conversion from sbasis to SVG path (which seems to break up sbasis curves which are not sufficiently like a cubic Bézier), or both. But I haven't checked this yet.
BTW, it might be worth it to also look at how close the approximations are to the arc-length parameterization. When converting an arc to a Bézier, it might be important to stay close to the parameterization of the arc. (Although I guess it's not used that much.)
However, if we draw the same rectangle with manual edited path with A/a
in path description element d, and use "Edit paths by nodes" to show the nodes, we have different approximation. We can press "Insert new nodes into selected segments" to get the representation in text in "XML Editor
- could you attach a sample file to illustrate the manually edited path? It is not clear how this example was produced. - which version of Inkscape? current trunk shows four options under "Insert new nodes into selected segments". The options are: min x, max x, min y, max y. Does it matter which option is used?
- there has been some previous discussion of a related issue: - see https://bugs.launchpad.net/inkscape/+bug/653315 - and http://inkscape.13.x6.nabble.com/rendering-arcs-Bug-653315-td2856040.html - and http://sourceforge.net/mailarchive/forum.php?thread_name=3.0.5.32.2010112923...
I think the main question will be whether the relevant code is found in Inkscape trunk or whether it is part of lib2geom. Fixing it in Inkscape trunk is relatively easy, and has been done before, for example: https://bugs.launchpad.net/inkscape/+bug/332735
Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Edit-paths-by-nodes-uses-different-and-wron... Sent from the Inkscape - User mailing list archive at Nabble.com.
On Tue, Aug 13, 2013 at 1:56 AM, alvinpenner <penner@...2467...> wrote:
However, if we draw the same rectangle with manual edited path with A/a
in path description element d, and use "Edit paths by nodes" to show the nodes, we have different approximation. We can press "Insert new nodes into selected segments" to get the representation in text in "XML Editor
- could you attach a sample file to illustrate the manually edited path? It
is not clear how this example was produced.
- which version of Inkscape? current trunk shows four options under "Insert
new nodes into selected segments". The options are: min x, max x, min y, max y. Does it matter which option is used?
i have included a sample svg file.
upper two drawings are the original rectangle/path. lower two drawings are converted so that they don't have arcs in it.
the round corner rectangle is converted to path by "Object to path", and the lower right path is converted by first click "Edit path by nodes" from the left toolbar, and then click the first tool button (Insert new nodes into selected segments) from the newly emerged toolbar at the top. the tool button is pressed so that we can see the converted path in xml editor. but actually, even before using that, we can see on the screen that the arcs in rectangle corner are each converted to two bezier curves. we just don't know the numerical values of the resulting bezier curves.
best regards
arc180_old.svg http://inkscape.13.x6.nabble.com/file/n4967687/arc180_old.svg arc180_org.svg http://inkscape.13.x6.nabble.com/file/n4967687/arc180_org.svg
Thanks for the demo files, they illustrate the problem well. I'm just writing to confirm your calculations, and propose a solution. Attached are two demo files. The file arc180_org.svg contains two arcs, both 180 degrees, both with radius 200. The two arcs are identical except that, in the bottom arc, I have deleted all the sodipodi attributes manually. This makes the bottom arc render differently. The difference can be seen by clicking F2.
The second file, arc180_old.svg, contains the same two arcs after being converted to Bezier form. The top one was converted using 'Path->Object To Path', and the bottom one was converted using the 'Insert new nodes' button, as you discovered. The Bezier data confirms your conclusions:
Top arc: 2 Beziers, 90 degrees each, Bezier control arm length = 110.45694. This is consistent with the formula : (4/3)*tan(theta/4).
Bottom arc: 8 Beziers, 22.5 degrees each, Bezier control arm length = 26.17994. This is consistent with the formula : theta/3.
Proposed solution below:
-- View this message in context: http://inkscape.13.x6.nabble.com/Edit-paths-by-nodes-uses-different-and-wron... Sent from the Inkscape - User mailing list archive at Nabble.com.
sbasis-to-bezier.cpp http://inkscape.13.x6.nabble.com/file/n4967688/sbasis-to-bezier.cpp sbasis-to-bezier.h http://inkscape.13.x6.nabble.com/file/n4967688/sbasis-to-bezier.h
attached are two files: sbasis-to-bezier.h and sbasis-to-bezier.cpp. They are from the directory \src\2geom. They are slightly updated versions of the proposal originally made at: http://sourceforge.net/mailarchive/forum.php?thread_name=3.0.5.32.2010112923... The updates are just to make them compatible with current trunk code. They contain a modified procedure of producing a Bezier curve from an sbasis curve, one which makes use of the value of the function at the midpoint.
-- View this message in context: http://inkscape.13.x6.nabble.com/Edit-paths-by-nodes-uses-different-and-wron... Sent from the Inkscape - User mailing list archive at Nabble.com.
arc180_new.svg http://inkscape.13.x6.nabble.com/file/n4967689/arc180_new.svg
after compiling Inkscape with this new function, the original file arc180_org.svg was reloaded and converted to Beziers as before, to produce the file arc180_new.svg, attached here. In the file arc180_new.svg, the top arc is identical to the original version, as expected. The bottom arc now has a typical Bezier control arm length of 26.26437, which is consistent with the formula (4/3)*tan(theta/4), as desired.
The two types of arcs are now rendered using the same approximation method, as hoped for. However, it is not possible to commit this change directly to the Inkscape repository. Since the change occurs in lib2geom code, it will be necessary for the proposed change to be reviewed by someone in that development group.
Alvin
-- View this message in context: http://inkscape.13.x6.nabble.com/Edit-paths-by-nodes-uses-different-and-wron... Sent from the Inkscape - User mailing list archive at Nabble.com.
participants (4)
-
alvinpenner -
Auguste Pop -
Jasper van de Gronde -
Tavmjong Bah