Quantcast

"Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

"Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Auguste Pop
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,

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Jasper van de Gronde
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.)

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Auguste Pop
On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde <[hidden email]> 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,

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Auguste Pop
On Mon, Aug 12, 2013 at 12:38 PM, Auguste Pop <[hidden email]> wrote:
On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde <[hidden email]> 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,

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user

traditional.png (16K) Download Attachment
comparison.png (13K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Tavmjong Bah
On Mon, 2013-08-12 at 14:07 +0800, Auguste Pop wrote:

> On Mon, Aug 12, 2013 at 12:38 PM, Auguste Pop <[hidden email]>
> wrote:
>         On Mon, Aug 12, 2013 at 12:21 AM, Jasper van de Gronde
>         <[hidden email]> 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









------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Jasper van de Gronde
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.)


------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

alvinpenner
>>  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.20101129231447.00b31828%40vaxxine.com&forum_name=lib2geom-devel

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

Auguste Pop
On Tue, Aug 13, 2013 at 1:56 AM, alvinpenner <[hidden email]> 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

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Inkscape-user mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-user

drawing.svg (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

alvinpenner
arc180_old.svg
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:

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

alvinpenner
sbasis-to-bezier.cpp
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.20101129231447.00b31828%40vaxxine.com&forum_name=lib2geom-devel
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Edit paths by nodes" uses different and wrong approximation of arc as bezier curve.

alvinpenner
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
Loading...